File Exchange

image thumbnail

Multiple Variable Traveling Salesmen Problem - Genetic Algorithm

version 1.3 (13.4 KB) by

Finds a near-optimal solution to a variation of the MTSP with variable number of salesmen using a GA

20 Downloads

Updated

View License

MTSPV_GA Variable Multiple Traveling Salesmen Problem (M-TSP) Genetic Algorithm (GA)
  Finds a (near) optimal solution to a variation of the M-TSP (that has a
  variable number of salesmen) 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 point to point distances or costs
- 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 4)
- 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:
mtspv_ga
  -or-
mtspv_ga(userConfig)
  -or-
resultStruct = mtspv_ga;
  -or-
resultStruct = mtspv_ga(userConfig);
  -or-
[...] = mtspv_ga('Param1',Value1,'Param2',Value2, ...);

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

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

Example:
% Pass a random set of user-defined XY points to the solver
userConfig = struct('xy',10*rand(35,2));
resultStruct = mtspv_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 = mtspv_ga(userConfig);

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

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

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

Comments and Ratings (3)

Bharath

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

Hello, really great job!!!

Could you help me to change this example into simulink, please!

The Author

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

Updates

1.3

Major overhaul of input/output interface.

1.2

Minor cosmetic updates.

1.1

Added 3D capability.

MATLAB Release
MATLAB 8.3 (R2014a)

Download apps, toolboxes, and other File Exchange content using Add-On Explorer in MATLAB.

» Watch video