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

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.