使用Google OR-Tools的C#带取送货时间窗VRP遇Null解问题排查

我用C#基于Google OR-Tools实现了带取送货（Pickups and Deliveries）与时间窗（Time Windows）的车辆路径规划（VRP），但多数场景下求解得到的solution为null，同时无法正确获取每个站点的配送时间。以下是我的代码：

public void VRP(DataModel data)
{
    try
    {
        // Create Routing Index Manager
        RoutingIndexManager manager = new RoutingIndexManager(data.DistanceMatrix.GetLength(0), data.VehicleNumber, data.Depot);

        // Create Routing Model.
        RoutingModel routing = new RoutingModel(manager);

        // Create and register a transit callback.
        int transitCallbackIndex = routing.RegisterTransitCallback((long fromIndex, long toIndex) =>
        {
            // Convert from routing variable Index to
            // distance matrix NodeIndex.
            var fromNode = manager.IndexToNode(fromIndex);
            var toNode = manager.IndexToNode(toIndex);
            return data.DistanceMatrix[fromNode, toNode];
        });

        // Define cost of each arc.
        routing.SetArcCostEvaluatorOfAllVehicles(transitCallbackIndex);

        int transitCallbackIndextime = routing.RegisterTransitCallback((long fromIndex, long toIndex) =>
        {
            // Convert from routing variable Index to time
            // matrix NodeIndex.
            var fromNode = manager.IndexToNode(fromIndex);
            var toNode = manager.IndexToNode(toIndex);
            return data.TimeMatrix[fromNode, toNode];
        });
        routing.SetArcCostEvaluatorOfAllVehicles(transitCallbackIndextime);

        // Add Distance constraint.
        routing.AddDimension(transitCallbackIndex, 0, Int32.MaxValue,
                             true, // start cumul to zero
                             "Distance");

        RoutingDimension distanceDimension = routing.GetMutableDimension("Distance");
        distanceDimension.SetGlobalSpanCostCoefficient(100);

        //Define Transportation Requests.
        if (data.PickupsDeliveries != null)
        {
            Solver solver = routing.solver();
            for (int i = 0; i < data.PickupsDeliveries.GetLength(0); i++)
            {
                long pickupIndex = manager.NodeToIndex(data.PickupsDeliveries[i][0]);
                long deliveryIndex = manager.NodeToIndex(data.PickupsDeliveries[i][1]);
                routing.AddPickupAndDelivery(pickupIndex, deliveryIndex);
                solver.Add(solver.MakeEquality(routing.VehicleVar(pickupIndex), routing.VehicleVar(deliveryIndex)));
                solver.Add(solver.MakeLessOrEqual(distanceDimension.CumulVar(pickupIndex),
                                                  distanceDimension.CumulVar(deliveryIndex)));
            }
        }

        if (data.TimeWindows != null)
        {
            for (int i = 0; i < data.TimeWindows.GetLength(0); i++)
            {
                for (int j = 0; j < data.TimeWindows.GetLength(1); j++)
                {
                    data.TimeWindows[i, j] *= 3600;
                }
            }

            routing.AddDimension(transitCallbackIndextime, // transit callback
             3600,                   // allow waiting time
             Int32.MaxValue,                   // vehicle maximum capacities
             false,                // start cumul to zero
             "Time");
            RoutingDimension timeDimension = routing.GetMutableDimension("Time");

            // Add time window constraints for each location except depot.
            for (int i = 1; i < data.TimeWindows.GetLength(0); ++i)
            {
                long index = manager.NodeToIndex(i);
                timeDimension.CumulVar(index).SetRange(data.TimeWindows[i, 0], data.TimeWindows[i, 1]);
            }
            // Add time window constraints for each vehicle start node.
            for (int i = 0; i < data.VehicleNumber; ++i)
            {
                long index = routing.Start(i);
                timeDimension.CumulVar(index).SetRange(data.TimeWindows[0, 0], data.TimeWindows[0, 1]);
            }
            for (int i = 0; i < data.VehicleNumber; ++i)
            {
                routing.AddVariableMinimizedByFinalizer(timeDimension.CumulVar(routing.Start(i)));
                routing.AddVariableMinimizedByFinalizer(timeDimension.CumulVar(routing.End(i)));
            }
        }

        // Setting first solution heuristic.
        RoutingSearchParameters searchParameters = operations_research_constraint_solver.DefaultRoutingSearchParameters();
        searchParameters.FirstSolutionStrategy = FirstSolutionStrategy.Types.Value.PathCheapestArc;

        // Solve the problem.
        Assignment solution = routing.SolveWithParameters(searchParameters);

        if (solution != null)
        {
            // Print solution on console.
            PrintSolutionVRP(data, routing, manager, solution);
            PrintSolutionTW(data, routing, manager, solution);
        }
    }
    catch (Exception ex)
    {
        throw ex;
    }
}

