建模优秀特等奖2014年上交a

1、2014 MCM Outstanding Winners MCM2014#25142上海交通大学，m C史ontr昭ol N阳um，berFor office use onlyFor office use onlyF1 校苑数模251网42全球首发T1 T2 T3 T4 F3 F4 A2014ing (MCM/ICM) Summary SheetBased on CellularMathematical Contest in Mway Traffic MAutomata and Monte-Carlo MethodSummaryBased on Cellular Automata and Mo

2、nte-Carlo method, we build a mto discuss theinfluence of the “Keep right except to pass” rule. First we break down the process of vehiclemovement and establish corresponding sub-ms, inflow mfor car-generation,vehicle-following mfor one vehicle following another, and overtaking mfor onevehicle passin

3、g another.Then we design rules to simulate the movement of vehicles in sub-ms. We furtherdiscuss rules for our mto adapt to the keep right situation, the unrestricted situation,and the situation where transportation is controlled by intelligent system. We also design aformula to evaluate the danger

4、index of the road.We simulate the traffic on two-laneway (two lanes per direction, four lanes intotal), and three-laneway three lanes per direction, six lanes in total) via computer andanalyze the data. We record the average velocity, overtaking rate, road density and dangerindex and assess the perf

5、ormance of the keep-right rule by comparison with theunrestricted rule. We vary the upper speed limitations to analyze the sensitivity of themand see the impacts of different upper speed limits. Left-hand traffic is also discussed.Based on our analysis, we come up with a new rule combining the two e

6、xisting rules(the keep-right rule and the unrestricted rule) for an intelligent system to achieve betterperformance.感谢作者，请注明来源：校苑数模网作者拥有2014 MCM Outstanding Winners MCM2014#25142上海交通大学，史昭阳，校苑数模网全球首发Team # 25142 Page 2 of 341Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

7、 . .4551.11.2Terminology . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .Assumptions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .2The Ms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .6678101010111313142.12.22.32.4Design of Cellular Automata. . . . .

8、 . . . . . . . . . . . . . .Inflow M. . . . . . . . . . . . . . . . . . . . . . . .Vehicle-Following M. . . . . . . . . . . . . . . . . . .Overtaking M. . . . . . . . . . . . . . . . . . . . . . . . .2.4.12.4.22.4.3Overtaking Probability. . . . . . . . . . . . . . . . . . . .Overtaking Condition . .

9、 . . . . . . . . . . . . . . . . . . .Danger Index. . . . . . . . . . . . . . . . . . . . . . . . .2.5Two Sets of Rules for CA M. . . . . . . . . . . . . . . . . . . .2.5.12.5.2Keep Right Except to Pass Rule . . . . . . . . . . . . . . . .Unrestricted Rule . . . . . . . . . . . . . . . . . . . . . .

10、 . .3Supplementary Analysis on the M. . . . . . . . . . . . . . . . . .143.1Design of the Acceleration and Deceleration Probability Distribu- tions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .Design to Avoid Collision . . . . . . . . . . . . . . . . . . . . . . .14143.24MI

11、mplementation with Computer . . . . . . . . . . . . . . . . . .155Data Analysis and MValidation . . . . . . . . . . . . . . . . . . .16165.1Average Velocity. . . . . . . . . . . . . . . . . . . . . . . . . . . .2014 MCM Outstanding Winners MCM2014#25142上海交通大学，史昭阳，校苑数模网全球首发Team # 25142Page 3 of 345.2

12、5.35.45.5AverDensity. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .17181919Overtaking Rate . . . . . . . . . . . . . . . . . . . . . . . . . . . . .Danger Index. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .6Sensitivity Evaluation of the Munder Different Speed L

13、imitations207Driving on the Left . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .218Transportation under Intelligent System . . . . . . . . . . . . .212122238.18.28.3New Rule for Intelligent System . . . . . . . . . . . . . . . . . .Adaption of the M. . . . . . . . . . . . . . . . . . .Re

