时间窗口约束定义为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 路由模型的数学模型的论文或详细页面？
最佳答案
对于时间窗口约束，您可以将松弛值视为等待时间。
从源代码。
// 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) + 5B(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
关于python-3.x - 时间窗路由中slack变量的定义，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/50483447/