Timing inconsistencies in VrpPaths (for diversion)

[sebhoerl]

I'm currently porting the dispatcher from Alonso-Mora et al. to MATSim. When implementing the dispatcher, I noticed that some routing capabilities of dvrp provide inconsistent predictions of arrival times, even under strict free flow conditions and even when using the QSimFreeFlowTravelTime estimator. The code for the unit test can be found at https://github.com/matsim-org/matsim-libs/commit/3e4ad4a9f8829dec865dd5bd34af545215fb7deb.

The experiment in the unit test is as follows: I construct a very simple scenario with a straight line of 8 links with length 1000 m and an odd free flow speed, to make sure that the QSimFreeFlowTravelTime works properly and rounding does not have an influence. I then create one DVRP vehicle at L0 and add one task to the schedule, which makes it drive to L8. Every 10 seconds, I obtain the next diversion point for the vehicle from the OnlineDriveTaskTracker of the active drive task and perform an updated routing to the final link L8. During the simulation, I track the predicted arrival time when doing the initial routing, after every diversion routing, and I track the final arrival time from the events.

Ideally, all cases should produce the same arrival time, only then the predictions are correct. Currently, the following happens:

• Tracking the event-based arrival time gives an arrival time at 657s (reference value)
• The initial routing predicts an arrival time of 656s (wrong, too quick)
• At every diversion, the new routing gives an arrival time of 658s (wrong, too slow)
• Once the vehicle enters the final link, all remaining diversions give 657s (correct)

Findings for the time being:

• Different than stated in VrpPaths.createPath, it seems to take two seconds (one for "enter traffic", one for "leave link") to depart from an activity
• The change of prediction after diversion when entering the last link comes from the fallback in VrpPaths.createPath with considerZeroLengthPath == true
• The difference between the initial routing and the diversion routing comes from the fact that for the initial routing, VrpPaths.createPath considers the time to depart (rightfully so, but maybe faulty). However, when diverting, this buffer should not be considered as, there, the vehicle will just enter the next link fluently after traversing the current one.

Now, to fix the issue and get correct predictions:

• I think it would make sense to either add a boolean divertingPath argument in VrpPaths.* which disables the use of the initial slack for departing. Alternatively, we could have a set of VrpPaths.createPathForDiversion methods. This fixes the difference between the initial and diversion routing.
• For the standard case, I have the feeling that the VrpPaths.FIRST_LINK_TT should be 2s instead of 1s? But here I am not sure, maybe I am missing something in my experimental setup?

[sebhoerl]

Maybe even better would be an option VrpPaths.calcAndCreatePath(LinkTimePair diversionPoint, Link toLink, LeastCostPathCalculator router, TravelTime travelTime).

[sebhoerl]

The potential fixes are implemented in https://github.com/matsim-org/matsim-libs/commit/80a1e2471832e6c72c0a17486847a87cd036e5b0. However, theu invalidate some existing tests (but there 1 second was used arbitrarily it seems). It even "fixes" DefaultPassengerEngineTest where the predicted drop-off time needed to be corrected arbitrarily in the test. The -1 can now be removed and the test passes: https://github.com/matsim-org/matsim-libs/blob/d5e8fc8424aecf2438fe6009b686c9a0af7ea132/contribs/dvrp/src/test/java/org/matsim/contrib/dvrp/passenger/DefaultPassengerEngineTest.java#L95-L98

[sebhoerl]

And a third point in this series: Is VrpPaths.getLastLinkTT still an artifact from older versions of the class? Wouldn't it be more correct, to have

    public static double getLastLinkTT(Link lastLink, double time, TravelTime travelTime) {
        return travelTime.getLinkTravelTime(lastLink, time, null, null);
    }

Assuming that we are working with the QSimFreeFlowTravelTime here.

[sebhoerl]

And yet another issue :) I implemented another test, which goes from a link L0 along a chain of links to L8. And while I never divert, I calculate the diversion path to the next link L9. While traversing the links, most of the time we get the correct prediction of the theoretical arrival time at L9. However, once we are traversing L7, we get a wrong signal, because the diversion time from L8 is calculated wrongly. The problem here is that, currently, VrpPaths.createPath calculates the travel time of the last link as floor(length / speed), while for all other links it is this +1, because it is calculated that the vehicle needs to traverse the following node. This is not the case for the last link in the drive task, as the vehicle stops there. However, if we divert, we must take into account this missing second, because the diversion starts after passing the node. I will push the corresponding unit test and some fixes later on for that.

[sebhoerl]

Here is a little summary, some tests and potential fixes are to come.

Initial routing

       1         2         3
|**|--------*|--------*|--------|

• Here we have routed an initial route for the drive task from the end of Link 1 to end of Link 3.

• Total task time = FIRST_LINK + LINK 1 + Node + Link 2 + Node + Link 3

• Task end time = Departure time + FIRST_LINK + LINK 1 + Node + Link 2 + Node + Link 3

• Given a TravelTime that correctly replicates QSim dynamics, calculating the travel times is as follows:

  • The initial routing adds a timestep-based travel time for the first link (entering the vehicle etc.)
  • The initial routing removes one time step as the final node of the route is not passed (see no star after link 3)

1) For a diversion, we must not take into account FIRST_LINK as we have a smooth transition:

|**|--------*|--------*|--------|
             |--------*|--------|

• Here, diversion starts at the end of Link 2 and we perform a routing to the end of Link 3

• Diversion point = Departure time + FIRST_LINK + LINK 1 + Node

• Task end time = Diversion point + Link 2 + Node + Link 3

• The diversion routing does not contain the initial FIRST_Link time as before

• The diversion routing removes one second as the last nodes is not passed

2) Special case: Extending the route

                                   Added node here
