Ramp metering is a very popular and effective way to prevent traffic congestion on freeways. Many different control strategies depending on the traffic characteristics and/or features of the freeway were implemented. Whatever strategy is used, it must be effective not only in terms of preventing traffic breakdowns or supporting recovery from congestion, but also of the simplicity of solving the mathematical problem underlying the control strategy. The paper introduces an approach for a coordinated ramp metering control strategy based on solving a non-linear optimization problem. The solution of the described problem was found using the Differential Evolution strategy giving a global optimum for non-linear and non-differentiable or multimodal functions. Numerical experiments were made using data from a section of the freeway A 57 in Germany operated by a ramp metering system. The results proved the effectiveness of the proposed approach compared with local ramp metering strategies.

Der Fachvortrag zur Veranstaltung ist im Volltext verfügbar. Das PDF enthält alle Bilder und Formeln.

1 Introduction

Ramp metering is a very popular and effective way to prevent traffic congestion on freeways. It is employed mainly for reducing delays for the users of high-volume freeways at critical times, improving safety by managing merging traffic as well as decreasing the number of traffic accidents and the consequential influences. Based on various assumptions and techniques, many different control algorithms were proposed. Ramp metering systems differ in the data used as control parameters, the schedule in which they should be applied, the areas where they function, and – in case of coordinated operation – the type of cooperation.

Depending on the data which a particular control strategy uses, it is possible to determine fixed-type, adaptive, and predictive policies. The fixed-time control methods are usually based on historical data, which include various driver behavior patterns. Adaptive algorithms calculate the required metering rates by adjusting to real-time conditions such as speed, volume, capacity, or other parameters. Finally, in predictive strategies, current data are analyzed and new short-term metering rates for the next step are determined depending on the results.

The areas where ramp metering algorithms are applied define the level of operation. If a single ramp operates independently and is not connected with neighboring entries, it is controlled locally, e. g. with the Demand-Capacity [1] or the ALINEA [2] algorithm. When various ramps are linked, they can be controlled connectedly to improve local strategies. There are three ways to connect control in order to get a better service quality within the freeway:

• In the cooperative strategy, the previous ramp upstream reacts to the pre-congested situation downstream reducing the metering rate to support the next ramp. This strategy is applied by the Helper [3] and the MILOS [3, 4] algorithms.
• Competitive algorithms are based on a comparison between the calculated metering rates. These ideas are realized in the SWARM [5] and the Bottleneck [3, 6] algorithms.
• The integral mechanism is used to find a consensus between the local optimal strategies and the system-wide strategy. The best known algorithms are the linear programming scheme [3, 7] and METALINE [8].

Strategies underlying ramp metering must be effective in different contexts. First of all, metering a ramp is only reasonable when entering vehicles cause congestion on the main roadway and no large delays on the entry ramps result from the control strategies. Secondly, the control algorithms should be chosen in consideration of the particular traffic characteristics and the geometry of the freeway. Last but not least, one of the most important requirements is the simplicity of the way in which the mathematical problem underlying the strategy could be solved.

The computation of metering rates can be formulated as an optimization problem. The paper presents an approach to establish a managing strategy for coordinated ramp metering based on solving a non-linear optimization problem for all entry ramps within a freeway facility, taking into account the facility as a complete system. In a general definition, it is a non-linear constrained optimization problem. For every particular application, it has individual details, e. g. equality-constraints showing the relation between on-ramps. Inequality constraints can be taken into account to restrict the set of possible solutions. For the mathematical formulation of the described problem, a combination of different functions to calculate the total travel time within the facility and, because of their structure, only numerical zero-order methods are applicable. The well-known Differential Evolution strategy, which delivers a global optimum for non-linear and non-differentiable or multimodal functions possessing good convergence at the same time, is used to solve the assigned problem.

2 Differential Evolution Optimization Approach

Being an iterative zero-order, stochastic direct search procedure based on main ideas of genetic algorithms, Differential Evolution can be used to find an optimum solution of nondifferentiable, non-linear or multimodal functions under certain conditions. Similar direct strategies like those by NELDER and MEAD [9] or by HOOKE and JEEVES [10] use the greedy criterion to decide whether the optimal parameters are found and, because of a fast convergence, have a risk to be trapped into local optima. In contrast to them, the Differential Evolution strategy guarantees finding a global optimum if it exists. The algorithm was first proposed by STORN and PRICE [11] and then developed further.

Good practical optimization procedures should fulfill the following requirements:

• the ability to handle different types of cost functions, including non-linear, nondifferentiable and multimodal,
• the possibility to parallelize the computation of cost functions,
• simplicity in setting control parameters and
• good convergence properties.

