Route Planning with ArcadeDB

Exact shortest paths on road, logistics and utility networks: Dijkstra and A* for any graph, Customizable Contraction Hierarchies for answers in microseconds at any distance, following live traffic in a millisecond. In the database, not next to it.

Published

Dijkstra vs A* vs Contraction Hierarchies

The classic answers to "what is the fastest way from A to B?", Dijkstra and A*, are exact and need no preparation, but the farther apart the two points, the more of the network they read. The animation runs them and a Customizable Contraction Hierarchy on the real road network of Florida, 1.07 million junctions and 2.7 million road segments, from Tallahassee to Coral Gables by travel time: 8 hours 18 minutes, down I-75 and the Florida Turnpike. Each colored square is a part of the state the search has to read before it knows the answer, and all three panels play at the same speed. All three return the same route, to the second.

Animation: on the Florida road network, Dijkstra settles 1,029,617 junctions to find the fastest route from Tallahassee to Coral Gables, A* settles 840,138, CCH 346. All three return the same route, 8 hours 18 minutes.

Dijkstra: 1,029,617 junctions

Settles junctions in order of travel time from the start. Its search is a growing circle: by the time it reaches Coral Gables it has settled almost all of Florida, because Pensacola, Jacksonville and Tampa are closer to Tallahassee than Coral Gables is. No preparation, works on any graph with non-negative weights.

A*: 840,138 junctions

Adds an estimate of the time left from the straight line to Coral Gables and leans the circle south. To stay exact the estimate may never exceed a real road, and a few of Florida's 2.7 million segments are faster than the straight line suggests, so the guidance is weak and the search still covers most of the state. Needs coordinates on the vertices.

CCH: 346 junctions

Climbs a precomputed hierarchy from both ends until the two climbs meet: 166 junctions above Tallahassee, 163 above Coral Gables. The work barely depends on the distance, so the gap is three orders of magnitude: 0.04 ms instead of about 100. Exact, not a heuristic.

How Customizable Contraction Hierarchies Work

The technique, from the research of Dibbelt, Strasser and Wagner, moves the work from query time to preparation time, and splits the preparation into a part that depends only on which roads exist and a part that depends on what they cost. That split is what lets the hierarchy follow traffic.

Animation: on the left, the Florida road network split into pieces by nested dissection, with the 17 junctions of the first cut, then 28 and 43 more; on the right, a query from Tallahassee to Coral Gables climbs the hierarchy from both ends, 166 and 163 junctions, and the climbs meet near Vero Beach before the shortcuts unpack into the route.

Order, Contract, Customize, Query

  • Order (once): find a small set of junctions that cuts the network in two (in Florida, 17 junctions cut the state in two, 28 more cut it in four), then recurse into each half. Road networks are full of small separators: bridges, passes, the few junctions every long route crosses.
  • Contract (once): remove the junctions bottom-up, adding a shortcut wherever a removal would break a route. No weights are needed yet.
  • Customize (on every weight change): price every road and shortcut from the weights. After a change, only the arcs above the changed road are re-priced.
  • Query (on every request): walk up from both endpoints, meet, unpack the shortcuts into real roads. No priority queue, no frontier, a few kilobytes of scratch.

ArcadeDB keeps the hierarchy on a Graph Analytical View, the in-memory columnar copy of the graph its analytics run on, and keeps it in step with every commit.

One Statement to Enable It

-- one hierarchy per cost: distance and time
CREATE GRAPH ANALYTICAL VIEW Florida
  EDGE TYPES (ROAD)
  UPDATE MODE SYNCHRONOUS
  CCH (km, minutes)

Built in the background, about 7 seconds for the 2.7 million roads of Florida. Queries never wait for it.

The Same Route, in Cypher and SQL

// Cypher: route and total travel time
MATCH (a:Junction {name: 'Tallahassee'}),
      (b:Junction {name: 'Coral Gables'})
CALL algo.cch.shortestPath(a, b,
     'ROAD', 'minutes', 'OUT')
YIELD path, weight
RETURN weight AS minutes, size(path.nodes) AS junctions

-- SQL: the junctions of the route, in order
SELECT lat, lon FROM (
  SELECT expand(cchShortestPath($from, $to, 'minutes',
    { direction: 'OUT', edgeTypeNames: ['ROAD'] }))
  LET $from = (SELECT FROM Junction WHERE name = 'Tallahassee'),
      $to   = (SELECT FROM Junction WHERE name = 'Coral Gables')
)

dijkstra() and astar() take the same arguments, so switching algorithm is one word.

Always Exact, Never Stale

