使用 Google Or-Tools 解决 VRP 中删除仓库约束

Question

嗨！ 我目前正在研究一个特定的 VRP。目标与传统 VRP 相同，即最小化与最长路由相关的时间。目前阻碍我的根本区别是我需要消除与仓库相关的约束。每辆车可以从不同的位置出发，一旦到达其指定路线的最后一个位置，它必须返回到其起始位置（两辆车不能从同一位置出发）。

在网上多次搜索后，我发现推荐的解决方案是将站点与位置之间的距离设置为零。但是，这个解决方案并不能解决我的问题，因为它不会导致闭环路线。实际上，在以这种方式获得的路线内，不考虑与车辆从最后位置返回到起始位置相对应的最后一段。 因此，我想问是否有可能解决这个问题（我知道删除仓库会显着增加计算复杂度），如果可以，我怎样才能达到预期的结果。 预先感谢您的关注，如果您能提供任何帮助，我将不胜感激。

Answer 1

我的第一次尝试是：

Duplicate each location twice:

  A -> A', A''
  B -> B', B''

_' will serve as depot-out node
_'' will serve as depot-in node
(Those are normal nodes and the routing-solver doesn't allow multiple visits -> two copies).

Remove all outgoing-edges of the depot-node, except for _' (mutate cp-domain of next-var).
Remove all ingoing-edges of the depot-node, except for _''.
All edges incident to the depot-node have 0 transit costs and time-accumulation.

Model pickup-delivery semantics for each pair of _' and _'' in this order:
  _' precedes _'' (and is on same tour).

链接：

• PD
• 下一个变量