Expand description
§RouteE Compass Core
The core routing algorithms and abstractions used by RouteE Compass.
This crate has the following three top-level modules:
- the traits for data models (
crate::model) - implementations for the search algorithms which use those models (
crate::algorithm) - utility modules (
crate::util)
§Data Model
§Top-Level Data Models
A search algorithm for a search query uses a unique SearchInstance built of the following types to execute a search. These are grouped into three categories for readability: the topology of the network, the physics of how the search updates, and the metrics that are captured by the search. These are either implemented with some static type closed for extension (e.g. a Rust struct) or, a dynamic type (a Rust trait object) which can be implemented in downstream crates. Each of these models is configured in the Compass configuration file with the given configuration key.
| model | category | implementation | key | description |
|---|---|---|---|---|
| Graph | topology | static | [graph] | the road network topology as a vectorized adjacency list |
| MapModel | topology | static | [mapping] | geospatial map matching and LineString reconstruction of routing results |
| TraversalModel | physics | dynamic | [traversal] | applies link traversal updates to search state (e.g., link travel time) |
| AccessModel | physics | dynamic | [access] | applies updates between link pairs to search state (e.g., turn delays) |
| FrontierModel | physics | dynamic | [frontier] | predicates for determining if a given link is traversable |
| TerminationModel | physics | static | [termination] | applies rules on compute resource utilization for each search instance |
| StateModel | metrics | static | [state] | mapping between domain-level state representation and the vectorized search state |
| CostModel | metrics | static | [cost] | maps search state to a cost scalar that is minimized by the search algorithm |
§Builder, Service, Model
In Compass, the requirement for phased initialization of (thread-) shared assets is to represent them as new values in the system.
At initialization, empty Builder objects that implement a build method can construct a Service.
A Service has a lifecycle of the entire program but is not read directly by a search algorithm as it has not yet had the chance to be customized for a given search query.
For that, the Service must build a Model from the query arguments.
A Model is instantiated in the thread when running the search and is destroyed when the search is completed.
For details on the builder, service, and model traits for each dynamic model type, see:
crate::model::traversal- [
crate::model::access] crate::model::frontier
§Algorithm
RouteE Compass provides implementations for the following search algorithms in the core module. These algorithms are selectable via the SearchAlgorithm enum which is configured using the [algorithm] configuration key. The algorithm type is either single-sourced shortest path (SSSP) or k-shortest path (KSP).
| algorithm | implementation | type | link | description |
|---|---|---|---|---|
| Dijkstra’s Algorithm | a_star | SSSP | wikipedia | implemented as A* with h(n) = 0 for all vertices |
| A* | a_star | SSSP | wikipedia | graph search with goal-oriented heuristic tuned by the StateModel, TraversalModel, AccessModel and CostModel parameters |
| Yen’s Algorithm | yens | KSP | wikipedia | metaheuristic to approximate the k least-cost paths subject to an optional similarity constraint, does not scale well to national routing |
| Single-Via Paths | svp | KSP | dl.acm.org | metaheuristic to approximate the k least-cost paths to an optional similarity constraint, suitable for national routing |