cchShortestPath() and algo.cch.shortestPath always return the exact shortest path and pick the fastest way to compute it. The hierarchy answers when it was prepared for exactly the data the view is serving. Otherwise the same call answers with bidirectional Dijkstra: while the hierarchy is being built or is catching up with a commit, for a different weight, or for a transaction that holds uncommitted changes, which it sees as part of the route.

Only the speed changes, never the answer. That is the difference between a routing feature of the database and a routing cache next to it: there is no window in which a query returns a route over a road that was closed a second ago.

Every hierarchy reports its status, size and memory, the queries it answered and the ones it handed to Dijkstra, and how long the last update took from commit to ready, through SELECT FROM schema:graphAnalyticalViews. In Cypher, PROFILE says when a query was answered by the hierarchy.

Live Traffic: One UPDATE, a New Route a Millisecond Later

A weight is an ordinary edge property. Traffic feeds, closures and maintenance windows are plain UPDATE or Cypher SET statements, in a transaction, next to the rest of your data. The hierarchy re-prices only the arcs above the changed road and keeps everything else.

Animation: the fastest route from Tallahassee to Coral Gables runs down I-75 and the Florida Turnpike in 8 hours 18 minutes; after a Cypher SET adds a four-hour jam on the Turnpike south of Orlando, the hierarchy catches up in 0.9 ms and the next query returns the route along I-10 and I-95 down the Atlantic coast in 8 hours 20 minutes

Weights Change Every Second, the Hierarchy Keeps Up

Measured on the Florida road network, from the commit until the hierarchy answers for the new data (median of three runs):

Change Commit + catch-up
1 road weight0.61 + 0.19 ms
10 road weights5.0 + 3.3 ms
100 road weights34 + 7.2 ms
Close a road0.81 + 0.14 ms
A new road between junctions not yet joined0.46 s

A road is closed by giving it a negative weight, which no path finder walks, and reopened by restoring it. A new road keeps the existing order and only re-contracts.

Traffic Is Just a Property Update

// four hours of queue on the Turnpike
MATCH (:Junction {id: 702459})
      -[r:ROAD]->(:Junction {id: 702911})
SET r.minutes = 240

-- the same road closed, in SQL:
-- a negative weight is never walked
UPDATE ROAD SET minutes = -1
WHERE @rid = :road

Tallahassee to Coral Gables leaves I-75 and the Turnpike (8 h 18 min) for I-10 and I-95 down the Atlantic coast (8 h 20 min). The hierarchy caught up in 0.9 ms.

Tallahassee to Coral Gables

Minimize Route Cost
km Highways through the interior, past Lake Okeechobee 742 km, 11 h 19 min
minutes I-10, I-75, the Turnpike 789 km, 8 h 18 min

Same query, same view, a different weight property: 46 km longer, 3 hours faster.

Several Costs on One Network

The shortest route is rarely the only one that matters. Distance, travel time, tolls, fuel, emissions, risk: each is a property on the same edges, and a view keeps one hierarchy per cost, all built from the same topology and all kept up to date by the same commits.

Because the network lives in a multi-model database, the costs can come from anywhere in it: travel times aggregated from time-series sensor data, tolls stored as documents, restrictions joined from your asset records. The route is computed where the data already is.

Benchmark: CCH vs Dijkstra vs A* on 1 Million Junctions

The DIMACS Florida road graph (USA-road-d.FLA) has 1,070,376 junctions and 2,712,798 road segments. The routes start in Tallahassee and go to 12 destinations, from the nearest to the farthest quantile of its shortest-path tree, plus Coral Gables, across the state.

Chart: on the Florida road network, Dijkstra's query time from Tallahassee grows from 7.8 ms to 104 ms as the destination moves away, A*'s from 3.1 ms to 132 ms; the Customizable Contraction Hierarchy stays between 0.010 and 0.041 ms. Tallahassee to Coral Gables: 0.039 ms with CCH, 99 ms with Dijkstra, 121 ms with A*

Dijkstra pays for every kilometer, CCH does not: its line is flat. Per query it also allocates kilobytes instead of tens of megabytes, which is what lets one server answer many routing requests in parallel without feeding the garbage collector.

A* is only as good as its estimate. To stay exact, the straight line to the destination may never exceed the real cost of any road, and in this data 112 of 2.7 million road segments are shorter than the straight line between their ends. That caps the estimate at 67% of the true distance. A* is then 2.5x faster than Dijkstra for nearby destinations, and slower across the state, where the weaker estimate no longer pays for its extra work. A bolder estimate would be faster and could return a longer route. CCH has no estimate to tune.

