论文标题
同步旅行推销员问题
Synchronized Traveling Salesman Problem
论文作者
论文摘要
我们考虑了众所周知的旅行推销员问题的变化，其中有多个代理商必须参观同一图的整个节点，同时遵守节点和边缘容量约束，要求代理必须“崩溃”。我们考虑了最简单的模型，其中输入是无向图，其所有容量等于一个的图形。解决同步旅行推销员问题的解决方案称为“代理商”。我们的模型将同步的旅行推销员问题与旅行推销员问题与所谓的疏散问题有类似的关系，或者众所周知的动态流（流动时间）问题与最低成本流问题有关。 我们根据应尽可能大的代理数量来衡量代理商的强度，以及应尽可能小的时间范围。除了对所引入的概念的一些基本讨论之外，我们还建立了几个上限和下限，以使代理的强度在以下假设是输入图是树或3个连接的3型图。
We consider a variation of the well-known traveling salesman problem in which there are multiple agents who all have to tour the whole set of nodes of the same graph, while obeying node- and edge-capacity constraints require that agents must not "crash". We consider the simplest model in which the input is an undirected graph with all capacities equal to one. A solution to the synchronized traveling salesman problem is called an "agency". Our model puts the synchronized traveling salesman problem in a similar relation with the traveling salesman problem as the so-called evacuation problem, or the well-known dynamic flow (flow-over-time) problem is in relation with the minimum cost flow problem. We measure the strength of an agency in terms of number of agents which should be as large as possible, and the time horizon which should be as small as possible. Beside some elementary discussion of the notions introduced, we establish several upper and lower bounds for the strength of an agency under the assumption that the input graph is a tree, or a 3-connected 3-regular graph.
