Finds a nearoptimal solution to a MTSP using a GA
MTSP_GA Multiple Traveling Salesmen Problem (MTSP) Genetic Algorithm (GA)
Finds a (near) optimal solution to the MTSP by setting up a GA to search
for the shortest route (least distance needed for the salesmen to travel
to each city exactly once and return to their starting locations)
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 citytocity 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 userdefined 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:n1);
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);
1.3  Major overhaul of input/output interface. 

1.2  Minor cosmetic updates. 

1.1  Added 3D capability. 

updated help notes, description 

Fixed waitbar issues. 
Joseph Kirk (view profile)
@Olivia, I do not currently have a simple way to enforce path constraints in my code, sorry!
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 (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 bestoffour citizen: flip, swap, and slide. I make copies of the bestoffour 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 (view profile)
sir what if we are to take the data from solomon's bench mark sheets.
vrehani@yahoo.com
Bharath (view profile)
Could someone tell me where can I get the code for solving the same MTSP using ACO in MATLAB?
Joseph Kirk (view profile)
Abdullah, try this one:
http://www.mathworks.com/matlabcentral/fileexchange/21299
Abdullah Alomari (view profile)
What if I want all of the salesman start from the same point?
Thanks
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 (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 bestoffour citizen: flip, swap, and slide. I make copies of the bestoffour 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 (view profile)
can someone please tell me why POP_SIZE must be divisible by 8? Please! thank you!
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.
good
Update: The SINGLES parameter has been replaced with a more generalized MIN_TOUR.
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.
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.
good tool but very simple and dont new approach
Neat tool. Easy to use.
nice ,great!
What a great calculation engine, really appreciate your work. I am one of Evolutionary Approach Fans too.
The waitbar glitch should be fixed.
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.