Authors
David C. Clark Dr. William T. Scherer Dr. Brian L. Smith

The contents of this report reflect the views of the authors, who are responsible for the facts and the accuracy of the information presented herein. This document is disseminated under the sponsorship of the Department of Transportation, University Transportation Centers Program, in the interest of information exchange. The U.S. Government assumes no liability for the contents or use thereof.

Although extensive Intelligent Transportation Systems (ITS) technology is being deployed in the field, little analysis is being performed to evaluate the benefits of implementation schemes. Benefit analysis is particularly in need for one popular ITS technique: ramp metering systems. The reported benefits of ramp metering systems range widely and little analysis has been performed to determine the magnitude and cause of this discrepancy. There is such a wide range of opinions that some transportation professionals are currently questioning whether ramp meters generate any benefits at all.

The variation in opinions is largely due to the fact that the relationship between the performance and cost of ramp metering systems is not well understood. Without understanding what factors cause ramp meters to perform well, it is very difficult to efficiently design a new ramp metering system. Additionally, insufficient analysis of prior benefits causes difficulty for transportation engineers attempting to make rational design decisions based on past results.

This study investigates the benefit-cost relationship of ramp metering systems by constructing a performance-cost tradeoff curve that displays the maximum achievable performance for any budget. A simulation-optimization methodology was developed to generate the tradeoff curve. This methodology employs heuristic search techniques to locate the "optimal" ramp metering deployment scheme (quantity and location of equipment) for each budget. All deployment schemes are evaluated using CORSIM, a traffic simulation tool.

The performance-cost curve constructed by the simulation-optimization methodology has the shape of a step function. Significant benefits are possible with only a small initial investment, however, beyond this initial step, diminishing returns are experienced as benefits slowly increase with additional spending.

Analysis of the tradeoff curve provides valuable information about the performance-cost relationship and ramp metering systems in general. Recommendations for improving ramp metering implementation are developed using this information. Also offered are additional recommendations for improvement of the simulation-optimization methodology and suggested areas of future research.

Abstract *

List of Tables *

List of Figures *

Chapter 1: Introduction *

Chapter 2: Literature Review *

Chapter 3: Methodology *

Chapter 4: Implementation *

Chapter 5: Preliminary Results *

Chapter 6: Analysis of Results *

Chapter 7: Conclusions *

References *

Appendix A: Cost Rules *

Appendix B: Traffic Arrival Distributions *

Appendix C: Simulation Model Calibration *

Appendix D: Traffic Responsive Algorithm Evaluation Results *

Appendix E: Clock-Time Algorithm Evaluation Results *

Appendix F: Higher Replication Test Results *

Appendix G: Linear Regression Models *

Table 1.1: Available Ramp Metering Algorithms ………………………………………4

Table 2.1: Speed Control Lookup Table ……………………………………………….20

Table 2.2: Occupancy Control Lookup Table ……………………………………….…20

Table 4.1: Weight Assigned to each MOP …………………………………………….46

Table 4.2: Weight Assigned to each Traffic Scenario …………………………………46

Table 5.1: Deployment Schemes Costing Approximately $475,000 ………………….55

Table 6.1: Results of Deployment Schemes from Twenty-Minute Evaluations ………66

Table 6.2: Results from Evaluations over Entire Rush Hour ………………………….67

Table 6.3: Results Using Both Traffic Data Sets ………………………………………68

Table 6.4: Normalized Results from Both Data Sets ………………………………….69

Table 6.5: Results of Equivalence Class Assumption Tests …………………………...71

Table 6.6: Results for Clock-time Algorithm Choice Assumption Test ………………72

Table 6.7: Results for Traffic Responsive Algorithm Choice Assumption Test ………72

Table 6.8: Weight of each MOP ……………………………………………………….74

Table 6.9: Three Alternative Weighting Schemes …………………………………….75

Table 6.10: Results with Alternative Weighting Schemes …………………………….75

Table 6.11: Car-Following Aggressiveness Set at Original Values (1.0 – 0.1, 5).….….77

Table 6.12: Car-Following Aggressiveness Set at New Values (1.2 – 0.3, 10) ………..77

Table 6.13: Results with Traffic Demand Increased Ten Percent ……………………..79

Table 6.14: Square Error of Distributions Fit to Arrival Data …………………………82

Table 6.15: Base Model Results with Different Arrival Distributions ………………...83

Table 6.16: Deployment Scheme Results with Different Arrival Distributions ……….83

Table 6.17: Summary of Tests Performed ……………………………………………84

Table B.1: Arrival Data Partitioned into Logical Groupings ………………………101

Table B.2: February 10, 2000 – Raw Data from each Measurement ………………102

Table B.3: February 11, 2000 – Raw Data from each Measurement ………………102

Table D.1: Traffic Responsive Algorithm Evaluation Results – Ramp 1 …………….108

Table D.2: Traffic Responsive Algorithm Evaluation Results – Ramp 2 …………….109

Table D.3: Traffic Responsive Algorithm Evaluation Results – Ramp 3 …………….109

Table D.4: Traffic Responsive Algorithm Evaluation Results – Ramp 4 …………….110

Table D.5: Traffic Responsive Algorithm Evaluation Results – Ramp 5 …………….110

Table D.6: Traffic Responsive Algorithm Evaluation Results – Ramp 6 …………….111

Table D.7: Traffic Responsive Algorithm Evaluation Results – Ramp 7 …………….111

Table E.1: Clock-Time Algorithm Evaluation Results ……………………………….112

Table F.1: Comparison of Scores of All Deployment Schemes in Budget One ……..114

Table F.2: Comparison of Scores for Seventeen Highest Scoring

Deployment Schemes …………………………………………………………….115

Figure 1.1: Schematic of a Traffic Responsive Ramp Meter ……………………………3

Figure 1.2: Possible Shapes of Performance-Cost Tradeoff Curve ……………………..7

Figure 3.1: Simulation-Optimization Methodology ……………………………………26

Figure 3.2: Binary Representation ……………………………………………………..29

Figure 4.1: Diagram of the Test Area ………………………………………………….33

Figure 4.2: Binary Representation of a Deployment Scheme …………………………34

Figure 4.3: Temperature at each Iteration of the Search ……………………………….51

Figure 5.1: Performance and Cost of all Tested Deployment Schemes ……………….52

Figure 5.2: Speed Score and Cost of all Tested Deployment Schemes ………………..53

Figure 5.3: Accident Score and Cost of all Tested Deployments ……………………54

Figure 5.4: Amount of Data Collected and Cost of all Tested Deployment

Schemes …………………………..……………………………………………….54

Figure 5.5: Diagram of Deployment Scheme Number Nine …………………………..56

Figure 5.6: Diagram of Deployment Scheme Number Ten ……………………………57

Figure 6.1: Ninety-percent Confidence Interval Around the Total Score of the

Top Fifty Performers ……………………………………………………………...61

Figure 6.2: Ninety-percent Confidence Intervals of Total Score for Top Performers

After Twenty Replications ………………………………………………………...62

Figure 6.3: Total Score of Top Performing Deployment Schemes ……………………64

Figure 6.4: Annual Hours of Traveled Saved due to Ramp Metering …………………64

Figure 6.5: Number of Accidents Avoided Annually due to Ramp Metering …………65

Figure 6.6: Coverage Score of Top Performing Deployment Schemes ……………….65

Figure 6.7: Results From Original Search of Budget 3.………………………………..80

Figure 6.8: Results From Second Search of Budget 3 …………………………………81

Figure 7.1: Performance-Cost Tradeoff Curve ………………………………………...88

Figure 7.2: Simulation-Optimization Methodology ……………………………………90

Figure B.1: Histogram of Inter-arrival Times (6:15AM – 7:15AM Thursday,

February 10, 2000) ………………………………………………………………100

Figure B.2: Histogram of Inter-arrival Times. 6:15AM – 7:15AM Friday,

February 11, 2000 ……………………………………………………………….100

