Multiple Traveling Salesmen Problem - Genetic Algorithm, using multi-chromosome representation

Finds a (near) optimal solution to a modified MTSP by a GA, with additional constraints

MTSP_GA_MULTI_CH Multiple Traveling Salesmen Problem (M-TSP) Genetic Algorithm (GA) using multi-chromosome representation
Finds a (near) optimal solution to a variation of the M-TSP by setting
up a GA to search for the shortest route, taking into account
additional constraints, and minimizing the number of salesmen.
Summary:
1. Each salesman starts at the first location, and ends at the first
location, but travels to a unique set of cities in between
2. Except for the first, each city is visited by exactly one salesman
3. The algorithm uses a special, so-called multi-chromosome genetic
representation to code solutions into individuals.
4. Special genetic operators (even complex ones) are used.
5. The number of salesmen used is minimized during the algorithm
6. Additional constraints have to be satisfied
- minimum number of locations, what each salesmen visit
- maximum distane travelled by each salesmen
7. Time windows can be defined for each locations (e.g. packing/loading times).
Note: The Fixed Start/End location is taken to be the first XY point
Inputs:
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 number of cities for each
salesmen, NOT including the start/end point
MAX_TOUR (scalar integer) is the maximum tour length for each salesmen
TW (scalar_integer) is the time window for each location
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
USE_COMPLEX (scalar boolen 0/1) is the flag wether to use complex mutation operators or not
SHOW_PROG (scalar logical) shows the GA progress if true
SHOW_RES (scalar logical) shows the GA results if true
Outputs:
OPT_RTE (integer array) is the best route found by the algorithm
MIN_DIST (scalar float) is the total distance traveled by the salesmen
OPT_ITER (scalar int) is the number of iterations until the optimal solution has been found
OPT_TIME (scalar float) is the time in milliseconds until the optimal solution has been found
DIST_HISTORY (float array) is the history of distances of best found solutions
Authors: Andras Kiraly, Janos Abonyi
Email: [e-mail]
Release Date: 16/10/2014
The implementation is based on the work of Joseph Kirk: mtspf_ga

*************************************************************************************************
******************** Reference notice ********************
*************************************************************************************************
If you use this implementation in your work, please cite our paper:

Andras Kiraly, Janos Abonyi: Redesign of the Supply of Mobile Mechanics
based on a novel Genetic Optimization Algorithm using Google Maps API.
Engineering Applications of Artificial Intelligence, 2014.
*************************************************************************************************