Thor

Thor serves as a routing engine backed by tiled open source routing data. Thor is a companion to Sif which it relies heavily on to determine the appropriate graph traversal. The resulting path can be used as input for creating guidance/narrative. The name Thor was chosen as an acronym standing for: Tiled Hierarchical Open Routing and was the foundational idea around which the organization Valhalla and its Norse mythology theme was formed.

The thor library is essentially a set of various data structures and algorithms which deal with things like: A* graph traversal, edge costing, vertex costing and path construction. It also includes methods for computing time-distance matrices, optimized routing, and isochrones.

Components

What follows are some notable components of thor.

PathAlgorithm

Valhalla uses a couple different algorithms to generate the route path. Thor contains a base class, called PathAlgorithm, defining the route path comptution interface. The following classes are derived from PathAlgorithm: - AStar - This is a forward direction A* algorithm which is currently used only for “trivial paths” where the origin and destination are on the same edge or adjacent, connected edges. - TimeDepForward - This is a forward direction A* algorithm meant to be used for time dependent routes where a departure time from the origin is specified. - TimeDepReverse - This is a revers direction A* algorithm meant to be used for time dependent routes where an arrival time at the destination is specified. - BidirectionalAStar - This is a bidirectional A* algorithm used for routes that are not time-dependent and are not trivial. - MultiModal - This is a forward direction A* algorithm with transit schedule lookup included as well as logic to switch modes between pedestrian and transit. This algorithm is time-dependent due to the nature of transit schedules.

TripPathBuilder

The PathAlgorithm methods all form a simple definition of the route path containing the directed edges comprising the path as well as the elapsed time at each edge along the path. This list is sent to a class called TripPathBuilder to form a more detailed representation of the trip path. TripPathBuilder forms details along the path that are required for guidance or narrative generation. Forming this TripPath requires reading attribution such as names, geometry, and other information required so that the subsequent guidance generation processing does not have to access the Valhalla tiles.

Matrix, Isochrone, Optimized Routes

Thor also includes methods to compute time-distance matrices, isochrones, and optimized routes (Traveling Salesman Problem).