# 论文.pdf

Team 770 Page 1 of 50 1 The Booth Tolls for Thee Team 770 February 7, 2005 Abstract In this paper, we address the problems associated with heavy demands on toll plazas such as lines, backups, and traffic jams. We consider several models in hopes of minimizing the “cost to the system,“ which includes the time-value of time wasted by drivers as well as the cost of daily operations of the toll plaza. One model yields a microscopic simulation of line formation in front of the toll booths when the service rate cannot match the demand. Using hourly demand data from a major New Jersey parkway, the simulation is limited in not taking bottlenecking effects into consideration. The results, however, when subjected to threshold analysis can serve to set upper bounds on the number of booths that could potentially be suggested by any other models. After presenting this basic model, a more general, macroscopic framework for analyzing toll plaza design is introduced. In analyzing “total cost“ and allowing bottlenecking, this model is more complete than the first, and it is able to make recommendations for booth number based on data obtained from the first model. This computation melds the macro- and micro- levels, a strategy that is helpful in looking at toll booth situations. Finally, a model for traffic flow through a plaza is formulated in the world of “cellular automata.“ An interesting take on microscopic ideas, the cellular automata model can serve as an independent validation of our other models. In fact, the models mostly agree that given L lanes, a number of booths around [ ][ ]9.065.1 += LB , where [ ][ ]x is the greatest integer less than x, will minimize the total human cost associated with the plaza. Team 770 Page 2 of 50 2 Introduction When Will Smith s name was called, announcing his receipt of the Best Male Performance award at a recent installment of the MTV Movie Awards, he bounded to the podium. Needling MTV for baiting him to attend their show, Smith snarkily quipped, “M.T.V.: My Time is Valuable.“ And of course, many other Americans would say the same for themselves, without Smith s irony. In an economy as driven by efficiency as America s, there certainly seems to be a predominant national mindset induced by the toil of the workweek. It s broader than just a desire to be busy or to accomplish; rather it extends to the notion of having control over one s own time, something we abhor to see wasted. It is no stretch, either, to say that paying a toll to be able to travel to one s destination is largely viewed as an inconvenience. Americans have, for the most part, come to view having free, open roads as an inalienable right from our government. Toll roads are then aberrant and annoying. But the vexing aspects of toll roads do not stop at the quarter or 35-cent fee, but rather include the time that drivers are forced to waste. Stopping at tolls retards the steady, quick flow of a highway, while not necessarily offering safety benefits like stopping at traffic lights (which are widely tolerated). What s worse is when heavy demand creates jams in the merging lanes exiting the booths or backs up traffic in delineated stripes of hot metal and hotter humanity entering the plaza. The time spent at a toll plaza is easily and often seen as time that could be more fruitfully spent. It is time when the drivers lose sovereignty over their personal whims and obligations. Despite the anachronisms, imagining Sir Isaac Newton being stranded in a car at a toll plaza when the all-important apple decided to drop back at his home, or envisioning Albert Einstein sitting in a traffic jam without a pencil the moment that relativity dawned upon his own head serve to illustrate some (hyperbolic) motivation in trying to make the toll process as expedient as possible. It is certainly strange to think so, but Newton and Will Smith have something in common. Restatement of the Problem Drivers have places to be and people to see, but for one reason or another, tolls must at times be collected from them. It is our goal in this paper to make the process more optimal for everyone involved, including the owners and operators of the booths, and of course the drivers. The only mechanism for optimization at our disposal is, presumably, adjustment of the number of booths present at a certain toll plaza, given the number of lanes entering and exiting it. During peak hours, which occur typically when suburbanites make their way to and from work in larger cities, it is common for lines to form entering the tollbooths, as Team 770 Page 3 of 50 3 demand overtakes the fastest rates that the tolls can be collected. On the other side of the booths, too, as the (often) greater number of lanes coming out of the booths converge back down to the original number, bottlenecks and jams are wont to amass in response to the harried merging. We seek to balance these effects, along with the cost associated to offer extra booths, in order to provide reasonable recommendations for how to minimize the waste of time and money in the toll-collecting process by adjusting the number of booths offered at a given toll plaza. Previous Work in Traffic Theory Mark Twain famously remarked, in his disdain for arithmetic, that the answer to all mathematical problems is three. While insightful, the Twain model leaves some room for improvement in addressing the tollbooth conundrum at hand. A five-lane highway will need more than three tollbooths, but Twain wrote great novels. There is a rather substantial literature on models for traffic flow, and most models fall into one of two categories: microscopic and macroscopic. The microscopic models are the ones that can be said to “miss the forest for the trees.“ They examine the actions and decisions made by individual cars and drivers. Often these models are called car-following models since they use the spacing and speeds of cars to characterize the overall flow of traffic. Interesting models have emerged from examining cellular automata in a traffic sense (much more to come) and queuing theory. Macroscopic models tend to view traffic flow in analogy to hydrodynamics and the flow of fluid streams: just as blood hurtles red blood cells through veins, vehicles pulse down streets toward their destinations. The “average“ behavior is assessed, and commonly used variables include steady-state velocity, flux of cars per time, and density of traffic flow. Some models bridge the gap, including the gas-kinetic model which allows for individual driving behaviors to enter into a macroscopic view of traffic, much like ideal gas theory can examine individual particles and collective gas [Tampere, et al. 2003]. The tollbooth problem is an interesting addition to the traffic literature because it involves no steady velocity, so macroscopic views may be tricky. On the other hand, specific bottlenecking events are quite complex, and microscopic ideas are certainly put to the test. An M/M/s queue (vehicles arriving with gaps determined by an exponential random variable, to s tollbooths, and service at each tollbooth taking an exponential random Team 770 Page 4 of 50 4 variable amount of time [Gelenbe, 1987]) seemed appropriate at first. However, queuing assumptions did not satisfy our thirst for details about bottlenecking and about multiple lanes. Drawing on ideas from old models, while still developing ideas more pertinent to the tollbooth problem, we were able to incorporate aspects of the situation from a small- scale into a larger-scale framework. It seems that neither micro- nor macro- will alone be adequate to capture the dynamics of a toll plaza, though our cellular automata simulation (for herky-jerky driving at lower speeds) produced some surprisingly good results (in terms of matching with other analyses). Properties of a Successful Model A successful toll plaza configuration should achieve the following objectives: ? Maximize efficiency of the toll plaza by reducing customer waiting time (due to bottlenecking, tollbooth lines, etc.) ? Suggest a reasonably implementable policy to toll plaza operators ? Be robust enough to efficiently handle the demands of a wide range of operating capacities ? As the number of highway lanes feeding the toll plaza is increased, the optimal number of tollbooths will not decrease. General Assumptions and Definitions Assumptions ? There is only one type of driver in the system. In navigating toll plaza traffic, all drivers act according to the same set of rules. Although the individual decisions of any given driver are probabilistic, the associated probabilities are the same for all drivers. ? Bottlenecking downstream of the tollbooths does not hinder their operation. Vehicles which have already passed through a tollbooth may experience a slowing down due to the merging of traffic, but this effect is not extreme enough to block the tollbooth exits. ? The number of highway lanes does not exceed the number of tollbooths. An obvious solution to the posed problem may especially occur Team 770 Page 5 of 50 5 to those sitting still at a traffic plaza: namely, set the number of tollbooths equal to zero. The assumption above instead ensures that the number of tollbooths must be strictly positive. ? All tollbooths offer the same service and vehicles do not distinguish between them. We seek to improve toll plaza efficiency by optimizing the number of tollbooths – not the services they provide. While several types of tollbooth exist in practice, we have not been charged with distinguishing between them and suggesting their selective use. This is a problem of a different nature. Later, we return to this assumption and list ways in which our solution might change in response to multiple booth types. ? The amount of traffic on the highway is dictated by the number of lanes on the highway and not the number of tollbooths. Changing the number of tollbooths for a given number of lanes does not affect the ‘demand’ for the roadway. ? The number of operating plaza booths remains constant throughout the day. Terms and Definitions ? Take a “highway lane” to be a lane of roadway in the original highway before and after the toll plaza. Thus, the number of ‘lanes’ in a given toll plaza configuration depends not on the plaza itself but on the width of the roadway before and after the toll barrier. ? Influx is the rate (in cars/min) of cars entering all booths of the plaza. ? Outflux is the rate (in cars/min) of cars exiting all booths of the plaza. It is a function of time. Optimization Next, we seek a method of optimization that can be used to evaluate potential solutions to the problem. How do we decide that a given toll plaza configuration is optimal? One natural way to compare potential solutions is to compute the total time drivers spend waiting in the toll plaza. It seems logical to conclude that well-designed toll plazas will require less customer waiting time than their inefficient counterparts. Although this method might offer insight, we note some serious drawbacks. Namely, this waiting time minimization disregards the standpoint of the agency operating the Team 770 Page 6 of 50 6 toll plaza. In other words, minimizing the waiting time for customers may not present convenient policy options for toll plaza operators. Suppose a model based on waiting time minimization suggests that forty tollbooths should be used in a plaza for a six lane stretch of highway. Should operators heed this advice? Certainly, the operators of the plaza will incur significant cost in building and maintaining such a facility. In crowded areas, it may not even be possible to construct a toll plaza of this size. Furthermore, tollbooths employ personnel to serve customers without exact change. Paying additional construction, maintenance, and labor costs may not be worth the added benefit of lowering customer wait time. We seek a more balanced method of facility optimization. This method must consider not only the customers, but also the agency operating the toll plaza. To implement this scheme, we must somehow equate customer waiting time with toll plaza operating costs. We elect to use cost as a yardstick of our solutions. Cost is a convenient medium due to its ubiquity in our culture and the relative ease of its translation into time. In considering the entire plaza system, we seek the facility configuration that will generate the lowest net cost. This cost will be distributed among both parties in our system – the users and the operators. In creating a cost optimization apparatus, we invoke the following terms and definitions: ? The general cost, C [dollars], of a toll booth is the time-value of the delays incurred at a toll plaza for each individual (driver or passenger) AND the cost associated with daily operations of the booths at the plaza. The toll fees themselves and the upstart cost of building a new plaza are NOT part of this cost. ? α is the average time-value of a minute for a car occupant. ? γ is the average car occupancy. ? N is the total number of (indistinct) tolls paid over the course of the day. ? L is the number of lanes entering and leaving a plaza. B is the number of booths in the plaza. ? Q [dollars] is the average daily operating cost of a human-staffed tollbooth. The underlying goal of this construct is to find a reasonable number of toolbooths, B that minimizes cost C, a function of B. We formulate this function C(B). Team 770 Page 7 of 50 7 First, notice that the total waiting time per car will be WN, and so the total cost incurred by waiting time will be WαNγ. General human time-value is cited as $6/hour or α = 10 cents a minute [Boronico, 1998]. The amount that must be expended to operate a booth for a day would then be QB. The average annual operation cost for a human-staffed tollbooth is $180,000, so we set Q = 180000/365.25 [Sullivan, et al. 1994]. Reasoning that W depends on B, we now see that ( ) QBNWBC += γα This is the function we ll want to minimize with respect to B (for a given L). Naturally, the knee-jerk reaction is to take its derivative and set it equal to zero, showing that the B we seek must necessarily satisfy .)( γαNQBW ?= Fourier Approximation of Toll Plaza Car Entry Rate From a previous research paper’s traffic flow data [Boronico, 1998], we find the mean demand per minute (influx) of cars for a toll plaza on a given typical day. The reason the data peaks are very high at the 6am – 7am rush hour and are not as high during the 3pm – 4pm rush hour period is that the data is collected in the direction headed toward the metropolis. Thus, the main reason for traffic on a typical weekday, the workers during a business day, will be using the “toward big city” tollbooths in the morning, and these tollbooths will be far less frequented in the evening hours. Table 1: Fourier Approximation of Influx Data Team 770 Page 8 of 50 8 Start Time End Time Hour* Influx (cars/min) Fourier Approx of Influx** 12: