MDMTSPV_GA - Multiple Depot Multiple Traveling Salesmen Problem solved by Genetic Algorithm
Updated 15 Jun 2011
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.
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.
* 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
* 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
Elad Kivelevitch (2023). MDMTSPV_GA - Multiple Depot Multiple Traveling Salesmen Problem solved by Genetic Algorithm (https://www.mathworks.com/matlabcentral/fileexchange/31814-mdmtspv_ga-multiple-depot-multiple-traveling-salesmen-problem-solved-by-genetic-algorithm), MATLAB Central File Exchange. Retrieved .
MATLAB Release Compatibility
Platform CompatibilityWindows macOS Linux
- Mathematics and Optimization > Global Optimization Toolbox > Genetic Algorithm >
- AI, Data Science, and Statistics > Statistics and Machine Learning Toolbox > Cluster Analysis > Nearest Neighbors >
- MATLAB > Mathematics > Graph and Network Algorithms > Shortest Path > Traveling Salesman (TSP) >
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!Start Hunting!
Discover Live Editor
Create scripts with code, output, and formatted text in a single executable document.