The United States surface transportation system accommodates four trillion passenger-miles and three trillion ton-miles of freight per year. With travel demand expected to increase thirty percent between 1999 and 2009, more than 4,400 lanes-miles of roadway need to be added each year in order to maintain current levels of congestion. However, high construction costs and diminishing available land make building new roads unattractive, and roads are currently only being added at a rate of 3,000 lane-miles per year [26].

One solution is to build fewer new roads and invest money in Intelligent Transportation Systems. Intelligent Transportation Systems integrate technologies in fields such as information processing, communications, control, optics, and other electronics to increase the effective capacity of existing transportation infrastructures. ITS includes a diverse range of program areas such as Advanced Traffic Management Systems (ATMS), Advanced Traveler Information Systems, Commercial Vehicle Operations, Electronic Toll Collection, and Intelligent Vehicle Initiatives [30]. These systems increase the effective roadway capacity and improve safety on the roadway while costing far less than building additional roads. A 1997 study conducted for the United States Department of Transportation and the Intelligent Transportation Society of America found that ITS systems produce a benefit-cost ratio of more that 8:1 in the nation’s 75 largest metropolitan areas [4].

Ramp metering is a ATMS technique that was first implemented in the early 1960s in Chicago and is now in place in 23 metropolitan areas in the United States [27]. This control strategy places traffic signals on freeway entrance ramps to regulate the number of vehicles entering a freeway. The traffic signal reduces the flow of cars onto the freeway. Ramp metering benefits arise from the smoothed flow of traffic on the freeway and the storage of excess vehicles on the entrance ramp instead of on the freeway mainline. Reduced congestion on the mainline leads to increased speeds and improves overall corridor flow despite the extra delay vehicles experience on the ramp.

Ramp meters can be quite simple or extremely complex. Pre-timed ramp meters have a constant metering rate and simply allow one vehicle to pass every set number of seconds. These meters are programmed to turn on and off at predetermined times and are unaware of the current traffic conditions. Conversely, traffic responsive meters communicate with vehicle detectors in the roadway and calculate an appropriate metering rate based on the current traffic conditions. Figure 1.1 shows a schematic of a traffic responsive ramp meter.

Figure 1.1: Schematic of a Traffic Responsive Ramp Meter.

Traffic sensitive ramp meters can be classified as local or system wide. Local ramp meters act independently of all other ramp meters when determining their metering rate. They only consider the traffic conditions within a mile or two of the on-ramp and select a metering rate with the objective of optimizing traffic flow in the ramp’s local area. Conversely, system wide ramp meters communicate with vehicle detectors and other ramp meters outside of the local area. Each ramp’s metering rate is based on traffic conditions throughout the system and the metering rate at other ramps. Table 1.1 contains a two-by–two matrix which displays available ramp metering algorithms for each class of ramp meter.

Table 1.1: Available Ramp Metering Algorithms
1.3 Rationale

Ramp metering systems across the country are providing a wide range of benefits. Ramp metering systems in Detroit, for example, have reduced accidents by 50% while ramp meters on Long Island have reduced the accident rate by only 15%. Additionally, ramp meters in Portland have increased mainline speeds by over 60% on some stretches of road, but Detroit only reports an 8% increase in speed on its metered sections of freeway [26]. Unfortunately, like ramp metering, most other forms of Intelligent Transportation Systems are also experiencing a large range of benefits.

Compounding this situation is the fact that some parties are questioning the accuracy of past evaluation studies. The local press claims that the Minnesota Department of Transportation (MnDOT) has been overstating the benefits of ramp metering. According to a 1997 MnDOT report, ramp meters in the Minneapolis/St. Paul metro area typically increase speeds and flow rates by thirty percent while decreasing the accident rate approximately forty percent [33]. However, in March 2000, the Transportation Committee in Minnesota’s House of Representatives endorsed a bill to turn off the ramp metering system for one month to perform an independent benefits study [1].

Thus far, researchers have had very little success determining why some ramp metering systems have provided drastic improvements, while other systems have done little to reduce congestion and increase safety. Some of this difficulty can be attributed to the large number of variables that differ from system to system. Site specific factors such as flow rates, level of congestion, driver aggressiveness, and road geometry likely all affect the observed benefits. Additionally, design decisions such as the number of meters installed, the spatial location of the meters, and the algorithms used to determine the metering rates affect the level of return.

Making the situation even more difficult is the fact that ramp meters are often installed at the same time as other freeway improvements such as variable message signs (VMS), additional travel lanes, and HOV lanes [25]. This makes it quite difficult to evaluate the benefits of the individual components.

Unfortunately, individual municipalities generally do not perform thorough evaluations of ITS deployment activities. Any evaluation is almost always performed to justify expenditures instead of attempting to understand why and under what conditions benefits occur [34]. ITS benefit studies rarely provide information concerning the pre-existing conditions or the specific implementation details. Therefore, it is extremely difficult for an outside researcher to combine data from several different systems and determine what factors lead to greater improvements.

These factors cause ITS professionals to have a very difficult time determining which parameters determine the level of benefit generated by ramp metering. Without understanding what drives benefits it is extremely difficult to predict the benefits that will be generated by a ramp metering system design.

The failure to perform and share ITS benefit analyses has led to two significant problems. First, appropriation committees are unable to predict accurately what budget is needed to achieve their ITS goals. Additionally, once a budget is selected, engineers are unable to recognize an inefficient ITS design. Earlier mistakes are repeated and inefficient designs are copied. If this situation is not improved, public money will continue to be wasted.

The goal of this research is to investigate the relationship between the costs and benefits of ITS projects. However, due to time and feasibility constraints this study will only analyze ramp metering systems. Choosing ramp metering systems allows this exploration to focus on one area of ITS technology and reduces the complexity and state space of possible deployment schemes. For the purpose of fulfilling this goal, two specific objectives for this study have been established:

1. To generate a performance-cost tradeoff curve (i.e. optimal frontier) which clearly illustrates the relationship between the cost and achievable performance of a ramp metering system.
2. To develop useful ramp metering guidelines from the information gained while building and analyzing the tradeoff curve.

The relationship between the benefits and costs of ramp metering has not been sufficiently explored and the shape of the optimal frontier between performance and cost is unknown. Once generated, the optimal frontier curve will be an extremely helpful tool that will allow financial funding committees of ramp metering systems to objectively choose an appropriate budget for a project given their desired benefits and monetary constraints. Figure 1.2 illustrates possible shapes of the performance-cost tradeoff curve.

Figure 1.2: Possible Shapes of performance/cost tradeoff curve

The ramp metering guidelines will contain information that the transportation professional can reference when designing or evaluating a proposed ramp metering system. It will inform the reader which parameters drive ramp metering benefits and how other parameters affect the system. By following these guidelines, ramp metering designers will be able to choose an efficient design which generates the maximum possible benefits for their budget and lies on the optimal portion of the performance-cost tradeoff curve.

This study investigates the relationship between the costs and benefits of ITS projects. However, in order to maintain a manageable level of complexity and increase the likelihood of generating useful recommendations, the scope of this research was limited to one type of ITS project: ramp metering.

Additionally, due to time and data constraints, all ramp metering deployment schemes were tested on models of roadways in Southeastern Virginia. Precautions were taken to ensure that the results from this study are transferable to other freeways, but it is beyond the range of this study to test multiple freeway locations in different geographic areas.

Multiple ramp metering algorithms need to be implemented in order to determine the maximum possible benefits of a ramp metering system. However, some metering algorithms are extremely complicated and are still in the developmental stage. Advanced metering algorithms that incorporate neural networks, fuzzy logic, and traffic prediction were not used in this study since their implementation and testing are significant research endeavors in themselves.

