r5
r5 copied to clipboard
conveyal
Interlining
We don't currently support interlining. There are two problems we need to resolve to be able to properly support interlining. The first is that no one really has any idea how interlining is supposed to be implemented in GTFS, see discussion here.
The second is that when some trips on a pattern interline and some don't we have a bit of a conundrum on our hands. If we are searching along the route and board one of the trips that doesn't interline, we really ought also to board one of the trips that does in case the interline gets us where we want to go. (see image below, consider someone wanting to go from A to F; the lines are trips and the dots are stops. Every other trip interlines.)
I suppose though that the range-raptor search will take care of this particular issue by finding the later, interlining trip first and not replacing it with a non-interlining trip that isn't better.
One solution is to just treat several trips that interline together as a single pattern.
It seems like we have a consensus at Conveyal, TriMet, and gtfs-changes that the transfers.txt proposal for representing block transfers is best. We'll try to get both TriMet and NL data to use it, and then we can forge ahead with implementation.
I'm not sure the partially-interlining-patterns problem you illustrated is really a problem. This is just another kind of transfer. The only difference is deciding whether to tell the rider to stay on board or stand on a platform, right?
The concern I had is that we might board one of the trips that does not interline, and then you would not be able to reach the interlined trip (suppose stops D and E are too far apart to walk between them).
Oh I see. That's a special case but indeed one that could cause problems. Range raptor stepping backward through time would solve the problem in the topology you illustrated, but consider the case where the more frequent route is route 2. I think it fails there.
How would it fail there? You'd then always be boarding an interlining trip.
I think you're right. I responded too quickly without really thinking it through, and was also imagining an arrive-by search.
I'm not convinced there isn't a situation where it's a problem but I'm having trouble coming up with an example.
Of course if it turns out that if this is not a problem, we ought to be able to drastically speed up the search by folding subpatterns into their superpatterns. For example we could just have one pattern for the red line in DC regardless of the umpteen short turns it does. Range raptor would find you the right train.
Good idea. But are you sure that would lead to major speedup? It sounds like a clever optimization, and those should generally only be applied when they are proven to have a large benefit... I think there's some advantage to maintaining the exact mapping between GTFS trips and patterns too.
This comment is the result of a long discussion between @abyrd and myself. We realized that this is in fact a problem; consider the case where there is a route 0 above that does not interline, and arrives at stop A 2 minutes before each non-interlining trip on route 1. We will then never explore any of the interlining trips on route 1, so the range raptor transfer compression won't save us from missing optimal routes. What it boils down to is that the RAPTOR algorithm is based on patterns, which are unique sequences of stops that can be reached without transfers, and trying to circumvent this ignores the definition of the algorithm.
One thought was to just treat interlining as a transfer (even one that gets priority over other transfers). This also means interlining moves to a new round, meaning that interlined trips wouldn't beat out a trip that arrives on the same vehicle with a transfer instead of an interline. It also doesn't work in general; suppose that there exists a route 2 that is interlined from the 1 at stop A. The 1 arrives at 10:00 and the 2 leaves also at 10:00. There is a trip on the 3 that arrives at 9:58; it will beat out the trip on the 1 and the interline will not be considered.
Our conclusion is that we just need to create patterns for all possible interline sequences. However, rather than breaking all our definitions, we just change the key that makes a pattern unique to include the subsequent patterns that will be visited via block transfers. In the example above, there would be two patterns ABCD on the 1, one with an interline to the 2 and one without. This sounds like it would horrendously increase the number of patterns, but bear in mind that these represent the movements of a single physical vehicle. This is also the way we will enumerate them; we will simply group the trips by what vehicle they are served by. It's slightly messy when block_ids are not specified and we only have the information in transfers.txt, but it's not insurmountable; it still simply represents chaining trips together.
Of course there is an additional problem: loops. Consider a route 1 with stops ABCDA which interlines to itself. From the rider's perspective there are two patterns: the 1 with the interline and the 1 without. This is important because on all trips except the last one it is possible to get to an earlier stop in the pattern (e.g. from C -> B). You never need to make more than one loop. The only case we can contrive at the moment where this is a problem is if you have something like 28 -> 24 Inbound -> 24 Outbound -> 24 Inbound -> 24 Outbound -> 28. If you want to ride from the 24 Outbound to the 28, and you get on the first trip on the 24 Outbound, you won't be able to interline to the 28. However, you will be able to take a normal (non-block) transfer to the later trip on the 24 Outbound.
We should be liberal about printing log messages when assumptions are violated. We believe these cases are extremely rare.
One more thing about this: in the InactiveTripsFilter we check if a particular trip overlaps the time window of interest. On the code that does the checking in TripSchedule.java, there is this comment:
* I can't think of any reason we need to use the first arrivals and last departure,
* rather than the first departure and last arrival.
Of course for interlining we do need to use the first arrival and last departure as they could be the end or start, respectively, of an interline.
I think there's a way to do this that's pretty non-destructive and doesn't break the route <-> pattern mapping. For every trip we follow all the trips that it interlines to, and tack them on to that trip without deleting the later trips, and then we set pick_up_type on those tacked-on stops to drop off only. This way you will always board on the trip that has accurate information (destination etc.). We still have to split patterns if not all trips interline, but that's doable.
@mattwigway looks like this hasn't been worked on in years, but wondering if there is any context on why the existing interlining trip chaining was removed? Is the "serviceId scoping" issue referenced have anything to do with the conversation here regarding how to structure the route<>pattern relationships in light of interlined trips?
Referring to: https://github.com/conveyal/r5/commit/e9c0e13a0eab210c819e8118ba8b0a2f439bbfb7
Which removes the actual modification to TripSchedules applied in:
https://github.com/conveyal/r5/commit/585e7ba89ba50af988107cd562d0a3175164b021
cc: @abyrd
No, I don't think the service ID scoping has anything to do with this conversation. If I'm reading that comment right, I think serviceId scoping refers to the problem that some agencies (e.g. TriMet) use the same service ID to refer to different services on different days - and of course these trips on different days shouldn't be considered interlined.
Re-reading this thread, I'm thinking from a routing standpoint that the best thing to do that will work in all situations is to prepend the last stop_time of the previous trip, and the first stop_time of the next trip, onto every interlined trip, and then allow a special zero-second transfer between interlined routes (if memory serves, transfers currently require 1 minute of slack). This doesn't break when a trip interlines to itself (e.g. a loop). Some post-processing on a user-facing frontend can clean up the directions, and for analysis it doesn't matter. It does mean if you have a say 3-transfer limit, the interline will count as one of those transfers.