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.

or-tools/ortools/constraint_solver/routing.h

Lines 248 to 266 in a48bab1

	/// Status of the search.
	enum Status {
	/// Problem not solved yet (before calling RoutingModel::Solve()).
	ROUTING_NOT_SOLVED,
	/// Problem solved successfully after calling RoutingModel::Solve().
	ROUTING_SUCCESS,
	/// Problem solved successfully after calling RoutingModel::Solve(), except
	/// that a local optimum has not been reached. Leaving more time would allow
	/// improving the solution.
	ROUTING_PARTIAL_SUCCESS_LOCAL_OPTIMUM_NOT_REACHED,
	/// No solution found to the problem after calling RoutingModel::Solve().
	ROUTING_FAIL,
	/// Time limit reached before finding a solution with RoutingModel::Solve().
	ROUTING_FAIL_TIMEOUT,
	/// Model, model parameters or flags are not valid.
	ROUTING_INVALID,
	/// Problem proven to be infeasible.
	ROUTING_INFEASIBLE
	};

[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.

[Regista6]

Your problem could be too constrained. Maybe allow nodes to be dropped.

penalty = 1_000_000_000_000_000_000
for node in range(4, len(data['time_matrix'])):
    routing.AddDisjunction([manager.NodeToIndex(node)], penalty)