如何用OR-Tools Python API建模基于负载的VRP碳排放弧成本？

核心解决方案 #

你的需求属于状态依赖型VRP（弧段成本随车辆实时负载变化），OR-Tools默认支持静态弧成本，但可通过自定义维度跟踪负载+动态成本回调的方式实现。以下是具体实现思路与代码示例：

关键步骤 #

• 预计算每个弧段的固定排放系数K和负载相关系数alpha
• 通过RoutingModel的维度（Dimension）跟踪车辆在每个节点的实时负载
• 编写动态成本回调函数，基于当前负载计算弧段的CO₂排放成本
• 将回调函数绑定为全局弧成本，替代默认的距离/时间成本

完整代码示例 #

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

def create_data_model():
    data = {}
    # 节点需求（索引0为仓库，需求为0）
    data['demands'] = [0, 10, 20, 15, 25]
    # 车辆容量与数量
    data['vehicle_capacities'] = [60]
    data['num_vehicles'] = 1
    data['depot'] = 0
    
    # 预定义弧段的CO₂排放参数（实际可根据地形/距离批量计算）
    num_nodes = len(data['demands'])
    data['K'] = [[0]*num_nodes for _ in range(num_nodes)]
    data['alpha'] = [[0]*num_nodes for _ in range(num_nodes)]
    
    # 示例弧段参数
    data['K'][0][1] = 50
    data['alpha'][0][1] = 2
    data['K'][1][2] = 30
    data['alpha'][1][2] = 1.5
    data['K'][2][3] = 40
    data['alpha'][2][3] = 1.8
    data['K'][3][4] = 60
    data['alpha'][3][4] = 2.2
    # 补充其他弧段参数...
    
    return data

def main():
    data = create_data_model()
    
    # 初始化路由索引管理器与模型
    manager = pywrapcp.RoutingIndexManager(
        len(data['demands']),
        data['num_vehicles'],
        data['depot']
    )
    routing = pywrapcp.RoutingModel(manager)
    
    # 添加负载跟踪维度，记录车辆在每个节点的剩余负载
    load_dim_name = 'Load'
    routing.AddDimension(
        # 需求回调：配送节点时负载减少对应需求值
        lambda from_idx, to_idx: (
            -data['demands'][manager.IndexToNode(to_idx)]
            if manager.IndexToNode(to_idx) != data['depot']
            else 0
        ),
        0,  # 无负松弛需求
        max(data['vehicle_capacities']),  # 最大负载限制
        True,  # 仓库出发时负载为0
        load_dim_name
    )
    load_dim = routing.GetDimensionOrDie(load_dim_name)
    
    # 定义CO₂排放成本回调函数
    def co2_cost_callback(from_idx, to_idx):
        from_node = manager.IndexToNode(from_idx)
        to_node = manager.IndexToNode(to_idx)
        # 获取当前出发节点的车辆负载
        current_load = load_dim.CumulVar(from_idx).Value()
        # 计算弧段CO₂排放成本
        return data['K'][from_node][to_node] + data['alpha'][from_node][to_node] * current_load
    
    # 注册回调函数并设置为全局弧成本
    transit_callback_idx = routing.RegisterTransitCallback(co2_cost_callback)
    routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_idx)
    
    # 配置求解参数（启发式算法更适合此类NP-hard问题）
    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 = 30
    
    # 求解并输出结果
    solution = routing.SolveWithParameters(search_params)
    if solution:
        print(f"总CO₂排放成本：{solution.ObjectiveValue()}")
        for vehicle_id in range(data['num_vehicles']):
            idx = routing.Start(vehicle_id)
            route_output = f"车辆{vehicle_id}路线：\n"
            current_load = 0
            while not routing.IsEnd(idx):
                node = manager.IndexToNode(idx)
                current_load += data['demands'][node]
                route_output += f"节点{node}(负载:{current_load}) -> "
                idx = solution.Value(routing.NextVar(idx))
            route_output += f"节点{manager.IndexToNode(idx)}\n"
            print(route_output)

if __name__ == '__main__':
    main()

方案优势 #

无需拆分两级优化，直接在OR-Tools中实现端到端的CO₂排放最小化求解，避免两级优化带来的次优解问题。负载维度的设计确保了每个弧段的成本计算完全依赖车辆当前状态，符合你的建模需求。

内容的提问来源于stack exchange，提问作者Rémi Soulignac