Skip to content

Instantly share code, notes, and snippets.

@zhezheng

zhezheng/NSGA.m

Last active December 25, 2015 06:09
Show Gist options
  • Save zhezheng/6929924 to your computer and use it in GitHub Desktop.
Save zhezheng/6929924 to your computer and use it in GitHub Desktop.
Download ZIP
Vehicle Routing Problem Using NSGA-II Algorithm
Raw
NSGA.m
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