Last active
December 25, 2015 06:09
-
-
Save zhezheng/6929924 to your computer and use it in GitHub Desktop.
Vehicle Routing Problem Using NSGA-II Algorithm
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
clc; | |
clear; | |
last = []; | |
pop = 10; | |
path = zeros(pop,20); | |
dis = zeros(20,20); | |
order1 = zeros(10,26); | |
c = [0.6606,0.9695,0.5906,0.2124,0.0398,0.1367,0.9536,0.6091,0.8767,0.8148,0.3876,0.7041,0.0213,0.3429,0.7471,0.5449,0.9464,0.1247,0.1636,0.8668;0.9500,0.6740,0.5029,0.8274,0.9697,0.5979,0.2184,0.7148,0.2395,0.2867,0.8200,0.3296,0.1649,0.3025,0.8192,0.9392,0.8191,0.4351,0.8646,0.6768]; | |
f = zeros(10,4); | |
qd = [45,25,29,65,17,60,15,40,55,35,50,38,35,15,20,40,19,28,30,41]; %Quantity Demanded | |
for i = 1:20 %distance matrix | |
for j = 1:20 | |
dis(i,j) = sqrt((c(1,i)-c(1,j))^2 + (c(2,i)-c(2,j))^2); | |
end | |
end | |
%% populaion initialize | |
for i = 1:pop | |
path(i,:) = randperm(20); | |
end | |
%path for each car | |
for i = 1:pop %pop = 10 | |
weight = 0; | |
num = 1; | |
order = [0]; | |
for x_1 = 1:20 %for one solution | |
weight = weight + qd(path(i,x_1)); %weight car can carry | |
if weight <= 250 | |
order = [order path(i,x_1)]; | |
else | |
num = num + 1; | |
weight = qd(x_1); | |
order = [order 0 path(i,x_1)]; | |
end | |
end | |
f(i,1) = num; | |
order1(i,1:length(order)) = order; | |
end | |
f = [f order1]; | |
%% total distance and max single car distance | |
gdis = 0; %gobal max car distance | |
pdis = 0; %personal max car distance | |
for i = 1:pop | |
for j = 1:25 | |
if order1(i,j) == 0 && order1(i,j+1) ~= 0 | |
f(i,2) = f(i,2) + sqrt((0.5 - c(1,order1(i,j+1)))^2 + (0.5 - c(2,order1(i,j+1)))^2); | |
pdis = sqrt((0.5 - c(1,order1(i,j+1)))^2 + (0.5 - c(2,order1(i,j+1)))^2); | |
elseif order1(i,j) ~= 0 && order1(i,j+1) ~= 0 | |
f(i,2) = f(i,2) + dis(order1(i,j),order1(i,j+1)); | |
pdis = pdis + dis(order1(i,j),order1(i,j+1)); | |
elseif order1(i,j) ~= 0 && order1(i,j+1) == 0 | |
f(i,2) = f(i,2) + sqrt((0.5 - c(1,order1(i,j)))^2 + (0.5 - c(2,order1(i,j)))^2); | |
pdis = pdis + sqrt((0.5 - c(1,order1(i,j)))^2 + (0.5 - c(2,order1(i,j)))^2); | |
end | |
if pdis > gdis | |
gdis = pdis; | |
end | |
end | |
f(i,3) = gdis; | |
gdis = 0; | |
end | |
%% Non-Dominated sort. | |
[N, m] = size(f); | |
clear m | |
% Initialize the front number to 1. | |
front = 1; | |
F(front).f = []; | |
individual = []; | |
N = pop; | |
M = 2; | |
V = 1; | |
for i = 1 : N | |
% Number of individuals that dominate this individual | |
individual(i).n = 0; | |
% Individuals which this individual dominate | |
individual(i).p = []; | |
for j = 1 : N | |
dom_less = 0; | |
dom_equal = 0; | |
dom_more = 0; | |
for k = 1 : M | |
if (f(i,V + k) < f(j,V + k)) | |
dom_less = dom_less + 1; | |
elseif (f(i,V + k) == f(j,V + k)) | |
dom_equal = dom_equal + 1; | |
else | |
dom_more = dom_more + 1; | |
end | |
end | |
if dom_less == 0 && dom_equal ~= M | |
individual(i).n = individual(i).n + 1; | |
elseif dom_more == 0 && dom_equal ~= M | |
individual(i).p = [individual(i).p j]; | |
end | |
end | |
if individual(i).n == 0 | |
f(i,M + V + 1) = 1; | |
F(front).f = [F(front).f i]; | |
end | |
end | |
% Find the subsequent fronts | |
while ~isempty(F(front).f) | |
Q = []; | |
for i = 1 : length(F(front).f) | |
if ~isempty(individual(F(front).f(i)).p) | |
for j = 1 : length(individual(F(front).f(i)).p) | |
individual(individual(F(front).f(i)).p(j)).n = ... | |
individual(individual(F(front).f(i)).p(j)).n - 1; | |
if individual(individual(F(front).f(i)).p(j)).n == 0 | |
f(individual(F(front).f(i)).p(j),M + V + 1) = ... | |
front + 1; | |
Q = [Q individual(F(front).f(i)).p(j)]; | |
end | |
end | |
end | |
end | |
front = front + 1; | |
F(front).f = Q; | |
end | |
[temp,indef_of_fronts] = sort(f(:,M + V + 1)); | |
for i = 1 : length(indef_of_fronts) | |
sorted_based_on_front(i,:) = f(indef_of_fronts(i),:); | |
end | |
for i = 1:pop | |
if f(i,4) == 1 | |
last = [last;f(i,:)]; | |
end | |
end | |
%% populaion evolution | |
for max = 1:1000 | |
f = zeros(10,4); | |
for i = 1:pop | |
for j = 1:20 | |
rnum = randint(1,1,[1,20]); | |
if rand < 0.2 %mutation, get new path | |
path_1 = path(i,j); | |
path(i,j) = path(i,rnum); | |
path(i,rnum) = path_1; | |
end | |
end | |
end | |
%path for each car | |
for i = 1:pop %pop = 10 | |
weight = 0; | |
num = 1; | |
order = [0]; | |
for x_1 = 1:20 %for one solution | |
weight = weight + qd(path(i,x_1)); %weight car can carry | |
if weight <= 250 | |
order = [order path(i,x_1)]; | |
else | |
num = num + 1; | |
weight = qd(x_1); | |
order = [order 0 path(i,x_1)]; | |
end | |
end | |
f(i,1) = num; | |
order1(i,1:length(order)) = order; | |
end | |
f = [f order1]; | |
% total distance and max single car distance | |
gdis = 0; %gobal max car distance | |
pdis = 0; %personal max car distance | |
for i = 1:pop | |
for j = 1:25 | |
if order1(i,j) == 0 && order1(i,j+1) ~= 0 | |
f(i,2) = f(i,2) + sqrt((0.5 - c(1,order1(i,j+1)))^2 + (0.5 - c(2,order1(i,j+1)))^2); | |
pdis = sqrt((0.5 - c(1,order1(i,j+1)))^2 + (0.5 - c(2,order1(i,j+1)))^2); | |
elseif order1(i,j) ~= 0 && order1(i,j+1) ~= 0 | |
f(i,2) = f(i,2) + dis(order1(i,j),order1(i,j+1)); | |
pdis = pdis + dis(order1(i,j),order1(i,j+1)); | |
elseif order1(i,j) ~= 0 && order1(i,j+1) == 0 | |
f(i,2) = f(i,2) + sqrt((0.5 - c(1,order1(i,j)))^2 + (0.5 - c(2,order1(i,j)))^2); | |
pdis = pdis + sqrt((0.5 - c(1,order1(i,j)))^2 + (0.5 - c(2,order1(i,j)))^2); | |
end | |
if pdis > gdis | |
gdis = pdis; | |
end | |
end | |
f(i,3) = gdis; | |
gdis = 0; | |
end | |
[N, m] = size(f); | |
clear m | |
% Initialize the front number to 1. | |
front = 1; | |
F(front).f = []; | |
individual = []; | |
N = pop; | |
M = 2; | |
V = 1; | |
for i = 1 : N | |
% Number of individuals that dominate this individual | |
individual(i).n = 0; | |
% Individuals which this individual dominate | |
individual(i).p = []; | |
for j = 1 : N | |
dom_less = 0; | |
dom_equal = 0; | |
dom_more = 0; | |
for k = 1 : M | |
if (f(i,V + k) < f(j,V + k)) | |
dom_less = dom_less + 1; | |
elseif (f(i,V + k) == f(j,V + k)) | |
dom_equal = dom_equal + 1; | |
else | |
dom_more = dom_more + 1; | |
end | |
end | |
if dom_less == 0 && dom_equal ~= M | |
individual(i).n = individual(i).n + 1; | |
elseif dom_more == 0 && dom_equal ~= M | |
individual(i).p = [individual(i).p j]; | |
end | |
end | |
if individual(i).n == 0 | |
f(i,M + V + 1) = 1; | |
F(front).f = [F(front).f i]; | |
end | |
end | |
% Find the subsequent fronts | |
while ~isempty(F(front).f) | |
Q = []; | |
for i = 1 : length(F(front).f) | |
if ~isempty(individual(F(front).f(i)).p) | |
for j = 1 : length(individual(F(front).f(i)).p) | |
individual(individual(F(front).f(i)).p(j)).n = ... | |
individual(individual(F(front).f(i)).p(j)).n - 1; | |
if individual(individual(F(front).f(i)).p(j)).n == 0 | |
f(individual(F(front).f(i)).p(j),M + V + 1) = ... | |
front + 1; | |
Q = [Q individual(F(front).f(i)).p(j)]; | |
end | |
end | |
end | |
end | |
front = front + 1; | |
F(front).f = Q; | |
end | |
[temp,indef_of_fronts] = sort(f(:,M + V + 1)); | |
for i = 1 : length(indef_of_fronts) | |
sorted_based_on_front(i,:) = f(indef_of_fronts(i),:); | |
end | |
for i = 1:pop | |
if f(i,4) == 1 | |
last = [last;f(i,:)]; | |
end | |
end | |
if ~mod(max,10) | |
clc | |
fprintf('%d generations completed\n',max); | |
end | |
end | |
f = last; | |
%% finally sorting | |
front = 1; | |
F(front).f = []; | |
individual = []; | |
N = size(f,1); | |
M = 2; | |
V = 1; | |
for i = 1 : N | |
% Number of individuals that dominate this individual | |
individual(i).n = 0; | |
% Individuals which this individual dominate | |
individual(i).p = []; | |
for j = 1 : N | |
dom_less = 0; | |
dom_equal = 0; | |
dom_more = 0; | |
for k = 1 : M | |
if (f(i,V + k) < f(j,V + k)) | |
dom_less = dom_less + 1; | |
elseif (f(i,V + k) == f(j,V + k)) | |
dom_equal = dom_equal + 1; | |
else | |
dom_more = dom_more + 1; | |
end | |
end | |
if dom_less == 0 && dom_equal ~= M | |
individual(i).n = individual(i).n + 1; | |
elseif dom_more == 0 && dom_equal ~= M | |
individual(i).p = [individual(i).p j]; | |
end | |
end | |
if individual(i).n == 0 | |
f(i,M + V + 1) = 1; | |
F(front).f = [F(front).f i]; | |
end | |
end | |
% Find the subsequent fronts | |
while ~isempty(F(front).f) | |
Q = []; | |
for i = 1 : length(F(front).f) | |
if ~isempty(individual(F(front).f(i)).p) | |
for j = 1 : length(individual(F(front).f(i)).p) | |
individual(individual(F(front).f(i)).p(j)).n = ... | |
individual(individual(F(front).f(i)).p(j)).n - 1; | |
if individual(individual(F(front).f(i)).p(j)).n == 0 | |
f(individual(F(front).f(i)).p(j),M + V + 1) = ... | |
front + 1; | |
Q = [Q individual(F(front).f(i)).p(j)]; | |
end | |
end | |
end | |
end | |
front = front + 1; | |
F(front).f = Q; | |
end | |
[temp,indef_of_fronts] = sort(f(:,M + V + 1)); | |
for i = 1 : length(indef_of_fronts) | |
sorted_based_on_front(i,:) = f(indef_of_fronts(i),:); | |
end | |
final_sort = []; | |
for i = 1:size(f,1) | |
if f(i,4) == 1 | |
final_sort = [final_sort;f(i,:)]; | |
end | |
end | |
%% plot the result | |
figure(1) | |
%[a,b] = min(final_sort(:,2)); | |
plot(0.5,0.5,'o'); %set center | |
hold on; | |
for i = 1:20 %plot the city | |
plot(c(1,i),c(2,i),'*'); | |
hold on; | |
ylim('manual'); ylim([0, 1]); | |
xlim('manual'); xlim([0, 1]); | |
end | |
for i = 5:29 | |
if final_sort(b,i) == 0 && final_sort(b,i+1) ~=0 | |
plot([0.5;c(1,final_sort(b,i+1))],[0.5;c(2,final_sort(b,i+1))]); | |
elseif final_sort(b,i) ~= 0 && final_sort(b,i+1) ~=0 | |
plot([c(1,final_sort(b,i));c(1,final_sort(b,i+1))],[c(2,final_sort(b,i));c(2,final_sort(b,i+1))]); | |
elseif final_sort(b,i) ~= 0 && final_sort(b,i+1) ==0 | |
plot([c(1,final_sort(b,i));0.5],[c(2,final_sort(b,i));0.5]); | |
end | |
end | |
%% plot the front | |
figure(2) | |
for i = 1:size(final_sort,1) | |
plot(final_sort(i,2),final_sort(i,3),'*'); | |
hold on; | |
xlim('manual'); xlim([0, 15]); | |
ylim('manual'); ylim([0, 5]); | |
end | |
num = abs(final_sort(b,1)); | |
total_dis = final_sort(b,2); | |
sigle_dis = final_sort(b,3); | |
disp(num); | |
disp(total_dis); | |
disp(sigle_dis); |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment