Language learning | English » Mátyásfalvi György - NaSch model

http://www.doksihu Eötvös Loránd University Faculty of Science Department of Probability Theory and Statistics Bachelor’s Thesis http://www.doksihu The influence of lane changing on spontaneous highway traffic congestion through the implementation and mean field approximation of the cellular automata type NaSch model Author: György Mátyásfalvi Supervisor: Tamás Pröhle January, 2011 http://www.doksihu I would like to thank hereby all my teachers who have thought me and have given me the opportunity to develop. I am thankful for my thesis supervisor Tamás Pröhle and members of the Eötvös Loránd University Mathematics Institute for their support. This thesis wouldn’t have been accomplished without the help of my sister and my parents. http://www.doksihu Contents 1 4 1.1 Introduction . 4 1.2 Traffic Model . 6 1.21 Continuous approach [12] . 9 1.22 Discrete

traffic model . 10 2 11 2.1 Dynamical Systems . 11 2.2 Cellular Automata [22] . 13 2.3 Probability theory 14 2.31 2.4 . Stochastic processes . 15 Fundamental Diagram . 19 3 22 3.1 3.2 NaSch model and the two lane extension . 22 3.11 One lane model . 22 . 22 3.12 Two lane model with lane changing . 23 3.13 Simulation results . 24 Hypothesis testing . 30 3.21 31 Chi-square Test for Homogeneity . 4 33 4.1 Mean Field Approximation of one lane model . 5 33 48 5.1 Conclusion . 1 48 http://www.doksihu A MFA for vmax ∞ 50 B Time evolution equations two lane MFA 51 C Source Code of trfc ring100.cpp 53

D Octave script for E(X) 66 2 http://www.doksihu List of Figures 1.1 Theory of gridlock [24] . 8 1.2 Gridlock in New York [24] . 8 2.1 Segment of 1 dimensional cellular automata . 14 2.2 Segment of 2 dimensional cellular automata . 14 2.3 Fundamental Diagram for cellular automata simulation [1] . 20 2.4 Comparison FD simulation (B) and empirical (A) [14]. 21 3.1 Flow for p = 0.1 no lane changing 28 3.2 Flow for p = 0.1 lane changing yes 28 3.3 Displaying both results . 29 4.1 Approximation on grid coarse [2] . 34 4.2 Displaying both simulation and MFA results . 47 3 http://www.doksihu Chapter 1 1.1 Introduction Frictionless transport is a substantial condition for sustainable economic development. In the last decade we have witnessed a strong increase in road

traffic and to a lesser degree expansion of road networks thereby greatly affecting the quality of traffic flow. It makes sense to optimize throughput and travel times through traffic engineering. To address the optimization new methods in traffic control are being developed Some of these methods include intersection control, lane and grid influence in order to enhance traffic flow with different degrees of complexity. A prerequisite for the development of such control systems is the profound and detailed understanding of the dynamics of traffic flow and the parameters that influence it. Both empirical observations and traffic evolution models play an important role in the description of traffic dynamics. Traffic evolution models are usually analogically developed models taken from hydrodynamics or statistical physics. For macroscopic parameters such as density, flow and mean velocity derived form these analogies one observes a functional dependency that allows us to describe traffic

flow. This functional dependency between density, flow and mean velocity is depicted in the so called fundamental diagram. The fundamental diagram can be used as a tool when determining the effectiveness of elements of transportation infrastructure in the level of service (LOS) system thus helping the classification of transportation infrastructure elements [16]. The LOS system grades transport infrastructure elements according to following [3]: 4 http://www.doksihu A free flow B reasonably free flow C stable flow D approaching unstable flow E unstable flow F forced or breakdown flow As we can see the fundamental diagram is an essential tool for analyzing traffic related topics. This is no exception in our case either we will conduct our analysis of the influence of lane changing behavior on spontaneous traffic congestion with the help of the fundamental diagram. Road traffic is a complex dynamic system Experimental results show that various non-linear phenomena lead to different

phases of traffic flow. Just like the LOS classification shows beside stable free flow states with low density and congested states with high density there exists a metastable states where high density is coupled with high flow. In addition some measurement data shows evidence of another state designated as synchronized state. Almost every motorist nowadays is confronted with the phenomenon of spontaneous traffic congestion or the so called phantom jam i.e a jam that happens for no apparent reason Probably the most striking occurrence of a phantom jam for the motorist is when driving on a highway undisturbed with a relatively high velocity until suddenly one enters a jam. After some time has elapsed one leaves the jam without being able to identify the reason for it. Metastable states have a finite life time and a local increase in density can lead to the collapse of the metastable state so that a spontaneous traffic congestion emerges. Analysis of such occurrences first requires the

definition of a suitable model A model that is capable of reproducing experimental findings at least qualitatively. There are a vast majority of models created for modeling traffic. Most of them can be cast into two major categories: continuous or discrete. The type of model one uses depends on the nature of the investigation one is about to conduct. In our case a cellular automata (CA) model for freeway traffic the so called NaSch model has been selected to perform the analysis of lane changing behavior. This approach is particularly convenient for simulation purposes and to analyze microscopic behavior such as lane changing. 5 http://www.doksihu It is important however to state upfront that our model is relatively simple in terms that it does not take into account many aspects that influence traffic flow. Thus it is also minimal i.e any parameter left away would result in an unrealistic model For example, we will not distinguish between car types, and therefore our model will

incorporate only one type of car. One can rightfully question the reason behind such simplified models since there are very few attributes common with the phenomena observed in real life. However, interestingly even some very simple models are able to reproduce results observed in real life whereas keeping our model as simple as possible allows us to draw important conclusions more effectively. Thus, throughout this work we will always limit ourselves to the most simple case, which is still meaningful in a scientific way. 1.2 Traffic Model When studying any real world process a key moment in succeeding is creating a coherent model of the process that can help us simplify and therefore understand the key aspects of the process itself. However finding the right model in some cases is easier said than done. One of the cases that belongs to the just mentioned category is modeling traffic and traffic flow. A variety of models have been suggested with respect to reproducing traffic

phenomena. Each model has its pros and cons depending on the investigated field of traffic, for example, how and why traffic jams form, how to maximize carrying capacity of roads, or how best to use signals, speed limits and other controls to reduce journey times [12]. Many scientists have worked on this problem nevertheless, as of today no satisfactory mathematical theory of traffic flow has been published that can be consistently applied to real world traffic flow conditions [17]. A coherent traffic model could help understand the formation of traffic jams, maximize through put capacity of roads or draft traffic codes that reduce journey times [12]. There are many different approaches as to modeling traffic flow. However we can distinguish between the following two major categories: 6 http://www.doksihu 1. Discrete models (describes the movement of individual cars) 2. Continuous models (cars are handled as a continuum ie local density and velocity are both smooth functions of

space and time) The above mentioned categories have many subcategories, the list [11] below illustrates the diversity of these models: 1. Car-following models focuses on the non-linear interaction and dynamics of single vehicles. They specify their acceleration mostly as a function of the distance to the vehicle ahead and their own and relative velocity. 2. Submicroscopic models take into account even details such as perception thresholds, changing of gears, acceleration characteristics of specific car types, reactions to brake lights and winkers 3. Cellular automata models in favor of numerical efficiency describe the dynamics of vehicles in a coarse-grained way by discretizing space and time. 4. Gas-kinetic models agglomerate over many vehicles and formulate a partial differential equation for the spatio-temporal evolution of the vehicle density and velocity distribution. 5. Mesoscopic - hybrid traffic models describe the dynamics of single vehicles in response to aggregate

quantities such as density. 6. Queuing models restrict to the temporal change of numbers of vehicles on larger street sections as a function of entering and leaving flows, which is sufficient to determine the travel times. Each above mentioned approach has its advantages and disadvantages. Generally the discrete approach makes it possible to track individual behavior of objects in traffic and therefore allows for thorough analysis of traffic obstruction causes. However, the discrete model can become very complicated resulting in a complex system. Solving complex systems need strong mathematical and computational tools and these tools are not always on hand. The continuous approach usually does not result in a complex system that needs to be solved. It offers insights into the way in which traffic as a whole behaves and therefore can be compared with observations. 7 http://www.doksihu Figure 1.1: Theory of gridlock [24] Figure 1.2: Gridlock in New York [24] However, it is unlikely

ever to forecast the fine details of gridlocks1 or stop and go waves with continuous traffic simulation [12]. Examples of a gridlock are illustrated in Figure (1.1) and (12) 1 Gridlock is a term describing an inability to move on a transport network. The term originates from a situation possible in a grid network where intersections are blocked, preventing vehicles from either moving forwards through the intersection or backing up to an upstream intersection [24]. 8 http://www.doksihu 1.21 Continuous approach [12] The continuous approach treats the cars as a continuum with a local number density and velocity which are more or less smooth functions of space and time [12]. Let us begin with a much simplified model where vehicles are traveling in one direction on a single-lane road that is straight. Our model would have the following attributes: 1. Single lane straight road (no turns) 2. No overtaking 3. Closed system (there are no cars entering or leaving the system) 4. Constant

velocity (drivers are driving at constant speeds, drivers choose their speed at system entry (which again happens at the same time for all cars since according to 3 we are in a closed system)) We denote the measure of distance by x and the measure of time by t. We note density as: ρ(x, t) (cars per distance, note that this parameter will be accountable for the cars), and speed as u(x, t) (distance per time). We also have to introduce one of the most important variables in traffic modeling the so called flow or flux. The flow is the number of cars (quantity) passing a given point in a unit of time. According to the unit of flow which is number of cars unit time we can obtain the flow of our traffic system by multiplying the mean speed of the roadway with its density. Let us use denote flow with q so we can write q = u × ρ. We use the following notation: Notation 1.211 Density: ρ(x, t) Notation 1.212 Speed: u(x, t) Notation 1.213 Flow: q(ρ, x) Taking into account the above

mentioned restrictions we get the following two equations that describe the flow of traffic in our system: ∂ρ ∂q + =0 ∂t ∂x (1.1) Equation (1.1) stands for the ’conservation of cars’ Since no cars are entering or leaving the system, the density must not change over time. Therefore the number of 9 http://www.doksihu cars in a small element of length changes at a rate equal to the difference between inflow and outflow of cars. In order to be able to close the system we need one more equation. A greatly simplified model would be to assume that drivers choose their desired velocity at system entry, and once they have entered the system, they drive constantly at the speed chosen at that entry point. Multiplying Equation (11) with the derivative c = ∂q ∂ρ = c(ρ, x) gives us our second equation: ∂q ∂q +c =0 ∂t ∂x (1.2) So we end up with a special case of Partial Differential Equation PDE know as the kinematic wave equation, which is a solvable problem. One

