GraphPath.optimize incorrect

[novalis]

changes in r1346 make GraphPath.optimize give strange departure times and transfer times.

disabling optimize yields normal results.

[novalis]

This is caused by two things:

1. StateDate.resetForReverseOptimization() does not reset the lastAlightedTime.
2. Initial boarding slack should not be applied in alight edges during path optimization. The additional time offset will cause the last transit leg to be missed, and each successive leg will be shifted back in time.

Initial boarding slack is difficult to handle in arrive-by searches (and therefore path reverse-optimization), because we can't easily know when we've reached the first boarding.

The best solution I can think of is to have a per-board/alight event schedule slack parameter. This much wait time is inserted at each board or alight independent of whether this is a depart-after or arrive-by search. This way there will be 2 minutes of slack for the first board, 2+2 minutes of slack for each transfer, and 2 minutes at the last alight. Time is then proportional to the number of vehicles involved in the board/transfer, and is located in exactly the same places in the path, whether the search is arrive-by or depart-after.

--andrewbyrd

[novalis]

Fixed in r1347. Part 2 temporarily fixed by not applying initial board slack at all.

Ticket left open pending decision on / implementation of the symmetric board/alight slack solution mentioned above.

Path optimization needs to be rewritten anyway when working on ticket #399 (Eliminate SPTVertex/SPTEdge).

--andrewbyrd

[novalis]

In an arrive-by trip, isn't initial boarding slack replaced by final alighting slack?

--novalis

[novalis]

I tried and decided against this way. When the resulting arrive-by path is reversed, you will then get some extra slack at the end of the trip and none at the beginning. An arrive-by trip needs slack at both ends because the user has two time constraints: arriving at the destination and catching the first vehicle.

But the real problem is that path optimization uses traverseBack. If depart-after paths have no slack inserted at the last alight on the forward pass, then optimization does insert slack (because on the backward pass, the final alight edge is the first one encountered) the original last transit leg will be missed, completely messing up the itinerary (this was the reason for this ticket).

Because the slack is not directly visible (in the web interface), it doesn't really matter if it is applied at the board or alight end of a transfer between two vehicles, thus my suggestion of applying the same amount at every board and alight.

--andrewbyrd

[novalis]

Oh, now I see. I was confused by the term "slack". Let's do symmetrical slack.

--novalis

[novalis]

Did this ever get implemented?

--novalis

[novalis]

Yes, in r1494. But I left the name of the parameter "minTransferTime" rather than change the API. Would you be in favor of renaming this something like scheduleSlack? It doesn't work like the min transfer times specified in the transfer table.

--andrewbyrd

[novalis]

Actually, it looks like the transfer table is not used at all now, which is not good. TriMet has an obsession with transfer.txt and really wants to make sure that OTP uses it.

The current code does not handle the case of timed transfers, or min transfer times that are higher than the min transfer time in options.

I think that (Pattern)Alight (for forward trips) should, instead of advancing the clock, instead update an additional state field called something like lastBoarding. That field would be current time. Then, (Pattern)Board would have three cases:

(1) no entry in transfers.txt: advance the clock until lastBoarding + options.minTransferTime, then look for a transfer (2) timed transfer in transfers.txt: ignore boardingBlockedUntil and just get on the next available trip (3) min transfer time in transfers.txt: if this is greater than options.minTransfertime, advance the clock to lastBoarding + the value in transfers.txt, else, as per (1).

How does this handle optimization? Well, when you go through in reverse, you get the same blocking times, meaning the same set of trips is available. I think.

Does this make any sense?

--novalis

[novalis]

The tables are in fact being used, but in preboard/prealight instead of (pattern)board and (pattern)alight. It is true that some timed transfers would not work with the current implementation.

We discussed this some more on IRC. Here is a summary of the discussion:

Question: Why is it bad to insert that time at boarding rather than at alighting? Meaning, at boarding while going forwards and at alighting while going backwards.

Discussion: It's not bad if you only search one direction. But when you re-traverse those same edges backward, starting from the arrival time determined from the forward search, you cannot re-board the same trip you took forward. Adding minTransferTime to the final state before back-optimizing should make it work out right.

Conclusion: We are just going to add minTransferTime to the final state before back-optimizing the path.

Question: For timed transfers, do we not even take walking time into account? Because that means potentially letting time run backward.

Discussion: Timed transfers are usually at a single stop, but we need to ask agencies / on transit-developers to see how they're used in practice. Timed transfers could be free edges from station1_arrive to station2_depart, bypassing walking and preboard edges. They would then be artificially cheap since you don't have to walk between them, but the point of timed transfers is thet they are artificially cheap. Also, it is pretty much impossible to have a timed transfer where the busses are not at the same physical place, because the drivers need to actually see that the passengers have made their transfer. So it is coherent if they are almost free.

Question: So we are switching back to the idea of having different initial and transfer 'schedule slack'? Two parameters? Because the other reason for the "symmetric slack" thing was making it proportional to the number of vehicles involved in the board event.

