python-3.x - 时间窗路由中slack变量的定义

Question

时间窗口约束定义为
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 ?例如，假设时间窗口是 (50,60)松弛是 5 .这是否意味着 45 的累积变量的值？也是可以接受的，或者松弛是否与范围内的值有关？是否max_slack=0意味着 cumul var 的值必须是 50或 60 ，在上面的例子中？

是否有关于使用我的 or-tools 路由模型的数学模型的论文或详细页面？

Answer 1

对于时间窗口约束，您可以将松弛值视为等待时间。
从源代码。

// 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，又名 A(0)你有 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 分钟
如果松弛最大值是 5这条路线是禁止的，否则车辆最多会在节点 B 处 35 = A(0) + T(30) + 5太早了
即不在 [40,60] 范围内所以对于求解器来说，时间窗口约束不能得到尊重......
注意:我们还可以推导出: B(40) = A(5) + T(30) + 5 B(60) = A(30) + T(30)所以车辆必须在节点 A 的范围内 [5,30]成为 准时在节点 B 与 slack_max = 5 .
即使用 slack max 您可以限制沿路线允许的最大等待时间(额外容量)。

路由使用“两步”算法。
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