1. Introduction.

Fluid-dynamical methodologies

to traffic flow have been established since the 1950’s ii. Recently, the

methods of nonlinear dynamics were successfully applied to these models, highlighting

the notion of a phase transition from laminar flow to start-stop-waves with

increasing car density 2. Automatic detection of stronger fluctuations near

this critical point has already been used to install better traffic control

systems in Germany 3.

On

the other hand, boolean stimulation models for freeway traffic have been

developed 4, 5. For lattice gas automata, it is well known that boolean

models can simulate fluids 6. We illustrate that indeed our boolean model for

traffic flow has a shift from laminar to turbulent behavior, and our simulation

results show that the system reaches a possibly critical state by itself in a

bottleneck situation (aware of self-organizing criticality 7). This point together

with an extension to multi-lane traffic will be the subject of further

investigations 12.

The

outline of this paper is as follows: At the beginning, we describe our model

(para 2) and discuss its phenomenological behavior, especially the transition

(para 3). In para 4 results for the bottleneck situation are presented. Para 5

contains a discussion of the results and compares them to values in reality.

Para 6 and 7 give a short conclusion/ outlook.

2. The model.

Our computational model is

defined on a one-dimensional array of L sites and with open or periodic

boundary conditions. Each site may either be occupied by one vehicle, or it may

be empty. Each vehicle has an integer velocity with values between zero and

vmax. For an arbitrary configuration, one update of the system consists of the

following four consecutive steps, which are performed in parallel for all

vehicles:

a.

Acceleration: if

the velocity v of a vehicle is lower than vmax and if the distance to the next car ahead is larger

than v + 1, the speed is advanced by

one v ? v +1.

b.

Slowing

down (due to other cars): if a vehicle at site I sees the next vehicle at site i + j (with j ? v), it reduces its speed to j – 1 v ? j – 1.

c.

Randomization:

with probability p, the velocity of each vehicle (if greater than zero) is decreased by one v? v – 1.

d.

Car

motion: each vehicle is advanced v sites.

Through

the steps one to four very general properties of single lane traffic are modeled

on the basis of integer valued probabilistic cellular automaton rules 9, 10.

Already this simple model indicates nontrivial and realistic behavior. Step 3

is essential in simulating realistic traffic flow since otherwise the dynamics

is completely deterministic. It takes into account natural velocity

fluctuations due to human behavior or due to varying external conditions.

Without this randomness, every initial configuration of vehicles and

corresponding velocities reaches very quickly a stationary pattern which is

shifted backwards (i.e. opposite the vehicle motion) one site per time step.

The

Monte Carlo simulations have mainly been carried out with the choice of vmax = 5 for reasons stated below.

The model has been applied in FORTRAN, using a logical array for placing of the

cars and an integer array for velocities. For ‘realistic case’ of vmax

= 5 we made following observations: in the interesting regime of a relatively

low density of occupied sites (usually only about one fifth), an implementation

using IF-statements has been about five times faster than an implementation

using only boolean variables and operations (necessary for multispin coding for

32 cars at once). As the expected gain of multispin coding would consequently

give only a factor of about six, we adjourned the work on a bitwise

implementation.

The

speed on an IBM-RS/6000 320H workstation was about 0.2 site-updates per microsecond,

which is about a factor of 7 slower than the speed of a non-vectorized,

multispin coding Ising model 11. A significant part of the Monte-Carlo

simulation have been carried out on an iPSC-860 Hypercube using up to 16 nodes,

with only trivial changes of the program. The model’s speed on one processor of

the Hypercube was almost same as on workstation.

3. Traffic on a circle

(closed system).

In this para we present

results from systems with periodic boundary conditions (thus simulating traffic

in a closed loop “as in car races” but only on a single lane). As the

total number N of cars in the circle cannot change during the dynamics, it is

possible to define a constant system density.

P = N/L= number of cars in

circle/ number of sites of circle (1)

A

CELLULAR AUTOMATON MODEL FOR FREEWAY TRAFFIC

which is usually not

possible in reality. Thus, in order to simulate real conditions, we measured densities

(= occupancies) ?-T on

a fixed site I averaged over a time period T:

t0+T

?-T= 1/T ? ni(t) (2)

t =

t0+1

where ni (t) = 0(1)

if site i

is empty (occupied) at time step t. For large T we have

lim

?-T = ?

(3)

T??

The time-averaged flow q-

between i and i + I is defined by

t0+T

q-T = 1/T ? ni, i + 1(t) (4)

t =

t0+1

where ni, i + 1(t) =

1 if a car motion is detected between sites i and i + I.

With these definitions, it

was easy to perform many simulations applying diverse densities ?, thus after

relaxation to equilibrium acquiring data for the frequently used fundamental diagrams

which draw vehicle flow q- vs

density p-.

To be precise, we started with a random

initial configuration of cars with density p and velocity 0 and started gathering

of the data after first to time steps, where we took t0= 10 x L. In

