Single-commodity flow-based formulations and accelerated benders algorithms for the high-multiplicity asymmetric traveling salesman problem and its extensions
提出一种单商品流公式化方法，用于高重复度非对称旅行商问题，并设计加速Benders算法，能在1小时内求解多达1001个城市的最优解，适用于物流路径规划等场景。
In this paper, we present a single-commodity flow-based formulation for the high-multiplicity asymmetric traveling salesman problem (HMATSP), which is an extension of the asymmetric traveling salesman problem (ATSP) wherein a city can be visited multiple times. We show that even though this formulation is not as tight as the best known formulation for the HMATSP, it is faster and easier to use for direct solution by CPLEX and can be used to model several variants or extensions of the HMATSP that have not been studied in the literature. Furthermore, we propose effective accelerated Benders algorithms that are demonstrated to solve instances of the HMATSP and its extensions, which are derived from the well-known ATSP libraries and involve up to 1001 cities, within an hour of CPU time. These are the largest-sized HMATSP instances solved to optimality in the literature.