问题诊断与修复方案 #

1. 重复设置弧成本评估器 #

代码中先后调用两次SetArcCostEvaluatorOfAllVehicles，第二次用时间回调覆盖了距离回调，导致目标函数逻辑混乱。应保留主成本（比如距离）作为优化目标，时间维度仅作为约束使用：

// 仅设置一次主成本评估器（以距离为例）
routing.SetArcCostEvaluatorOfAllVehicles(transitCallbackIndex);

2. 取送货顺序约束错误 #

用距离维度约束取货在送货之前不合理——路径绕路可能导致取货点的累积距离大于送货点，直接引发约束冲突。应改用时间维度约束顺序：

// 替换原距离约束为时间约束
solver.Add(solver.MakeLessOrEqual(timeDimension.CumulVar(pickupIndex),
                                  timeDimension.CumulVar(deliveryIndex)));

3. 时间维度初始化参数错误 #

时间维度的start cumul to zero参数应设为true，确保车辆从 depot 出发时时间累积量为0，符合实际业务逻辑：

routing.AddDimension(transitCallbackIndextime,
 3600,                   // 允许等待时间
 Int32.MaxValue,         // 车辆最大时间容量
 true,                   // start cumul to zero
 "Time");

4. 时间窗约束冗余 #

不需要单独给车辆start节点设置时间窗，直接在循环中包含depot（i从0开始）即可：

// 给所有节点（包括depot）设置时间窗
for (int i = 0; i < data.TimeWindows.GetLength(0); ++i)
{
    long index = manager.NodeToIndex(i);
    timeDimension.CumulVar(index).SetRange(data.TimeWindows[i, 0], data.TimeWindows[i, 1]);
}

5. 优化求解参数 #

PathCheapestArc策略在复杂场景下可能无法生成可行解，建议尝试更鲁棒的初始解策略，并启用局部搜索：

RoutingSearchParameters searchParameters = operations_research_constraint_solver.DefaultRoutingSearchParameters();
// 尝试更优的初始解生成策略
searchParameters.FirstSolutionStrategy = FirstSolutionStrategy.Types.Value.Savings;
// 启用局部搜索改进解质量
searchParameters.LocalSearchMetaheuristic = LocalSearchMetaheuristic.Types.Value.GuidedLocalSearch;
searchParameters.TimeLimit = new Duration { Seconds = 10 }; // 设置求解时间限制

6. 获取站点配送时间 #

在打印结果的方法中，通过时间维度的累积变量获取每个站点的到达时间：

private void PrintSolutionTW(DataModel data, RoutingModel routing, RoutingIndexManager manager, Assignment solution)
{
    RoutingDimension timeDimension = routing.GetMutableDimension("Time");
    for (int vehicleId = 0; vehicleId < data.VehicleNumber; vehicleId++)
    {
        long index = routing.Start(vehicleId);
        Console.WriteLine($"--- Vehicle {vehicleId} Schedule ---");
        while (!routing.IsEnd(index))
        {
            long nodeIndex = manager.IndexToNode(index);
            long arrivalTimeSec = solution.Value(timeDimension.CumulVar(index));
            TimeSpan arrivalTime = TimeSpan.FromSeconds(arrivalTimeSec);
            Console.WriteLine($"Node {nodeIndex}: Arrival at {arrivalTime.Hours:D2}:{arrivalTime.Minutes:D2}");
            index = solution.Value(routing.NextVar(index));
        }
        long endIndex = routing.End(vehicleId);
        long endTimeSec = solution.Value(timeDimension.CumulVar(endIndex));
        TimeSpan endTime = TimeSpan.FromSeconds(endTimeSec);
        Console.WriteLine($"Vehicle {vehicleId} returns to depot at {endTime.Hours:D2}:{endTime.Minutes:D2}\n");
    }
}

修复后的完整代码 #