CCH pays once, up front: seven seconds to build the hierarchy for Florida and memory to hold it. For a network that serves many queries, that trade is easy. All numbers are the median of three runs of CCHRoadNetworkBenchmark in the open source engine, which runs on any DIMACS road graph; more results on our benchmarks page.

Florida, Apple M5 Pro

CCH Dijkstra A*
Query, near to farthest0.010-0.041 ms7.8-104 ms3.1-132 ms
Tallahassee to Coral Gables0.039 ms99 ms121 ms
CCH speed-up vs Dijkstra780-3,100x
Memory per query6-43 KB11-44 MB9-52 MB
Through the database0.04-0.06 ms
First build6.6 snonenone
Memory, view + hierarchy306 MBnonenone

Which Path Finder, When

You need Use
The fewest hopsshortestPath()
A weighted route, now and thendijkstra(), algo.dijkstra
The same, with coordinatesastar(), algo.astar
Many routes on a road-like networkcchShortestPath(), algo.cch.shortestPath
Alternativesalgo.kShortestPaths
Negative weightsbellmanFord()
Distances to every destinationalgo.dijkstra.singleSource

When Not to Use Contraction Hierarchies

CCH is a tool for networks with geography (roads, rail, pipes, power lines, floor plans, game maps) that answer many point-to-point queries. Reach for something else when:

  • The graph has no small separators. Social networks, citation graphs, anything with supernodes would need a hierarchy many times larger than the graph. ArcadeDB detects it, marks the hierarchy UNSUITABLE and keeps answering with Dijkstra.
  • You ask rarely. For a handful of routes a day, Dijkstra or A* need no preparation and no memory.
  • Weights can be negative. Use Bellman-Ford.
  • You need every destination from one source, as in a delivery-area map. Use single-source Dijkstra.
  • You need turn-by-turn navigation on public maps. Dedicated engines built on OpenStreetMap, with turn costs and road profiles, are the right tool. ArcadeDB is for routing over your network and your data.

Route Planning Applications

Logistics & Delivery

Depots, hubs and customer sites on one network. Price every candidate leg of a dispatch plan in microseconds, by distance, time or cost, and re-plan as soon as a road closes. Pairs naturally with the supply chain graph the shipments already live in.

Fleet & Field Service

Find the technician who can reach a failed asset first, with the travel times your telematics reported a minute ago, and the skills and spare parts stored next to them in the same database.

Utility & Telecom Networks

Power grids, water mains, gas pipelines, fiber: route around a failure, find the lowest-loss or lowest-latency path, and see the effect of switching a segment off before doing it.

Warehouses & Indoor Navigation

Aisles, floors, elevators and gates of a warehouse, hospital, airport or campus. Picking paths and wayfinding that follow blocked aisles and crowded corridors as they happen.

Mobility & Transport

Rail, ferry and road links with travel times, tolls and emissions as separate costs on the same edges. Answer "fastest", "cheapest" and "greenest" from one network.

Games & Simulation

Large world maps where many agents route at once and the terrain changes. Microsecond queries with a few kilobytes of scratch each, embedded in the game server's JVM.

Why ArcadeDB for Route Planning

Contraction hierarchies are well studied. Making them behave like a database feature is the hard part:

  • In the database: no export, no preprocessing job, no routing service to keep in sync. The network, its weights and the hierarchy share one engine and one transaction log.
  • Exact under change: a query is answered by the hierarchy only for exactly the data it was prepared for, and by bidirectional Dijkstra otherwise. A transaction sees its own uncommitted changes.
  • Incremental: weight changes, closures and deletions re-customize only the arcs above them; new roads keep the existing order.
  • Several costs: CCH (km, minutes, toll), built and kept up to date together.
  • Persisted: the expensive part, the order, is saved at a clean close and reused on restart.
  • Safe on the wrong graph: graphs without small separators are detected and refused instead of exhausting the heap.
  • Light: primitive arrays throughout, a per-query scratch sized to the height of the hierarchy (6.6 KB on Florida), pure Java, no native libraries.
  • Everywhere you query: SQL and Cypher, from Java (embedded or client/server), the HTTP API and the drivers.

Apache 2.0, Forever

Customizable Contraction Hierarchies are part of the open source engine starting with ArcadeDB 26.10.2: no enterprise edition, no routing add-on, no per-core license. ArcadeDB is Apache 2.0 forever. Embed it in your product, deploy it anywhere, fork it if you want.

Try It: Tallahassee to Coral Gables on Your Laptop