figures I and 2 we depicted distinctive conditions at low and high densities.

Whereas we got laminar traffic at low densities, there are congestion clusters

(small jams) at higher densities, which are established randomly due to

velocity-differences of the cars. If one follows (in Fig. 2) one car coming

from the left, one sees that the car comes in with a speed varying between four

and five and then has to stop due to the congestion cluster. There it stays jammed

in the queue for a certain time with some slow advances, and can accelerate to

max speed after leaving the cluster at its end. So the cluster signifies a

typical start-stop-wave as found in freeway traffic (cf. Fig. 3).

We

present this diagram of our model in figure 4. Where the line shows the results

of averaging over 106 time steps, the dots represent averages over

only 102 time steps and may be matched with results from real data

(Fig. 5). It can undoubtedly be seen that a change-over takes place near ? =

0.08. Further replications show that the position and the form of the maximum

of q(p) rest on the system size. (Simulations without randomization do not show

a dependence on the system size.) However, it is not clear from these diagrams where

to find an precise transition point.

For an analytical treatment of the circular

traffic, one chooses as starting point the case Vmax = I, where the

situation simplifies considerably. Here step one of the four update steps is trivial

since every car can accelerate in only one time step to its maximum speed Vmax

= I and therefore, before step two, every car has speed I. The question in the

update procedure then is simply if the next site is free (step two) and if the

speed is (randomly) set to zero (step three).

For speeds larger than 1 an additional

parameter for the current speed is needed which gives serious difficulties for

analytical treatments. However, even in this case a kind of mean-field approximation

is possible and the results will be reported elsewhere 12.

For direct calculations the easiest way to

formulate the dynamics is on the basis of a master equation with continuous

time and random sequential update. This makes of course a difference to the

parallel updating (which can simply be seen by simulating the two different

updates) but the results should be qualitatively similar and the randomization

parameter p plays a particular simple role for random sequential update.

With

the use of the more familiar spin variables ?i = ± 1 with +1 for

occupied and -1 for

empty

sites, the transition probability W(-?i, – ?i+1/ ?i,

?i+1

) from (-a ?i,

?i+1,) t0

(-?i,

-?i+1) (i.e. a car moves from I to i + 1) simply reads

