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

Question

我正在建立一个基于谷歌或谷歌工具的车辆路径问题求解器。

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

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

我该如何应对这些情况？现在，这似乎是一个二进制的通过或失败。我非常高兴某些案例被忽略，或者它返回了一个次优的解决方案。

这是我的解决方案的代码

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;
} 

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

Answer 1

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

但是你可以使用adddisconction（）使你的问题可行，让解算器删除这个位置。。。

请看看我们在留档网站上的例子：https://developers.google.com/optimization/routing/penalties