Need help on VRPTW with multiple start/end and capacity constraint

[jayendhar-cf]

OR Tool/Language used: Version: v9.6 Language: C# Solver: Routing OS: Windows 11

I am trying to get an optimal route solution for a VRPTW problem where vehicles (in my example, I have 4 vehicles) have to be certain locations within specific time windows, and the vehicles will start and end at different locations (note: for a given vehicle, the start and end location will be the same).

Below is my C# code. I am getting a "NULL" for the solution. I looked around for multiple references but did not see an implementation of VRPTW with multiple start/ends (I did see an implementation of multiple start/ends with the distance matrix, but in my case, the time windows are needed).

Any advice on the below would help.

` internal class DataModel { public long[,] TimeMatrix = { { 0, 6, 9, 8, 7, 3, 6, 2, 3, 2, 6, 6, 4, 4, 5, 9, 7 }, { 6, 0, 8, 3, 2, 6, 8, 4, 8, 8, 13, 7, 5, 8, 12, 10, 14 }, { 9, 8, 0, 11, 10, 6, 3, 9, 5, 8, 4, 15, 14, 13, 9, 18, 9 }, { 8, 3, 11, 0, 1, 7, 10, 6, 10, 10, 14, 6, 7, 9, 14, 6, 16 }, { 7, 2, 10, 1, 0, 6, 9, 4, 8, 9, 13, 4, 6, 8, 12, 8, 14 }, { 3, 6, 6, 7, 6, 0, 2, 3, 2, 2, 7, 9, 7, 7, 6, 12, 8 }, { 6, 8, 3, 10, 9, 2, 0, 6, 2, 5, 4, 12, 10, 10, 6, 15, 5 }, { 2, 4, 9, 6, 4, 3, 6, 0, 4, 4, 8, 5, 4, 3, 7, 8, 10 }, { 3, 8, 5, 10, 8, 2, 2, 4, 0, 3, 4, 9, 8, 7, 3, 13, 6 }, { 2, 8, 8, 10, 9, 2, 5, 4, 3, 0, 4, 6, 5, 4, 3, 9, 5 }, { 6, 13, 4, 14, 13, 7, 4, 8, 4, 4, 0, 10, 9, 8, 4, 13, 4 }, { 6, 7, 15, 6, 4, 9, 12, 5, 9, 6, 10, 0, 1, 3, 7, 3, 10 }, { 4, 5, 14, 7, 6, 7, 10, 4, 8, 5, 9, 1, 0, 2, 6, 4, 8 }, { 4, 8, 13, 9, 8, 7, 10, 3, 7, 4, 8, 3, 2, 0, 4, 5, 6 }, { 5, 12, 9, 14, 12, 6, 6, 7, 3, 3, 4, 7, 6, 4, 0, 9, 2 }, { 9, 10, 18, 6, 8, 12, 15, 8, 13, 9, 13, 3, 4, 5, 9, 0, 9 }, { 7, 14, 9, 16, 14, 8, 5, 10, 6, 5, 4, 10, 8, 6, 2, 9, 0 }, }; public long[,] TimeWindows = { { 8, 10}, // vehicle 1 { 8, 10 }, // vehicle 2 { 8, 10 }, // vehicle 3 { 8, 10 }, // vehicle 4 { 10, 11}, // delivery loc 1 { 9, 10 }, // delivery loc 2 { 9, 10 }, // delivery loc 3 { 12, 13 }, // delivery loc 4 { 12, 13 }, // delivery loc 5 { 13, 14 }, // delivery loc 6 { 13, 14 }, // delivery loc 7 { 13, 14 }, // delivery loc 8 { 13, 14 }, // delivery loc 9 { 15, 16 }, // delivery loc 10 { 15, 16 }, // delivery loc 11 { 17, 18 }, // delivery loc 12 { 17, 18 }, // delivery loc 13 }; public int[] Starts = { 0, 1, 2, 3 }; public int[] Ends = { 0, 1, 2, 3 }; public int VehicleNumber = 4; public long[] Demands = { 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }; / 0 for the first 4 locations since they are the vehicle start points / public long[] VehicleCapacities = { 9, 2, 5, 8 };

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

        // Create Routing Index Manager
        RoutingIndexManager manager =
            new RoutingIndexManager(data.TimeMatrix.GetLength(0), data.VehicleNumber, data.Starts, data.Ends);

        // 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 time
            // matrix NodeIndex.
            var fromNode = manager.IndexToNode(fromIndex);
            var toNode = manager.IndexToNode(toIndex);
            return data.TimeMatrix[fromNode, toNode];
        });

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

        // Add Time constraint.
        routing.AddDimension(transitCallbackIndex, // transit callback
                             30,                   // allow waiting time
                             30,                   // vehicle maximum capacities
                             false,                // start cumul to zero
                             "Time");
        // Add Capacity constraint.
        int demandCallbackIndex = routing.RegisterUnaryTransitCallback((long fromIndex) =>
        {
            // Convert from routing variable Index to
            // demand NodeIndex.
            var fromNode =
                manager.IndexToNode(fromIndex);
            return data.Demands[fromNode];
        });

        routing.AddDimensionWithVehicleCapacity(demandCallbackIndex, 0, // null capacity slack
                                            data.VehicleCapacities, // vehicle maximum capacities
                                            true,                   // start cumul to zero
                                            "Capacity");
        RoutingDimension timeDimension = routing.GetMutableDimension("Time");
        // Add time window constraints for each location except depot.
        for (int i = data.VehicleNumber; 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[i, 0], data.TimeWindows[i, 1]);
        }

        //// Instantiate route start and end times to produce feasible times.
        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);

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

    static void PrintSolution(in GoogleORVRPTW data, in RoutingModel routing, in RoutingIndexManager manager,
                          in Assignment solution)
    {
        Console.WriteLine($"Objective {solution.ObjectiveValue()}:");

        // Inspect solution.
        RoutingDimension timeDimension = routing.GetMutableDimension("Time");
        long totalTime = 0;
        for (int i = 0; i < data.VehicleNumber; ++i)
        {
            Console.WriteLine("Route for Vehicle {0}:", i);
            var index = routing.Start(i);
            while (routing.IsEnd(index) == false)
            {
                var timeVar = timeDimension.CumulVar(index);
                Console.Write("{0} Time({1},{2}) -> ", manager.IndexToNode(index), solution.Min(timeVar),
                              solution.Max(timeVar));
                index = solution.Value(routing.NextVar(index));
            }
            var endTimeVar = timeDimension.CumulVar(index);
            Console.WriteLine("{0} Time({1},{2})", manager.IndexToNode(index), solution.Min(endTimeVar),
                              solution.Max(endTimeVar));
            Console.WriteLine("Time of the route: {0}min", solution.Min(endTimeVar));
            totalTime += solution.Min(endTimeVar);
        }
        Console.WriteLine("Total time of all routes: {0}min", totalTime);
    }

}

`

