multiple travelling salesman problem

Multiple Traveling Salesman Problem (mTSP)

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.

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
• 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.

Advertisement

Multi-depot Multiple TSP: a polyhedral study and computational results

• Published: 17 November 2011
• Volume 207 , pages 7–25, ( 2013 )

Cite this article

• Enrique Benavent 1 &
• Antonio Martínez 1  

1544 Accesses

37 Citations

Explore all metrics

We study the Multi-Depot Multiple Traveling Salesman Problem (MDMTSP), which is a variant of the very well-known Traveling Salesman Problem (TSP). In the MDMTSP an unlimited number of salesmen have to visit a set of customers using routes that can be based on a subset of available depots. The MDMTSP is an NP-hard problem because it includes the TSP as a particular case when the distances satisfy the triangular inequality. The problem has some real applications and is closely related to other important multi-depot routing problems, like the Multi-Depot Vehicle Routing Problem and the Location Routing Problem. We present an integer linear formulation for the MDMTSP and strengthen it with the introduction of several families of valid inequalities. Certain facet-inducing inequalities for the TSP polyhedron can be used to derive facet-inducing inequalities for the MDMTSP. Furthermore, several inequalities that are specific to the MDMTSP are also studied and proved to be facet-inducing. The partial knowledge of the polyhedron has been used to implement a Branch-and-Cut algorithm in which the new inequalities have been shown to be very effective. Computational results show that instances involving up to 255 customers and 25 possible depots can be solved optimally using the proposed methodology.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Price includes VAT (Russian Federation)

Instant access to the full article PDF.

Rent this article via DeepDyve

Institutional subscriptions

Similar content being viewed by others

Alternative formulations and improved bounds for the multi-depot fleet size and mix vehicle routing problem.

A new matheuristic approach for the multi-depot vehicle routing problem with inter-depot routes

Exact and Compact Formulation of the Fixed-Destination Travelling Salesman Problem by Cycle Imposement Through Node Currents

Applegate, D., Bixby, R. E., Chvátal, V., & Cook, W. (2006). The traveling salesman problem: a computational study . New Jersey: Princeton University Press.

Google Scholar  

Baldacci, R., & Mingozzi, A. (2009). A unified exact method for solving different classes of vehicle routing problems. Mathematical Programming Series A , 120 (2), 347–380.

Article   Google Scholar  

Bektas, T. (2006). The multiple traveling salesman problem: an overview of formulations and solution procedures. The International Journal of Management Science , 34 , 1449–1458.

Belenguer, J. M., Benavent, E., Prins, C., Prodhon, C., & Wolfler-Calvo, R. (2011). A branch and cut method for the capacitated location-routing problem. Computers & Operations Research , 8 (6), 931–941.

Benavent, E., & Martínez, A. (2011). A polyhedral study of the multi-depot multiple TSP. Internal report, Universitát de Valencia. http://www.uv.es/~benavent/MDMTSP/report_MDMTSP.pdf .

Chvátal, V. (1973). Edmonds polytopes and weakly hamiltonian graphs. Mathematical Programming , 5 , 29–40.

Cordeau, J. F., Gendreau, M., & Laporte, G. (1997). A tabu search heuristic for periodic and multi-depot vehicle routing problems. Networks , 30 , 105–119.

Grötschel, M., & Holland, O. (1987). A cutting-plane algorithm for minimum perfect 2-matchings. Computing , 39 , 327–344.

Grötschel, M., & Padberg, M. W. (1979). On the symmetric traveling salesman problem I: inequalities. Mathematical Programming Studies , 16 , 265–280.

GuoXing, Y. (1995). Transformation of multi-depot multi-salesmen problem to the travelling salesman problem. European Journal of Operational Research , 81 , 557–560.

Gutin, G., & Punnen, A. P. (2002). The traveling salesman problem and its variations . Dordrecht: Kluwer Academic.

Kara, I., & Bektas, T. (2006). Integer linear programming formulations of multiple salesman problems and its variations. European Journal of Operational Research , 174 , 1449–1458.

Labbé, M., Martín, I. R., & Salazar, J. J. (2004). A branch-and-cut algorithm for the plant-cycle location problem. The Journal of the Operational Research Society , 55 , 513–520.

Laporte, G., Nobert, Y., & Taillefer, S. (1988). Solving a family of multi-depot vehicle routing and location-routing problems. Transportation Science , 22 (3), 161–172.

