Wherecamp Navigation Conference 2015 - GraphHopper Route Optimization

Stefan Schröder from GraphHopper

1. GraphHopper Route Optimization
Stefan Schröder

2. ●Fast and Flexible Directions API
●Lightweight API to solve heavy routing problems
What is GraphHopper?

3. ●04/2012 – Peter Karich published OS GraphHopper routing
based on OSM
●06/2013 – Stefan Schröder published jsprit, a toolkit to solve
vehicle routing problems
●04/2015 – we joined forces to develop the GraphHopper
Directions API
Brief history

4. Directions API

5. Route Optimization API
●Difference between Routing and Route
Optimization API
Least cost path
from A to B
Least cost paths with
via points
A
B
A
B
C
D
E
A
B
C
D
E
Least cost route by
ordering of via points

6. Route Optimization API
1. Geocode
2. Snap Geocodes to
networks
3. Calculate n x n travel
times/distances
4. Optimize
Friedrichstraße 52
lon,lat
1
n
1 n

7. Vehicle Routing Problem
●VRP: Given m vehicles with capacity restrictions and n
customers, find vehicle routes that minimize
transportation costs.
●TSP: Round trip visiting every location once
●Last mile deliveries, health care, garbage collection,
technicians, ...
●Challenges: Search space, Example 50 L-TSP

8. Search algorithms
●Exact methods – Branch & Bound
●Meta-Heuristics – Tabu Search, Simulated
Annealing, etc.
●Ruin and Recreate – Large Neighborhood
Search Threshold Acceptance and Simulated
Annealing

9. Route Optimization Editor
●Switch to Route Editor and solve problems live
●TSP
●TSP-Relation
●VRP
●VRP-Relation
●VRP-Bike
●VRP-Min-Max

10. Problem Berlin

11. Sufficient capacity - TSP

12. Direct sequence of 37 & 38

13. VRP

14. VRP with relation

15. VRP – min-max compl. time

16. VRP – min-max by foot

17. Shortest route through
Dublin avoiding pubs?

18. Dublin – “avoid pubs”

19. Dublin – “avoid pubs”

20. Publicity?
●handful retweets
●<100 blog readers
●pointer to this: “there's someone trying to drink in
every pub in Dublin, might be another interesting
demo for you.”

21. Shortest route through
Dublin visiting all pups?

22. Dublin – “visit all pubs”

23. Publicity?
●many retweets from all over the world
●>3000 readers
●on reddit
●a day on the front page of hacker news with 84
points

24. Dublin – “visit all pubs”

25. GraphHopper.com
[email protected]