IT鈥橲 FRIDAY evening, and you鈥檙e about to head out of the city. But the traffic news tells you that there鈥檚 a jam on your normal route. Is it worth taking an alternative? And how far out of your way do you need to go to avoid the snarl-up?
If you lived in Duisburg in Germany, you need never wrestle with this kind of dilemma. Instead, you could plan your journey using an up-to-the-minute map of traffic flow for the entire city.
These maps are constructed from data taken by vehicle detectors dispersed throughout the city鈥檚 streets. But there is no way that the entire city could be staked out this way. Data recorded at a few key points provide the input to a real-time on-line computer simulation of the traffic flow, pegging the model to reality. This system, developed by Michael Schreckenberg and his colleagues at the University of Duisburg, is now being used by several other cities in Germany, and a similar traffic project developed at Los Alamos National Labs in New Mexico is being applied to cities such as Dallas for urban traffic planning.
Advertisement
The technique of combining simulations with actual traffic data is made possible by the realization that traffic flow has its own brand of physical laws, which can be captured in simple computer models. Some of these are now a standard part of the lore of traffic planning; but others are only just being discovered. The ability to understand and predict traffic flow promises to help road planners discover the best design for their highway networks and to reveal the choice of speed restrictions and traffic calming measures that will keep vehicles flowing fast and trouble-free.
Mystery hold-up
The behaviour of traffic is notoriously unpredictable. How many times, for instance, have you inched your way forward in congested traffic, only to find no obvious cause of the hold-up once the jam starts to clear? You imagined an accident, road works, fog, or at least some explanation for why it just took you half an hour to travel a kilometre or two. But there鈥檚 nothing.
This is an example of a spontaneous jam, and it happens when traffic density rises above a certain threshold. When the density is low, you can do pretty much what you want: crawl along at 30 kilometres an hour, risk all at 150, change lanes to pass lorries, and so on. Traffic engineers call this 鈥渇ree flow鈥�. But increase the amount of traffic and the flow becomes unstable. Small fluctuations in speed caused by someone braking a little too hard, for instance, can become amplified downstream as drivers overcompensate for the slowing up ahead. The flow can even 鈥渇reeze鈥� locally, sending waves of stopped traffic sweeping along the motorway like shock waves in a fluid (快猫短视频, 25 June 1994, p 36). Eventually, as the traffic density increases, everything grinds to a halt.
Modelling this kind of complex behaviour has proved difficult. Some of the earliest models of traffic flow, such as those developed by James Lighthill and Gerald Whitham at Manchester University in the 1950s, treat traffic as a fluid flowing down a pipe. The main problem with these models is that the individuality of different vehicles is lost鈥攋ust as fluid dynamics ignores the tribulations of each molecule of liquid鈥攕o fluid models can鈥檛 always predict real traffic flow.
In an attempt to make the models more realistic, some now incorporate a 鈥渕icroscopic鈥� element that acknowledges the behaviour of each vehicle. These treat traffic passing down a highway as a special kind of grainy flow鈥攁 stream of discrete particles, such as cereal grain falling through a hopper. This type of flow is now known to behave in a way that can be quite different from that of a fluid in a pipe: in particular, the particles can move in a collective fashion, as if by some mysterious mutual agreement. They attempt to attain a certain 鈥渄esired speed鈥� throughout, and may experience ghostly 鈥減ressures鈥� that mimic the tendency of drivers to anticipate and overcompensate for events downstream.
Modellers who take this approach try to imagine the simplest instincts that a driver exhibits, and then add these rules to the computer model. They are 鈥渓ocal鈥� rules鈥攅ach driver can see and respond to only what happens in the immediate vicinity. So no prescription for collective behaviour鈥攕uch as a line of vehicles all moving at the same speed鈥攊s fed into the model. Instead, such behaviour manifests itself as an 鈥渆mergent鈥� property鈥攁 kind of spontaneous organisation, like the coordinated behaviour seen in ant colonies.
Models of many-particle processes in which each individual behaves in a way that is determined by the antics of its neighbours are called cellular automata: each particle moves about like a pre-programmed automaton on a checkerboard lattice of cells (快猫短视频, 29 August 1998, p 36). In 1992, Kai Nagel at the University of Cologne proposed a cellular-automaton model to describe traffic flow. In collaboration with Schreckenberg, Nagel developed this model into a prototype that has been the basis of almost all subsequent attempts to model traffic as a granular flow, including the simulation of Duisburg鈥檚 roads, which has been online since August last year.
This simulation uses detector units fixed at the roadside to feed car numbers into the cellular automaton program. This divides each lane of every main road in the city into a series of blocks a few metres in length, and the vehicles advance by moving from block to block. Each vehicle has an effective length which reflects the minimum amount of space drivers leave between each other. The drivers all have a preferred speed, towards which they will accelerate if space permits, but they will also slow down, if necessary, to avoid collisions. There are also rules for lane changing that take into account the speed of the vehicle ahead and the available space.
Since each vehicle affects all its neighbours, the behaviour of the group is highly nonlinear: a small perturbation in the flow might be amplified as its influence gets passed from one vehicle to the next. In this way, the Nagel-Schreckenberg model seems to be able to predict accurately the transition from free flow to jams.
Eyes on the road
But exactly how real traffic behaves in between these two extremes is a little more mysterious. In 1996, Boris Kerner and Hubert Rehborn at the Daimler-Benz research laboratories (now called DaimlerChrysler) in Stuttgart, Germany, reported observations of traffic flow that provided new insights into how jams form.
Kerner and Rehborn used a fluid-like model to analyse the flow on a section of the A5-South highway past Frankfurt, between Giessen and Basle in Switzerland. A 24-kilometre section of the three-lane highway was fitted with 24 banks of speed detectors, providing continual measurements of vehicle velocity and density.
The researchers found that in addition to free and jammed flow, there was a third kind of flow鈥攕ynchronised flow鈥攊n which the vehicles in all three lanes move at more or less the same speed. They claim that synchronised flow appears above a certain density of traffic鈥攁bout 20 vehicles per kilometre in single-lane traffic鈥攁nd it corresponds to a lower average speed than free flow. Because all the lanes move in similar fashion, overtaking is not easy in synchronised flow and rarely happens. Yet although it might be frustrating for drivers, their model reveals that synchronised flow is actually quite efficient at shifting cars: the high traffic density makes up for the slow speed, so that the throughput in cars per minute remains comparable to that of free flow.
It is not hard to spot when you are in synchronised flow, since everyone around you is moving at the same moderate speed. But if you notice this happening, expect trouble鈥攖he flow is potentially unstable. Although small perturbations, such as a driver slowing unexpectedly, might have no untoward consequences, larger perturbations鈥攁 lorry crawling uphill, for instance鈥攃an trigger a jam. Technically speaking, synchronised flow is 鈥渕etastable鈥�: only provisionally stable, and liable to freezing. Kerner had observed something like this metastable state in simulations of traffic flow using cellular automata before conducting the real-life observations鈥攚hich seemed to vindicate this prediction.
On the edge
At still higher traffic density, both observations of real traffic flow and the model show that the flow becomes unstable. In this state, all disturbances, no matter how small, will cause a jam.
Traffic engineers liken these three flow states to the states of matter. Free flow is like a gas: the density is low, and each 鈥減article鈥� is more or less free to wander, hardly interacting with others. Jams are like a solid: the density is high, and the particles are all but immobile. Synchronised flow is like the liquid state, with a moderately high density but retaining some mobility. And, as Kerner and Rehborn discovered, the transitions from one traffic flow state to another are abrupt, just like melting and evaporation.
But this analogy remains a loose one since traffic states, unlike the states of matter, are out of equilibrium鈥攖here is net flow of 鈥減articles鈥� in a certain direction. It may be more apt to regard synchronised flow as a supercooled liquid鈥攐ne that has been cooled below its freezing point, so there is a permanent risk of it suddenly solidifying. In supercooled liquids, this happens only if some fluctuation in density produces a solid nucleus around which the rest can solidify. If the nucleus is too small, it will disperse again, just as a small perturbation in synchronised flow can be washed away without nucleating a jam.
Kerner and Rehborn claim that it is rare to find traffic switching from free flow directly to a jam. Instead, synchronised flow is generally observed as an intermediate state, just as a gas usually condenses to a liquid before freezing solid. This probably accords with our everyday experience of driving on motorways, but it overturns much earlier thinking about traffic flow, which had considered only jammed and free states.
The researchers argue that transitions between these three states can occur spontaneously in traffic that contains identical vehicles, as the density changes. But not everyone is convinced.
Dirk Helbing, a physicist at the University of Stuttgart, says that it is extremely difficult to prove that synchronised flow appears in the absence of 鈥渋nhomogeneities鈥�, such as shallow inclines, bends in the road or even an accident in the opposite lane. These disturbances act like particles of dust in a supercooled liquid, providing sites around which nucleation of the solid can occur. Helbing believes that it remains to be seen whether synchronised flow is indeed an intrinsic feature of traffic on an open road, rather than something imposed by external disturbances.
Certainly, it becomes most common around entry and exit lanes on motorways, or at bottlenecks where lanes converge. 鈥淭he synchronised state exists, there is no question,鈥� says Schreckenberg. 鈥淏ut the mechanism for the transition from free to synchronised flow is still under debate.鈥�
Working with Bernardo Huberman of Xerox in Palo Alto, Helbing has recently found a type of behaviour that looks much like synchronised flow in a variant of the Nagel-Schreckenberg model. They call this behaviour coherent flow, in which all of the vehicles move as if in a solid block with almost no changes of lane or of distance between vehicles. Crucially, in contrast to synchronised flow, coherent flow seems to require that the traffic itself is heterogeneous. The computer model studied by Helbing and Huberman contained a mixture of cars and lorries, which differed in their preferred speeds.
Helbing says that 鈥渃oherent flow arises because at a certain traffic density the space on the highway is all used up鈥攖here are no gaps for lane changing and thus for overtaking鈥�. As a result, he says, the cars have to go at the same speed as the trucks. They have even observed this kind of motion, over a small density range, in real traffic on Dutch highways, occurring when cars are forced to 鈥渃rystallise鈥� around slower-moving lorries.
But even this simple picture of three flow modes isn鈥檛 quite sufficient, says Helbing. With co-workers Ansgar Hennecke and Martin Treiber at Stuttgart, he recently used a model that has more in common with the older 鈥渇luid鈥� models to identify at least three other traffic states.
The researchers considered how a bottleneck at an entry ramp onto a motorway affects the flow as the volume of traffic both on the motorway and the entry ramp changes. From free flow at low traffic volume, the traffic first developed a dense cluster of vehicles. This miniature jam either stayed 鈥減inned鈥� to the bottleneck region or moved upstream, receding from the entry ramp against the direction of traffic flow.
Heavy traffic
As the traffic density increased further, various new modes appeared. These are characterised by a series of density waves that become more frequent as the roads fill up. These congested modes, says Helbing, might be akin to the synchronised flow of Kerner and Rehborn.
These models may represent the future of traffic prediction. In the US, for instance, Nagel and a team at Los Alamos National Labs have used cellular automata to design their Transportation Analysis and Simulation System. This system can track traffic in a large city over a 24-hour period, and has already been used to plan road layouts in Dallas. And Schreckenberg鈥檚 group now aims to extend the Duisburg system to encompass the whole Autobahn network in North-Rhine Westfalia, in the hope of being able to provide hourly traffic forecasts. What鈥檚 more, such studies should help create both better road networks and more efficient driving regulations.
The work of Helbing and Huberman, for example, suggests that American-style lane rules, where drivers can travel at any speed in any lane rather than having designated fast and slow channels, make more efficient use of the road than European rules and can reduce the average travel time. They say that because lorries stay mainly in the slow lane in Europe, other drivers tend to avoid that lane, so the highway鈥檚 capacity is effectively reduced by up to 25 per cent.
And although it is frustrating for the drivers, coherent or synchronised traffic flow is actually safer than the alternatives because it reduces the main causes of highway accidents: differences in speed and lane changes. It also produces close to the maximum throughput of vehicles. So Helbing and Huberman have proposed that traffic rules and road controls should be designed to promote the transition to a coherent state. 鈥淭raffic policy in Germany is shaped by the automobile industry and other big companies,鈥� Helbing says. 鈥淪iemens is planning to implement some of our ideas, and Volkswagen is strongly interested.鈥�
Knowing that things like junctions are liable to trigger the transition from synchronised to jammed traffic, however, should alert traffic controllers to the need for restrictions at these points that will reduce fluctuations in speed. Helbing points out that most of the forms of jam seen in his models occur while the traffic volume does not actually exceed the road鈥檚 capacity, and so should be avoidable.
He says that jams around bottlenecks can be dissolved in the models by assuming the drivers pay more attention to the surrounding traffic, driving more closely but with a better response time. Drivers should be capable of this heightened concentration for limited periods of time, he says, if they know it is in their favour. Alternatively, he suggests that cars could be fitted with 鈥渟mart鈥� autopilots that use radar to respond to the vehicles nearby more sensitively than human drivers.
These improvements are not just about making life easier for drivers, or even about reducing accidents. Congestion also has an environmental cost鈥攍onger journeys mean more pollution. Schreckenberg plans to include an exhaust emission simulation into his real-time traffic model, so that he can calculate the environmental impact of vehicle flow directly. And with transport ministers admitting to the inevitability of 鈥渃haos on the roads鈥� in the future, making journeys more efficient has never seemed more urgent.