NEO4J SHORTEST PATH OPTIMIZATION
06 MARCH 2018
Replaced Dijkstra’s search for vessel route tracking in Neo4J.
Tracking 13,000 marine vessel route points. Needed shortest paths between ports for arrival prediction. Neo4j’s Dijkstra’s algorithm slows after 4,000 route points.
Implemented A* search using haversine function as heuristic:
private double computeHeuristic(
final double lat1, final double lon1,
final double lat2, final double lon2) {
final int earthRadius = 6371;
final double kmToNM = 0.539957;
final double latDistance = Math.toRadians(lat2 - lat1);
final double lonDistance = Math.toRadians(lon2 - lon1);
final double a = Math.sin(latDistance / 2)
* Math.sin(latDistance / 2)
+ Math.cos(Math.toRadians(lat1))
* Math.cos(Math.toRadians(lat2))
* Math.sin(lonDistance / 2)
* Math.sin(lonDistance / 2);
final double c = 2 * Math.atan2(Math.sqrt(a), Math.sqrt(1 - a));
return earthRadius * c * kmToNM;
}
Core search loop updates costs when better path found:
private void updateCosts(
final int source, final int target,
final double newCost, final double heuristic) {
final double oldCost = gCosts.getOrDefault(target, Double.MAX_VALUE);
if (newCost < oldCost) {
gCosts.put(target, newCost);
fCosts.put(target, newCost + heuristic);
path.put(target, source);
}
}
Outcome: 300x speedup. Scaled to 13,000 route points. Upstreamed changes. Neo4J v3.4.0. Full source