Mathematical formulations for consistent travelling salesman problems
研究一致性旅行商问题，即寻找多天内成本最小的哈密顿回路集合，要求同一客户在不同日期的服务时间差不超过给定阈值。分析了允许和不允许车辆等待两种变体，提出了适用于分支切割算法的新模型，并基于文献中最多100个客户和3天的实例进行了计算分析。
The consistent travelling salesman problem looks for a minimum-cost set of Hamiltonian routes, one for every day of a given time period. When a customer requires service in several days, the service times on different days must differ by no more than a given threshold (for example, one hour). We analyze two variants of the problem, depending on whether the vehicle is allowed to wait or not at a customer location before its service starts. There are three mathematical models in the literature for the problem without waiting times, and this paper describes a new model appropriated to be solved with a branch-and-cut algorithm. The new model is a multi-commodity flow formulation on which Benders’ Decomposition helps manage a large number of flow variables. There were no mathematical models in the literature for the variant with waiting times, and this paper adapts the four mathematical models to it. We analyze the computational results of the formulations on instances from the literature with up to 100 customers and three days.