Skip to content
Technology and development

Route planning on open engines: VROOM and Valhalla

What open route-planning engines can do, what licences they are released under and what is needed for them to run on your server.

AuthorArtem ShevchenkoFounder and systems architect
  • 10 min read
  • 1 view
Route planning on open engines: VROOM and Valhalla

Working out the order of deliveries for several vehicles, with customers’ time windows, load capacity and drivers’ breaks, is a task that has its own name in computer science: the vehicle routing problem (VRP). You do not have to solve it from scratch or buy a subscription. Open engines exist that have been doing this for years, and their code and documentation are public.

Two components: the optimizer and the routing engine

Route planning has two steps. First you need to know how long it takes to drive from each point to every other point on real roads: this is done by a routing engine, e.g. OSRM or Valhalla, on OpenStreetMap data. Then an optimizer, e.g. VROOM, uses that to work out the order of stops for each vehicle.

According to its documentation, VROOM supports: many vehicles and several depots, time windows, load capacity in several dimensions (e.g. weight and pallets), drivers’ breaks, pickups and deliveries in a single run, and required skills, e.g. only a vehicle with a tail lift for a given customer. It takes distances from OSRM, Valhalla or openrouteservice with no extra work, and it also accepts your own matrix.

You can also add an order priority and limits on the number of tasks, on travel time and on distance to the data passed to VROOM. Keep in mind that VROOM itself does not know the roads. Any map-dependent restriction, for example a ban on entry, must already be contained in the travel matrix it receives from the routing engine.

Routing engines differ in what they can do beyond calculating a single route. OSRM calculates a matrix of times and distances between many points at once, which is exactly what an optimizer needs. Valhalla also calculates a matrix, and in addition isochrones, that is the area a vehicle can reach within a given time, and it matches a recorded trace of a trip to the roads on the map. OSRM has no isochrones; Valhalla, GraphHopper and openrouteservice have them.

A truck is not a car

This is where a difference that matters to a carrier begins. The open OSRM has profiles for a car, a bicycle and a pedestrian, but no truck profile. Valhalla has one: it takes into account the vehicle’s height, width, length and weight, axle load and hazardous cargo. That is why for a truck fleet we propose the VROOM and Valhalla pair, while for vans and delivery vehicles, where dimensions rarely limit the route, OSRM is often enough. How precisely the map describes the restrictions on your routes is worth checking on your own data before a result is promised.

In Valhalla, the vehicle’s parameters are given in the truck costing model: height, width and length in metres, weight in tonnes, axle load, number of axles and information about hazardous cargo. If you do not provide them, the engine will assume default values, for example a height of 4.11 m and a weight of 21.77 t. That is why it is worth entering the parameters of each vehicle in the fleet separately.

A truck profile is also offered by openrouteservice (the driving-hgv profile: length, width, height, axle load, weight and hazardous cargo) and by the open core of GraphHopper (the truck profile, which avoids roads closed to trucks and compares width, height and weight restrictions on a road with the vehicle’s parameters). The shared principle: truck restrictions will end up in a VROOM plan only if the travel matrix is calculated by an engine with a truck profile. With a matrix from OSRM, these restrictions will not be in the plan.

When the rules are unusual, you reach for a solver: Google OR-Tools or Timefold Solver in the Community edition. Both require more programming work, but they let you describe almost any constraint.

OR-Tools is a library that you embed in your own service. Among other things it supports time windows, load capacity, pickups with deliveries, a separate start and end of the route for each vehicle, breaks, and skipping a stop at a penalty when it cannot be served. It does not calculate roads itself: you have to give it the time matrix, for example from OSRM or from Valhalla. Timefold Solver divides constraints into hard, medium and soft ones and lets you recalculate the plan during the day, leaving in place the tasks that someone has pinned. We do not, however, propose the VRP functions from pgRouting for route planning: the documentation marks them as experimental and warns that they may lead to a server crash.

What such a project looks like step by step