method of obtaining the solution of these equations is by characteristics dx = c dt. Along each of these the flow q is constant. This means that cars move along characteristics with constant velocity c. 1.22 Discrete traffic model There are a variety of continuous models that are more sophisticated than the one just mentioned. However, as already discussed, some fine model specifications are very difficult to treat in continuous settings. This is the reason why discrete models are created and with the help of computer simulation, consequences can be drawn from discrete models. Here the problem of analytical treatment presents itself Thankfully, to recently published works, the analytical treatment of discrete models in some special cases is possible through the Mean Field Approximation. Before we get into further details of our selected NaSch model, which is based on a cellular automata approach, it is important to discuss the essence of dynamical systems, cellular automata models;

and a special kind of stochastic process the so called totally asymmetric exclusion process (TASEP). 10 http://www.doksihu Chapter 2 2.1 Dynamical Systems We can think of a dynamical system as a collection of elements e.g cars and their effects on each other. Highway traffic therefore is a system A system that is present in reality. As described in [9] a real life system has the following characteristics: • It is dynamic i.e subject to lasting changes • It is complex i.e depends on many parameters • It is iterative i.e the laws that govern their behavior can be described by feedback. From a mathematical point of view, a dynamical system is the mathematical formalization for a given “rule,” which describes the time dependence of a point’s position in the space surrounding it also known as ambient space1 . Thus, in our case a vehicle is associated with a given point in the ambient space i.e the roadway The rule that describes a point’s position depends on the

acceleration and deceleration parameters of a given vehicle, and its position in regard to the other vehicles on the road. A dynamical system usually takes the following mathematical form: xn+1 = f (xn ), n = 0, 1, 2, 3, . , (2.1) In order to be able to grasp the essentials of a dynamical system we will start by introducing a very simple example. A good and easy example of a dynamical system is the evolution of a biological population. For example if the population size happens 1 ambient space: is the space surrounding a mathematical object e.g a line may be studied in isolation, or it may be studied as an object in two-dimensional space [25]. 11 http://www.doksihu to double from one generation to the next, we would have the following equation describing our dynamical system: xn+1 = 2xn , n = 0, 1, 2, 3, . , (2.2) A more realistic example would be the so called logistic equation, which is used to describe demographics: xn+1 = (1 + a)xn − ax2n , n = 0, 1, 2, 3, . ,

(2.3) Let us take the special case of the above system where a = 1 and x0 = 0.25 from which we get: x1 = 2x0 − x20 x1 = 0.4375 x2 = 0.6836 . . x5 = 0.9999 x6 = 1.0000 x7 = 1.0000 . . xn = 1.0000 (2.4) The sequence of values x0 , x1 , x2 , . , xn , denote the orbit or trajectory of the dynamical system. In this case the value 1 is the so called attractor of the dynamical system. The set of points that evolve to an attractor are said to lie in its basin of attraction [22]. The equation: f (x) = x (2.5) represents the fixed point of the function f . No further discussion of dynamical systems is needed in order to understand the NaSch model. So we can jump to our next topic the so called Cellular Automata. 12 http://www.doksihu 2.2 Cellular Automata [22] The emergence of cellular automata (for short: CA) is dated around the mid 20th century and is usually connected to John Von Neumann’s attempt to create a self-replicating machine. Essentially cellular automata

(CA) is a discrete model Discrete meaning that the time evolution of the model takes discrete steps i.e time steps t = 0, 1, 2, 3, . , m, This means that changes to the model only happen at predetermined time steps. We can think of cellular automata (CA) as a lattice network of cells, which are in our case square in shape. Each cell can have k ≥ 2 different values, or in other words can exist in k different states; therefore we need k ≥ 2 otherwise there is no difference between the cells in our lattice network and thus there is nothing to observe. We will distinguish one special state from all the other states this is called the “quiescent state.” If k = 2 we obtain the simplest case of cellular automata (CA), in this case we can think of the cells as either dead or alive, which can be denoted by 0 and 1. In this cellular automata the ”quiescent state“ would be the dead i.e the 0 state Certainly not only the state of the cells can have different values also our

lattice network can have different dimensions n ≥ 1. We will limit the discussion to n ≤ 2 i.e the one and the two dimensional cases Usually we can think of one dimensional cellular automata as an infinite length array and the two dimensional as a boundless graph paper. In our case we will limit the size of our lattice in order to satisfy certain conditions that enable analytical investigation of our cellular automata. These conditions, will be discussed later. After tying down the shape of our cells (square), the possible states of our cells (k), and the dimension of our lattice (n), we only need one more thing in order to have our cellular automata complete and ready to evolve in time, this is the so called local transition function. The local transition function governs how each cell alters its state from the present to the future, i.e form a given time step t to t+1 The argument of the local transition function is the state of the cell on which it acts at time step t and the

state of its neighbors at time step t. The neighborhood of a cell has to be and thus is always defined in the model. The transition function is applied parallel or synchronously for all cells in the lattice. The transition function can be deterministic or probabilistic. Our cellular automata model for traffic flow will be the latter. The lattice of cells, the set of allowable states, together with the transition function is called a cellular automaton. 13 http://www.doksihu 1 0 0 0 0 1 0 1 0 1 Figure 2.1: Segment of 1 dimensional cellular automata 1 0 0 0 0 0 0 1 0 1 1 1 0 0 1 1 0 0 0 1 1 0 1 1 0 1 0 1 1 1 1 0 0 0 0 0 0 1 1 1 0 0 1 0 0 0 1 0 0 1 1 1 1 1 1 0 0 0 0 0 Figure 2.2: Segment of 2 dimensional cellular automata Therefore the three fundamental features of cellular automaton are [22]: uniformity: all cell states are updated by the same set of rules. synchronicity: all cell states are updated simultaneously. locality: the rules are local in nature. A configuration is

the assignment of states or values by the transition function to each cell in the lattice. In our investigation of traffic flow we will apply a cellular automata model to illustrate the motion of cars on a roadway. We will think of the roadway as one-dimensional integer lattice where a cell may be occupied by exactly one car or it is empty. The values of a cell can take the values of either empty or the equivalent of the velocity of the vehicle that is occupying the cell. After discussing CA models it is time to talk a little about probability that is an essential part of most real world models and so of the NaSch model as well. 2.3 Probability theory Probability theory deals with the mathematical model of random events. All events that take place in nature can be classified according to two main categories. One category can be depicted as deterministic i.e if given conditions and circumstances are present the outcome of the event is certain e.g some chemical reactions The other

category is described as random i.e the observable conditions and circumstances do not determine clearly the course of the event; other more or less minor not necessarily 14 http://www.doksihu observable conditions and circumstances influence the course of the event, and as a consequences there is more than one possible outcome. In this case we speak of random or stochastic events. Traffic is a very complex dynamical system, similar to weather. Meteorologists are able to make predictions about tomorrow’s weather, however there are so many conditions and circumstances determining tomorrow’s weather that all of them cannot be taken into account; therefore tomorrow’s weather forecast remains the most probable outcome of a random event for most of us on earth. As already mentioned, traffic is very similar to weather, in the sense that there are so many unknowns that need to be considered in order to determine the exact velocity of a given vehicle, at any time and point in space,

that like many other processes in nature this remains a random event as well. Let us just think about our own driving habits, the speed we are driving can depend on the weather conditions, wind, rain, snow, humidity, etc. the type of car we are driving, our personality, the mood we are in, how many hours of sleep we had last night, number of passengers in the car, the music we listen to, the conversation we are engaged in, the type of journey, the surrounding scenery, the road conditions, etc. As we can see, it is impossible to define a model that is able to take into account all of these conditions and circumstances, and is able to provide us with a solution within a reasonable time frame. We cannot determine the outcome of stochastic events, however it is reasonable to assume that we are able to define a set called the sample space, containing all the possible outcomes of the event. During the mass-occurrence of random events certain regularities will prevail. Probability theory is

the investigation of these regularities Thus for the inquiry of traffic flow we will rely heavily on the findings of probability theory. 2.31 Stochastic processes The velocity of a vehicle at given time in space can be considered as a stochastic process. This means that our sample space consists of all the possible values a vehicle’s velocity can attain. A property of stochastic processes is that the collection of random variables2 it encompasses are indexed by the elements of a set T where T stands for ”time“. Thus taking the form of Xt , t ∈ T We will consider the case where t ∈ Z and the evolution of time happens in a discrete manner. 2 random variable: Let X(ω) be a function that is defined on the elements of the sample space Ω where ω ∈ Ω for a given probability space (Ω, F, P ). We denote the function X(ω) with X and define it as a random variable if for all a < b a, b ∈ R the aggregate of those ω events for which a ≤ X(ω) < b holds true is a

random event i.e ∈ A 15 http://www.doksihu Markov processes are stochastic processes perhaps the simplest model of a random evolution without long-term memory [7]. Let us examine a system with A1 , A2 , . possible states where the state of the system at a given time depends on randomness. The state in which the system is at discrete time steps t = 0, 1, 2, is denoted by the following discrete series of random variables X0 , X1 , . , Xt , Let Xt , (t = 0, 1, 2, . ) be a random variable, which takes on value i, if the system at time step t is in state Ai . Definition 2.311 i ∈ R is called a state if there ∃ n that P(Xn = i) > 0 Notation 2.312 Let I denote the state space I is countable. Definition 2.313 The sequence X0 , , Xn , is called a Markov chain if for arbitrary P(Xn n = in |X0 ∈ N = i0 , . , Xn−1 and = in−1 ) = P(Xn states i0 , i1 , . , in : = in |Xn−1 = in−1 ) holds true. (This condition is called Markov property)

Definition 2.314 steady state Certain properties of the system do not change over time i.e for a property p ∂p ∂t = 0. In stochastic systems, the probabilities that different states will be repeated will remain constant [13]. One can think of cars moving along a road, or within a network consisting of roads, as interacting particles. The cars are representing the particles, their interaction can be thought of as the continuous velocity adjustment in order to avoid accidents, the ambient space is considered to be the roadway. The stochastic process that will help us describe the movement of cars in the cellular automata model is the so called totally asymmetric exclusion process (TASEP). The asymmetric exclusion process is a Markov process, that describes the motion of particles on the one dimensional integer lattice, subject to the exclusion interaction that allows at most one particle at each site [5]. The asymmetric exclusion process is sometimes also called as the process

illustrating particle hopping where particles jump one step to the right, with rate p, and one step to the left, with rate q = 1 − p, as time evolves. We assume that 0 ≤ q < p ≤ 1. When talking about total asymmetric exclusion process we only consider jumps in one direction usually to the right. This is the case when we think about cars advancing on a freeway in one direction. The most simple cellular 16 http://www.doksihu automata model of traffic flow is a one dimensional cellular automata model with periodic boundary condition i.e a ring consisting of a finite number of cells In terms of asymmetric exclusion processes the motion of cars in the above mentioned setting can be described by the discrete-time TASEP on a ring. In our model we will assume site oriented discrete time dynamics i.e one update of the system corresponds to the elapse of one time step. Periodic boundary condition induces the criterion of i = 0, 2, 3, . , S − 1 and S − 1 + i = i on a system of S