public void VRP(DataModel data)
{
    try
    {
        RoutingIndexManager manager = new RoutingIndexManager(data.DistanceMatrix.GetLength(0), data.VehicleNumber, data.Depot);
        RoutingModel routing = new RoutingModel(manager);

        // 距离回调
        int transitCallbackDistance = routing.RegisterTransitCallback((long fromIndex, long toIndex) =>
        {
            var fromNode = manager.IndexToNode(fromIndex);
            var toNode = manager.IndexToNode(toIndex);
            return data.DistanceMatrix[fromNode, toNode];
        });

        // 时间回调
        int transitCallbackTime = routing.RegisterTransitCallback((long fromIndex, long toIndex) =>
        {
            var fromNode = manager.IndexToNode(fromIndex);
            var toNode = manager.IndexToNode(toIndex);
            return data.TimeMatrix[fromNode, toNode];
        });

        // 设置主成本为距离
        routing.SetArcCostEvaluatorOfAllVehicles(transitCallbackDistance);

        // 添加距离维度
        routing.AddDimension(transitCallbackDistance, 0, Int32.MaxValue, true, "Distance");
        RoutingDimension distanceDimension = routing.GetMutableDimension("Distance");
        distanceDimension.SetGlobalSpanCostCoefficient(100);

        // 添加时间维度与时间窗约束
        RoutingDimension timeDimension = null;
        if (data.TimeWindows != null)
        {
            // 转换时间窗为秒
            for (int i = 0; i < data.TimeWindows.GetLength(0); i++)
            {
                data.TimeWindows[i, 0] *= 3600;
                data.TimeWindows[i, 1] *= 3600;
            }

            routing.AddDimension(transitCallbackTime, 3600, Int32.MaxValue, true, "Time");
            timeDimension = routing.GetMutableDimension("Time");

            // 设置所有节点的时间窗
            for (int i = 0; i < data.TimeWindows.GetLength(0); ++i)
            {
                long index = manager.NodeToIndex(i);
                timeDimension.CumulVar(index).SetRange(data.TimeWindows[i, 0], data.TimeWindows[i, 1]);
            }

            // 最小化车辆的总时间跨度
            for (int i = 0; i < data.VehicleNumber; ++i)
            {
                routing.AddVariableMinimizedByFinalizer(timeDimension.CumulVar(routing.End(i)));
            }
        }

        // 设置取送货约束
        if (data.PickupsDeliveries != null && timeDimension != null)
        {
            Solver solver = routing.solver();
            for (int i = 0; i < data.PickupsDeliveries.GetLength(0); i++)
            {
                long pickupIndex = manager.NodeToIndex(data.PickupsDeliveries[i][0]);
                long deliveryIndex = manager.NodeToIndex(data.PickupsDeliveries[i][1]);
                routing.AddPickupAndDelivery(pickupIndex, deliveryIndex);
                solver.Add(solver.MakeEquality(routing.VehicleVar(pickupIndex), routing.VehicleVar(deliveryIndex)));
                solver.Add(solver.MakeLessOrEqual(timeDimension.CumulVar(pickupIndex), timeDimension.CumulVar(deliveryIndex)));
            }
        }

        // 配置求解参数
        RoutingSearchParameters searchParameters = operations_research_constraint_solver.DefaultRoutingSearchParameters();
        searchParameters.FirstSolutionStrategy = FirstSolutionStrategy.Types.Value.Savings;
        searchParameters.LocalSearchMetaheuristic = LocalSearchMetaheuristic.Types.Value.GuidedLocalSearch;
        searchParameters.TimeLimit = new Duration { Seconds = 10 };

        // 求解
        Assignment solution = routing.SolveWithParameters(searchParameters);

        if (solution != null)
        {
            PrintSolutionVRP(data, routing, manager, solution);
            PrintSolutionTW(data, routing, manager, solution);
        }
        else
        {
            Console.WriteLine("No feasible solution found.");
        }
    }
    catch (Exception ex)
    {
        throw ex;
    }
}

private void PrintSolutionTW(DataModel data, RoutingModel routing, RoutingIndexManager manager, Assignment solution)
{
    RoutingDimension timeDimension = routing.GetMutableDimension("Time");
    for (int vehicleId = 0; vehicleId < data.VehicleNumber; vehicleId++)
    {
        long index = routing.Start(vehicleId);
        Console.WriteLine($"--- Vehicle {vehicleId} Schedule ---");
        while (!routing.IsEnd(index))
        {
            long nodeIndex = manager.IndexToNode(index);
            long arrivalTimeSec = solution.Value(timeDimension.CumulVar(index));
            TimeSpan arrivalTime = TimeSpan.FromSeconds(arrivalTimeSec);
            Console.WriteLine($"Node {nodeIndex}: Arrival at {arrivalTime.Hours:D2}:{arrivalTime.Minutes:D2}");
            index = solution.Value(routing.NextVar(index));
        }
        long endIndex = routing.End(vehicleId);
        long endTimeSec = solution.Value(timeDimension.CumulVar(endIndex));
        TimeSpan endTime = TimeSpan.FromSeconds(endTimeSec);
        Console.WriteLine($"Vehicle {vehicleId} returns to depot at {endTime.Hours:D2}:{endTime.Minutes:D2}\n");
    }
}

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