 |
|
ISSN 1320-0682 | ||||
| Volume 3 | April 1996 | ||||
Mathew Mitchell & Bohdan Durnota
...Mitchell
Faculty of Computing and Information Technology, Monash University, PO Box
278, Caulfield East 3145, AUSTRALIA
...Durnota
Faculty of Computing and Information Technology, Monash University, PO Box
278, Caulfield East 3145, AUSTRALIA
Email:matt@insect.sd.monash.edu.au & bdurnota@fcit.monash.edu.au
Although there has been interest in one-dimensional models of traffic flow, there has only relatively recently been an increased interest in two-dimensional CA models. These models have not taken into account sophisticated routing behaviour as vehicles move from origins to destinations. In this paper, we develop a two- dimensional cellular automaton (CA) as a simple model of traffic flow in two dimensions which includes adaptive route-changing behaviour. In this model, sites are either occupied by a vehicle or are empty. Vehicles have an associated origin and destination site on the lattice, and tend to move towards their destinations. The number of vehicles is kept constant. As a vehicle reaches its destination, a new vehicle with a random origin and destination is created. Updating of the CA occurs asynchronously. We show some results of a number of initial experiments which indicate the dynamics of traffic flow in this model under different car densities. Not only global, but also individual-based trip-related statistics are investigated.
Work on cellular automaton simulations of traffic has dealt primarily with one-dimensional models [9], [7]. These models have been found to capture features of real traffic flows and have revealed complexity in even relatively simple traffic flow models including the presence of 1/f noise [8]. Following this CA approach to traffic simulation, [1] developed a two-dimensional model of traffic flow. The model consisted of traffic moving in two directions - up and to the left - at varying densities. A form of traffic light was implemented by allowing vehicles in each direction to move at alternating times. Several variations of the model were trialled. The first was a deterministic model with an initial random configuration where vehicles move to new sites unless they are blocked by other vehicles, in which case they remain at a site unchanged. Nondeterministic variations on the model were also trialled where vehicles all moved in the same timestep. If in a single timestep, two vehicles attempted to move to the same site, one was selected to move probabilistically. A final variation allowed two vehicles to both occupy the same site if they moved to it in the same timestep. Both the deterministic and nondeterministic models demonstrated a phase transition from vehicles moving from maximum velocity to a jammed phase.
In a subsequent model developed by [2], vehicles could move in four directions, with the ability to change direction probabilistically depending on the direction of the street. Once again, jamming behaviour was observed.
The ability of vehicles to turn was further examined by [6]. In this case, blocked vehicles would turn with a certain probability, or remain blocked. In this model it was found that a jam-avoiding turn can affect the development of jamming behaviour.
The model proposed here is a variation on previous models with traffic moving adaptively from origin to destination sites. The model is described, and then results are presented from this initial analysis of the observed behaviour.
The traffic model is a two-dimensional cellular automaton (CA) based on a square lattice with periodic boundary conditions. There are a fixed number of vehicles on the lattice at all times. Only one vehicle at most can occupy a given site (an exclusion process). At any timestep, a vehicle can move at most to one of its 4 neighbouring sites. Updating of the CA occurs "asynchronously" - at each timestep, each vehicle is chosen without replacement to be updated. We note that the method of updating the lattice at each timestep can have a profound effect on the dynamics of a system. For example, in models of spatial games there are significant differences in models which utilise synchronous updating [11] from those which utilise asynchronous updating [10].
We have adopted a well-mixed model of vehicle generation, one which broadly reflects the use of trip distribution data used by transportation planners [4]. Vehicles are associated with given origin-destination sites. They are "born" at their origin site, and travel towards their destination site, whereupon they "die". Each "dead" vehicle is immediately replaced by a new vehicle, and so there is always a constant number of vehicles present in the world.
A random model is used to generate a new vehicle's origin-destination pair. The origin pair is selected uniformly at random to be any site on the lattice. If, however, there is a vehicle already present at the chosen origin, then a new origin is generated. The destination site is similarly generated, with the condition that it is not allowed to be the same as the origin site.
Whenever possible, vehicles will move towards their destinations at all times, going to a neighbouring site which is closest to the destination. Thus, a myopic (greedy) approach is taken to vehicle movement. Consider an arbitrary vehicle. All nonblocked neighbouring sites are examined. For each of these sites a distance to the vehicle's destination is evaluated. Then, a site with a minimal distance is selected as the next site to which the vehicle moves. If all neighbouring sites are blocked, then the vehicle does not move. The distance metric used is the sum of the absolute x and y distances.
One of the implications of this routing mechanism is that whenever there is a neighbouring vacancy, a vehicle will always move, even if that means that in the short run it moves further away from its destination.
A number of statistics are used to assess the dynamics and performance of the traffic system. These cover both system-wide aspects as well as individual vehicle performance. The global observables that are collected at each timestep include:
Also, over some final time segment of a simulation, a number of cluster- related statistics are also collected:
By a cluster we mean a maximally-connected set of vehicles and by a jam we mean a maximally-connected set of blocked vehicles. Connectedness is given in terms of being adjacent to any of a site's 4 nearest neighbours.
Each time a vehicle completes its journey, the following statistics are computed:
We also can compute the congestion time (time the vehicle is blocked), and the relative congestion time (congestion time / time to travel from origin to destination).
The model was implemented in the [12] multi-agent simulation system [5], [3]. A typical display of the evolving lattice is shown in Figure (1). In this display, there are 1250 vehicles on a 50 x 50 grid. The red circles indicate a blocked vehicle. The arrows indicate the direction from where a vehicle has come.
Figure 1: A typical car configuration
A set of simulations was conducted to obtain indications of the type of dynamics which evolves in the model. A 50 x 50 periodic lattice was used, and three different car densities, p were chosen:
Each of 60 simulations was run for 10,000 timesteps.
Average velocities and a number of cluster distributions were collected from the simulation runs, and are summarised in the next section.
Since a vehicle can move, at most, a distance of one site at any given time, the average velocity for all vehicles in the lattice (number of moving vehicles / total number of vehicles) must lie between 0 (all vehicles blocked) and 1 (all vehicles moving). Figure (2) shows how average velocity changes over time for the three vehicle densities considered. We observe that for low densities (p = 0.2), we basically have free-flowing vehicles. However, as the density increases, the effects of blocking become more pronounced, and average velocities decrease significantly over time.
Figure 2: Time evolution of the global average velocity
Over time, the size of the largest cluster and the largest jam were collected. For each density, we normalise the size of each cluster to lie from 0 up to 1 by dividing by the constant number of vehicles present on the lattice. The time evolution of the size of the largest cluster is shown in Figure (3), with the normalised size shown on a log-scale. Not surprisingly, we observe that for low densities (p = 0.2), there are only very small clusters. By contrast, for higher densities (p = 0.5, p = 0.8), we see that the largest cluster size gets close to saturation at 1. Indeed, we see that for p = 0.5 there is a rapid increase in the size of the largest cluster from the beginning, until it finally asymptotes.
Figure 3: Time evolution of the size of the largest cluster
In terms of the number of clusters present in the lattice, Figure (4) (sampled from the last 2,000 timesteps of each simulation run) in log-log form, not surprisingly shows that there are many more small-sized clusters than larger ones. An interesting observation is the presence of the discontinuity in the distribution between small and quite large clusters for the higher densities (p = 0.5, p = 0.8). It is clear how this occurs when viewing how a simulation evolves. Once a large cluster develops, nearly the only clustering phenomenon occurring is the evaporation and aggregation of very small (say 1 or 2 vehicle) clusters from/to the boundary of the large cluster.
Figure 4: The distribution of cluster sizes
If we ask the question of in what size cluster an arbitrary vehicle is likely to fall, we obtain Figure (5), again sampled from the last 2,000 timesteps of each simulation run, and in log-log form. This refines the picture given in Figure (3). For the higher densities, we see the relatively high probability of being in a large cluster.
Figure 5: Probability of vehicle being in a given sized cluster
We now turn our attention to the dynamics and structure of clusters of blocked vehicles, the jams. The time evolution of the size of the largest jam is shown in Figure (6), with the normalised size shown on a log-scale. For low densities (p = 0.2), there are only very small jams, whilst for higher densities (p = 0.5, p = 0.8), there is a rapid increase in the size of jams until they get to relatively high levels. Obviously, the size of the largest jam is always somewhat below the size of the largest cluster, as presented earlier.
Figure 6: Time evolution of the size of the largest jam
The distribution of the number of jams present in the lattice is somewhat smoother than that for clusters, and is shown in Figure (7) (sampled from the last 2,000 timesteps of each simulation run), in log-log form. Not surprisingly, it shows that there are by far many more small-sized clusters than larger ones. We again observe the bimodal nature of the distribution as the density increases.
Figure 7: The distribution of jam sizes
If we look at the distribution of what size jam in which a jammed vehicle is likely to fall, we obtain Figure (8), again sampled from the last 2,000 timesteps of each simulation run, and in log-log form. For the higher densities we see the relatively high probability of being in a large jam.
Figure 8: Probability of a jammed vehicle being in a given
sized jam
A further cluster type of interest are clusters of moving vehicles - see Figure (9). As expected, these are comparatively small, and indicate the amount of movement within the lattice during the last 2000 timesteps of the model. The graphs show that a density of p = 0.5 has relatively larger moving clusters than the density p = 0.8. This is due to the greater degree of free traffic movement observed with the smaller densities.
Figure 9: Probability of a moving vehicle being in a given
sized moving cluster
Individual-based statistics have also been computed, and relate to the performance of a trip by an arbitrary individual vehicle.
Consider the velocity of a vehicle, averaged over the total time taken to complete its journey - Figure (10). As we would expect, for low densities (p = 0.2), there is virtually free flow. As the density increases, there is more obstruction, and so the average velocity decreases. Thus, at a density of p = 0.5, an individual vehicle is moving around 80% of the time, while at a density of p = 0.8, a vehicle slows down to move at just above 50% of the time. Note that the average velocities of individual vehicles is different from global average velocities - Figure (2): the individual-based velocities are averaged over a time series, whilst the global velocities are averaged for individual times across a number of time series. There is a higher degree of variance evident in individual velocities than in the global velocities.
Figure 10: Average velocity for a vehicle during its total
journey
Another useful indicator of journey efficiency is to compare the total journey length to the shortest possible journey length. We shall call the ratio of the minimum journey length to that of the actual journey length as the trip distance ratio. It has a value upwards from 0 (extremely long actual journeys compared to the minimum journey), to 1 (actual journey is as long as the shortest possible journey). We have plotted this statistic in Figure (11). This ratio decreases from a value around 0.8 at a density of p = 0.2, down to around 0.15 at a density of p = 0.8.
Figure 11: Decrease in trip distance efficiencies during an
individual car's journey
Following this initial analysis, it is apparent that the model exhibits a sufficient degree of complexity, including jamming behaviour. At the next stage of this investigation, we will complete this set of experiments with more densities and lattice sizes to allow comparison with other models. It is anticipated that an analysis of these experiments will indicate various influences on network traffic flow and the identification of self-organisational dynamics of traffic systems in general.
Considerations in further experiments include the collection of site-based statistics, such as the occupancy rates of sites. Possible refinements to the model which will be considered include adding site constraints such as street directions, and traffic lights.
A 2-Dimensional Cellular Automaton of Traffic Flow with Simple Adaptive Routing
This document was generated using the LaTeX2HTML translator Version 96.1 (Feb 5, 1996) Copyright © 1993, 1994, 1995, 1996, Nikos Drakos, Computer Based Learning Unit, University of Leeds.
The command line arguments were:
latex2html mitchdur.
The translation was initiated by Pam Milliken on Thu Jan 16 15:16:04 EST 1997