时间松弛变量的定义window路由

Question

时间 window 约束由

定义

time_dimension.CumulVar(node).SetRange(time_window[0], time_window[1])

时间维度

routing.AddDimension(evaluator, slack_max, capacity, fix_start_cumul_to_zero, name)

CumulVar(node)和slack_max的允许值之间有什么关系？例如，假设时间 window 是 (50,60)，松弛时间是 5。这是否意味着 45 的 cumul var 的值也是可以接受的，或者 slack 是否与范围内的值有关？在上面的示例中，max_slack=0 是否意味着累积变量的值必须是 50 或 60？

我的or-tools的路由模型使用的数学模型有没有论文或者详细的页面？

Answer 1

对于时间window约束，您可以将松弛值视为等待时间。
来自源代码。

// if j == next(i),
// cumuls(j) = cumuls(i) + transits(i) + slacks(i)

来源：https://github.com/google/or-tools/blob/d44fb1b423f9d6658c142c041143a4f54b5106d3/ortools/constraint_solver/routing.h#L1356-L1357

例如假设您在时间 0 又名 A(0) 处位于节点 A，并且您有 B([40,60]) 并且传输时间为 T(50)。因此你有：
B(40) < A(0) + T(50) -> 意味着即使没有等待时间也来不及到达下界。
B(60) = A(0) + T(50) + 10 -> 表示车辆可以在节点 A 等待最多 10 分钟，并且在节点 B 仍然准时。

第二个例子：A(0), B([40,60]), T(30):
B(40) = A(0) + T(30) + 10 -> 必须等待 10 分钟
B(60) = A(0) + T(30) + 30 -> 必须等待 30 分钟
如果 slack max 是 5 这条路线是被禁止的，否则车辆最多会在 35 = A(0) + T(30) + 5 的节点 B，这太早了
即不在 [40,60] 范围内，因此对于求解器来说，时间 windows 约束不能被遵守...
注意：我们还可以推导出：
B(40) = A(5) + T(30) + 5
B(60) = A(30) + T(30)
因此车辆必须在范围 [5,30] 的节点 A 处 准时 在节点 B slack_max = 5.
即，使用 slack max 可以限制沿途允许的最长等待时间（额外容量）。

路由使用 "two steps" 算法。
1）尝试找到一个可以使用各种算法的第一个解决方案 比照。 https://developers.google.com/optimization/routing/routing_options#first-solution-strategy-options 论文参考
2) 可以使用本地搜索来优化第一个解决方案 再次实现了几种方法 cf https://developers.google.com/optimization/routing/routing_options#local-search-options