OR-Tools求解VRP时车辆A未分配任务的问题及解决方法

问题根源 #

当前场景中，车辆B和C的访问范围刚好完全覆盖所有任务点（B负责1-8，C负责9-16），且它们的行驶距离均未超过3000的上限。算法找到的最优解无需动用车辆A——因为额外使用车辆不会降低总距离或全局跨度，默认情况下也没有车辆使用成本的约束，因此算法没有动力分配任务给A。

可行解决方案 #

方案1：添加车辆固定使用成本 #

给车辆设置固定出动成本，让算法在计算总成本时纳入车辆使用数量的考量。比如给B和C设置较高的固定成本，或者给A设置低成本，引导算法分配任务给A。

修改代码时，在create_data_model中添加固定成本配置：

data["fixed_costs"] = [0, 1000, 1000]  # 车辆A固定成本0，B、C为1000

然后在main函数中注册固定成本：

# 为每辆车设置固定使用成本
for vehicle_id in range(data["num_vehicles"]):
    routing.SetFixedCostOfVehicle(data["fixed_costs"][vehicle_id], vehicle_id)

方案2：强制车辆A必须执行任务 #

直接添加约束，要求车辆A的行驶距离大于0，确保其至少访问一个任务节点。

在main函数的距离维度设置后添加以下代码：

# 获取车辆A的起始、结束节点索引
start_index = routing.Start(0)
end_index = routing.End(0)
# 约束车辆A的累计行驶距离必须大于0
distance_dimension.CumulVar(start_index).SetMin(1)
distance_dimension.CumulVar(end_index).SetMin(1)

方案3：调整车辆最大行驶距离 #

降低车辆B和C的最大行驶距离，让它们无法单独覆盖各自的任务范围，必须将部分任务拆分给车辆A。

替换原有的AddDimension代码：

# 先创建维度，不设置全局最大距离
routing.AddDimension(
    transit_callback_index,
    0,  # 无松弛时间
    0,  # 全局上限设为0，后续单独配置车辆上限
    True,  # 起始累计值为0
    dimension_name,
)
distance_dimension = routing.GetDimensionOrDie(dimension_name)
# 为每辆车单独设置最大行驶距离
distance_dimension.SetVehicleMax(2000, 1)  # 车辆B最大2000m
distance_dimension.SetVehicleMax(2000, 2)  # 车辆C最大2000m
distance_dimension.SetVehicleMax(3000, 0)  # 车辆A最大3000m
distance_dimension.SetGlobalSpanCostCoefficient(100)

修改后的完整示例代码（方案2） #

from ortools.constraint_solver import routing_enums_pb2
from ortools.constraint_solver import pywrapcp
    
specific_locations = [
    [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16],
    [1,2,3,4,5,6,7,8],
    [9,10,11,12,13,14,15,16]
]
    

