Take fares into account for route calculation

[samvermette]

OTP doesn't seem to be taking fares into account when suggesting routes. For instance, in SF, it will suggest a BART+MUNI trip over a MUNI-only route because it's a few minutes shorter... but also more than twice the price.

I'm not sure of what's the best way to draw the line of fares vs time saved, but I definitely feel that OTP shouldn't prioritize a 5$, 30 min trip over a 2$, 35 min trip. Thoughts?

[novalis]

In general, there is no sane way to do this. There are cases where traveling further costs less. But for your specific case, you could play with preferred or unpreferred routes to get the effect you want.

Sam Vermette notifications@github.com wrote:

OTP doesn't seem to be taking fares into account when suggesting routes. For instance, in SF, it will suggest a BART+MUNI trip over a MUNI-only route because it's a few minutes shorter... but also more than twice the price.

I'm not sure of what's the best way to draw the line of fares vs time saved, but I definitely feel that OTP shouldn't prioritize a 5$, 30 min trip over a 2$, 35 min trip. Thoughts?

---

Reply to this email directly or view it on GitHub: https://github.com/openplans/OpenTripPlanner/issues/943

Sent from my Android phone with K-9 Mail. Please excuse my brevity.

[gcamp]

I would have guessed that a simple transfer penalty applied depending on the fare of that new transfer. There's probably something I don't understand. The most complicated thing is to find a sensible default I think.

[samvermette]

@novalis any thoughts on @gcamp's idea? Maybe something we might be overlooking?

[novalis]

Sorry, missed that email. The problem with that concept is that you can't compute the fare for the second leg until you know where it's going to end. So there's no way to do a sensible transfer penalty there.

[mattwigway]

I see two potential solutions to this problem.

The first is to apply a fare penalty when leaving the transit vehicle. When offboarding, we have to already know the fare for that leg (except in the case of a reverse search, which I address below)--we have to know the fare, because otherwise there would be no way for a fare system to work. We could apply a penalty based on that fare. One problem with this approach is that the planner will stay on transit attempting to find a cheaper place to offboard. This system neatly handles the situation where travelling further costs less; since costs aren't applied until transit is left, we can always apply an accurate fare.

Alternately we could decompose the system into zones of some sort and apply the charge when leaving a zone; this means that intermediate states have more accurate costs, but is more complex and of dubious value, and doesn't handle a case where travelling further on a line actually costs less than travelling a shorter distance (uncommon but possible, I suppose).

The problem, of course, comes with reverse searching. If the fares of legs were independent, this would be fine. However, legs that are earlier in time can affect fares later in time via transfer privileges. In a forward search, this is easy; legs that are earlier in trip time are also reached earlier by the algorithm, so transfer privileges can be propagated forward. However, when reverse searching this does not hold true. But if one makes the assumption that there is no case where it is cheaper to take two vehicles than it is to take only the second of those vehicles, one can simply subtract the transfer privilege from the fare the first vehicle in time (second reached by the algorithm) and still have an accurate fare. Fares would still need to be recalculated when creating GraphPaths from trips so that correct fares are displayed for each leg, but the total would be accurate.

Is there something I'm missing here?

[novalis]

It might be worth a try, but I think it's going to end up being slow and giving weird results. Why not just do unpreferred routes for BART?

[abyrd]

The deeper problem is that unlike shortest paths, fares do not have "optimal substructure", i.e. a prefix of an optimal combination is not necessarily itself optimal. Optimal substructure is necessary for effective use of greedy algorithms like Dijkstra's, which is not the right tool for the job.

A search algorithm which enumerates all reasonable paths (up to some degree of pruning) would be able to calculate fares for all of them and use the fare information when choosing the top N routes. It seems to me that RAPTOR would allow this.

One simpler solution would be to increase the transfer cost significantly (the default is quite low).

[mattwigway]

Building on @abyrd's comment, we could have an agency-agency matrix of transfer penalties, so that there was a low Muni->Muni (free transfer) penalty, a high Muni->BART penalty (expensive) and a medium BART->Muni penalty (discounted Muni fare).

[abyrd]

In OTP2 the transit router has been completely rewritten. It now produces a wide variety of results which are filtered down to ensure variety.