Dear fellow programmers,
We're developing software which simulates vehicular traffic.
Part of the process called "assignment" is concerned with assigning vehicles to their routes and has to use some kind of shortest-path-finding algorithm.
Traditionally, people do this with Dijkstra's, and certain scientific literature seems to indicate that A* and other alternatives don't give any significant improvement, perhaps due to the nature of the graph.
Hence, we're using Dijkstra's as well. A small problem arose in that, if you treat traffic links (spans of roads between intersections) as edges and intersections as nodes, you can't get a classic uni-directional graph:
when approaching an intersection, where you can turn frequently depends on where you're coming from, whereas in a traditional graph you can take any edge from a node.
We resolved this problem quite easily by representing a link-intersection pair (call it "lath") as a node. Since you'd need to traverse a link to get to any subsequent "lath", or point of choice, an edge would then be defined as this traversal, and you get a typical graph.
The results then are stored in a simple table, N x N, where N is the number of "laths."
Here's the (unavoidable?) drawback. If a typical network for our simulation can have, say, 2000 intersections, it will have somewhere around 6000 links, i.e. N = 3V. Obviously, if counted in terms of intersections (V), we're now up to O(log(3V)*(3V + E)).
You might argue that 3 (or 9) is a constant factor, but from the practical standpoint, it does slow things down quite a bit, and increases storage space to 3V x 3V.
Does anyone have any idea how we can restructure this to improve performance?
Not necessarily any alternative algorithm, perhaps reshape the data structures to fit a graph in some other way?
Best Answer
Dijkstra's finds the shortest path between a given node and all other nodes, so I expect it would be more expensive than A*. However, it looks like you're trying to pre-compute the cost & path from any node to any other? Then Dijkstra's is the way to go.
As for a simpler representation, a few things come to mind:
At many intersections, you can come & leave any way you want. It's only a a subset that you have restrictions like "no left turn." So you could use the "laths" only for intersections where you actually need them. That should greatly reduce the size right there.
You could do this automatically by looking for "equivalent laths" and combining them. Two laths are equivalent if all the links coming out are the same. E.g. if "Intersection X coming from the West" and "Intersection X coming from the South" both lead to the same set of other nodes, with the same cost, then just merge them into a single node.
Are you sure you need/want to precompute the best path, instead of computing it online? Video games typically compute these things online.
Also, how are you representing the paths? In your matrix, you only need to represent the first link in the path. For example, to get from Bob's house to Bob's work, you only need to know the first link, since when they get there, you can now look in your matrix for how to get from the first link to Bob's work, which will give you the second link, etc.