Academic Research

[MoKob]

This ticket is tracking an overview of available research in the algorithmic community.

Overview paper: Route Planning in Transportation Networks contains a lot of information on both car navigation and public transit routing.

[MoKob]

A* Search

Publication: Multi-criteria Shortest Paths in Time-Dependent Train Networks

Basic setting

• uses time-dependent graph model
• multi-criteria Dijkstra on graph
• A* via lower bounds obtained by backwards search from the destination
• Running time within order of seconds (Amd Athlon, 2.4) -- probably much faster on other CPUS, but seems slow

Initial Ruling

I expect this algorithm to be too slow for what we want to achieve. It could end up as a tool to speed-up other algorithmic approaches, though.

[MoKob]

ALT

Available in two versions, time-dependent graph and time expanded graph.

Time-Exapnded graph

Publication: Engineering Time-Expanded Graphs for Faster Timetable Information?

Basic Setting

• uses some contraction to reduce network size
• requires special care on modelling routes, otherwise graph size grows too quickly
• presents multiple techniques:
  • node blocking (trade-off edges vs speed-up: factor 3 max)
  • model optimisations (speed-up up to 4)
  • arc flags (geo distance seems a big factor, speed-up 4)
  • ALT variants in different models offer speed-up up to 50
• single criteria optimisation
• mainly model of graph setting

Time-Dependent Graph

Publication: Bidirectional A∗ Search on Time-Dependent Road Networks

Basic Setting

• bidirectional search on time-dependent network
• searches forwards normally, builds form of corridor from backward direction
• only extend forward search into corridor
• trade-off in error-rate vs speed-up, speed-ups depend on worst case guarantees

Initial Ruling

I expect both settings to have little influence on our approach. The graph modelling strategies could prove useful.

[MoKob]

Geometric Containers

Publication: Geometric Containers for Efficient Shortest-Path Computation

Basic Setting

• multiple possible containers explained
• bounding boxes seem to be working best
• few hard numbers of speed-up
• seems to reduce the number of visited nodes to ~ 5% compared to Dijkstra's algorithm.

Initial Ruling

Strong indicator that partitions might possibly help in reducing costs in some form. As of now, I don't think we should use this technique.

[MoKob]

Time Dependent Sharc

Publication: Time-Dependent SHARC-Routing

Basic Setting

• speed-up technique creating shortcuts / using arcflags in combination
• factor 20 faster than Dijkstra, long preprocessing (12 hours)

Initial Ruling

Probably only a good source of model considerations. The general speed-up seems too low in comparison to the preprocessing overhead. Might revisit later, after I have gained more insight.

[MoKob]

Multi Level Graphs

Publication: Using Multi-level Graphs for Timetable Information in Railway Systems

Basic Setting

• uses 4 level-graph to achieve speed-ups of 11
• mld like implementation
• requires pre-computation to generate connections between overlay nodes

Initial Ruling

It might benefit from better partitioning algorithms available now. I fear the complexity of combining connections might offer problems in a production setting. Requires re-visit when I have gained more insight into the problem.

Multi Level Separators

Actual separators seem to be a useful tool to speed-up the connection scan algorithm. More information to follow on the Connection Scan comment.

[MoKob]

Connection Scan

Publication: Intriguingly Simple and Fast Transit Routing

Basic Setting

• Linear Scan of Connections (connection array)
• Topological sort over Dijkstra's algorithm
• No explicit graph
• able to handle complex scenarios other than earliest arrival
• very fast algorithm, usually well within a 100 ms

Connection Scan Accelerated

Publication: Connection Scan Accelerated

Basic Setting

• adding multi level support based on Separators to CSA
• MLD like setting

Further speed up over already fast technique. Would potentially allow for all the speed we need.

Initial Ruling

This technique is a strong contender. While moving away from the graph model (on demand / taxi would possibly be impossible to incorporate), it provides one of the fastest exact algorithms.

[MoKob]

CH

Publication: Contraction of Timetable Networks with Realistic Transfers

Basic Setting

• Special Graph model (station graph model)
• applies contraction hierarchies algorithm
• low speed-up (~ 5) over Dijkstras algorithm on smaller networks
• better speed-up (up to ~ 70) on longer rail networks.

Initial Ruling

Probably not the way to go. Seems to offer not enough benefit in comparison to other techniques.

[MoKob]

Transfer Patterns

Publication: Fast Routing in Very Large Public Transportation Networks using Transfer Patterns

Basic Setting

• division into different transfer patterns (direct connections, hub stations)
• extensive pre-computation
  • requires space increase, direct connections alone nearly double space)
  • very fast direct connection look-up
  • hubs required to make large networks manageable
• 1:1 queries in 10 ms, 50:50 in 50 ms (good table behaviour)

Initial Ruling

Precompute / Space overheads are large. Heuristics to keep it manageable without too large overheads. Might be something to revisit, but I'd expect the cost to bee too high in comparison to other algorithms like Raptor/Connection Scan.

[MoKob]

Transit

Publication: Finding Multi-criteria Optimal Paths in Multi-modal Public Transportation Networks using the Transit Algorithm

Basic Setting

• small heuristic component, not specified exactly how heuristic
• very fast query (0.4 ms in their setting)
• long precompute phase (20 hours on Sydney)

Initial Ruling

Probably way to costly for what we require. Some optimisation techniques done might get useful.

[MoKob]

Round Based Public Transportation Optimizer (Raptor)

Publication: https://www.microsoft.com/en-us/research/wp-content/uploads/2012/01/raptor_alenex.pdf

Basic Setting

• bicriteria optimisation (transfers + arrival)
• search in rounds by increasing number of transfers (direct, one hop, two hops...)
• parallel search based on individual lines (not necessarily helpful for us)
• seems to not consider larger networks (probably due no pre-processing)

Initial Ruling

Could potentially be a component of our search. Depends on our scope (cities first?)

[MoKob]

Public Transit Labelling

Publication: Public Transit Labelling

Basic Setting

• group events by stop / sorted by time
• builds on top of RXL
  • label generation in an approx. an hour possible single criteria
  • 60 hours in multi criteria
• mainly graph creation model
• offers special label techniques to reduce cost (stop labels)
• different graphs for earliest arrival, multi criteria search

Initial Ruling

Multi criteria search seems way out of reach, although times might not update as often so we could possibly do with longer processing times. Updates to the network would become costly, though. Query times are incredibly fast, though. It might be possible to use parts of the approach for different steps? Keep in mind.

[MoKob]

Condensed Search Trees

Publication: Trip-Based Public Transit Routing Using Condensed Search Trees

Basic Setting

• trips as nodes
• transfers as edges
• precomputes transfers
• very fast precompute phase
  • compute all possible transfers
  • remove superfluous transfers (opposing direction, suboptimal)
• Query algorithm similar to Raptor (BFS on trips == nodes)
• Prefix Tree Structure to speed up searches, optimised for space with Postfix trees
• Full algorithm (optimised with trees) has very long preprocessing, though (231h sequential on Germany)
• very fast queries (below ms range, way faster than Accelerated Connection Scan)

Initial Ruling

I find the model intriguing and feel that we can possibly use the ideas, whether we opt for the algorithm itself or not. Pre-processing would have to be kept in check, though.

[MoKob]

No further actions. Can be accessed over research milestone.