search

Project-OSRM / osrm-backend

Open Source Routing Machine - C++ backend
http://map.project-osrm.org
BSD 2-Clause "Simplified" License
6.29k stars 3.32k forks source link

Time-dependent routing #4449

Closed emiltin closed 1 month ago

emiltin commented 7 years ago

We would like to use our bike app to guide cyclist from A to B in the fastest and most convenient way. Avoiding stops at red light is an important factor. There are several possible strategies:

  1. Avoid intersection with traffic ligths. However, this can make the route longer, and crossing streets with a lot of traffic can be slow if there's no traffic ligtht.

  2. Provide real-time speed advice based on real-time data from the traffic lights combined with GPS from the device. Suggesting a slower speed will make the travel time longer, but can increase the comfort. Suggesting a faster speed can save significant travel time, if it means you make it through the current green cycle.

  3. Recompute the route dynamically based on real-time data about when traffic lights are predicted to change between red and green.

Is it possible to use OSRM for strategy 3? It doesn't yet handle time-based data, but it does support updating weights based on e.g. travel times.

daniel-j-h commented 7 years ago

If you really want to incorporate changing traffic lights into the route calculation you should give the new MLD pipeline a try. It's built specifically to allow for amazingly fast traffic updates:

https://github.com/Project-OSRM/osrm-backend/wiki/Traffic

osrm-extract berlin.osm.pbf
osrm-partition berlin.osrm
osrm-customize berlin.osrm
osrm-routed --algorithm=MLD berlin.osrm

You need to adapt the pipeline here with how the wiki updates speeds and weights; the wiki is still on the old CH pipeline. Then you can run osrm-extract and osrm-partition once and re-run osrm-customize as fast as possible with an up-to-date file.

Without accurate speeds (read: only using the OSM data with the profiles) youre routes are probably inaccurate enough such that you won't see much benefit in incorporating red/green traffic lights. Historic and/or real-time traffic data helps immensely there.

emiltin commented 7 years ago

Thank you for the tips. Yes, I agree it would make most sense if we already use real-world travel times to adjust weights. The time it takes to cross roads without intersections can also be also quite significant compared to red lights.

emiltin commented 7 years ago

Updating weight according to current state of traffic lights is not enough. The route computation needs to take into account when a particular traffic light is reached, otherwise a route might be suggested that passes a traffic light that is green the moment the route is computed, but red when you actually reach it.

The problem is similar to gates or ways that are open at particular times, and probably also to time-tables on public transport. Probably not possible with the current algorithms in OSRM?

I'm renaming this issue to more broadly support time-dependent routing, with use-cases such as:

daniel-j-h commented 7 years ago

Okay if you want to do full time-dependent routing then here's a great accessible paper for a heuristic you might want to use for time-dependent routing: https://arxiv.org/abs/1606.06636

emiltin commented 7 years ago

Thank you, interesting paper.

emiltin commented 7 years ago

For the traffic light problem, the approach in the paper could be used to compute a number of future time windows based on predicted traffic light states. But a problem would be that the cycle times of intersection are not the same, meaning that the overall system is not cyclical, as it is with hours in the day. Combined with the fact that time windows would have to be small (since cycle times of intersections are typically 50-100 seconds), you would need a large number of time windows. On the other hand, traffic light predictions can only be made for a few minutes into the future for intersections that has varying cycle times due to bus priority, etc.

MichalPP commented 7 years ago

do you want to emit instructions like "speedup to 22km/h to catch the ferry" or "slowdown to 10km/h, you are going to stand at red light anyway"? that would be nice...

emiltin commented 7 years ago

yes we do want to do that in the front-end. but including that in the route computation might further complicate things.

daniel-j-h commented 7 years ago

For the record @emiltin you can already implement the paper mentioned above on top of OSRM:

Interested in what you will find out!

holgerlewin commented 6 years ago

I have a similar use-case where I want to use real-world speed data that comes in 15min daytime slots. I would like to annotate the segments with speed data and set the edge weight dynamically during routing using the time of day at the current node in the current path. Does this sound reasonable or is this approach too different from how OSRM works?

daniel-j-h commented 6 years ago

