Solution time out for VRPTW in or-tools

Question

I am experimenting around with or-tools and somehow I can't get a solution for the VRPTW problem for any of the instances I have tested from Gehring & Homberger datasets.

The smallest dataset I have tested is with 200 nodes (+1 for the depot) and 50 vehicles. The longest I have run for is 30 minutes 6 hours (!) and the algorithm I am trying is Automatic for the FirstSolutionStrategy and Guided_Local_Search for the LocalSearchMetaheuristic. The status I get is 3 indicating that the solver cannot find a solution in time.

I do get a solution if I remove the time window constraints, but the moment I add them back in it cannot find a solution. As far as I have been able to check the modeling and the constraints being set seems about correct. Here is the piece of code that adds the time window constraints.

See code below, note that I have omitted some code for brevity, but this is the most of it anyway.

class OrToolsProblem {
/** Time windows is  for the locations. Index 0 is that time windows of the depot*/
  private long[][] timeWindows;
  /** Array of travel times between locations. Index 0 is the travel distances from depot.*/
  private long[][] timeMatrix;
  /** Number of vehicles*/
  private int vehicleNumber;
  /** Index of depot.*/
  private int depotIndex;

  private long[] vehicleCapacities;
  private long[] demands;

  private RoutingModel routingModel;
  private Assignment solution;
  private RoutingIndexManager routingIndexManager;

 /* Constructor and methods to set various constraints */

   private void setTimeWindowConstraints() {
    RoutingDimension timeDimension = routingModel.getMutableDimension("TravelTime");

    // add time window constraints for each location except depot.
    for (int i=1; i < timeWindows.length; i++) {
      long index = routingIndexManager.nodeToIndex(i);
      timeDimension.cumulVar(index).setRange(timeWindows[i][0], timeWindows[i][1]);
    }

    // add time window constraints for each vehicle's start node
    for (int i=0 ; i < vehicleNumber; i++) {
      long index = routingModel.start(i);
      long[] timeWindowsForDepot = timeWindows[0];
      timeDimension.cumulVar(index).setRange(timeWindowsForDepot[0], timeWindowsForDepot[1]);
    }

    for(int i=0; i < vehicleNumber; i++) {
      routingModel.addVariableMinimizedByFinalizer(timeDimension.cumulVar(routingModel.start(i)));
      routingModel.addVariableMinimizedByFinalizer(timeDimension.cumulVar(routingModel.end(i)));
    }


  }
    private void setTravelTimeMatrix() {
    // minimise total travel time
    final int transitCallBackIndex = routingModel.registerTransitCallback(
            (long fromIndex, long toIndex) -> {
              // Convert from routing variable Index to user NodeIndex
              int fromNode = routingIndexManager.indexToNode(fromIndex);
              int toNode = routingIndexManager.indexToNode(toIndex);
              return timeMatrix[fromNode][toNode];
            }
    );
    routingModel.setArcCostEvaluatorOfAllVehicles(transitCallBackIndex);
    routingModel.addDimension(transitCallBackIndex, 250, Integer.MAX_VALUE, false, "TravelTime");
  }

  public void buildProblem() {
    routingIndexManager = new RoutingIndexManager(timeMatrix.length, vehicleNumber, depotIndex);
    routingModel = new RoutingModel(routingIndexManager);
    setCapacityConstrainsts();
    setTravelTimeMatrix();
    setTimeWindowConstraints();

    // set service times
    // Or tools does not support separate service times, hence this is added to the travel time matrix.

    // minimise number of used vehicle
    routingModel.setFixedCostOfAllVehicles(10000);

  }
}

Below is the method that runs the solver:

 public Assignment run() {
    if (uninitiatedVrpProblem == null || problemType == null)  {
      throw new NullPointerException("The variable uninitiatedVrpProblem is not yet initialised. ");
    }

    uninitiatedVrpProblem.buildProblem();
    RoutingSearchParameters searchParameters = main
        .defaultRoutingSearchParameters()
        .toBuilder()
        .setFirstSolutionStrategy(FirstSolutionStrategy.Value.AUTOMATIC)
        .setLocalSearchMetaheuristic(LocalSearchMetaheuristic.Value.GUIDED_LOCAL_SEARCH)
        .setTimeLimit(Duration.newBuilder().setSeconds(60 * 5).build())
        .build();

    uninitiatedVrpProblem.solve(searchParameters);
    this.solvedSolution = uninitiatedVrpProblem.getSolution();
    return solvedSolution;
  }

Any ideas what I am doing wrong, or do I need to simply give it more time? (Though I am confident 30 mins should be more than enough for a problem this small).

Answer 1

Ok so I have figured out a way to speed up the solver and have it return a solution. Key here seems to be adding the following method.

 public void setDisjunction() {                                                                                               
   long penalty = 100000;                                                                                                  
   for (int i =1; i < timeMatrix.length; i++) {                                                                            
     routingModel.addDisjunction(new long[] {routingIndexManager.nodeToIndex(i)}, penalty);                                
   }                                                                                                                       
 }                                                                                                                         

And then

 public void buildProblem() {                                                                                                        
   routingIndexManager = new RoutingIndexManager(timeMatrix.length, vehicleNumber, depotIndex);                                      
   routingModel = new RoutingModel(routingIndexManager);                                                                             
   setCapacityConstrainsts();                                                                                                        
   setTravelTimeMatrix();                                                                                                            
   setTimeWindowConstraints();                                                                                                       
   setDisjunction();                                                                                                                    
   // set service times                                                                                                              
   // Or tools does not support separate service times, hence this is added to the travel time matrix.                               

   // minimise number of used vehicle                                                                                                
   routingModel.setFixedCostOfAllVehicles(10000);                                                                                    
 }                                                                                                                                   

See explanation for what addDisjunction does here. Now I don't know the internals of or-tools that well, but my understanding is that the first solution strategy is unable to build a feasible solution as the problem has too many constraints. However, doing this I noticed it doesn't visit all nodes.

I'll update my answer when I found out what set of parameters make it visit all nodes.