Laporte, G., Nobert, Y., & Arpin, D. (1986). An exact algorithm for solving a capacitated location-routing problem. Annals of Operations Research , 6 , 283–310.

Laporte, G., Nobert, Y., & Arpin, D. (1984). Optimal solutions to capacitated multi-depot vehicle routing problems. Congressus Numerantium , 44 , 283–292.

Malik, W., Rathinam, S., & Darbha, S. (2007). An approximation algorithms for a symmetric generalized multiple depot, multiple travelling salesman problem. Operations Research Letters , 35 , 747–753.

Naddef, D., & Rinaldi, G. (1993). The graphical relaxation: a new framework for the symmetric traveling salesman polytope. Mathematical Programming Series A , 58 , 53–88.

Padberg, M. W., & Rinaldi, G. (1990). Facet identification for the symmetric traveling salesman polytope. Mathematical Programming Series A , 47 , 219–257.

Parragh, S. N. (2010). Solving a real-world service technician routing and scheduling problem. Presented at seventh Triennial symposium on transportation analysis . TRISTAN VII, Tromso, Norway, June 20–25.

Queyranne, M., & Wang, Y. (1993). Hamiltonian path and symmetric travelling salesman polytopes. Mathematical Programming Series A , 58 , 89–110.

Prins, C., Prodhon, C., Ruiz, A., Soriano, P., & Calvo, R. W. (2007). Solving the Capacitated LRP by a cooperative Lagrangean relaxation-granular tabu search heuristic. Transportation Science , 41 (4), 470–483.

Rathinam, S., Sengupta, R., & Darbha, S. (2007). A resource allocation algorithm for multiple vehicle systems with non-holonomic constraints. IEEE Transactions on Automation Science and Engineering , 4 (1), 98–104.

Reinelt, G. (1991). TSPLIB: a travelling salesman problem library. ORSA Journal on Computing , 3 , 376–384.

Yadlapalli, S., Malik, W. A., Darbha, S., & Pachter, M. (2009). A Lagrangian-based algorithm for a multiple depot, multiple traveling salesmen problem. Nonlinear Analysis: Real World Applications , 10 , 1990–1999.

Yadlapalli, S., Malik, W. A., Rathinam, S., & Darbha, S. (2007). A Lagrangian-based algorithm for a combinatorial motion planning problem. In Proceedings of the 46th conference on decision and control , New Orleans, Dec. 12–14.

Download references

Acknowledgements

The contributions by Enrique Benavent and Antonio Martínez have been partially supported by the Ministerio de Ciencia e Innovación of Spain through projects MTM2009-14039-C06-02 and DPI2008-02700, respectively and co financed by FEDER funds.

Author information

Authors and affiliations.

Departamento de Estadística e Investigación Operativa, Universitat de València, C/Dr. Moliner, 50, 46100, Burjassot, Valencia, Spain

Enrique Benavent & Antonio Martínez

You can also search for this author in PubMed   Google Scholar

Corresponding author

Correspondence to Enrique Benavent .

Rights and permissions

Reprints and permissions

About this article

Benavent, E., Martínez, A. Multi-depot Multiple TSP: a polyhedral study and computational results. Ann Oper Res 207 , 7–25 (2013). https://doi.org/10.1007/s10479-011-1024-y

Download citation

Published : 17 November 2011

Issue Date : August 2013

DOI : https://doi.org/10.1007/s10479-011-1024-y

Share this article

Anyone you share the following link with will be able to read this content:

Sorry, a shareable link is not currently available for this article.

Provided by the Springer Nature SharedIt content-sharing initiative

• Multiple depot traveling salesman problem
• Polyhedral study
• Branch-and-cut
• Find a journal
• Publish with us
• Track your research

A transformation for a Heterogeneous, Multiple Depot, Multiple Traveling Salesman Problem

Ieee account.

• Change Username/Password
• Update Address

Purchase Details

• Payment Options
• Order History
• View Purchased Documents

Profile Information

• Communications Preferences
• Profession and Education
• Technical Interests
• US & Canada: +1 800 678 4333
• Worldwide: +1 732 981 0060
• Contact & Support
• About IEEE Xplore
• Accessibility
• Terms of Use
• Nondiscrimination Policy
• Privacy & Opting Out of Cookies

A not-for-profit organization, IEEE is the world's largest technical professional organization dedicated to advancing technology for the benefit of humanity. © Copyright 2024 IEEE - All rights reserved. Use of this web site signifies your agreement to the terms and conditions.