Assign geo locations to roads and its impacts on route optimization

These are the three basic steps to solve a real world vehicle routing problem with GraphHopper’s Optimization API:

1) Assign geo locations to (road) network
2) Calculate travel times and distances
3) Solve vehicle routing problem

Each step impacts the solution of the vehicle routing problem. This article illustrates how 1) – the assignment of geo locations – affects solutions negatively, and how to mitigate these negative effects.

I would like to illustrate the problem with two simple examples. Let me start with the following traveling salesman problem. There is a single vehicle that needs to conduct 4 stops. This is our solution: The driver takes 41min and needs to travel 30km.

When looking at the map above the question arises why the driver needs to travel all the way over the motorway to get from stop 3 to 4 to 5. There is a simple reason for it. Stop 4 is assigned to the motorway, even though stop 4 should actually be assigned to the Woltersdorfer Street as illustrated below.

To better control the assignment at the level of the vehicle routing problem, we just introduced a new field to the address object called "street_hint". It can be used like this:

{
"id": "4",
"name": "serve sportpark",
"address": {
"location_id": "13.795629_52.460965",
"lon": 13.795629,
"lat": 52.460965,
"street_hint":"Woltersdorfer Straße"
}
}

This handy modification gives the snapping algorithm a hint to prefer a road link on the Woltersdorfer street rather than the motorway. This improves the solution of the above problem a lot. Now the driver only takes 25min and needs to travel 8km.

Note that if there is no road link belonging to Woltersdorfer street, the algorithm ignores the hint and proceeds as though as there were no hint, i.e. it assigns the closest road link. We also accept notation variations here.

Let me show you another typical example from an inner city area in Berlin. It is again a simple traveling salesman problem with this solution:

Why on earth does the driver need to travel this tail between stop 3 and 4? The reason is that there is tunnel going from the south red line to the north one, and the snapping algorithm assigns stop 3 to a tunnel link.

However, if this stop should not be located in the tunnel, but on the Ben-Gurion street above, we need to modify our address with “street_hint” as follows:

{
"id": "3",
"name": "deliver person on Ben-Gurion street",
"address": {
"location_id": "13.372159_52.509617",
"lon": 13.372159,
"lat": 52.509617,
"street_hint": "Ben-Gurion"
}
}

which yields the following solution:

Happy Routing!