You can't set weights dynamically during routing - both the CH as well as the MLD pipeline do pre-processing. What you can do is either change your speeds and weights every 15 minutes

https://github.com/Project-OSRM/osrm-backend/wiki/Traffic

but then long distance routes much longer than your 15 minutes will not respect "current" traffic. To solve this you can use the approach in the paper linked above and described in https://github.com/Project-OSRM/osrm-backend/issues/4449#issuecomment-327477669.

holgerlewin commented 6 years ago

I would have to go with the 2nd option, since there is not only the 'long distance routing' problem, but also is the time of day a parameter of the query. Thanks anyway for the quick response.

chnlior commented 5 years ago

Any progress on the dynamic traffic update? My use case requires planning many routes in many arbitrary future time slots. As I understand changing the traffic update.csv requires processing so it is not practical to change for every request. Is it possible to load many update.csv files for many time slots in advance?

danpat commented 5 years ago

@chnlior No - OSRM does not support this, and there are no concrete plans to implement it.

There are a couple of academic papers that outline possible approaches to extend OSRM's CH algorithm to support time-dependent queries:

http://algo2.iti.kit.edu/documents/routeplanning/tch_alenex09.pdf https://algo2.iti.kit.edu/download/sea10_atch.pdf http://drops.dagstuhl.de/opus/volltexte/2017/7897/pdf/OASIcs-ATMOS-2017-3.pdf

but the implementations here are quite complex (weeks or months of work most likely).

chnlior commented 5 years ago

@danpat, many thanks for the prompt answer and thanks for this great project.

Out of curiosity I still wonder if this is not planned because of resources issues or because there is no much demand for such feature. As traffic is timely-dependent (in rush hours travel-time can be easily X2-3 ), what use-case can a static traffic file support?

daniel-j-h commented 5 years ago

@chnlior happy to review pull requests if you want to give it a try. The tl;dr is

HTH, Daniel J H

chnlior commented 5 years ago

@daniel-j-h, Thanks for your help.

wangyoucao577 commented 5 years ago

For the record @emiltin you can already implement the paper mentioned above on top of OSRM:

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

Interested in what you will find out!

@daniel-j-h I can understand the first two phases. But how to implement the "Make time-dependent query on the intersection of all segments, use weight for optimization"?
I think we need a same graph, then query on subgraph which restricted by segments generated by the first two phases, right? It's better to have OSRM support such "restrict to generate subgraph" stuff, otherwise we have to construct the graph by ourselves, but it's not easy to get same rules from speed to weight. Apply dynamic speed into the query on subgraph should not be difficult since the subgraph will very small. But I think query dnyamic speed on the fly during query still will be better than customize into subgraph in this use case.

ghost commented 5 years ago

For the record @emiltin you can already implement the paper mentioned above on top of OSRM:

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

Interested in what you will find out!

@daniel-j-h I can understand the first two phases. But how to implement the "Make time-dependent query on the intersection of all segments, use weight for optimization"? I think we need a same graph, then query on subgraph which restricted by segments generated by the first two phases, right? It's better to have OSRM support such "restrict to generate subgraph" stuff, otherwise we have to construct the graph by ourselves, but it's not easy to get same rules from speed to weight. Apply dynamic speed into the query on subgraph should not be difficult since the subgraph will very small. But I think query dnyamic speed on the fly during query still will be better than customize into subgraph in this use case.

1)I might be completely wrong here but to keep things simple how about keeping one osrm instance for each time slot rather thank making another sub graph. i.e if there are 4 time slots then we have one main osrm instance with no traffic information . and then 4 more OSRM instances where we feed in traffic information. at query time we can get shortest path from main instance and then query time specific slots for same waypoints .

ghost commented 5 years ago

this might not be perfect place to ask but lets say if i am just interested in calculating approximate time for trip time . then combining osrm with https://www.kaggle.com/c/new-york-city-taxi-fare-prediction/kernels like machine learning regression models any good? anyone has any experience on this?

nurgasemetey commented 4 years ago

@chansbest https://github.com/melmasri/traveltimeHMM could help you, implementation based on one Microsoft research paper.

github-actions[bot] commented 2 months ago

This issue seems to be stale. It will be closed in 30 days if no further activity occurs.