Return multiple pareto-optimal results

[JordenVerwer]

Right now, OTP returns only one result in long-distance mode. It would be more efficient if multiple pareto-optimal results can be returned, so several alternatives can be offered to the user without having to replan.

[abyrd]

In master, this functionality is now available -- if nPaths is set > 1 in GenericAStar, it will indeed return multiple paths, even if a timeout occurs before that full number of paths is found. It would be possible to simply set nPaths to a higher number in the OTPConfigurator when long distance mode is selected. However, the numItineraries in the routing request would then be ignored.

Further difficulties arise if we want to combine the retrying path service with returning multiple itineraries. If N paths are requested and the SPT service returns N-1 paths, the RetryingPathService that wraps it needs to retry; however the SPT service should not go looking for another N paths, but only 1. There are many different ways to communicate this fact: the retrying path service could change the request, if the SPT service is no longer a singleton the retrying path service can change the SPT service's parameters etc.

But perhaps the best solution is to stop using the retrying layer at all. Its sole function is to increase walk distances and ban routes arbitrarily, both of which regularly produce odd or incorrect results. Now that we have soft walk limiting and multiple-path return from the SPT maybe it can be eliminated.

That will leave us with options on different routes rather than different trips though, since we board only one trip on each pattern.

[bmander]

There's a problem with pareto optimal sets and very short trip plans. Like, imagine the best itinerary is to simply walk a block. The SPT gets there really quick, but there's really no competition. The trip planner remains hungry for a 2nd and 3rd option, so it continues exhausting the graph searching outward. Eventually it times out and returns the single best itinerary. So counterintuitively, a very very short trip plan takes $TIMEOUT to finish, but a longer trip returns more quickly.

Options:

• Set the timeout shorter for "nearer" trip plans.
• Abandon SPT growth beyond a certain multiplier of a path already found. For example, if a path was found with length 10, abandon SPT growth at 3*10=30 even though nPaths haven't been found.

[laurentg]

@bmander Shouldn't the following lines (GenericAStar.java,L278) cover this specific case? if (runState.foundPathWeight != null && runState.u.getWeight() > runState.foundPathWeight * OVERSEARCH_MULTIPLIER ) { break; } Basically it break the search if the last dequeued state weight is x times larger than the last found path weight. However, it could make more sense to compare with the weight of the best (ie first) result found, not the last one. (That is, to set foundPathWeight once only)

+1 for getting rid of the RetryingPathService.

[abyrd]

@laurentg now that we've worked with getting multiple results from the same tree, the case is even stronger for getting rid of the retrying path service. In fact, maybe we should even eliminate the idea of "path services" (or even "spt services") and move away from this semblance of pluggable modularity.

[t2gran]

This will be available in OTP2 when the multi-criteria Raptor search is fully operating.