conveyal / r5

Developed to power Conveyal's web-based interface for scenario planning and land-use/transport accessibility analysis, R5 is our routing engine for multimodal (transit/bike/walk/car) networks with a particular focus on public transit
https://conveyal.com/learn
MIT License
280 stars 73 forks source link

McRaptorSuboptimalPathProfileRouter applies strict dominance to states using the same sequence of patterns #433

Open mattwigway opened 6 years ago

mattwigway commented 6 years ago

At the top of doOneRound in McRaptorSuboptimalPathProfileRouter, ~we~ I put a comment that

// We never propagate more than one state from the same previous pattern _sequence_
// e.g. don't have two different ways to do L2 -> Red -> Green, one with a transfer at Van Ness
// and one with a transfer at Cleveland Park.

This is done by applying strict time-based dominance regardless of the DominatingList implementation.

This makes sense for Modeify/point-to-point applications, as we want to avoid presenting "ladder transfers" where we have a bunch of options that transfer between parallel lines at different points. But for fare-based routing it's incorrect - in the example above, the transfer at Van Ness is probably faster but the one at Cleveland Park is probably cheaper.

In systems with long parallel line sections, this has the potential to increase algorithmic complexity significantly, but probably wouldn't actually be that bad because we don't save strictly equal states (i.e. same fare and same time) which a lot of these ladder transfers would probably be.

mattwigway commented 6 years ago

I have a fix for this in my fork. Performance is still fine, since the fare for these different paths is generally comparable and thus the fastest ones win.