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
SALESMEN (scalar integer) is the number of salesmen to visit the cities
MIN_TOUR (scalar integer) is the minimum tour length for any of the salesmen
POP_SIZE (scalar integer) is the size of the population (should be divisible by 8)
NUM_ITER (scalar integer) is the number of desired iterations for the algorithm to run
SHOW_PROG (scalar logical) shows the GA progress if true
SHOW_RES (scalar logical) shows the GA results if true
Output:
OPT_RTE (integer array) is the best route found by the algorithm
OPT_BRK (integer array) is the list of route break points (these specify the indices
into the route used to obtain the individual salesman routes)
MIN_DIST (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);
salesmen = 5;
min_tour = 3;
pop_size = 80;
num_iter = 5e3;
a = meshgrid(1:n);
dmat = reshape(sqrt(sum((xy(a,:)-xy(a',:)).^2,2)),n,n);
[opt_rte,opt_brk,min_dist] = mtsp_ga(xy,dmat,salesmen,min_tour,pop_size,num_iter,1,1); |