Differential Evolution was designed to be a stochastic direct search method. It means that only the value of the function but not the derivatives in every step is used and the method can be applied to different types of cost functions. This scheme uses a vector of optimized values where the stochastic perturbation of this vector could be done independently within different processors of even different computers. Principles of setting control parameters are very transparent and can be modified in every specific problem so that the Differential Evolution approach is applicable and adaptive. Many practical tests for classical well-known and non-classical specific cost functions allow considering a very good convergence of the described optimization method.

Let us give a basic scheme of the optimization by using the Differential Evolution approach [11]. For every generation, an N-dimensional parameter vector x_i,G, i = 1, …, NP, is produced. At each step, mutation, crossover, and selection are used. The initial population vector should be chosen randomly from the set of possible solutions. This technique generates a new parameter vector by adding a weighted difference of two vectors to the third. This operation is called mutation:

v_i,G+1 = x_r1,G + F × (x_r2,G - x_r3,G)    (1)

where: v_i,G+1 = mutated vector

x_r1,G, x_r2,G, x_r3,G = population vectors with random indexes r₁, r₂ , r₃ Î {1, ..., NP}

F = positive constant parameter that controls the differential variance, F Î [0;2]

The parameters of the mutated vector should then be mixed with the parameters of another predetermined vector to build a trial vector. This trial vector is

u_i,G+1 = (u_1i,G+1, ..., u_Ni,G+1)      (2)

rand(j) = the j^th evaluation of a uniform random number

CR = crossover constant which has to be determined, CR Î [0;1], a bigger value of CR gives faster convergence (in case if it occurs)

rnbr(i) = randomly chosen index, which ensures that u_i,G+1 gets at least one parameter from v_i,G+1

If the trial vector delivers a lower cost function value (in case of minimization) than the vector from which it was produced, the trial vector replaces that vector in the following generation. This operation is called selection. Successful combination of the three operations above may construct effective and fast algorithms to solve the considered problem.

Being a zero-order procedure, this method is independent of the function type and provides the possibility of parallel computing, which allows to widen the fitness function up to a very high scale and quickly find a solution using many computer hosts. The principles of setting control parameters are quite good explored; they are transparent and make the algorithm adaptive. Additionally, Differential Evolution has a good convergence, which guarantees that the solution will be found within a countable number of iterations.

3 Applying the Differential Evolution Approach to Compute Optimal Ramp Metering Rates

3.1 Freeway Facility Description

We consider a freeway facility with a ramp metering system controlling the access to the main roadway from all entry ramps. Depending on the traffic volumes and other factors, the ramp metering system can be either active or not. Therefore, activation parameters are defined and set for the freeway facility based on its traffic characteristics and geometry, the weather conditions, and other factors. For detecting optimal metering rates from the global point of view, it is proposed to use the solution of a mathematical optimization problem, which determines the minimal travel time (including delays on the entry ramps) for traversing the whole facility.

Figure 1 demonstrates a part of a freeway with entry and exit ramps. The investigated main roadway is divided into sections of two types. This division is characterized by the location of the entry ramps.

• (I) Sections of the first type consist of an exit ramp and the following segment up to the next entry ramp. The traffic volume in this case can be calculated as the difference between the volume upstream of the exit ramp and the volume of the exiting traffic.
• (II) Sections of the second type, which start where vehicles from the ramp enter the main roadway and end at the next exit, are more important in terms of optimization, because the traffic volume depends on the calculated ramp metering parameters.

Sections of both types have a total travel time which must be calculated in an on-line regime according to the current traffic conditions. Delays in the entry ramps, which are caused by the ramp metering system, are referred to sections of type II.

Figure 1: Structure of a freeway segment

In contrast to other similar methods to find optimal regimes, which use only local information or the linked combination of local entry access schemes, the presented policy supposes using all the information from the controlled freeway facility as a whole. For this, an analytical model consisting of different approaches to estimate the travel time on the main roadway and the delays on the entry ramps is applied. The segment capacities were estimated with the stochastic capacity estimation technique based on models for censored data by BRILON et al. [12].

3.2 Estimating the Travel Time on the Main Roadway

The applied approach to estimate the total travel time is based on distinguishing between travel times in fluid traffic conditions, which depend on the length of the segment, and travel time losses during congestion, which only depend on the volume-to-capacity ratio [13]:

Formel siehe PDF.

where: t = total travel time (veh∙h),

L = segment length (km),

v(q) = speed (km/h),

q = traffic volume (veh/h),

Δ = interval duration (h),

v_crit = critical speed at capacity (km/h),

t_loss = congestion-related travel time losses (veh∙h).

