Converting TSP(Travelling Salesman Problem) to CVRP(Capacitated Vehicle Routing Problem) using AS (Ant system).
9 ビュー (過去 30 日間)
古いコメントを表示
Respected Sir/Madam,
I have tried to convert the TSP matlab code to CVRP code using ant system optimization, but due to some reason i am not getting the feasible results. Can you please point out where i am going wrong and suggest measures in order to correct the code to acheive results for CVRP dataset.
clear;clc;
%INITIALIZE DATA
nodes = csvread('CMT151.csv')';
demand = csvread('Demand_51.csv')';
%PARAMETER SETTING
MAX_ITERATION = 1000;
alpha = 1;
beta = 5;
rho = 0.5;
Q_int = 100;
Vehicle_capacity = 160;
demand_points = demand;
iteration = 1;
number_of_nodes = size(nodes, 2);
number_of_ants = number_of_nodes;
%mtip = ceil(sum(demand)/Vehicle_capacity);
%mstep = number_of_nodes + mtip;
distance = dist(nodes);
visibility = 1./distance;
shortest_path = zeros(1, number_of_nodes+1);
shortest_distance_each_iteration = zeros(MAX_ITERATION, 1);
shortest_distance_all_iteration = zeros(MAX_ITERATION, 1);
%load = zeros(demand);
% CALCULATION OF PHEROMONE MATRIX
visited_nodes = zeros(1, number_of_nodes);
unvisited_nodes = colon(1, number_of_nodes);
% compute Lnn
Lnn = 0;
for n = 1: number_of_nodes
if n ==1
visited_nodes(n) = floor(rand()*number_of_nodes+1);
tempLnn = visited_nodes;
tempLnn(tempLnn == 0) = [];
unvisited_nodes(unvisited_nodes == tempLnn) = [];
else
distance_temp = zeros(1, size(unvisited_nodes, 2));
for i = 1:size(unvisited_nodes, 2)
if visited_nodes(n-1) ~= unvisited_nodes(i)
distance_temp(unvisited_nodes(i)) = distance(visited_nodes(n-1), unvisited_nodes(i));
end
end
distance_temp(distance_temp == 0) = NaN;
founded = find(distance_temp == min(distance_temp));
Lnn = Lnn + min(distance_temp);
visited_nodes(n) = founded(1);
unvisited_nodes(find(unvisited_nodes == founded(1))) = [];
end
end % END OF Lnn CALCULATION
initial_tao = 1/(number_of_nodes*Lnn);
tao = ones(number_of_nodes, number_of_nodes) * initial_tao;
while iteration <= MAX_ITERATION
s = 1;
tabu = zeros(number_of_ants, number_of_nodes+1); % save the route of each ant
depot =1;
% Initilization of nodes to ants
tabu(:,1) = depot;
%fill tabu
while s <= number_of_nodes
s = s + 1; % s = tabu index to be filled
for k = 1:number_of_ants
if s == (number_of_nodes+1) % last tabu, fill it with initial node
tabu(:, end) = tabu(:, 1);
else
% determine the next node to be visited
probability = zeros(1, number_of_nodes); % probability initialization, certain column in probability matrix = the probability in those city
temp = colon(1, number_of_nodes); % matrix for unvisited node
tabu1 = tabu(k, 1:end-1); % create clone of tabu
tabu1(tabu1 == 0) = []; % remove visited node
temp(tabu1) = []; % remove visited node
for x = 1:size(temp, 2) % looping 1 until total nodes
probability(1, temp(x)) = tao(tabu(k, s-1), temp(x))^alpha * visibility(tabu(k, s-1), temp(x))^beta;
end
probability = probability./sum(probability);
% choose the next node based on probability
sorted = sort(probability);
range = cumsum(sorted);
randomResult = rand();
founded1 = find(probability == sorted(max(find(range <= randomResult))+1));
tabu(k, s) = founded1(floor((rand()*size(founded1, 2))+1)); % random when there're the same probabilities
% Is the Route feasible????
if sum(demand_points(tabu(k,s))) <= Vehicle_capacity
disp('Condition is satisfied');
else
tabu(k,s) = depot;
end
end
end
end
% calculate the distance
distance_of_ants_tour = zeros(number_of_ants, 1);
for k=1:number_of_ants
for x = 1:number_of_nodes
distance_of_ants_tour(k, 1) = distance_of_ants_tour(k, 1) + (distance(tabu(k, x), tabu(k, x+1)));
end
end
% update best global solution (best of all iteration)
founded = find(distance_of_ants_tour' == min(distance_of_ants_tour));
if iteration == 1
shortest_path = tabu(founded(1), :);
shortest_distance_all_iteration(iteration) = min(distance_of_ants_tour);
else
if min(distance_of_ants_tour) < shortest_distance_all_iteration(iteration-1)
shortest_path = tabu(founded(1), :);
shortest_distance_all_iteration(iteration) = min(distance_of_ants_tour);
else
shortest_distance_all_iteration(iteration) = shortest_distance_all_iteration(iteration-1);
end
end
% update best local solution (best of certain iteration)
shortest_distance_each_iteration(iteration) = min(distance_of_ants_tour);
% update delta tao of each iteration (global update)
delta_tao = zeros(number_of_nodes, number_of_nodes);
tao_addition_of_every_ant = Q_int ./ distance_of_ants_tour;
for k = 1:number_of_ants
for x = 1:(number_of_nodes)
delta_tao(tabu(k, x), tabu(k, x+1)) = delta_tao(tabu(k, x), tabu(k, x+1)) + tao_addition_of_every_ant(k);
delta_tao(tabu(k, x+1), tabu(k, x)) = delta_tao(tabu(k, x), tabu(k, x+1));
end
end
tao = (tao.*rho) + delta_tao;
fprintf('iteration: %d/%d | shortest distance of all iteration: %d \n', iteration, MAX_ITERATION, shortest_distance_all_iteration(iteration));
iteration = iteration + 1;
end
close
f = figure;
subplot(1, 2, 1);
plot([1:MAX_ITERATION]', shortest_distance_each_iteration(:, 1)');
title('Shortest Distance Each Iteration');
xlabel('Iterations');
ylabel('Shortest Distance');
subplot(1, 2, 2);
plot([1:MAX_ITERATION]', shortest_distance_all_iteration(:, 1)');
title('Shortest Distance All Iteration');
xlabel('Iterations');
ylabel('Shortest Distance');
drawnow
set(f, 'position', [200, 200, 700, 300]);
disp(shortest_path);
disp(shortest_distance_all_iteration(MAX_ITERATION));
0 件のコメント
採用された回答
imen ben haj
2021 年 7 月 22 日
Hello !
Can you give me access to the csv file
Thank you in advance for your answer.
その他の回答 (0 件)
参考
カテゴリ
Help Center および File Exchange で Traveling Salesman (TSP) についてさらに検索
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!