Deploying route planning on open engines can be described in five steps. Each of them can be checked on your data before the system goes into daily use.

  1. Orders and fleet. The starting point is the data the company already has: orders with addresses, customers’ time windows, weight and number of pallets, and vehicles with their load capacity, depot and working hours. For trucks, dimensions and weight are added, and for some cargo the information that it is hazardous.
  2. Addresses on the map. The optimizer works on points, not on addresses. Turning an address into a point, that is geocoding, can be done by Nominatim on OpenStreetMap data. Photon, a second open geocoder, suggests an address as you type and copes with typos. An address that the geocoder does not find goes to an employee for correction, and the corrected point is saved with the customer.
  3. Travel matrix. The routing engine calculates times and distances between all the points of the day. For a truck fleet, this is done by an engine with a truck profile.
  4. Plan rules. Constraints are added to the data: time windows, load capacity, drivers’ breaks, the skills vehicles are required to have and order priorities. A rule that cannot be written in VROOM is a signal to reach for OR-Tools or Timefold.
  5. Dispatcher’s decision. The optimizer proposes the order of stops for each vehicle. The dispatcher sees the plan on the map, changes what the system does not know about, and approves the plan before it goes to the drivers.

What has to run on the server

Three services are needed on the server: an optimizer, a routing engine and a geocoder. VROOM has a ready-made Docker image, vroom-docker, which contains the optimizer itself and vroom-express, an HTTP service that accepts tasks. The routing engine is chosen in it with a single setting: OSRM, Valhalla or openrouteservice. OSRM and Valhalla also have ready-made images, and the map data is an extract from OpenStreetMap, e.g. from the Geofabrik service.

One caveat concerns openrouteservice: its built-in optimization works only in the public API, not on your own instance. On your own server the order of stops is therefore worked out by a separately run VROOM, while openrouteservice calculates the travel.

Licences and costs

VROOM and OSRM are under the BSD licence, Valhalla under MIT, OR-Tools and Timefold Community under Apache 2.0. You do not pay for a licence, and your system’s code stays closed-source. You pay for the deployment and the server. The map requires one thing: the credit “© OpenStreetMap contributors” with a link to the OSM copyright page. Beware of the paid versions: GraphHopper route optimization is a cloud service, and Timefold Enterprise requires a licence.

The BSD, MIT and Apache 2.0 licences allow an engine to be embedded in a closed-source system. You only have to keep the copyright notice and the licence text, and with Apache 2.0 also the NOTICE file, if the project has one. The open core of GraphHopper is also under Apache 2.0, and you can run it yourself. Its cloud services are paid, and the free plan is intended exclusively for non-commercial use.

The GPL licence is a different matter. openrouteservice and the Nominatim geocoder have it (GPL version 3), as does pgRouting (GPL version 2). The obligation to make the source code available arises when a program is conveyed, and the text of GPLv3 states outright that a user merely working with a program over a network, without a copy being handed over, is not conveying it. That is why we propose running such a tool as a separate service on your server, rather than combining its code with the code of your system. Whoever passes a modified version of such a program to someone else must make the source of the changes available under the GPL. None of the tools mentioned here has the AGPL licence. The assessment for a specific project is, however, worth leaving to a lawyer.

OpenStreetMap data is made available under the Open Database License (ODbL). You must state that it comes from OpenStreetMap and is under that licence, with a link to the OSM copyright page. The rules of the OpenStreetMap Foundation allow the credit “© OpenStreetMap” or “© OpenStreetMap contributors”, placed on the map in a corner or right next to it. An application that calculates routes on this data must also name OpenStreetMap. In the system we will build, the credit “© OpenStreetMap contributors” with a link will appear next to every route map and in the client portal.

Where to start

We build systems with AI, integrations and document reading for other industries, but we have not yet built a system for logistics. That is why we propose starting not with promises but with a trial. Data from a few ordinary days is enough: orders with addresses and time windows, and a list of vehicles with their load capacity and depots. On that basis we can work out a plan with an open engine and lay it next to the plan the dispatcher prepared. Such a comparison will show whether the rules are well described and whether the map knows the restrictions on your routes.

We do not give percentages of fuel or kilometre savings in advance: without a measurement on your data there is nothing to calculate them from.

If you want to check how such an engine would arrange routes from your orders, describe your process.

Sources

Tags

Share this article

Back to blog

Cookies

We use essential cookies and one functional cookie, the latter only with your consent. Visit statistics are counted on our server, without cookies. Cookie Policy