For the calculation of the average travel speed in fluid traffic conditions, the speed-flowrelationship by BRILON and PONZLET [14] from the German Highway Capacity Manual HBS [15] is used:

v(q) = v₀/(1+v₀/L₀ ∙ [C₀ – q])

where: v(q) = average speed (km/h),

q = traffic volume (veh/h),

v₀, L₀, C₀ = model parameters.

The parameters of the speed-flow-model (4) depend on the gradient, the speed limit, the location of the freeway inside or outside of urban areas, and the percentage of trucks. They were taken from the HBS [15].

The congestion-related travel time losses are estimated with the following model [13]:

t_loss(q,c) = A ∙ (q/c – 0.9)^B,

where t_loss = congestion-related travel time losses (veh∙h),

q = traffic volume (veh/h),

c = capacity (veh/h),

A, B = model parameters

For the model parameters, values of A = 60,000 and B = 3 were found to be representative for different types of freeways in Germany in previous research [13].

3.3 Estimating Delays on Entry Ramps

The delay due to the metering on the entry ramps can be estimated in the same way as the delay at the approach of an uncontrolled intersection (when ramp metering is inactive) or of a signal controlled intersection (when ramp metering is active). These delays depend on the volume-to-capacity ratio and are calculated with the model from the HCM 2010 [16]:

d(q) = [0.5 ∙ C ∙ (1-g/C)²]/[1 – min(1,q/c) ∙ g/C] + 900 ∙ T ∙ [q/c – 1 + √(q/c – 1)2 + (8 ∙ k ∙ l ∙ q/c)/(c ∙ T)]

where d(q) = average delay time (s),

C = phase cycle time (s),

g = green time within the cycle time (s), (always equal to 2 s in Germany),

q = traffic volume (veh/h),

c = capacity (veh/h),

T = duration of analysis period (h),

k = incremental delay factor that is dependent on controller settings,

l = upstream filtering/metering adjustment factor.

According to the methods for the assessment of traffic flow quality on freeways given in the HBS [15], which are based on the analysis of 1-hour intervals, the parameter T of the model (6) is set to 1 hour, and for the same assumptions the parameters k and I are set to 0.5 and 1, respectively. This formula can be used in both cases of estimation for controlled and uncontrolled entry ramps. The first component includes the delay caused by the signal control (and is zero without control), and the second component is the additional delay caused by a traffic demand volume exceeding the capacity. The entry capacity should be calculated based on the saturation flow if the ramp metering system is being activated as

Formel (7) siehe PDF.

where: s = saturation flow (veh/h)

and should be taken as a constant value when the system is deactivated.

3.4  Modeling Freeway Segments as Queueing Systems

To quantify the total travel time, the travel time on the main roadway and the delay on the entry ramps have to be summed up. The volumes measured at the detectors on the entry ramps and on the main roadway serve as input data for the optimization model. For each time interval (here: 1 minute), both travel time components are calculated with the models (3) and (6), respectively. In contrast to the classical stochastic approach based on a Poisson distribution for the arriving process and some stochastic distribution for the explanation of the service time, the deterministic (systematic) mechanism assumes to use a constant fixed arriving time for every request (vehicle) in a system and constant times for the service process. The assumed deterministic queueing system is a D/D/1 queue with deterministic arrivals and deterministic service times at 1 server.

Figure 2 illustrates how deterministic queueing systems were applied for modelling the different segment types. The following two types of queueing systems were defined.

• QS Type 1: D/D/1 queueing system used to model the traffic flow on the main roadway. The main traffic flow characteristics on the main road (traffic volume etc., see Models (3)(5)) are taken as input parameters. As an output parameter, the total travel time, estimated with Equation (3), is determined.
• QS Type 2: D/D/1 queueing system used to model the traffic flow on the entry ramps. Delays on the entry ramp arise because of a high volume on the main roadway and/or ramp metering. By varying the ramp metering control parameters, it is possible to minimize the service time.

The aim of formulating the problem is to find optimal regulation parameters for the Type 2 queuing systems to provide a higher level of quality for the whole freeway facility.

Figure 2: Types of queueing systems

3.5 Optimization problem statement

The problem described above can be considered as a non-linear multidimensional constrained global optimization problem with the following formulation: (...)

and the following constraints: (...)

where: t_j(x) = total travel time within the segment j (veh∙h)

d_j(x) = average delay time on the approach within the segment j (veh∙h)

x = vector of optimal cycle times for the investigated part of the freeway (s)

x^min, x^max = minimum and maximum limitations of the cycle times (s)

h(x), g(x) = equality and inequality constraints functions 

