OR-Tools中如何在VRP/CVRP/VRPTW场景定义不可直接通行的节点路径

OR-Tools 完全支持有向图场景下的禁止通行边约束，你遇到的问题是用0表示无通路的方式错误，按照以下步骤调整即可：

1. 替换无通路标记 #

不要用0表示无直接通路，0会被求解器识别为通行成本为0，会被优先选择。你可以用一个远大于业务场景最大可能路径总成本的常量（通常称为INF）表示不可通行。注意不要取值过大避免数值溢出，以你的示例场景为例，所有边总长度不超过20，INF设为10000即可。

2. 修正距离矩阵 #

调整后的Java代码示例如下：

// 不可通行边的标记值，需远大于场景最大可行路径总成本
private static final long INF = 10000L;
public final long[][] distanceMatrix = {
         {0, 2, 1, INF, INF},
         {INF, 0, INF, 2, 1},
         {INF, 1, 0, INF, INF},
         {INF, INF, INF, 0, 3},
         {INF, INF, INF, INF, 0},
};

3. 正常注册成本回调 #

不需要额外添加特殊约束，直接将距离矩阵作为弧成本注册即可：

// 示例回调代码，需结合你实际的RoutingManager、RoutingModel实例调整
LongToLong transitCallback = fromIndex -> {
    long from = routingManager.indexToNode(fromIndex);
    return toIndex -> {
        long to = routingManager.indexToNode(toIndex);
        return distanceMatrix[(int) from][(int) to];
    };
};
routing.setArcCostEvaluatorOfAllVehicles(transitCallback);

求解器会自动规避成本为INF的边，这类边会导致总成本远超可行解的数值，不会被纳入最优解的选择范围。

补充说明 #

OR-Tools的VRP求解天然支持不对称的有向图距离矩阵，你不需要额外做其他配置，只要保证距离矩阵中两个方向的成本按照实际有向通路填写即可。比如节点1到节点3成本为2，节点3到节点1成本为INF，就代表仅允许从节点1到节点3的单向通行，完全匹配你的业务需求。

内容的提问来源于stack exchange，提问作者uncle bob