Vehicle Routing Problems And How To Solve Them
Tags: vrp, tsp, osrm, cpp
Published: 2019-08-14 14:45:50

# Vehicle Routing Problems
---
 [Vehicle routing problems (VRP)](https://en.wikipedia.org/wiki/Vehicle_routing_problem) 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 - Wikipedia](https://upload.wikimedia.org/wikipedia/commons/2/2b/Figure_illustrating_the_vehicle_routing_problem.png "A figure illustrating the vehicle routing problem - Wikipedia") 
*A figure illustrating the vehicle routing problem*

We could say VRPs are a subset of [Traveling Salesman Problem (TSP)](https://en.wikipedia.org/wiki/Travelling_salesman_problem). 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 ? 🤔

![A map showing the relationship between common VRP subproblems. - Wikipedia](https://upload.wikimedia.org/wikipedia/commons/2/29/Map_of_vrp_subproblems.jpg "A map showing the relationship between common VRP subproblems. - Wikipedia")

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](https://en.wikipedia.org/wiki/Seven_Bridges_of_Königsberg) 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](http://neo.lcc.uma.es/vrp/solution-methods/)  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)***](https://wiki.openstreetmap.org/wiki/Main_Page) 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)***](http://map.project-osrm.org/)? 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)***](http://vroom-project.org) is a VRP solver. It uses OSRM or  [***OpenRouteService (OSR)***](https://openrouteservice.org/) 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](https://github.com/Project-OSRM/osrm-backend/wiki/Building-OSRM) .

Then, you need to download an OSM map and process it for OSRM. Next, you can run the OSRM backend. Follow [this guide](https://github.com/Project-OSRM/osrm-backend/wiki/Running-OSRM) to achieve them all.

### Running VROOM Backend and Exposing the API

Clone and build VROOM according to [this guide](https://github.com/VROOM-Project/vroom/wiki/Building). 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](https://github.com/VROOM-Project/vroom-express).

Okay then, let's install and run *VROOM Express.js API*. It is very easy. Just clone the repository and follow the guide [here](https://github.com/VROOM-Project/vroom-express). 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](https://github.com/Project-OSRM/osrm-backend#using-docker). 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:


%[https://gist.github.com/iedmrc/51d02fefa9e3ee91a5608c02c452c965]

Adjust the `command` and `volume` parameters to your own. If you wish to edit config files of VROOM backend, clone [this repository](https://github.com/iedmrc/vroom-docker) and build your own image. You can do the same for VROOM frontend by cloning [this repository](https://github.com/iedmrc/vroom-frontend-docker). 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: https://github.com/iedmrc/vroom-docker
- VROOM frontend docker repository: https://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](https://github.com/VROOM-Project/vroom/blob/master/docs/API.md).

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](https://cdn.hashnode.com/res/hashnode/image/upload/v1559256825172/I4vq18w7D.png "A screenshot of VROOM frontend")
*A screenshot of VROOM frontend*



# Final Overview
---
1. Download an OSM map [here](http://download.geofabrik.de) (or wherever you want).
2. Build OSRM binaries and process .osm file with [docker](https://github.com/Project-OSRM/osrm-backend#using-docker) or as described  [here](https://github.com/Project-OSRM/osrm-backend/wiki/Running-OSRM).
3. Build VROOM binary and make sure it is in the path.
4. Run OSRM HTTP Server to listen port 5000 (or whichever you want).
5. 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. 
6. Run the VROOM Express.js API to listen port 3000 (or whichever you want).
7. Make a JSON file as described [here](https://github.com/VROOM-Project/vroom/blob/master/docs/API.md).
8. Make HTTP request to VROOM Express.js with the JSON file you prepared.
9. [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! 🙏🏼