1999_HiMCM_Outstanding_Papers(3)

数模资料

HiMCM OUTSTANDING PAPERS

6.When turning, cars decelerate to 15 mph, and execute the

turn at 15 mph. If they are making the turn from rest, theyaccelerate to 15 mph.EXPLANATION OF ASSUMPTIONS:

1.Real life traffic moves as a stream without distinction of thecars. The values in 1a and 1b are an average of 12 sedans in aPopular Mechanicsreview. Over time, the deviations betweencars should approach this average. For stopping distance wechose the largest value—had we picked a smaller one, carswith a greater stopping distance would not stop until theywere in the middle of an intersection.2.This is a standard side street in our area. The 12 ft width isfrom a study by a contractor about an idealized road.3.We need a speed limit, and 60 mph seems reasonable.4.Most people prefer safety over an extra 5–10 mph, especiallyin busy streets where speed is limited by traffic. Without thisassumption, cars could do anything. As far as going the max-imum speed, there is no reason for drivers notto wish to getto their destinations as quickly as possible. 5.Because the thoroughfare consists of two lanes in each direc-tion and a left turn lane, it will accommodate all actions: theleft turn lane allows a left turn without impeding others, andthe rightmost of the two normal lanes allows a right turnwithout impeding cars continuing forward—these cars canuse the center lane. Thus, cars turning off the thoroughfaredo not affect the straight motion of others. Also, cars turningonto the thoroughfare will not change the motion of those onit. If cars are turning left onto the thoroughfare, cars on thethoroughfare will be stopped at a red light, and if a driverwants to turn right off a side road onto the thoroughfare, heis prudent, and turns only if he will not disrupt oncomingtraffic.6.Assumption 4 says drivers are prudent. In driver’s education,we learned that 15 mph is the safe turning speed—thus driv-ers would not exceed 15 mph in turns.ANALYSIS AND MODEL DESIGN:

The natural question is, “what does flowing as smoothly as pos-sible” mean? We measure “smoothness” as rate of flow, or howmany cars travel along the thoroughfare per lane per hour. Ifthis were our only criterion, we could optimize by making thethoroughfare lights always green. However, we must satisfydrivers on side streets.

We pursued two models. One was based on a “wave” pattern,and the other is a genetic algorithm that iteratively approachesa solution based on initial conditions.

If all cars on the thoroughfare are going in one direction, anideal solution is a “wave” of lights. By this we mean that if ittakes a car moving at the speed limit mseconds to go from oneintersection to the next, light changes are staggered by msec-onds, and so a car can travel the entire stretch without stopping.What’s more, between the green light waves it is possible tohave waves of red lights allowing cars turning onto the thor-oughfare to ride the next wave. The problem is that creating

3

waves in only one direction creates trouble in the other direc-tion. The question is: “How can we create two sets of greenlight waves, going in opposite directions?”

Asolution is two waves of green lights travelling in oppositedirections that overlap each other. This has one major problem:there can be stoplightswhich either are never red(as viewed by drivers trav-eling on the thoroughfare;this notation will be usedhereafter), or have only avery short red light. In thediagrams at right, the col-ored blocks represent thestatus of a light (green orred). Time increases fromtop to bottom, and the

height of each block is approximately 7.5 seconds (the time ittakes a car to travel between intersections). There are 17

columns in each picture, representing 17 stoplights in a two-mile stretch. As one looks down a column of blocks, one can seethe red-green pattern that that light will take over time.

However, in the left diagram, which represents a simple criss-cross pattern, one can find stoplights that are only red for oneblock at a time. This means that the side roads at this particularintersection only have a green light for 7.5 seconds, not enoughfor any feasible traffic flow. Therefore, we modified the modelby adding another row of “blocks” beneath each red diamond,as shown on the right, making the minimum green light for aside road about 15 seconds. However, the thickness of the criss-cross diagonal paths of green, which are analogous to the carry-ing capacity of the thoroughfare, is reduced by 1/7. The alterna-tive is far worse, and increasing the thickness of the green criss-cross paths reduces the ratio of loss in carrying capacity. Thereare, however, graver problems. For instance, varying the thick-ness of the “waves” of green and red lights can create lights thatare always green.

An example of this behavior might be forcrisscrossed green paths of thickness 6 and7, as shown at left. As you can see, there areareas where the light is always green. Infact, in the 17 stoplight example, any timethere is a green strip of even-numberedthickness, there will be such lights. Theseare costly to correct since they require theaddition of at least two layers of red. Onlywhen both green paths are of odd thicknessis one additional layer required. Thus, wewill use only paths of odd thickness.

The next task is to determine the shape of the model as adependence on different traffic flows. Since we must assumethat traffic is relatively uniform, as many cars come onto thethoroughfare as leave it again. However, there may be moretraffic in one direction. For instance, the east end of the thor-oughfare might lead to a highway to a suburb, while the westend might lead to office buildings. Therefore, most morningtraffic will be from west to east as office workers enter the city,and in the opposite direction in the afternoons. Call the ratio of