5

时间窗口约束定义为

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 的值必须是50or 60，在上面的示例中？

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

4

1 回答 1

6

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

// 如果 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->
如果 slack max 是5禁止这条路线，则必须等待 30 分钟，因为否则车辆将最多在节点 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到达。
ie 使用 slack max，您可以限制沿途允许的最大等待时间（额外容量）。

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

于 2018-05-24T07:53:03.990 回答