def create_data_model():
        """存储问题数据"""
        data = {}
        data["distance_matrix"] = [
            # fmt: off
          [0, 548, 776, 696, 582, 274, 502, 194, 308, 194, 536, 502, 388, 354, 468, 776, 662],
          [548, 0, 684, 308, 194, 502, 730, 354, 696, 742, 1084, 594, 480, 674, 1016, 868, 1210],
          [776, 684, 0, 992, 878, 502, 274, 810, 468, 742, 400, 1278, 1164, 1130, 788, 1552, 754],
          [696, 308, 992, 0, 114, 650, 878, 502, 844, 890, 1232, 514, 628, 822, 1164, 560, 1358],
          [582, 194, 878, 114, 0, 536, 764, 388, 730, 776, 1118, 400, 514, 708, 1050, 674, 1244],
          [274, 502, 502, 650, 536, 0, 228, 308, 194, 240, 582, 776, 662, 628, 514, 1050, 708],
          [502, 730, 274, 878, 764, 228, 0, 536, 194, 468, 354, 1004, 890, 856, 514, 1278, 480],
          [194, 354, 810, 502, 388, 308, 536, 0, 342, 388, 730, 468, 354, 320, 662, 742, 856],
          [308, 696, 468, 844, 730, 194, 194, 342, 0, 274, 388, 810, 696, 662, 320, 1084, 514],
          [194, 742, 742, 890, 776, 240, 468, 388, 274, 0, 342, 536, 422, 388, 274, 810, 468],
          [536, 1084, 400, 1232, 1118, 582, 354, 730, 388, 342, 0, 878, 764, 730, 388, 1152, 354],
          [502, 594, 1278, 514, 400, 776, 1004, 468, 810, 536, 878, 0, 114, 308, 650, 274, 844],
          [388, 480, 1164, 628, 514, 662, 890, 354, 696, 422, 764, 114, 0, 194, 536, 388, 730],
          [354, 674, 1130, 822, 708, 628, 856, 320, 662, 388, 730, 308, 194, 0, 342, 422, 536],
          [468, 1016, 788, 1164, 1050, 514, 514, 662, 320, 274, 388, 650, 536, 342, 0, 764, 194],
          [776, 868, 1552, 560, 674, 1050, 1278, 742, 1084, 810, 1152, 274, 388, 422, 764, 0, 798],
          [662, 1210, 754, 1358, 1244, 708, 480, 856, 514, 468, 354, 844, 730, 536, 194, 798, 0],
            # fmt: on
        ]
        data["num_vehicles"] = 3
        data["depot"] = 0
        return data
    

def print_solution(data, manager, routing, solution):
        """在控制台打印解"""
        print(f"目标值: {solution.ObjectiveValue()}")
        max_route_distance = 0
        for vehicle_id in range(data["num_vehicles"]):
            index = routing.Start(vehicle_id)
            plan_output = f"车辆 {vehicle_id} 的路线:\n"
            route_distance = 0
            while not routing.IsEnd(index):
                plan_output += f" {manager.IndexToNode(index)} -> "
                previous_index = index
                index = solution.Value(routing.NextVar(index))
                route_distance += routing.GetArcCostForVehicle(
                    previous_index, index, vehicle_id
                )
            plan_output += f"{manager.IndexToNode(index)}\n"
            plan_output += f"路线距离: {route_distance}m\n"
            print(plan_output)
            max_route_distance = max(route_distance, max_route_distance)
        print(f"最大路线距离: {max_route_distance}m")
    
    

def 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)

        # 添加距离约束维度
        dimension_name = "Distance"
        routing.AddDimension(
            transit_callback_index,
            0,  # 无松弛时间
            3000,  # 车辆最大行驶距离
            True,  # 起始累计值为0
            dimension_name,
        )
        distance_dimension = routing.GetDimensionOrDie(dimension_name)
        distance_dimension.SetGlobalSpanCostCoefficient(100)

        # 强制车辆A必须执行任务：约束其累计行驶距离大于0
        start_index = routing.Start(0)
        end_index = routing.End(0)
        distance_dimension.CumulVar(start_index).SetMin(1)
        distance_dimension.CumulVar(end_index).SetMin(1)

        # 设置车辆可访问的节点
        for i in range(data["num_vehicles"]):
            for j in range(len(specific_locations[i])):  
                routing.SetAllowedVehiclesForIndex([i], manager.NodeToIndex(specific_locations[i][j]))

        # 设置搜索参数
        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)
        else:
            print("未找到可行解!")


if __name__ == "__main__":
    main()

预期效果 #

添加强制约束后，算法会将部分任务从B或C转移到A，确保A被分配任务，典型输出类似：

目标值: 268248
车辆 0 的路线:
 0 -> 7 -> 3 -> 4 -> 0
路线距离: 1298m

车辆 1 的路线:
 0 -> 5 -> 8 -> 6 -> 2 -> 1 -> 0
路线距离: 2470m

车辆 2 的路线:
 0 -> 9 -> 10 -> 16 -> 14 -> 13 -> 15 -> 11 -> 12 -> 0
路线距离: 2624m
最大路线距离: 2624m

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