sites This can also be regarded as modulo operation calculating modS We distinguish between the different sequences of updates. There are four different updating procedures depending on the order the update rules are implemented. • Parallel update all sites are updated simultaneously • Forward order sequential update: update rules are applied according to i = 0, 1, 2, . , S increasing order • Backward order sequential update: update rules are applied according to i = S, . , 2, 1, 0 decreasing order • Random sequential update: update rules are applied to sites in a random order. According to how the update rule is executed sites are updated. In the one dimensional case particles cannot overtake each other, hence their order is preserved in time Thus the possible outcomes depend on the presence of empty sites between particles. Let us consider the following notation: • C denotes a possible configuration of a system. • M (C, C 0 ) is the rule of evolution. • M (C, C 0

)dt is the probability of a transition form configuration C 0 to configuration C during the infinitesimal time interval dt. For the asymmetric exclusion process, ensuring that a distribution P (C) has a long time limit independent of the initial condition, the rule of evolution M (C, C 0 ) should not leave any subset of configurations disconnected from the rest (i.e there should be a path of non-zero matrix elements connecting any pair of configurations) [8]. When no energy function present the system is only defined by its dynamical rules. In the 17 http://www.doksihu long time limit if all configurations are connected the system can reach a steady state. Which satisfies the condition of stationarity : X M (C 0 , C)Psteady state (C) = C0 X M (C, C 0 )Psteady state (C 0 ) (2.6) C0 The above expression states that the probabilities of entering and of leaving the configuration C during the time interval dt are equal [8]. If we consider the findings in [6], we can see that for

the discrete case backward order sequential update, the total transition probabilities for the direct and reserved dynamics coincide. If
−1 P0 (C) = NS equiprobable distribution for a ring consisting of S sites occupied by N particles. Applying the Bethe ansatz we obtain for the conditional probability PT (C|C 0 ) = PT (x1 , . , xn |x01 , , x0n ) : 0 PT (C|C ) = ∞ X k1 =−∞ . ∞ X (−1)(N −1) PN i=1 ki detM (2.7) kn =−∞ , where the elements of N × N matrix M are: Mij = Fsij (x0i , xj + kj S|T ) (2.8) The two-lane model is defined on a two lane lattice of S × 2 sites. The time evolution equation of the two-lane model is more complex as described in [18]: 18 http://www.doksihu X d P (τ1;1 , . , τL;2 ) = (h1;1 )τ1;1 ;σ1;1 P (σ1;1 , . , τL;2 ) dt σ1;1 X + (h1;2 )τ1;1 ;σ1;2 P (τ1;1 , . , σ1;2 , , τL;2 ) σ1;2 + 2 X L−1 X X (hj,j+l;l )τj;l ,τj+1;l ;σj;l ,σj+1;l × l=1 j=1 σj;l ,σj+1;l ! × P (τ1;1 , . , σj;l ,

σj+1;l , , τL;2 ) + X (2.9) (hL;1 )τL;1 ;σL;1 P (τ1;1 , . , σL;1 , , τL;2 ) σL;1 + X (hL;2 )τL;2 ;σL;2 P (τ1;2 , . , σL;2 ) σL;2 + L X X (hj;1,2 )σj;1 ,σj;2 ;τj;1 ,τj;2 × j=1 σj;1 ,σj;2 ! × P (τ1;1 , . , σj;1 , , σj;2 , , τL;2 ) Now we are ready to advance to the last part of this work before building our model and investigating the effect of lane changes on spontaneous highway traffic congestion. 2.4 Fundamental Diagram As already mentioned in the introduction, we will conduct our analysis of the impact of lane changing behavior based on the fundamental diagram. The fundamental diagram illustrates the connection between density ρ number of cars . unit time number of cars unit distance and flow q In real life, for the fundamental diagram measurements taken from roadways, with the help of sensors measuring the percentage of the road which is covered by vehicles simultaneously, taking values for the number of cars passing a

given point. The calculation of flow for our NaSch model with periodic boundary conditions is more simple since the density does not change over time, therefore we only have to calculate the mean velocity of the roadway and apply the functional relation of: q =ρ×v 19 (2.10) http://www.doksihu Figure 2.3: Fundamental Diagram for cellular automata simulation [1] Where ρ = N , S N denotes the number of cars on the lattice S, the number of sites in PN our lattice and v the average velocity for our roadway i.e v = i=1 N vi where vi is the velocity of an individual car i. Basic property of the empirically observed fundamental diagram is the asymmetry to the left. Thus, if simulation results yield similar asymmetry in their fundamental diagram, we can assume that the simulation is capable of reproducing some traits of real life traffic flow. With the help of the fundamental diagram we can formulate statements about the throughput of a given road segment. This observation will

help in our analysis on the influence of lane changing behavior on phantom jams. 20 http://www.doksihu Figure 2.4: Comparison FD simulation (B) and empirical (A) [14] 21 http://www.doksihu Chapter 3 3.1 NaSch model and the two lane extension 3.11 One lane model Let us start by investigating the one-lane CA traffic model, the so called NaSch model. As described by Nagel and Schreckenberg [19] the model is defined by a onedimensional array of S sites The model can be implemented with open or periodic boundary conditions. In our case we will limit the investigation to scenarios involving periodic boundary conditions. Each site in the array is either occupied by exactly one vehicle or it is empty. The velocity of each vehicle can take integer values between 0 and vmax . Traffic flow according to the NaSch model has the following runoff: For an arbitrary initial state the following four consecutive update rules are implemented parallel for all vehicles [23] (in terms of CA

these are our local transition functions): 1. Acceleration: If the velocity v of a vehicle is lower than vmax the speed is advanced by one [v = v + 1]. 2. Deceleration (due to other cars): If the distance l to the next car ahead is not larger than v (l ≤ v) the speed is reduced to l − 1 [v = l − 1]. 3. Random Deceleration: With probability p, the velocity of a vehicle if v > 0 is decreased by one [v = v − 1]. 4. Car motion: Each vehicle is advanced v sites As we can see at each discrete time-step t t+1, an arbitrary configuration of N cars is updated, according to the above mentioned update rules. The update rules and the periodic boundary condition ensure that the number of cars N is conserved. We also 22 http://www.doksihu have to point out that update rule Random Deceleration yields non-deterministic behavior in our system. 1 . . 0 . 5 . In order to determine to what extent the NaSch model reproduces real life traffic flow we are interested in calculating the

fundamental diagram. For the fundamental diagram we need to obtain the flow q vs. density ρ = N . S The more the fundamental diagram produced by the model resembles the fundamental diagram obtained by real life measurements, the better our model. Thus, we can expect our fundamental diagram to be asymmetric to the left. The model should also reproduce a transition from laminar flow to start-stop waves with increasing density [23]. 3.12 Two lane model with lane changing Our two lane model remains basically the same as the one dimensional NaSch model, except for the introduction of lane changing behavior. As already stated, we are going to introduce the most simple lane changing rule. This rule states, that if a vehicle has to slow down due to another vehicle, and the site to its side is empty, the vehicle will change its lane regardless of the vehicles behind and in front of the site to which it changes its position. We can think of this simplification as a bunch of narrow-minded

drivers selected for this experiment. In the sequel the update rules: 1. Acceleration: If the velocity v of a vehicle is lower than vmax the speed is advanced by one [v = v + 1]. 2. Lane changing: If the distance l to the next car ahead is not larger than v (l ≤ v) and the site to the side is empty, the vehicle changes the lane. [(i, j) (i + 1 mod 2, j)]. It follows from the lane changing rule that vehicles with velocity zero do not change lanes. 3. Deceleration (due to other cars): If the distance l to the next car ahead is not larger than v (l ≤ v) the speed is reduced to l − 1 [v = l − 1]. 4. Random Deceleration: With probability p, the velocity of a vehicle if v > 0 is decreased by one [v = v − 1]. 5. Car motion: Each vehicle is advanced v sites 23 http://www.doksihu The NaSch model is perfectly capable of reproducing spontaneous traffic congestions. This can be confirmed by simulation data [19]. The cause of throughput decline on road segments is accounted for the

formation of traffic congestions of any kind, however since the NaSch model does not incorporate parameters for accidents, road closures, etc. this traffic congestion according to the definition of spontaneous traffic congestion, can only be of spontaneous nature. Hence the decline of throughput for a NaSch model with given parameters indicates that the formation of phantom jams become more frequent. 3.13 Simulation results Now that we have introduced the two-lane model we can start to investigate the influence of lane changing behavior on some of the basic properties of traffic flow. We will start our investigation by simulation. We are interested in the differences between the fundamental diagrams of a two-lane road, where overtaking is allowed, and two-lane road, where overtaking is not allowed. By comparing the two fundamental diagrams we can draw conclusions in regard to the throughput of each road segment. Nevertheless we have to construct a simulation that is capable of

producing data for the two fundamental diagrams. The C++ program trfc ring100.cpp I have developed for simulation purposes is capable of simulating two-lane highway traffic (source code in Appendix C). The program implements all the update rules defined in our two-lane model. Cars first accelerate, then the condition for lane changing is examined, and if applicable vehicles engage in lane changing, then the deceleration condition is examined, followed by the random deceleration, finally cars are moved according to their velocities. The order of the update is forward sequential that means that the acceleration rule is first forced on site 0 then site 1, . , i, , site S then the lane changing condition is examined for site 0 then site 1, . , i, , site S etc until cars are advanced according to their velocity The program takes two input parameters p for random deceleration and g ∈ {0, 1} 0 for no lane changing allowed and 1 for lane changing allowed. After receiving the two input

parameters an initial configuration for a given density is attained by distributing the vehicles randomly. At time step 0 the initial speed of all vehicles is 3 This initial configuration is updated 1000 times. After the update procedure, the next density value is fed to the system, which again produces a random initial positioning of vehicles. This initial configuration is updated again a 1000 times This procedure goes on 24 http://www.doksihu until we reach the final density value 0.99 fed to the system The simulation produces the data necessary for plotting the fundamental diagram. It measures the flow values q for density values ρ ρ ∈ {0, 0.01, 002, , 050, 051, 052, , 098, 099} Thus we can plot the fundamental diagrams for different p random deceleration probabilities and g guidance i.e lane changing parameters A sample output of the density flow table: 0 -0 0.01 004775 0.02 009164 0.03 013494 0.04 017512 0.05 021395 . . . 0.18 055062 0.19 056373 0.2 05602 . . . 0.47

006204 0.48 001344 0.49 000049 0.5 0 0.51 0 0.52 0 0.53 0 Above one possible output of the program. In the first row we can see the different density ρ values, in the second the associated flow q values. The flow values are obtained by taking the mean flow q for a given initial configuration i.e flow is measured over 1000 time steps for each different density value. To get an idea how the program simulates two-lane highway traffic we will illustrate the control and traffic output files of the program: A segment of the detailed control output of traffic flow where each update rule is documented (the right side of the array has been deleted for space purposes): 25 http://www.doksihu Start .1 2 1 1 0 2 1 1 2 000 00 1 2 1 . 0 1 100 2 2 1 10 1000 2 0 2 1 Acceleration .2 3 2 2 1 3 2 2 3 111 11 2 3 2 . 1 2 211 3 3 2 21 2111 3 1 3 2 Lane Changing .2 3 21 2 1 23 3 11 211 132 2 . 1 2 2 1 3 3 2 2 121

