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