The Multiple Traveling Salesman Problem (\(m\)TSP) is a generalization of the Traveling Salesman Problem (TSP) in which more than one salesman is allowed. Given a set of cities, one depot where \(m\) salesmen are located, and a cost metric, the objective of the \(m\)TSP is to determine a tour for each salesman such that the total tour cost is minimized and that each city is visited exactly once by only one salesman.
Problem Statement
The Multiple Traveling Salesman Problem (\(m\)TSP) is a generalization of the Traveling Salesman Problem (TSP) in which more than one salesman is allowed. Given a set of cities, one depot (where \(m\) salesmen are located), and a cost metric, the objective of the \(m\)TSP is to determine a set of routes for \(m\) salesmen so as to minimize the total cost of the \(m\) routes. The cost metric can represent cost, distance, or time. The requirements on the set of routes are:
- All of the routes must start and end at the (same) depot.
- Each city must be visited exactly once by only one salesman.
The \(m\)TSP is a relaxation of the vehicle routing problem (VRP); if the vehicle capacity in the VRP is a sufficiently large value so as not to restrict the vehicle capacity, then the problem is the same as the \(m\)TSP. Therefore, all of the formulations and solution approaches for the VRP are valid for the \(m\)TSP. The \(m\)TSP is a generalization of the TSP; if the value of \(m\) is 1, then the \(m\)TSP problem is the same as the TSP. Therefore, all of the formulations and solution approaches for the \(m\)TSP are valid for the TSP.
Bektas (2006) lists a number of variations on the \(m\)TSP.
- Multiple depots: Instead of one depot, the multi-depot \(m\)TSP has a set of depots, with \(m_j\) salesmen at each depot \(j\). In the fixed destination version, a salesman returns to the same depot from which he started. In the non-fixed destination version, a salesman does not need to return to the same depot from which he started but the same number of salesmen must return as started from a particular depot. The multi-depot \(m\)TSP is important in robotic applications involving ground and aerial vehicles. For example, see Oberlin et al. (2009).
- Specifications on the number of salesmen: The number of salesmen may be a fixed number \(m\), or the number of salesmen may be determined by the solution but bounded by an upper bound \(m\).
- Fixed charges: When the number of salesmen is not fixed, there may be a fixed cost associated with activating a salesman. In the fixed charge version of the \(m\)TSP, the overall cost to minimize includes the fixed charges for the salesmen plus the costs for the tours.
- Time windows: As with the TSP and the VRP, there is a variation of the \(m\)TSP with time windows. Associated with each node is a time window during which the node must be visited by a tour. The \(m\)TSPTW has many applications, such as school bus routing and airline scheduling.
Mathematical Formulation
Here we present an assignment-based integer programming formulation for the \(m\)TSP.
Consider a graph \(G=(V,A)\), where \(V\) is the set of \(n\) nodes, and \(A\) is the set of edges. Associated with each edge \((i,j) \in A\) is a cost (or distance) \(c_{ij}\). We assume that the depot is node 1 and there are \(m\) salesmen at the depot. We define a binary variable \(x_{ij}\) for each edge \((i,j) \in A\); \(x_{ij}\) takes the value 1 if edge \((i,j)\) is included in a tour and \(x_{ij}\) takes the value 0 otherwise. For the subtour elimination constraints, we define an integer variable \(u_i\) to denote the position of node \(i\) in a tour, and we define a value \(p\) to be the maximum number of nodes that can be visited by any salesman.
Objective
Minimize \( \sum_{(i,j) \in A} c_{ij} x_{ij}\)
Constraints
Ensure that exactly \(m\) salesmen depart from node 1
\(\sum_{j \in V: (1,j) \in A} x_{1j} = m\)
Ensure that exactly \(m\) salesmen return to node 1
\(\sum_{j \in V: (j,1) \in A} x_{j1} = m\)
Ensure that exactly one tour enters each node
\(\sum_{i \in V: (i,j) \in A} x_{ij} = 1, \forall j \in V\)
Ensure that exactly one tour exits each node
\(\sum_{j \in V: (i,j) \in A} x_{ij} = 1, \forall i \in V\)
Include subtour elimination constraints (Miller-Tucker-Zemlin)
\(u_i – u_j + p \cdot x_{ij} \leq p-1, \forall 2 \leq i \neq j \leq n\)
The literature includes a number of alternative formulations. Some of the alternatives to the two-index variable, assignment-based formulation are a two-index variable formulation with the original subtour elimination constraints (see Laporte and Nobert, 1980), a three-index variable formulation (see Bektas, 2006), and a \(k\)-degree center tree-based formulation (see Christofides et al., 1981 and Laporte, 1992).
To solve this integer linear programming problem, we can use one of the NEOS Server solvers in the Mixed Integer Linear Programming (MILP) category. Each MILP solver has one or more input formats that it accepts.
GAMS Model
Click here for a GAMS model for the bayg29 instance from the TSPLIB. The formulation was provided by Erwin Kalvelagen in a blog post here.
If we submit this model to FICO-Xpress with a CPU time limit of 1 hour, we obtain a solution with a total cost of 2176 (gap of 4.3%) and the following tours:
- Tour 1: i13 – i4 – i10 – i20 – i2 – i13
cost = 60 + 39 + 25 + 49 + 87 = 260 - Tour 2: i13 – i18 – i14 – i17 – i22 – i11 – i15 – i13
cost = 128 + 32 + 51 + 47 + 63 + 68 + 86 = 475 - Tour 3: i13 – i24 – i8 – i28 – i12 – i6 – i1 – i13
cost = 56 + 48 + 64 + 71 + 46 + 60 + 82 = 427 - Tour 4: i13 – i29 – i3 – i26 – i9 – i5 – i21 – i13
cost =160 + 60 + 78 + 57 + 42 + 50 + 82 = 529 - Tour 5: i13 – i19 – i25 – i7 – i23 – i27 – i16 – i13
cost = 71 + 52 + 72 + 111 + 74 + 48 + 57 = 485
References
- Bektas, T. 2006. The multiple traveling salesman problem: an overview of formulations and solution procedures. OMEGA: The International Journal of Management Science 34(3), 209-219.
- Christofides, N., A. Mingozzi, and P. Toth. 1981. Exact algorithms for the vehicle routing problem, based on spanning tree and shortest path relaxations. Mathematical Programming 20, 255-282.
- Laporte, G. 1992. The vehicle routing problem: an overview of exact and approximate algorithms. European Journal of Operational Research 59, 345-358.
- Laporte, G. and Y. Nobert. 1980. A cutting planes algorithm for the \(m\)-salesmen problem. Journal of the Operational Research Society 31, 1017-1023.
- Oberlin, P., S. Rathinam, and S. Darbha. 2009. A transformation for a heterogeneous, multi-depot, multiple traveling salesman problem. In Proceedings of the American Control Conference, 1292-1297, St. Louis, June 10 – 12, 2009.