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

Question

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

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

Answer 1

那只是 Vehicle Routing with Time Windows :

• 每辆“车辆”代表“销售员”的 1 个工作周
• “仓库”是“推销员的家乡”
• 每个“客户的服务时长”就是每个“城市的停留时间”
• 每个“Customer's startTime and dueTime”都被忽略，因为城市没有开门或关门时间
• 目标是相同的:在每辆车(=行程)的可用时间内拜访尽可能多的客户(=城市)。