Code covered by the BSD License

### Highlights from Multiple Traveling Salesmen Problem - Genetic Algorithm

4.42857
4.4 | 15 ratings Rate this file 16 Downloads (last 30 days) File Size: 13.7 KB File ID: #19049 Version: 1.3

# Multiple Traveling Salesmen Problem - Genetic Algorithm

### Joseph Kirk (view profile)

04 Mar 2008 (Updated )

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

File Information
Description

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

Required Products MATLAB
MATLAB release MATLAB 8.3 (R2014a)
06 Jun 2016 Joseph Kirk

### Joseph Kirk (view profile)

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

Comment only
24 May 2016 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

05 Oct 2014 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)."}

24 Apr 2013 virat rehani

### virat rehani (view profile)

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

24 Nov 2012 Bharath

### Bharath (view profile)

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

27 Mar 2012 Joseph Kirk

### Joseph Kirk (view profile)

Abdullah, try this one:
http://www.mathworks.com/matlabcentral/fileexchange/21299

Comment only
26 Mar 2012 Abdullah Alomari

### Abdullah Alomari (view profile)

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

Thanks

29 Dec 2011 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?

Comment only
05 May 2011 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).

Comment only
04 May 2011 tim

### tim (view profile)

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

06 Jul 2010 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.

03 Oct 2008 venugopal rachakonda

good

01 Oct 2008 The Author

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

Comment only
25 Sep 2008 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.

Comment only
25 Sep 2008 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.

24 Sep 2008 Erick Rojas

good tool but very simple and dont new approach

18 Aug 2008 Sumana Srinivasan

Neat tool. Easy to use.

23 Jun 2008 Stefan Simon
04 May 2008 wayne wang

nice ,great!

23 Apr 2008 Ronald Halim

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

13 Mar 2008 The Author

The waitbar glitch should be fixed.

Comment only
05 Mar 2008 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.

07 Mar 2008

Fixed waitbar issues.

02 Sep 2008

updated help notes, description

02 Jun 2009 1.1