Article Application of an Evolutionary Optimization Technique to Rou...

I wonder if your question is this: how can I use added factors (traffic and such) -- and you are suspecting that Dijkstra is not going to be a good method. In fact Dijkstra has a well-deserved reputation as an outstanding algorithm (from a complexity point of view). So the right question should probably be: can I get Dijkstra to work with my data. And the answer is almost certainly yes. If you construct an index that has a property like distance or cost AND includes some added incentives or costs for traffic, I think you are going to be able to apply Dijkstra. Ask your question another way: is there an algorithm with better efficiency? I would have to say that I cannot think of another approach. Perhaps other data structures would help but the basic computational task is well studied.

If you have a many x many routing situation, you might look at Floyd Algorithm -- and again with the same reasoning you could modify the "cost" measure to reward the kinds of flows that you want to have.

• If you know any info about traffic conditions, you can plug it into Dijkstra by means of the costs of links. Costs do not necessarily mean distance, but any generalized cost (time, money, etc.,) hence you can find the quickest path, or the one with the lowest subjective cost, etc.
• A generalization of Dijkstra that yields results more quickly is A* (https://en.wikipedia.org/wiki/A*_search_algorithm) and its variations. Are you familiar with it? Basically you select your next link based not only in total cost from the origin, but also on an estimate of the remaining cost to the destination. The estimate has to fulfill certain conditions, but the algorithm is very good with 2D maps where you can compute euclidean distance to the destination
• A related but different problem is called assignment, where you need to assign routes to multiple trips from possibly more than one origin-destination pair in a network whose costs change depending on demand. For that I'd recommend the book Modelling Transport by Ortúzar and Willumsen (ISBN 0471861103)

I agree with Rafael's answer.

Another thought occurs to me: it may be that you are in fact interested in another (harder) problem where traffic equilibrates in view of the impact of traffic on travel time. (So an initially attractive route gets very busy and slows down, so some flows go other routes.) In fact "all or nothing" assignment according to the lowest generalized costs is the basic problem of Dijkstra. This is equivalent to assuming that the travel cost on the link (however you measure it) is a static element. When you allow an interdependence between travel time and flow, you have to use what's called a "user equilibrium" approach. This is a massive topic in transport models.

Thank you for your recommendations