Reasonable Alternative Routes for MLD

[daniel-j-h]

Provide reasonably looking alternative routes (many, if possible) with reasonable query times (< 100ms) on MLD. The main use-cases are alternatives directly for the end-users but also for having alternatives in the context of traffic.

Notes:

• The task here is to find alternatives for a single metric. Once we have multi-metric it could make sense to return fastest, shortest, most efficient, .. routes (out of scope).
• We are also not doing the Penalty Method here (penalizing edges to simulate congestion) - it can be somewhat done via the traffic feature externally already (out of scope).

Resources

• Alternative Route Techniques
• Candidate Sets for Alternative Routes in Road Networks
• Algorithmen für Routenplanung: Alternativrouten (requires learning German first)

General Idea

Here's the general idea for the so called Via-Method for finding alternative routes.

• Start search from s and continue "for a while" when t was found. Save all vertices.
• Start search from t and continue "for a while" when s was found. Save all vertices.
• Intersect both vertex sets: these are the candidate vertices.
• For all candidate vertices c a (potentially arbitrarily bad) alternative route is (s, c, t).
• Make route request with candidate c as via: (s, c, t) .
• Apply heuristic to evaluate alternative route based on stretch, overlap, how reasonable it is.

Problem: the candidate set is huge; need to be pruned for reasonable candidates.

MLD Specific Pruning

The partition and the level structure we generate out of it can be used to shrink the candidate sets.

• Prune candidate vertices based on partition border vertices: all routes and therefore also alternative routes have to go through border vertices. Only consider (s, c, t) alternative routes where candidate c is a border vertex. *
• Add meta data to all border vertices * e.g. a flag if the vertex is on highway. Candidate vertices should be "important" in the road network to prevent unreasonable detours. Only consider (s, c, t) alternative routes where candidate c is on a highway.

* Let's assume at a fixed level for now. Later on we might want to descend.

Look out for

There are some constraints we need to operate with and ideas how we can make it work.

• We can only do maybe tens or (low) hundreds of route requests, otherwise we're already too slow. Pruning needs to be very good already.
• Try not to unpack routes (expensive). We have vertex locations and can use heuristics here. If exact distances are required do a forward and a backward search at the beginning (once) and store all distances.
• Filter out candidates c that are too close to s and t.
• Filter out candidates based on combined distance d(s,c) + d(c,t) < f(d(s,t))
• Special-case first and last cell for low range alternative routes. We can't prune based on border vertices there. Local search could be feasible here.

cc @MoKob @oxidase @TheMarex @danpat

[danpat]

requires learning German first

Can't we just require users to apt-get install lang-de or install via Mason?

[daniel-j-h]

Closing here - this landed with #4047.