Is there any better approach to shortest path finding within a (vehicular) traffic network?

Question

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?

Answer 1

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.

Answer 2

You have large graph and you made it even larger. Martinc C. Martin advised using lathes only when needed, so i will not go into this.

One of things that could help you, is tranform your graph into smaller graphs.

First simplification that helped me a lot (I worked with road networks of europian states) was "removing" nodes with digree 1 and 2 recursively. This way you have no dead end roads, and T intersections (originally degree 3) becomes degree 2 and that is not interesting, if you are not pathing to that node or node in that removed cull de sac.

After that, you can try to divide your graph into parts that have large ammount of internal nodes and edges, but have minimal connection with other parts. To find them, I used minimal cut where sink and source were as far from each other (in edges) from each other and edges near them had huge capacity and edges somewhere in between had small.