11 13 3 2 Deceleration .2 1 01 2 1 01 3 01 001 002 2 . 1 1 1 1 3 1 2 2 001 01 01 2 2 Randomization .2 1 01 2 1 00 3 01 001 002 2 . 1 1 1 1 3 1 2 2 001 01 01 2 2 Start . 2 10 1 2 1 00 30 100 1 00 2 2 .2 1 1 1 1 3 1 2 200 1 0 1 0 1 2 Or without lane changing: Start . 2 3 4 100000 1 100 10 1 2 10 1 10000 0 1 1 .00 1 1 1 2 200 1 2 30 100 1 1 20 10 Acceleration . 3 4 5 211111 2 211 21 2 3 21 2 21111 1 2 2 .11 2 2 2 3 311 2 3 41 211 2 2 31 21 Deceleration . 3 4 1 000001 1 001 01 2 1 01 1 00001 1 2 1 .01 1 1 2 2 001 2 3 01 001 1 2 01 01 Randomization . 3 4 0 000001 1 001 01 2 1 01 0 00001 0 2 1 .01 1 1 2 2 001 2 3 01 001 1 1 01 01 Start 1 . 3 40 00000 1 100 10 1 2 10 10 0000 10 .10 1 1 1 2 200 1 2 3 0 100 1 1 1 0 1 0 The output of traffic flow where only the car motion and actual velocities are

documented (the right side of the array has been deleted for space purposes): 26 http://www.doksihu . 4 1 2 2 2 1 2 3 3 2 0000 .100 1 2 20000000 2 1 1 1 30 2 10 20 1 000 .10 1 1 0000000 0 1 1 3 3 200 1 .4 10 1 2 2 1 1 1 1 2 2 0 2 2 .0 10 1 2 2 1 1 1 1 1 2 3 2000 0 . 20 1 2 1000000 1 2 0 3 1 1 20 3 1 1 .10 1 2 3 000000 1 20 2 20 30 200 .1 0 1 2 2 1 1 1 1 2 0 4 2 00 1 1 .1 1 2 3 1 1 10 1 200 3 0 200 1 0 1 .10 1 2 3 10000 2 2 30 3 200 2 Now we can compare the fundamental diagram of the extended two lane version of the NaSch model with lane changing allowed and lane changing not allowed. Plotting the output data we get the fundamental diagram in figure (3.1) At first sight we can see that diagram is asymmetrical, which is good news, since as already mentioned, this is one of the most important properties of the fundamental diagram. This

diagram tells us that for p = 0.1 and no lane changing the transition point1 is around the density value ρ0 = 0.15 and gives us a flow value around q0 = 064 When looking at the fundamental diagram (3.2) of the model with lane changing for p = 01 the transition point is a little more ambiguous in terms of density, the value is somewhere between ρ1 ∈ [0.1, 014] However we can see that the flow value remains drastically lower than for the case of no lane changing q1 < 0.44 < 064 ≤ q0 This certainly makes us suspicious on the impact of lane changing on the throughput of highways. In order to get a better picture of the results we plot the two results on the same diagram in figure (3.3) The astonishing result is that both fundamental diagrams are almost identical in terms of their shape, the only crucial difference between them is in their magnitude. It seems that over a certain density lane changing increases the formation of spontaneous traffic congestions. Based on the

diagram we can assume that for low density values there is no difference between the flow q of the two configurations however around density value ρ = 0.1 the increase of flow in the model with lane changing comes to a halt, whereas the flow of the model with no lane changing continues to increase. In [19] it is proven that the NaSch model reproduces empirically observed traits of traffic flow. The most important trait of the fundamental diagram is the asymmetry reproduced by the model. This leads to the assumption that the model 1 transition point: gives us the maximal flow value. Until this point the function usually shows a continuous increase. 27 http://www.doksihu Figure 3.1: Flow for p = 01 no lane changing Figure 3.2: Flow for p = 01 lane changing yes 28 http://www.doksihu Figure 3.3: Displaying both results indeed is capable of reproducing some properties of empirical traffic. Therefore we can assume that the simulation where lane changing is not allowed basically

amounts to a close approximation of the implementation of the original NaSch model to each lane. Further supporting our assumption that the fundamental diagram of our model takes a promising shape. At this point we have to mention the work of Knospe et al. where they discuss that the rule of lane changing has to take into consideration an incentive criterion and safety criterion in order to reproduce realistic results. Thus, a vehicle is allowed to change lane only if the gap between successor and predecessor in the destination lane is sufficient. In addition to increase the efficiency of the lane changes, the movement of the preceding vehicle in the destination lane is anticipated [15]. 1. Incentive criterion: (b0 = 0) and (v(t) > d) 2. Safety criterion: (ef f ) (dpred ≥ v(t)) and (dsucc ≥ vsucc ) 29 http://www.doksihu Having said that, we also have to mention, that since the shape of the fundamental diagram of the implementation, where lane changing is allowed, is almost

identical to the other, it is reasonable to anticipate that our rule of lane changing does not distort the model to an unrealistic extent. Also, the difference between the fundamental diagrams seems to be significant enough to further investigate this phenomenon. Even if the implementation of the more sophisticated lane changing rule would probably take away some of the difference between flow results for both models, one conclusion can clearly be drawn from the observation; namely that disciplined driving has an enormous effect on the throughput of any road segment. In the sequel let us see if we can back up our hypothesis statistically, namely that lane changing has a profound effect on traffic flow. 3.2 Hypothesis testing In general statements concerning the distribution or parameters of the distribution of one or more random variables is called statistical hypothesis. Methods that allow us to make a decision about these statements are called statistical tests. We will conduct

our work on the usual probability space (Ω, A, P) [10]. Definition 3.201 Statistical test We call the test function Ψ(X) a measurable function on the sample space, that assigns 0 or 1 to the points of the sample space a statistical test [10]. Definition 3.202 Regions of acceptance and rejection • Region of acceptance: Ra = {x : Ψ(x) = 0} • Region of rejection: Rr = {x : Ψ(x) = 1} Our hypothesis is that the overall throughput of the lane changing system is less than that of the other system. In other words the expected velocity of the vehicles is lower in the system where lane changing is allowed. In terms of our hypothesis the weakest claim we can make is that the velocities of the vehicles in either system are not from the same probability distribution. To test this hypothesis we will use the Chi-square test (χ2 ) for homogeneity. 30 http://www.doksihu 3.21 Chi-square Test for Homogeneity Usually to maintain the presumption of innocence our H0 hypothesis will be the

opposite of what we suspect to be the truth. Therefore we are interested in investigating the hypothesis that the velocities of the vehicles in the two different scenarios (lane changing allowed vs. lane changing not allowed) are from the same distribution This will be our H0 hypothesis: H0 : P (X < x) = P (Y < x). (3.1) As a consequence our alternate hypothesis H1 will be the following: H1 : P (X < x) 6= P (Y < x). (3.2) Our test statistic for the χ2 test is the following: χ2 = nm r X i=0
si 2 −m vi + si vi n (3.3) So in our case the random variables X and Y represent the velocities of the vehicles from the two different systems. As taken from the model X and Y can take values of: 0, 1, 2, 3, 4, and 5 only, keeping us in the discrete world. The χ2 test requires us to take our sample for the two random variables independently. We can satisfy this condition since we are operating on a direct product of two Ω event spaces. Thus for all A ∈ A and B ∈ B it

is true that P (A, B) = P (A)P (B). In other words the sample is taken from two separate runs of our simulation program. In addition the χ2 test also demands the independence of the sample points taken for each random variable. As it is stated in [23] this formulation of the dynamics neglects spatial correlations completely. In CA terms this means that no effect coming from outside the cell neighborhood (in our case: [i − vmax , i + vmax ]) is taken into account. Therefore if we select velocities that are not in one neighborhood our sample can be regarded as independent. Our simulation program will provide us with the necessary samples Basically velocity samples are selected for random densities at random update steps. The following table illustrates the results of the sampling. X v0 v1 v2 v3 v4 Frequency 1 2 3 2 18 90 31 v5 P =n 116 http://www.doksihu Y s0 s1 s2 s3 s4 Frequency 8 16 21 18 12 40 P s5 =m 115 Now we have all the data necessary to test

our hypothesis. All we need at this point is to identify the region of rejection and acceptance. For the χ2 -test our region of rejection is the following: Rr = {χ2 ≥ χ2α (f )} (3.4) , where χ2α (f ) is the critical value from the χ2 distribution table with degree of freedom f so that: P0 (χ2 ≥ χ2α (f )) = α. (3.5) Our test statistic is the following: χ2

5 si 2 vi si 2 X −m − 116 115 = nm = 115 × 116 × v + s v + si i i i i=0 i=0


8 2 16 2 21 2 1 2 3 − − − 116 115 = 115 × 116 × + 116 115 + 116 115 + 1+8 2 + 16 3 + 21


! 2 18 2 18 12 2 90 40 2 − − − + 116 115 + 116 115 + 116 115 2 + 18 18 + 12 90 + 40 5 X vi n (3.6) = 63.061 The possible values of X and Y were r = 6 thus our test statistic is approximately χ2 distributed with degrees of freedom r − 1 = 6 − 1 = 5. Let us look at the critical values for χ2α (5) [10]: Df 90% 95% 97.5% 99% 995% 999% 5 9.24 11.1 12.8 15.1 16.7 20.5 99.95% 22.1 Since χ2 > χ20.05%

(5) 63061 > 221 we can reject the H0 hypothesis even at an α = 0.05% level of significance In other words what we see in the diagram is ”true” Lane changing significantly reduces the flow of our highways. After having said that we can advance to the mean field approximation of our system, which will allow us to compare analytical results with our simulation results. 32 http://www.doksihu Chapter 4 4.1 Mean Field Approximation of one lane model Certainly for some inquiries the simulation results of the model is sufficient enough, however a more complete understanding of the dynamics of the model can be attained through investigating the analytical solution of the traffic model. A complete analytical solution for arbitrary parameters is a rather difficult task Some recent articles claim analytical solutions of CA traffic models specifically [4]. A complete analytical solution for maximum velocity vmax = 1 is given in [23]. Thus one naturally takes into account

approximation methods when studying the NaSch model analytically for vmax > 1. A mean field type theory has been successfully implemented in [23] In the sequel we will examine this method in detail According to [21] mean field methods provide efficient approximations, which are able to cope with the increasing complexity of modern probabilistic data models. A major problem in modern probabilistic modeling is the huge computational complexity involved in typical calculations with multivariate probability distributions when the number of random variables is large. In the mean field approach, the mutual influence between random variables is replaced by an effective field, which acts independently on each random variable. By completing the mean field approximation of our model we will we will receive analytical results for the model, which we then can compare to our simulation results. This comparison allows us to depict the difference between the two different systems lane changing vs.

