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

Enrique Benavent () and Antonio Martínez

Annals of Operations Research, 2013, vol. 207, issue 1, 7-25

Abstract: 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. Copyright Springer Science+Business Media, LLC 2013

Keywords: Multiple depot traveling salesman problem; Polyhedral study; Branch-and-cut (search for similar items in EconPapers)
Date: 2013
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (7)

Downloads: (external link)
http://hdl.handle.net/10.1007/s10479-011-1024-y (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:annopr:v:207:y:2013:i:1:p:7-25:10.1007/s10479-011-1024-y

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10479

DOI: 10.1007/s10479-011-1024-y

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

More articles in Annals of Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().