The issue #2788 describe different ways to transfer(interchange). Implementing all of these in OTP2 in one PR is not practical and at Entur we would like to start with Stay seated and Guaranteed transfers for trip-to-trip transfers. We expect these to to have similar implementations. I will use the term Transfer with an advantage to refer to both Guaranteed transfer and Stay seated .
Transfers is implemented in OTP1, but need to be implemented again with Raptor as a transit search engine.
Outside of scope
The stop-to-stop, and route-to-route and other combinations can be solved by pre-processing the transit data and convert these into trip-to-trip transfers. This might not be efficient, but this issue is not about those cases. Implementing this issue will only add trip-to-trip transfer and focus on the Raptor implementation.
Input GTFS and NeTEx
Both NeTEx and GTFS support the information needed to implement this, at least partially.
GTFS
This issue will support transfers with transfer_type=1 (Guaranteed) transfers in transfers.txt.
Trip-to-trip transfers is proposed in the Google extension to GTFS. This first implementation will NOT include stop-to-stop transfers, you need to use the extension to use it with trip-to-trip.
GTFS do not support the Stay seated and we will not use the blockId to implement this as part of this issue.
NeTEx
The Interchange in the NeTEx specification (Nordic profile) have all the information needed to implement this.
Example
This example is used in the discussion below. Alternative 1 and Alternative 2 both arrive at Stop C, and depending on the number-of-transfers, time and generalized-cost they might end up dominating each other (OTP McRaptor).
Implementation discussion
This is not straight forward to implement in Raptor. The main problem is that we keep a set of pareto-optimal arrivals at each stop/quay. For Guaranteed transfer and Stay seatedSome transfers are preferred over others, but the trip with a preferred transfer can be dropped on arrival at a stop. This happens before we know witch trips to board or transfers to use.
**The Raptor algorithm is based on the assumption that to arrivals at a stop can be compared and that none of them is given an advantage in the future. ** For example, Alt 1 and Alt 2 arrive at C, if Alt 1 is better than Alt 2, Alt 2 is dropped. The problem occurs if Alt 2 have a Guaranteed transfers to Trip X. If we had not dropped Alt 2 the cost would be better than Alt 1 at stop D. The reason is that the Guaranteed transfers is given a advantage and is preferred over Alt 1 at stop D, but not at stop C. The problem is the same independent of the iteration(departure time), round(number-of-transfers) and transfer at the same stop or by walking. The problem exist as long as Alt 2 is dominated by Alt 1 and Alt 2 would be a valid, pareto-optimal, alternative in stop D.
Many solutions is suggested, but most of them have undesired side-effects. In some cases we could patch the result in a post-processing step, but that increase the complexity. The way to solve this is to keep track of all arrivals with an "later-advantage" and make sure they are allowed to board Trip X - even if they are not part of the pareto-set at stop C.
Performance
We also need to pay attention to the performance, in theory the transfers should limit the number of possible solutions; hence improve the performance. But, it might be hard to find such solution, and we are happy if we can find a solution with the same performance. The first implementation of this aim to support a few "special" transfers compared with the total set of all possible transfers. In the future we can look at pruning the branching if the number of "special" transfers become very large. An effective way to do this is if we can produce a static map of all forbidden [stop, trip] to [stop, trip] transfers.
We are using several Raptor configurations(StdRaptor/McRaptor, optimizations, SingleRoundRaptor/RangeRaptor). Specialized transfers can lead to lower cost; hence we need to support this for McRaptor. Trips with better arrival-time and/or number-of-transfers will never be dominated by a Guaranteed or Stay seated transfer; Hence it is safe to use StdRaptor for heuristic purposes. This is, by the way, not true for a "not allowed transfer"(out of scope here).
Design
Alt A - Using pareto-set
One way to do this is to use a specialized pareto-set at every stop with a "special" transfer. All arriving trips with a special transfer must then be pareto-optimal. To do this we can use a special transfer criteria C. This criteria would be zero for regular trips and eg something unique(the arrived by tripId) for special transfers. If the special transfer criteria is different for two alternatives, they are both pareto-optimal, if not the other criteria(time, num-of-transfers, ...) will be used to decide. The problem with this method is that the number of pareto-optimal solutions will grow quite large. For alternatives with an advantage (C != 0) the only time it competes with another alternative is if you arrive at the same stop riding the same trip, this is a rare event. For earlier-departures(RangeRaptor iterations) this happens only if the earlier-departure is better on cost or number-of-transfers. For higher-number-of-transfers(Raptor rounds) the cost must be lower.
Alt B - Adjusting the algorithm flow
Another way is to handle trips with special transfers is to always include them in the next round. We could do this by keeping a map of (stop->arrivals) for special transfers and process those after/before we do the transits in each round. This would case some extra work, but we do not pollute the pareto-sets at each stop with "special-transfers". We could do a check if the current specal-transfer is in the optimal set before we board the next trip, and skip it, if it is (It will be processed the standard way).
At the end, when we construct paths, this work in McRaptor, because each stop-arrival have a reference to the previous stop-arrival. It would not work in the StdRaptor, because we do not have such back pointer, but instead have a stop index and look up the previous arrival in the raptor state. In this solution the special_transfers are not added to the state. So, when the destination is reached we do not use the RaptorState, we traverse the pointers backwards to produce the path.
The issue #2788 describe different ways to transfer(interchange). Implementing all of these in OTP2 in one PR is not practical and at Entur we would like to start with Stay seated and Guaranteed transfers for trip-to-trip transfers. We expect these to to have similar implementations. I will use the term Transfer with an advantage to refer to both Guaranteed transfer and Stay seated .
Transfers is implemented in OTP1, but need to be implemented again with Raptor as a transit search engine.
Outside of scope
The stop-to-stop, and route-to-route and other combinations can be solved by pre-processing the transit data and convert these into trip-to-trip transfers. This might not be efficient, but this issue is not about those cases. Implementing this issue will only add trip-to-trip transfer and focus on the Raptor implementation.
Input GTFS and NeTEx
Both NeTEx and GTFS support the information needed to implement this, at least partially.
GTFS
This issue will support transfers with
transfer_type=1(Guaranteed) transfers in transfers.txt.Trip-to-trip transfers is proposed in the Google extension to GTFS. This first implementation will NOT include stop-to-stop transfers, you need to use the extension to use it with trip-to-trip.
GTFS do not support the Stay seated and we will not use the
blockIdto implement this as part of this issue.NeTEx
The Interchange in the NeTEx specification (Nordic profile) have all the information needed to implement this.
Example
This example is used in the discussion below. Alternative 1 and Alternative 2 both arrive at Stop C, and depending on the number-of-transfers, time and generalized-cost they might end up dominating each other (OTP McRaptor).
Implementation discussion
This is not straight forward to implement in Raptor. The main problem is that we keep a set of pareto-optimal arrivals at each stop/quay. For Guaranteed transfer and Stay seatedSome transfers are preferred over others, but the trip with a preferred transfer can be dropped on arrival at a stop. This happens before we know witch trips to board or transfers to use.
**The Raptor algorithm is based on the assumption that to arrivals at a stop can be compared and that none of them is given an advantage in the future. ** For example, Alt 1 and Alt 2 arrive at C, if Alt 1 is better than Alt 2, Alt 2 is dropped. The problem occurs if Alt 2 have a Guaranteed transfers to Trip X. If we had not dropped Alt 2 the cost would be better than Alt 1 at stop D. The reason is that the Guaranteed transfers is given a advantage and is preferred over Alt 1 at stop D, but not at stop C. The problem is the same independent of the iteration(departure time), round(number-of-transfers) and transfer at the same stop or by walking. The problem exist as long as Alt 2 is dominated by Alt 1 and Alt 2 would be a valid, pareto-optimal, alternative in stop D.
Many solutions is suggested, but most of them have undesired side-effects. In some cases we could patch the result in a post-processing step, but that increase the complexity. The way to solve this is to keep track of all arrivals with an "later-advantage" and make sure they are allowed to board Trip X - even if they are not part of the pareto-set at stop C.
Performance
We also need to pay attention to the performance, in theory the transfers should limit the number of possible solutions; hence improve the performance. But, it might be hard to find such solution, and we are happy if we can find a solution with the same performance. The first implementation of this aim to support a few "special" transfers compared with the total set of all possible transfers. In the future we can look at pruning the branching if the number of "special" transfers become very large. An effective way to do this is if we can produce a static map of all forbidden [stop, trip] to [stop, trip] transfers.
We are using several Raptor configurations(StdRaptor/McRaptor, optimizations, SingleRoundRaptor/RangeRaptor). Specialized transfers can lead to lower cost; hence we need to support this for McRaptor. Trips with better arrival-time and/or number-of-transfers will never be dominated by a Guaranteed or Stay seated transfer; Hence it is safe to use StdRaptor for heuristic purposes. This is, by the way, not true for a "not allowed transfer"(out of scope here).
Design
Alt A - Using pareto-set
One way to do this is to use a specialized pareto-set at every stop with a "special" transfer. All arriving trips with a special transfer must then be pareto-optimal. To do this we can use a special transfer criteria C. This criteria would be zero for regular trips and eg something unique(the arrived by tripId) for special transfers. If the special transfer criteria is different for two alternatives, they are both pareto-optimal, if not the other criteria(time, num-of-transfers, ...) will be used to decide. The problem with this method is that the number of pareto-optimal solutions will grow quite large. For alternatives with an advantage (C != 0) the only time it competes with another alternative is if you arrive at the same stop riding the same trip, this is a rare event. For earlier-departures(RangeRaptor iterations) this happens only if the earlier-departure is better on cost or number-of-transfers. For higher-number-of-transfers(Raptor rounds) the cost must be lower.
Alt B - Adjusting the algorithm flow
Another way is to handle trips with special transfers is to always include them in the next round. We could do this by keeping a map of (stop->arrivals) for special transfers and process those after/before we do the transits in each round. This would case some extra work, but we do not pollute the pareto-sets at each stop with "special-transfers". We could do a check if the current specal-transfer is in the optimal set before we board the next trip, and skip it, if it is (It will be processed the standard way).
At the end, when we construct paths, this work in McRaptor, because each stop-arrival have a reference to the previous stop-arrival. It would not work in the StdRaptor, because we do not have such back pointer, but instead have a stop index and look up the previous arrival in the raptor state. In this solution the special_transfers are not added to the state. So, when the destination is reached we do not use the RaptorState, we traverse the pointers backwards to produce the path.