我们可以在 Google OR 工具中指定禁止的边缘约束吗？

Question

我正在尝试解决经典的旅行商问题 (TSP)。我正在使用 Google OR Tools 默认 TSP 包装器代码。我希望禁止某些弧，因为节点 10 和节点 12 之间可能没有路径。在这种情况下，我将值设置为一个很大的数字，例如 10^6，但求解器仍然使用该弧。

我验证了这个特定实例有一个可行的解决方案，在某种意义上，当我运行两次相同的代码或将求解器的时间限制从 30 秒延长到 60 秒时，求解器找到了一个解决方案不使用这个弧。

我的问题是：有没有办法指定一个不能使用的硬约束，而不是将弧成本设置为∞？我想象在经典的 TSP 线性规划中，可以对二元决策变量设置约束。

Answer 1

您有两个选择：

创建路线维度，以便您可以设置车辆容量（即允许的车辆最长距离）。因此，任何运输成本高于此容量的弧线都被有效禁止（车辆容量是硬约束）。

例如

# Add Distance constraint.
dimension_name = 'Distance'
routing.AddDimension(
  transit_callback_index, # you can reuse the same callback use in SetArcCost
  0,  # no slack
  42_000, # vehicle maximum travel distance
  True,  # start cumul to zero
  dimension_name)

现在 42_000 以上的所有弧线都被禁止。

您可以通过调整 routing.NextArc() 来删除一些圆弧例如删除圆弧 {I,J}

i_index = manager.NodeToIndex(I)
j_index = manager.NodeToIndex(J)
routing.NextVar(i_index).RemoveValue(j_index)

注意：您还可以使用 RemoveValues([....]) 来抑制传出弧的列表。

我们可以在 Google OR 工具中指定禁止的边缘约束吗？

Can we specify forbidden edge constraints in Google OR Tools?

or-tools