[jayendhar-cf]

Also, I tried adding the routing timeout and solution limit, by adding the below lines. When I try printing the solution, I get a status code of "3", which I think corresponds to "ROUTING_FAIL_TIMEOUT: Time limit reached before finding a solution." The strange part is the timeout occurs much before 500 seconds (Around 20 seconds or so).

searchParameters.TimeLimit = new Duration { Seconds = 500 }; searchParameters.SolutionLimit = 100; Console.WriteLine("Solution Status: " + routing.GetStatus().ToString());

[Regista6]

3 corresponds to ROUTING_FAIL. Maybe try changing first_solution_strategy. https://github.com/google/or-tools/blob/a48bab16acbc389fb07770007c377d1019d4ca6c/ortools/constraint_solver/routing.h#L248-L266

[jayendhar-cf]

I tried all the solution strategy options. The output is always 3 ROUTING_FAIL_TIMEOUT.

I guess I am not building the routing model in the required manner for VRPTW with multiple/start/end and Capacity constraint. I tried to look for examples in the samples and I could not find one.

This is what I tried to do: 1) I took the sample code for the VRPTW (https://developers.google.com/optimization/routing/vrptw) -- this had a single "depot" as the start/end location for all vehicles. Since I have multiple starts/ends, I initialized the routing manager as follows: RoutingIndexManager manager = new RoutingIndexManager(data.TimeMatrix.GetLength(0), data.VehicleNumber, data.Starts, data.Ends);

2) I am building the time dimension as provided in the sample, but with a minor adjustment to address multiple starts/ends. ` RoutingDimension timeDimension = routing.GetMutableDimension("Time"); // Add time window constraints for each location except vehicle start location (iteration starts from Vehicle Number) for (int i = data.VehicleNumber; 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[i, 0], data.TimeWindows[i, 1]); }

        //// Instantiate route start and end times to produce feasible times.
        for (int i = 0; i < data.VehicleNumber; ++i)
        {
            routing.AddVariableMinimizedByFinalizer(timeDimension.CumulVar(routing.Start(i)));
            routing.AddVariableMinimizedByFinalizer(timeDimension.CumulVar(routing.End(i)));
        }

3) Then added the routing dimension for vehicle capacity using the demand callback index. // Add Capacity constraint. int demandCallbackIndex = routing.RegisterUnaryTransitCallback((long fromIndex) => { // Convert from routing variable Index to // demand NodeIndex. var fromNode = manager.IndexToNode(fromIndex); return data.Demands[fromNode]; });

        routing.AddDimensionWithVehicleCapacity(demandCallbackIndex, 0, // null capacity slack
                                            data.VehicleCapacities, // vehicle maximum capacities
                                            true,                   // start cumul to zero
                                            "Capacity");

`

Would like advise on where I am going wrong here.