no lane changing in more detail The mean field approach looks at the multi-bodied system from a stochastic point of view. This means that we examine the probability distribution of each site at each time step. Using the following notation: 33 http://www.doksihu Figure 4.1: Approximation on grid coarse [2] d(i, t) is the probability that there is no vehicle at site i (i = 1, 2, 3, . , S) at time step t i.e empty site cα (i, t) is the probability that there is a vehicle at site i (i = 1, 2, 3, . , S) and time step t with velocity α (α = 0, 1, 2, . , vmax ) c(i, t) is the probability that a site is occupied i.e c(i, t) = Pvmax α=0 cα (i, t). The c and d distributions take into account all possible states of a site. Therefore we can write the following: d(i, t) + c0 (i, t) + c1 (i, t) + c2 (i, t) + · · · + cvmax (i, t) = 1 (4.1) Taking into account the update rules in Section (3.1) we can derive the following set of equations denoting the time evolution of the cα

(i, t) probability distributions: • Acceleration stage c0 (i, t1 ) = 0 cα (i, t1 ) = cα−1 (i, t), 0 < α < vmax cvmax (i, t1 ) = cvmax (i, t) + cvmax −1 (i, t) 34 (4.2) http://www.doksihu • Deceleration stage c0 (i, t2 ) = c0 (i, t1 ) + c(i + 1, t1 ) vX max cβ (i, t1 ) β=1 cα (i, t2 ) = c(i + α + 1, t1 ) α Y d(i + j, t1 ) j=1 + cα (i, t1 ) α Y vX max cβ (i, t1 ) (4.3) β=α+1 d(i + j, t1 ), 0 < α < vmax j=1 cvmax (i, t2 ) = vY max d(i + j, t1 )cvmax (i, t1 ) j=1 • Randomization stage c0 (i, t3 ) = c0 (i, t2 ) + pc1 (i, t2 ) cα (i, t3 ) = qcα (i, t2 ) + pcα+1 (i, t2 ), 0 < α < vmax (4.4) cvmax (i, t3 ) = qcvmax (i, t2 ) • Motion stage cα (i, t + 1) = cα (i − α, t3 ), 0 ≤ α ≤ vmax (4.5) As in [23] described t1 , t2 , t3 should be interpreted as intermediate time steps between t and t + 1 (t + 41 , t + 24 , t + 43 ) respectively. Let us investigate the validity of these equations by examining the

expression cα (i, tj ) at each stage. In the first stage we have: cα (i, t1 ) = cα−1 (i, t), 0 < α < vmax The first update rule tells us that unless v(i, t) = vmax we accelerate our vehicle by one unit, therefore the above equation holds true since the probability that after the acceleration stage we have v(i, t1 ) = α equals the probability that v(i, t) = α − 1. The second update rule states that if the distance l to the next vehicle is too short v(i, t1 ) ≥ l we decelerate accordingly i.e v(i, t2 ) = l − 1 35 http://www.doksihu For cα (i, t2 ) we have equation: cα (i, t2 ) = c(i + α + 1, t1 ) α Y d(i + j, t1 ) j=1 + cα (i, t1 ) α Y vX max cβ (i, t1 ) β=α+1 d(i + j, t1 ), 0 < α < vmax (4.6) j=1 which for thorough understanding we have to investigate piecewise, but first let us jot down the two different possibilities a vehicle at stage two can have velocity v(i, t2 ) = α. It either had to slow down to v(i, t2 ) = α and was

traveling at higher speeds before or because of sufficient space it is allowed to maintain its speed and therefore was traveling at velocity α before. According to this logic it is easier to understand equation (5.6) First let us consider the first part of cα (i, t2 ): c(i + α + 1, t1 ) α Y d(i + j, t1 ) j=1 vX max cβ (i, t1 ) β=α+1 The above expression denotes the probability that site i + α + 1 is occupied however sites i + 1, i + 2, . , i + α are empty and the vehicle at site i is traveling at one of the α + 1, α + 2, . , vmax velocities at time step t1 Now let us consider the second part of cα (i, t2 ): cα (i, t1 ) α Y d(i + j, t1 ) j=1 which denotes the probability that the vehicle at site i is traveling with velocity α and there is sufficient space in front of the car i.e sites i + 1, i + 2, , i + α are empty The third update rule randomly decelerates cars i.e according to a given probability p if v(i, t2 ) > 0 it is decelerated by one unit

v(i, t3 ) = v(i, t2 ) − 1 Looking at the equation for cα (i, t3 ): cα (i, t3 ) = qcα (i, t2 ) + pcα+1 (i, t2 ) Here the possibility that at time step t3 a car has velocity α can occur either if it was traveling at velocity α + 1 at time step t2 and according to update rule number three deceleration took place pcα+1 (i, t2 ), or it was traveling at velocity α and no deceleration took place which has probability qcα (i, t2 ) where q = 1 − p. 36 http://www.doksihu At stage four cars are advanced according to their speed at time step t3 , therefore the probability that at site i at time step t + 1 a car is traveling at velocity α equals the probability that a vehicle at site i − α at time step t3 is traveling with velocity α. cα (i, t + 1) = cα (i − α, t3 ) The time-evolution equations (5.2-55) and the property of periodic boundary condition preserves the total number of cars at each stage. These time-evolution equations are non-linear, which makes the analysis

of the system more difficult. As it is stated in [23] this formulation of the dynamics neglects spatial correlations completely. In CA terms this means that no effect coming from outside the cell neighborhood (in our case: [i − vmax , i + vmax ]) is taken into account. The first two steps and the fourth are deterministic, the stochastic nature of the system originates from the third random deceleration step. Let us examine how to express cα (i, t+1) with variables where the time dimension depends only on t. This we can achieve by combining these equations and through substitution. We can begin with c0 (i, t + 1): c0 (i, t + 1) = c0 (i − 0, t3 ) c0 (i − 0, t3 ) = c0 (i, t3 ) ⇓ c0 (i, t3 ) = c0 (i, t2 ) + pc1 (i, t2 ) c0 (i, t2 ) = c0 (i, t1 ) + c(i + 1, t1 ) vX max cβ (i, t1 ) β=1 pc1 (i, t2 ) = pc(i + 1 + 1, t1 ) 1 Y d(i + j, t1 ) j=1 + pc1 (i, t1 ) 1 Y vX max cβ (i, t1 ) β=1+1 d(i + j, t1 ) j=1 ⇓ c0 (i, t3 ) = c0 (i, t1 ) + c(i + 1, t1 ) vX max cβ (i,

t1 ) β=1 + pc(i + 2, t1 )d(i + 1, t1 ) vX max β=2 + pc1 (i, t1 )d(i + 1, t1 ) 37 cβ (i, t1 ) http://www.doksihu We can simplify the expression for c0 (i, t3 ) by taking into account the following: c0 (i, t1 ) = 0 cα (i, t1 ) = cα−1 (i, t) cvmax (i, t1 ) = cvmax (i, t) + cvmax −1 (i, t) c(i + 1, t1 ) = c(i + 1, t) c(i + 2, t1 ) = c(i + 2, t) d(i + 1, t1 ) = d(i + 1, t) ⇓ We also know that c0 (i, t + 1) = c0 (i, t3 ) thus we can write: c0 (i, t + 1) = c(i + 1, t) vX max cβ (i, t) β=0 + pd(i + 1, t) c(i + 2, t) vX max ! cβ (i, t) + c0 (i, t) (4.7) β=1 This way we have expressed the probability that a vehicle at site i and time step t + 1 travels with velocity zero with probabilities only in time step t. Now we can take a look at cα (i, t + 1) where 0 < α < vmax − 1: 38 http://www.doksihu cα (i, t + 1) = cα (i − α, t3 ) cα (i − α, t3 ) = qcα (i − α, t2 ) + pcα+1 (i − α, t2 ), 0 < α < vmax α vX max Y cβ (i − α, t1 )

cα (i − α, t2 ) = c(i + 1, t1 ) d(i + j − α, t1 ) j=1 β=α+1 + cα (i − α, t1 ) α Y d(i + j − α, t1 ), 0 < α < vmax j=1 cα+1 (i − α, t2 ) = c(i + 2, t1 ) α+1 Y d(i + j − α, t1 ) j=1 vX max cβ (i − α, t1 ) β=α+2 α+1 Y + cα+1 (i − α, t1 ) d(i + j − α, t1 ), 0 < α < vmax j=1 ⇓ cα (i − α, t3 ) = q c(i + 1, t1 ) α Y d(i + j − α, t1 ) j=1 +cα (i − α, t1 ) vX max cβ (i − α, t1 ) β=α+1 α Y ! d(i + j − α, t1 ) j=1 + p c(i + 2, t1 ) α+1 Y j=1 +cα+1 (i − α, t1 ) α+1 Y j=1 39 d(i + j − α, t1 ) vX max β=α+2 ! d(i + j − α, t1 ) cβ (i − α, t1 ) http://www.doksihu Combining the above expression for cα (i − α, t3 ) and the following: cα (i, t1 ) = cα−1 (i, t) cα+1 (i, t1 ) = cα (i, t) cα (i − α, t1 ) = cα−1 (i − α, t) cα+1 (i − α, t1 ) = cα (i − α, t) vmax vmax X−1 X−2 cβ (i − α, t1 ) = cβ (i − α, t1 ) β=α+1 β=α vmax X−1

vmax X−2 cβ (i − α, t1 ) = β=α+2 cβ (i − α, t1 ) β=α+1 cvmax (i − α, t1 ) = cvmax (i − α, t) + cvmax −1 (i − α, t) c(i + j, t1 ) = c(i + j, t) d(i + j − α, t1 ) = d(i + j − α, t) We can write for cα (i − α, t3 ): cα (i − α, t3 ) = q c(i + 1, t) α Y d(i + j − α, t) j=1 +cα−1 (i − α, t) vX max cβ (i − α, t) β=α α Y ! d(i + j − α, t) j=1 + p c(i + 2, t) α+1 Y d(i + j − α, t) j=1 +cα (i − α, t) α+1 Y d(i + j − α, t) j=1 40 ! vX max β=α+1 cβ (i − α, t) http://www.doksihu After transforming the above expression and substituting cα (i, t + 1) for cα (i − α, t3 ): cα (i, t + 1) = α Y d(i + j − α, t) × (4.8) j=1   qcα−1 (i − α, t) + qc(i + 1, t) + pd(i + 1, t) cα (i − α, t) × + vX max !  cβ (i − α, t) qc(i + 1, t) + pc(i + 2, t)d(i + 1, t) ,  β=α+1 0 < α < vmax − 1 Of course we have to evaluate the probability distribution in terms of t

