基于OR-Tools的分车型道路限制VRP路径规划求解求助

核心思路 #

由于卡车和依维柯的通行道路受限，各自的距离/时间矩阵独立，我们需要在OR-Tools的VRP模型中为每种车型绑定专属的成本矩阵，通过车辆类型标记来区分使用的矩阵，确保路径计算符合通行规则。

具体实现步骤及代码示例 #

以下是基于Python的OR-Tools实现，假设你已经有卡车的truck_dist_matrix、truck_time_matrix，依维柯的iveco_dist_matrix、iveco_time_matrix，且所有客户可被单一车型覆盖：

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

def create_data_model():
    """定义问题数据"""
    data = {}
    # 假设 depot 是索引0，客户是1..n
    data['truck_dist_matrix'] = truck_dist_matrix  # 你的卡车距离矩阵
    data['truck_time_matrix'] = truck_time_matrix  # 你的卡车时间矩阵
    data['iveco_dist_matrix'] = iveco_dist_matrix  # 你的依维柯距离矩阵
    data['iveco_time_matrix'] = iveco_time_matrix  # 你的依维柯时间矩阵
    data['num_vehicles'] = 4  # 示例：2辆卡车 + 2辆依维柯，可按需调整
    data['vehicle_types'] = [0, 0, 1, 1]  # 0=卡车，1=依维柯，对应车辆索引
    data['depot'] = 0
    return data

def main():
    data = create_data_model()
    
    # 创建路由索引管理器
    manager = pywrapcp.RoutingIndexManager(
        len(data['truck_dist_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)
        vehicle_idx = routing.VehicleIndexToVehicle(from_index)
        vehicle_type = data['vehicle_types'][vehicle_idx]
        if vehicle_type == 0:
            return data['truck_dist_matrix'][from_node][to_node]
        else:
            return data['iveco_dist_matrix'][from_node][to_node]
    
    # 注册距离成本
    transit_callback_index = routing.RegisterTransitCallback(distance_callback)
    routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)
    
    # （可选）添加时间窗口或容量约束，同样根据车辆类型选择对应矩阵
    def time_callback(from_index, to_index):
        from_node = manager.IndexToNode(from_index)
        to_node = manager.IndexToNode(to_index)
        vehicle_idx = routing.VehicleIndexToVehicle(from_index)
        vehicle_type = data['vehicle_types'][vehicle_idx]
        if vehicle_type == 0:
            return data['truck_time_matrix'][from_node][to_node]
        else:
            return data['iveco_time_matrix'][from_node][to_node]
    
    time_callback_index = routing.RegisterTransitCallback(time_callback)
    # 添加时间约束示例（按需调整）
    time = 'Time'
    routing.AddDimension(
        time_callback_index,
        30,  # 等待时间上限
        300,  # 车辆最大工作时间
        False,  # 不强制从零开始
        time
    )
    time_dimension = routing.GetDimensionOrDie(time)
    
    # 设置求解参数
    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)

def print_solution(data, manager, routing, solution):
    """打印路径结果"""
    total_distance = 0
    total_time = 0
    for vehicle_id in range(data['num_vehicles']):
        vehicle_type = '卡车' if data['vehicle_types'][vehicle_id] == 0 else '依维柯'
        index = routing.Start(vehicle_id)
        plan_output = f"{vehicle_type} {vehicle_id+1} 路径:\n"
        route_distance = 0
        route_time = 0
        while not routing.IsEnd(index):
            node_index = manager.IndexToNode(index)
            next_index = solution.Value(routing.NextVar(index))
            next_node_index = manager.IndexToNode(next_index)
            # 根据车辆类型计算当前路段的距离和时间
            if data['vehicle_types'][vehicle_id] == 0:
                route_distance += data['truck_dist_matrix'][node_index][next_node_index]
                route_time += data['truck_time_matrix'][node_index][next_node_index]
            else:
                route_distance += data['iveco_dist_matrix'][node_index][next_node_index]
                route_time += data['iveco_time_matrix'][node_index][next_node_index]
            plan_output += f" {node_index} ->"
            index = next_index
        plan_output += f" {manager.IndexToNode(index)}\n"
        plan_output += f" 路径距离: {route_distance} 单位\n"
        plan_output += f" 路径时间: {route_time} 单位\n"
        print(plan_output)
        total_distance += route_distance
        total_time += route_time
    print(f"总距离: {total_distance} 单位")
    print(f"总时间: {total_time} 单位")

if __name__ == '__main__':
    main()

关键说明 #

• 车辆类型标记：通过vehicle_types列表为每辆车指定类型，在回调函数中根据类型选择对应的矩阵，确保路径计算符合通行规则。
• 成本矩阵隔离：卡车和依维柯的矩阵完全独立，不会出现车辆走禁行道路的情况。
• 扩展性：如果需要添加容量约束，同样可以为不同车型设置不同的容量值，在约束中区分处理。

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