1999_HiMCM_Outstanding_Papers

数模资料

HIGH SCHOOL MATHEMATICAL CONTEST IN MODELING

OUTSTANDING PAPERS

Major funding provided by the National Science Foundation.

NSF Project Award Number ESI-9708171

ly as possible. Consider a 2 mile stretch of a major thoroughfare withcross streets every city block. Build a mathematical model that satisfiesboth the commuters on the thoroughfare as well as those on the crossstreets trying to enter the thoroughfare as a function of the traffic lights.Assume there is a light at every intersection along your 2 mile stretch.First, you may assume the city blocks are of constant length. You maythen wish to generalize to blocks of variable length.

helpful to team members and advisors. Because ofspace considerations, the four outstanding papersthat appear here have been edited to remove

redundancies and shorten wording as much as pos-sible. In particular, since summaries tend to repeatanalyses found elsewhere in the papers, we haveincluded only one to serve as an example.

数模资料

2

HiMCM OUTSTANDING PAPERS

数模资料

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

数模资料

4

HiMCM OUTSTANDING PAPERS

数模资料

HiMCM OUTSTANDING PAPERS

5

数模资料

6

EQUATIONS GOVERNING P, AND THEIR DERIVATIONS:It is possible to derive equations for the rate of cars makingeach of the three choices, from all four compass directions. Forinstance, if Pis the probability to turn away from the thorough-fare, the rate of cars per second that want to turn away from theeast or west is P(r(rE-W), and the rate of cars that want to be in,say, lane 0, is Pthe intersection going south is the rate turning right from westE-W)/2. The total rate of cars that are leavingplus the rate turning left from east, or, P(rP(rE-W)/2 + P(rE-W)/2 =E-W). Thus, P(rE-W)is the amount of cars that have to comefrom the south onto the thoroughfare to make up for those carslost, which can be split into half to accommodate east and left-bound cars. This is all mirrored by the southbound street, andso P(rE-W)/2is the rate of cars in every turning lane in everydirection.

For cars not turning, the rate approaching from the east or westminus the rate turning away is the total rate: (rE-W) – P(rE-W) =(1 – P)*(rE-W).

The remaining possibility is cars crossing thoroughfare. Pcarscoming at the intersection do not leave via the thoroughfare, sothe rate Aof cars going straight is 2P(A+ P(r(rE-W)) = A, which canbe solved for A= PE-W)/(1 – P).GREEN LIGHT COMBINATIONS

To decide the most efficient way to cycle through the differentcombinations of green lights, we came up with all of the list inAppendix B. We chose the necessary ones and found the bestcircular order: 1, 5, 2, 4, 3, 6, and back to 1 again. In an averagecycle, all of these states would be present for an amount of timeproportional to the average number of cars that need to useeach combination. We found the number of cars for each

combo, which is based on Pand rlane with the most cars to pass through is the lane that limits itsE-W. For each combination, thebrevity. By finding the lane with the greatest relative amount ofcars for each combination, we hoped to minimize the time thatno traffic is moving and maximize the time that traffic is flowing.We used two approaches to this problem. First, we assumedthat all traffic stops when changing from one green light combi-nation to another and improved our model to let traffic contin-ue to flow when it does not need to stop. For instance, betweengreen light combinations 1 and 2, lane 1 does not need to cometo a halt. In both cases, we divided this greatest flow rate by thetotal flow rate, which is the sum of the six greatest flow rates.By repeating this for the six different green light combinations,we arrived at expressions that, when evaluated, returned thefraction of a full light cycle that the corresponding green lightcombination would be lit. For example, in the first and less effi-cient model, the total flow was –1/(P– 1), and our limiting fac-tor expression for the first green light combination is (1 – P).Therefore, on average, the fraction of a light changing cycle thatgreen light combination 1 is active is estimated as (P– 1)2. All ofthese results are in Appendix B.

The graph in Figure 2gives a visual representation of how theoverlapping data is better. The more efficient model is darker.The lines represent the six green light configurations, of whichthere are three unique expressions. They are a plot of the proba-bility that each configuration is used in a cycle against thegreater likelihood that more people would want to turn onto

HiMCM OUTSTANDING PAPERS

side roads. It is a graph of time fraction to P. The bold linesintersect sooner and are closer to each other than the fine linesare, an indication of better total efficiency.

Figure 2. [0.38, 0.50] x[0.10, 0.33]

