entur / r5

Rapid Realistic Routing on Real-world and Reimagined networks
MIT License
2 stars 2 forks source link

Replace `maxDuration` test at each stop with a test against destination pareto set. #12

Open t2gran opened 5 years ago

t2gran commented 5 years ago

As soon as the destination is reached we can start to check agains the destination set of arrivals. If an arrival at a stop does not dominates at least one destination arrival, then we know that to stop arrival can be dropped.

This will have a very good effect on short trips since the majority number of stops is expected to be further away than the destination.

For long trips there might give a negative effect, but it is expected to be minimal since testing agains an empty set is very fast. For trips with few transfers, but extreme cost or duration, it will be costly - dependent of the implementation.

Implementation Notes

There is several ways to implement this:

  1. We can check every time we add an arrival to a stop state.
  2. We can check only when the arrival set at a stop is empty. A path exploration will not die as fast as in the first case, but it is likely to die just a couple of arrivals later anyway - because it will hit a state were it is not accepted or is empty -> compared with the destination again.
  3. In stead of comparing with the destination we can add accepted destination arrivals to all stops as fake arrivals. The fake arrivals has only one purpose - dominate obsolete real arrivals. The benefit of this is that existing arrivals are thrown away, when a new destination arrival is added. This will prune away arrivals happening in the same round as the destination arrival and also reduce the future set of arrival vectors to compare against. When merging two pareto set, elements from both sets is pruned off; hence less elements to compare with. The downside is the extra complexity and slightly higher memory consumption. By reducing the time window the temporary objects live in memory, we also increase trough put and overall memory consumption - so I do not worry about the memory temporary higher consumption.

The 3 alternatives should be tested agains the Norwegian and the Dutch graph to find the best method.

t2gran commented 5 years ago

This is implemented in the 1ecf8add and 5250f26b commits. The implementation is combined with a heuristic function calculating minimum travelTime and transfers to destination and using this to add to the current arrival before checking against the destination pareto set.