Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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?

share|improve this question
    
I'm not clear what N and V are. Is V the number of vertices (intersections) and N the number of arcs between vertices? Also, what is E? –  Mike Dunlavey Aug 22 '12 at 21:09
    
What resources did you read? IIRC, A* is proven to find the optimal path in the least amount of time given a pessimistic heuristic. In fact, A* regresses into Dijkstra with an empty/0 heuristic. –  Steve Evers Aug 22 '12 at 21:39
    
Also, what graph representation are you using? Unidirectional graphs with adjacency lists would easily permit roads as edges/intersections as nodes (actually, even an adjacency matrix would, but it'd obviously have to be a full matrix instead of upper/lower triangular). TBH: I'd suggest a lot of game programming literature, it's a highly worked problem in that field and has the same ore more stringent performance restraints as you're mentioning. –  Steve Evers Aug 22 '12 at 21:48
1  
@SnOrfus: yes, but you can't always represent a single intersection as a single node, for example of an intersection allows you to turn left or go straight but not turn right, the simple adjacency matrix would not be able to represent that (worse if you have a roundabout). –  Lie Ryan Aug 23 '12 at 4:01
    
@LieRyan: Maybe I'm misunderstanding you but that's no different from an intersection where there is no right turn and should be represented in the same way. –  Steve Evers Aug 23 '12 at 14:27

1 Answer 1

up vote 6 down vote accepted

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.

share|improve this answer
    
Combining "laths" is indeed an interesting idea. You're right, we're finding shortest path between every node pair and then generating paths. In a typical traffic simulation, hardly any roads never get used (why would there even be a road there in the first place, right?). When you say "online," do you mean in real time? All we really can do is compute "expected" shortest paths, since we don't really know exactly what the conditions are going to be on some link when the vehicle actually gets there. We update the shortest path matrix based on current conditions. –  Greg Kramida Aug 23 '12 at 14:23
    
Yes, by "online," I mean in real time, i.e. when Bob leaves his house and wants to go to work, do the A* then. –  Martin C. Martin Aug 23 '12 at 14:45
    
Depending on how often the shortest path matrix needs to be updated, you may do a lot of work for the update, and not end up using most cells before doing the update again. I don't know the details of your use case, but from the outside, it seems A* is at least worth trying. Also, while all N nodes are used at some point, that doesn't mean that all N^2 pairs will be used at some point. The people on Bob's block, how many unique destinations do they have? –  Martin C. Martin Aug 23 '12 at 14:51
    
Yeah, I concur, A* is probably worth trying. For some simulations, we're routing some fraction of vehicles at each origin to almost all destinations, but by far not in every case. I found a few papers on people using various heuristics w/ A* specifically for traffic networks, I'm going to try these out. Thanks for your help, Martin. –  Greg Kramida Aug 23 '12 at 15:38

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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