Long Distance Mode and Transfers

[andrew byrd]

Hello dev-list,

OTP has two main strategies for trip planning: long-distance mode and
(for lack of a better term) "classic" mode. Long distance mode emerged
as we moved up to data sets the size of the Netherlands or all of New
York State. Classic has been maintained mainly because of an obscure
requirement with wide-reaching implications that emerged organically
while working on the TriMet regional trip planner, namely that
non-walking (generally bike) segments of a trip could occur not only at
the beginning and end of a trip but also at transfers.

One of the key differences in long-distance mode that allows it to scale
well is the elimination of this requirement. It uses only precomputed
transfers found at graph build time and only explores the street network
to find nodes where it can enter or exit the transit network. The need
to explore the street network and apply user-specified biking
preferences at every potential transfer location has long been a source
of complexity in OTP. Many months have been spent ensuring this
requirement is met, and it has interfered with the implementation of new
routing algorithms more than once.

It turns out that many users perceive bicycle transfers that differ from
their walking counterparts as confusing at best, and at worst they are
seen as bugs. This is a case of the router being too clever by half:
finding an unusual and unintended way to use the transit system that is
by some definition better or faster, but is far enough outside what
people expect to be problematic. In fact, a rather old ticket reveals
that bike transfer legs have been perceived as bugs internally at
TriMet: https://github.com/opentripplanner/OpenTripPlanner/issues/268

Long-distance mode is now used in production in New York State among
other places, and TriMet has formally acknowledged that they intend to
make the switch next time they move to a newer release of OTP. Unless
anyone has a serious objection, to simplify development and maintenance
I plan to remove the classic mode and make long-distance mode the
default.

-Andrew

[Hannes Junnila]

Hi Andrew,

Something that should be fixed before that can be done is adapting the long distance transfers to support wheelchair-accessible transfers. Currently the transfers for the long-distance mode are created without taking into account if they are wheelchair-accessible, but used as such in the routing process.

I don't know if this is a known bug, or if it should be opened on Github as a new issue. A possible solution is to search for two transfer paths between stations, one with wheelchair set to true and another with false. If the paths are the same, then just mark it as wheelchair enabled, and if they are different, two transfer paths between the stops should be generated.

/Hannes

[Laurent Gregoire]

Hi Andrew,

Le 21/01/15 00:32, andrew byrd a écrit :

> anyone has a serious objection, to simplify development and maintenance
> I plan to remove the classic mode and make long-distance mode the
> default.

By removing do you mean removing or deprecating the code or just making
it a non-default option?

The classic mode allows hybrid transit / bike share trip plans (bike
share at the start, end or middle of a journey). We may tweak the path
parser to allow this in long distance mode for bike share at the
start/end, I'm wondering if it would be possible to include it in the
middle? We may also want to keep bike P+R, "OV-fiets" modes and various
other bike+transit combinations, we have to make sure they are
compatible with the long distance mode.

--Laurent

[andrew byrd]

On Wed, Jan 21, 2015, at 08:46, Hannes Junnila wrote:
> I don't know if this is a known bug, or if it should be opened on Github
> as a new issue. A possible solution is to search for two transfer paths
> between stations, one with wheelchair set to true and another with false.
> If the paths are the same, then just mark it as wheelchair enabled, and
> if they are different, two transfer paths between the stops should be
> generated.

True, we will need to allow for multiple transfers with different
characteristics between the same pair of stops. This also provides a
solution for anyone who might want to enable bicycle transfers in the
future.

I don't see any existing issue for this so I have created one (1706).

-Andrew

[andrew byrd]

On Wed, Jan 21, 2015, at 10:29, Laurent Gregoire wrote:
> By removing do you mean removing or deprecating the code or just
> making it a non-default option?

At the highest level, all I want to do is remove the --longDistance
switch, always precompute transfers when building a graph, and not force
the person deploying OTP to choose between two server-wide "modes" when
starting up the server. It would perhaps be more accurate to say I want
to merge all the search techniques, keeping the more successful ideas
from LD mode active when transit routing is selected.

I was planning to remove the path services other than LD, and then
eliminate the concept of pluggable path services entirely. This
abstraction was already present so we used it to try out some
experimental search techniques, but the interface and multiple alternate
implementations belie the simplicity of what we're really doing here:
just enabling or disabling a couple blocks of logic farther down in the
call stack (a goal-direction heuristic or the comparison function used
when building an SPT). That can be done in a much more readable,
maintainable way with a couple of booleans and conditional blocks.
There's no clear reason to modify behavior globally by plugging together
application components at startup time, that's simply a relic of Spring.

> The classic mode allows hybrid transit / bike share trip plans (bike
> share at the start, end or middle of a journey).

Note that I do not intend to keep LD mode exactly as it currently is.
The restriction of the on-street searches via the heuristic and the path
parser was just a way to let the classic and LD systems coexist while we
were experimenting. It is really quite an arcane way to impose the LD
constraints on our stock SPT-generator class.

Once we unify the search techniques, we could actually perform the
access-to-transit and egress-from-transit searches separately, saving
the on-street paths that successfully reach transit stops before ever
beginning the on-transit part of the search. It will avoid repeating the
destination-zone search for every path, and would would make it quite
efficient to use any mode (including rental/parking variations) at the
beginning or end of the trip.

> I'm wondering if it would be possible to include it in the
> middle?

We will still have a code path that runs a simple forward search
disabling the special LD mode heuristic. This is essential for
single-mode bike or driving requests, as well as one-to-many searches.
This same logic with precomputed transfers disabled would conceivably
allow bike transfers mid-route.

The use of precomputed transfers, origin/destination street searches
before ever entering transit, and the transit-friendly reverse heuristic
would all be independently switchable ingredients rather than a
prepackaged "mode" that requires rebuilding the graph and restarting the
server with a different configuration.

Note however that major users of OTP have clearly stated that they and
their users perceive mid-trip bike transfers as a bug, and it's faster
to use precomputed transfers, so I'm thinking it should be diabled by
default.

> We may also want to keep bike P+R, "OV-fiets" modes and various
> other bike+transit combinations, we have to make sure they are
> compatible with the long distance mode.

We absolutely want to keep these modes: they are among the most valuable
features of OTP. I would even say one of the main motivations for
switching entirely to LD mode is to ensure that all these new modes can
be used efficiently both before and after transit.

-Andrew