在 OR-Tools 中对多站点车辆调度问题进行建模

Modeling Multiple Depot Vehicle Scheduling Problem in OR-Tools

or-tools

是否可以在 OR-tools 中解决多站点车辆调度问题 (MDVSP)？

问题在 this paper 中有详细说明，但这里只是一个简短的总结。

我们得到了一组站点和每个站点的可用车辆数量。给定了一组时间表行程，我们知道起点、目的地、开始时间、结束时间，以及一组可以为给定行程提供服务的站点。在连接两个行程时，即指派一辆车依次为两个行程服务时，可能会出现空闲行程，即死头行程。从一个站点到第一趟行程以及从最后一次行程返回到一个站点时，也有死机。 objective 是为了最小化所有无用行程成本的总和，同时确保每次行程仅由一辆车提供服务并且使用的车辆数量不超过可用性。（其他 trips/links，即占用的行程，无论如何都必须 served/traversed；因此，没有必要将它们包含在 objective 中）。

您似乎只想在车辆为空时才考虑电弧成本。（注意：修正错字）

AFAIK，使用 OR-Tools 没有简单的方法。在 C++ 中，您可以使用 DimensionDependentDimension 并在容量维度为零时返回弧成本，否则为零...

我也很好奇你为什么只想数 dead-trip 例如如果总的车辆路线是很少的 dead-trip 而不是很少 dead-trip 的较短路线，那么你为什么要激励第一个？例如1km dead-trip 的 100km 路线是 2km dead-trip...
的 50km 路线的两倍
多个depot请查看 vrp_starts_ends.py
对于 TimeWindows：vrp_time_windows.py
你看文档了吗？例如https://developers.google.com/optimization/routing/cvrp
使用routing.NextVar(A).SetValues([A, B])你可以强制链A->B
参考：https://github.com/google/or-tools/blob/49b6301e1e1e231d654d79b6032e79809868a70e/ortools/constraint_solver/routing.h#L1364-L1366
注意：即使短于 A->B->C 或 C->A->B（假设 TW 允许它们...）
，Solver 也无法使用 A->C->B

在 OR-Tools 中对多站点车辆调度问题进行建模

Modeling Multiple Depot Vehicle Scheduling Problem in OR-Tools

or-tools