GlobalSpanCoefficient 背后的直觉
The intuition behind the GlobalSpanCoefficient
我正在研究 vehicle routing problem,它可以最大限度地降低 "the slowest truck" 车队的成本。
所以现在 objective 函数应该涉及两个量:
- 所有车辆的所有过渡的总和(总距离),并且
- 最贵路线的费用
这些值是如何组合的?我假设全局跨度系数
distance_dimension.SetGlobalSpanCostCoefficient(100)
涉及?就是加权和的系数
cost = w*A + (100-w)*B
其中 A
是最慢卡车的成本,B
是所有卡车的总距离?
不,它只是: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 只是所有这些成本的总和乘以它们各自的系数...
我正在研究 vehicle routing problem,它可以最大限度地降低 "the slowest truck" 车队的成本。
所以现在 objective 函数应该涉及两个量:
- 所有车辆的所有过渡的总和(总距离),并且
- 最贵路线的费用
这些值是如何组合的?我假设全局跨度系数
distance_dimension.SetGlobalSpanCostCoefficient(100)
涉及?就是加权和的系数
cost = w*A + (100-w)*B
其中 A
是最慢卡车的成本,B
是所有卡车的总距离?
不,它只是: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 只是所有这些成本的总和乘以它们各自的系数...