One of the biggest technical challenges in point to point route calculation is figuring out how to do real time pre-processing while keeping query latency low. One common method is partitioning the graph into various cells and being able to figure out which cells need updates based on live traffic. Only need to pre-processing particular sections of the graph and then creating shortcut edges across boundary nodes in each cell, then do routing on the overlay. CRP is one of the best paper to summary those idea.
- Consider all details of road network(turns, speed limit, etc.)
- Consider different metrix(different cost function, fastest, shortest, avoid toll, avoid highway, etc.)
- Consider dynamic information
- Traffic jam and user information could reconstruct graph
- low latency
Graph partition, preprocessing, hours
After partition, each cell would be abstract to "big node", only keeps entry -> exit pair. Graph be dramatically constructed but keeps original structure.
(Image from Paper of CRP)
- Nested multi-level partition
- H is abstract graph only contains overlays.
(Image from Paper of CRP)
-
Query applied on overlay.
-
Pruning the overlay
(Image from Paper of CRP)
-
Modeling turn pattern is important for routing algorithm's performance. Ideally, we should hide the complexity of turns and let upper algorithm could apply on classic graph.
-
arc-basedstrategy only keeps tail vertices of intersection, each arc is a road segment following with a turn. Similar strategy be used in OSRM, click here for more information. -
compact representationwill convert intersection to a single vertex. Similar toBig node.- p * q table, tu[i, j] contains all combination {head, tail}
- CRP mentioned based on carefully optimize, performance penalty due to turns could dropped from 3 times to 2 times.
-
Stalling: During search, scanning an entry point of an intersection immediately gives us upper bound of exists points. We could only scan another entry point is its own distance label is small enough to potentially improve result.
Apply dynamic information with cost models, each round of traffic update, seconds
This step should be fast, live traffic could be used only after this step is ready. Partition data with minimum cut is crucial to this step, and in practice, move efforts into step1 could also help to speed up.
Pre-allocating metrics table during pre-processing is one of the most important optimization. During customization only recalculate cost based on traffic and update value.
Real time, per request, miliseconds
(Image from Paper of CRP)
Topological and metric properties of the network is differernt. The topology is the graph structure of the network together with a set of static properties. The metric encodes the actual cost of traversing a road segment or taking a turn.
Partition road network with balanced count and min-cut is the most important step of CRP. Kernighan Lin and Dinic are two basic algorithms. In practice, there are METIS, PUNCH, KAHIP, Inertial flow. For more details, please go to graph partition page.
- OSRM has 3 related components: partition, customization, routed(query).
- Inertial flow is the algorithm used for partition graph, you could go to notes related with OSRM partition for more information.
- OSRM customization and OSRM traffic update records the information for how OSRM update graph based on live traffic.
- How query works in OSRM could go to this page.