时间窗口路由中松弛变量的定义

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。这是否意味着cumul var的45值也是可接受的，还是松弛与范围内的值有关？在上面的示例中，是否max_slack=0意味着cumul var的值必须为50或60？

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

Answer 1

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

//如果j == next（i），
//累积量（j）=累积量（i）+过境量（i）+松弛量（i）

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

例如，假设您在时间0 aka处位于节点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分钟
，如果松弛max是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。
即使用最大松弛时间，您可以限制沿路线允许的最大等待时间（额外容量）。

路由使用“两步”算法。
1）尝试找到第一个解决方案，可以使用各种算法。https://developers.google.com/optimization/routing/routing_options#first-solution-strategy-options供纸张参考
2）可以使用本地搜索再次优化该第一个解决方案，请参见https：// developers。 google.com/optimization/routing/routing_options#local-search-options