or-tools - 定义不必访问的节点

Question

我想使用RoutingModel包括从必须访问约束中解放出来的节点来定义路由问题，但如果访问会影响容量维度。你有什么建议如何做到这一点？

标签： or-tools

Answer 1

您可以使用析取约束使您的节点成为可选的。您应该将每个节点添加到其自己的析取组中，每个节点都有一个元素：

    for node in [0, 1, 2, 3, 4]:
        routing.AddDisjunction(
            nodes=[node],
            penalty=1)

为什么这行得通？

在析取组中，求解器将尝试在解中准确包含max_cardinality该组中的节点。

• 如果penalty为负，这将被视为硬约束，这意味着如果不满足约束，求解器将不会返回有效的解决方案。
• 但是，如果penalty是正数，这将是一个软约束，这意味着违规将对全局成本变量增加惩罚。

因此，为了最大限度地减少惩罚，求解器将尝试在解决方案中包含尽可能多的节点，同时仍然允许将其中一些节点排除在外。