# Incorrect solution for Vehicle Routing Problem in or-tools

I am trying to understand how the Vehicle Routing Problem is solved in OR-Tools. Using the example given here, I have tried to solve the following distance matrix with 9 separate vehicles:

[0, 1, 1, 1, 1, 1, 1, 1, 1, 1],
[1, 0, 1, 1, 1, 1, 1, 1, 1, 1],
[1, 1, 0, 1, 1, 1, 1, 1, 1, 1],
[1, 1, 1, 0, 1, 1, 1, 1, 1, 1],
[1, 1, 1, 1, 0, 1, 1, 1, 1, 1],
[1, 1, 1, 1, 1, 0, 1, 1, 1, 1],
[1, 1, 1, 1, 1, 1, 0, 1, 1, 1],
[1, 1, 1, 1, 1, 1, 1, 0, 1, 1],
[1, 1, 1, 1, 1, 1, 1, 1, 0, 1],
[1, 1, 1, 1, 1, 1, 1, 1, 1, 0]


My understanding is, that the example given should minimize the longest route, resulting in 9 routes of similar length. To quote the example:

This makes the global span the predominant factor in the objective function, so the program minimizes the length of the longest route.

In this simple example, each vehicle should visit one node and return to the depot.

0 -> 6 -> 7 -> 8 -> 9 -> 0
0 -> 4 -> 3 -> 2 -> 1 -> 0
0 -> 5 -> 0
... 6x times ...
0 -> 0


Am I misunderstanding the VRP, OR-Tools, or is there a more basic mistake?

I have tried various settings for FirstSolutionStrategy and LocalSearchMetaheuristic, and used other symmetric matrices with the same result: It's always possible to remove a node from the longest route, assign it to an unused one and thereby trivially improve the solution.

Code used:

import com.google.ortools.constraintsolver.Assignment;
import java.util.logging.Logger;

/** Minimal VRP.*/
public class VrpGlobalSpan {
static {
}

private static final Logger logger = Logger.getLogger(VrpGlobalSpan.class.getName());

static class DataModel {
public final long[][] distanceMatrix = {
{0,1,1,1,1,1,1,1,1,1},
{1,0,1,1,1,1,1,1,1,1},
{1,1,0,1,1,1,1,1,1,1},
{1,1,1,0,1,1,1,1,1,1},
{1,1,1,1,0,1,1,1,1,1},
{1,1,1,1,1,0,1,1,1,1},
{1,1,1,1,1,1,0,1,1,1},
{1,1,1,1,1,1,1,0,1,1},
{1,1,1,1,1,1,1,1,0,1},
{1,1,1,1,1,1,1,1,1,0}
};
public final int vehicleNumber = 9;
public final int depot = 0;
}

/// @brief Print the solution.
static void printSolution(
DataModel data, RoutingModel routing, RoutingIndexManager manager, Assignment solution) {
// Inspect solution.
long maxRouteDistance = 0;
for (int i = 0; i < data.vehicleNumber; ++i) {
long index = routing.start(i);
logger.info("Route for Vehicle " + i + ":");
long routeDistance = 0;
String route = "";
while (!routing.isEnd(index)) {
route += manager.indexToNode(index) + " -> ";
long previousIndex = index;
index = solution.value(routing.nextVar(index));
routeDistance += routing.getArcCostForVehicle(previousIndex, index, i);
}
logger.info(route + manager.indexToNode(index));
logger.info("Distance of the route: " + routeDistance + "m");
maxRouteDistance = Math.max(routeDistance, maxRouteDistance);
}
logger.info("Maximum of the route distances: " + maxRouteDistance + "m");
}

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

// Create Routing Index Manager
RoutingIndexManager manager =
new RoutingIndexManager(data.distanceMatrix.length, data.vehicleNumber, data.depot);

// Create Routing Model.
RoutingModel routing = new RoutingModel(manager);

// Create and register a transit callback.
final int transitCallbackIndex =
routing.registerTransitCallback((long fromIndex, long toIndex) -> {
// Convert from routing variable Index to user NodeIndex.
int fromNode = manager.indexToNode(fromIndex);
int toNode = manager.indexToNode(toIndex);
return data.distanceMatrix[fromNode][toNode];
});

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

true, // start cumul to zero
"Distance");
RoutingDimension distanceDimension = routing.getMutableDimension("Distance");
distanceDimension.setGlobalSpanCostCoefficient(100);

// Setting first solution heuristic.
RoutingSearchParameters searchParameters =
main.defaultRoutingSearchParameters()
.toBuilder()
.setFirstSolutionStrategy(FirstSolutionStrategy.Value.PATH_CHEAPEST_ARC)
.build();

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

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

• can you post a minimal working example? I.e. some code which can be run if you have or-tools installed. Oct 24, 2019 at 20:32
• I added the code, but apart from the matrix is the same code that is found in the example here developers.google.com/optimization/routing/vrp
– Joba
Oct 24, 2019 at 20:43
• @Joba Did you (or anybody) ever get anywhere with this? I am facing a similar issue. Dec 2, 2019 at 16:00
• My "solution" was to decrease the maximum route length until OR-Tools was unable to find a solution. I am obviously not happy with this, so let me know if you find a way to do this more efficiently. Maybe opening an issue on Github helps.
– Joba
Dec 3, 2019 at 13:27

I notice you are using FirstSolutionStrategy.Value.PATH_CHEAPEST_ARC. If this name does what it suggests, then it's probably a greedy strategy that chooses between distance 1, 1 and so on.

The clue is that you're using a strategy that does not guarantee optimal solutions. The structure also suggests that a certain random seed is used; there is an iteration above five until the largest node number is reached, an iteration under five until the lowest number is reached and in the end, five is left.

Edit: For any strategy to work, you cannot force it into making random decisions (such as choosing between 1 and 1). This matrix offers enough variation for a simple strategy to work.

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9],
[1, 0, 100, 100, 100, 100, 100, 100, 100, 100],
[2, 100, 0, 100, 100, 100, 100, 100, 100, 100],
[3, 100, 100, 0, 100, 100, 100, 100, 100, 100],
[4, 100, 100, 100, 0, 100, 100, 100, 100, 100],
[5, 100, 100, 100, 100, 0, 100, 100, 100, 100],
[6, 100, 100, 100, 100, 100, 0, 100, 100, 100],
[7, 100, 100, 100, 100, 100, 100, 0, 100, 100],
[8, 100, 100, 100, 100, 100, 100, 100, 0, 100],
[9, 100, 100, 100, 100, 100, 100, 100, 100, 0]

• I have experimented with other solution strategies and got similar results every time. I do not expect an optimal solution, but I'm quite surprised to see a solution like this. The optimal result would have a maximum path length of 2, while the current one is 5.
– Joba
Oct 25, 2019 at 12:53
• My best guess is that the uniform distance matrix causes such results. I would experiment with a symmetric matrix with unique values (diagonal excluded), maybe distanceMatrix[0][i] := i and high values for distances between non-depot nodes. Oct 25, 2019 at 13:49
• I have just tried that an updated the question with additional information. It sadly didn't change anything.
– Joba
Oct 25, 2019 at 15:12
• I have tried my own suggestion in python and I get 18, which is the theoretical minimum. I am now convinced that the problem lies in the fact that there is not enough variation in your initial data for a heuristic to work decently. Oct 25, 2019 at 15:53
• This seems to be the reason. Another observation: If I change the 3000 parameter used when creating the dimension to 2 (or whatever the theoretical minimum is), I indeed get an optimal solution.
– Joba
Oct 25, 2019 at 16:57