使用OR-Tools Python解决非完全图VRP问题的技术问询

针对非完全图的VRP场景，常规解决方案就是先计算所有节点对的最短路径距离，再将结果填入距离矩阵或回调函数——这是因为OR-Tools的VRP求解器本质需要的是任意节点间的「可达成本」，不管是直接连通还是间接连通。下面是具体的实现步骤和注意事项：

1. 预处理：计算所有节点对的最短路径 #

首先需要基于你的非完全图结构，用最短路径算法批量计算任意两个节点间的可达距离。常用的算法有Floyd-Warshall（适合节点数不多的场景）或批量Dijkstra（适合节点数较多的场景）。

举个Floyd-Warshall的实现示例：

def compute_all_pairs_shortest_path(adj_matrix):
    n = len(adj_matrix)
    # 初始化距离矩阵，直接边填实际距离，不连通的设为无穷大
    dist = [row[:] for row in adj_matrix]
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if dist[i][k] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
    return dist

# 示例邻接矩阵：0是仓库，1-3是客户；inf表示无直接边
INF = float('inf')
adj_matrix = [
    [0, 5, INF, 10],
    [5, 0, 3, INF],
    [INF, 3, 0, 1],
    [10, INF, 1, 0]
]

shortest_path_dist = compute_all_pairs_shortest_path(adj_matrix)

如果存在完全不可达的节点对（即图不连通），那你的VRP问题本身无解，需要先调整节点集合或图结构。

2. 将最短路径距离整合到OR-Tools中 #

OR-Tools支持两种方式传入距离信息，选哪种都可以：

方式一：使用距离矩阵 #

把计算好的shortest_path_dist直接传给求解器，注意将不可达的节点对（如果还有的话）设为一个极大值（比如1e9），让求解器自动避开这条路径：

from ortools.constraint_solver import routing_enums_pb2
from ortools.constraint_solver import pywrapcp

def create_vrp_model(num_vehicles, depot, shortest_path_dist):
    n = len(shortest_path_dist)
    # 替换inf为极大值
    dist_matrix = [[d if d != INF else 1e9 for d in row] for row in shortest_path_dist]
    
    manager = pywrapcp.RoutingIndexManager(n, num_vehicles, depot)
    routing = pywrapcp.RoutingModel(manager)
    
    # 注册距离矩阵
    def distance_callback(from_index, to_index):
        from_node = manager.IndexToNode(from_index)
        to_node = manager.IndexToNode(to_index)
        return dist_matrix[from_node][to_node]
    
    transit_callback_index = routing.RegisterTransitCallback(distance_callback)
    routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)
    
    # 其他配置（比如车辆容量、时间窗等）...
    return routing, manager

方式二：直接在回调函数中返回最短路径距离 #

和上面逻辑类似，只是不需要提前替换inf，直接在回调里判断：

def distance_callback(from_index, to_index):
    from_node = manager.IndexToNode(from_index)
    to_node = manager.IndexToNode(to_index)
    dist = shortest_path_dist[from_node][to_node]
    # 不可达则返回极大值
    return dist if dist != INF else 1e9

transit_callback_index = routing.RegisterTransitCallback(distance_callback)

3. 关键注意事项 #

• 连通性检查：预处理后必须确保所有客户节点都能从仓库（depot）到达，否则求解器会返回不可行解。
• 极大值设置：极大值要远大于所有正常路径的总距离（比如比最大单条路径大100倍），避免求解器误选不可达路径；同时不要过大，防止数值溢出。
• 算法选择：如果节点数超过100，Floyd-Warshall的O(n³)复杂度会变慢，建议用批量Dijkstra（对每个节点跑一次Dijkstra），复杂度O(n(m+n log n))，效率更高。

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