Closed t2gran closed 5 years ago
A simple test of this uses a reverse, no-wait search to calculate min (transfers, time, and cost) and then uses these three to create an optimistic estimate for the destination arrival in the multi-criteria search.
For my 27 test cases searching from 0800 and 12 hour window the search time go down from 3000 ms to 900 ms - the reverse search uses on average 160 ms. With a 4 hour time window the search window only improve from 560ms to 500ms. The reverse search took 160 ms.
Implemented using a heuristic calculation and limit by by testing if the arrival qualify at the destination. See commit 1ecf8add and 5250f26b.
Provide a limit on cost. There is several ways to do this:
maxLimit
by calculatingmaxLimit = a * minCost + b
. Thea
andb
are constants passed in as parameters. TheminCost
is the is the best cost found at the destination - dynamiclly updated when new destinations arrivals are found.delta
constant that is used in every stop for comparing cost. For every pareto compare operation the new cost must be better than an existing value by adelta
to be added to the set.So let say we use walkingDistance as cost. An arrival at a given stop arrive with 500 meters walking. Then later a new arrival arrive with 490 meters walking. The later arrival is pareto optimal if delta is 0 (<10) and not optimal (rejected) if delta is > 10.The first alternative prune of the rim of the search, while the second start pruning on every stop.
In principle these optimizations can be applied to other criteria as well.