14、sult of Intelligent System . . . . . . . . . . . . . . . . . . . .9s . . . . . . . . . . . . . . . . . . . . . . . . . . . . .2310Strengths and Weaknesses. . . . . . . . . . . . . . . . . . . . . . . . .10.1 Strengths . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .10.2 Weakness . . . .

15、 . . . . . . . . . . . . . . . . . . . . . . . . . . . . .252525References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .26Appendices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .262014 MCM Outstanding Winners MCM2014#25142上海交通大学，史昭阳，校苑数模网全球首发Team

16、 # 25142Page 4 of 341IntroductionToday, about 65% of the worlds population live in countries with right-hand traffic and 35% in countries with left-hand traffic. worldstandards.eu,2013 Incountries with right-hand traffic, like USA and, regulations request driv-ing and walking keep to the right side

17、of the road. Multi-lane ways in these countries often employ a rule that requires drivers to drive in the right-most lane unless they are passing another vehicle, in which case they move one lane to the left, pass, and return to their former travel lane. This rule on driving and overtaking is referr

18、ed to as the ”Keep right except to pass” rule, or the keep-right rule in our paper. The rule in countries with left-hand traffic is exactly mirror symmetrical to the keep-right rule(”Keep left except to pass”). So, whats the purpose of applying such a rule? Does the keep-right rule ameliorate theway

19、 traffic condition? Transportationof the restriction of the keep-rightrule (Vehicles can choose either side for overtaking.) is referred to as obeying the unrestricted rule. How does the keep-right rule perform comparing with the unrestricted rule?Based on the Cellular Automata mand the Monte Carlo

20、algorithm, weestablish a mto simulateway traffic under different conditions (underthe keep-right rule or the unrestricted rule, in light traffic or in heavy traffic,2-lane or 3-lane per direction). Our mis divided into 3 sub-ms the in-flow m, the vehicle-following mand the overtaking m. The inflowme

21、mploys the Poisson probability distribution for the simulation of thevehicle-generation process. The vehicle-following mintroduces a specialprobability distribution mwhich makes the simulation of the process of acar following another more realistic. The overtaking msimulates the over-taking behavior

22、 and defines the danger index to evaluate the safety risk of acertainway. We also build an extended m control of an intelligent system.for transportation under theWe implement the min, and obtain sufficient data. We test theaverage velocity, the density, the overtaking rate and the danger index, ana

23、lyze their properties and assess the performance of the keep-right rule by comparison with the unrestricted rule. In addition, we analyze the sensitivity of our munder different speed limits. It turns out that our mis robust.Then we cours which consist with common sense. Wealso put forward a new rul

24、e for transportation under the control of an intelligent system.2014 MCM Outstanding Winners MCM2014#25142上海交通大学，史昭阳，校苑数模网全球首发Team # 25142Page 5 of 34 Table 1: NotationSymbolMeaningcurrent velocity of the vehicle um velocity of the vehiclethe upper speed limit of theway the velocity before overtakin

25、gthe velocity in the overtaking processthe distance between a vehicle and the vehicle ahead of it the minimum gap required for safety considerationthe minimum gap after the vehicle stops PIEV time(human reaction time)the overtaking probability the acceleration probability the deceleration probabilit

26、ythe frictional force when braking danger index in one overtaking event danger index of the road systemthe acceleration during overtakingthe component parallel to the lane of acceleration during overtaking the available decelerationVVm Vl V0 V1 GGs G0TrPo Pa Pb f d Da ap ad1.1TerminologyTwo-lane roa

27、d: Two lanes on right-half of the road, four lanes in total.Three-lane road: Three lanes on right-half of the road, six lanes in total.Danger ind x: An index designed in our paper to evaluate the danger of the road systemMinimum safety gap: The distance between two vehicles that deemed safe enough i

28、n our m.Keep-right rule:Keep right except to pass rule.Unrestricted rule:Vehicles are not restricted and can overtake others from either side.-driving style:When there is no vehicles nearby, drivers will not accel- erate or decelerate deliberately,but the speed will still fluctuate slightly.1.2Assum

29、ptionsThe road is straight and there is no bypass.2014 MCM Outstanding Winners MCM2014#25142上海交通大学，史昭阳，校苑数模网全球首发Team # 25142Page 6 of 34The width of one lane is only enough for one vehicle. All vehicles have the same volume.There are only two kinds of vehicles on the road(fast one and slow one). The

30、 environment and climate are good for driving.Driving on the right is the norm.Pedestrians are ignored.2The Ms2.1Design of Cellular AutomataLarge quties of former traffic simulations Wagner P et al.2005 basedon Cellular Automata (CA) indicate that CA mis a feasible and effectivemethod to emulate tra

31、ffic flow. Space, time and status are all discrete in Cellu-lar Automata. For example, the mdivides the road into small rectangularcells, and time is divided into small units This feature predigests the simulationprocess significantly. Besides, the status of a cell is controlled by its neighboring c

32、ells following a set of rules, which is much similar to real-life traffic where a cars movement largely depends on its neighboring cars movement. Therefore, it is rational for us to apply Cellular Automata in solving our problem.In our simulation, we divide each lane into 1000 cells. Each cell is 4

33、meters long in length and width and has two properties, the current velocity V and the um velocity Vm. A cell is empty when V is 0, because a car wont stopin our crash- simulation. We consider only one direction of the way for simplicity. Thus, a way of n lanes is converted into an n*1000 matrix.In

34、our simulation, we employ two kinds of vehicles,faster ones to simulate the cars and slower ones to simulate the trucks.For each lane, the first 6 cells are used as car-generation area, traffic flow is observed in the last 10 cells and traffic density is calculated on the basis of thelast 500 cells.

35、Our mupdates once per second, while the period T = 1s is theaverage reaction time of a driver.We discuss the basic processes for the CA m: Inflow Process: According to the inflow mthat we will discuss later,assign vehicles in the vehicle-generation area.2014 MCM Outstanding Winners MCM2014#25142Team

36、 # 25142上海交通大学，史昭阳，Pa校苑数模网全球首发Acceleration Process: If V < Vm, a vehicle accelerates by V , and the new speed is V 0 = V + V .Deceleration Process: If the distance between a vehicle and the vehicle ahead of it (Front bumper to front bumper distance, we call it the gap, and the gap is denoted by G

37、 and its unit is cell. When there is no vehicleahead , G is set to +.) is no more than V , the vehicle decelerates toV 0 = (G 1)/T .Moving Process: Vehicles move forward by V 0 T cells only when G >Gs(V 0). ( Gs(V 0) is the minimum gap required for safety consideration, and is to be defined later

38、.)Specific rules will be set in the inflow m, the following mand theovertaking mto simulate traffic under the Keep Right-Except-To-Pass ruleand traffic under no such restriction.2.2Inflow MThe inflow m, or the vehicle-generat on m, simulates the stochasticarrivals of vehicles at the entrance of the

39、f eeway. For each lane, the first six cellsin the cellular automata are set as vehicle-generation area. We assume that the arrival of each vehicle obeys the binomial probability distribution. Let ts denote the sampling time interval and N denote the total of vehicle arrivals during ts. Then N can be

40、 approximated to obey the Poisson probability distribution. Let Pts (N ) be the probability of N and we haveNeN !P ts (N ) =, N > 0With ts being ocond in our implementation, we can assign the expecta-tion of N to a range of values from 0 to 3.6. N being the total of vehicle arrivals in each secon

41、d, the expectation of N, can effectively reflect the traffic condition. The smaller the is, the lighter the traffic is; the greater, the heavier. Thus we are able to simulate different traffic conditions, light or heavy, by assigning cor- responding values to . After the value of is set, we get the

42、stochastic number of vehicles entering the way for every second in simulation. Which lane to enter is then randomly assigned.Our msupports two kinds of vehicles of different velocity ranges, theinitial speed of all vehicles are set to 20 m/s. Such practice brings simplification and doesnt weaken the

