9
$\begingroup$

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);
  }
}
$\endgroup$
  • $\begingroup$ can you post a minimal working example? I.e. some code which can be run if you have or-tools installed. $\endgroup$ – JakobS Oct 24 '19 at 20:32
  • $\begingroup$ 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 $\endgroup$ – Joba Oct 24 '19 at 20:43
  • $\begingroup$ @Joba Did you (or anybody) ever get anywhere with this? I am facing a similar issue. $\endgroup$ – Tom Liptrot Dec 2 '19 at 16:00
  • $\begingroup$ 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. $\endgroup$ – Joba Dec 3 '19 at 13:27
6
$\begingroup$

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]
| improve this answer | |
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Joba Oct 25 '19 at 12:53
  • $\begingroup$ 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. $\endgroup$ – Maarten Oct 25 '19 at 13:49
  • $\begingroup$ I have just tried that an updated the question with additional information. It sadly didn't change anything. $\endgroup$ – Joba Oct 25 '19 at 15:12
  • $\begingroup$ 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. $\endgroup$ – Maarten Oct 25 '19 at 15:53
  • $\begingroup$ 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. $\endgroup$ – Joba Oct 25 '19 at 16:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.