OR 工具 - VRP - 无法找到最佳解决方案的处理案例

Question

我正在基于 Google 的 ORTools 构建车辆路径问题的求解器。

对于简单问题或高容量问题，它工作正常，但是对于大多数“真实”数据集，我最终得到的解决方案要么运行无限期地或超时。

经过一番思考，我意识到并非所有现实世界的问题都可以解决或优化。例如。我可能希望大多数车辆每天行驶不超过 500 公里。但是，如果我必须向 600 公里以外的人送货，整个解决方案就会失败。

我该如何处理这些情况？现在它似乎是二元的通过或失败。我很高兴某些情况被忽略或 return 一个次优的解决方案。

这是我的解决方案的代码

public List<OptimisedVehicleRoute> Start(Location depot, List<Location> locations, int numVehicles = 1, float maxDistanceKmPerVehicle = 1000f, float maxDistanceKmSlack = 5f)
{
    // Create Routing Index Manager
    var depotIndex = locations.IndexOf(depot);
    var manager = new RoutingIndexManager(locations.Count, numVehicles, depotIndex);
    Console.WriteLine($"Depot at {depot.Postcode}");

    var routing = new RoutingModel(manager);

    var numCalls = 0l;

    int transitCallbackIndex = routing.RegisterTransitCallback((long fromIndex, long toIndex) =>
    {
        numCalls++;

        // Convert from routing variable Index to distance matrix NodeIndex.
        var fromNode = manager.IndexToNode(fromIndex);
        var toNode = manager.IndexToNode(toIndex);

        var fromLocation = locations[fromNode];
        var toLocation = locations[toNode];

        var mDistance = fromLocation.DistanceTo(toLocation);

        return mDistance;
    });

    // The arc cost evaluator tells the solver how to calculate the cost of travel between any two locations
    routing.SetArcCostEvaluatorOfAllVehicles(transitCallbackIndex);

    long maxVehicleDistanceSlack = (long)Math.Round(maxDistanceKmSlack * 1000); // slack per day
    long maxVehicleDistance = (long)Math.Round(maxDistanceKmPerVehicle * 1000); // 1000km max distance per day

    routing.AddDimension(transitCallbackIndex, maxVehicleDistanceSlack, maxVehicleDistance, true, "Distance");
    RoutingDimension distanceDimension = routing.GetMutableDimension("Distance");
    distanceDimension.SetGlobalSpanCostCoefficient(100);

    var searchParameters = operations_research_constraint_solver.DefaultRoutingSearchParameters();
    searchParameters.FirstSolutionStrategy = FirstSolutionStrategy.Types.Value.PathCheapestArc;

    var timer = new Stopwatch();
    timer.Start();
    searchParameters.LogSearch = true;
    var solution = routing.SolveWithParameters(searchParameters);
    timer.Stop();
    Console.WriteLine(timer.Elapsed.TotalSeconds);

    var optimisedVehicleRoutes = this.CreateOptimisedVehicleLocations(locations, numVehicles, routing, manager, solution);

    this.OptimisedDistanceKm = optimisedVehicleRoutes.Sum(r => r.TotalDistanceKm);

    routing.Dispose();

    return optimisedVehicleRoutes;
}

P.s。如果有人能帮助我理解“Slack”的实际用途，我将不胜感激。我最初假设这是每辆车的公差（即 10 公里的间隙允许车辆在其最大路线距离上行驶 10 公里）。但是现在我不确定

Answer 1

如果你的位置在 600 公里处，最大允许距离为 500 公里，你的问题基本上是不可行的...

但是您可以允许求解器使用 AddDisjunction() 删除此位置，使您的问题可行...

请查看文档站点上的示例：https://developers.google.com/optimization/routing/penalties

OR 工具 - VRP - 无法找到最佳解决方案的处理案例

OR Tools - VRP - Handling cases where no optimal solution can be found

c#

or-tools