Google Or-Tools 车辆路径问题 - 解为空

Question

我不明白为什么解决方案对象总是空的。我正在尝试修改 Google OR-Tools 车辆路径问题的 C# 示例。该示例使用位置，我正在尝试使用距离矩阵。我的代码与 Python 示例非常相似，因此它应该可以工作。问题似乎出在 AddDistanceDimension 方法中。

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

namespace ConsoleApp1
{
    /// <summary>
    ///   This is a sample using the routing library .Net wrapper to solve a VRP problem.
    ///   A description of the problem can be found here:
    ///   http://en.wikipedia.org/wiki/Vehicle_routing_problem.
    /// </summary>
    class Program3
    {
        public class DataProblem
        {
            private int[,] distances_;

            // Constructor:
            public DataProblem()
            {
                distances_ = new int[,] {
                            { 0, 6177, 17282, 7866, 25029, 4511, 6120}, 
                            { 8469, 0, 9517, 1018, 17264, 6101, 615}, 
                            { 17504, 9865, 0, 10445, 9319, 15136, 10464}, 
                            { 7533, 1315, 9699, 0, 17446, 5165, 534}, 
                            { 25351, 17712, 10199, 18291, 0, 22983, 18310}, 
                            { 4993, 5221, 16381, 4620, 24128, 0, 4516}, 
                            { 5969, 958, 10309, 762, 18056, 4538, 0}
                    };
             }

            public int GetVehicleNumber() { return 4; }
            public ref readonly int[,] GetLocations() { return ref distances_; }
            public int GetLocationNumber() { return distances_.GetLength(0); }
            public int GetDepot() { return 0; }
        };


        public class DistanceMatrix : NodeEvaluator2
        {
            private int[,] distances;

            public DistanceMatrix(in DataProblem data)
            {
                distances = data.GetLocations();
            }

            public override long Run(int FromNode, int ToNode)
            {
                return distances[FromNode, ToNode];
            }
        };

        /// <summary>
        ///   Add distance Dimension
        /// </summary>
        static void AddDistanceDimension(in DataProblem data, in RoutingModel routing)
        {
            // public bool AddDimension(NodeEvaluator2 evaluator, long slack_max, long capacity, bool fix_start_cumul_to_zero, string name);
            // Returns false if a dimension with the same name has already been created (and doesn't create the new dimension).
            bool bResult = routing.AddDimension(
                new DistanceMatrix(data),
                0,  // null slack
                7000, // maximum distance per vehicle
                true, // start cumul to zero
                "Distance");
            Console.WriteLine("Was dimension dreated? " + bResult);
            RoutingDimension distanceDimension = routing.GetDimensionOrDie("Distance");
            // Try to minimize the max distance among vehicles.
            // /!\ It doesn't mean the standard deviation is minimized
            distanceDimension.SetGlobalSpanCostCoefficient(100);
        }

        /// <summary>
        ///   Print the solution
        /// </summary>
        static void PrintSolution(
            in DataProblem data,
            in RoutingModel routing,
            in Assignment solution)
        {
            Console.WriteLine("Objective: {0}", solution.ObjectiveValue());
            // Inspect solution.
            for (int i = 0; i < data.GetVehicleNumber(); ++i)
            {
                Console.WriteLine("Route for Vehicle " + i + ":");
                long distance = 0;
                var index = routing.Start(i);
                while (routing.IsEnd(index) == false)
                {
                    Console.Write("{0} -> ", routing.IndexToNode(index));
                    var previousIndex = index;
                    index = solution.Value(routing.NextVar(index));
                    distance += routing.GetArcCostForVehicle(previousIndex, index, i);
                }
                Console.WriteLine("{0}", routing.IndexToNode(index));
                Console.WriteLine("Distance of the route: {0}m", distance);
            }
            Console.ReadLine();
        }

        /// <summary>
        ///   Solves the current routing problem.
        /// </summary>
        static void Solve()
        {
            // Instantiate the data problem.
            DataProblem data = new DataProblem();

            // Create Routing Model
            RoutingModel routing = new RoutingModel(
                data.GetLocationNumber(),
                data.GetVehicleNumber(),
                data.GetDepot());

            // Debugging 
            Console.WriteLine("Number of locations: {0}", data.GetLocationNumber());
            Console.WriteLine("Number of vehicles: {0}", data.GetVehicleNumber());
            Console.WriteLine("Get depot: {0}", data.GetDepot());

            // Define weight cost of each edge
            NodeEvaluator2 distanceEvaluator = new DistanceMatrix(data);
            //protect callbacks from the GC
            GC.KeepAlive(distanceEvaluator);
            routing.SetArcCostEvaluatorOfAllVehicles(distanceEvaluator);
            AddDistanceDimension(data, routing);

            // Setting first solution heuristic (cheapest addition).
            RoutingSearchParameters searchParameters = RoutingModel.DefaultSearchParameters();
            searchParameters.FirstSolutionStrategy = FirstSolutionStrategy.Types.Value.PathCheapestArc;

            Assignment solution = routing.SolveWithParameters(searchParameters);
            PrintSolution(data, routing, solution);
        }

        public static void Main(String[] args)
        {
            Solve();
        }
    }
}

Answer 1

当您构建 DistanceDimension 时，您将 horizon 设置为 7000，而您的矩阵包含 25000、10000 等...

你确定你的数据是正确的吗？尝试增加 horizon (7000)...

Google Or-Tools 车辆路径问题 - 解为空

Google Or-Tools Vehicle Routing Problem - Solution is null

c#

or-tools