algorithm - 旅行推销员的一个特例（他周末休息）

Question

假设推销员不得不回家过周末。并假设在每个城市花费的时间不是恒定的。有没有人知道为解决这个版本的问题所做的任何特定工作？

我的意思是每个城市都会有一个附加成本，说明他需要在那个城市停留多长时间（低至 1 小时，高至 4 天）当然每个城市都有一个位置，因此距离每个点和可以计算到每个点。推销员将多次出差访问所有城市。每趟旅程为期 5 天（周一开始，周五结束）。因此，目标是设计旅行，以便他可以在尽可能短的时间内访问所有城市（除了他将在每周结束时返回的家乡）。

Answer 1

这只是带有时间窗的车辆路线：

• 每辆“车辆”代表“推销员”的 1 个工作周
• “仓库”是“推销员的家乡”
• 每个“客户的服务时长”就是每个“城市的停留时间”
• 每个“客户的 startTime 和 dueTime”都被忽略，因为 City 没有开放或关闭时间
• 目标是相同的：在每辆车（=行程）的可用时间内访问尽可能多的客户（=城市）。