The formulation (8)-(9) is a general one. In every particular case, different additional equality and inequality constraint functions could be taken into account. For the investigated freeway section, a connection inequality relation for entry ramps, which control the access to the main roadway and function as a coordinated system, was used.

To find the solution of the problem (8)-(9), both analytical and numerical algorithms may be applied. The only limitation for using an analytical approach is the non-differentiability of the function estimating the delay on the entry ramps in case of congestion. Before the volume-tocapacity ratio equals 1, the problem (8)-(9) could be solved with traditional methods such as the Lagrange multipliers approach. But it is more complicated than applying numerical schemes. 

4 Numerical Experiments

4.1  Data Description

The experimental data for the numerical analysis were taken from a 16 km stretch of the freeway A 57 near Krefeld, Germany, which is operated by a ramp metering system. This system contains five entry ramps. Two of these ramps are connected and lead into the same merge point (cf. Figure 3). For the optimization procedure and the following analysis, traffic demand was estimated based on data collected by automatic loop detectors located before and after the merge points and on the entry ramps were used (cf. Figure 4). Traffic flow data in 1-minute intervals from both congested and uncongested periods in the morning peak hour were used. The segment capacities were estimated based on the concept of stochastic capacities, where – in contrast to deterministic capacities used in traffic engineering guidelines – the capacity is regarded as a random variable [12]. By randomly generating the segment capacity values in the simulation, a total of 1000 simulation runs was carried out in order to receive a realistic distribution of congestion occurrence. To simulate and optimize the system, the free software R was used.

Figure 3: Layout of the investigated freeway facility

Figure 4: Flow rates within part 3 of the investigated freeway facility

4.2 Optimization Results and Comparison with other Strategies

The found optimal metering rates were applied to calculate the total travel times on the main roadway and on the entry ramps. Firstly, the advantage of the described method in comparison with not using ramp metering at all was investigated. Then the results were compared with applying the local algorithm ALINEA. Hence, the following three scenarios were investigated:

• Scenario A: Ramp metering system is deactivated.
• Scenario B: Applying local algorithms (ALINEA).
• Scenario C: Using the proposed coordinated control strategy.

Comparing the results for scenarios A and C, Figure 5 shows the relationship between increasing delays on the entry ramps and decreasing travel times on the main roadway. In the diagram, 10 time periods of 30 minutes each are distinguished. The increments of delays on the entry ramps are less than 1 minute, while the maximum benefit on the main roadway, reached towards the middle of the investigated period, is close to 10 minutes.

Results of the comparison of the ALINEA and the proposed coordinated control strategy (scenarios B and C) are given in Figure 6. ALINEA results in smaller delays on the entry ramps, whereas the proposed approach leads to a significant reduction of travel times on the main roadway.

The application of different scenarios was investigated both during the whole analyzed 5-hour period (5:00 to 10:00 a.m.) and for peak traffic conditions. The obtained results are presented in Figure 7, indicating the percentages of simulation runs for which the respective control scenarios delivered the lowest total travel time losses.

For the whole analyzed time period, the deactivation of the ramp metering system (scenario A) resulted in the lowest total travel time in 29.5% of the simulation runs. This can be explained by including time intervals prior to and after the peak hours. In 5.1% of the simulation runs, scenarios B and C delivered the same result because of the existence of a minimum solution on the lower bounds of possible solutions. Scenario B was most effective in only 7.8% of the simulation runs, whereas the proposed coordinated control strategy (scenario C) was most effective in 52.1% of the simulation runs.

Figure 5: Differences of the per-vehicle delays on the entry ramps and on the main roadway between the scenarios C (proposed coordinated control strategy) and A (no ramp metering)

Figure 6: Differences of the per-vehicle delays on the entry ramps and on the main roadway between the scenarios C (proposed coordinated control strategy) and B (ALINEA)

Investigating the effectiveness of the scenarios only during peak traffic conditions, it was found that the proposed algorithm delivered the best solution in 87.7% of the simulation runs. In 1.7% of the simulation runs, the scenarios A and C gave the same best result, while both scenarios B and C were equally effective in 4.6% of the cases.

Figure 7: Comparing the effectiveness of the investigated control scenarios: Percentages of the simulation runs in which the respective ramp metering control scenario delivers the lowest total travel time losses.

5 Conclusions and Outlook

Ramp metering strategies differ considerably with traffic flow conditions, areas of practice, possibilities of adaptation etc. One of the main ideas of every policy is the simplicity of solving the problem on which the control algorithm is based. In the paper, a strategy for coordinated ramp metering based on the formulation of a global optimization problem for a freeway facility and finding the global optimum with the Differential Evolution procedure was proposed.

