Design OSRM Alternatives Ranking Strategy to Involve Live Traffic and Historical Speed

[wangyoucao577]

As we discussed in #63 (comment), the original idea comes from Refer to Project-OSRM#4449 (comment)

1. Make time-independent route requests potentially with the alternatives=n MLD parameter
2. Use the annotations feature for osm node ids, speed and weight on route segments for all routes
3. Make time-dependent query on the intersection of all segments, use weight for optimization

In our design, at the begginning, we can name it as Phase 1:

• In step 1, the calculation maybe based on pure time-independent data or data within blocking traffic(flows with speed near 0 and blocking incidents).
• In step 3, the time-dependent query mostly will start with calculate weight/duration with both live traffic and historical speed for each alternatived routes, then ranking them to pick up the best one or the best several as result.

We have to estimate whether the alternatives can returns good enough routes(the routes should not look similar but have significant differences).

Phase 2
In step 3, we may possible to construct a subgraph based on these alternatives since we can have all nodes,weights, then do Dijkstra on it to get better route. That's the better way mentioned in paper(https://arxiv.org/pdf/1606.06636.pdf) , and there're a lot of discussion in Project-OSRM#5503

[wangyoucao577]

Let's focus on Phase 1 in this issue.

There'll be another process in front of OSRM engine to handle the logic, we name it osrm-ranking for now.

[wangyoucao577]

design doc: https://github.com/Telenav/osrm-backend/blob/feature/design-osrm-ranking/docs/design/osrm-with-telenav-traffic.md#alternatives-ranking

[wangyoucao577]

PR for design doc has been merged, doc link: https://github.com/Telenav/osrm-backend/blob/master-telenav/docs/design/osrm-with-telenav-traffic.md#alternatives-ranking