for all α i.e vmax − 1 and vmax as well. cvmax −1 (i − vmax + 1, t3 ) = q c(i + 1, t1 ) vmax Y−1 d(i + j − vmax + 1, t1 ) × j=1 vX max × cβ (i − vmax + 1, t1 ) β=vmax +cvmax −1 (i − vmax + 1, t1 ) vmax Y−1 ! d(i + j − vmax + 1, t1 ) j=1 + p c(i + 2, t1 ) vY max d(i + j − vmax + 1, t1 )× j=1 vX max × cβ (i − vmax + 1, t1 ) β=vmax +1 +cvmax (i − vmax + 1, t1 ) vY max ! d(i + j − vmax + 1, t1 ) j=1 At time step t1 the above expression because of Pvmax β=vmax +1 cβ (i − vmax + 1, t1 ) greatly simplifies to the succeeding: cvmax −1 (i, t + 1) = vmax Y−1 d(i + j − vmax + 1, t) qcvmax −2 (i − vmax + 1, t) j=1   + qc(i + 1, t) + pd(i + 1, t) ×   cvmax −1 (i − vmax + 1, t) + cvmax (i − vmax + 1, t) 41 ! (4.9) http://www.doksihu Now let us see the same for cvmax (i, t + 1): cvmax (i, t + 1) = cvmax (i − vmax , t3 ) cvmax (i − vmax , t3 ) = qcvmax (i − vmax , t2 ) ! vY max qcvmax (i − vmax ,

t2 ) = q d(i + j − vmax , t1 )cvmax (i − vmax , t1 ) j=1 ⇓ cvmax (i, t + 1) = q vY max d(i + j − vmax , t) × (4.10) j=1 ! cvmax (i − vmax , t) + cvmax −1 (i − vmax , t) This way we have expressed cα (i, t + 1) for all 0 ≤ α ≤ vmax in terms of t. According to [23] the NaSch model satisfies the stationarity condition Equation (2.6) in Section (2.32) In the stationary state c and d distributions become homogeneous in space for periodic boundary conditions. Thus both space and time dependence can be omitted. With this remark and the above equations we get the following set of vmax + 1 equations: c0 = (c + pd)c0 + (1 + pd)c vX max cβ β=1 cα = dα qcα−1 + (qc + pd)cα + (q + pd)c vX max ! cβ , (4.11) β=α+1 0 < α < vmax − 1 ! cvmax −1 = dvmax −1 qcvmax −2 + (qc + pd)(cvmax −1 + cvmax ) ! cvmax = qdvmax cvmax −1 + cvmax To prove the stationarity of the system we have to show that there exists a state that is attainable with

positive probability from any initial state and that from that state any state is attainable with positive probability. With equations (411) we can depict the motion of a single vehicle with statistical tools. If we define density as c = d − 1 then the above equations are linear and can be recast in a matrix form as A− c =− c. Where A is the matrix satisfying the above set of equations and − c is the vector with 42 http://www.doksihu elements c0 , . , cα , , cvmax If vmax is small enough we can even invert A however for larger values of vmax it is more convenient to go by the recursion relation in order to obtain a steady state solution. Definition 4.101 steady state Certain properties of the system do not change over time i.e for a property p ∂p ∂t = 0. In stochastic systems, the probabilities that different states will be repeated will remain constant [13]. Let us begin with c0 here no recursion is needed since c0 can be determined exactly using Equations

(5.11): c0 = (c + pd)c0 + (1 + pd)c vX max cβ β=1 vX max cβ = c − c0 β=1 ⇓ c0 = (c + pd)c0 + c(c − c0 ) + cpd(c − c0 ) c0 = (c + pd)c0 + c2 − cc0 + c2 pd − c0 cpd c0 (1 − c − pd + c + cpd) = c2 + c2 pd 1 + pd c0 = c2 1 − pd + cpd c = 1−d ⇓ c0 = c2 1 + pd 1 − pd2 43 (4.12) http://www.doksihu With the help of c0 c1 can be expressed directly as well: c1 = d1 qc0 + (qc + pd)c1 + (q + pd)c vX max ! cβ β=2 vX max cβ = c − c0 − c1 β=2 c1 =     dq c0 d + c2 + pd2 c(c − c0 )  c1 = c2 d q = 1−p ⇓ c1 = c1 = c1 = c1 = 1 − pd2 + cpd2   1 (q − pc)(1 + pd)d + (q + pd)(1 − pd2 ) 1 − pd2 1 − pd2 + cpd2     pd − (1 − d)(1 + pd) − pd2 + q + d  1 2   cd 1 − pd2 1 − pd2 + cpd2     pd (1 − p)d − 1 + q + d  c2 d  (1 − pd3 )(1 − pd2 )   pqd2 + q + (1 − p)d 2 cd (1 − pd3 )(1 − pd2 )   1 + d + pd2 2 c dq (4.13) (1 − pd3 )(1 − pd2 )  For α > 1 a recursion relation

cα − dcα−1 can be derived: cα − dcα−1 = d α vX max qcα−1 + (qc + pd)cα + (q + pd)c cβ β=α+1 −qcα−2 − (qc + pd)cα−1 − (q + pd)c  cα = cα = ! cβ β=α dα qcα−1 − qcα−2 − (qc + pd)cα−1 + dcα−1 c = 1−d ⇓  vX max 1 − dα (qc + pd) + dα (q + pd)c 1 + (q − p)dα qdα dc − cα−2 , 2 ≤ α ≤ vmax−2 (4.14) α−1 1 − pdα+2 1 − pdα+2 After calculating c0 , c1 one can determine cα recursively. Using the last two equations 44 http://www.doksihu of Equation (5.11) we get the following for cvmax −1 and cvmax : 1 − qdvmax qdvmax −1 cvmax −2 1 − dvmax −1 (q + pd) qdvmax = cv −1 1 − qdvmax max cvmax −1 = cvmax (4.15) (4.16) At this stage we are ready to calculate the expected value of velocity, which will come very handy for us as we shall see. Definition 4.102 If the possible values of a discrete random variable X are x1 , x2 , x3 , and P (X = xk ) = pk , then the sum ∞ X xk p

k (4.17) k=1 is called the expected value of X, denoted by E(X). As already described in Section (2.4) we are mainly interested in the flow as a function of density (flow = speed × density). All the work we have been doing so far will make sense now because if we assume that we can think of the probability cα as the relative frequency of cars driving with velocity v = α we can write that the flow f (c, p) is defined by: f (c, p) = vX max αcα (4.18) α=1 Note that equation (4.18) is the expected value of the velocity since for α = 0 we would receive 0 in the sum above thus it is sufficient enough to start from α = 1. Let us calculate the f (c, p) for vmax = 5. Interesting enough the value of vmax does not affect our results for the value of f (c, p) a closed formula can be formulated with help of the generating function for arbitrarily high vmax 1 . In order to calculate the flow 1 See further in Appendix A 45 http://www.doksihu we need to determine the probabilities

for X = 0, 1, 2, 3, 4, 5. Results are as follows: 1 + pd 1 − pd2 1 + d + pd2 = c2 dq (1 − pd3 )(1 − pd2 ) qd2 1 + (q − p)d2 dc − c0 = 1 1 − pd4 1 − pd4 1 + (q − p)d3 qd3 = dc − c1 2 1 − pd5 1 − pd5 1 − pd5 = qd4 c3 1 − d4 (q + pd) qd5 = c4 1 − qd5 P (X = 0) = c0 = c2 (4.19) P (X = 1) = c1 (4.20) P (X = 2) = c2 P (X = 3) = c3 P (X = 4) = c4 P (X = 5) = c5 (4.21) (4.22) (4.23) (4.24) Thus the expected value takes the following form: 1 + d + pd2 + (1 − pd3 )(1 − pd2 )   1 + (q − p)d2 qd2 +2 × dc1 − c0 + 1 − pd4 1 − pd4   1 + (q − p)d3 qd3 dc2 − c1 + +3 × 1 − pd5 1 − pd5   1 − pd5 4 qd c3 + +4 × 1 − d4 (q + pd)   qd5 +5 × c4 1 − qd5 E(X) = c2 dq (4.25) The Octave script in Appendix D calculates and plots the expected values for p = 0.1 and various d densities. Putting our simulation results and the values of the expected value on the same diagram gives us Figure (4.2): With this diagram we are ready to jump to the

concluding part of our work. Figure (42) basically depicts that the mean field approximation of the model indicates a smoother fundamental diagram then the simulation results. The max point of the fundamental diagram for the simulation results with no lane changing and the max point of our approximation results coincide in terms of density and the max value is almost identical in both cases, with the simulation result having a slightly higher value. But what is more interesting for us is that the approximation results attain a higher flow than the the simulation results with lane changing for every single density value. This fact further 46 http://www.doksihu Figure 4.2: Displaying both simulation and MFA results supports our assumption about the effectiveness of the two possible traveling styles, namely that rash lane changing reduces the throughput of the road systems. 47 http://www.doksihu Chapter 5 5.1 Conclusion In this thesis we have demonstrated how undergraduate

mathematics can be used to investigate real world phenomena. Initially we have observed that there is an anomaly called spontaneous traffic jams present on our highways, which is worthwhile investigating. After that we have used our knowledge to select a traffic model that allows us to effectively conduct our examination of the phenomenon. We then have tailored this model to serve our needs and have applied our knowledge in programming, probability theory and statistics to develop and prove a hypothesis. Stating that the hotheaded driving maneuver of a few individuals greatly contributes to the creation of spontaneous traffic congestion and thereby drastically increases the traveling times of every individual on the road. The mean field approximation and the simulation program proved to be powerful tools when it comes to investigating complex probabilistic systems. The most spectacular manifestation of malfunctioning settlement operations is the aggregation of daily traffic congestion,

which is continuously expanding in time and space [20]. This means that in the past traffic jams were only occurrences during rush hour, and concentrated around the downtown area; whereas nowadays traffic jams take up a much larger area making it dysfunctional for a longer period of time. As we think about the factors influencing traffic we will find that there are some that affect traffic to a larger degree and some, which have less of an impact; thereby some of these factors are easier to influence and some of them are more difficult. This implies that any research trying to explore the driving elements behind traffic congestion comes to the conclusion that traffic congestion is strongly stochastic in nature, and very complex in its dynamics. When examining the results of traffic 48 http://www.doksihu congestion mitigation and its effects on society one must take into consideration the different habits and life styles of individuals, which may change over time. We can see how

complex the dynamics of even a single lane road can be. One can imagine what a challenge traffic organization in a larger more dense, more intensely traveled settlements is. Since in these larger settlements paradoxically not only progress of cars but also their ability to stop and park may also be challenging. Parking and storage of cars is difficult solely because of their space intensive nature. Nonetheless, a good thought to take away from this thesis, is that without the actual investment in infrastructure and by merely enforcing efficient use of roadways, their capacity can be increased measurably. This observation increases the importance of the rules of the road and the traffic code and their rigorous enforcement To be more specific, simulation results have shown us that undisciplined overtaking drastically reduces the throughput of the road segments; thus for instance the rules of the road that regulate the distance between vehicles on the road and during lane changing can

