Is there an algorithm for solving a gridlock (traffic jam)? Given a gridlock situation, this algorithm should tell which moves each car should make, and in which order the cars should move, so that the congestion is eliminated and the cars can go in the direction they intended to.

I have googled 'traffic jam solve algorithm', but I've found results about preventing jams (not solving jams once they occurred), or results about mathematical modelling of the traffic jams (or mining other kind of data from a traffic jam) - which is not what I'm looking for.

So far, the 'sliding blocks' game/puzzle seems to me to be a simpler version of the traffic jam problem (some variants of the game are even called Rush Hour), but it seems that this kind of problem is PSPACE-complete (which is even harder than NP-complete), according to http://groups.csail.mit.edu/mac/users/bob/sliding-blocks.pdf

So, is there at least some approximate algorithm to do this?

By traffic jam I do not mean a situation where the traffic is going on very slowly, but otherwise is still going on, but a situation where cars are actually blocked by other cars, and cannot move forward, or backwords. actually, only a few cars can move at a time - just like in the block sliding problem. See this picture for example.

  • $\begingroup$ Could you specify the traffic jam situation more precisely? For instance, are the variables for how many lanes and how many vehicles there are in each lane? $\endgroup$ – J W May 4 '15 at 11:41
  • $\begingroup$ well, for the sake of simplicity, let's not bother yet about the number of lanes, nor the number of cars coming from behind on each lane. The picture that i had in mind was an aerial overview of an intersection crowded with cars, and i would expect the algorithm to tell which car to move first, and how, and so on. Basically, if you regard cars as rectangles, what I'm asking is a solution ( or at least some research) to the sliding blocks game $\endgroup$ – Petre Luca May 4 '15 at 12:22
  • 1
    $\begingroup$ Are you thinking more of a gridlock situation? $\endgroup$ – J W May 4 '15 at 13:57
  • $\begingroup$ you are right!! gridlock describes perfectly what i mean. i didn't knew this term, that's why i used the term 'traffic jam'. i will edit the post right now $\endgroup$ – Petre Luca May 4 '15 at 14:41
  • $\begingroup$ traffic lights and/or roundabouts? $\endgroup$ – JMP Jun 23 '15 at 1:14

Modelling traffic flow is a huge mathematical field. There are many different approaches to this problem. There are continuous models like LWR-Model, car-following theory etc. however since you are looking for an algorithm you may be interested in stochastic traffic cellular automata!

However, until now I have only worked with cellular automata modelling on a single lane. For example, a traffic jam forming behind a traffic light, and its behaviour when the light turns green. Maybe this paper is of interest.

  • $\begingroup$ thanks for the answer! i will search for the models you've told me about. sorry i can't upvote yet - i don't have enough reputation :( $\endgroup$ – Petre Luca May 4 '15 at 12:18
  • $\begingroup$ you are welcome! :) I hope you find something interesting. if you like, I can send you my bachelor thesis on the matter. take an upvote - problem solved ;) $\endgroup$ – the.polo May 4 '15 at 12:31
  • $\begingroup$ See also Algorithm to solve traffic jam on MSE and Traffic Flow with Cellular Automata. $\endgroup$ – J W May 4 '15 at 14:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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