Change transit routing algorithm from A* to RAPTOR

[drewda]

Goal

We want to make the transit routing in OTP faster and at the same time better by changing from the existing A* (AStar) to a Raptor based algorithm. We want to keep all existing features or replace them with something at least as good. Some of the benefits are:

• faster travel search (our goal is at least 10 times faster)
• more and better variation in the result. We want true support for multi-criteria search (arrival time, transfers, travel duration, operator, weight/cost ...)

Changing the algorithm also mean that we will create a new data structure for transit - optimized for Raptor. The existing routing graph will be used for none transit search, but transit data will be removed.

Terminology

The Raptor algorithm is described in a paper by Microsoft from 2012. We plan to use the Range Raptor with Multi-criteria pareto-optimal search.

Raptor

Raptor is a graph algorithm that works in rounds. The search start from a list of access stops and arrival times (initial stop-arrivals). Then for each round all trips from these stops is explored, and so are transfers from all stops reached. A new list of stop-arrivals is found. This new list of stop-arrivals is used as input for the nest round. The algorithm will terminate by it self, or can be stoped when you have the desired results. The reason this is much faster than the current OTP A* is that there is no need to maintain a priority queue of edges to explore.

Range Raptor (RR)

Range Raptor works in iterations over minutes. Let say you want to travel from A to B sometime between 12:00 and 13:00. Then Range Raptor start at 13:00, and for each minute run the search again: 12:59, 12:58 ... until 12:00. The way Raptor works enable us to do this in a super efficient way only adding a smal percentage to overall performance (compared to a singel Raptor search). This pack the trip and ensure finding the best trip in that period with departure time after 12:00 o'clock. Search on arrival time is done in a similar way. The packing is only valid for the search time window; There might be a trip leaving after 13:00 that is faster than the trips found.

Multi-criteria Range Raptor (McRR)

Raptor gives us the optimal trip based on arrival time. With some overhead we can add number of transfers. Range Raptor also gives us the shortest travel duration (within its search window). But we want more - OTP is today only optimized on cost, witch is a mix of time, waiting time, walking distance, transfers and so on. So, a McRR search will return a pareto-optimal set of paths with at least these criteria:

• arrival time (seconds)
• number of transfers (scalar)
• travel duration (seconds)
• cost (scalar) (a function of anything else than mention above)

We will also experiment with extracting other criteria from the cost like walkingDistance, operator. The goal is to make this configurable so each deployment may tune this to their needs. Due to performance reasons it might not be 100% dynamic.

Because Raptor is much faster than the multi-criteria Raptor we will provide an option (request parameter) to run both RR and McRR. We might even use RR as a heuristics optimization for McRR. In a bench mark test, RR takes on average 80ms while McRR with the same configuration takes 400ms. If we add walking distance as an extra criteria the average time increase to 1000ms. (The numbers provided are for relative comparison - it is to early to compare with the existing OTP performance).

Paths and Itineraries

In this context, Path and Itineraries are almost the same. We use Path to talk about the minimum set of data returned by Raptor, then these paths are decorated with more information and returned to the end user as Itineraries.

Pareto optimal/efficiency set

All paths that is considered pareto optimal for a set of criteria is returned by the McRR. This can be a large set (like 500 paths), so we need to reduce this by applying a filter to the set of paths and further a final filter to the itineraries (paths decorated with more info). The idea here is to have a configurable filter-chain with decorating, mapping, sorting and filtering capabilities.

Pareto-set explained

See Wikipedia A pareto-set of paths/itineraries is a set where all elements are better (less than) for at least one criteria than all other elements in the set. Given a set { [9,2], [5,6], [3, 8] } then [7, 4] would make it into the set. This is because 7 < 9 (comparing the 1sr criteria, element 1), while 4 < 6 and 8 (comparing the 2nd criteria, element 2 and 3). [6,7] would not make it into the set because [5,6] is better for both criteria.

Features

Algorithm implementation (R5 repo)

• Algorithms
  • Range Raptor :white_check_mark:
  • Mc Range Raptor :white_check_mark:
• Mc-criteria
  • Arrival time :white_check_mark:
  • Number of transfers (Egress optimization due):white_check_mark:
  • Travel duration :white_check_mark:
  • Cost :white_check_mark:
  • Operator
  • Wheelchair/Accessibility
  • ???
• arriveBy search. See #2885

  OTP integration

• Itinerary sort and filtering.
  TODO

  Filters

• Filter on stop :white_check_mark:
• Filter on routes
• Filter on trips

Design

The Raptor implementation is implemented as a Java library with its own API and has a singel point of access theRangeRaptorService.

• It is self contained and have no dependencies to any other library.
• It is modular, with several pluggable components. The wiring is done in separate assembly classes (configure classes).
• To provide Transit data for the algorithm you need to implement a data provider. Currently we have done so both in R5 and in OTP.

Optimizations

• Limit on maxAdditionalNumberOfTransfers not maxNumberOfTransfers. We want to change this to be relative to the trip with fewest transfers. :white_check_mark:
• Limit on destination pareto-set (not just time). Doing this the first time (not every time) we arrive at a stop might give the best performance. :white_check_mark:
• Use R or RR as a "heuristics optimization", possible bi-directional, computing a set of stops/routes that can be used as a filter for the McRR. RR is super fast, more than 10x faster than McRR with 4 criteria. :white_check_mark:
• A full list of optimizations is in the Entur r5 repository.

Status

We at Entur started on this with support from @abyrd the Summer 2018. We are currently developing the McRR in R5 on GitHub and integrating it in OTP, Entur´s GitHub repo. We will move the code from R5 into OTP repo later, but currently this arrangment is the most efficient way of developing this.

• A POK is available at: https://otp2.staging.en-tur.no/
• A list of "things to remember" is maintained in the Entur R5 GitRepo - feel free to take a look and comment. Note! This issue is the formal place to document and follow up on the R5 development with regard to the OTP community.

All relevant info should be documented in the code, so when moving the code from Entur/R5 the insights from the issues should also be part of the code documentation.

[drewda]

@abyrd feel free to revise title. Perhaps also worth starting a bullet list of the high-level questions to discuss and tasks to complete?

[abyrd]

Work is already underway for this on the Entur fork. That work is at prototype stage, we will update this ticket when finalized concepts actually start being re-written into the dev-2.x branch.

[ShoSashko]

@t2gran Hello, do you have any idea when Wheelchair/Accessibility will be implemented?