The remainder of this report details the study performed to generate the performance-cost tradeoff curve and ramp metering guidelines. Chapter Two provides a Literature Review focusing on prior research in the measurement and evaluation of ITS benefits. The simulation-optimization methodology employed to generate the tradeoff curve and the measures of performance used are described in Chapter Three. Chapter Four provides details of the implementation of the simulation-optimization methodology. This chapter focuses of the development of the traffic simulation model and the pseudo-random search methodology applied to locate the "optimal" deployment scheme. The results of the study are presented in Chapter Five, where the shape of the tradeoff curve is discussed. Chapter Six is dedicated to testing assumptions and performing a sensitivity analysis. The affects of modeling assumptions and site-specific variables on the results are discussed in this chapter. Chapter Seven contains conclusions about the performance-cost relationship and lessons learned from the curve can lead to more efficient ramp metering designs. This section also contains conclusions about the simulation-optimization methodology and recommends areas of future research.

  Chapter 2: Literature Review

Many government agencies and private businesses use the benefit-cost ratio method to evaluate and compare capital investment projects. The ratio is calculated by dividing the present value of the expected benefits of an investment by the present value of its expected costs. The value of the ratio is directly related to the investment’s rate of return, where higher ratio values correspond to larger rates of return. Investments with a benefit-cost ratio value less than one should not be considered since they produce a rate of return lower than the risk-free interest rate.

Analysts employing this method to choose between mutually exclusive projects must exercise caution since the alternative with the largest benefit-cost ratio will not necessarily produce the largest profit. It is possible that an alternative requiring a larger investment will produce a greater profit than an alternative with a larger benefit-cost ratio but requiring a smaller investment. Despite these shortcomings, the benefit-cost ratio is an excellent method for comparing the rate of return between many possible investments [6].

Benefits from ITS projects typically include reductions in delay, decreased accident rates, and lower levels of pollution. Since most benefits are not monetary it is often difficult to measure and directly compare the benefits of ITS projects. The ITS Joint Programs Office of the United States Department of Transportation (USDOT) has identified six metrics which it uses to measure the benefits of ITS projects. Termed "a few good measures," the metrics are "robust enough to represent the goals and objectives of the entire ITS program, yet are few enough to be affordable in tracking the ITS program on a yearly basis" [4]. These six metrics track the magnitude of safety improvements, delay reduction, cost savings, effective capacity improvements, customer satisfaction, and energy and other environmental impacts.

Each metric is tied to one of the ITS program goals. The safety measure focuses on reducing the number of accidents and lessening the probability of a fatality if a crash does occur. The delay reduction metric measures the total travel time as well the variability of travel times. The cost metric generally measures the difference in cost between an ITS solution and the preexisting condition. It is more meaningful when applied to ITS programs that lower operating costs such as electronic toll collection. The effective capacity metric tracks the maximum potential rate at which vehicles can traverse a network. Since the true potential is difficult to measure, the throughput of a roadway is often used as a surrogate measure. The customer satisfaction metric attempts to quantify the public’s happiness with the ITS implementation. It is often measured using surveys, questionnaires, or focus groups. Environmental impacts cannot be measured directly and must be estimated through simulation or other analysis. It is believed that, at least in the short term, smoother more efficient traffic flows will create a positive environmental impact. Long-term impacts, however, have not been measured and are not well understood [26].

The non-monetary metrics used to measure the benefits of ITS projects make benefit evaluation difficult. The vast majority of ITS projects have shown positive improvements indicating that some positive level of return is being generated by investments in ITS. However, without formal benefits analysis it is impossible to determine at what cost these improvements come. Additionally, it is impossible to compare the benefit per dollar of different ITS strategies or different implementations of the same technique.

The need for more rigorous ITS benefits analysis has been recognized for several years. In the paper "Models for Assessing the Impacts and Potential Benefits of Intelligent Transportation Systems," Ajay K. Ruthi of the Oak Ridge National Library states that the absence of a systematic analysis of the benefits and costs of ITS is well recognized in the ITS community [29]. This paper, written in 1995 for the Joint Programs Office (JPO) of the United States Department of Transportation, is the first call to action for the evaluation of ITS benefits. Although the paper lists several research organizations that are formulating benefits models, nothing yet has been produced that can accurately point Transportation Engineers towards efficient ITS designs.

This lack of benefit analysis, and consequential lack of design tools for ramp metering systems, was confirmed in December of 1998 when the Virginia Transportation Research Council (VTRC) performed its own thorough literature review of ramp metering systems. In the resulting publication, Ramp Metering: A Review of the Literature, VTRC senior research scientist E.D. Arnold Jr. states "although some attempts have been made to develop warrants, criteria, or guidelines for the implementation of ramp metering, few have been successful due to the many factors involved with ramp metering" [5].

Fortunately, a few researchers have recognized the need for thorough ITS benefits analysis and the lack of ramp metering system design tools. In their paper "Benefit/Cost Analysis on Ramp Metering: Optimization of Travel Time and Cost Factors," Haikun Dong and Bin Ran evaluate the benefit-cost tradeoffs that ramp metering system designers should be making. They developed a mathematical programming model with an objective function that considers throughput and cost while adhering to constraints that ensure the physical laws of traffic are upheld [13]. Although this model addresses a large need, it usefulness is diminished by the complex mathematics needed to evaluate the model, the deterministic nature of the model, and the lack of a high level description of the general shape of the tradeoff curve.

Vassilios Alexiadis and James Schmidt, supported by JHK & Associates, provided a look at the general shape of the benefit-cost tradeoff curve in their paper "Ramp Metering: A System Concept Design Methodology." During their research, Alexiadis and Schmidt performed traffic simulations on a 500-mile freeway network in California using four different ramp metering deployment schemes. Their empirical results showed that as the amount of equipment deployed increased, the benefit-cost ratio decreased [3]. This suggests that the tradeoff curve is concave down and that benefits rise quickly with lower budgets but do not increase at the same rate as cost at higher budgets. Although this is a significant finding, we must keep in mind that only four budgets were considered and no time was spent attempting to locate the optimal equipment locations or metering algorithm for each budget.

Traffic simulation is a powerful tool for modeling traffic flows along a roadway. It is useful for estimating the effects on traffic flow caused by events such lane closures due to construction and vehicle accidents or unusually high traffic due to an event such as a professional football game. Additionally, simulation can be used to predict the effects of proposed improvements such as lane additions, a new traffic light, and ramp metering.

Traffic simulations can be classified into two types: microscopic and macroscopic. In a microscopic simulation each vehicle is modeled as an individual entity. In a macroscopic simulation the high-level traffic flow is modeled. During each step of a microscopic simulation every vehicle will travel (accelerate, decelerate, maintain speed, change lanes, etc) based on its desired freeflow speed, desired following distance, and any upcoming exits. Sophisticated car-following logic controls each vehicle and directs its actions. In macroscopic simulations flow is modeled according to macroscopic traffic laws and parameters. Microscopic simulation is preferable for smaller scale simulations and simulations in which vehicle interactions, such as those found in merging and weaving sections, are significant. Macroscopic simulation is preferable when vehicle interactions are not significant or the roadway model is too large to make microscopic simulation practical [18, 21]

Developing a traffic simulation model is a very time-consuming task. The user must construct an accurate model of the roadway using blueprints, ariel photography, maps, or other data sources. Additionally, a large amount of traffic information such as the flow rate distributions of vehicles entering the simulation, vehicle destinations, and desired speed must be collected. Furthermore, the user must tune simulation parameters such as the roadway capacity and driver characteristics. Lastly, the user must compare simulation output to actual traffic data in order to validate the simulation is an accurate representation of the real world.

Despite its high level of labor intensity, the benefits of traffic simulation are numerous. Results are often obtained more quickly and less costly with traffic simulation than by performing field tests. Also, traffic simulation does not cause the disruptions that are often associated with field experiments. Simulation is occasionally the only option when field tests are impossible or their disruptions are unacceptable. Furthermore, traffic simulation is often more useful than field experiments. Simulation allows the user to hold variables constant and isolate only the parameters of interest. This can yield insight into which variables are truly important and how these variables interrelate. Lastly, the flexibility of simulation allows a user to quickly evaluate many proposed solutions and test "what if" scenarios [18, 21].

