Compact Integer Programs for Depot-Free Multiple Traveling Salesperson Problems

Multiple traveling salesperson problems ( m TSP) are a collection of problems that generalize the classical traveling salesperson problem (TSP). In a nutshell, an m TSP variant seeks a minimum cost collection of m paths that visit all vertices of a given weighted complete graph. This paper introduces novel compact integer programs for the depot-free m TSP (DF m TSP). This fundamental variant models real scenarios where depots are unknown or unnecessary. The proposed integer programs are adapted to the main variants of the DF m TSP, such as closed paths, open paths, bounding constraints (also known as load balance), and the minsum and minmax objective functions. Some of these integer programs have O ( n 2 m ) binary variables and O ( n 2 ) constraints, where m is the number of salespersons and n = | V ( G ) | . Furthermore, we introduce more compact integer programs with O ( n 2 ) binary variables and O ( n 2 ) constraints for the same problem and most of its main variants. Without losing their compactness, all the proposed programs are adapted to fixed-destination multiple-depots m TSP (FD-M m TSP) and a combination of FD-M m TSP and DF m TSP, where fewer than m depots are part of the input, but the solution still consists of m paths. We used off-the-shelf optimization software to empirically test the proposed integer programs over a classical benchmark dataset; these tests show that the proposed programs meet desirable theoretical properties and have practical advantages over the state of the art.