liveBook · Manning

Highway hierarchies

As explained in Optimization Algorithms: AI techniques for design, planning, and control problems

A hierarchical shortest-path technique that accelerates routing by identifying and using higher-level highway edges.

Highway hierarchies speed up routing through a road-network graph by assigning roads levels, such as residential road, national road, and highway. The aim is to avoid exploring millions of nodes when an interactive navigation app needs a route. section 4.3.4

Road levels can be supplemented with data such as designated speed and number of turns. A modified search, using bidirectional Dijkstra’s or A*, considers both distance to the destination and the type of road it might explore next. Far from the destination, it favors highways; closer in, it also considers national roads and then residential streets. section 4.3.4

New York to Miami

A long-distance drive starts on local roads, joins a highway for the middle of the trip, and returns to local roads near Miami. The hierarchy focuses the long middle stretch on major roads rather than searching every nearby street. section 4.3.4

How Optimization Algorithms: AI techniques for design, planning, and control problems covers it

How deep it goes
Explains road levels, supporting data, and search behavior through a driving example, without giving a highway-hierarchy implementation.
Examples
Uses a New York–Miami drive to contrast local roads near endpoints with highways over the long middle stretch.
What it assumes
Assumes familiarity with road-network graphs and shortest-path search, using Dijkstra’s algorithm as the performance baseline.
What you can do after
Evaluate/understand how road levels can reduce node exploration in a long-distance routing query.
How it connects
Connects road-network graphs and search-space pruning to bidirectional Dijkstra’s algorithm and A*.
Cover of Optimization Algorithms: AI techniques for design, planning, and control problems
liveBookmanning.com
Read Optimization Algorithms: AI techniques for design, planning, and control problems on liveBook Get the book at manning.com

Related concepts

This explainer was generated by Manning's knowledge graph from the text of Optimization Algorithms: AI techniques for design, planning, and control problems. The section links point to the parts of the book it draws on.