# Solution time out for VRPTW in or-tools

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++) {
}

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

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

• Did you try removing the fleet size constraint? It is the usual rule in the classical VRPTW instances from the literature to ignore the fleet size constraint. – Claudio Contardo Mar 3 '20 at 18:34
• @ClaudioContardo Do you mean there is a constraint saying all vehicles should be used ? No, I haven't removed any constraint, all my constraints are identical to the or-tools example with the addition of capacity constraints as the standard example and a fixed cost of some large number per vehicle. – k88 Mar 4 '20 at 1:48

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++) {
}
}


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.