Incorrect solution for Vehicle Routing Problem in or-tools

Question

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.

Instead I get this result:

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 com.google.ortools.constraintsolver.FirstSolutionStrategy;
import com.google.ortools.constraintsolver.RoutingDimension;
import com.google.ortools.constraintsolver.RoutingIndexManager;
import com.google.ortools.constraintsolver.RoutingModel;
import com.google.ortools.constraintsolver.RoutingSearchParameters;
import com.google.ortools.constraintsolver.main;
import java.util.logging.Logger;

/** Minimal VRP.*/
public class VrpGlobalSpan {
  static {
    System.loadLibrary("jniortools");
  }

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

    // Add Distance constraint.
    routing.addDimension(transitCallbackIndex, 0, 3000,
        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);
  }
}

Answer 1

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]