Skip to main content

Car

The Car Routing is used for all analyses in GOAT that contain car trips.

1. Objectives​

Car routingGlossaryRoutingCalculating the best path between places across a transport network, and the time or distance that path takes.Read more ↗ is used for many indicators in GOAT, such as Catchment Areas and Heatmaps.

A custom routing algorithm is used for the mode of the car, which only considers paths that are suitable for driving.

2. Data​

Routing Network​

Data from the Overture Maps Foundation is used as a routing network in GOAT. It includes the transportation infrastructure with edges (for any continuous path not bisected by another) and nodes (for any point where two distinct paths intersect), representing real-world networks.

3. Technical Details​

Data Pre-processing​

The following steps are performed on the data to enable quick and accurate routing for cars:

  1. Attribute Parsing: Categorizing attributes of edges (street class and surface).
  2. Geospatial Indexing: Utilizing Uber's H3 grid-basedGlossaryH3 gridA system that divides the earth's surface into hexagonal cells at several resolutions, used to compute and display values over an area.Read more ↗ indexing for efficient routing.
  3. Extracting Restrictions: Identifying one-way access restrictions in addition to speed limits for both directions of the edge (maxspeed_forward and maxspeed_backward).

Routing Process Steps​

Sub-network Extraction​

  1. Buffer Region: Based on user-origin, travel time, and maximum potential driving speed.
  2. Edge Filtering: Include only relevant edges for driving.

For car routing, the edges of the following street classes are considered:

motorway, primary, secondary, tertiary, residential, living_street, trunk, parking_aisle, driveway, alley and track.

You can find further information on this classification in the Overture Wiki.

Artificial Edge Creation​

User-provided origin points are typically located a short distance away from the street network. To account for the additional time (or cost) of driving from the origin to its nearest street (e.g. using an unmarked driveway), artificial (or simulated) edges are created.

Edge Cost Computation​

For all edges in the sub-network, a cost value (represented as time) is calculated based on path length and driving speed.

Cost function for car:

cost_forward = length / maxspeed_forward

cost_reverse = length / maxspeed_backward

When calculating cost_reverse, if an edge contains a one-way restriction and therefore must not be traversed in the reverse direction, it is given a very large cost. This prevents the routing algorithm from considering such edges for routing in the reverse direction.

Note

GOAT's routing algorithm does not currently take into account historic traffic patterns for car routing. This feature is currently under development. 🧑🏻‍💻

Network Propagation​

To compute the shortest path from the origin point to various destinations, a custom implementation of the well-known Dijkstra Algorithm is used.

The implementation has a time complexity of O(ElogV), is written in Python, and uses the just-in-time compiler Numba.