Solving vehicle routing problem in Java

28 Nov 2022.4 minutes read

Solving vehicle routing problem in Java webp image

A vehicle routing problem (VRP) is an optimization problem in which we want to find the optimal (not necessarily shortest) set of routes for a given set of n stops and m vehicles. It’s an NP-hard problem, so we have to utilize metaheuristic algorithms to solve it in real time.

We will try to create a simple web service to solve such a problem without dependency on any external services (such as Google Maps). The building blocks of our application are going to be:

Micronaut framework as an HTTP server with reactive streams support
OpenStreetMap dataset in form of a static file (PBF)
GraphHopper core module - a library that will extract travel time and distance data from the dataset
GraphHopper JSprit - a library that will do the actual optimization

Modeling request

As stated above a VRP consists of a set of vehicles and a set of stops to visit. For the latter we use shipment instead, which in fact is information about two stops: pickup and delivery.

Since the problem will be represented as a JSON payload sent via a POST request, we will utilize Java 17 records to model our data.

public record RoutingProblem(
       List<Vehicle> vehicles,
       List<Shipment> shipments
) { }

The minimum piece of information to describe a vehicle are fields:

start and end location (as geographical coordinates)
driver’s work time window (interval during which an order can be delivered)

public record Vehicle(
       String id,
       Coordinates startLocation,
       Coordinates endLocation,
       TimeWindow timeWindow
) { }

Shipment needs the following data:

pickup and delivery locations
pickup and delivery time windows (JSprit supports multiple time windows but we use single ones)

public record Shipment(
       String id,
       Coordinates pickupLocation,
       Coordinates deliveryLocation,
       TimeWindow pickupTimeWindow,
       TimeWindow deliveryTimeWindow
) { }

Setting up distance matrix

Beside the problem definition, a VRP optimization algorithm needs a distance matrix.
Distance matrix is a 2D array holding information about travel time and distance between any two points in our VRP.

For the purpose of this application, we’ll utilize the data from the OpenStreetMap repository and extract the data we need using GraphHopper.

If you would like to search for routes on the entire planet, you need to download the entire Earth’s PBF file, which at the moment of writing this article has a size of 66 GB. I’ll be running my demo using coordinates in my city, so I’ll only download the PBF file corresponding to my region.

Due to performance reasons, this data should not be lazily loaded but stored entirely in the memory instead.

Having all this set up we can map our input to JSprit objects and run the optimizer that will search for routes.

How does it work?

As mentioned previously VRP is an NP-hard problem. JSprit implements a heuristic algorithm to solve this problem.

JSprit operates on a cost function, similar to how genetic algorithms work. The cost usually includes transportation costs (due to work time and traveled distance), activity costs (for example time consumed by delivering a package to a door), and penalties (due to soft constraints).

The first step is to find an initial solution. At a high level, the algorithm starts with an empty solution and inserts shipments one by one starting from the cheapest ones and finishing with the most expensive ones. If it’s not possible to insert a shipment due to broken hard constraints (for example exceeding a time window), it’s left unassigned. Such a solution is usually far from optimal, but most importantly it’s valid, which makes it a good starting point for further computation. A valid solution is one, that fulfills all the hard constraints defined in the algorithm. For example, delivery cannot exceed its delivery time window - that would violate one of the core JSprit hard constraints.

Next JSprit runs multiple iterations (the max number can be specified with a parameter). A single iteration has two phases:

Ruin - randomly removes some shipments from the previous solution and adds them to the unassigned jobs collection.
Recreate - tries to insert unassigned jobs to the solution using the same algorithm that was used to build the initial solution.

Eventually, the algorithm stabilizes (either there’s no better solution or the probability of finding the better one is very small). Small problems (like 10-20 shipments) are usually solved after a few iterations, which takes less than a second. Big problems (hundreds of shipments) can take thousands of iterations and hours of execution time on a multicore CPU to stabilize. Although we rarely need the perfect solution.

Modeling response

JSprit output consists of vehicle routes and unassigned jobs.

public record Routes(List<Route> routes, List<String> unassignedShipmentsIds) { }

Each route contains a list of tour activities. In our example, these would be pickup and delivery job activities along with the start and the end of each tour.

public record Route(
       String vehicleId,
       List<Job> jobs,
       String mapUrl
) { }

Finally, we can look up the generated Google Maps URL and visualize our tour (up to 10 stops are supported).

Try it!

Full implementation is available on our GitHub. Take a look at IntegrationTest where you can find an example routing problem and the API request solving the problem.

Contents