I have a graph extracted from an American city: vertices represent road intersections, edges/arcs represent road segments connecting the intersections. For each road segment, I have the length and allowed driving speed. Furthermore, roads belong to different classes such as highway/residential/primary roads/....

I am looking for a routing algorithm which does the following:

  • Compute a pairwise travel time matrix for each intersection (i.e how long it would take to travel from intersection i to intersection j.
  • Query the quickest route from intersection i to j and returns a path (sequence of edges/arcs). The algorithm should be able to take updates into consideration. For instance, if there is a congestion on road segment (x,y) which increases its anticipated travel time, or if road segment (x,y) becomes blocked, the data structures should be updated incrementally, thereby updating all affected shortest paths (i.e. update all shortest paths through (x,y)).
  • The distance matrix will be queried very often so this should be precomputed, but the actual shortest paths can be computed at a later stage if that's more efficient. The number of nodes in the graph is roughly 5000-10000.

I was hoping that people could refer me to literature about this, preferably something that doesn't take weeks to implement. Obviously, simply running Dijkstra for each intersection takes too long. Running Floyd–Warshall all-pairs shortest path algorithm could be a possibility, but I'm not so sure how to update the result if the cost of one of the edges/arcs changes. Furthermore, it seems to be a slow approach since the algorithm ignores that most of the routes go through a small subset of the road segments.

I'm not looking for an exact approach. A good approximation suffices. Any pointers to literature or algorithm descriptions are welcome. I presume that any kind of routing software needs a similar algorithm. I'm mainly interested in something that works; it shouldn't necessarily be state of the art. I'm not sure what would be a good place to ask this question?

asked 18 Aug '15, 04:32

JorisK's gravatar image

JorisK
26445
accept rate: 0%

closed 19 Aug '15, 12:52

SK53's gravatar image

SK53 ♦
22.3k46228350

1

I'm not sure what would be a good place to ask this question?

Since I cannot find any immediate connection to OpenStreetMap in your question (maybe you just forgot to mention it?), may I suggest to try on gis.stackexchange.com instead and close this question?

OSM universe offers different routers like OSRM or GraphHopper. Please give the search on this page a try.

(18 Aug '15, 17:46) mmd

The question has been closed for the following reason "Question is off-topic or not relevant. Generic question with no OSM content, more suitable for GIS StackExchange." by SK53 19 Aug '15, 12:52

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported

Question tags:

×249
×13

question asked: 18 Aug '15, 04:32

question was seen: 1,794 times

last updated: 19 Aug '15, 12:52

powered by OSQA