One negative aspect of traffic simulation is that accidents do not randomly occur during the simulation as they do on actual freeways. The user can simulate the effects of an accident by closing travel lanes, but the simulation will never spontaneously create an accident. One goal of ITS improvements is to lessen the likelihood and severity of a crash. Since accidents do not occur, traffic simulation alone cannot be used to evaluate the safety improvements of a potential ITS improvement.

When using traffic simulation to evaluate the benefits of a proposed improvement, a surrogate measure for accident rate must be used. The surrogate measures attempt to estimate the actual accident rate by using other traffic statistics. The estimators can be as simple as the historical average or can be complex equations taking into account factors such as flow per lane, mean speed, variance of the speed, lane width, etc. [14].

The Oak Ridge National Laboratory uses a relatively simple accident rate model in its ITS Deployment Analysis System (IDAS). The model considers only the percentage of the freeway capacity being utilized (volume / capacity) and the total number of vehicle miles traveled. Despite using only two predictor variables, the model is more sophisticated than most since it separately predicts accidents involving fatalities, accidents involving injuries, and property damage only accidents. The complete model is listed below.

Fatalities: 0.004 Fatalities per Million Vehicle Miles (MVM)

Injuries: 0.5156 Injuries per MVM (if volume / capacity is less than 0.78 )

0.5757 Injuries per MVM (if volume / capacity is between 0.79 and 0.88 )

0.7329 Injuries per MVM (if volume / capacity is between 0.89 and 0.98 )

0.7642 Injuries per MVM (if volume / capacity is greater than 0.98 )

Property Damage Only: 0.8551 Property Damage Only per MVM

[2]

Prior research has shown that the variance of the speed is one of the most effective predictors of accident rate [15]. Using hourly speed data collected from data stations throughout the Virginia highway system, Nicholas Garber and Ravi Gadiraju employed linear regression analysis to create a model for the accident rate. The model obtained describes about 60% of the variance observed and has the form:

ACCRT = 43.2 + 0.00347(SPVA)² Equation 2.1

Where

ACCRT = Number of accidents per 100 million vehicle miles

SPVA = Speed Variance

[15]

In 1999 Angela Ehrhart extended Garber’s work by creating a more complex model to estimate the accident rate. Like Garber’s study, Ehrhart also used hourly traffic data collected from data stations throughout the Virginia highway system. Using a heuristic process called the multivariate ratio of polynomial procedure, Ehrhart generated the following model (Ehrhart, 52):

