Journal
MATHEMATICS
Volume 11, Issue 13, Pages -Publisher
MDPI
DOI: 10.3390/math11133014
Keywords
integer programming; multiple traveling salesperson problem; depot-free mTSP
Categories
Ask authors/readers for more resources
The paper introduces novel compact integer programs for the depot-free multiple traveling salesperson problem (DFmTSP). These programs are adapted to different variants of the DFmTSP and have been empirically tested to show their theoretical and practical advantages over the state of the art.
Multiple traveling salesperson problems (mTSP) are a collection of problems that generalize the classical traveling salesperson problem (TSP). In a nutshell, an mTSP 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 mTSP (DFmTSP). This fundamental variant models real scenarios where depots are unknown or unnecessary. The proposed integer programs are adapted to the main variants of the DFmTSP, 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 mTSP (FD-MmTSP) and a combination of FD-MmTSP and DFmTSP, 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.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available