INTERESTING RELATIONSHIPS BETWEEN VARIABLES

We created an equation containing all three variables P, rE-W,and rN-S, First we added together the expressions that representthe output of lanes 4 and 5; this sum is equal to rtion is: (rN-S. The equa-E-WP) + (rE-WP2)/(1 – P) = rmore sense (and looks prettier) when solved for N-S. This equation makesP:

P= rN-S/(rN-S+ rE-W). It is then possible to substitute the rightside of this equation into the ratio equations in Appendix B toget applicable data. The graph in Figure 3, shows how rindirect proportion to rS-Nis inE-W, when Pis constant.

10.80.60.40.200

50y

Figure 3.

80x

150

40

200

DETERMINING THE OPTIMUM TIME PER LIGHT CYCLESeveral factors impact the problem. First, synchronization oflights must be avoided. This is because if cars get backed up atone light and the next light simultaneously turns green, therewill not be many cars to pass through the second green light.Synchronization is difficult to control because the length of alight cycle can vary depending on whether cars are on the sen-sor when the cycle is allowed to move on to a non-straight-thor-oughfare. In a city with differing block lengths, the probabilities

数模资料

HiMCM OUTSTANDING PAPERS

7

数模资料

8

HiMCM OUTSTANDING PAPERS

数模资料

HiMCM OUTSTANDING PAPERS

9

数模资料

10

HiMCM OUTSTANDING PAPERS

数模资料

HiMCM OUTSTANDING PAPERS

11

数模资料

12

HiMCM OUTSTANDING PAPERS

数模资料

HiMCM OUTSTANDING PAPERS

13

数模资料

14

HiMCM OUTSTANDING PAPERS

数模资料

HiMCM OUTSTANDING PAPERS

15

数模资料

16

HiMCM OUTSTANDING PAPERS

COMAP ANOUNCES THE SECOND

graphs that were judiciously selected to help clarify ideas andresults to the reader. Key mathematical formulas were carefullydeveloped leading to a final model, rather than just being

‘dropped in’ from some reference. Several of the weaker paperschose to present a volume of detail without an accompanyingexplanation, which is equivalent to saying to the judges: “Here,we did the work, now you figure it out.” This is never a goodidea. Using a spell checker and carefully verifying any algebraused cannot be overemphasized.

Apoint worth mentioning is the difference between ‘evaluatinga model’s results’ and ‘evaluating the strengths and weakness-es’ of a model. Both elements are critical to the modeling

process. Simply put, the strengths and weaknesses of a modelare identified by examining the model and its results in light ofthe simplifying assumptions made to create the model.Evaluating a model’s results consists of determining if theresults make sense, and interpreting what these results meanwith regard to the information sought. This latter action pro-vides the basis for modifying the model until a team is satisfiedwith the model’s performance.

By and large, the exceptional papers provided conclusive evi-dence that their teams had dedicated a substantial amount oftime thinking about the problem prior to starting their quest forsupporting information. While the Internet does provide aseemingly limitless source of information, it can also act as asiren’s call to act before thinking, thus using up valuable timepotentially pursuing dead ends.

Finally, the need for precise supporting documentation in thebody of the final paper cannot be stressed enough. Exceptionalpapers all convey a clear link to verifiably credible informationsources within the body of their paper. Lesser quality papersshow a reliance on supporting information that fails to includenecessary explanations of why certain facts are valid. Althoughthe temptation to ‘cut-and-paste’ directly from sources such asthe Internet is recognizably strong, doing so can often result in apaper that is predominantly statements of unsupported ‘facts’rather than one demonstrating that the team has a clear under-standing of the model.

HiMCM School websites

Parker School:Westminster Schools:

Illinois Math and Science Academy:www.imsa.edu

Chesterfield County Math & Science HS:

/Schools/Clover_Hill_HS/mathsci.htm

2000

FEBRUARY 17–23, 2000

HIGH SCHOOLMATHEMATICALCONTEST INMODELING

The contest offers students the opportuni-ty to compete in a team setting usingapplied mathematics in the solving ofreal-world problems.

For information on participating in theHiMCM 2000, please contact Clarice

Callahan at c.callahan@ orcall 781-862-7878 x37 to receive a contestbrochure and registration card.

Major funding provided by the National Science Foundation.

57 Bedford St., Suite 210Lexington, MA 02420

本文来源：https://www.bwwdw.com/article/dyl1.html