File Exchange

Multiple Traveling Salesmen Problem - Genetic Algorithm

version 1.3.0.0 (13.7 KB) by Joseph Kirk

Joseph Kirk (view profile)

Finds a near-optimal solution to a M-TSP using a GA

Updated 06 May 2014

MTSP_GA Multiple Traveling Salesmen Problem (M-TSP) Genetic Algorithm (GA)
Finds a (near) optimal solution to the M-TSP by setting up a GA to search
for the shortest route (least distance needed for the salesmen to travel
Summary:
1. Each salesman travels to a unique set of cities and completes the
route by returning to the city he started from
2. Each city is visited by exactly one salesman

Input:
USERCONFIG (structure) with zero or more of the following fields:
- XY (float) is an Nx2 matrix of city locations, where N is the number of cities
- DMAT (float) is an NxN matrix of city-to-city distances or costs
- NSALESMEN (scalar integer) is the number of salesmen to visit the cities
- MINTOUR (scalar integer) is the minimum tour length for any of the salesmen
- POPSIZE (scalar integer) is the size of the population (should be divisible by 8)
- NUMITER (scalar integer) is the number of desired iterations for the algorithm to run
- SHOWPROG (scalar logical) shows the GA progress if true
- SHOWRESULT (scalar logical) shows the GA results if true
- SHOWWAITBAR (scalar logical) shows a waitbar if true

Input Notes:
1. Rather than passing in a structure containing these fields, any/all of
these inputs can be passed in as parameter/value pairs in any order instead.
2. Field/parameter names are case insensitive but must match exactly otherwise.

Output:
RESULTSTRUCT (structure) with the following fields:
(in addition to a record of the algorithm configuration)
- OPTROUTE (integer array) is the best route found by the algorithm
- OPTBREAK (integer array) is the list of route break points (these specify the indices
into the route used to obtain the individual salesman routes)
- MINDIST (scalar float) is the total distance traveled by the salesmen

Route/Breakpoint Details:
If there are 10 cities and 3 salesmen, a possible route/break
combination might be: rte = [5 6 9 1 4 2 8 10 3 7], brks = [3 7]
Taken together, these represent the solution [5 6 9][1 4 2 8][10 3 7],
which designates the routes for the 3 salesmen as follows:
. Salesman 1 travels from city 5 to 6 to 9 and back to 5
. Salesman 2 travels from city 1 to 4 to 2 to 8 and back to 1
. Salesman 3 travels from city 10 to 3 to 7 and back to 10

Usage:
mtsp_ga
-or-
mtsp_ga(userConfig)
-or-
resultStruct = mtsp_ga;
-or-
resultStruct = mtsp_ga(userConfig);
-or-
[...] = mtsp_ga('Param1',Value1,'Param2',Value2, ...);

Example:
% Let the function create an example problem to solve
mtsp_ga;

Example:
% Request the output structure from the solver
resultStruct = mtsp_ga;

Example:
% Pass a random set of user-defined XY points to the solver
userConfig = struct('xy',10*rand(35,2));
resultStruct = mtsp_ga(userConfig);

Example:
% Pass a more interesting set of XY points to the solver
n = 50;
phi = (sqrt(5)-1)/2;
theta = 2*pi*phi*(0:n-1);
rho = (1:n).^phi;
[x,y] = pol2cart(theta(:),rho(:));
xy = 10*([x y]-min([x;y]))/(max([x;y])-min([x;y]));
userConfig = struct('xy',xy);
resultStruct = mtsp_ga(userConfig);

Example:
% Pass a random set of 3D (XYZ) points to the solver
xyz = 10*rand(35,3);
userConfig = struct('xy',xyz);
resultStruct = mtsp_ga(userConfig);

Example:
% Change the defaults for GA population size and number of iterations
userConfig = struct('popSize',200,'numIter',1e4);
resultStruct = mtsp_ga(userConfig);

Example:
% Turn off the plots but show a waitbar
userConfig = struct('showProg',false,'showResult',false,'showWaitbar',true);
resultStruct = mtsp_ga(userConfig);

Christoph Aoun

Christoph Aoun (view profile)

Hello,
Is there a possibility for adding a relaxation for the formulation of the problem with a variable number of salesmen while having a upper limit to the distance each salesman should travel?

David Franco

Perfect!

Joseph Kirk

Joseph Kirk (view profile)

@Olivia, I do not currently have a simple way to enforce path constraints in my code, sorry!

Olivia Bordeu

Olivia Bordeu (view profile)

Hi Joseph!

I've been using your code and it has work perfectly, thank you!

My problem now is that I want to avoid routes between some specific cities but, even putting a really high cost in dmat, sometimes the solution contains that combination I want to prohibit. That doesn't make much sense but since it has a random component I guess it can happen.

Do you have a better solution?

Thank you!

Olivia

virat rehani

virat rehani (view profile)

Thanks to the idea of Mr.Josph Kirk and my co- guide (Mr.U. Sharma) for the following suggestion and implementation with figure 4 instead of 8.

{"tim: POP_SIZE must be divisible by 8 because of the way good solutions in the current population are propagated to the next iteration.

(I randomly group 8 citizens at a time, take the best one of those eight, and pass it on to the next generation. I then perform 3 different mutations on that best-of-four citizen: flip, swap, and slide. I make copies of the best-of-four and three mutated versions and mix up the length of the salesmen routes for each. The seven modified solutions are then passed on to the next generation)."}

virat rehani

virat rehani (view profile)

sir what if we are to take the data from solomon's bench mark sheets.
vrehani@yahoo.com

Bharath

Bharath (view profile)

Could someone tell me where can I get the code for solving the same MTSP using ACO in MATLAB?

Joseph Kirk

Abdullah Alomari

Abdullah Alomari (view profile)

What if I want all of the salesman start from the same point?

Thanks

Anatoly

Anatoly (view profile)

And it’s of interest – does evolutionary nature of the search algorithm has any amenity over simple random search in terms of fitness function evaluations count (=computation time) or quality of solution?

Joseph Kirk

Joseph Kirk (view profile)

tim: POP_SIZE must be divisible by 8 because of the way good solutions in the current population are propagated to the next iteration.

(I randomly group 8 citizens at a time, take the best one of those eight, and pass it on to the next generation. I then perform 3 different mutations on that best-of-four citizen: flip, swap, and slide. I make copies of the best-of-four and three mutated versions and mix up the length of the salesmen routes for each. The seven modified solutions are then passed on to the next generation).

tim

tim (view profile)

can someone please tell me why POP_SIZE must be divisible by 8? Please! thank you!

Sumana Srinivasan

Sumana Srinivasan (view profile)

When you say (near) optimal, have you used any standard benchmarks to quantify how close the solution is to the optimal? Thank you for your response in advance.

venugopal rachakonda

good

The Author

Update: The SINGLES parameter has been replaced with a more generalized MIN_TOUR.

The Author

João, I'm not using a binary string/word to represent the various possible solutions, if that's what you mean, but that doesn't exclude it from being a GA. GAs can take many forms, but they have (1) an abstract way of representing possible solutions (2) a method for evaluating the fitness or cost of a candidate solution (3) a population of candidate solutions (4) and a method of propagating good solutions while forming new (potentially better) solutions. This file has all of those.

João Silva

As far as I know, this is not a GA, at least not a classical one. But it is very useful as a trying tool with an evolutionary algorithm.

Erick Rojas

good tool but very simple and dont new approach

Sumana Srinivasan

Neat tool. Easy to use.

Stefan Simon

wayne wang

nice ,great!

Ronald Halim

What a great calculation engine, really appreciate your work. I am one of Evolutionary Approach Fans too.

The Author

The waitbar glitch should be fixed.

John D'Errico

These are the submissions that I enjoy finding on the file exchange. This one does what it says it will do, and does it well. Good help. Good example.

There was only one irrelevant glitch - the waitbar on my machine was the wrong size. The end of the waitbar was cut off for some reason.

Despite that - well done.