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.