0
$\begingroup$

I want to develop one algorithm which can predict shortest time to be taken to go to a destination from a source in a road network based on traffic congestion data. Consider that I have a server which gives me real time traffic congestion data for all the path segments in a road network. Now I want to develop such an algorithm which can predict time to be taken based on these data. So in short:

time_to_be_taken_from_source_to_destination = function ( traffic_congestion_data ). And 'time_to_be_taken_from_source_to_destination' is proportional to 'traffic_congestion_data' as time increases when traffic_congestion increases.

Are there any such algorithm alraedy developed? Any idea? reference to any algorithm or theory will be appreciated.

Improve this question
$\endgroup$
2
  • $\begingroup$ Yes, if you want one way traffic, Dijkstra, else other Ford Fulkerson Algorithm might be cool to look at. $\endgroup$ – Subhayan May 3 '14 at 8:49
  • $\begingroup$ Have you checked Wikipedia? Why do standard algorithms not solve your problem? $\endgroup$ – Raphael♦ May 4 '14 at 10:41
1
$\begingroup$

There is no special "algorithm theory" behind this.

You decomposed this data into a graph, right? You have intersection nodes, and you have edges with path difficulty (distance/average speed), yes? The congestion data simply modifies the average speed of the edge, so it's just A* business as usual. Regular shortest path heuristics will probably still be relevant for conservation purposes if you're lazy.

Obviously a prominent example of an implementation of this would be https://maps.google.com/.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Why use a heuristic? There are good exact algorithms for shortest paths. (The reference to Google is completely superfluous on this site.) $\endgroup$ – Raphael♦ May 4 '14 at 10:41
  • $\begingroup$ Heuristics are used to optimize pathfinding algorithms to prevent tree expansions into the wrong direction. Here's a short intro: theory.stanford.edu/~amitp/GameProgramming/Heuristics.html $\endgroup$ – guest May 5 '14 at 10:10

Not the answer you're looking for? Browse other questions tagged or ask your own question.