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 or the salesmen to travel to each city exactly once and return to their starting locations). The salesmen originate from a set of fixed locations, called depots.
This algorithm is based on Joseph Kirk's MTSPV_GA, but adds the following functionality:
1. Depots at which each salesman originates and ends its tour.
2. Two possible cost functions, that allow to find minimum sum of all tour lengths (as in the original version) and to find the minimum longest tour. The latter problem is sometimes called MinMaxMDMTSP.
Summary:
1. Each salesman travels to a unique set of cities and completes the route by returning to the depot he started from.
2. Each city is visited by exactly one salesman.
Inputs:
* XY (float) is an Nx2 matrix of city locations, where N is the number of cities
* max_salesmen (scalar integer) is the maximum number of salesmen
* depots (float) ia an Mx2 matrix of the depots used by salesmen, M=max_salesmen
* CostType (integer) defines which cost we use. If 1 - sum of all route lengths, if 2 - maximum route length
* 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 16)
* NUM_ITER (scalar integer) is the number of desired iterations for the algorithm to run after a new best solution is found. Don't worry the algorithm will always stop.
* SHOW_PROG (scalar logical) shows the GA progress if true
* SHOW_RES (scalar logical) shows the GA results if true
* DMAT (float) is an NxN matrix of point to point distances or costs
Outputs:
* MIN_DIST (scalar float) is the best cost found by the algorithm, depending on the cost function used.
* BEST_TOUR (matrix integer) is an MxL matrix, each row is an agent tour
* Generation (scalar integer) is the number of generations required by the algorithm to find the solution
|
