2014年美國大學生數學建模MCM-A題-O獎論文31333.pdf

Team 31333 Page 1 of 17 1 Rules of the Road Using adaptations of Nagel Schreckenberg Cellular Automaton Traffic Simulations to Evaluate Passing Rules for Multi Lane Freeways Abstract We present three conventions for regulating the behavior of automobiles on a freeway as potential alternatives to the keep right except to pass rule that is currently established in the United States and in many other nations These conventions are tested against the established convention within a freeway traffic flow model we have designed based on Nagel Schreckenberg models of traffic flow We assume cars remain on the freeway and all drivers attempt to adhere to the rules of the road but sometimes make mistakes that can lead to accidents We also assume that an intelligent system controlling the actions of all cars on the roadway would not make those same mistakes The first of the three alternatives proposed presents drivers with no rules governing their lane to lane movement allowing them to move to any lane that will let them go faster and to stay there for exactly so long as that remains the case This convention results in the highest flow rate of cars through the system but also results in a higher accident rate for a typical three lane freeway than does the keep right except to pass rule However when the number of lanes is increased the accident rate drops significantly The second of the three alternatives forbids drivers from changing lanes at all and results in the second highest flow rate seen between the no rule and keep right except to pass systems but results in a higher accident rate than either system for typical three lane highways The third model mandating that drivers remain in the center lane of a three lane of five lane freeway exhibited the lowest flow rate and highest accident rate of any of the four conventions studied Unfortunately the model used was seen to be very sensitive to the rate governing accident probability and the number of lanes in a simulation The way accidents were modeled meant that a single accident tended to promote the occurrence of many more Additionally a software limitation in the function used to generate an initial matrix with unique car locations meant that it was impossible to create true gridlock within the model Based on the data from all of the models and the uncertainty in the accident data we conclude that a no rules convention would result in greater flow rate through a typical three lane freeway but that no convention is safer than the keep right except to pass rule supporting its status as the established rule in much of the world Team 31333 Page 2 of 17 2 1 Introduction Due to the high speed at which freeway traffic travels transport regulatory bodies impose rules on where in a multi lane freeway drivers should be at any given time with the purpose of maximizing the safety and efficiency of freeway travel One such rule which is commonly used in countries where automobiles drive on the right hand side of roads requires drivers to stay in the right most lane of the freeway unless they are attempting to pass another car Cars that attempt to pass are required to safely move to the left pass the car or cars they wish to pass and then return to their original lane An analogous rule can be used in countries such as the United Kingdom and Australia where automobiles are driven on the left hand side of the road In this paper we attempt to answer the question of whether or not the stay right except to pass rule is a safe and efficient method for controlling freeway traffic and compare it to three other rules that could be used to regulate traffic The three alternate rules have been called No Rules No Lane Changes and Middle Lane Rule and allow for free lane movement no lane movement and randomized lanes and free passing with mandatory return to the middle lane respectively The three rules were all implemented into the same cellular automaton traffic control model based on a model outlined by Nagel and Schreckenberg1 under a variety of traffic conditions with both heavy and light car density fast and slow speed limits and three different probabilities governing accident rates For each rule and traffic condition data was gathered on accident count and flow rate for 100 cell regions of 2 through 6 lane freeways across 250 time steps The results of these simulations are presented in Section 4 2 followed by a discussion of the limitations and assumptions of the model in Sections 4 3 and 5 2 Previous Work 2 1 Different Approaches to the Problem Modeling of traffic flow is by no means a new problem and many models have previously been used to describe and model the flow of traffic on various road types from cities to freeways The Wikipedia page on Traffic Flow 2 alone lists a huge number of model types and parameters that have been used in the past to describe traffic flow with both discrete and continuous methods for approaching the problem One model by Doboszczak and Forstall3 used partial differential equations to model traffic 1 M Schreckenberg et al Discrete Stochastic Models for Traffic Flow Physical Review E 51 no 4 April 1995 2939 2949 doi 10 1103 PhysRevE 51 2939 2 Traffic Flow Wikipedia the Free Encyclopedia February 8 2014 http en wikipedia org w index php title Traffic flow oldid 579155609 3 Stefan Doboszczak and Virginia Forstall Mathematical Modeling by Differential Equations University of Maryland October 9 2013 http www norbertwiener umd edu Education m3cdocs Presentation2 pdf Team 31333 Page 3 of 17 3 flow for average densities of cars rather than looking at each individual car These sorts of models use basic equations and assumptions to build up to more complex mathematical statements Another model by a group at MIT examined Phantom Traffic Jams4 and watched a group of cars and observed behaviors of traffic flow then empirically developed algorithms to display the phenomena they observed 2 2 The Nagel Schreckenberg Model The traffic model used in this paper was derived from the previous work by Kai Nagel and Michael Schreckenberg5 originally published in 1992 in which cars are placed into a one dimensional array wherein each cell may either be occupied or unoccupied and the car in each occupied cell will have an associated speed between zero and the assigned maximum speed for the system Multiple cars may not occupy the same cell and the model is governed by fours basic operations that are taken to occur simultaneously for each iteration These four steps are 1 Acceleration All cars that are not at the maximum velocity Vmax speed limit for the road and that have more than v 1 empty cells in front of them accelerate by one unit v v 1 2 Slowing Down for Safety If a car has d empty cells ahead of it and its velocity after step one is greater than d then it reduces it velocity to x v min d v 3 Randomization For cars with a speed greater than 0 the velocity is reduced by one unit with probability p V v 1 4 Driving After steps 1 3 the each car is assigned a new position x based on its current velocity v x x v Each car acts independently in the sense that the driver is concerned with reaching his or her own destination but any given car s actions are also based in response to the cars around it The model assumes that each driver wishes to drive as fast as allowable but also that drivers wish to avoid accidents It also introduces an element of imperfect to the control of the drivers by randomly reducing the speed of each car though it should be noted that as cars slow down in response to the position of the car in front of them rather than to its speed or expected position this randomness will never result in the creation of accidents It is also important to note that the model is designed for a single lane system and so cannot be used to answer the problem addressed in this paper without modification to account for the probability of lane changes 4 MIT Mathematics Traffic Modeling accessed February 9 2014 http math mit edu projects traffic 5 Schreckenberg et al Discrete Stochastic Models for Traffic Flow Team 31333 Page 4 of 17 4 3 Model 3 1 Simplifying Assumptions A simulation of a small number of cars in a small pre defined region can be taken to be representative of an entire freeway No cars entered or exited the highway during each simulation that is the number of cars remained constant for each simulation and therefore that the car density on the studied region remained constant for the entire simulation All cars were identical and they were separated by integer multiples of the cell length Differing weather conditions can be accounted for by modifying the probability that governed accident rates The reaction times of drivers to impending accidents are different for every driver and take random values All accidents were taken to occur between two cars and have the same effect on traffic in their lane All cars return to the system after their accident is cleared The first assumption is necessary due to the fact that simulating large numbers of cars over a large distance is computationally expensive and requires a complex system for measuring traffic flow which may differ significantly along the length of the region This assumption is one that has been previously made and discussed in a paper by Courage et al 6 wherein cars were taken to be members of small platoons that travelled together The second and third assumptions are inherent in the Nagel Schreckenberg model on which ours is based and is also necessary due to limited available computing power Simulation of variable cell lengths and variable densities and car counts within each simulation would have been extremely resource intensive for the style of model used The fourth assumption was made due to the fact that the model does not explicitly consider how different weather conditions affect the accident rate on the freeway despite the fact that weather conditions certainly do change driving conditions in regards to accidents a great deal If asked to describe how each rule works in heavy rain or snowy conditions we would address its performance under a condition that simulated high accident rates The fifth assumption was used to allow drivers in individual cars to prevent an accident from occurring There was to be a fixed value for reaction time that was required in order to prevent a dangerous speed up and each driver would randomly be assigned a reaction time to each incident Benekohal and Treiterer present a justification for the use of random reaction times in their 1988 paper on their model CARSIM7 While their 6 Kenneth G Courage Charles E Wallace and Rafiq Alqasem MODELING THE EFFECT OF TRAFFIC SIGNAL PROGRESSION ON DELAY Transportation Research Record no 1194 1988 http trid trb org view aspx id 302135 7 J Treiterer R F Benekohal CARSIM Car Following Model for Simulation of Traffic in Normal and Stop and Go Conditions Transportation Research Record 1988 99 111 Team 31333 Page 5 of 17 5 model for assigning random reaction times is far more sophisticated and data based than our own the reasons for using random reaction times remains the same The sixth and final assumption was another assumption that significantly reduced the amount of time required for each simulation Though it would be possible for a car to collide with a car that had already collided with another creating a three car pileup cars were assumed to never engage in a simultaneous three car collision and cars were assumed not to collide with cars in other lanes This concept specifically will be discussed in detail when discussing limitations of the model in Section 5 3 2 The Model The model we designed to compare the effectiveness of the different driving conventions used the concept of cells from the Nagel Schreckenberg model and then added to the model to fit our needs Our simulation of driving conditions was done by performing various operations on an n by 3 matrix where n was the number of cars in the simulation Each row in the matrix represented a car where the first column s entry was the cell number of the car s location the entry in the second column was the lane that car was located in and the third column s entry was the current speed of that car The largest change made from the Nagel Schreckenberg system was the modeling of multi lane systems necessary for the comparison of lane switching strategies It was made possible for multiple cars to occupy the same cell number provided they had different lane numbers The movement of the cars was studied on short 100 cell regions with a mechanism implemented to count the number of cars that left the 100 cell region and return them to the region in cell 1 A separate system counted the number of accidents that occurred in the timeframe of a simulation and to lock down lanes behind accidents forcing other cars to switch lane or stop and wait for the accident to clear Accidents themselves occur due to a randomization step that was modified from the Nagel Schreckenberg randomization step In the original randomization step every car had fixed probability of randomly slowing down which as previously noted would never cause accidents to be simulated in the system In our model the cars have a fixed probability of randomly speeding up potentially causing them to rear end the car in front of them Additionally all the drivers will randomly respond to each potential accident and will either succeed or fail in preventing the accident from occurring as discussed in Section 3 1 Though the explicit step sequence differed for each rule within our model the general sequence of steps in the cellular automaton traffic simulation each of which modifies the n by 3 matrix discussed above was as follows 1 Acceleration All cars that are not at the maximum velocity Vmax speed limit for the road and that have more than v 1 empty cells in front of them accelerate by one unit v v 1 2 Lane Changing If a car has d empty cells ahead of it and its velocity after step one is greater than d and there is no adjacent car preventing lane changes as Team 31333 Page 6 of 17 6 allowed by the rule system the car will move over one lane and then repeat this step until no further productive lane movement is possible In the Right Hand Rule system cars can only move left in this step while in the No Rules and Middle Lane Rule systems the cars were free to move either left or right In the No Lane Changes system this step is skipped Lane Lane 1 3 Slowing Down for Safety If a car has d empty cells ahead of it and its velocity after step one is greater than d then it reduces it velocity to x v min d v 4 Randomization For cars with a speed less than Vmax the velocity is increased by one unit with probability p v v 1 5 Driving After steps 1 4 the each car is assigned a new position x based on its current velocity v x x v 6 Exit Count and Car Cycling If after moving a car is in a cell number above 100 having previously been in a cell number less than or equal to 100 the count of cars that have gone through the system will increase by 1 and if there is an open lane in cell 1 the car will be placed in it If there is no open lane the car is recycled at a later time step Throughput Throughput 1 Cell 1 7 Check for and Respond to Accidents If two cars are found to be in the same lane and cell the count of accidents is increased by one and their velocities are set to different negative numbers As all steps other than Acceleration ignore cars with a negative value for speed this will freeze the cars in their accident position for a fixed amount of time taken to be the amount of time to clear the accident and return the cars to the road Accidents Accidents 1 v 1 or 5 8 Return to Designated Start Lane This step is only applied to the Right Hand Rule system and the Middle Lane rule system For each car the model checks whether or not the car is in its designated start lane 1 for Right Hand Rule and 2 or 3 for Middle Lane Rule and if the car is in the wrong lane and if there is no car adjacent to it in the direction of its start lane the car will move one step toward its start lane It will then repeat this step until it is no longer possible for it to move closer to its start lane Lane Lane 1 The model was built in MATLAB as a series of scripts to perform the functions described above with at least one script per step and multiple scripts for steps that varied in different rule systems that could be inserted into a function in a modular fashion so as to simply create a function capable of running the model several times and averaging data for each of the four rule systems Team 31333 Page 7 of 17 7 4 Results 4 1 Description of Parameters and Terminology All of the data presented are the result of averaging the results of ten simulations of the model for each rule system A single simulation is defined as being 250 time steps of the model evaluated on a 100 cell region The required reaction time for a driver to prevent an accident was fixed such that any given driver would succeed 30 of the time All other parameters were considered variable and tests were performed with every possible combination of conditions Vmax Fast For a fast speed limit Vmax is set equal to 6 cells per time step Slow For a slow speed limit Vmax is set equal to 2 cells per time step Rate of Random Speed Increase Potentially Resulting in Accidents Computer The probability of random speed changes being manually set to zero which also mean the probability of an accident is zero Accident Prone The probability of any given car speeding up in any given time step is 0 3 Normal The probability of any given car speeding up in any given time step is 0 01 Traffic Density Heavy Large number of cars in the region which we have defined as 100 cars Light Small number of cars in the region which we have defined as 30 cars For each of the 5 lane numbers in each of the four rule systems the Average Flow Rate is calculated by averaging the total number of cars tha