algorithm - 旅行推销员的特例(他周末休息)

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

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

最佳答案

那只是 Vehicle Routing with Time Windows :

每个“车辆”代表“销售员”的 1 个工作周

“仓库”是“推销员的家乡”

每个“客户的服务时长”就是每个“城市的停留时间”

每个“客户的开始时间和到期时间”都被忽略，因为城市没有开放或关闭时间

目标是相同的:在每辆车(=行程)的可用时间内访问尽可能多的客户(=城市)。