论文标题
2-周期平衡的旅行推销员问题：一个多项式解决的案例和启发式方法
2-Period Balanced Travelling Salesman Problem: a polynomially solvable case and heuristics
论文作者
论文摘要
我们考虑NP-HARD 2周期平衡的旅行推销员问题。在这个问题中，推销员需要在两个时间段内访问一组客户。给定的客户的一个子集必须在两个时期访问，而其余的客户仅在两个时期中只需要一次访问一次。此外，要求第一阶段访问的客户数量与第二阶段的各个数字没有大于P的差异，而P是给定的小常数。目的是找到在总长度最少的两个时期访问客户的旅行。我们表明，在下面的距离矩阵是Kalmanson矩阵时，可以在多项式时间内解决问题。对于一般情况，我们提出了两个新的启发式方法。这两种启发式方法的结合在文献中的基准实例上显示了非常有利的结果。
We consider the NP-hard 2-period balanced travelling salesman problem. In this problem the salesman needs to visit a set of customers in two time periods. A given subset of the customers has to be visited in both periods while the rest of the customers need to be visited only once, in any of the two periods. Moreover, it is required that the number of customers visited in the first period does not differ from the respective number in the second period by more than p, where p is a given small constant. The objective is to find tours for visiting the customers in the two periods with minimal total length. We show that in the case when the underlying distance matrix is a Kalmanson matrix, the problem can be solved in polynomial time. For the general case, we propose two new heuristics. A combination of these two heuristics has shown very favourable results in computational experiments on benchmark instances from the literature.
