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?