如何在 Google OR 工具的 VRP 中强制执行某些节点不应首先和最后访问的硬约束

Question

我试图强制执行一个约束，即某些节点不应在旅行开始时或旅行结束时出现 VRP 问题。有没有办法在 Google OR 工具中强制执行此类约束？仅供参考，我使用的语言是 java.

Answer 1

最简单的方法是调整距离矩阵，使 'firsts' 的唯一传入弧线来自仓库，而最后的唯一传出弧线是到仓库。

Answer 2

您可以尝试修改nextVar变量的范围

例如为每辆车禁止圆弧start -> index。

Java:

long toIndex = manager.nodeToIndex(index); 
for(int i = 0; i < vehicleNumber; ++i) {
  long fromIndex = routing.start(i);
  logger.info("Forbidding connection " + fromIndex + " -> " + toIndex);
  routing.nextVar(fromIndex).removeValue(toIndex);
}

.网

long toIndex = manager.NodeToIndex(index); 
for (int i = 0; i < vehicleNumber; ++i) {
  long fromIndex = routing.Start(i);
  Console.WriteLine($"Forbidding connection {fromIndex} -> {toIndex}");
  routing.NextVar(fromIndex).RemoveValue(toIndex);
}

Python

to_index = manager.NodeToIndex(index);
for i in range(vehicle_number):
  from_index = routing.Start(i)
  print(f"Forbidding connection {from_index} -> {to_index}")
  routing.NextVar(from_index).RemoveValue(to_index)

index -> end 节点基本相同。

Java:

long fromIndex = manager.nodeToIndex(index); 
for(int i = 0; i < vehicleNumber; ++i) {
  long toIndex = routing.end(i);
  logger.info("Forbidding connection " + fromIndex + " -> " + toIndex);
  routing.nextVar(fromIndex).removeValue(toIndex);
}

.网

long fromIndex = manager.NodeToIndex(index); 
for (int i = 0; i < vehicleNumber; ++i) {
  long toIndex = routing.End(i);
  Console.WriteLine($"Forbidding connection {fromIndex} -> {toIndex}");
  routing.NextVar(fromIndex).RemoveValue(toIndex);
}

Python

from_index = manager.NodeToIndex(index);
for i in range(vehicle_number):
  to_index = routing.End(i)
  print(f"Forbidding connection {from_index} -> {to_index}")
  routing.NextVar(from_index).RemoveValue(to_index)

如何在 Google OR 工具的 VRP 中强制执行某些节点不应首先和最后访问的硬约束

How to enforce Hard Constraint that certain nodes should not be visited first and last in VRP of Google OR tools

java

or-tools

vehicle-routing