Rock Street, San Francisco

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.

We Will Write a Custom Essay Specifically
For You For Only \$13.90/page!

order now

On
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

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 = 0.304 ± 0.001.

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,

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.

Posted on / Categories Papers