have positive effects on the effective use of the roadway. In some countries, for example in Germany, highway police are authorized to take action when vehicles proceed to close to each other on the highway. In conjunction with speed traps police also deploy equipment to measure the effective distance between vehicles traveling on the highways. Influencing driver habits positively may be a labor intensive task, nonetheless it looks to be a profitable endeavor where there is still room for further improvement. 49 http://www.doksihu Appendix A MFA for vmax ∞ Let us define the following generating function: g(z) = ∞ X z α cα (A.1) α=0 Using Equations (5.12-514) we can obtain a closed form of g(z) [23]: g(z)[1 − dz] − g(dz)d2 (1 − z)[p + qz] = c2 + pc2 d(1 − z) (A.2) The densities of the fast vehicles go to zero rapidly, since one expects an exponentially fast decay from the recursion relations (5.14-516) The contributions from fast cars thus are negligible. Here

since vmax ∞ one does not have to take into account the upper boundary Equations (5.15-516) since the contribution of cvmax −1 and cvmax is negligible. One has to deal with the different arguments of g z and dz After differentiating and substituting for g 0 (1) = f (c, p). Finally we receive an asymptotic expression of the form: f (c, p) = qcd 1 + ∞ X n=1 d2n n−1 Y ! (p + qdl ) (A.3) l=0 for f (c, p). With the help of (520) we can express the flow as a function of vehicle concentration c and of deceleration probability p. 50 http://www.doksihu Appendix B Time evolution equations two lane MFA Just like in the one lane version taking into account the update rules in Section (3.1) we can derive the following set of equations denoting the time evolution of the cα (i, j, t), i ∈ {0, 1}, j ∈ {0, 1, 2, . , S −1}, t ∈ {0, 1, 2, 3, , n, , ∞} probability distributions: • Acceleration stage c0 (i, j, t1 ) = 0 cα (i, j, t1 ) = cα−1 (i, j, t), 0 < α

< vmax (B.1) cvmax (i, j, t1 ) = cvmax (i, j, t) + cvmax −1 (i, j, t) • Lane changing stage c0 (i, j, t2 ) = c0 (i, j, t1 ) cα (i, j, t2 ) = cα (i, j, t1 ) + d(i, j, t1 ) × α X cα (i + 1 mod 2, j, t1 ) × l=1 l−1 Y × (B.2) !! d(i + 1 mod 2, j + k, t1 )c(i + 1 mod 2, j + l, t1 ) k=1 0 < α ≤ vmax 51 http://www.doksihu • Deceleration stage c0 (i, j, t3 ) = c0 (i, j, t2 ) + c(i, j + 1, t2 ) vX max cβ (i, j, t2 ) β=1 cα (i, j, t3 ) = c(i, j + α + 1, t2 ) α Y d(i, j + k, t2 ) k=1 + cα (i, j, t2 ) α Y vX max cβ (i, j, t2 ) β=α+1 d(i, j + k, t2 ), 0 < α < vmax (B.3) k=1 cvmax (i, j, t3 ) = vY max d(i, j + k, t2 )cvmax (i, j, t2 ) k=1 • Randomization stage c0 (i, j, t4 ) = c0 (i, j, t3 ) + pc1 (i, j, t3 ) cα (i, j, t4 ) = qcα (i, j, t3 ) + pcα+1 (i, j, t3 ), 0 < α < vmax (B.4) cvmax (i, j, t4 ) = qcvmax (i, j, t3 ) • Motion stage cα (i, j, t + 1) = cα (i, j − α, t4 ), 0 ≤ α ≤ vmax (B.5) After

proving the stationarity of the system we could use the same technique we have applied in the one lane model to conduct the mean field approximation and arrive at a closed formula for the flow of the system. 52 http://www.doksihu Appendix C Source Code of trfc ring100.cpp /* * trfc ring.cpp * * Copyright 2010 Mátyásfalvi György User <george@george-laptop> * * This program is free software; you can redistribute it * and/or modify * it under the terms of the GNU General Public License as * published by * the Free Software Foundation; version 2 of the License. * * This program is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. * GNU General Public License for more details. See the * * You should have received a copy of the GNU General Public * License * along with this program; if not, write to the Free Software * Foundation,

Inc., 51 Franklin Street, Fifth Floor, Boston, * MA 02110-1301, USA. */ 53 http://www.doksihu #include <algorithm> #include <ctime> #include <cstdlib> #include <fstream> #include <iostream> #include <vector> using namespace std; vector<int> cpos jam(int L[][100]) { vector<int> wc jam; for(int i=0; i<2; i++) { for(int j=1; j<100; j++) { if(L[i][j]==0) { wc jam.push back(j); } } } return wc jam; } int deceleration(int L[][100], int row, int column) { int m, dec, dist=0, c; for(m=column+1; m<column+L[row][column]+1; m++) { c=m%100; if(L[row][c]==-1) { dec=0; dist+=1; 54 http://www.doksihu } else { dec=L[row][column]-dist; m=column+L[row][column]+1; } } return dec; } int lnch(int L[][100], int row, int column) { int m, pos, c; for(m=column+1; m<column+L[row][column]+1; m++) { c=m%100; if(L[row][c]!=-1) { switch(row) { case 0: if(L[1][column]==-1) { pos=1; } else { pos=row; }; break; case 1: if(L[0][column]==-1) {

pos=0; } else { pos=row; }; break; } m=column+L[row][column]+2; } 55 http://www.doksihu else { pos=row; } } return pos; } int motion(int L[][100], int row, int column) { int pos; pos=column+L[row][column]; if(pos>99) { pos=pos%100; } return pos; } int num jam(int L[][100]) { int n jam=0; for(int i=0; i<2; i++) { for(int j=1; j<100; j++) { if(L[i][j]==0) { n jam+=1; } } } return n jam; } void randomization(int L[][100], float p) 56 http://www.doksihu { for(int i=0; i<2; i++) { for(int j=0; j<100; j++) { float rand num = (float) rand()/RAND MAX; if(L[i][j]>0 && rand num<p) { L[i][j]=L[i][j]-1; } } } } vector<int> rpos jam(int L[][100]) { vector<int> wr jam; for(int i=0; i<2; i++) { for(int j=1; j<100; j++) { if(L[i][j]==0) { wr jam.push back(i); } } } return wr jam; } int rws(int L[][100], float N) { float rws=0; float sumspeed=0; for(int i=0; i<2; i++) { for(int j=1; j<100; j++) { if(L[i][j]>0) { sumspeed+=L[i][j]; 57

http://www.doksihu } } } rws=sumspeed/N; return rws; } int main(int argc, char* argv) { //Initialization ofstream outtraffic("traffic.txt"); ofstream outcontrol("control.txt"); ofstream avv("avv.txt"); ofstream jpos("jpos.txt"); ofstream numjam("numjam.txt"); ofstream lnchng("lnchng.txt"); ofstream df("df.txt"); ofstream rdec("rdec.txt"); // T=total number of jams; D=density; // P=probability of random deceleration; G=guidance int v max=5; int v init=3; int iter in=1000; float iter out=100; float density=0; float p; cout<<"Enter probability 0<=p<=1 for random deceleration"<<endl; cin>>p; int g; 58 http://www.doksihu cout<<"Enter guidance 0 for normal flow 1 for flow with lane changing"<<endl; cin>>g; int L1[2][100]; int L2[2][100]; srand((unsigned)time(NULL)); for(float s=0; s<iter out; s++) { float sumrws=0; float avvt=0; float flow=0;

int sumnumlnch=0; int total n jam=0; int occupancy; density=(s/100); occupancy=200*density; //Init L1 for(int i=0; i<2; i++) { for(int j=0; j<occupancy/2; j++) { L1[i][j]=v init; } } for(int i=0; i<2; i++) { for(int j=occupancy/2; j<100; j++) { L1[i][j]=-1; } } 59 http://www.doksihu //Init L2 for(int i=0; i<2; i++) { for(int j=0; j<100; j++) { L2[i][j]=-1; } } //Shuffle random shuffle( L1[0], L1[0]+99 ); random shuffle( L1[1], L1[1]+99 ); for(int t=0; t<iter in; t++) { outcontrol<<"Start"<<endl; for(int i=0; i<2; i++) { for(int j=0; j<100; j++) { if(L1[i][j]==-1) { outtraffic<<" ."; outcontrol<<" ."; } else { outtraffic<<L1[i][j]; outcontrol<<L1[i][j]; } } outtraffic<<endl; outcontrol<<endl; } outtraffic<<endl; outcontrol<<endl; //Acceleration for(int i=0; i<2; i++) { 60 http://www.doksihu for(int j=0; j<100; j++) { if(L1[i][j]!=-1 && L1[i][j]<v

max) { L1[i][j]=L1[i][j]+1; } } } outcontrol<<"Acceleration"<<endl; for(int i=0; i<2; i++) { for(int j=0; j<100; j++) { if(L1[i][j]==-1) { outcontrol<<" ."; } else { outcontrol<<L1[i][j]; } } outcontrol<<endl; } outcontrol<<endl; //Lane Changing if(g==1) { for(int i=0; i<2; i++) { for(int j=0; j<100; j++) { if(L1[i][j]!=-1) { L2[lnch(L1, i, j)][j]=L1[i][j]; } } } 61 http://www.doksihu for(int i=0; i<2; i++) { for(int j=0; j<100; j++) { L1[i][j]=-1; } } for(int i=0; i<2; i++) { for(int j=0; j<100; j++) { L1[i][j]=L2[i][j]; } } for(int i=0; i<2; i++) { for(int j=0; j<100; j++) { L2[i][j]=-1; } } outcontrol<<"Lane Changing"<<endl; for(int i=0; i<2; i++) { for(int j=0; j<100; j++) { if(L1[i][j]==-1) { outcontrol<<" ."; } else { outcontrol<<L1[i][j]; } } outcontrol<<endl; } outcontrol<<endl; } //Deceleration 62 http://www.doksihu

for(int i=0; i<2; i++) { for(int j=0; j<100; j++) { if(L1[i][j]>0) { L1[i][j]=L1[i][j]-deceleration(L1, i, j); } } } outcontrol<<"Deceleration"<<endl; for(int i=0; i<2; i++) { for(int j=0; j<100; j++) { if(L1[i][j]==-1) { outcontrol<<" ."; } else { outcontrol<<L1[i][j]; } } outcontrol<<endl; } outcontrol<<endl; //Randomization randomization(L1, p); outcontrol<<"Randomization"<<endl; for(int i=0; i<2; i++) { for(int j=0; j<100; j++) { if(L1[i][j]==-1) { outcontrol<<" ."; } else { outcontrol<<L1[i][j]; 63 http://www.doksihu } } outcontrol<<endl; } outcontrol<<endl; sumrws+=rws(L1, occupancy); //Car motion for(int i=0; i<2; i++) { for(int j=0; j<100; j++) { if(L1[i][j]!=-1) { L2[i][motion(L1, i, j)]=L1[i][j]; } } } //Reset L1 & L2 for(int i=0; i<2; i++) { for(int j=0; j<100; j++) { L1[i][j]=L2[i][j]; } } for(int i=0; i<2; i++) {

