Vehicle Routing Problems
Vehicle routing problems (VRP) are essential in logistics. As the name suggests, vehicle routing problems come to exist when we have N vehicle to visit M nodes on any map.
A figure illustrating the vehicle routing problem
We could say VRPs are a subset of Traveling Salesman Problem (TSP). In general, it looks like that:
CVRP, VRPTW ⊆ SVRP, DVRP ⊆ VRP ⊆ TSP ⊆ Graph Theory
CVRP: If you have vehicles restricted by any capacity (e.g. max loading limit) constraint, then we call it Capacitated Vehicle Routing Problem (CVRP)
VRPTW: If you have vehicles restricted with working times, then we call it Vehicle Routing Problem with Time Windows (VRPTW)
SVRP: If the visiting points (nodes) are given, then we call it Static Vehicle Routing Problem
DVRP: If the visiting points (nodes) come to exist while trying to solve or moving on the map, then we call it Dynamic Vehicle Routing Problem
Confused ? 🤔
Here is a map showing the relationship between common VRP subproblems, from Wikipedia.
Graph Theory and VRP Solvers
The leading actor is Graph Theory. It all started with the "The Seven Bridges of Königsberg" question being asked to Euler. Today we ask more sophisticated questions such as "How are all packages delivered to their addresses in the most efficient way?".
There are many ways to solve a VRP. Heuristics, Constructive Methods, 2-Phase Algorithms, Metaheuristics and more are general methods for VRPs. See here for more information.
Today we have enough compute power to run iterative solutions or optimizers that take long times while solving VRPs with computers.
Real World Map, Routes and Solving on
Open Street Map
So far we have described the problem and introduced some solutions but what about the roads & routes on the real world map? One can think about Google Maps, Yandex Maps, HERE Maps etc.. They are all good but also commercial. Thanks to OpenStreetMap (OSM) and the community, we have a very big and useful real world map updated every week.
Open Source Routing Machine
OpenStreetMap just provides the real world map, not routes and therefore we need something else to give us the routes, distances, durations etc.. Oh, what's that Open Source Routing Machine (OSRM)? You guess right, we love free (as in freedom) software! OSRM uses OpenStreetMap as (map) backend and has the following features:
- Nearest - Snaps coordinates to the street network and returns the nearest matches
- Route - Finds the fastest route between coordinates
- Table - Computes the duration or distances of the fastest route between all pairs of supplied coordinates
- Match - Snaps noisy GPS traces to the road network in the most plausible way
- Trip - Solves the Traveling Salesman Problem using a greedy heuristic
- Tile - Generates Mapbox Vector Tiles with internal routing metadata
Now we can fetch the routes between all the nodes and then run a VRP solver algorithm to have optimized (the fastest or the shortest) sequence of routes of nodes.
But wait! Send me more open source, please! 😂
Vehicle Routing Open-source Optimization Machine
Vehicle Routing Open-source Optimization Machine (VROOM) is a VRP solver. It uses OSRM or OpenRouteService (OSR) as backend to get routes and returns solutions for CVRP, VRPTW, CVRPTW problems. It also has a nice UI (frontend) to show vehicles, nodes and routes on the map.
You should note that VROOM's objective is optimizing the overall duration, not the overall distance. Hence you might need to find another open source solution or write your own in order to calculate the shortest path.
Talk is Cheap Show Me the Code!
Preparing Dependencies in the Traditional Way
That means, without docker. I suggest you jump to the non-traditional.
Running OSRM With an OSM Map
To build OSRM for your OS and architecture follow this guide .
Then, you need to download an OSM map and process it for OSRM. Next, you can run the OSRM backend. Follow this guide to achieve them all.
Running VROOM Backend and Exposing the API
Clone and build VROOM according to this guide. Make sure you have vroom binary in your path (environment variable).
Thus far, we had a routing machine (OSRM) with a map (OSM), and a VRP solver (VROOM) which uses them. We can call VROOM with proper parameters through CLI and have the calculated result. However, it is easier to interact with VROOM via the Node.js HTTP API.
Okay then, let's install and run VROOM Express.js API. It is very easy. Just clone the repository and follow the guide here. One caveat: Don't forget to configure via config.js, before running. You might want to change the MAX_JOBS, MAX_VEHICLES, PORT or routingServers values.
Preparing Dependencies via Docker
First, download an OSM map and process it with dockerized OSRM through this simple guide. But don't run the OSRM as in the last command. Because from now on, we'll use docker-compose with the following compose file:
Adjust the command and volume parameters to your own. If you wish to edit config files of VROOM backend, clone this repository and build your own image. You can do the same for VROOM frontend by cloning this repository. These repositories are the images I prepared for VROOM backend and frontend. I recommend you to review them.
Fire it up!
docker-compose up -d
One caveat: If you use Docker for Mac, you may need to increase the default Docker resources. I have reserved the following resources for Docker:
- CPUs: 4
- Memory: 6 GiB
- Swap: 2.0 GiB
Links to docker files:
- VROOM backend docker repository: github.com/iedmrc/vroom-docker
- VROOM frontend docker repository: github.com/iedmrc/vroom-frontend-docker
Solving VRP via Direct API Request
Now you can have the VRP solved by making a request to VROOM Express API with a JSON payload attached according to this API guide.
An example request:
curl 'http://localhost:3000/' -H 'Content-type: application/json' --data-binary \
'{ "jobs": [ { "id": 1613, "service": 1200, "amount": [ 1 ], "location": [ 29.02988, 40.99423 ] }, { "id": 1665, "service": 1200, "amount": [ 1 ], "location": [ 29.216, 41.008520000000004 ] }, { "id": 21234, "service": 900, "amount": [ 1 ], "location": [ 29.272640000000003, 40.94765 ] }, { "id": 23457, "service": 600, "amount": [ 1 ], "location": [ 29.119659999999996, 40.97359 ] }, { "id": 24145, "service": 900, "amount": [ 1 ], "location": [ 29.16579, 40.925540000000005 ] }, { "id": 33007, "service": 900, "amount": [ 1 ], "location": [ 29.123801, 40.978068 ] }, { "id": 38081, "service": 600, "amount": [ 1 ], "location": [ 29.113429999999997, 40.980259999999994 ] }, { "id": 39163, "service": 900, "amount": [ 1 ], "location": [ 29.25528, 40.87539 ] } ], "vehicles": [ { "id": 7, "start": [ 29.208498, 40.890795 ], "end": [ 29.208498, 40.890795 ], "capacity": [ 25 ], "time_window": [ 30600, 61200 ], "startDescription": "Start", "endDescription": "End" } ], "options": { "g": true }}' --compressed
The response:
{
"code": 0,
"summary": {
"cost": 4387,
"unassigned": 0,
"amount": [8],
"service": 7200,
"duration": 4387,
"waiting_time": 0,
"distance": 72452,
"computing_times": {"loading": 28,"solving": 4,"routing": 10}
},
"unassigned": [],
"routes": [{
"vehicle": 7,
"cost": 4387,
"amount": [8],
"service": 7200,
"duration": 4387,
"waiting_time": 0,
"distance": 72452,
"steps": [{
"type": "start",
"location": [29.208498,40.890795],
"arrival": 30600,
"duration": 0,
"distance": 0
},{
"type": "job",
"location": [29.16579,40.925540000000005],
"job": 24145,
"service": 900,
"waiting_time": 0,
"arrival": 31064,
"duration": 464,
"distance": 8110
},{
"type": "job",
"location": [29.02988,40.99423],
"job": 1613,
"service": 1200,
"waiting_time": 0,
"arrival": 32854,
"duration": 1354,
"distance": 25277
},{
"type": "job",
"location": [29.113429999999997,40.980259999999994],
"job": 38081,
"service": 600,
"waiting_time": 0,
"arrival": 34586,
"duration": 1886,
"distance": 34414
},{
"type": "job",
"location": [29.123801,40.978068],
"job": 33007,
"service": 900,
"waiting_time": 0,
"arrival": 35260,
"duration": 1960,
"distance": 35539
},{
"type": "job",
"location": [29.119659999999996,40.97359],
"job": 23457,
"service": 600,
"waiting_time": 0,
"arrival": 36215,
"duration": 2015,
"distance": 36533
},{
"type": "job",
"location": [29.216,41.00852],
"job": 1665,
"service": 1200,
"waiting_time": 0,
"arrival": 37454,
"duration": 2654,
"distance": 47712
},{
"type": "job",
"location": [29.272640000000003,40.94765],
"job": 21234,
"service": 900,
"waiting_time": 0,
"arrival": 39281,
"duration": 3281,
"distance": 57059
},{
"type": "job",
"location": [29.25528,40.87539],
"job": 39163,
"service": 900,
"waiting_time": 0,
"arrival": 41007,
"duration": 4107,
"distance": 67891
},{
"type": "end",
"location": [29.208498,40.890795],
"arrival": 42187,
"duration": 4387,
"distance": 72452
}
]}
]}
Solving VRP via Frontend
If you have run the VROOM frontend either via docker-compose or via compiling manually, by uploading the JSON you prepared, you can make VROOM solve the VRP.
A screenshot of VROOM frontend
Final Overview
- Download an OSM map here (or wherever you want).
- Build OSRM binaries and process .osm file with docker or as described here.
- Build VROOM binary and make sure it is in the path.
- Run OSRM HTTP Server to listen port 5000 (or whichever you want).
- Configure VROOM Express.js API to use the VROOM binary at the path, and to connect to OSRM HTTP Server via the port it listens.
- Run the VROOM Express.js API to listen port 3000 (or whichever you want).
- Make a JSON file as described here.
- Make HTTP request to VROOM Express.js with the JSON file you prepared.
- [Optional] Configure VROOM frontend to connect to VROOM Express.js API and run it to listen port 9966 (or whichever you want).
In conclusion
Vehicle routing problems are a very valuable and still active area of research, especially in logistics. The community has good solutions for it. Here we combined them and solved the problem.
If you have any questions, feel free to ask! And please spread the word! 🙏🏼