在我试图解决的使用 Google 的 OR-Tools 的车辆路线问题 (VRP) 的实例中，只有某些路线（旅行）应该在起点（即站点）结束。
我可以编辑从每个位置到仓库的距离。将它们全部设置为 0 将具有设置任意结束位置的效果，并且路线看起来有点像“径向”，中心位于站点。而设置从每个位置到站点的距离将使路线看起来“圆形”。
问题是，如何对问题进行建模，以便只有一些路由（包含特定类型的节点）是“循环的”？
问问题
1467 次
1 回答
2
这里有一些例子：
“径向”（从中心 0 开始）。例如：https ://github.com/google/or-tools/raw/stable/ortools/constraint_solver/doc/vrp_starts_ends_solution.svg?sanitize=
true 源代码：https ://github.com/google/or-tools/blob /stable/ortools/constraint_solver/doc/VRP.md#multiple-starts-ends
注意：在此示例中，每辆车都有不同的起始节点，并且都使用相同的仓库结束节点，即 0
循环：（从仓库开始并返回到它）。
例如：https ://github.com/google/or-tools/raw/stable/ortools/constraint_solver/doc/vrp_global_span_solution.svg?sanitize=
true src：https ://github.com/google/or-tools/blob /stable/ortools/constraint_solver/doc/VRP.md#global-span-constraints
只需创建一个虚拟节点，与您所说的任何节点的距离为零，但也保留您的仓库。
在构建 RoutingIndexManager 时，您可以传递一个开始/结束列表，以便在最终列表中选择您的虚拟节点或真实站点，以便让车辆返回或不返回站点。
在您的“打印/显示”方法中，您可以检查结束节点索引并相应地绘制/打印......
注意：您可以在源代码树中找到用于生成这些 svg 的 python 脚本（我已经好几个月没有运行它了，所以它可能会损坏（TODO：在上面添加 CI 作业 ^^））
于 2020-01-22T08:58:11.743 回答