W ((-?i, –

?i+1/ ?i, ?i+1) = (I-P) 1+ ?i/2

(5)

With

periodic boundary conditions this transition probability ensures the

conservation of the total magnetization ?i?i in the

system. The master equation for the probability P((?j),t) to find configuration (?j) at time

t is given by

dP({?j})/dt = – ?

w (-?i, – ?i+1/ ?i, ?i+1) P ({?i, ?i+1, t}

+? w (?i,

?i +1/ (-?i, – ?i +1)

P({-?i, – ?i

+1, t}) (6)

From

this formula it can easily be seen that the factor I p) only gives a simple

scaling factor of the time axis. Therefore, in continuous time, the systems

with different p < I are equivalent in the sense that they have the same
equilibrium distribution. Analyzing this equilibrium distribution one finds
that, given a fixed total magnetization, every configuration of the spin is
equally probable. Therefore, in this simple situation, one has
q =
p (1 - p) (7)
which
is just the probablity that a car has a free site in front of it. The property
that every
configuration
of the cars is equally probable is certainly not true for Vmax >

0. The parallel update gives a different function q(p) but it is also symmetric

with respect to

p

= 1/2 12.

4. Traffic

in a bottleneck situation (Open system).

For

this section, we apply different boundary conditions, leaving the rest of the

model unchanged:

a.

When the leftmost site (site I) is empty, we

occupy it with a car of velocity 0. As our traffic is going from left to right,

one may imagine a bottleneck situation where a saturated twc-lane-street feeds

a street of only one lane (which we simulate).

b.

At the right side (I.e. the end of the

street), we simply delete cars on the rightmost six sites, thus producing an

open boundary. (This simulates the beginning of an expanded (four-lane) freeway).

Our

simulations included grid length up to 10000 sites with durations up to 5 x 106

time

steps.

After relaxation, the model shows traffic at a density of

= 0.069 ± 0.002 and a flow of

Again

the situation here simplifies considerably for Vmax = I. The case of

random sequential update is exactly equivalent to an asymmetric exclusion model

investigated in detail in references 13, 14 where the equilibrium

distribution in a system with open boundaries is calculated. The case ? = ? = 1

(in the notation of Refs. 13, 14) corresponds then to our bottleneck

situation. It can be seen that in this simple case the system drives itself to

the state of maximum flow at ? = 1/2. However this seems not to be a general

property also valid for larger Vmax > 1 (cf. Fig. 6).

5. Quantitative

comparison with realistic traffic.

In

this section, we make some rough arguments concerning the length scale and time

scale of the simulation model. The easiest approach to scale the model is the

claim that in a complete jam each car occupies about 7.5m of place, which is

thus the length of one site. As the average velocity in free traffic of 4.5

sites per time step should correspond to a velocity of about 120 km/h (in

Germany), we arrive naturally at a time for one iteration of

7.5 m/site

x 4.5 sites/ time-step/ (120/3.6)

s/m (8)

?

(1 second per time-step) which agrees with 5.

A

second possibility is to scale the model by the position of the maximum in the

fundamental diagram. From traffic measurements, this maximum is found at about

p r- (30 vehicles per lane and kilometer) = (0.225 vehicles/7.5 m), which is by

a factor of about 2 higher than the position of the maximum in the scatterplot

for our model.

Similarly,

freeways have a maximum capacity of about (2000 vehicles per hour and lane) =

(0.56 vehicles per second). As our maximum of the flow is only 0.32 vehicles

per time step, our model time step should cot-respond to 0.32/0.56 m 0.5

seconds, thus being by a factor of two lower from the value presented above.

A fourth possibility uses the value

of the velocity of the back-travelling start-stop-waves, where a value of about

15 km/h ? 4.2 m/s has been measured on freeways. As the maximum capacity of our

simulated system is about 0.3 cars per time step, the maximum speed of the back

propagating wave is 0.3 sites (? 2.25 m) per time step (i.e., about every third

time step a new car arrives at the back of the traffic jam). This would fix one

model time step at 2.25/4.2 ? 0.7 seconds, thus yielding a value between those

of the first and of the third method. Thus all these estimates agree in order

of magnitude: time steps correspond to seconds.

Another interesting result of the last

argument is that start-stop-waves might intrinsically be a queueing phenomenon

where only the formation takes place dynamically: once a congestion cluster of

length L has formed, there is a probability parr per time step that

a new car arrives at the end, and a probability pdep per time step

(determined in a nontrivial way by the dynamics of the model) that a car

departs at the front of the jam (cluster). As pdep at one cluster

dictates parr for the next cluster, all clusters act like queues at

the critical threshold where parr = pdep. But the

formation of the flusters as well as the self-organization of the critical

value of parr take place without external control.

One should note that, contrarily to intuition,

the parameters for a discrete traffic flow model are relatively fixed once one

accepts “one car per lattice site in a jam”. The parameters used for

the simulations seem relatively reasonable.

6. Conclusion.

It has been shown that a discrete model approach

for traffic flow is not only computationally advantageous 5, 4, but that it

contains some of the important aspects of the fluid-dynamical approach to

traffic flow such as the transition from laminar to start-stop-traffic in a

natural way (see particularly the end of the last section). Thereby, it retains

more elements of individual (though statistical) behavior of the driver, which might

lead to better usefulness for traffic simulations where individual behavior is

concerned (e.g. dynamic routing).

An additional interesting observation is that

sand falling down in a long and narrow tube shows very similar behavior, i.e.

“start-stop-waves” originally caused by fluctuations in the velocity

of the freely moving particles. In the case of sand these fluctuations are due

to dissipation at the boundary 15.

References

1 LIGHTHILL M-J-, WHITHAM

G-B-, Proc. R. Soc. Lond. A229 (1955) 317.

2 KUHNE R., in: Highway

Capacity and Level of Service, U. Brannolte Ed., Proc. Int. Symp.

Highway Capacity, Karlsruhe (Rotterdam:

Balkema, 1991).

3 ZACKOR H., KUHNE R., BALZ

W., Forschung Straflenbau und Straflenverkehrstechnik 524

(1988), (Bundesanstalt fur Straflenwesen,

Bonn-Bad Godesberg).

4 CREMER M., LUDWIG J.,

Mathematics and Computers in Simulation 28 (1986) 297.

5 SCHOTT H., Schriflenieihe

der AG Automatisierungstechnik TU Hamburg-Harburg 6 (1991).

6 FRISCH U., HASSLACHER B.,

POMEAU Y., Phys. Rev. Lent. 56 (1986) 1505.

7 BAK P., TANG C.,

WIESENFELD K., Phys. Rev. A 38 (1988) 368.

8 NAGEL K., Proc. Phys.

Comp. ’92 Conf., Praha (Singapore: World Scientific, 1992).

9 WOLFRAM S., Theory and

Applications of Cellular Automata (Singapore: World Scientific,

1986).

10 STAUFFER D., J. Phys. A:

Math Gen. 24 (1991) 909.

11 KOHRING G-A-, STAUFFER

D., Int. J. Mod. Phys. C (October 1992).

12 NAGEL K., SCHRECKENBERG,

M., in preparation.

13 DERRIDA B., DOMANY E.,

MUKAMEL D., J. Stat. Phys. 69 (November 1992).

14 DERRIDA B., EVANS M.R.,

preprint 1992.

Is HERRMANN H.J., personal

communication.

16 TREITERER J., TR PB 246

094 (Columbus, Ohio State University, 1975).

17 HALL FL., BRIAN L.A., GUNTER

M.A., Transpn. Res. A 20A (1986) 3, 197.