GlobalSpanCoefficient 背后的直觉

Question

我正在研究 vehicle routing problem，它可以最大限度地降低 "the slowest truck" 车队的成本。

所以现在 objective 函数应该涉及两个量：

所有车辆的所有过渡的总和（总距离），并且
最贵路线的费用

这些值是如何组合的？我假设全局跨度系数

distance_dimension.SetGlobalSpanCostCoefficient(100)

涉及？就是加权和的系数

cost = w*A + (100-w)*B

其中 A 是最慢卡车的成本，B 是所有卡车的总距离？

Answer 1

不，它只是：cost = B + A
其中 B = 路线中所有边成本的总和（通常使用 routing.SetArcCostEvaluatorOfAllVehicles(arc_cost_callback)）
和 A = w * (max{end} - min{start})

注意：需要 B 来帮助求解器找到第一个好的解决方案（否则像 CHEAPEST_PATH 这样的策略会表现得很奇怪，因为选择最便宜的边缘没有成本......），通过最小化 Max cumul Var，A helps 到 "distribute" 个工作。但是它仍然不是真正的分散激励
例如假设具有 cumul_start = 0 的维度和成本为 0,0,6,6 的 4 条路线，它与 2,2,2,6 一样好（或 6,6,6,6 但 B 更高在这里）。
即在这两种情况下 max(cumul_end) == 6。

我在文档中添加了有关 GlobalSpan here 的部分。

ps：看看https://github.com/google/or-tools/issues/685#issuecomment-388503464
pps：在文档示例中，尝试将 maximum_distance = 3000 更改为 1800 或 3500（如果我没记错的话）;)
ppps：请注意，您可以在多个维度上拥有多个 GlobalSpan，objective 只是所有这些成本的总和乘以它们各自的系数...

GlobalSpanCoefficient 背后的直觉

The intuition behind the GlobalSpanCoefficient

python-3.x

or-tools