# Multiple travelling salesman
#
# Partitions customers among m salesmen, each starting and ending at the
# depot, minimising total distance. Structurally it is CVRP with unlimited
# vehicle capacity, which isolates what the load variable contributes: with
# capacity removed the potentials are doing only subtour elimination.
#
# Technique: CVRP with the capacity row dropped: exactly m routes leave the
# depot, and potentials handle subtours alone.
#
# On this instance the optimum is 32 (minimisation), confirmed
# independently by exhaustive enumeration before publication.
#
# Reference: Bektas, T. (2006). The multiple traveling salesman problem: an
# overview of formulations and solution procedures. Omega 34(3), 209–219.
model m
set V = {1, 2, 3, 4}
set C = {2, 3, 4}
const c = {{0, 2, 7, 9},
{2, 0, 12, 9},
{7, 12, 0, 12},
{9, 9, 12, 0}}, forall i in V, forall j in V
const M = 2
const N = 4
bin x, forall i in V, forall j in V
int 1 <= u <= 4, forall i in V
min sum_{i in V}{sum_{j in V setminus {i}}{c_{i,j} * x_{i,j}}}
constr sum_{i in V setminus {j}}{x_{i,j}} = 1, forall j in C
constr sum_{j in V setminus {i}}{x_{i,j}} = 1, forall i in C
# exactly M routes leave and return
constr sum_{j in C}{x_{1,j}} = M
constr sum_{i in C}{x_{i,1}} = M
# potentials rule out cycles that miss the depot
constr u_{i} - u_{j} + N * x_{i,j} <= N - 1, forall i in C, forall j in C setminus {i}
end
import elytica
Read this through MCP: read with path: "formulations/m-tsp", or resource hlpl://formulations/m-tsp.