Discussion: Initial slack should just be half of (default) transfer slack, since in the case of a transfer, the arriving bus can be late and the departing bus early. So schedule tolerance is specified for transfers (over and above walking time), and initial boarding schedule tolerance is 1/2 transfer schedule tolerance. All of this can be increased via transfers.txt. When traversing backwards, we need to look up the transfer times backwards too, because transfer time from A to B is not necessarily the same as transfer time from B to A.

--andrewbyrd

[novalis]

Re: Why is it bad to insert all the time at boarding? I just remembered why I had opted for cutting the min transfer time in half and applying it at both board and alight. It has to do with A* heuristics. For any (off-vehicle) vertices A and B, the lower bound on weight from A to B and from B to A is usually almost the same, but board cost and transfer time can interfere with that. By making those components the same in both directions, it is possible to represent all your lower bounds on weight with an undirected graph, which is a discrete metric space (having a commutative notion of distance), which is then potentially embeddable into euclidean space, which means O(N)-size weight tables. I don't know if that will perform any better than ALT without trying it. Incidentally ALT doesn't care whether distances are symmetric, because the triangle inequality holds even in quasimetric spaces (whose norm is not commutative).

So anyway, that's experimental and there's no reason to bend OTP to that requirement for the moment. It's also perfectly viable to only cut the board cost in half, and not include min transfer time in the heuristic at all.

--andrewbyrd

[novalis]

done in r1531 still need to check whether it works right on CH searches

--andrewbyrd

[novalis]

Fabian Viger says on transit-developers: "In reality, timed transfers certainly exist, even farther than a block: the suburban bus that takes me home from the train station is pretty much always waiting for the train; up to a 10min delay or so; and the bus stop is a good 7 to 8 min walk from the train platform."

This implies that representing a timed transfer as a free edge might fail to give useful turn-by-turn walking directions.

On the other hand, the bus departure is probably actually scheduled to depart at the train's arrival time plus eight minutes. So, there would be no need to run time backwards here. We just need to ignore any ordinary slack, as timed transfers might be scheduled to ignore slack.

--novalis

[novalis]

Just checked, timed transfers would already work as described above.

If a transfer time is found in the table, it is added to the previous alight time. The time found this way is compared to the on-foot arrival time at the departure stop, and the later one is used. This also applies to transfer times of 0 found in the table, which are timed transfers. When transfers are found in the table, minTransferTime is not used at all.

If no transfer time is found in the table, minTransferTime is added to the arrival time at the current stop, which takes inter-station walk time into account.

So transfer times from the table completely override the (default) minimum transfer time.

--andrewbyrd

[novalis]

Looks like we still have a bug -- see Nirmal's post on the mailing list for a test case. The problem seems to be that slack is not applied in PreAlightEdge when traversing it forwards -- and similarly for PreBoardEdge in reverse.

For a forward search, we want to give a conservative time at the destination, meaning that we expect that the trip might arrive a few minutes (that is, one slack) late. The only exception to this is if a timed transfer is coming up, which assumes that the arriving vehicle will be on time. But really, since we want to be conservative, we should assume that the arriving vehicle will be late and thus the departure will be a few minute late. So really, if we have a timed transfer, we should just set a flag in State which permits us to reach a few minutes back in time when looking for the trip, but then advances the trip to make time not run backwards.

Does this make any sense?

--novalis

[abyrd]

The latest manifestation of this bug (reported by Nirmal) was triggered by not providing a date/time in the request. The problem was that the fractional part of the millisecond-precision system time propagated forward all the way to the end of the search. During reverse-optimization, that fractional part was truncated when searching for an arrival time in PatternAlight.traverse, causing trips to be missed by less than one second.

I have made the State constructor truncate fractional seconds, which should avoid the missed trips.

This bug points out an implementation detail we are likely to encounter again in future bugs: we store time at millisecond precision, but timetables and many other things at 1-second precision. I will implement timed (synchronized) transfers as edges, then hopefully we can close this issue.

[novalis]

Can we just not use millisecond precision?

On Sat, 2011-07-30 at 05:40 -0700, andrewbyrd wrote:

The latest manifestation of this bug (reported by Nirmal) was triggered by not providing a date/time in the request. The problem was that the fractional part of the millisecond-precision system time propagated forward all the way to the end of the search. During reverse-optimization, that fractional part was truncated when searching for an arrival time in PatternAlight.traverse, causing trips to be missed by less than one second.

I have made the State constructor truncate fractional seconds, which should avoid the missed trips.

This bug points out an implementation detail we are likely to encounter again in future bugs: we store time at millisecond precision, but timetables and many other things at 1-second precision. I will implement timed (synchronized) transfers as edges, then hopefully we can close this issue.

[abyrd]

Sure, it would be simpler. I thought of suggesting it, but figured there must have been an intentional decision to use milliseconds. I'll switch everything over unless we notice a good reason not to.

[novalis]

The history is that Java's date functions all take milliseconds, and we used to use them during the searches. We no longer do, so it's OK to switch. I would like to switch the API (if it uses milliseconds, which I now can't remember) , but we should wait to do that until we have API versioning.