For a section of freeway A 57 in Germany, optimal metering rates were determined with the proposed coordinated control strategy. To prove its effectiveness, calculations applying no ramp metering, the local algorithm ALINEA and the coordinated strategy were conducted. Based on 1000 simulation runs of randomly generated traffic demand and capacity time series, the resulting travel time losses were analyzed. In 57.6% of the simulation runs, the proposed strategy resulted in the lowest travel time losses. Considering only peak traffic conditions, the new strategy even delivered the best result in 87.7% of the simulation runs.

Combining good convergence in finding the global optimal solution and high effectiveness, the proposed approach allows for effective coordinated ramp metering control in order to prevent traffic congestions on freeways. It can be easily applied within a freeway segment containing multiple metered ramps. A comparison of the proposed approach with existing strategies for coordinated ramp metering will be subject to future research. 

6 References

[1] AGHDASHI, S.: Traffic Flow Optimization in a Freeway with Stochastic Segments Capacity. Dissertation for the degree of Doctor of Philosophy in Operations Research, North Carolina State University, Raleigh, North Carolina, USA, 2013.

[2] PAPAGEORGIOU, M.; HAJ-SALEM, H; BLOSSEVILLE, J.M.: ALINEA: A Local Feedback Control Law for On-Ramp Metering. Transportation Research Record: Journal of the Transportation Research Board, No. 1320, pp. 58-64, 1991.

[3] LIPP, L.; CORCORAN, L.; HICKMAN G.: Benefits of central computer control for the Denver ramp metering system. Transportation Research Record: Journal of the Transportation Research Board, No. 1320, pp. 3-6, 1991.

[4] CIARALLO, W.; MIRCHANDANI, B.: RHODES-ITMS-MILOS: Ramp Metering System Test. Report AZ-02-481. Arizona Department of Transportation, USA, 2002.

[5] BERTINI, R.L.; ESHEL, O.; MONSERE, C.M.: Using Archived ITS Data to Measure the Operational Benefits of a System-Wide Adaptive Ramp Metering System. SPR 645 OTREC-RR-08-04, Transportation Research and Education Center (TREC), Portland, 2008.

[6] HOCHBAUM, D.S.; WOEGINGER, G.J.: A linear-time algorithm for the bottleneck transportation problem with a fixed number of sources. Operations Research Letters, Vol. 24, No. 1-2, February 1999.

[7] BOGENBERGER, K.; MAY, A.D.: Advanced Coordinated Traffic Responsive Ramp Metering Strategies. California PATH Working Paper UCB-ITS-PWP-99-19, Report for MOU 305, 3004, USA, 1999.

[8] PAPAGEORGIOU M.; HADJ-SALEM, H.; BLOSSEVILLE, J.-M.: Modeling and real time control of traffic flow on the southern part of the Boulevard Peripherique in Paris: Part II: Coordinated on-ramp metering. Transportation Research A, Vol. 24, No. 5, pp. 361-370, 1990.

[9] MATHEWS, J.H.; FINK, K.K.: Numerical Methods Using Matlab, 4th Edition, 2004.

[10] KIRGAT, G.S.; SURDE, A.N.: Review of Hooke and Jeeves Direct Search Solution Method Analysis Applicable to Mechanical Design Engineering. International Journal of Innovations in Engineering Research and Technology, Vol. 1, No. 2, December 2014.

[11] STORN, R.; PRICE, K.: Differential Evolution – A Simple and Efficient Heuristic for global Optimization over Continuous Spaces. Journal of Global Optimization, Vol. 11, No. 4, 1997.

[12] BRILON, W., GEISTEFELDT, J.; ZURLINDEN, H.: Implementing the Concept of Reliability for Highway Capacity Analysis. Transportation Research Record: Journal of the Transportation Research Board, No. 2027, pp. 1-8, 2007.

[13] GEISTEFELDT, J.; HOHMANN, S.: Model-Based Estimation of Congestion-Related Travel Time Losses on Freeways. Transportation Research Record: Journal of the Transportation Research Board, No. 2470, pp. 78-85, 2014.

[14] BRILON, W.; PONZLET, M.: Application of traffic flow models. In: Proceedings of the Workshop in Traffic and Granular Flow. World Scientific, Singapore, 1995.

[15] FGSV: Handbuch fuer die Bemessung von Straßenverkehrsanlagen (German Highway Capacity Manual, HBS). Forschungsgesellschaft für Straßen- und Verkehrswesen, Cologne, 2015.

[16] TRB: Highway Capacity Manual. Transportation Research Board, National Research Council, Washington D.C., 2010.