基于OR-tools求解带约束的灵活多车场多车辆VRP问题

问题定义 #

你面临的是两级配送VRP问题：需先将全国枢纽的1000件包裹分配到8个容量上限200件的车场，再由20辆容量50件的车辆（可任意选择车场取货）完成末端配送。核心要解决三个问题：包裹-车场分配、车辆-包裹分配、单车辆最优配送路线，最终需输出各车场分配量、车辆取货量、配送顺序。

OR-Tools适配实现思路 #

OR-Tools默认的固定起点VRP可通过以下方式扩展，适配多车场、车辆灵活选起点的场景：

1. 统一节点建模 #

将整个配送链路转化为带虚拟节点的VRP模型：

• 虚拟节点0：代表全国枢纽
• 节点1~8：代表8个车场（需添加最大流入量约束对应存储上限）
• 节点9~1008：代表1000个配送点（每个点需求1件）
• 车辆起点可设置为任意车场节点（允许重复设置同一车场，支持多辆车从同一车场出发）

2. 核心约束配置 #

（1）基础数据与车辆装载约束

直接用OR-Tools的Capacity维度实现车辆装载量限制：

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

def create_data_model():
    data = {}
    # 预计算所有节点间的路径时长矩阵（覆盖枢纽<->车场、车场<->配送点、配送点间）
    data['time_matrix'] =  # 替换为你的实际时长数据
    data['demands'] = [0] + [0]*8 + [1]*1000  # 枢纽/车场无需求，每个配送点需求1件
    data['vehicle_capacities'] = [50]*20  # 20辆车，每辆容量50
    data['num_vehicles'] = 20
    # 车辆可选起点：重复车场节点，支持多辆车从同一车场出发
    data['starts'] = [1,2,3,4,5,6,7,8] * 2 + [1,2]  # 生成20个起点，覆盖所有车场
    data['ends'] = data['starts']  # 车辆返回出发车场，也可设为任意车场
    return data

（2）车场容量约束

通过自定义维度约束限制每个车场的总流入包裹量（即分配到该车场的包裹数）：

data = create_data_model()
manager = pywrapcp.RoutingIndexManager(len(data['time_matrix']), data['num_vehicles'], data['starts'], data['ends'])
routing = pywrapcp.RoutingModel(manager)

# 定义回调：统计从枢纽到车场的包裹流
def depot_flow_callback(from_index, to_index):
    from_node = manager.IndexToNode(from_index)
    to_node = manager.IndexToNode(to_index)
    # 若路径是枢纽->车场，计1件（对应分配1个包裹到该车场）
    if from_node == 0 and 1 <= to_node <=8:
        return 1
    return 0

# 注册回调并添加车场容量维度
flow_callback_index = routing.RegisterTransitCallback(depot_flow_callback)
routing.AddDimension(
    flow_callback_index,
    0,  # 无松弛量
    200,  # 单车场最大容量
    True,  # 累积量从0开始
    'DepotCapacity'
)

# 给每个车场单独设置累积上限
for depot_node in range(1,9):
    total_flow = routing.solver().Sum(
        routing.CumulVar(routing.End(vehicle_id), 'DepotCapacity')
        for vehicle_id in range(data['num_vehicles'])
        if manager.IndexToNode(data['starts'][vehicle_id]) == depot_node
    )
    routing.solver().Add(total_flow <= 200)

3. 求解与结果解析 #

设置求解策略后运行，解析结果即可得到所需的分配数据和配送路线：

# 配置求解参数
search_params = pywrapcp.DefaultRoutingSearchParameters()
search_params.first_solution_strategy = routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC
search_params.local_search_metaheuristic = routing_enums_pb2.LocalSearchMetaheuristic.GUIDED_LOCAL_SEARCH
search_params.time_limit.seconds = 300  # 根据需求调整求解时间

solution = routing.SolveWithParameters(search_params)

if solution:
    # 1. 统计各车场分配数量
    depot_assignments = {depot:0 for depot in range(1,9)}
    # 2. 输出每辆车的配送信息
    print("车辆配送详情:\n")
    for vehicle_id in range(data['num_vehicles']):
        index = routing.Start(vehicle_id)
        start_depot = manager.IndexToNode(index)
        route = []
        load = 0
        while not routing.IsEnd(index):
            node = manager.IndexToNode(index)
            load += data['demands'][node]
            route.append(node)
            index = solution.Value(routing.NextVar(index))
        # 累计车场分配量
        depot_assignments[start_depot] += load
        # 输出车辆信息
        print(f"车辆{vehicle_id+1}: 起点车场{start_depot} | 装载量{load}件")
        print(f"配送顺序: {' -> '.join(map(str, route))}\n")
    
    # 输出车场分配结果
    print("车场分配详情:\n")
    for depot, count in depot_assignments.items():
        print(f"车场{depot}: 分配{count}件包裹")

关键优化点 #

• 路径时长矩阵需覆盖所有节点对的实际行驶时间，确保路线最优性
• 若允许车辆返回任意车场，可将data['ends']设为包含所有车场节点的列表，重复次数与车辆数一致
• 可通过调整first_solution_strategy和local_search_metaheuristic平衡求解速度和结果质量，比如用SAVINGS策略更快生成初始方案

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