Everything on this page runs on the Florida road network of the 9th DIMACS Implementation Challenge: 1,070,376 junctions with their coordinates and 2,712,798 road segments with a length (km) and a travel time (minutes). The route-planning use case downloads it and loads it with one request to the GraphBatch endpoint, in about 11 seconds. With Docker: 

git clone https://github.com/ArcadeData/arcadedb-usecases.git
cd arcadedb-usecases/route-planning
docker compose up -d     # starts ArcadeDB on port 2480
./setup.sh               # downloads Florida, loads it, creates the view with CCH (km, minutes)
./queries/queries.sh     # every query of this page, through curl

The java folder runs the same queries from a Java client, and embedded/FloridaRoutes.java runs them in an embedded database with no server and no build step: it loads the network with the GraphBatch Java API, compares dijkstra(), astar() and cchShortestPath() on the same route, shows the two costs, and applies the traffic jam. 

java -Xmx4g -cp "$ARCADEDB_HOME/lib/*" embedded/FloridaRoutes.java

Through the HTTP API, Tallahassee to Coral Gables takes about 3 seconds with dijkstra(), 6 seconds with astar() and 2 milliseconds with cchShortestPath(). The SQL functions walk the stored records, while the hierarchy reads the in-memory view; the benchmark above compares all three on that same view. The Shortest Path guide covers every option, from the unweighted shortestPath() to A* heuristics, and how to check which engine answered a query.

Frequently Asked Questions

What is a Customizable Contraction Hierarchy (CCH)?

A CCH is a precomputed structure for point-to-point shortest paths. It ranks the vertices so that the small sets of vertices that split the network sit at the top, adds shortcut edges, and answers a query by climbing from both endpoints to the top. The cost of a query depends on the height of the hierarchy, not on how far apart the two vertices are. It is customizable because the ranking and the shortcuts depend only on the topology: when weights change, only the costs above the changed edges are recomputed.

How much faster is CCH than Dijkstra?

On the DIMACS Florida road network (1.07 million junctions, 2.7 million road segments), CCH answered 12 queries from Tallahassee at increasing distance in 0.010 to 0.041 ms, Dijkstra in 7.8 to 104 ms and A* in 3.1 to 132 ms: 300 to 3,200 times faster than either. Tallahassee to Coral Gables took 0.039 ms with CCH, 99 ms with Dijkstra and 121 ms with A*. Dijkstra's time grows with the length of the route, CCH's does not. Each CCH query used 6 to 43 KB of memory, Dijkstra 11 to 44 MB, A* 9 to 52 MB.

Can the routes follow live traffic and road closures?

Yes. A weight is an ordinary edge property: an UPDATE changes it, and the hierarchy re-prices only the arcs above that edge. On the Florida network a single weight change took 0.8 ms from its commit to a hierarchy answering for it, 100 changes about 41 ms, and a closed road about 1 ms. Queries never wait: until the hierarchy has caught up they are answered exactly by bidirectional Dijkstra.

Do I need a separate routing engine next to my database?

Not for routing over your own network. ArcadeDB keeps the network, its weights and the hierarchy in one transactional engine, so there is no export, no preprocessing job and no sync between a database and a routing service. Dedicated engines built on OpenStreetMap remain the right tool for turn-by-turn navigation on public road maps.

When should I use Dijkstra or A* instead of CCH?

For occasional queries, for networks that change shape all the time, and for graphs without small separators such as social networks or graphs with supernodes, where a hierarchy would be many times larger than the graph. ArcadeDB detects those graphs, marks the hierarchy UNSUITABLE and keeps answering with Dijkstra. Use Bellman-Ford when weights can be negative.

Can one network have several costs, such as distance and travel time?

Yes. A Graph Analytical View keeps one hierarchy per weight property, for example CCH (km, minutes), and keeps all of them up to date together. Each query names the weight it minimizes.

Which query languages can compute shortest paths in ArcadeDB?

SQL, with dijkstra(), astar(), cchShortestPath(), bellmanFord() and shortestPath(), and Cypher, with algo.dijkstra, algo.astar, algo.cch.shortestPath, algo.kShortestPaths and the shortestPath() pattern. Both are available from Java, the HTTP API and the drivers.

Is route planning on ArcadeDB free to use?

Yes. ArcadeDB is Apache 2.0 licensed and free in production, including Customizable Contraction Hierarchies, which are part of the engine starting with ArcadeDB 26.10.2, written in Java with no native dependencies.

Ready to Route on Your Own Network?

Load your network, add one view, and get exact shortest paths in microseconds that follow every change you commit. No routing service to deploy, no pipeline to maintain.

Get Started Run the Demo Code Read the Shortest Path Guide