期刊
MATHEMATICS
卷 11, 期 13, 页码 -出版社
MDPI
DOI: 10.3390/math11133014
关键词
integer programming; multiple traveling salesperson problem; depot-free mTSP
类别
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.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据