for(int j=0; j<100; j++) { L2[i][j]=-1; } } //Outadditional vector<int> row; 64 http://www.doksihu vector<int> column; row=rpos jam(L1); column=cpos jam(L1); total n jam+=num jam(L1); for(unsigned int i=0; i<row.size(); i++) { jpos<<row[i]<<","<<column[i]<<endl; } } avvt=sumrws/iter in; flow=avvt*density; avv<<avvt<<endl; numjam<<total n jam<<endl; lnchng<<sumnumlnch<<endl; df<<density<<","<<flow<<endl; } return 0; } 65 http://www.doksihu Appendix D Octave script for E(X) #! /usr/bin/octave -qf function f0 = c0 ( p, d, c ) f0 = (c^2) * ( (1+pd ) / ( 1-p(d^2)) ); endfunction function f1 = c1 ( p, q, d, c ) f1 = q*(c^2)d ( 1+d+p(d^2) ) / ( (1-p(d^3)) (1-p(d^2)) ); endfunction function f2 = c2 ( p, q, d, c ) f2 = ( ( 1+(q-p)*(d^2) ) / ( 1-p(d^4) ) ) d ( q(c^2)d ( 1+d+p*(d^2) ) / ( (1-p(d^3)) (1-p(d^2)) ) ) ( ( q(d^2) ) / ( 1-p(d^4) ) ) (c^2) * ( (1+pd ) / (

1-p(d^2)) ); endfunction function f3 = c3 ( p, q, c, d ) f3 = ( 1+(q-p)*(d^3) ) / ( 1-p(d^5) ) d ( ( ( 1+(q-p)*(d^2) ) / ( 1-p(d^4) ) ) d ( q(c^2)d ( 1+d+p*(d^2) ) / ( (1-p(d^3)) (1-p(d^2)) ) ) ( ( q(d^2) ) / ( 1-p(d^4) ) ) (c^2) * ( (1+pd ) / ( 1-p*(d^2)) ) ) - ( ( q(d^3) ) / ( 1-p(d^5) ) ) ( q*(c^2)d ( 1+d+p(d^2) ) / ( (1-p(d^3)) (1-p(d^2)) )); endfunction 66 http://www.doksihu function f4 = c4 ( p, q, c, d ) f4 = ( ( 1-q*(d^5) ) / ( 1-(d^4)(q+pd) ) ) q(d^4) ( ( 1+(q-p)*(d^3) ) / ( 1-p(d^5) ) d ( ( ( 1+(q-p)(d^2) )/ ( 1-p*(d^4) ) ) d ( q(c^2)d ( 1+d+p(d^2) ) / ( (1-p(d^3)) (1-p*(d^2)) ) ) - ( ( q(d^2) ) / ( 1-p(d^4) ) ) (c^2) ( (1+p*d ) / ( 1-p(d^2)) ) ) - ( ( q(d^3) ) / ( 1-p(d^5) ) ) ( q*(c^2)d ( 1+d+p(d^2) ) / ( (1-p(d^3)) (1-p(d^2)) ) ) ); endfunction function f5 = c5 ( p, q, c, d ) f5 = ( ( q*(d^5) ) / ( 1-q(d^5) ) ) ( ( ( 1-q(d^5) ) / ( 1-(d^4)*(q+pd) ) ) q(d^4) ( ( 1+(q-p)(d^3) ) / ( 1-p*(d^5) ) d ( ( ( 1+(q-p)(d^2) ) / ( 1-p(d^4) ) ) d* ( q(c^2)d (

1+d+p(d^2) ) / ( (1-p(d^3)) (1-p*(d^2)) ) ) - ( ( q(d^2) ) / ( 1-p(d^4) ) ) (c^2) * ( (1+pd ) / ( 1-p(d^2)) ) ) ( ( q(d^3) ) / ( 1-p(d^5) ) ) ( q(c^2)d ( 1+d+p*(d^2) ) / ( (1-p(d^3)) (1-p(d^2)) ) ) ) ); endfunction density = [ 0 0.01 002 003 004 005 006 007 008 009 01 0.11 012 013 014 015 016 017 018 019 02 021 022 0.23 024 025 026 027 028 029 03 031 032 033 034 0.35 036 037 038 039 04 041 042 043 044 045 046 0.47 048 049 05 051 052 053 054 055 056 057 058 0.59 06 061 062 063 064 065 066 067 068 069 07 071 0.72 073 074 075 076 077 078 079 08 081 082 083 084 0.85 086 087 088 089 09 091 092 093 094 095 096 097 0.98 099 ]; flow0 = [ 0 0.04748 00916 013458 017548 02138 025332 0.2926 033048 036711 04054 04444 048216 052052 056 0.59685 06304 059466 054864 056354 05618 054159 0.49148 04669 048 04995 051428 052002 049364 043065 67 http://www.doksihu 0.3618 032085 032096 033 034 035 036 037 037962 038922 0.3992 040918 041118 040936 036652 027495 016146 006063 0.01008 000049 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ]; flow1 = [ 0 0.04731 009188 013464 017464 021415 025422 0.29169 03324 03672 03975 040557 039636 039923 04074 0.39345 037008 035564 03618 03762 03886 038409 035552 0.30498 02748 0259 02613 027027 028 029 03 031 031936 0.32868 033286 03353 031608 03034 022952 017004 01016 0.03895 00105 000645 0 00009 000046 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ]; p=0.1; q=0.9; hold on for i=1:100 c=(1/100)*i; d=1-c; v1=c1(p,q,c,d); v2=c2(p,q,c,d); v3=c3(p,q,c,d); v4=c4(p,q,c,d); v5=c5(p,q,c,d); plot(c, E(v1,v2,v3,v4,v5), "@13" , "markersize", 4); endfor plot(density, flow0, "@22" , "markersize", 4); plot(density, flow1, "@31" , "markersize", 4); title ("blue approximation, green no lane changing, red lane changing; flows for p=0.1"); 68 http://www.doksihu xlabel

("density [cars per sites]") ylabel ("flow [cars per time step]") print sumflow 0.1 linejpg; hold off 69 http://www.doksihu Bibliography [1] Fundamental diagram for ca simulation. Online, 2010 Traffic Simulation with PLANSIM-T. [2] Grid coarse. Online, 2010 http://wwwmimsmanchesteracuk/research/numericalanalysis/fe-approximationhtml [3] Local government & municipal knowledge base. Online, 2010. http://www.lgaminfo/level-of-service [4] American Institute of Physics. Analytical Solution of Traffic Cellular Automata Model, Suite 1NO1 2 Huntington Quadrangle, August 2009. AIP Conference Proceedings. [5] Marton Balazs and Timo Seppalainen. Order of current variance and diffusivity in the asymmetric simple exclusion process. Ann Math, 171(2):619–647, 2010 [6] J. G Brankov, Vl V Papoyan, V S Poghosyan, and V B Priezzhev The totally asymmetric exclusion process on a ring: Exact relaxation dynamics and associated model of clustering transition. Physica A,

386:471–480, 2006 [7] Wlodzimierz Bryc. Probability and stochastic processes Cincinnati Free Texts, 1996 March. Department of Mathematics University of Cincinnati [8] B. Derrida An exactly soluble non-equilibrium system: The asymmetric simple exclusion process. Physics Reports, 301:65–83, 1998 [9] Michael Dörfler and Karl-Heinz Becker. Dynamical systems and fractals Mathematics Application of computer graphics Cambridge University Press, Cambridge, 1990 70 http://www.doksihu [10] Janosne Bognar et al. Matematikai statisztika Nemzeti Tankonyvkiado, Budapest, 1995 [11] Dirk Helbing and Martin Schönhof. Empirical features of congested traffic states and their implications for traffic modeling. Technical report, Institute for Economics and Traffic, Dresden University of Technology, Andreas-Schubert Str 23, 01062 Dresden, Germany, February 2008. [12] Sam Howison. Practical Applied Mathematics: Modelling, Analysis, Approximation Cambridge University Press, The Edinburgh Building,

Cambridge CB2 2RU, UK, 2005. [13] Bronowski J. The Ascent of Man, pages 348–349 Little, Brown, 1973 [14] W Knospe, L Santen, A Schadschneider, and M Schreckenberg. Towards a realistic microscopic description of highway traffic J Phys A: Math Gen, 33:477– 485, October 2000. [15] W Knospe, L Santen, A Schadschneider, and M Schreckenberg. A realistic twolane traffic model for highway traffic J Phys A: Math Gen, 35:3369–3388, April 2002. doi: 101088/0305-4470/35/15/302 [16] Reinhart Kühne. Fgsv merkblatt (entwurf) das fundamentaldiagramm - grundlagen und anwendungen Technical report, FGSV, October 2004 [17] Henry Lieu. Traffic-Flow Theory Public Roads (US Dept of Transportation), February 1999. [18] Tetsuya Mitsudo and Hisao Hayakawa. Synchronisation of kinks in the two-lane totally asymmetric simple exclusion process with open boundary conditions. J Phys. A: Math Gen, 38, 2005 [19] Kai Nagel and Michael Schreckenberg. A cellular automaton model for freeway traffic. J Phys I

France, 2:2221–2229, December 1992 Classification: Physics Abstracts 02.50 - 0270 - 0340G [20] Bela Nagy. A telepules , az epitett vilag. cal&technical) Lap- es Könyvkiado Kft., 2005 71 GEO Konyvek. B+V (medi- http://www.doksihu [21] Manfred Opper and David Saad, editors. Advanced Mean Field Methods: Theory and Practice. Neural Information Processing Series The MIT Press, Cambridge, Massachusetts, 2001. [22] Joel L. Schiff Cellular automata: a discrete view of the world Wiley series in discrete mathematics and optimization. John Wiley & Sons, Inc, Hoboken, New Jersey, 2008. [23] M. Schreckenberg, A Schadschneider, K Nagel, and N Ito Discrete stochastic models for traffic flow. Phys Rev E 51, page 2939, 1995 [24] M Stringer Scott. Thinking outside the box: an analysis of Manhattan gridlock and spillback enforcement. Office of Manhattan Borough President, July 2006 [25] Stephen Wiggins. Chaotic Transport in Dynamical Systems Springer Verlag, 209 edition, 1992. 72

http://www.doksihu Index ambient space, 11 Bethe ansatz, 18 CA, 13 mean velocity, 4 metastable state, 5 NaSch, 5, 10, 22 cellular automata, 5, 13 parallel, 13 cellular automaton, 13 phantom jam, 5 configuration, 14 density, 4, 5, 19 dimension, 13 discrete model, 13 dynamical system, 11 quiescent state, 13 random variables, 15 rules of the road, 49 safety criterion, 29 attractor, 12 sample space, 15 basin of attraction, 12 states, 13 orbit, 12 stationarity, 18 trajectory, 12 statistical test, 30 flow, 4, 9, 19 flux, 9 fundamental diagram, 4, 19 incentive criterion, 29 steady state, 16, 43 stochastic process, 15 synchronized state, 5 synchronously, 13 totally asymmetric exclusion process, 10, 16 level of service, 4 local transition function, 13, 22 traffic code, 49 argument, 13 transition point, 27 logistic equation, 12 trfc ring100.cpp, 24 Markov processes, 15 mean field approximation mean field methods, 33 73