OR-Tools：如何定义VRP/CVRP/VRPTW中无法访问的节点？

Question

我正在尝试这个 vrp example
据我了解，我们必须有二维数组来定义所有节点之间的距离矩阵
但是对于我的需求，很少有节点之间没有距离矩阵，就像这个图

距离矩阵数组将为：

public final long[][] distanceMatrix = {
         {0, 2, 1, 0, 0},
         {0, 0, 0, 2, 1},
         {0, 1, 0, 0, 0},
         {0, 0, 0, 0, 3},
         {0, 0, 0, 0, 0},
  };

问题是对于距离矩阵数组，我们必须在所有节点之间有 int 个数字，因此对于两个之间没有直接路径的节点（如 A->D），我使用 0，但 OrTool 将了解这两个节点之间的旅行成本为零。求解器总是选择那条路走。
那么 ortool 库是否支持在有向图上声明这种类型？
谢谢

Answer 1

要禁止弧线，您基本上有两种方法：

使用距离尺寸和高于车辆最大容量的值。例如假设你有一个距离维度：

transit_callback_index = routing.RegisterTransitCallback(distance_callback)

routing.AddDimension(
  transit_callback_index,
  0, # no slack for distance, can be use as waiting time for Time dimension
  42,  # maximum distance a vehicle can travel
  True,  # force start cumul to zero, i.e. vehicle start a km 0
  "Distance"
)
...

如您所见，这里 42 是车辆的限制，所以如果在您的距离矩阵中使用 43 则没有车辆可以采用此弧线，因为它超出了车辆容量（上面的编辑CumulVar 域的上限）。因此，您可以将距离矩阵写为：

public final long[][] distanceMatrix = {
         {43, 2, 1,43,43},
         {43,43,43, 2, 1},
         {43, 1,43,43,43},
         {43,43,43,43, 3},
         {43, 3,43,43,43},
  };

注意：您的 SetArcCost() 和 AddDimension() 可以使用相同的注册评估员。

您可以设置允许的下一个节点列表。对于每个节点，您可以定义一个允许的节点列表（默认情况下所有节点）例如在这里你有：

next = {
  [A, [B, C]],
  [B, [E, D]],
  [C, [B]],
  [D, [E]],
  [E, []]}

注意（必须使用 0-4 而不是 A-E）

那么你可以使用：

for node, l in next:
  node_index = manager.NodeToIndex(node)
  next_indices = [node_index] # need itself in case node is dropped
  for next_node in l:
    next_indices.append(manager.NodeToIndex(next_node))
  routing.NextVar(node_index).SetValues(next_indices)

Answer 2

而不是 0，我会尝试以无法承受的成本初始化这些节点，例如 int64.Maxvalue

OR-Tools：如何定义VRP/CVRP/VRPTW中无法访问的节点？

OR-Tools: how to define node that not possible to visit in VRP/CVRP/VRPTW?

or-tools