一个特殊的旅行商人问题（他周末休息）

Question

一个特殊的旅行商人问题（他周末休息）

algorithmgraph-algorithmtraveling-salesmanplanning

4

假设销售员需要回家度过周末。假定每个城市停留的时间不是恒定的。是否有任何针对这个问题版本的特定工作完成？

我的意思是每个城市都会附加一个成本，表示他需要在该城市停留多长时间（最短为1小时，最长为4天）。每个城市当然都有一个位置，因此可以计算出每个点到每个点的距离。销售员将进行几次旅行以访问所有城市。每次旅行需要5天（从星期一开始，到星期五结束）。因此，目标是设计旅行计划，使他可以在最短的时间内访问所有城市一次（除了家庭所在城市，在每周末他将回到那里）。

- user2681358

真实情况是他必须访问所有城市，但你会如何选择组成旅行的城市群，以优化所需总时间。通常的TS解决方案在这种情况下不一定是最优的，因为你会一直回到起点。 - user2681358

我怀疑，如果访问单个城市所需的时间有下限，那么这比标准TSP更容易优化。甚至可能在多项式时间内得到最优解。 - Ilmari Karonen

看起来我们本质上是在解决一个更小的集合（每次旅行）的TSP问题。选择旅行仍然是最耗时的任务。每次旅行的城市数量的上限可以很容易地计算出来。但这似乎对TSP的一般表示方式来说太泛了，所以我认为可能已经有一些优化工作已经完成了。 - user2681358

首先，我需要知道每个城市之间的移动速度并计算所需时间。然后，该图将成为一个DiGraph，每个城市之间有两条边。接着，将在城市停留的时间加入到边的成本中。但是，只有当城市数量足够少时，才能完全解决这个问题。 - Marichyasana

1

研究人员称之为“车辆路径问题”。 - David Eisenstat

"车辆路径问题"非常适合，感谢@DavidEisenstat。 - user2681358

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Geoffrey De Smet · Accepted Answer

这就是带时间窗口的车辆路径规划：

每个 "车辆" 代表 "推销员" 的1个工作周
"中转站" 是 "推销员的家乡"
每个 "客户服务时间" 是每个 "城市停留时间"
每个 "客户的开始时间和dueTime" 被忽略，因为城市没有开放或关闭时间
目标相同：在每个车辆（=旅行）的可用时间内访问尽可能多的客户（=城市）。