论文标题
节点重量依赖的旅行销售人员问题：近似算法和随机搜索启发式方法
The Node Weight Dependent Traveling Salesperson Problem: Approximation Algorithms and Randomized Search Heuristics
论文作者
论文摘要
车辆路由区域中的几个重要优化问题可以看作是经典旅行销售人员问题（TSP）的变体。在进化计算领域，在过去的5年中，旅行小偷问题（TTP）越来越多。在本文中，我们研究了权重对此类问题的影响，从某种意义上说，旅行成本在旅行中已经访问过的节点的权重增加。这提供了重要的TSP变体的抽象，例如旅行小偷问题和依赖时间的TSP变体，并允许精确研究体重依赖性引起的难度增加。我们为具有度量距离和有界正权重的TSP的重量依赖性版本提供了3.59个approximation。此外，我们对简单的随机局部搜索进行了实验研究，并具有经典的突变算子和两个适合加权TSP的最先进进化算法EAX的变体。我们的结果表明，节点权重对结果巡回演出中节点位置的影响。
Several important optimization problems in the area of vehicle routing can be seen as a variant of the classical Traveling Salesperson Problem (TSP). In the area of evolutionary computation, the traveling thief problem (TTP) has gained increasing interest over the last 5 years. In this paper, we investigate the effect of weights on such problems, in the sense that the cost of traveling increases with respect to the weights of nodes already visited during a tour. This provides abstractions of important TSP variants such as the Traveling Thief Problem and time dependent TSP variants, and allows to study precisely the increase in difficulty caused by weight dependence. We provide a 3.59-approximation for this weight dependent version of TSP with metric distances and bounded positive weights. Furthermore, we conduct experimental investigations for simple randomized local search with classical mutation operators and two variants of the state-of-the-art evolutionary algorithm EAX adapted to the weighted TSP. Our results show the impact of the node weights on the position of the nodes in the resulting tour.