CRASHRATE = ((-0.4468269) – (3.13093E-03)*(SD*SD) – (1.469674E-

06)*(SD*SD)^2 + (2.797139E-07)*(FPL*FPL) – (6.315968E-

10)*(SD*SD)*(FPL*FPL) + (2.384377E-14)*(FPL*FPL)^2 +

(3024.788)*(1/(MEAN*MEAN)) + (15.15044)*(SD*SD)*(1/(MEAN*MEAN)) –

(5329379*(1/(MEAN*MEAN))^2)

Where

SD = Speed Variance

FPL = Flow Per Lane

MEAN = Mean Speed

[14]

This model has a R² value of 0.5816 and an Akiake information criterion (AIC) of –475.68. However, given the complexity of the equations and number of predictor variables, it seems likely that this model may be overfit to the training data used to generate the model.

All three models presented above were implemented in the simulation model. The estimates of the accident rate generated by each of the three models were compared to each other and to the historical accident rate in the test area.

Ehrhart’s model was eliminated due to the poor quality of its results. When traffic data generated by the simulation run were used as the input, the model predicted a negative accident rate. Since negative accident rates are impossible, the model was no longer considered.

The results returned from the ORNL model and Garber’s model were similar, although the ORNL prediction tended to be higher. However, when the standard deviation of the speed was around twelve miles per hour, the two models predicted the same accident rate.

The ORNL model was discarded since it is contradictory to historical accident data . The ORNL predicts that the accident rate will increase as use of the road reaches capacity. However, field results show that ramp metering not only brings traffic flows closer to their theoretical capacity, it also decreases the accident rate. Therefore, the ORNL model predicts that implementing a ramp metering system will increase the accident rate although historical data clearly shows that this is not the case.

Before implementing Garber’s model as the predictor for accident rate, predictions generated by the model were compared to historical accident data. Simulations using actual historical traffic data were performed and Garber’s model was used to predict the number of accidents that would occur between 6:30AM and 8:30AM on weekday mornings on the test section of road. Garber’s model predicted 16.5 accidents during the course of one year, an average of 1.375 per month. The Smart Travel Lab’s incident database was queried to see the actual number of accidents that occur on this stretch of road between July 1998 and June 1999. Except during May of 1999, whose six accidents were at least twice as high as any other month, the average number of monthly accidents was 1.55. The May data appear to be an anomaly and may be due to construction, severe weather, or other factors. However, even if the May data are included, it is obvious that the prediction generated by Garber’s model is satisfactorily close to actual accident levels. Therefore, Garber’s model will be used to predict the accident rate in all future simulation studies.

In addition to the simple clock-time metering algorithm, five traffic responsive metering algorithms were implemented as control policies for the ramp meters. The five algorithms are speed control, occupancy control, demand-capacity control, ALINEA, and a bottleneck algorithm. The following sections detail the logic embedded in each of these traffic responsive algorithms.

The speed control algorithm utilizes real-time speed data collected from the vehicle detectors. Measurements from the immediate upstream detector are often used, but data from downstream detectors can also be used.

The speed measurements are compared to a preset lookup table. Table 2.1 provides an example of a speed lookup table. The measurements are compared to the values in the table and the appropriate metering rate is applied. If the designer desires a more precise return from the lookup table, the metering rate can be interpolated if the speed value falls between two thresholds.

Table 2.1: Speed Control Lookup Table

The occupancy control algorithm is extremely similar to the speed control algorithm. Real-time traffic measurements are again taken from the immediate upstream sensor and compared to a lookup table. However, in this case the metering rate decreases as the occupancy of the mainline increases. Table 2.2 provides an example of a Occupancy control lookup table.

Table 2.2: Occupancy Control Lookup Table

The demand-capacity algorithm attempts to prevent the demand downstream of the entrance ramp from exceeding capacity. The current demand is measured using vehicle detectors placed upstream of the entrance ramp. The metering rate is determined by subtracting the current upstream demand from the maximum downstream capacity. For example, assume downstream capacity is 7200 vehicles per hour (vph). If the upstream vehicle detectors record a demand of 6500 vehicles per hour, then the meter will release vehicles at the rate of 700 per hour.

In times of unusually high or low demand, the minimum metering rate is often set to 240 vehicles per hour and the maximum metering rate is often set at 900 vph. Releasing fewer than 240 vehicles per hour usually leads to excessive delays and the vehicles will often become impatient and proceed through a red light. On the other hand, releasing over 900 vehicles an hour leads to a cycle time of less than four seconds, and it is difficult for vehicles to keep up with the signal.

Asservissement Linéaire d’entrée Autoroutière (ALINEA) is a local feedback ramp metering strategy developed by M. Papageorgiou, H. Hadj-Salem, and F. Middelham. The algorithm attempts to keep the mainline occupancy near at an optimal rate known as the "critical occupancy." However, unlike most traditional metering algorithms, ALINEA uses the occupancy measurement as well as the metering rate during the previous period when calculating the metering rate for the current period. This allows the ALINEA algorithm to react smoothly to large differences and respond to small fluctuations in the occupancy measurement. The metering rate is for any given period is calculated as follows:

r(k) = r(k-1) + K_R[ô – o_out(k)] Equation 2.3

Where

r(k) = number of vehicles to be released this period

r(k-1) = actual ramp volume last period

K_R = regulatory parameter (units: vehicles per hour)

ô = critical occupancy

o_out(k) = most recent occupancy measurement

[23]

Unlike the four local ramp metering algorithms described above, bottleneck algorithms are used in system-wide ramp metering. Instead of attempting to optimize traffic flow in the meter’s local area, multiple meters are controlled with the objective of optimizing the flow through a downstream bottleneck. Although many different control equations can be used, almost all attempt to ensure that the demand entering the bottleneck area does not exceed the capacity of the bottleneck. The number of vehicles released from entrance ramps added to the upstream mainline demand must be less than the capacity of the bottleneck. This algorithm often causes upstream meters to have more restrictive metering rates than they would if a local metering algorithm were used [33, 35].

Many problems exist in which a researcher is attempting to maximize or minimize an objective function. In general, there exists an objective function f(x) that translates decision variables into an objective function value. If f(x) is known, a maximum or minimum value can be located through the use of calculus or more sophisticated programming methods. However, cases exist where the objective function is in the form of a "black box" and the analytical description of the function is unknown. An example of this situation is a simulation model.

Several different methods are available that attempt to find the set of decision variables which optimizes the value of the objective function. If time were not a constraint, all possible solutions would be evaluated. The solution with the highest (or lowest) value of the objective function would easily be identified as the optimal solution. Unfortunately, time constraints often cause a complete search of the state space to be infeasible. Another method is to test a randomly selected subset of all possible solutions. Although it cannot be stated with complete confidence, the solution in the subset with the highest (or lowest) value of the objective function could be considered the optimal solution. This method requires less time than a complete search, but drastically reduces the probability of finding the optimal solution. A third option is to use a pseudo-random search method. Pseudo-random search methods attempt to locate the optimal solution without searching the entire search space. These methods use the objective function value of previously evaluated solutions to determine where to search next. The idea is to evaluate solutions that are similar to, or in the same neighborhood as, previously tested solutions that performed well.

Simulated annealing is one proven pseudo-random search technique. In order to use simulated annealing it must be possible to represent the decision variables as a string of binary digits. The first step is to generate an initial solution. The initial solution, named S1, can be randomly generated or based on a good guess. The initial solution is evaluated and the objective function value, or measure of merit, for this solution is termed MOM(S1). This solution is then randomly mutated by probabilistically flipping the value of each digit in the binary string. The probability of a flip should be low such that only relatively small changes are made to this solution. The new solution, termed S2, is evaluated. If S2 is an improvement over S1, it is always accepted and S2 becomes S1. If S2 is not an improvement over S1, then it is still accepted with a probability based on the difference between MOM(S1) and MOM(S2) and the value of a variable called the temperature.

This process is then repeated. S1 is mutated in order to form a new string called S2. The new string is evaluated and accepted if MOM(S2) is greater than MOM(S1). If the measure of merit is not greater, then S2 may still be accepted with some probability. This cycle continues until a stopping criterion is reached.

The purpose of probabilistically accepting an inferior solution is to avoid getting stuck in a local maximum. Often, steps in the wrong direction are required to locate the global maximum. If S2 is inferior to S1, the probability of still accepting S2 is:

p = exp(delta/TEMP_k), Equation 2.4

Where

delta = MOM(S1) – MOM(S2)

TEMP_k = value of the temperature at the current step (step k)

[22]

The temperature is a parameter initially set by the user and reduced each iteration. The higher the temperature, the greater the probability of accepting an inferior solution. Thus, early in the search the probability of accepting an inferior solution is relatively high, but late in the search this probability approaches zero.

The search ends when a stopping criterion is met. The stopping criterion may be a maximum number or iterations or may be a number of iterations in which no improvement is found.

Simulated annealing is more efficient than random searches since the search focuses around solutions that have performed well. This focus increases the probability of finding the "optimal" solution without testing the entire state space. Additionally, simulated annealing is more robust than a strict uphill search since it probabilistically accepts inferior solutions. This keeps the search from getting stuck in a local optimum and increases the probability of finding the global optimal solution.

Figure 3.1 provides an illustration of the circular simulation-optimization methodology used to create the optimal tradeoff curve. The curve is generated by determining the maximum benefits possible from a variety of budgets. At each budget level the "optimal" deployment scheme is located using a pseudo-random search technique. All deployment schemes tested by the search technique are evaluated via traffic simulation.

Figure 3.1: Simulation-Optimization Methodology

Within each budget level, the search technique attempts to locate the deployment scheme that produces the largest benefits by exploring many different possible schemes (this occurs in box A). The type of metering algorithm and algorithm parameters used to control ramp metering equipment has a large effect on the level of benefits returned by the deployment scheme. Therefore, for each deployment scheme it is necessary to determine which ramp metering algorithm and parameter values generate the maximum benefit from the scheme (this occurs in box B). Once the best metering algorithm and parameter values are located, traffic simulation is used to evaluate the performance of the deployment scheme. Several different traffic scenarios are used to ensure the robustness of the scheme.

After the scheme is evaluated, it is mutated to form a new deployment scheme that meets the budgetary constraints. This new scheme is optimized, evaluated, and modified in the same manner as the previous scheme. This cyclical process continues until the pseudo-random search technique has located an optimal equipment deployment scheme or a stopping criterion is reached. If the stopping criterion is reached, the algorithm will consider the deployment scheme that generated the largest benefits to be the optimal scheme.

Once the optimal deployment scheme for a given budget is located, a point is added to the tradeoff curve. This point indicates the maximum benefits that can be achieved for that budget level. At this point the budget is incremented by a fixed amount and the above activities are repeated until an optimal scheme is located for this new budget. The maximum benefit level for this incremented budget is also marked on the tradeoff curve. This process continues until there are enough points that can be connected with a smooth curve to display the optimal tradeoff frontier.

The two technologies that can be deployed are ramp meters and vehicle detectors. A ramp meter may be located at each entrance ramp to the freeway. If no meter is present, vehicles continue onto the freeway without delay. If a meter is present, vehicles are released onto the highway one at a time. The rate vehicles are released is determined by the metering algorithm used.

In order to bring the number of possible deployment schemes to a manageable number, the mainline has been broken into discrete zones one-half mile long. Each mainline zone (one-half of a mile in length) may contain one vehicle sensor. Traffic data gathered by the vehicle detectors are communicated to ramp meters allowing the use of traffic responsive metering algorithms.

The decision variables are binary digits that indicate whether a technology is deployed at each potential location. Therefore, a decision variable is needed for each ramp. If the decision variable has a value of one, a ramp meter is deployed on this entrance ramp. If no meter exists, the decision variable is given a value of zero. The same representation is used for vehicle detectors. If a mainline zone contains a vehicle detector, the corresponding decision variable has a value of one. If no detector exists, the decision variable has a value of zero.

When these binary decision variables are placed in order from the furthest upstream point of the freeway to the furthest downstream, a binary string is created that completely defines the deployment scheme. Figure 3.2 provides an illustration of representing a section of roadway as a binary string. The scheme in this figure can be represented by the string "1011."

Figure 3.2: Binary Representation

The performance of all deployment schemes is evaluated in a variety of different traffic scenarios. This is done to ensure the robustness of each scheme and to more accurately model the demand fluctuations experienced by freeways.

Three distinct scenarios are simulated: normal demand, heavy demand, and accident occurrence. The traffic demand in the normal scenario is the actual traffic demand experienced on the test days. The traffic demand experienced in the heavy scenario are higher than the demand used in the normal scenario. The arrival rate at each entrance ramp is increased by twenty percent, and the arrival rate at the upstream mainline entrance of the freeway is increased by ten percent.

The accident scenario is modeled with two different simulation runs. Each run has the same traffic demand as the normal scenario, but contains a fifteen minute incident on a three-lane section of road. During the first ten minutes, the left-most lane is completely closed and the middle lane has a reduced capacity due to rubbernecking. During the final five minutes the middle lane is back to full capacity, but the left-most lane is partially blocked due to rubbernecking and/or debris on the road. In the first accident simulation run the incident is located in the first one-third of the modeled freeway. In the second accident run the incident is located in the final one-third of the modeled freeway. The different locations are needed to ensure that certain deployment schemes are not favored by the location of the accident.

Each deployment scheme will by evaluated via simulations of all four traffic conditions (one normal, one heavy, and two accident). The performance during each scenario will be used to calculate a total performance score for the scheme.

The USDOT uses six measures of performance (MOP’s) to compare the benefits of ITS projects. These six metrics track the magnitude of safety improvements, delay reduction, cost savings, effective capacity improvements, customer satisfaction, and energy and other environmental impacts. The delay reduction, effective capacity improvement, customer satisfaction, and energy and environmental impact metrics are all highly correlated. An increase in effective capacity reduces delay which leads to more satisfied travelers, less wasted gasoline, and less pollutants outputted by the vehicles.

To avoid redundancy, this study will use three independent measures of performance instead of the six correlated metrics used by the USDOT. The three MOP’s are average system speed, accident rate, and cost. The average system speed is the average speed of all vehicles, in all parts of the model (including entrance and exit ramps), throughout the duration of the simulation. This metric is easy to calculate and accurately measures congestion on the freeway and the delays being experienced by travelers. The accident rate is a good measure of the safety improvements produced by the deployed equipment. The accident rate is estimated using Garber’s model which was discussed in the literature review. The cost of each deployment scheme includes the funds needed to install and maintain the ramp meters, vehicle detectors, and communications hardware. Maintenance costs are calculated assuming a five-year lifecycle. A complete description of the rules used to calculate costs is provided in Appendix A.

Many ramp metering systems are part of a larger Advanced Traffic Management System (ATMS). Traffic information is valuable to an ATMS because it may be used for incident detection, traffic predictions, or simply to alert commuters of the present traffic conditions. Therefore, the quantity of traffic information collected by the deployment scheme is the fourth, and final, MOP. The amount of information gathered is based on the number of vehicle detectors in the deployment scheme.

CORSIM, part of ITT Industries’ Traffic Software Integrated System (TSIS) suite, was chosen as the traffic simulation package used to evaluate all equipment deployment schemes. A combination of ITT’s old FRESIM and NETSIM models, CORSIM is a well documented and widely used microscopic simulation package. A significant portion of the benefits generated by ramp meters comes from smoothing out the randomness of traffic flows on the mainline and vehicles entering the freeway. Therefore, the car-level detail provided by a microscopic simulation package such as CORSIM is needed to accurately assess the benefits of ramp metering.

Other reasons for choosing CORSIM include its built-in ramp metering functionality and Run-Time Extension capability. The built-in ramp metering allows the user to easily implement basic ramp metering algorithms. The Run-Time Extension (RTE) is a dynamically linked library (DLL) written by the user which interfaces with COSRIM every second. The RTE allows the user to implement more sophisticated ramp metering algorithms and is also helpful for extracting performance data from the simulation.

The test area used for this research is a six and one-half mile stretch of Interstate 64 in the Hampton Roads area of southeastern Virginia. The westbound travel lanes from 3,300 feet south of the Military Highway Interchange to the Bay View Boulevard crossing are modeled. The roadway contains seven entrance ramps and eight exit ramps.

The six and one-half miles of freeway are partitioned into fourteen mainline zones, each approximately one-half mile long. Describing the state of the seven entrance ramps and fourteen mainline zones requires twenty-one binary decision variables. Therefore, there are 2²¹, or 2,097,152, possible deployment schemes. Figure 4.1 provides a diagram of the test area.

Figure 4.1: Diagram of the Test Area

Figure 4.2 provides an example of representing a deployment scheme as a binary string. Each digit of the binary string represents an entrance ramp or a section of road that may contain a vehicle sensor. If the area contains a piece of equipment the corresponding digit receives a value of one. If no equipment is located in the area, the digit is set to zero.

Figure 4.2: Binary Representation of a Deployment Scheme

Traffic patterns on this section of I-64 are largely influenced by the United States Naval base located on the Elizabeth River. The westbound travel lanes lead to the Naval Base and the freeway exit for the base is located near the western-most end of the model. The flow of commuters traveling to the base causes the morning traffic levels to be much higher than the afternoon traffic levels.

Ramp metering is most useful when implemented on roadways with high levels of congestion. In practice, ramp meters are only turned on during the morning and/or evening rush hours when traffic levels are at there highest. Since the modeled section of roadway has it highest levels of congestion in the morning, the simulation runs use morning traffic data.

If ramp meters were implemented on this stretch of freeway, they would likely be operating every weekday during the morning rush hour. Rush hour, which actually tends to last more than one hour, is the time of day when increased traffic demand leads to reduced speeds and delays for travelers. If simulation time were not a constraint, it would be logical for the simulation runs that evaluate each deployment scheme to last the entire duration of the morning rush hour. However, simulating this entire rush hour period is quite time consuming and requires nearly ten minutes per simulation run.

One timesaving solution is to assume that the performance of the deployment scheme can be accurately evaluated without simulating the entire morning rush hour period. It is reasonable to assume that the performance of the deployment scheme during a subset of the rush hour should be highly correlated to the performance of the deployment scheme during the entire rush hour period. Therefore, instead of modeling the entire rush hour, each run simulates the portion of the morning rush hour from 6:30AM to 6:50AM. This twenty-minute span was chosen because it has a higher demand than any other period during the day. The effects of modeling a twenty-minute time period instead of the entire morning rush hour are analyzed and discussed in the "testing assumptions" section of Chapter 6.

The traffic data used to populate the simulation runs were obtained from the Smart Travel Laboratory at the University of Virginia. The Smart Travel Lab possesses a data warehouse that contains daily traffic data dating back to June of 1998. Originally, historical averages of daily weekday volumes from 6:30AM to 6:50AM were going to be used. However, once implemented, the ramp metering produced no benefits when the simulation used these historical averages of traffic data. The averaging process smoothed most of the randomness that is found in a single day’s data. As mentioned before, smoothing this randomness is one of the features that cause ramp meters to produce benefits. Additionally, the historical averages tended to be lower than the actual traffic demand found on single days. The lower average traffic flow is likely caused by days of reduced travel due to holidays and severe weather events.

Since historical averages do not replicate actual daily traffic conditions, the simulation runs had to be populated with traffic data from individual days. Wednesday, August 11, 1999 and Monday, Aug 23, 1999 were chosen as the two test days. All traffic simulations use actual traffic data from one of these two days. The days were chosen because the traffic on these days followed the "normal" traffic pattern on the freeways of the Hampton Roads region of Southeastern Virginia. The Smart Travel Laboratory has scrutinized weekday traffic flows in the area and traffic demand on these two days follows the normal pattern. The plot of each day’s traffic data appeared as expected and neither day had reduced traffic flows due to weather, construction, accidents, or holidays. Additionally, most of the vehicle detectors were operational and each day had extremely few data points removed by the Smart Travel Lab’s data filters.

All simulation runs used to evaluate a performance scheme use data from the same test day. Before the first run the control program randomly decides which day’s data (August 11 or August 23) will be used in the simulation runs. It was assumed that two different days were enough to ensure the shape of the performance-cost curve would not be skewed by the peculiarities of a single day’s data. Chapter 6 tests this assumption and examines in closer detail what effect the input data has on the performance of the deployment schemes and the shape of the tradeoff curve.

CORSIM requires the user to specify the volume at all entrance points to the model and the turn percentage at all points in the model where vehicles have the opportunity to exit. The volumes for each entrance ramp and at the mainline entrance to the model are the actual volumes measured during the two test days and stored in the Smart Travel Laboratory’s database.

The turn percentage data is calculated directly from the volumes in the test data. Each exit ramp in the test area has a sensor (which contains a vehicle detector in each lane) on the exit ramp, immediately upstream of the exit ramp, and immediately downstream of the exit ramp. As long as two of the three sensors are functioning correctly, the percentage of vehicles that exit can be easily calculated. Historical averages are used for turn percentages in the two locations where failed sensors make the calculation of turn percentages impossible.

The data stored by the Smart Travel Lab are aggregated into two-minute intervals. Thus, every two minutes during the simulation runs both the input volumes and turn percentages are updated to reflect the changing traffic demand.

CORSIM requires the user to enter a statistical distribution to model the vehicle entry headways. The user can choose between the uniform distribution, normal distribution, or Erlang distribution. The traffic data in the Smart Travel Laboratory contains volume counts, but does not include any information regarding the distribution of the vehicle arrivals. Additional research and data collection needed to be performed in order to determine which distribution most accurately modeled the actual arrival distribution.

Inter-arrival times were collected and analyzed during two morning rush hours in February of 2000. Based on this analysis, the Erlang distribution with a shape parameter (K) value of two was selected to model the inter-arrival times. Of the three distributions that CORSIM makes available, the Erlang distribution with K equal to two most accurately models the actual inter-arrival times. Appendix B provides more detail on the data collection and analysis procedures. Additionally, Chapter 6 explores how the arrival distribution affects the performance of deployment schemes.

CORSIM’s internal logic contains many parameters that influence the behavior of individual drivers and affect the flow of traffic as a whole. Prior research has shown that using the default values for these parameters often leads to simulations that do not closely mimic the actual traffic pattern of the roadway [11, 36]. Therefore, a calibration process was performed to determine what parameter values would lead to simulation runs that most accurately modeled actual traffic flows.

Model parameters were iteratively varied and evaluated with a training set of traffic data. Each parameter set was evaluated by calculating the percentage deviation between the volume data and speed data from the simulation and actual measurement found in the training data. The process continued until the parameter set which minimized the deviation between the simulation traffic measurements and actual traffic measurements was found. This "best" parameter set was then evaluated against a test set to generate an unbiased estimate of how well the actual traffic flows were modeled. Appendix C contains a complete description of the calibration procedure.

The calibration process resulted in the following six actions:

1. Freeflow speed set at 70 mph on all mainstream links (default is 55 mph).
2. Car following aggressiveness set to 1.0 – 0.1 with a Pitt Car following constant of 5 feet (defaults are 1.5 – 0.6 and 10 feet).
3. Time required to make a lane change set at one second (default is 3 seconds)
4. Courtesy factor (percentage of drivers willing to yield the right of way to vehicles attempting to merge in front of them) set at 40% (default is 20%)
5. Location of one exit warning sign moved to two thousand feet before the exit (default location is twenty-five hundred feet before the exit).

When the final parameter set was evaluated against the test data set, the average speed error was 2.5% and the average absolute speed error 24.9%. The average volume error was 3.1% and the average absolute volume error was 11.6%. Although the speed error is higher than desired, the error levels are comparable to error levels experienced by past researchers. In his 1998 paper, Cheu describes using a genetic algorithm to test over four hundred different parameter sets for a FRESIM model of a freeway in Singapore. Even with all these tests he was never able to reduce the average speed error below 11% or the average volume error below 30%.

The ramp metering algorithm used to determine the metering rate can have a large effect on the performance of a ramp metering system. Fortunately, the Run-Time Extension provided with CORSIM allows the user to implement any ramp metering algorithm, or combination of algorithms he chooses. The following algorithms were implemented and available to ramp meters during the generation of results: clock-time metering, speed control, occupancy control, demand-capacity control, and ALINEA.

Although each algorithm uses different logic to calculate the metering rate, all the rates have some common attributes. In all algorithms traffic data is aggregated into thirty-second periods, and the metering rates are updated every thirty seconds using the previous period’s data. Each algorithm contains parameters that must be tuned in order to maximize the performance of the algorithm. Additionally, each algorithm contains a queue override feature to ensure the queue of vehicles does not spill back onto arterial streets. An advanced queue detector measures the length of the queue, and all algorithms will increase the metering rate if the queue is in jeopardy of backing up onto city streets.

The extremely large number of possible deployment schemes and the sizeable number of algorithms available to control each scheme makes searching the state space a daunting task. Two assumptions were made that reduces the time required to search the state space. The first assumption allows similar deployment schemes to be placed in equivalence classes which receive a single performance score. The second assumption greatly reduces the amount of time required to locate the optimal control policy for each deployment scheme. The following sections discuss each assumption in more detail.

The methodology described in Chapter Three states that time will be spent locating the best policy to govern each deployment scheme. If you refer back to Figure 3.1, this procedure takes place in box "B." With as many as fourteen different data sensors to choose from it would, however, be extremely time consuming to determine which sensor, or combination of sensors, should provide the data needed by a single ramp meter for a traffic responsive metering algorithm. Given that a single deployment scheme can include up to seven ramp meters, it could take hundreds of test runs to determine the optimal policy.

In practice, a sensor located immediately upstream or downstream of the ramp meter usually provides the data required by the traffic responsive metering algorithm. It is wasteful to spend a large amount of time considering all available sensors, when the best performing policy most often uses a sensor in close proximity to the ramp meter. The time spent testing all available sensors simply is not justified by the small increase in expected performance. Therefore, when being controlled by a traffic responsive algorithm, ramp meters only use data from a sensor located immediately upstream or downstream from the meter. This assumes that the increased performance from considering all sensors is insignificant and is not worth pursuing.

This assumption greatly limits the number of control policies that need to be evaluated for each deployment scheme. The majority of sensors have one upstream sensor and one downstream sensor. Therefore, there are only four possible states for each entrance ramp:

1. No meter available.
2. Meter controlled by a clock-time algorithm.
3. Meter controlled by a traffic responsive algorithm using data from the immediate upstream sensor.
4. Meter controlled by a traffic responsive algorithm using data from the immediate downstream sensor.

The benefits derived from this assumption are twofold. First, considering fewer sensors greatly decreases the time required to determining the best control policy. Second, having a discrete number of states for each ramp allows deployment schemes to be placed into an equivalence class. A single equivalence class contains many different schemes that are controlled in the same manner and should generate the same level of benefits.

For example, consider a deployment scheme in which only the first ramp contains a meter. Additionally, assume that the only sensor in this scheme is immediately upstream of this ramp. Obviously, the optimal policy for this scheme would be to control the first ramp with a traffic responsive algorithm that receives data from the sensor immediately upstream. Now consider a second deployment scheme, which is identical to the first, except that it has a second sensor located five miles downstream of the ramp meter. Most likely, the optimal policy for this scheme would also be to control the first ramp with a traffic responsive algorithm that receives its data from the sensor immediately upstream. These two deployment schemes are in the same equivalence class, since they have identical locations of ramp meters and are controlled by the same policy.

Each equivalence class contains dozens of different deployment schemes. In fact, while there are 2.1 million different deployment schemes, there are only 15,360 different equivalence classes. And since every scheme in an equivalence class should generate the same level of benefits, there is no need to test more than one scheme from each equivalence class.

While the equivalence class assumption reduces the amount of time needed to determine the optimal policy for a deployment scheme, the task is still far from trivial. After a sensor is selected to provide data for a traffic responsive algorithm, time must be spent determining which algorithm generates the best results. This process is made more complex by the fact that each algorithm contains parameters that can greatly influence the performance of the algorithm. An exhaustive search would first determine the optimal parameter values of each algorithm and then compare the performance of the algorithms. With four traffic responsive algorithms under consideration and no less than five appropriate parameter values for each algorithm, it is obvious that an exhaustive search would require a tremendous amount of time.

Since the traffic responsive metering algorithms receive data from sensors located near the meter, they are effectively attempting to optimize traffic flows in the meter’s local area. Thus, it is reasonable to assume the same metering algorithm and parameter values will perform best regardless of whether other entrance ramps have meters on them. If the same algorithm and parameter values are always optimal for a meter, then it is unnecessary to spend time determining the best policy for each equivalent class. The best performing algorithm for each state of each meter can be determined ahead of time and implemented whenever the state occurs.

Appendix D contains the results of the traffic responsive algorithm evaluation tests. The top performing traffic responsive algorithms (with appropriate parameter values) for each state is provided for each of the seven ramp metering locations. States zero and one are not included in Appendix D, since state zero indicates no meter is present and state one indicates clock-time metering.

It is also assumed that the same clock-time metering parameter value will be optimal regardless of the presence and control policy of other meters. Appendix E contains the results of the clock-time algorithm evaluation results.

With these assumptions in place, there is no longer a need to determine the optimal policy for each deployment scheme. The optimal policy can be determined from the algorithm evaluation test results located in Appendices D and E. Each meter will use a traffic responsive metering algorithm as long as one of the local sensors is available. If multiple local sensors are available, the meter will receive data from the sensor that generated the best test results. The clock-time algorithm parameter values will also be selected based on the results of the algorithm evaluation tests.

For example, consider a deployment scheme in which a meter exists on the second entrance ramp. As Appendix D indicates, if the immediate upstream sensor is available, it will be used. In this case an occupancy control algorithm with lookup-table 1 will control the meter. If this sensor is not available, the immediate downstream sensor will provide data for the traffic responsive algorithm. However, if the downstream sensor is used, the meter will be controlled by the speed control algorithm utilizing lookup-table 6. If neither sensor is available, a clock-time algorithm will control the meter. Results located in Appendix E indicate that a metering rate of one car every six seconds will be used.

The results provided in Chapter Five were generated using both the equivalence class and algorithm choice assumptions. These assumptions will be further analyzed in Chapter 6 and their impacts on the results will be discussed.

The costs of deployment schemes range from a minimum of $281,560 (if no sensors or ramp meters are installed) to a maximum of $922,210 (if a sensor and ramp meter is installed at every possible location). This total cost range was split into six budgets of equal width.

Simulated annealing was used to search for the optimal deployment scheme in each of the six budgets. Each search was seeded with a deployment scheme that was expected to perform well.

The process used to evaluate each deployment scheme is non-trivial since it considers three MOP’s that are measured during four different traffic scenarios (normal congestion, heavy congestion, and two accident occurrence scenarios). During each simulation run, the average system speed, accident rate, and amount of information collected are measured. These three MOP’s are then normalized on a scale from zero to one hundred. Each normalized score is then multiplied by the MOP’s weight and the products are summed to generate a single score for that simulation run. The weights assigned to the three MOP’s are provided in Table 4.1.

Table 4.1: Weight Assigned to each MOP

This process is repeated for each of the other three scenarios until four scores are generated, one score for each scenario. These four scores are then multiplied by the scenario weights and the products are summed to generate a single score for this four scenario iteration. Table 4.2 contains the weights assigned to each traffic scenario.

Table 4.2: Weight Assigned to each Traffic Scenario

The scenario weights were chosen to reflect the relative frequency of each scenario occurring. Thus, it is implied that normal flows will occur about three and one-half times as often as heavy flows are experienced. Likewise, it is implied that an accident will occur roughly one out of each ten morning rush hours. Accidents occurred during twenty-three morning rush hours between July 1998 and June 1999. A full year has approximately two hundred and fifty weekday morning rush hours. Therefore, accidents occurred on roughly 9.2% of all rush hour mornings.

This iteration score captures how well the deployment scheme fulfills each MOP during all four different traffic scenarios. If traffic simulation was a deterministic evaluation method, the iteration score could be used as the final score for the deployment scheme. However, due to the stochastic nature of traffic simulation, deployment schemes will receive different iteration scores due to the randomness in the simulation. Multiple replications must be performed in order to accurately estimate the actual performance score of a deployment scheme.

The number of iterations performed to evaluate a deployment scheme is dependent on the score of the current deployment scheme. If the current deployment scheme (S1) is scoring worse than the current max (S2), the current scheme is only subjected to three iterations. If the current deployment scheme is scoring higher than (S2), five iterations are performed. This rule ensures that high performing deployment schemes are sufficiently tested, but valuable simulation time is not wasted on poor performing deployment schemes. An analysis was performed to determine the sensitivity of the results to the number of iterations performed. The results of this sensitivity analysis are located in Chapter 6.

After five full iterations are complete, if the average iteration score of the candidate scheme is higher than the current maximum, the candidate scheme becomes the current maximum. This new maximum is then be mutated to form a new candidate deployment scheme.

If three or more iterations are completed and the candidate deployment scheme has a lower score than the current maximum, no more iterations are be performed. However, this inferior candidate may still be accepted as the new maximum. Equation 2.4 illustrated how the probability of acceptance can be calculated based on the current temperature and the difference between the scores of the current maximum and the candidate solution. Equation 2.4 assumes a deterministic evaluation process. However, traffic simulation is a stochastic process and the scores assigned to the candidate and maximum are only estimates of their true values. In fact, a candidate that appears inferior after a few iterations may actually have a higher performance score than the current maximum.

Equation 2.4 must be modified to account for the fact that we are not certain of the actual difference between the two performance scores. Although other methods could be used, the law of total probability was chosen to incorporate the uncertainty of the true difference in performance scores.

Based on the mean score and the variance of the scores of each deployment scheme, we can state with a certain degree of confidence that the current maximum score is actually higher than the candidate’s score. The confidence level can be determined by testing the hypothesis that the actual value of the two scores (u1 and u2) are equal. Since the number of replications performed is less than thirty, this is done by calculating the appropriate t score and comparing it to the t-value table. Equations 4.1 and 4.2 show how to calculate the t-score.

Where s_p² is calculated as:

Recall that a superior candidate will always be accepted and that an inferior candidate will be accepted with a probability equal to exp(delta/TEMP_k). Equation 4.3 presents the probability of accepting an apparently inferior candidate when a stochastic evaluation process is used.

Prob(accept candidate) = Prob(candidate is an improvement)*1 +

The value of the temperature drops throughout the simulation. This allows many backward steps to occur early in the search, but very few backward steps late in the search. The temperature was set so that early in the search an inferior, yet reasonable, candidate will have a forty percent chance of being accepted, and late in the search (around the 100^th iteration) a reasonable candidate will have a one percent chance of being accepted. A reasonable candidate is defined as having a score no more than ten points below the current maximum. This correlates to an average system speed approximately 0.75 miles per hour slower and approximately one more accident per year than the best solution.

These specifications require a temperature of 10.9 on the first iteration of the search and a temperature of 2.17 at the one-hundredth iteration. Each iteration, the temperature is decreased by multiplying it by .9838. Figure 4.3 provides the value of the temperature during each iteration.

Figure 4.3: Temperature at each Iteration of the Search

If a candidate solution is accepted as the new maximum, it will be mutated to form the next candidate. If it is not accepted, the current maximum will again be mutated to form the new candidate. In both cases, the probability of mutating each binary digit in the string is 0.1. Since there are 21 bits in the string, the expected number of mutations is 2.1 bits. It is felt that an expected value of two bits is large enough to generate a variety of candidates, but small enough to ensure that the candidates do not mutate too rapidly.

Eight hundred and twenty-eight deployment schemes were search and evaluated using the methodology described in Chapters 3 and 4. The performance of each deployment scheme and its cost is displayed in Figure 5.1. This figure provides our first look at the performance-cost tradeoff curve for ramp metering systems.

Figure 5.1: Performance and Cost of all Tested Deployment Schemes

Although the data appear quite noisy and the curve is surprisingly flat, several important observations can be drawn from these preliminary results. First, notice that in many cases the implementation of ramp metering produced positive benefits. The base model (no metering) received a performance score of forty-five. This level, marked with a thick red line, represents the traffic flow as it currently exists without any ramp metering equipment. It is obvious that well over half of the deployment schemes tested earned a performance score higher than forty-five. Surprisingly, if ramp metering is implemented, the amount of spending does not seem to strongly influence the performance score. The level of benefits returned from a $400,000 investment is only slightly lower than the benefits returned from an investment of $800,000. Even more surprisingly, for spending levels higher than $800,000, the performance of the ramp metering system appears to degrade as spending increases.

The relatio