假设推销员不得不在周末回家。并假设在每个城市花费的时间不是恒定的。有人知道为解决这一版本的问题所做的任何特定工作吗?
我的意思是每个城市都会有附加的成本,说明他需要在那个城市停留多长时间(低至 1 小时,高至四天) 当然,每个城市都有一个位置,因此可以计算每个点到每个点的距离。 推销员将多次出差访问所有城市。每个行程为期 5 天(周一开始,周五结束)。因此,目标是设计行程,以便他可以在尽可能短的时间内访问所有城市一次(除了他将在每周结束时返回的家乡城市)。
最佳答案
那只是 Vehicle Routing with Time Windows :
- 每辆“车辆”代表“销售员”的 1 个工作周
- “仓库”是“推销员的家乡”
- 每个“客户的服务时长”就是每个“城市的停留时间”
- 每个“Customer's startTime and dueTime”都被忽略,因为城市没有开门或关门时间
- 目标是相同的:在每辆车(=行程)的可用时间内拜访尽可能多的客户(=城市)。
关于algorithm - 旅行推销员的特例(他周末休息),我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/21967411/