File Exchange

image thumbnail

Fixed Start/End Point Multiple Traveling Salesmen Problem - Genetic Algorithm

version 1.5.0.0 (14.3 KB) by Joseph Kirk
Finds a near-optimal solution to a variation of the M-TSP with fixed endpoints using a GA

3 Downloads

Updated 06 May 2014

View License

MTSPF_GA Fixed Multiple Traveling Salesmen Problem (M-TSP) Genetic Algorithm (GA)
Finds a (near) optimal solution to a variation of the M-TSP by setting
up a GA to search for the shortest route (least distance needed for
each salesman to travel from the start location to individual cities
and back to the original starting place)
Summary:
1. Each salesman starts at the first point, and ends at the first
point, but travels to a unique set of cities in between
2. Except for the first, each city is visited by exactly one salesman

Note: The Fixed Start/End location is taken to be the first XY point

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, NOT including the start/end point
- 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 4 2 8 10 3 7], brks = [3 7]
Taken together, these represent the solution [1 5 6 9 1][1 4 2 8 10 1][1 3 7 1],
which designates the routes for the 3 salesmen as follows:
. Salesman 1 travels from city 1 to 5 to 6 to 9 and back to 1
. Salesman 2 travels from city 1 to 4 to 2 to 8 to 10 and back to 1
. Salesman 3 travels from city 1 to 3 to 7 and back to 1

Usage:
mtspf_ga
-or-
mtspf_ga(userConfig)
-or-
resultStruct = mtspf_ga;
-or-
resultStruct = mtspf_ga(userConfig);
-or-
[...] = mtspf_ga('Param1',Value1,'Param2',Value2, ...);

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

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

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

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

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

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

Comments and Ratings (18)

xiao luo

I want to implement the following features: When limiting the maximum path for each salesperson, after completing all the cities, I need several salespeople.

i'm a bginner in matlab & i need powerfully this code for educational using, may someone explain me how the crossover & mutation have beeing implements in this code ??

Joseph Kirk

@noor, I used a genetic algorithm approach for this code, not simulated annealing.

noor kc

great work, is this simulated annealing or not?
if not can you please tell me whats the iteration criteria ?

and if its simulated annealing, whats the starting temperature ?

Joseph Kirk

@Jarev, a larger number of iterations will take longer to process, but will give the algorithm more chances to find a better solution. It is a trade-off inherent in GA approaches.

Hi, what is the effect of increasing or decreasing the number of iterations in the code? and what does a very high iteration do to the results?

Joseph Kirk

@shang, if you have a DMAT input whose size is NxN, then you could provide a "dummy" XY matrix that is Nx2, and the algorithm will work as you would expect (in the case where a distance/cost matrix is provided, the XY points are only used for plots)

shang ni

Hi,Sir!What could I do when I don't have a input if xy but dmat?

I would like to use mTSP(fixed) for my following code:

xx1 = [-0.5 -0.5 31 31 -0.5];
yy2 = [2.5 -2.5 -2.5 2.5 2.5];
spc = 2;
x = [-1,1];
y = x*spc;
hold on;
xx = 15;
yy = 0;
plot(xx1,yy2,'b'); % draw square
plot(xx,yy,'bo'); % Draw centre circle
f = 0:10:30 ;
F = repmat(f,[4 1]) ;
f = F' ;
Z = [x,y] ;
z = repmat(Z,[4 1]) ;
% draw pluses
plot(f,z,'+r')
% finding distance between ohvs and turbines by creating a distance matrix
for i = 1:size(z,1)
for j = 1:size(z,2)
dist = sqrt((15-f(i,j))^2+(0-z(i,j))^2);
distanceMatrix(i,j) = dist;
end
end
cost = distanceMatrix .* 2; %price of cable per metre
s1 = sum(cost(1,:));
s2 = sum(cost(2,:));
s3 = sum(cost(3,:));
s4 = sum(cost(4,:));
total = s1+s2+s3+s4
for i = 1:size(z,1)
for j = 1:size(z,2)
plot([f(i,j),xx],[z(i,j),yy],'k')
end
end

but finding quite difficult on how to implement it. Please help. thank you

learn

GOOD JOB!

This worked well -- thanks! You can reduce the "mindist" about 80% by initializing each salesman to explore a non-overlapping sector of the cities. The following code replaces lines 180-185:

% popRoute(1,:) = (1:n) + 1;
% popBreak(1,:) = rand_breaks();
% for k = 2:popSize
% popRoute(k,:) = randperm(n) + 1;
% popBreak(k,:) = rand_breaks();
% end

%A Heuristic that reduces MINDIST in practice:
% initialize each salesman to a single sector, each sector has almost the same number of cities:
theta = atan2(xy(2:end,1),xy(2:end,2)); %angle from depot to each city
[~,thetaInd] = sort(theta); %sort the angles
breaks = round(linspace(0,n,nSalesmen+1)); %try to give each salesman the same number of cities
sectorLabels(thetaInd) = floor(linspace(0,nSalesmen-10*eps,n))'+1; %label each city with the assigned salesman

% generate populations where each salesman's sector is randomly permuted
for k = 1:popSize
for i =1:nSalesmen
indices = find(sectorLabels==i)+1;
r = randperm(numel(indices));
popRoute(k,breaks(i)+1:breaks(i+1)) = indices(r);
end
popBreak(k,:)= breaks(2:end-1)+1;
end

Joseph Kirk

@sukanya, why don't you just download the file? And a rating of 1 when you apparently haven't even used the code seems a little premature, no?

sukanya

i need coding for
Fixed Start/End Point Multiple Traveling Salesmen Problem - Genetic Algorithm

Joseph Kirk

@Pedro, yes the notes are in error. They will be fixed shortly.

Pedro p

Thanks Joseph for this submission, It works great for me, from what i understand of how the algorithm works where it says:

"""Route/Breakpoint Details:
If there are 10 cities and 3 salesmen, a possible route/break
combination might be: rte = [5 6 9 4 2 8 10 3 7], brks = [3 7]
Taken together, these represent the solution [1 5 6 9 1][1 4 2 8 1][1 10 3 7 1]"""

Shouldn't it say brks = [3 6]?

Albert

Could you please tell me how i
can edit the number of points that a salesman visits at MOST ? ( Because each salesman has a limit)

I mean, I want to add this input:

MAX_TOUR (scalar integer) is the maximum tour length for any of the
salesmen, NOT including the start/end point

MINTOUR constraint will remain and MAX_TOUR constraint will be added.
Thanks a lot in advance.

The Author

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

barki yak

Thanks alot, it works superb! but could you please tell me how i can edit the number of points that a salesman visit at least? its "2" in your work but i couldnt manage to increase that number

Updates

1.5.0.0

Major overhaul of input/output interface.

1.4.0.0

Removed waitbar.

1.3.0.0

Corrected the route/break details in the comment section.

1.2.0.0

Bug fix. Minor cosmetic updates.

1.1.0.0

Added 3D capability.

1.0.0.0

Removed the SINGLES parameter and replaced it with a more generalized MIN_TOUR

updated title

updated description

MATLAB Release Compatibility
Created with R2014a
Compatible with any release
Platform Compatibility
Windows macOS Linux