276 The UMAP Journal 22.3 (2001) 40000000080001000001200001400000008000200000 N 8 gure 1. Comparison of minimum evacuation time(lower line)and maximum flow evacuation me(upper line One-Dimensional Cellular automata model Development In heavy traffic, cars make repeated stops and starts, with somewhat arbi each time state, cars move according to the following rules ella ness into trary timing a good model of heavy traffic should take this randomness into account but also be simple enough to give an explicit formula for speed We divide a single-lane road into cells of equal length. A ontains one car or no car. A car is blocked if the cell directly in front of it is occupied. At . a blocked car does not move If a car is not blocked, it advances to the next cell with probability p The decisions of drivers to move forward are made independently A traffic configuration can berepresented by a functionf: Z-10, 1, where f(k)= l if cell k contains a car and f(k)=0 if not. Probability distributions on the set of all such functions are called binary processes
276 The UMAP Journal 22.3 (2001) Figure 1. Comparison of minimum evacuation time (lower line) and maximum flow evacuation time (upper line). One-Dimensional Cellular Automata Model Development In heavy traffic, cars make repeated stops and starts, with somewhat arbitrary timing; a good model of heavy traffic should take this randomness into account but also be simple enough to give an explicit formula for speed. We divide a single-lane road into cells of equal length. A cell contains one car or no car. A car is blocked if the cell directly in front of it is occupied. At each time state, cars move according to the following rules: • A blocked car does not move. • If a car is not blocked, it advances to the next cell with probability p. The decisions of drivers to move forward are made independently. A traffic configuration can be represented by a functionf : Z → {0, 1}, where f(k)=1 if cell k contains a car and f(k)=0 if not. Probability distributions on the set of all such functions are called binary processes
Traffic Flow Models 277 Given a process X, define a process Ip(X) according to the following rule X(i),X(i+1)=(1,0 then (Ip (X)(), IP()(+1))=1(0, 1), with probability p; (1,0), with probability 1-p This rule is identical to the traffic flow rule given above: If X represents the traffic configuration at time t, Ip(X) gives the traffic configuration at timet+1 We are interested in what the traffic configuration looks like after several iterations of I. Let Ip(X)mean Ip applied n times to X. The formula for traffic speed in terms of density comes from the following theorem Theorem. Suppose that X is a binary process of density d. Let 1-1-4d(1-d)p 2pd and let Mp, d denote the Markov chain with transition probabilities prob. 1 1, w/prob. r The sequence of processes X, Ip(X), IF(X), IS(X),.. converges to Mp. d Here"density"means the frequency with which Is appear, analogous to the averagenumber of cars per cell. This theorem tells what the traffic configuration looks like after a long period of time Knowing the transition probabilities allows us to compute easily the average speed of the cars in Mp. d: the average speed is the likelihood that a randomly chosen car is not blocked and advances to the next cell at the next time state Pr[(Mp, d(i))=0p, (i)=1 Prp, d(i+1=0 Mp, d(i=1] Pr[I(Mp. d(i))=0Mp d(i)=l and Mp, d(i+1)=o 7=(1-1-01=)p=1-4=D.a The model does not accurately simulate high-speed traffic and does not take into account following distance, and the stop-and-start model of carmovement is not accurate when traffic is sparse. The model is best for slow traffic(under 15 mph)with frequent stops IThis theorem is the result of previous research [Miller 2001] by an author of this paper. The Appendix on binary processes(written during the contest period) gives a relatively complete prod of the result. [EDITOR'S NOTE: We unfortunately must omit the Appendix J
Traffic Flow Models 277 Given a process X, define a process Ip(X) according to the following rule: If X(i), X(i + 1) = (1, 0) then Ip(X)(i), Ip(X)(i + 1) = (0, 1), with probability p; (1, 0), with probability 1 − p. This rule is identical to the traffic flow rule given above: If X represents the traffic configuration at time t, Ip(X) gives the traffic configuration at time t+ 1. We are interested in what the traffic configuration looks like after several iterations of I. Let In p (X) mean Ip applied n times to X. The formula for traffic speed in terms of density comes from the following theorem1: Theorem. Suppose that X is a binary process of density d. Let r = 1 − 1 − 4d(1 − d)p 2pd and let Mp,d denote the Markov chain with transition probabilities 0 −→ 0, w/ prob. 1 − r; 1, w/ prob. 1 − r; 1 −→ 0, w/ prob. r; 1, w/ prob. r. The sequence of processes X, Ip(X), I2 p (X), I3 p (X),... converges to Mp,d. Here ìdensityî means the frequency with which 1s appear, analogous to the average number of cars per cell. This theorem tells what the traffic configuration looks like after a long period of time. Knowing the transition probabilities allows us to compute easily the average speed of the cars in Mp,d: the average speed is the likelihood that a randomly chosen car is not blocked and advances to the next cell at the next time state: v = P r [I(Mp,d(i))=0 |Mp,d(i) = 1] = P r [Mp,d(i + 1)=0 |Mp,d(i) = 1] · P r [I(Mp,d(i))=0 |Mp,d(i)=1 and Mp,d(i + 1) = 0] = rp = 1 − 1 − 4d(1 − d)p 2pd p = 1 − 1 − 4d(1 − d)p 2d . (2) The model does not accurately simulate high-speed traffic and does not take into account following distance, and the stop-and-start model of car movement is not accurate when traffic is sparse. The model is best for slow traffic (under 15 mph) with frequent stops. 1This theorem is the result of previous research [Miller 2001] by an author of this paper. The Appendix on binary processes (written during the contest period) gives a relatively complete proof of the result. [EDITORíS NOTE: We unfortunately must omit the Appendix.]