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.
Best Answer
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.