Converting TSP(Travelling Salesman Problem) to CVRP(Capacitated Vehicle Routing Problem) using AS (Ant system).

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));

Answer 1

[imen ben haj]

Hello !

Can you give me access to the csv file

Thank you in advance for your answer.

[ANURAG DEEPAK]

Yes of course Imen ben haj. Please help me to convert it.

[imen ben haj]

I want to try