论文标题
多次访问的多个旅行推销员问题的有效近似
Efficient Approximations for Many-Visits Multiple Traveling Salesman Problems
论文作者
论文摘要
经典旅行推销员问题（TSP）的基本变体是所谓的多个TSP（MTSP），其中一组$ m $ salesmen共同从一组$ n $ n $城市访问所有城市。 MTSP对许多重要的现实生活应用进行了建模，特别是用于车辆路由问题。 Bektas（Omega 34（3），2006年）进行的一项广泛调查列出了MTSP的各种启发式和精确的解决方案程序，这些程序迅速解决了特定的问题实例。 在这项工作中，我们考虑了MTSP的进一步概括，MTSP是MTSP的MTSP，每个城市$ v $都有一个请求$ r（v）$的$ r（v）$，即推销员应访问多少次。这个问题打开了新的现实生活应用，例如飞机测序，同时构成了一些计算挑战。我们为许多Visits MTSP的重要变体提供了多种有效的近似算法，这些算法可以保证在所有问题实例中快速计算高质量的解决方案。
A fundamental variant of the classical traveling salesman problem (TSP) is the so-called multiple TSP (mTSP), where a set of $m$ salesmen jointly visit all cities from a set of $n$ cities. The mTSP models many important real-life applications, in particular for vehicle routing problems. An extensive survey by Bektas (Omega 34(3), 2006) lists a variety of heuristic and exact solution procedures for the mTSP, which quickly solve particular problem instances. In this work we consider a further generalization of mTSP, the many-visits mTSP, where each city $v$ has a request $r(v)$ of how many times it should be visited by the salesmen. This problem opens up new real-life applications such as aircraft sequencing, while at the same time it poses several computational challenges. We provide multiple efficient approximation algorithms for important variants of the many-visits mTSP, which are guaranteed to quickly compute high-quality solutions for all problem instances.
