Hi,
I’m a non-Java developer who is trying to understand why the builder.buildAlgorithm() part of our app (which runs for a long time) is only ever using a single CPU core. Another long-running line of our code is algorithm.searchSolutions(), and that uses all available cores, so we know it’s a problem with our implementation of builder.buildAlgorithm().
I believe I’ve isolated the problem code, but due to my lack of knowledge, I’m unable to solve the problem. I’ve tried my best to independently solve this issue, but am turning to the graphhopper jsprit community to hopefully get some advice!
We’re using the graphhopper library to provide us with transport cost and transport time values by asking it for routes between jobs. This is implemented as a VehicleRoutingTransportCosts class, and is added to VehicleRoutingProblem.Builder as the routing cost, like this:
VehicleRoutingProblem.Builder vrpBuilder = new VehicleRoutingProblem.Builder();
// ... here we add vehicles and add jobs
vrpBuilder.setRoutingCost(new GraphHopperRoutingCosts(costCalculator));
The GraphHopperRoutingCosts class is a very basic class, essentially a wrapper around custom GraphhopperCachingCostCalculator class (which is assigned as “proxy” in the following class), but here it is in its entirety:
import com.graphhopper.jsprit.core.problem.Location;
import com.graphhopper.jsprit.core.problem.cost.VehicleRoutingTransportCosts;
import com.graphhopper.jsprit.core.problem.driver.Driver;
import com.graphhopper.jsprit.core.problem.vehicle.Vehicle;
public class GraphHopperRoutingCosts implements VehicleRoutingTransportCosts {
private final GraphhopperCachingCostCalculator proxy;
public GraphHopperRoutingCosts(GraphhopperCachingCostCalculator proxy) {
super();
this.proxy = proxy;
}
@Override
public double getBackwardTransportCost(Location from, Location to, double v, Driver driver, Vehicle vehicle) {
return proxy.costs(to.getId(), to.getCoordinate().getY(), to.getCoordinate().getX(),
from.getId(), from.getCoordinate().getY(), from.getCoordinate().getX())
[GraphhopperCachingCostCalculator.COST];
}
@Override
public double getBackwardTransportTime(Location from, Location to, double v, Driver driver, Vehicle vehicle) {
return proxy.costs(
to.getId(), to.getCoordinate().getY(), to.getCoordinate().getX(),
from.getId(), from.getCoordinate().getY(), from.getCoordinate().getX()
)[GraphhopperCachingCostCalculator.TIME];
}
@Override
public double getTransportCost(Location from, Location to, double v, Driver driver, Vehicle vehicle) {
return proxy.costs(
from.getId(), from.getCoordinate().getY(), from.getCoordinate().getX(),
to.getId(), to.getCoordinate().getY(), to.getCoordinate().getX()
)[GraphhopperCachingCostCalculator.COST];
}
@Override
public double getTransportTime(Location from, Location to, double v, Driver driver, Vehicle vehicle) {
return proxy.costs(
from.getId(), from.getCoordinate().getY(), from.getCoordinate().getX(),
to.getId(), to.getCoordinate().getY(), to.getCoordinate().getX()
)[GraphhopperCachingCostCalculator.TIME];
}
}
The GraphhopperCachingCostCalculator (which is the “proxy” variable in the above class) is where we ask for route information from graphhopper, and cache it in HashBasedTable variables.
Here it is in its entirety:
import com.google.common.collect.HashBasedTable;
import com.graphhopper.GHRequest;
import com.graphhopper.GHResponse;
import com.graphhopper.jsprit.core.problem.Location;
import com.vworkapp.routing.graphhopper.GraphhopperApi;
import com.vworkapp.routing.util.Uturns;
import java.lang.management.ManagementFactory;
import java.lang.management.MemoryMXBean;
import java.lang.management.MemoryPoolMXBean;
public class GraphhopperCachingCostCalculator {
private HashBasedTable<String, String, GHResponse> cache = HashBasedTable.create();
private HashBasedTable<String, String, Double[]> costCache = HashBasedTable.create();
public static final int COST = 0;
public static final int TIME = 1;
private static long costsHits = 0;
private static long hits = 0;
private static long costsMisses = 0;
private static long misses = 0;
private static long costsQueries = 1;
private static long queries = 1;
private static boolean logEnabled = true;
private double trafficTimeMultiplier;
public static final double TIME_ADD = 30;
public GraphhopperCachingCostCalculator(double trafficTimeMultiplier) {
this.trafficTimeMultiplier = trafficTimeMultiplier;
initializeValues();
}
private static void setLogging(boolean shouldLog) {
logEnabled = shouldLog;
}
// public synchronized GHResponse route(String fromId, double fromLat, double fromLon, String toId, double toLat, double toLon) {
public GHResponse route(String fromId, double fromLat, double fromLon, String toId, double toLat, double toLon) {
if (logEnabled && (queries & (queries - 1)) == 0) {
System.out.println(String.format("\nGraphhopperCachingProxy: %d queries, %d hits, %d misses", queries, hits, misses));
}
queries += 1;
if (fromId == null || toId == null) {
//We can't cache, so just get the cost directly.
misses += 1;
GHRequest request = new GHRequest(fromLat, fromLon, toLat, toLon);
GHResponse response = GraphhopperApi.get().route(request);
System.out.println("Returning uncacheable response.");
return response;
}
if (cache.contains(fromId, toId)) {
hits += 1;
return cache.get(fromId, toId);
} else {
misses += 1;
GHRequest request = new GHRequest(fromLat, fromLon, toLat, toLon);
GHResponse response = GraphhopperApi.get().route(request);
cache.put(fromId, toId, response);
costCache.put(fromId, toId, getCostAndTime(response));
return cache.get(fromId, toId);
}
}
public static String mb (long s) {
return String.format("%d (%.2f M)", s, (double)s / (1024 * 1024));
}
public static void printStats() {
System.out.println(String.format("Hits: %d, Misses: %d, Queries: %d", hits, misses, queries - 1));
System.out.println(String.format("Miss %%: %f", ((misses * 1.0f) / hits) * 100));
System.out.println("Runtime max: " + GraphhopperCachingCostCalculator.mb(Runtime.getRuntime().maxMemory()));
MemoryMXBean m = ManagementFactory.getMemoryMXBean();
System.out.println("Non-heap: " + GraphhopperCachingCostCalculator.mb(m.getNonHeapMemoryUsage().getMax()));
System.out.println("Heap: " + GraphhopperCachingCostCalculator.mb(m.getHeapMemoryUsage().getMax()));
for (MemoryPoolMXBean mp : ManagementFactory.getMemoryPoolMXBeans()) {
System.out.println("Pool: " + mp.getName() +
" (type " + mp.getType() + ")" +
" = " + GraphhopperCachingCostCalculator.mb(mp.getUsage().getMax()));
}
}
public GHResponse route(Location a, Location b) {
return route(a.getId(), a.getCoordinate().getY(), a.getCoordinate().getX(), b.getId(), b.getCoordinate().getY(), b.getCoordinate().getX());
}
public GHResponse route(String a, String b) {
double a_x = Double.valueOf(a.split(",")[0]);
double a_y = Double.valueOf(a.split(",")[1]);
double b_x = Double.valueOf(b.split(",")[0]);
double b_y = Double.valueOf(b.split(",")[1]);
return route(a, a_x, a_y, b, b_x, b_y);
}
public Double[] getCostAndTime(GHResponse response) {
return new Double[]{getCost(response), getTime(response)};
}
public double getCost(GHResponse response) {
if (response.hasErrors()) {
return Double.MAX_VALUE;
}
double result = (response.getBest().getTime() / 1000. / 60.);
if (result > 0.00001d) { result += TIME_ADD; }
return result;
}
public double getTime(GHResponse response) {
if (response.hasErrors()) {
return Double.MAX_VALUE;
}
double result = (response.getBest().getTime() * trafficTimeMultiplier);
//Special case: if time is zero, we don't need to get into the vehicle, so don't add TIME_ADD.
if (result > 0.00001d) { result += TIME_ADD; }
return result;
}
public void reset() {
clearCaches();
initializeValues();
}
public void clearCaches() {
System.out.println(String.format("\n> Clearing cost calculator caches of %d cache objects and %d costCache objects", cache.size(), costCache.size()));
cache.clear();
costCache.clear();
}
public void initializeValues() {
costsHits = 0;
hits = 0;
costsMisses = 0;
misses = 0;
costsQueries = 1;
queries = 1;
}
// public synchronized Double[] costs(String fromId, double fromLat, double fromLon, String toId, double toLat, double toLon) {
public Double[] costs(String fromId, double fromLat, double fromLon, String toId, double toLat, double toLon) {
costsQueries += 1;
if (logEnabled && (costsQueries & (costsQueries - 1)) == 0) {
System.out.println(String.format("\nGraphhopperCachingProxy: %d costsQueries, %d hits, %d misses", costsQueries, costsHits, costsMisses));
System.out.println(String.format("Heap status [heapSize,heapMaxSize,heapFreeSize]: %d | %d | %d", Runtime.getRuntime().totalMemory(), Runtime.getRuntime().maxMemory(), Runtime.getRuntime().freeMemory()));
}
if (fromId == null || toId == null) {
//We can't cache, so just get the cost directly.
costsMisses += 1;
GHResponse response = route(fromId, fromLat, fromLon, toId, toLat, toLon);
System.out.println("Returning uncacheable response.");
return getCostAndTime(response);
}
if (costCache.contains(fromId, toId)) {
costsHits += 1;
return costCache.get(fromId, toId);
} else {
costsMisses += 1;
route(fromId, fromLat, fromLon, toId, toLat, toLon);
return costCache.get(fromId, toId);
}
}
}
As you can see, I’ve commented out what were “synchronized” method declarations, just to see if that made the code run multi-threaded, but it hasn’t.
I believe that it could be our implementation of GraphhopperCachingCostCalculator that’s to blame for the single-threadedness (which is an attempt to query graphhopper for routing information, and cache the responses to speed up iterations).
My questions are:
- Is anyone able to help me identify how to use graphhopper route responses as the VehicleRoutingProblem.Builder instance’s routing cost, in a way that caches, and runs multi threaded?
- Has anyone seen any code that queries graphhopper for route cost and time, but is done cleaner than ours?
Any help would be very appreciated!
Luke