VRP Resource Constraints bug - solver over allocating resources

[eitanbart]

Version: v 9.9.3963
Language: C#

Routing Solver
Windows 10

Please find an MRE below.
I expect to see a maximum of 2 jobs being executed simultaneously (as the ServiceSite has a capacity of 2).
From the output (also attached below), it seems that all three vehicles are executing jobs at ServiceSite at time 0, which would be violating the constraint. Not sure if my implementation is wrong, or if there is a bug in the solver.

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

/// <summary>
///   Vehicles Routing Problem (VRP) with Resource Constraints.
/// </summary>
public class VrpResources
{
  class DataModel
  {
    public int VehicleNumber = 3;
    public int JobNumber = 11;
    public int JobServiceTime = 600;
    public int ServiceSiteCapacity = 2;
    public int ServiceSiteClosingTime = 3540; //site is open for 59 mins
    public int Depot = 0;
  };

  /// <summary>
  ///   Print the solution.
  /// </summary>
  static void PrintSolution(in DataModel data, in RoutingModel routing, in RoutingIndexManager manager,
                            in Assignment solution)
  {
    if (solution is null) { 
      Console.WriteLine("No solution found");
      return;
    }

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

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

    // Create Routing Index Manager
    RoutingIndexManager manager =
        new RoutingIndexManager(data.JobNumber + 1, 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 serviceDuration = fromNode == 0 ? 0 : data.JobServiceTime;
      return serviceDuration;
    });

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

    // Add Distance constraint.
    routing.AddDimension(transitCallbackIndex, // transit callback
                         3600,                   // allow waiting time
                         2 * 3600,                   // vehicle maximum capacities
                         false,                // start cumul to zero
                         "Time");
    RoutingDimension timeDimension = routing.GetMutableDimension("Time");
    IntervalVar[] intervals = new IntervalVar[data.JobNumber];
    Solver solver = routing.solver();
    // Add time window constraints for each location except depot.
    for (int i = 0; i < data.JobNumber; i++)
    {
      long index = manager.NodeToIndex(i + 1);
      // service site is only open for 59 minutes
      // Since each job takes 10 minutes,
      // latest time to service site = (site closing time) - (job service time)
      timeDimension.CumulVar(index).SetRange(0, data.ServiceSiteClosingTime - data.JobServiceTime);

      intervals[i] = solver.MakeFixedDurationIntervalVar(timeDimension.CumulVar(index), data.JobServiceTime, $"service_interval{i}");
    }

    long[] depot_usage = Enumerable.Repeat<long>(1, intervals.Length).ToArray();
    solver.Add(solver.MakeCumulative(intervals, depot_usage, data.ServiceSiteCapacity, "depot"));

    // 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.Automatic;
    searchParameters.TimeLimit = new Google.Protobuf.WellKnownTypes.Duration
    {
      Seconds = 20,
    };

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

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

Objective 6600:
Route for Vehicle 0:
0 Time(0,0) -> 2 Time(0,600) -> 1 Time(600,1200) -> 0 Time(1800,1800)
Time of the route: 1800min
Route for Vehicle 1:
0 Time(0,0) -> 6 Time(0,660) -> 5 Time(600,1260) -> 4 Time(1860,1860) -> 3 Time(2460,2460) -> 0 Time(3060,3060)
Time of the route: 3060min
Route for Vehicle 2:
0 Time(0,0) -> 11 Time(0,540) -> 10 Time(600,1140) -> 9 Time(1740,1740) -> 8 Time(2340,2340) -> 7 Time(2940,2940) -> 0 Time(3540,3540)
Time of the route: 3540min
Total time of all routes: 8400min

[Mizux]

Few notes:

1. On my nuc using the main branch solver and net6.0 (archlinux) I didn't manage to find a solution (i.e. reproduce your output)...

2. According to the time CumulVar it seems the solver didn't "collapse" to a single solution,
   Means for the solver there is equivalent solutions having node 2 at time 0 and node 6 at 600 or vice-versa so solver return the "range" instead of arbitrary fixing each variables aka choose one solution among them (what I call collapsing (like in wave function collapse)). So Here solver produce kind of interleaved solutions which can be difficult to decipher...

At the end try to add this loop to force solver to fix each CumulVar...:

for (int i = 0; i < data.JobNumber; i++)
{
  long index = manager.NodeToIndex(i + 1);
  routing.AddVariableMinimizedByFinalizer(timeDimension.CumulVar(index));
}

3. Also, to get a solution, I've used this hack

public int ServiceSiteClosingTime = 3540+250;

note: Maybe allowing the solver to drop few node would be better in your case...

as well as enabling the GLS.

  searchParameters.FirstSolutionStrategy = FirstSolutionStrategy.Types.Value.Automatic;
  searchParameters.LocalSearchMetaheuristic = LocalSearchMetaheuristic.Types.Value.GuidedLocalSearch;
  searchParameters.TimeLimit = new Google.Protobuf.WellKnownTypes.Duration{ Seconds = 10, };

to get the output:

Start 69: dotnet_constraint_solver_Tsp_net60

69: Test command: /usr/bin/cmake "-E" "env" "--unset=TARGETNAME" "/usr/bin/dotnet" "run" "--no-build" "--framework" "net6.0" "-c" "Release"
69: Working Directory: /home/mizux/work/main/build/dotnet/constraint_solver/Tsp
69: Test timeout computed to be: 1500
69: Objective 6600:
69: Route for Vehicle 0:
69: 0 Time(0,0) -> 0 Time(0,0)
69: Time of the route: 0min
69: Route for Vehicle 1:
69: 0 Time(0,0) -> 5 Time(0,0) -> 4 Time(600,600) -> 3 Time(1200,1200) -> 2 Time(1800,1800) -> 1 Time(2400,2400) -> 0 Time(3000,3000)
69: Time of the route: 3000min
69: Route for Vehicle 2:
69: 0 Time(0,0) -> 11 Time(0,0) -> 10 Time(600,600) -> 9 Time(1200,1200) -> 8 Time(1800,1800) -> 7 Time(2400,2400) -> 6 Time(3000,3000) -> 0 Time(3600,3600)
69: Time of the route: 3600min
69: Total time of all routes: 6600min
1/1 Test #69: dotnet_constraint_solver_Tsp_net60 ...   Passed   10.56 sec

[eitanbart]

Hi @Mizux ,

To clarify - in this example, I expect the solver to find no solution (i.e. your output). Since the service site can only accommodate 2 vehicles at a time, and is only available for 59 minutes, a maximum of 10 jobs can be done, so I expect it to find no solution if jobs aren't allowed to be dropped.

1. Using the main branch solver (Windows 10, C#) I get the same result as before - with the solver over allocating resources, when it should find no solution.
2. Adding routing.AddVariableMinimizedByFinalizer(timeDimension.CumulVar(index)); for each service node results in no solution, so it does resolve the issue. However, I still believe there could be a bug, as this addition shouldn't be necessary? It looks like it will work for my scenario though.

Thank you for your assistance.