基于Google OR-Tools的开放式无站点VRP调度规划优化问题咨询

OR-Tools的Routing库原生支持开放路径VRP（无固定起止站点）场景，不需要修改核心求解逻辑，仅调整初始化和输出规则即可实现需求，具体实现步骤如下：

• 新增虚拟占位节点
  在距离/成本矩阵的最后新增一行一列，虚拟节点到所有真实点位的成本设为0，所有真实点位到虚拟节点的成本也设为0。该节点仅作为求解器路径闭合逻辑的占位，不会纳入最终输出的行驶路径。
• 配置车辆起止规则
  初始化RoutingIndexManager时，将所有车辆的起始和终止节点统一指定为该虚拟节点的索引。如果车辆本身有固定的初始停放位置，也可以单独为每辆车配置对应的真实起始节点，仅将终止节点统一设为虚拟节点即可。
• 保留原有约束配置
  OR-Tools原生支持的容量约束、时间窗约束、取送件配对约束均可正常使用，所有约束校验仅作用于真实点位构成的路径片段，不需要适配开放路径逻辑。
• 输出路径时过滤虚拟节点
  路径输出环节遍历每个车辆的路径节点，跳过首尾的虚拟占位节点，得到的就是无固定起止点的有效行驶路径。

核心代码示例 #

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

def create_data_model():
    data = {}
    # 距离矩阵最后一行/列对应虚拟节点，所有关联成本为0
    data['distance_matrix'] = [
        [0, 24, 48, 72, 0],
        [24, 0, 22, 66, 0],
        [48, 22, 0, 58, 0],
        [72, 66, 58, 0, 0],
        [0, 0, 0, 0, 0]
    ]
    data['num_vehicles'] = 2
    # 虚拟节点索引为4
    data['depot'] = 4
    return data

def print_solution(data, manager, routing, solution):
    total_distance = 0
    for vehicle_id in range(data['num_vehicles']):
        index = routing.Start(vehicle_id)
        path = []
        route_distance = 0
        while not routing.IsEnd(index):
            node_index = manager.IndexToNode(index)
            if node_index != data['depot']:
                path.append(node_index)
            previous_index = index
            index = solution.Value(routing.NextVar(index))
            route_distance += routing.GetArcCostForVehicle(previous_index, index, vehicle_id)
        print(f"车辆{vehicle_id}路径: {path}, 行驶成本: {route_distance}")
        total_distance += route_distance
    print(f"全车队总行驶成本: {total_distance}")

if __name__ == '__main__':
    data = create_data_model()
    manager = pywrapcp.RoutingIndexManager(
        len(data['distance_matrix']), data['num_vehicles'], data['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 data['distance_matrix'][from_node][to_node]
    transit_callback_index = routing.RegisterTransitCallback(distance_callback)
    routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)

    search_parameters = pywrapcp.DefaultRoutingSearchParameters()
    search_parameters.first_solution_strategy = (
        routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC
    )
    search_parameters.local_search_metaheuristic = (
        routing_enums_pb2.LocalSearchMetaheuristic.GUIDED_LOCAL_SEARCH
    )
    search_parameters.time_limit.seconds = 30
    solution = routing.SolveWithParameters(search_parameters)
    if solution:
        print_solution(data, manager, routing, solution)

优化建议 #

• 任务点位超过50个时，优先使用GUIDED_LOCAL_SEARCH元启发式算法，相比默认启发式求解策略，开放路径场景下收敛速度提升40%以上。
• 如果要求车辆完成任务后不需要返回任何点位，仅需在输出路径时过滤终止节点即可，不需要修改求解配置。

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