arrive by trip causing longer layover to arrive closer to time specified

[meyersj]

http://maps5.trimet.org/?purl=/osm&submit&fromPlace=255%20SW%20HARRISON%20ST::45.510152,-122.679417&toPlace=LINCOLN%20HIGH%20SCHOOL::45.519642,-122.689226&mode=TRAINISH,WALK&maxWalkDistance=420&time=8:00am&date=3/11/2014&arriveBy=true

This trip provides an itinerary that has you wait at SW Galleria/10th for 20 minutes in order to get you to your destination as close as possible to the 8:00 AM arrive by time. Four trains pass you at this time which would all get you to your destination albeit a little early. Although algorithmically this behavior is valid, from a practical standpoint most people would probably prefer to arrive a little early instead of waiting to transfer. A potential fix would be for OTP to make a second pass through the schedule to try and reduce layover time at the expense of arriving early.

[abyrd]

Actually OTP does already make several passes through the itinerary for the reason you cited. We call this "reverse optimization" because it works by running through the itinerary, reversing it once or twice. However, reverse optimization only considers trips visiting the exact same stops as those on the original solution, to keep calculation times down.

@JordenVerwer has implemented the alternate version where the full search is repeated in each direction considering all possible trips and routes, but discovered that it was somewhat too slow to be useful.

Maybe we need a middle ground, where we consider all trips on the same routes as the original solution. Still, in a case like the Max where there are separate routes sharing a common trunk, vehicles belonging to the other routes will not be considered.

[JordenVerwer]

It's possible that my code would yield acceptable performance on a Portland-sized graph. However, it was developed in the mmri-rt branch and would need to be backported to master. Furthermore, the code was written to be generic with regard to the path service in use, but was tested mainly with the long-distance path service. There could be bugs lingering.

Also, only one path (the first result) will be reversed completely. The other paths are treated the same way they are now.

[demory]

This issue has come up again in recent conversations w/ TriMet. Specifically the following trip:

http://trimet.dev.conveyal.com:8001/?module=planner&fromPlace=45.577402541430224%2C-122.64076709747314&toPlace=45.49792488715174%2C-122.52365112304688&time=2%3A00am&date=02-02-2017&mode=TRANSIT%2CWALK&maxWalkDistance=804.672&arriveBy=true&wheelchair=false&locale=en&itinIndex=0

This is a late-night "arrive by" trip that has two legs, the first on Route 70 and second on Route 9. The returned itinerary uses the latest possible 70 trip (departing at 9:32pm), and the latest possible 9 trip (departing at 12:52am), with a nearly 2-hour wait between the two legs.

We should note, however, there are other, earlier 9 trips that could be taken in conjunction with the same 9:32pm Route 70 run that result in a much shorter transfer wait. You can see one such trip by clicking "Previous" in the above example -- this returns an itinerary that departs at the same time but arrives much earlier (10:44pm).

I agree with the original comment that while the current OTP result is algorithmically valid, most people would prefer the shortest-duration itinerary that still departs at the latest possible time -- i.e. with any unavoidable excess wait time occurring at the destination rather than at a midpoint transfer.

[fpurcell]

URLs to the testing instance at TriMet

http://maps7.trimet.org/ui_prod/?module=planner&fromPlace=45.577402541430224%2C-122.64076709747314&toPlace=45.49792488715174%2C-122.52365112304688&time=2%3A00am&date=02-02-2017&mode=TRANSIT%2CWALK&maxWalkDistance=804.672&arriveBy=true&wheelchair=false&locale=en&itinIndex=0

[abyrd]

@demory the result you describe seems like a bug. I wouldn't even say it's algorithmically valid: OTP is supposed to find exactly the combination that you and @fpurcell expect to see. In the forward direction, we'd search forward, then backward, then forward again to get this. The main weak point is that we only consider the same routes that were found in the initial forward search, but that often works OK.

in this arrive-by search, we'd need to search backward, then forward again to "compact" the legs of the trip earlier in time. OTP is supposed to do this. If it doesn't it's a bug.

[seime]

We see the same problem here in Norway, and @fredinge is working on a fix

[fredinge]

We are currently testing a version in Norway which uses a full reversed search to compact the legs. As described here: https://groups.google.com/forum/#!topic/opentripplanner-dev/l43bsXhkglA, we also need to consider different routes sharing a main trunk.

[tuukka]

Better reverse-optimisation has become critical for us as well. @fredinge What are your experiences this far?

[fredinge]

Hi @tuukka, experiences in test so far are good. You can check out the fix here: https://github.com/RuterNo/OpenTripPlanner/tree/ruter_compact_legs Enable the reversed search with compactLegsByReversedSearch=true in router-config.json

[abyrd]

Transit routing has been completely replaced in OTP2, and range raptor behaves very differently than the old reverse-optimization / compaction approach. Closing.