Code covered by the BSD License  

Highlights from
Multiple Traveling Salesmen Problem - Genetic Algorithm

4.38462

4.4 | 13 ratings Rate this file 52 Downloads (last 30 days) File Size: 13.7 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 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
  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 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)
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.

06 May 2014

Major overhaul of input/output interface.

Contact us