This articles gives some hints for solving the Vehicle Routing with GraphHopper and OptaPlanner. It focuses on the GraphHopper’s API to compute distances.
I also recommend the blog post of Geoffrey De Smet about OptaPlanner and GraphHopper, that discusses the necessity of using real distances instead of euclidian distances for solving real vehicle routing problems.
You can use GraphHopper for computing the distances between locations during optimization. OptaPlanner needs thousands of distances to find good solutions. Distance calculation should deliver the travel time or meters between two locations as fast as possible.
You can also use GraphHopper to compute the concrete route between locations, including instructions and way-points.
How to start?
1. Download GraphHopper jar from https://graphhopper.com or from within your project from maven-central:
<dependency>
<groupId>com.graphhopper</groupId>
<artifactId>graphhopper</artifactId>
<version>0.3</version>
</dependency>
2. Download OptaPlanner jar from http://www.optaplanner.org/ or maven-central:
<dependency>
<groupId>org.optaplanner</groupId>
<artifactId>optaplanner-core</artifactId>
<version>6.1.0.Final</version>
</dependency>
3. Download some geo data (of the region of your choice) as osm-file from http://download.geofabrik.de/
Example for Germany: http://download.geofabrik.de/europe/germany-latest.osm.pbf
Prepare a GraphHopper instance
GrapHopper also provides a REST-API. We are not discussing it, because we use the direct Java API to avoid the HTTP overhead for requests.
Tip: you should make these values configurable:
- location of osm-file
- work-directory for GraphHopper
- vehicle (“car”, “foot” or “bike”)
In order to get results as fast as possible, there are a few decisions to be made:
GraphHopper supports “contraction hierarchies”. This feature is enabled by default and we keep it this way because it improves the performance.
But it has also some drawbacks:
1. The first startup of GraphHopper can take quite long, because it loads and precomputes index files.
2. If we need distances for different vehicle types (supported: car, bike, foot), we need to create separate GraphHopper instances with different work-directories for each.
graphHopper = new GraphHopper().setGraphHopperLocation(workDir) // "gh-car"
.setEncodingManager(new EncodingManager(vehicle) // "car"
.setOSMFile(osmFile) // "germany-lastest.osm.pbf"
.forServer();
3. Load the osm data before we can use graphHopper
This will take quite long the first time. Each time, you use a new osm file (e.g. data update), you must delete the work dir and it will precompute the index files again. Startup with consistent work dir will be quite fast.
graphHopper.importOrLoad();
Tip: You can run the statement above in a separate thread, if you need multiple graphHopper instances so that the overall startup can do that in parallel.
Compute distances with GraphHopper
This piece of code computes the route between two geo points:
double[] orig = new double[]{52.1536925d, 11.6395728d};
double[] dest = new double[]{52.1610366d, 11.6322505d};
GHRequest request = new GHRequest(orig[0], orig[1], dest[0], dest[1]);
request.putHint("calcPoints", false);
request.putHint("instructions", false);
request.setWeighting("fastest");
request.setVehicle(vehicle); // "car"
GHResponse route = graphHopper.route(request)
Tip: If we set these hints, GraphHopper will neither return route instructions nor way points, because we only need the distance.
For the score optimize you can use the time:
route.getMillis()
or the distance:
route.getDistance()
We recommend to use the time instead of the distance for feeding the score calculation with OptaPlanner.
What about caching?
OptaPlanner will request the distance between locations multiple times. We should avoid to let GraphHopper compute it each time.
A simple solution could be to use a memory based cache provided by google guava.
<dependency>
<groupId>com.google.guava</groupId>
<artifactId>guava</artifactId>
<version>18.0</version>
</dependency>
The cache contains the origin-location (with latitude, longitude doubles) as key and a sub-cache with the destination-location as key and the distance between both as value.
Cache<Location, Cache<Location, Distance>> cache
You can create the instance with:
cache = CacheBuilder.newBuilder()
.weigher(weigher)
.maximumWeight(maxSize)
.build();
A simple weigher helps the cache to remove some elements, when a maximum size has been reached (in this case the distance might be computed multiple times later if requested):
public int weigh(Location key, Cache<Location, Distance> value) {
return value.size() > Integer.MAX_VALUE ? Integer.MAX_VALUE : (int) value.size();
}
Cache lookup
So before calling graphHopper to compute the distance we first make a lookup in the cache. If it does not find an entry, it computes and caches it:
Distance entry;
Cache<Location, Distance> bucket = cache.getIfPresent(origin);
if (bucket != null) {
entry = bucket.getIfPresent(destination);
} else {
entry = null;
}
if (entry == null) { // compute it and cache it
entry = computeDistance(origin, destination); // call graphHopper
if (entry != null) {
if (bucket == null) {
bucket = CacheBuilder.newBuilder().maximumSize(cacheSize);
bucket.put(destination, entry);
cache.put(origin, bucket);
} else {
bucket.put(destination, entry);
}
}
}
return entry;
In this article we shared some hints about using the GraphHopper API to compute distances that you can use to work with real geo data when solving Vehicle Routing Problems.
We hope that you found the snippets you were searching for.
In OptaPlanner 6.2, I added RoadDistance to the VRP example, to demonstrate real-world road usages.
I took a different approach related to caching: instead of caching, I pre-calculated all distance pairs. Because GraphHopper is local, this works fairly well, although it can take over an hour to calculate them all for 1000 locations (because that 1m pairs).
The bigger problem is that it’s impossible to keep that matrix of over 20k locations in RAM, because 400m pairs of 32bit ints uses almost 2GB RAM. So 40k locations needs 8GB RAM for the matrix alone… That’s why I did experimented with SegmentedRoadDistance. The idea is to add hub locations (typically highway onramps and offramps), to break down the distance matrix. This turned out to be difficult and clunky, but I got it to work – although slower. I ‘ll improve it in further iterations.
Anyway, the real intresting thing for 6.2 for VRP is other stuff:
– general speed improvements
– nearby selection, a huge scalability improvement for VRP – more info in a blog post soon.
Thank you for sharing. It is informative.
I am using optaPlanner to deal with a similar VRP problem. I have a few questions concerning your post.
1: Why not use the open API of Google Map to calculate the route between locations? I know that some geo data of OSM are not very accurate and not updated so frequenty. Also not all the roads where cars are allowed to travelled on are not really fit for develering vehicles, like trucks.
2: In the context of optaPlanner, where do you create the instance “cache” (Cache bucket = cache.getIfPresent(origin); ). You implement it in the core part of the optaPlanenr as a global variable? As a static Variable in the Solution class?
3: Do you create a new GP instance everytime you need routing data if they do not exist in cache (did not defined previously, or expired), or use a global GP instance?
Thanks,
Frank Cheung
1.
As far as I know, you need a Google Key and you need to pay per requests, which could become quite expensive to calculate the distances for many locations. the Google API is free, but not for productive use and only for a limited number of requests.
2.
We have a global or thread-local instance of a DistanceProvider. The cache is implementing the same interface so that it is transparent whether a distance comes from the cache or is computed again.
3.
Sorry, what do you mean with GP (GeoPoint?)?
If a location is not in the cache, it computes it again and puts it into the cache.
Thank you for your reply. I have a few follow-up questions and hope you could help to answer.
2.
We have a global or thread-local instance of a DistanceProvider. The cache is implementing the same interface so that it is transparent whether a distance comes from the cache or is computed again.
I don’t get what you mean here. I think the Distance entry retrieving snippets is implemented in the getDistanceFrom(Location locaiton) method in the class Customer. The cache here is accessible for all customer instances so that the cache could be a variable of an interface which is implemented by the Customer Class, or a static variable on another Class.
Are you implementing the first solution, which creates an interface to host the variable cache?
3.
Sorry, what do you mean with GP (GeoPoint?)?
If a location is not in the cache, it computes it again and puts it into the cache.
Sorry I mistyped GH (GraphHopper) as GP. My question is, in
entry = computeDistance(origin, destination); // call graphHopper
does it create a new GH instance every time this method is called (would that be too cpu-consuming), or u have a global variable similar to the implementation of the cache?
Thank you
Sorry, i did not see your 2nd question.
1)
interface DistanceProvider {
Distance getDistance(Location origin, Location destination);
}
You can implement this interface by your GraphHopperDistanceProvider and by your CachedDistanceProvider, that is a wrapper around a GraphHopperDistanceProvider. You can put the CachedDistanceProvider in a thread-local global variable to retrieve a distance whenever you need it.
2) no it does not create a new instance of graphHopper. The GraphHopperDistanceProvider is created once during app-startup and kept.
class GraphHopperDistanceProvider implements DistanceProvider {
private final GraphHopperAPI graphHopper;
public GraphHopperDistanceProvider(GraphHopperAPI graphHopper) {
this.graphHopper = graphHopper;
}
public Distance getDistance(Location origin, Location destination) {
GHRequest request = new GHRequest(
origin.getLatitude(), origin.getLongitude(), destination.getLatitude(), destination.getLongitude());
// … set options …
GHResponse route = graphHopper.route(request);
// … handle errors …
return new Distance((long) route.getDistance(), seconds);
}
}
So maybe instead of keeping the matrix locally try to fetch those distances on the go from some web service (e.g. Google Maps Directions API). This will significantly slow down solving but it make it possible at least.