1

在 VRP 的几个问题中，当通知车辆总数时，妥协的是所有车辆都被使用并且至少它们访问一个节点。实际上，这甚至可能不是最好的，但我想了解为什么以及如何根据需要进行调整。下面的示例涉及根据 OR Tools 的简单 VRP 示例，距离矩阵中有一个小版本，并根据网站（博客）进行了一些更改 - https://activimetrics.com/blog/ortools/counting_dimension/。根据后者，可以进行路线的公平分配，这似乎非常有吸引力，因为通常，求解器会最小化最长的路线并最终使用更少的车辆并为其分配多个节点。一个重要的需求是使用一种使车辆行动的方法，确保它至少被使用一次。但是，如果使用 5 辆车来解决问题，根据逻辑和得到的结果，他到达那里，为每辆车放置一个节点，如果没有这个版本是不可能的。问题是，仅使用 4 辆车，求解器不再存在，它设法分配路线，但总是留下一辆车。

using System;
using System.Collections.Generic;
using Google.OrTools.ConstraintSolver;

public class VrpGlobalSpan
{
    class DataModel
    {      
        public long[,] DistanceMatrix = {
        {0, 9777, 10050,7908,10867,16601},
        {9777, 0, 4763, 4855, 19567,31500},
        {10050, 4763,0,2622,11733,35989},
        {7908,4855,2622,0,10966,27877},
        {10867,19567,11733,10966,0,27795},
        {16601,31500,35989,27877,27795,0},
    };
        public int VehicleNumber = 4;
        public int Depot = 0;
    };

    /// <summary>
    ///   Print the solution.
    /// </summary>
    static void PrintSolution(
        in DataModel data,
        in RoutingModel routing,
        in RoutingIndexManager manager,
        in Assignment solution)
    {
        // Inspect solution.
        long maxRouteDistance = 0;
        for (int i = 0; i < data.VehicleNumber; ++i)
        {
            Console.WriteLine("Route for Vehicle {0}:", i);
            long routeDistance = 0;
            var index = routing.Start(i);
            while (routing.IsEnd(index) == false)
            {
                Console.Write("{0} -> ", manager.IndexToNode((int)index));
                var previousIndex = index;
                index = solution.Value(routing.NextVar(index));
                routeDistance += routing.GetArcCostForVehicle(previousIndex, index, 0);
            }
            Console.WriteLine("{0}", manager.IndexToNode((int)index));
            Console.WriteLine("Distance of the route: {0}m", routeDistance);
            maxRouteDistance = Math.Max(routeDistance, maxRouteDistance);
        }
        Console.WriteLine("Maximum distance of the routes: {0}m", maxRouteDistance);
    }

    public static void Main(String[] args)
    {
        // Instantiate the data problem.
        DataModel data = new DataModel();

        // 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);
        
        double answer = 5/data.VehicleNumber +1;
        //double Math.Ceiling(answer);
        //double floor = (int)Math.Ceiling(answer);
        routing.AddConstantDimension(
            1,
            (int)Math.Ceiling(answer),
            true,  // start cumul to zero
            "Distance") ;
        RoutingDimension distanceDimension = routing.GetDimensionOrDie("Distance");
        //distanceDimension.SetGlobalSpanCostCoefficient(100);
        for (int i = 0; i < data.VehicleNumber; ++i)
        {
            distanceDimension.SetCumulVarSoftLowerBound(routing.End(i), 2, 1000000);
        }
        // Setting first solution heuristic.
        RoutingSearchParameters searchParameters =
          operations_research_constraint_solver.DefaultRoutingSearchParameters();
        //searchParameters.FirstSolutionStrategy =
        //  FirstSolutionStrategy.Types.Value.PathCheapestArc;
        searchParameters.TimeLimit = new Google.Protobuf.WellKnownTypes.Duration { Seconds = 5 }; 
        searchParameters.LocalSearchMetaheuristic = LocalSearchMetaheuristic.Types.Value.Automatic;       

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

        // Print solution on console.
        PrintSolution(data, routing, manager, solution);
    }
}

也许它一定是一个已经讨论过的话题，但我想了解和理解什么是最好的路径，以及采取什么措施来改变这个例子和其他例子，以更好地遵循。我提前感谢您的关注，我正在等待反馈。谢谢你。

4

0 回答 0