|**|--------*|--------*|-------*|
                                |--------|

• In this case we are on link 2 and want to divert, we may divert from link 3, i.e. we will extend the route

• Diversion point = Departure time + FIRST_LINK + LINK 1 + Node + LINK 2 + Node + LINK 3 + Node

• Task end time = Diversion point + Link 4

• The diversion point is one time step after the planned task end time as we need to add one time step for passing the node that was ignored to far

Summary

• Routing from a diversion point is different than routing from a stay task (FIRST_LINK)

• The task end time is never a diversion point

• The diversion point is not the planned arrival time when extending a route, but one time step later

• Good nomenclature is needed when updating the code:

  • A Path travel time when calculated correctly according to QSim dynamics is the sum of link traversal times and a time step of passing the node at the end of each link. If we do not use QSimFreeSpeedTravelTime, we have an approximation thereof.
  • A drive Task duration is the path travel time (diverted or not) plus passing the first link, minus one time step for the final node that is not passed.

• In code, it might make sense to not talk about travel times at all, but work directly with departure/arrival times

[michalmac]

Thanks for looking into this issue and providing a detailed analysis!

I am aware that the current approach is not exact, it's more a compromise between accuracy (+/-1 s ) and complexity. Of course, making it "more" exact is good, however there are limits to it. A few examples:

• departing may take more than 1 seconds (if the queue buffer is occupied, even if QSimConfigGroup.insertingWaitingVehiclesBeforeDrivingVehicles is set to true)
• arriving at the last link may also take time (if the queue buffer is occupied and a preceding vehicle is blocked on entering the buffer)
• in a simulation with realistic traffic, estimates for all links (not only the first and last) are of limited accuracy
• moving along links with lanes will add additional seconds (for moving over "internal nodes") even in the free-flow case
• running a QSim with larger time steps (> 1 s) will also impact the accuracy (even in free flow; perhaps we should assume 1 full time step in QSimFreeSpeedTravelTime to model moving over a node)

IMO VrpPaths and QSimFreeSpeedTravelTime are already unnecessarily complicated. Here is another example which is too complex (given the purpose) and easy to get wrong: https://github.com/matsim-org/matsim-libs/blob/c3143a8658a64a194d13462dd24565374b6e0a2d/contribs/drt/src/main/java/org/matsim/contrib/drt/optimizer/insertion/SingleInsertionDetourPathCalculator.java#L142-L145

Therefore, I am thinking about going in a different direction. Instead of fully following the QSim implementation (incl. potential bugs or arbitrary decisions), maybe we should assume (and even implement?) a super simple, deterministic, (time-dependent) no-congestion model (e.g. 0 s for moving over nodes, 0 s for departing, no waiting at the buffer etc.) where we can obtain 100% exact estimates. Such a "reference model" could be used for traffic-free DVRP simulations where we need a very precise assessment. It would be also useful for unit/integration tests of VRP algorithms. At the same time, in real-traffic simulations (run with QSim), those 1-second errors are usually negligibly small compared to all other traffic-related approximations, so we would simply ignore them.

BTW. Simulating activities, such as charging, picking up, dropping off has also a limited accuracy (+/- 1 time step).

[michalmac]

This is how the referenced code section could look like if we simplify our assumptions

Path path = router.calcLeastCostPath(fromLink.getToNode(), toLink.getFromNode(), departureTime, null, null); 
double lastLinkTT = VrpPaths.getLastLinkTT(toLink, departureTime + path.travelTime); 

[michalmac]

BTW. A quite recent finding while working on #1741 related to the idea of simplifying the TT model in DVRP:

I ran our "old" Berlin DRT scenario with 6000 DRT buses and 270 000 requests, free-flow traffic (link capacities increased x100, so basically no congestion), rejections turned off.

It turned out that having restrictiveBeelineSpeedFactor set to 0.5 (i.e. travel times 2x longer then the free-speed times) gave better results than restrictiveBeelineSpeedFactor set to 1.0 (although the latter was the "right" one for a free-float scenario). Interestingly, "0.5" shortened the planning horizon (due to TWs) and led to a better workload distribution across vehicles, higher sharing rates and lower waiting times.

This showed that the choice and precise tuning of the cost function may have a much higher impact on the obtained results than the use of precise travel times.

[sebhoerl]

Nice list of caveats :) Yes, I think a benchmark simulator could be a good way forward (but also see my remark further below).

However, what is your take on this in the short term? I would like to fix VrpPaths such that in well-defined conditions, we can predict QSim 100%:

• with 1s time step
• with vehicles enter at the end of the link
• with infinite capacity
• with QSimFreeFlowTravelTime

This would allow me to set up some consistent test cases for porting the Alonso-Mora algorithm. Here, the timing is actually crucial if we don't want to have an extremely deteriorated service level under free flow conditions. Because the algorithm performs a re-matching of all vehicles and all request in every decision epoch, and the first assigned wait time is later on served as the wait time constraint for an agent (as if the service would communicate the expected arrival time to the customer and wants to stick to it). So we have the phenomenon that in one epoch a wait time of 05:00 is promised, and in the next epoch the exact same vehicle under free flow conditions is expected at 05:01 which will make the algorithm assign a new vehicle, and the whole logic cascades until a vehicle is close enough.

If I prepare a PR that covers the points above, do you see any obstacle for merging it?

[michalmac]

Sure, let's make a round with the 1-second issue fixes. However, in the long term we should think about some simplifications in this area. I think I agree with all your suggestions, but let's discuss them inside the PR.

BTW. Have you thought of making the solutions more stable, so the algorithm does not over-react to little changes in the ETA?

[sebhoerl]

Yes, this is what we were working on for TRB, basically making the algorithm more robust to fluctuations in travel time. This will also be ported.

[michalmac]

Awesome.