我们可以在谷歌或工具中指定禁止的边缘约束吗

Question

我正试图解决一个经典的旅行推销员问题(TSP(。我使用的是谷歌OR工具默认的TSP包装代码。我希望一些弧被禁止，因为节点10和节点12之间可能没有路径。在这种情况下，我将值设置为一个大数字，如10^6，但解算器仍然使用该圆弧。

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

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

Answer 1

您有两个选项：

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以上的所有弧都被禁止。

2. 您可以通过调整routing.NextArc()来移除一些圆弧例如去除电弧{I，J}

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

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