Code covered by the BSD License  

Highlights from
Multiple Traveling Salesmen Problem - Genetic Algorithm

4.38462

4.4 | 13 ratings Rate this file 66 Downloads (last 30 days) File Size: 4.1 KB File ID: #19049
image thumbnail

Multiple Traveling Salesmen Problem - Genetic Algorithm

by

 

04 Mar 2008 (Updated )

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

| Watch this File

File Information
Description

MTSP_GA Multiple Traveling Salesman 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
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:
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

Output:
OPTRTE (integer array) is the best route found by the algorithm
OPTBRK (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

Example:
n = 35;
xy = 10*rand(n,2);
nSalesmen = 5;
minTour = 3;
popSize = 80;
numIter = 5e3;
a = meshgrid(1:n);
dmat = reshape(sqrt(sum((xy(a,:)-xy(a',:)).^2,2)),n,n);
[optRoute,optBreak,minDist] = mtsp_ga(xy,dmat,nSalesmen,minTour,popSize,numIter,1,1);

Example:
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]));
nSalesmen = 5;
minTour = 3;
popSize = 80;
numIter = 1e4;
a = meshgrid(1:n);
dmat = reshape(sqrt(sum((xy(a,:)-xy(a',:)).^2,2)),n,n);
[optRoute,optBreak,minDist] = mtsp_ga(xy,dmat,nSalesmen,minTour,popSize,numIter,1,1);

Example:
n = 35;
xyz = 10*rand(n,3);
nSalesmen = 5;
minTour = 3;
popSize = 80;
numIter = 5e3;
a = meshgrid(1:n);
dmat = reshape(sqrt(sum((xyz(a,:)-xyz(a',:)).^2,2)),n,n);
[optRoute,optBreak,minDist] = mtsp_ga(xyz,dmat,nSalesmen,minTour,popSize,numIter,1,1);

Acknowledgements

Traveling Salesman Problem Genetic Algorithm inspired this file.

This file inspired Multiple Variable Traveling Salesmen Problem Genetic Algorithm, Open Multiple Traveling Salesmen Problem Genetic Algorithm, Fixed Start Open Multiple Traveling Salesmen Problem Genetic Algorithm, Fixed Endpoints Open Multiple Traveling Salesmen Problem Genetic Algorithm, and Fixed Start/End Point Multiple Traveling Salesmen Problem Genetic Algorithm.

Required Products MATLAB
MATLAB release MATLAB 7.12 (R2011a)
Tags for This File   Please login to tag files.
Please login to add a comment or rating.
Comments and Ratings (19)
24 Apr 2013 virat rehani

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

24 Nov 2012 Bharath

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

27 Mar 2012 Joseph Kirk

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

26 Mar 2012 Abdullah Alomari

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

Thanks

29 Dec 2011 Anatoly

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?

05 May 2011 Joseph Kirk

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

04 May 2011 tim

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

06 Jul 2010 Sumana Srinivasan

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.

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.

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.

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.

Updates
07 Mar 2008

Fixed waitbar issues.

02 Sep 2008

updated help notes, description

02 Jun 2009

Added 3D capability.

07 Nov 2011

Minor cosmetic updates.

Contact us