43、 result.2014 MCM Outstanding Winners MCM2014#25142上海交通大学，史昭阳，校苑数模网全球首发Team # 25142Page 8 of 34That is because the speed of all vehicles tends to converge toward a value controlled by the traffic density and by the distribution of acceleration proba- bility which is to be introduced later. When traff

44、ic density is low, vehicles canalways accelerately to theum speed without worrying about colli-sions, so the convergence speed is near the highest speed allowed. When traffic density is high, all the lanes will be filled with vehicles, and the speed of the traffic flow is decided by the speed of the

45、 slowest vehicle on the lane, so the con- vergence speed is near the lower speed limit. The preliminary analysis on the convergence speed will be justified by later implementation of the m .The utilization of the Poisson probability distribution makes our inflow mod-elto reality and practical. Becau

46、se of the convergence tendency, the sameinitial speed policy can yield simplification without harm to the simulation.2.3Vehicle-Following MThe Federal Highway Administration of the United States Department of Transportation defines, in its Manual on Uniform Traffic Control Devices, define drivers re

47、action time as PIEV time PIEV time consists of four parts: Perception process: A driver perceives the change in driving environment. Intellection process: The driver analyzes the information about the change. Evaluation process: The driver determines driving behavior based on hisanalysis. Volition p

48、rocess: The driver executes the driving behavior.We apply the PIEV process in our vehicle-following mand overtakingm. In every time cycle, we first obtain the velocity and position of eachvehicle, calculate the gap, and then determine the driving behavior (whether to continue following or to change

49、lane for overtaking). According to driving behavior, compute the acceleration and update the speed and position.Decision on driving behavior based primarily on the current gap. If the gapG is safe enough, acceleration is feasible; otherwise, the vehicle should slowdown. Here, we define the minimum s

50、afe gap Gs to be Tr V . (Tr stands for thePIEV time, and V is the current velocity.)We assume that decisions on driving behavior follow certain principles:2014 MCM Outstanding Winners MCM2014#25142上海交通大学，史昭阳，校苑数模网全球首发Team # 25142Page 9 of 34 When G > Gs, the vehicle tends to accelerate (Later we

51、will introduce aprobability m speed limit or itsto simulate the tendency.), until achieving theway um possible velocity; When G < Gs, whether to overtake or to follow is determined by the over-taking probability Po and the overtaking conditions (Po and overtaking conditions are to be discussed in

52、 the overtaking m).When following, a vehicle can accelerate, decelerate or keep the original speed. We introduce two parameters SUN yue 2005, the acceleration proba- bility Pa and deceleration probability Pb. The higher the speed, the smaller the Pa and the greater the Pb. Vl represents the higher s

53、peed limit of the way,and Vmax is theum speed the vehicle can reach. This probability mtakes intothe fact that speeding cant be ignored. When V > Vl, Pa getseven smaller and Pb gets even bigger, which makes it possible for speeding but the possibility is small. We use a stochastic variable R for

54、implementation: If R < Pb, the vehicle decelerates; If R > 1 Pa, the vehicle accelerates; Otherwise, the vehicle maintains the current speed.Based on the probability m, we create several rules for the Cellular Au-tomata:( Theum possible speed of vehicle i is, the current gap isVmaxG, the minim

55、um safe gap is Gs and its velocity is denoted as V , Pa and Pb arefunctions of velocity V , and Pa + Pb 1.)driving rule: If G Gs,min(Vmax, V + 1),withwithprobability Pa;probability Pb; others.V 0 =max(Vmin, V 1),V, Safe deceleration rule: If G < Gs but wont crash if moving forward,V 0 = max(Vmin,

56、 V 1)Vmin is under-posted the lower speed limit Crash-rule: If moving forward causes crash, stopthe formervehicle.The values of Pa and Pb are listed in table 2 for fast cars, table 3 for slow ones.2014 MCM OutstandingPagWe 1i0nonf 3e4 rsTeam # 25142MCM2014#25142Table 2: Acceleration a上nd 海Dec交ele通rati大on P学ror，Fa史st V昭ehi阳cles，校5 苑6 数模7网8 全球首发34V/cell · s110.80.70.50.300.10