Mathematical Contest in Modeling 2007: A Judge�s Perspective
June 12, 2007
Longtime SIAM MCM judge James Case, after a weekend in California reading and ranking solution papers submitted for this year's "discrete" problem, discusses the complexities of the problem and outlines some of the approaches devised by the undergraduate teams.
Between February 8 and February 12, 2007, 949 teams from 12 countries participated in the 23rd annual Mathematical Contest in Modeling. Three hundred fifty-one of the three-person teams elected to work on the "continuous" problem A, and 598 chose the "discrete" problem B. A total of 14 papers were judged "outstanding": five for problem A (two from the University of Washington, and one each from Harvard, MIT, and Duke) and nine for problem B (two from Duke, and one each from Truman State University, Kirksville, Missouri; Stellenbosch University, South Africa; Singapore National University; Peking University; the University of Puget Sound; the National University of Defense Technology, China; and Slippery Rock University, Slippery Rock, Pennsylvania).
The authors of two of the outstanding papers were named the SIAM winners: the team from MIT for problem A (see "MIT's 'Dream Team' Wins SIAM Award for MCM 2007" for highlights of the team's four-year MCM run) and the team from Stellenbosch---Louise Viljoen, Chris Rohwer, and Andreas Hafver, with faculty adviser Jan van Vuuren---as described here. With no SIAM Annual Meeting scheduled for this year, the SIAM winners will present their papers at the 2008 meeting. In the meantime, the UMAP Journal intends to publish five of the outstanding papers.
The students who worked on the continuous problem were asked to devise a method for dividing a state into the constitutionally mandated number of congressional districts having the "simplest" possible geometric shapes, after which they were to apply their method to the state of New York. The definition of "simplest" was left to the individual teams, who had only to justify their choice in terms that would be understandable to the public at large. Judges assigned to the problem reported that contestants reformulated the problem in a wide variety of ways, and employed an impressive variety of solution techniques.
The discrete problem concerned protocols for boarding and deboarding passenger aircraft. With the advent of ever-larger planes---the new Airbus model A380 is expected to hold as many as 800 seats in some configurations---the time spent on the ground (the bulk of which is devoted to on- and offloading of passengers) can represent a significant fraction of the time an aircraft and/or crew is in service, as well as a significant drain on airline revenues. Contestants were asked to devise and compare procedures for boarding and deboarding aircraft of different sizes: small (85�210 seats), midsize (211�330), and large (450�800).
The simplest way to board an aircraft is simply to open the doors and let the passengers enter at random. Experience suggests, however, that there are better ways to proceed. Almost all airlines currently allow first-class passengers and passengers with special needs---including the elderly, the infirm, and families traveling with small children---to board before others. But in filling the rest of their seats, individual airlines follow markedly different protocols, with little consensus as to which ones perform best. The New York Times (November 14, 2006) ran an article describing airlines' concern with the problem, along with their methods for dealing with it.
To reduce congestion in the aisles, Southwest Airlines has long issued boarding passes labeled group A, B, or C, on a first-come, first-served basis. Most other airlines assign seats, often allowing passengers with seats near the back of the plane to enter the cabin as soon as the preboarding process is complete, followed by passengers with seats amidships, and finally those seated near the front. Call it the "back to front" (B2F) approach. There is evidence to suggest---and a number of the MCM teams added to it---that better results might be obtained by allowing passengers assigned to window seats to be seated before those with middle seats, who are in turn seated before those in aisle seats. Call that approach WILMA: "window, middle, aisle." Then there is the "rotating zone" (RZ) approach, which allows a group of passengers assigned to seats at the rear of the cabin to board first, followed by a group assigned to seats near the front, who will presumably enter as those in the rear are getting seated. These are followed by a group to be seated just forward of the first group of passengers, now seated in the rear, then one just aft of the ones by now seated near the front of the cabin, and so on, until the groups meet in the middle.
Combining the considerable virtues of B2F and WILMA, the "reverse pyramid" (RP) method allows people assigned to window seats in the back third of the cabin to enter first, followed by those assigned either to window seats amidships or middle seats toward the rear. Next come those with window seats in the front section or middle seats amidships or aisle seats in the rear, and so on, until only aisle seats near the front of the cabin remain unfilled. The name refers to the fact that, at any stage of the process, the unfilled seats will form a pyramid pointing toward the back of the plane.
Many of the MCM teams merely tested---via simulation---the variants of the foregoing protocols obtained by varying the numbers and sizes of the boarding groups. Others invented alternative protocols to test against those in current use, or used genetic algorithms to do the inventing for them. Most observed that enplaning was a more serious problem than deplaning, and advised that cabin crews refrain from interfering with the latter. It was also widely noted that baggage is the enemy of boarding efficiency, and advised that carry-on luggage be strictly limited.
The team from Stellenbosch University that won the SIAM award for the discrete problem tested a total of ten boarding protocols---again via simulation---before concluding that the reverse pyramid method with about nine groups performs as well as any. They distinguished themselves for their thoroughness in assessing a wide range of possibilities.
Readers can find detailed information about the Mathematical Contest in Modeling, including complete results for MCM 2007, at www.comap.com.
