Transportation Research Part C 18 (2010) 489–506

Contents lists available at ScienceDirect

Transportation Research Part C

journal homepage: www.elsevier.com/locate/trc

A Pareto-optimization approach for a fair ramp metering

Qiang Meng a,*, Hooi Ling Khoo b

a b

Department of Civil Engineering, National University of Singapore, Singapore 117576, Singapore Department of Civil Engineering, Universiti Tunku Abdul Rahman (UTAR), Setapak 53300, Malaysia

a r t i c l e

i n f o

a b s t r a c t

This paper deals with a fair ramp metering problem which takes into account average travel delay distribution among on-ramps for an expressway system comprising expressways, on-ramps and off-ramps. A novel spatial equity index is de?ned to measure the evenness of travel delay distribution among on-ramps within the prede?ned on-ramp groups. An ideal fair ramp metering problem therefore aims to ?nd an optimal dynamic ramp metering rate solution that not only minimizes the total system delay, but also maximizes the equity indexes associated to the groups. Some of these objectives, however, contradict with each other, and their Pareto-optimality is explored. The fair ramp metering problem proposed in this paper is formulated as a multiobjective optimization model incorporating a modi?ed cell-transmission model (MCTM) that captures dynamic traf?c ?ow pattern with ramp metering operations. The MCTM then is embedded in the Non-dominated Sorting Genetic Algorithm II (NSGA-II) to solve the multiobjective optimization model. Finally, the Interstate I-210 W expressway-ramp network in the United States is adopted to assess the methodology proposed in this paper. ? 2009 Elsevier Ltd. All rights reserved.

Article history: Received 26 September 2007 Received in revised form 1 October 2009 Accepted 1 October 2009

Keywords: Ramp metering Equity Multiobjective optimization model Pareto-optimality Cell-transmission model

1. Introduction Ramp metering is an application that regulates vehicles at on-ramps entering to expressways by means of a proper ramp metering rate solution. It is a practical traf?c control strategy to mitigate traf?c congestion on an expressway-ramp system, which consists of expressways’ mainline sections, on-ramps and off-ramps. A ?eld study carried out by Cambridge Systematics (2000) has demonstrated some bene?ts of ramp metering, such as, increasing expressway’s throughput, reducing total system travel time and enhancing traf?c safety. Papageorgiou and Kotsialos (2002) performed a comprehensive overview on how and why ramp metering improves traf?c ?ow conditions. Over years, researchers have neglected one vital issue concerning the performance of ramp metering, namely the ramp metering inequity issue. Although this issue has been raised in the literature as early as 1960s (Pinnel et al., 1967), it has been neglected. Only until recently when this lack of consideration of user equity has adversely affected public acceptance and handicapped the widespread adoption of ramp metering, researchers start to realize its importance. The public resistance is evident in research studies carried out on the drivers in Portland (Alkadri, 1998) and Twin Cities (Levinson and Zhang, 2006) in America. Levinson and Zhang (2006) reported that the ramp metering algorithm used in Twin Cities provoked the inequity issue, in which long trips drivers are favored compared to short trips drivers. Hence, it is urgent that the inequity issue should be addressed and considered in the future ramp metering research studies. According to Levinson and Zhang (2006), there are two types of ramp metering equity, namely the temporal and spatial inequity. Temporal inequity measures the difference of travel time, delay or speed among drivers who travel on the same route but arrive at the on-ramp

* Corresponding author. Tel.: +65 6516 5494; fax: +65 6779 1635. E-mail address: cvemq@nus.edu.sg (Q. Meng). 0968-090X/$ - see front matter ? 2009 Elsevier Ltd. All rights reserved. doi:10.1016/j.trc.2009.10.001

490

Q. Meng, H.L. Khoo / Transportation Research Part C 18 (2010) 489–506

at different times. Spatial inequity measures these differences among drivers who arrive at different on-ramps at the same time. From a system manager’s point of view, the key objective to implement ramp metering is to improve the ef?ciency of the expressway-ramp systems. Usually, this is measured by a system ef?ciency index, such as total system travel time or delay. However, the system-wide bene?ts of ramp metering should not be achieved at the expense of some individuals, thereby causing user inequity in the allocation of ramp metering bene?ts. Therefore, it is important to develop a methodology that can compromise both objectives in determining a ramp metering rate solution. 1.1. Literature review Since the pioneering work by Wattleworth and Berry (1965), there have been considerable ramp metering studies. These studies can be, in general, classi?ed into two categories – with and without taking into account the equity constraints. Because this paper is concerned with equity in ramp metering, more emphasis is placed on it as compared to the latter category. 1.1.1. Ramp metering without the equity constraints Static and dynamic ramp metering have been the two main approaches adopted in the past. Under static traf?c ?ow conditions, linear programming and bi-level programming models were built to determine an optimal ramp metering rate solution (e.g., Iida et al., 1989; Yang and Yagar, 1994). To consider dynamic nature of ramp metering, more emphasis has been put on algorithm design and analysis to obtain the optimal dynamic ramp metering rate solution. A variety of optimal control theories coupled with proper dynamic traf?c simulation models have been applied for expressway or expressway-corridor systems (e.g. Papageorgiou et al., 1990; Stephanedes and Chang, 1993; Zhang et al., 1996; Zhang and Recker, 1999; Zhang et al., 2001; Kotsialos et al., 2002; Bellemans et al., 2003; Hegyi et al., 2002; Gomes and Horowitz, 2006). The objective for these studies is to minimize the total system travel time including ramp delay. The studies are differing by the research methodologies adopted. Some researchers attempted to employ a better traf?c ?ow model to describe dynamic traf?c ?ow conditions while others aimed to improve ef?ciency of ramp metering by applying various advanced optimal control theories. The state-of-practice for the ramp metering on the other hand, tends to be focused on the operational algorithms such as, BOTTLENECK (Jacobson et al., 1989), FLOW (Jacobson et al., 1989), ALINEA (Papageorgiou et al., 1991), ZONE (Lau, 1997), METALINE (Papageorgiou et al., 1997), HELPER (Lipp et al., 1991) and SWARM (Paesani et al., 1997). Most of these operational algorithms lack the proper optimization techniques in identifying a better ramp metering rate solution. Hence, microscopic traf?c simulation models such as INTEGRATION, MITSIM and PARAMICS were adopted to evaluate effectiveness of these algorithms; for example Hellinga and Van-Aerde (1995), Hasan et al. (2002), Chu et al. (2004), and Beegala et al. (2005). 1.1.2. Ramp metering with the equity constraints There were a few studies dealing with the ramp metering equity issue. Benmohamed and Meerkov (1994) were the pioneers in investigation of this issue. They gave an intuitive example with three on-ramps showing that average travel delays experienced by drivers on two on-ramps are dramatically different, ranging from zero to two time periods of interest, if dynamic ramp metering rate solution follows the feedback law suggested by Papageorgiou et al. (1990). To distribute the average travel delay incurred on the interested on-ramps more evenly, Benmohamed and Meerkov (1994) proposed a dynamic traf?c control architecture that needs to calculate ramp metering rate based on the decentralized control law and local measurements for the bene?t of individual expressway’s segment. This is inspired by a data network ?ow control mechanism. Unfortunately, this dynamic traf?c control architecture is not applicable in practice because its assumption on traf?c ?ow conditions is unrealistic (refer Section 1 and Section 2.1 of Benmohamed and Meerkov (1994)). Papageorgiou and Kotsialos (2001) de?ned an equity constraint for each on-ramp that aims to keep queuing length at the on-ramp within a desired threshold. They also built an optimization model to determine the optimal ramp metering rate solution, in which the objective function includes a penalty term de?ned by the ramp metering equity constraints with different predetermined weight factors. These weight factors have signi?cant impact on the ramp metering rate solution. Nevertheless, it is a challenging issue to determine these weights in practice. Kotsialos and Papageorgiou (2004) continued to develop an optimal freeway network-wide ramp metering strategy, termed as Advanced Motorway Optimal Control (AMOC), for the ring-road of Amsterdam, the Netherlands. In AMOC, ramp metering control coordination is formulated as a dynamic optimal control model that can be numerically solved for given traf?c demands and vehicle turning rates over a time horizon. They found that by imposing a maximum queue requirement to the model, burden of ramp queuing needed to reduce the total system travel time is distributed among the on-ramps. They further mentioned that the equity is achieved at the expense of further improvement of the traf?c conditions, proving that equity and ef?ciency are two partially competing objectives of ramp metering operations. The new ramp metering algorithm, implemented in the expressway system between Twin Cities of Minneapolis and St. Paul, Minnesota, has imposed a maximum ramp delay constraint that ensures a delay of less than 4 min per vehicle on local ramps and less than 2 min per vehicle on expressway to expressway ramps (Cambridge Systematics, 2000). All of these practical equity constraints can balance the ef?ciency and equity to some extent. However, as Zhang and Levinson (2005) pointed

Q. Meng, H.L. Khoo / Transportation Research Part C 18 (2010) 489–506

491

out, the impact of these ramp metering operations with the equity constraints is dif?cult to evaluate in advance and the compromising process is achieved implicitly. Instead of using the above-mentioned equity constraints, Zhang and Levinson (2005) transformed the total system travel time according to an assumed relationship to balance the ef?ciency and equity of ramp metering. In order to give more priority to ramp’s users, travel delay encountered by ramp’s users is weighted non-linearly with respect to the actual waiting time. With longer waiting time, a larger value of weight parameter is allocated. Their method actually intends to ?nd a dynamic ramp metering rate solution that ensures on-ramps within same group encounter same delay by minimizing the transformed total system travel time. Nonetheless, such an ideal ramp metering rate solution may not exist in reality. Also, Yin et al. (2004) proposed a concave transformation function to capture the equity issue. While the transformation relationship is utmost important in expressing the equity issue, such function or relationship is unknown in practice or may not exist. Although there is an attempt done by Levinson et al. (2006) to quantify the transformation relationship through the virtual experience stated preference (VESP) method, the study could not come to a ?rm conclusion nor provide any concrete expression for the transformation relationship. This shows that the study of the weighting relationship is still immature at the current stage. 1.2. Objectives and contributions From the aforementioned literature review, it can be seen that an equity index is needed to re?ect the ramp metering equity issue since it is always addressed in ad hoc manner without a proper index or measure. Having had the equity index, it is an interesting and also important research topic about how to simultaneously take into account the equity and ef?ciency issues in ?nding a dynamic ramp metering rate solution. For the ease of exposition, such a problem is known as the fair ramp metering problem. This paper ?rst de?nes an equity index used to measure the degree of spatial equity that the ramp metering system can achieve. The equity index takes the ratio of the minimum and the maximum average travel delay incurred by on-ramp members in a group. It can be demonstrated that by maximizing the equity index can result in an even distribution of average travel delay experienced by drivers at on-ramps of a group. To some extend, the equity index quanti?es the spatial equity being a part of qualitative description of the perfect equitable metering de?ned by Zhang and Levinson (2005), which implies that there is no difference among drivers whenever/wherever they access the expressway through on-ramps. Having de?ned the equity index, the remaining challenge is how to balance both system ef?ciency and equity issue. This paper proposes a multiobjective optimization model incorporating with dynamic traf?c ?ow model to simultaneously consider both issues. Since it is a multiobjective optimization model, any type of the transformation relationship is not required. This can avoid dif?culty encountered by previous studies, in which a valid transformation relationship between both issues is necessary in capturing the equity issue. It can be observed from the literature review that researchers have stressed the importance of a realistic traf?c ?ow model in ramp metering optimization. The cell-transmission model (CTM) (Daganzo, 1994, 1995) is chosen as the traf?c ?ow model in this study. It is an approximation method for solving the hydrodynamic or kinematic wave model of traf?c ?ow (Lighthill and Whitham, 1955; Richards, 1956). The CTM well characterizes dynamic traf?c ?ow conditions because it is able to capture the horizontal queue, shock wave and ?rst-in-and-?rst-out (FIFO) condition. Without further enhancement, however, the CTM cannot be applied directly for the ramp metering operations. This paper therefore contributes a modi?ed celltransmission model (MCTM) with the ramp metering rate, in which a set of new formulae to calculate dynamic traf?c ?ow on a pair of merging links is derived. To solve the multiobjective optimization model proposed in this paper, a hybrid non-sorting genetic algorithm (NSGA-II) (Deb et al., 2002) that embeds the MCTM is employed. It can ?nd a set of Pareto-solutions for the fair ramp metering problem. The proposed model and solution method are tested and evaluated using an example network of I210 W of Pasadena, California. The remainder of this paper is organized as follows. Section 2 gives a novel ramp metering equity index and rigorously de?nes the fair ramp metering problem. Section 3 elaborates on the modi?ed cell-transmission model (MCTM) that characterizes dynamic traf?c ?ow conditions with ramp metering operations. Section 4 builds a multiobjective optimization model for the fair ramp metering problem. Section 5 presents the solution method for solving the proposed multiobjective optimization model. Section 6 evaluates the proposed model and solution method using a numerical example. Finally, conclusions and future studies are presented in Section 7. 2. Ramp metering equity indexes and ramp metering problem Consider an expressway-ramp network system comprising expressways, on-ramps and off-ramps. The expressway-ramp network system can be represented by a directed graph G = (N, A), where N is the set of nodes denoting heads and tails of onramps or off-ramps, A is the set of directed arcs denoting on-ramps, off-ramps and expressway stretches, and A # N ? N. ? ? ? ? More speci?cally, the set of arcs, A, is the union of four mutually disjointed sets – Aon , Aon , Aoff and AE – where Aon , Aon , Aoff and AE are the sets of metered on-ramps, un-metered on-ramps, off-ramps and expressway stretches, respectively. Let [0, T] denote time horizon for the dynamic ramp metering operations. To re?ect dynamicity of traf?c ?ow, the time horizon is discretized into T equal time interval of d, namely, [0, d, 2d, 3d, ? ? ?, (T ? 1)d]. Let Ca(t) be the time-dependent ramp

492

Q. Meng, H.L. Khoo / Transportation Research Part C 18 (2010) 489–506

metering rate from clock tick t to clock tick t + d, where t e {0, 1, 2, . . . , T ? 1}, for on-ramp a 2 A? , and C be a dynamic ramp on metering rate solution denoted by a row vector of all on-ramp time-dependent metering rates, namely,

C ? ?C a ?t?; a 2 A? ; t ? 0; 1; . . . ; T ? 1? on

?1?

The dynamic ramp metering rate solution is de?ned as the ?ow of vehicles at the on-ramp that is allowed to ?ow into the expressway at each time interval. Given a dynamic ramp metering rate solution C, the total travel delay of all vehicles on arc a e A experienced from clock tick t to clock tick t + d is a function of the dynamic ramp metering rate solution and time t, denoted by Da(C, t). It is assumed that traf?c demand is generated at the tail of each on-ramp without specifying their destinations, and that the traf?c leaves an expressway stretch through the head of an off-ramp with a known split ratio to the total traf?c ?ow of the expressway stretch. The assumption of given split ratios is quite common in the ramp metering studies (e.g. Gomes and Horowitz, 2006) but not perfect, since these ratios may depend on the traf?c control variables. A better alternative way is to assume known origin–destination information. However, Erera et al. (1999) has shown that segregating ?ows by destination introduces the problem of having to manage FIFO queue on the on-ramps which make the ramp metering problem intractable. On the other hand, Zhang and Levinson (2004) have provided convincing arguments in favor of the use of split ratios instead of origin–destination matrices. Let qa(t) be traf?c demand (in unit of veh/h) generated at on-ramp a 2 A? [ A? from on on clock tick t to clock tick t + d; ba(t) denote the turn proportion of vehicles on the expressway stretch exiting from off-ramp a e Aoff from clock tick t to clock tick t + d. Without loss of generality, it is assumed that the length of time interval d = 1 for ease of exposition hereafter. To measure ef?ciency of a dynamic ramp metering rate solution C, the total system travel delay, denoted by F0(C), can be used as a system ef?ciency index. The total system travel delay is the sum of travel delay encountered by all the vehicles when traveling on the expressway network system over the time horizon [0, T], shown below.

F 0 ?C? ?

T?1 XX a2A t?0

Da ?C; t?;

a2A

?2?

where Da(C, t) is the travel delay encountered by vehicles traveling on arc a e A of the expressway-ramp system at time interval t. The average delay for all vehicles at the on-ramp, a 2 A? [ A? over the time horizon [0, T], denoted by Da ?C?, can be calculated by on on

PT?1

t?0

Da ?C? ?

Da ?C; t? V a ?T?

?3?

where Va(T) is the traf?c volume at on-ramp a 2 A? [ A? over the time horizon [0, T]. Here, travel delay (in veh h) is de?ned on on as the extra time drivers spend due to the queuing or stopping and it essentially sums up the queuing and waiting time. In addition to the ef?ciency of a dynamic ramp metering solution, the equity issue on even distribution of average travel delay for several neighboring on-ramps should be examined from drivers’ point of view. Let us ?rst classify all the on-ramps into K groups, where K is a positive integer, and each group is represented by set Ak , k = 1, 2, . . . , K. Certainly, Ak is a subset on on of the set of all on-ramps, i.e., Ak # A? [ A? . Given a dynamic ramp metering rate solution C, the ramp metering equity inon on on dex for a group of on-ramps can be de?ned by the ratio of the minimum and maximum average travel delay incurred by the on-ramp members in the group, namely:

Ik ?C? ?

mina2Ak fDa ?C?g

on

maxa2Ak fDa ?C?g

on

;

k ? 1; 2; . . . ; K

?4?

According to Eq. (4), it follows that

0 6 Ik ?C? 6 1;

k ? 1; 2 . . . ; K

?5?

It can be seen that, the average travel delay for each on-ramp in on-ramp group k is the same if Ik(C) = 1. In other words, a dynamic ramp metering rate solution with the equity index of Ik(C) = 1 exhibits the ‘‘perfect spatial equity” for drivers using on-ramps within the same group. Here, the perfect spatial equity is de?ned as drivers suffer the same amount of average travel delay regardless of which on-ramp they choose within the group, for the entire time horizon. More interestingly, if the value of the equity index is approximate to one, a fairer ramp metering system is ensured. Hence, index Ik(C) is competent for quantifying the equity issue arising from ramp metering operations. It should be pointed out that this equity index cannot measure the temporal equity that ensures the travel delay equity for drivers entering the on-ramps at different times. However, the temporal equity index can be de?ned by ?rst calculating inequity for each time interval and then take the average of it, refer Section 4.2. The above de?ned spatial equity index can be extended to incorporate the temporal issue. Assume that the time horizon [0, 1, 2, ? ? ?, T ? 1] is discretized into H consecutive intervals [h, h + D], h = 0, 1, 2, ? ? ?, H ? 1, where D is a positive integer, namely,

?0; 1; 2; . . . ; T ? 1? ? [ ?h; h ? D?

h?0

H?1

?6?

Q. Meng, H.L. Khoo / Transportation Research Part C 18 (2010) 489–506

493

The average delay over the time interval [h, h + D] is de?ned by

Da ?C; h; h ? D? ?

Ph?D

t?h Da ?C; t? ; V a ?h; h ? D?

h ? 0; 1; 2; . . . ; H ? 1

?7?

where Va(h, h + D) is the number of vehicles at on-ramp a 2 A? [ A? during the time interval [h, h + D]. The relevant equity on on index over the time interval [h, h + D] is de?ned as follows:

Ik ?C; h; h ? D? ?

mina2Ak fDa ?C; h; h ? D?g on ; max k fDa ?C; h; h ? D?g

a2Aon

k ? 1; 2; . . . ; K; h ? 0; 1; 2; . . . ; H ? 1

?8?

Taking average of the time-dependent equity index expressed by Eq. (8) yields another equity index incorporating the temporal issue:

PH?1 Ik ?C; D? ?

h?0 I k ?C; h; h

? D?

H

;

k ? 1; 2; . . . ; K

?9?

Note that the temporal equity index expressed by Eq. (9) is identical to the equity index de?ned by Eq. (4) when D = T ? 1, namely,

Ik ?C; T ? 1? ? Ik ?C?;

k ? 1; 2; . . . ; K

?10?

A fair ramp metering system should impose a ramp metering rate solution with the equity index, de?ned by Eq. (4) or Eq. (9), as large as possible in order to ensure the equity of the system. While the equity is captured, ef?ciency of the ramp metering cannot be sacri?ced. The fair ramp metering problem thus aims to ?nd a dynamic ramp metering rate solution that can simultaneously minimize the ef?ciency index expressed by Eq. (2) and maximize the equity indexes de?ned by Eq. (4) or Eq. (9) associated with several on-ramp groups. Multiple objectives of the fair ramp metering problem may lead to various Pareto-ramp metering solutions. Without loss of generality, we will use the ?rst equity index expressed by Eq. (4) to present the following methodology. 3. Modi?ed cell-transmission model The CTM developed by Daganzo (1994, 1995) is an approximate numerical method solving the hydrodynamic or kinematic wave model of traf?c ?ow (Lighthill and Whitham, 1955; Richards, 1956) by adopting the relationship between traf?c ?ow f and density j as follows:

f ? minfv j; qmax ; w?jjam ? j?g

?11?

where jjam (veh/km/ln), qmax (veh/h/ln), v (km/h) and w (km/h) denote, respectively, jam density, in?ow capacity, free-?ow speed, and backward shock wave speed. Eq. (11) essentially approximates the piece-wise linear ?ow-density model. The CTM is de?ned on the cell-based network that is encoded from a network of interest. To build the cell-based network for the expressway network system G = (N, A), each arc a e A is ?rst subdivided into la cells, where la is a positive integer. The cell-based network assumes that the number of links entering and/or leaving a cell (degree of the cell) is not greater than three. Thus, all the cells can be classi?ed into three types: (a) ordinary if one link enters and one leaves, and these links are known as the ordinary links collectively denoted by set Xordinary, (b) diverging if only one link enters the cell but two leave, and these paired diverging links are denoted by set Xdiverge and (c) merging if two links enter and one leave, and these merging links are denoted by set Xmerge. If the expressway network G = (N, A) has some nodes with degree of greater than three, the cell-based network can be also constructed by adding some dummy cells. The number of vehicles in cell (a, i) of arc a e A, where i e {1, 2, ? ? ?, la}, at time t is denoted by nai ?t?. We need to identify two reserve capacities of the cell from time t and t + 1 – reserve sending and reserve receiving capacities – which are represented by Sai ?t? and Rai ?t?, respectively. For cells in expressway segments, un-metered on-ramps and off-ramps, these two reserve capacities can be calculated by the following formulae proposed by Daganzo (1995):

Sai ?t? ? minfQ ai ?t?; nai ?t?g;

i ? 1; 2; . . . ; la ; a 2 A? [ Aoff [ AE on i ? 1; 2; . . . ; la ; a 2 A? [ Aoff [ AE on

?12? ?13?

Rai ?t? ? minfQ ai ?t?; w=v ?Nai ?t? ? nai ?t??g;

where parameter Q ai ?t? is the maximum possible number of vehicles through cell (a, i) when the clock advances from t to t + 1, and parameter N ai ?t? is the maximum number of vehicles presented in cell (a, i) at time t. For a metered on-ramp, however, the reserve sending capacity of the last cell at the on-ramp is governed by the metering rate. Accordingly, the reserve sending and reserve receiving capacities for the last cell of a metered on-ramp can be determined by

( Sai ?t? ?

minfQ ai ?t?; nai ?t?g; minfC a ?t?; nai ?t?g;

i ? 1; 2; . . . ; la ? 1 i ? la

; a 2 A? on

?14?

494

Q. Meng, H.L. Khoo / Transportation Research Part C 18 (2010) 489–506

? ? ? Rai ?t? ? minfQ ai ?t?; w=v Nai ?t? ? nai ?t? g;

i ? 1; 2; . . . ; la ; a 2 A? on

?15?

Following the CTM, the MCTM also consists of two computational interrelated procedures – Modi?ed Procedure 1 and Procedure 2. The former procedure calculates the number of vehicles on a link connecting two cells in time interval from t to t + 1 and the latter updates the number of vehicles present in a cell at time t + 1. The Modi?ed Procedure 1, in reality, determines the maximum number of vehicle that can move from one cell to the next cell when the time advances from t to t + 1, namely, dynamic traf?c ?ow of a link connecting these two cells in the cell-based network. Purpose of Procedure 2 is to update occupancies of each cell at time t by applying the fundamental ?ow conservation law. 3.1. Modi?ed Procedure 1 – calculation of the number of vehicles on a link in time interval from t to t+1 Daganzo (1995) has shown two formulae to calculate the number of vehicles on an ordinary link and a diverging link from clock tick t to the next clock tick t + 1 denoted as y. These two formulae are available for this study, which are present below.

yai ai?1 ?t? ? minfSai ?t?; Rai?1 ?t?g; 8 >y <

bi cj ?t?

ai ai?1 2 Xordinary

?16?

n o ? bbi cj ?t? ? min Sbi ?t?; Rcj ?t?=bbi cj ?t?; Rdk ?t?=bbi dk ?t? n o; > y ?t? ? b ?t? ? min S ?t?; R ?t?=b ?t?; R ?t?=b ?t? : bd cj bi dk bi dk bi c j bi dk i k

?bi cj ; bi dk ? 2 Xdiv erge

?17?

where ordinary link aiai+1 connect ordinary cells (ai, t) to (ai+1, t); two paired diverging links bicj and bidk emanate from cell (b, i) of arc b e A and they respectively enter cell (c, j) of arc c e A and cell (d, k) of arc d e A; bbi cj ?t? is the known fraction of vehicles in cell (b, i) of arc b e A to cell (c, j) of arc c e A at time t; bbi dk ?t? is the known fraction of vehicles in cell (b, i) of arc b e A to cell (d, k) of arc d e A at time t. In view of the expressway-ramp network system operations, it is not reasonable to assume a predetermined fraction of vehicles in the start cell of a merging link that will emit to the end cell of the merging link in the time interval from t to t + 1. As a result, the formulae calculating dynamic traf?c ?ow on a merging link like an on-ramp of Daganzo (Eqs. (7a)–(7b), Daganzo (1995)) is inapplicable for this study. In reality, the merging process is governed by the aggressiveness behavior of vehicles competing to obtain the priority to ?ow. Usually, the more aggressive drivers will ?ow ?rst compared to the less aggressive drivers. However, in this study, the aggressiveness behavior of the drivers could not be embedded since CTM is a cell-based traf?c simulation model. Hence, it is assumed that vehicles from two different cells are allowed to ?ow into the merge cells based on their waiting time. In other words, vehicles with long waiting time on the paired links will ?ow into the merge link early than those vehicles with short waiting time. To some extent, this process satis?es the FIFO rule that is well recognized by various dynamic traf?c assignment models (Mun, 2007). For a merging cell, say (c, i), it can be seen that all vehicles that can be sent by both start cells of the paired merging links (ejci, gpci) – (e, j) of arc e e A and (g, p) of arc – can reach the merging cell (c, i) if Rci ?t? P Sej ?t? ? Sgp ?t?, namely,

yej ci ?t? ? Sej ?t? and ygp ci ?t? ? Sgp ?t?;

if Rci ?t? P Sej ?t? ? Sgp ?t?

?18?

If Rci ?t? < Sej ?t? ? Sgp ?t?, i.e., the merging cell cannot accommodate all vehicles from these two start cells of the paired merging links, we need to identify which fractions of vehicles from these two start cells will go to the merging cell in time interval (t, t + 1). Given the received capacity Rci ?t?, let kci ?t? denote the minimum wait time of the vehicles present in two cells (e, j) and (g, p) at time t that can enter merging cell (c, i) in time interval (t, t + 1). With FIFO rule, kci ?t? readily indicates which vehicles are allowed to ?ow. Accordingly, we assume that the traf?c ?ow disaggregated by waiting time s on the paired merge links are given by the following function of kci ?t?:

8 > nej s ?t?; if > <? ? yej ci s ?t? ? s ? kci ?t? nej s ?t?; if > > : 0; if 8 > ngp s ?t?; if > <? ? ygp ci s ?t? ? s ? kci ?t? ngp s ?t?; if > > : 0; if

s > jkci ?t?j? s ? jkci ?t?j? s < jkci ?t?j? s > jkci ?t?j? s ? jkci ?t?j? s < jkci ?t?j?

?19?

?20?

where jkci ?t?j? denotes the smallest integer equal to or greater than kci ?t?, and nai s ?t? denotes the number of vehicles in cell (a, i) of arc a e A that entered the cell in the time interval immediately after clock tick (t ? s). Logically, Eqs. (19) and (20) indicates that all the occupancies in the two start cells of the paired links that have entered to these cells at time interval prior to t ? kci ?t? can move to the merge cell. Conversely, none of those vehicles with s < jkci ?t?j can proceed. Of those vehicles having entered the two start cells in the time interval containing time t ? kci ?t?, only a fraction

Q. Meng, H.L. Khoo / Transportation Research Part C 18 (2010) 489–506

495

equal to the proportion of the interval that precedes kci ?t? is advanced. In addition, the aggregate traf?c ?ow on these two merge links can be expressed as

sej ?t?

yej ci ?t; kci ?t?? ?

X

s?1

yej ci s ?t; kci ?t??

?21?

sgp ?t?

ygp ci ?t; kci ?t?? ?

X

s?1

ygp ci s ?t; kci ?t??

?22?

where sej ?t? and sgp ?t? denote the maximum waits present in cell (e, j) and (g, p), respectively. Let Y ej gp ci ?t; kci ?t?? be the aggregate traf?c ?ows on the paired merging links (ejci, gpci), namely:

Y ej gp ci ?t; kci ?t?? ? yej ci ?t; kci ?t?? ? ygp ci ?t; kci ?t??

?23?

Eqs. (19) and (20) de?ne non-increasing, piecewise-linear functions of the minimum wait kci ?t?, which change in slope at the integers (see Section 4.2, Daganzo, 1995). Because these functions are non-increasing, function Y ej gp ci ?t; kci ?t?? is also a non-increasing and piecewise-linear function with respect to the minimum wait. Hence, it can de?ne a non-increasing inverse function of function Y ej gp ci ?t; kci ?t??, denoted by Uej gp ci , which gives the minimum wait kci ?t? at the two start cells of the paired merge links, for a given value of the aggregate ?ow Y ej gp ci :

kci ?t? ? Uej gp ci ?t; Y ej gp ci ?

Given Rci ?t?, the corresponding minimum wait can be calculated by

?24?

kci ?t? ? Uej gp ci ?t; Rcj ?t??; if Rci ?t? < Sej ?t? ? Sgp ?t?

Thus, the dynamic traf?c ?ow on the paired merge links can be calculated below.

sej ?t?

?25?

yej ci ?t? ?

X

s?1

yej ci s ?t; Uej gp ci ?t; Rcj ?t???

?26?

sgp ?t?

ygp ci ?t? ?

X

s?1

ygp ci s ?t; Uej gp ci ?t; Rcj ?t???

?27?

It should be pointed out that the above method is motivated by Section 4 of Daganzo (1995). Although it is straight forward, to our best knowledge, we are the ?rst to come out with such a method for calculating dynamic traf?c ?ow on a merging link. 3.2. Procedure 2: update the number of vehicles presented in a cell at time t+1 According to the ?ow conservation law, occupancy of a cell at time t + 1 equals its occupancy at time t, plus the in?ow and minus the out?ow, i.e.,

nai ?t ? 1? ? nai ?t? ?

X

hm 2C? ?ai ?

yhm ai ?t? ?

X

hm 2C? ?ai ?

yai hm ?t?;

i ? 1; 2; . . . ; la ;

a2A

?28?

where C+(ai) is the set of all start cells of those links that enter cell (a, i), and C?(ai) is the set of all end cells of those links that leave cell (a, i). 4. Mathematical model To formulate the fair ramp metering problem, the multiobjective modeling technique is employed because both ef?ciency and equity as the multiple objectives should be taken into account. In addition to multiple objectives, necessary practical constraints for a ramp metering rate solution should be elaborated as well. 4.1. Constraints for ramp metering rates To implement the ramp metering in practice, imposing some restrictions on the ramp metering rate solution is necessitated. Although emphasis on these restrictions is different, they can be formulated as constraints in the model building. Prior to a uni?ed and concise expression for these constraints, three typical ramp metering rate schemes are analyzed as follows. The dynamic ramp metering rate is set to be varied after multiple consecutive time intervals, but not at every time interval. By doing this, it could provide a stability of traf?c ?ow condition for the vicinity of the on-ramp. These multiple consecutive periods form a ramp metering period. More speci?cally, the discretized time horizon [0, d, 2d, ? ? ?, (T ? 1)d] is

496

Q. Meng, H.L. Khoo / Transportation Research Part C 18 (2010) 489–506

completely partitioned into M disjoint ramp metering periods, where M is a positive integer, named by ?Dl?1 ;Dl ?, l = 0, 1, 2, . . ., M, in which D0 = 0 and DM = (T ? 1)d. With these ramps metering periods, the aforementioned dynamic ramp metering solution become the period-dependent ramp rate pattern. 4.1.1. Period-dependent ramp metering rate scheme governed by the average queuing length In this scheme, ramp metering rate in the current metering period for a metered on-ramp is governed by the average queuing length on the on-ramp in the previous period, namely,

C a ?t? ? qa ? Ha ?Dl?1 ?;

8t 2 ?Dl?1 ; Dl ?; l ? 1; 2; . . . ; M; a 2 A? on

?29?

where 0 6 qa 6 1, referred to as the ramp metering ratio here, is a decision variable to be determined, and Ha(Dl-1) is the average number of vehicles at the on-ramp in the previous metering period ?Dl?2 ; Dl?1 ? that can be calculated by

P Ha ?Dl?1 ? ?

t2?Dl?1 ;Dl ?

Pla h

i?1

nai ?t? ?

P

hm 2C? ?ai ? yai hm ?t?

i ?30?

Dl?1 ? Dl

To some extent, Eq. (29) re?ects a dynamic feedback control strategy of traf?c ?ow. 4.1.2. Period-dependent ramp metering rate scheme with the reserve receiving capacity split ratio To mitigate traf?c congestion on the expressway, limiting the number of vehicles on a metered on-ramp that is allowed to enter the expressway stretch is a reasonable ramp metering strategy. It can be carried out by imposing a fraction of the dynamic reserve receiving capacity of the downstream expressway stretch as the ramp metering rate set at each ramp metering period, namely:

C a ?t? ? la ? Rci ?Dl?1 ?;

8t 2 ?Dl?1 ; Dl ?; l ? 1; 2; . . . ; M; a 2 A? on

?31?

where 0 6 la 6 1 is known as the reserve receiving capacity split ratio, and Rci ?Dl?1 ? is the reserve receiving capacity de?ned by Eq. (13) for merging cell (c, i) of expressway stretch c e AE at which the metered on-ramp a 2 A? meets the expressway on stretch. Eq. (31) indicates that the number of vehicles at on-ramp a 2 A? to enter the expressway during ramp metering period l on cannot exceed 100la% of the dynamic reserve receiving capacity of the downstream expressway stretch. 4.1.3. Period-dependent constant ramp metering rate scheme Taking a constant ramp metering rate over a ramp metering period for a metered on-ramp is an easy but practical way to implement the ramp metering operations. This period-dependent constant ramp metering rate solution can be expressed by

^ ga ?Dl ? 6 C a ?t? 6 ga ?Dl ?; 8t 2 ?Dl?1 ; Dl ?; l ? 1; 2; . . . ; M; a 2 A? on

?32?

^ where ga ?Dl ? and ga ?Dl ? are two predetermined lower and upper bounds of the constant ramp metering rate in the period ?Dl ; Dl?1 ?. 4.1.4. Uni?ed expressions In addition to the three ramp metering rate constraints above, there may be other constraints needed to be imposed in practice. For easy of exposition and without loss of generality, we can utilize the following generic constraints to express any restriction on the ramp metering rate:

g a ?C a ?t?; t? 6 0;

a 2 A? ; t ? 0; 1; . . . ; T ? 1 on

?33?

where ga(Ca(t), t) is a function of ramp metering rate and time t at on-ramp a 2 A? . on 4.2. Multiobjective optimization formulation The total system delay F0(C), shown by Eq. (2), is a function of a dynamic ramp metering rate solution C. Value of function F0(C) for any given dynamic ramp metering rate solution C can be evaluated by the MCTM according to the formula:

F 0 ?C? ?

la T?1 XXX t?0 a2A i?1

2 4na ?t? ?

i

X

hm 2C? ?ai ?

3 yai hm ?t?5 ?34?

where nai ?t? is the vehicle’s ?ow in cell (a, i) of arc a e A at time t in unit of veh/h and yai hm ?t? is the vehicle ?ow of the cellbased network, which connects cell (a, i) of arc a e A to cell (h, m) of arc h e A, from clock tick t to clock tick t + 1. Since a vehicle that does not proceed at each time interval will encounter one time interval extra travel delay, Eq. (34) sums up all the travel delay encountered by vehicles over the speci?ed time horizon.

Q. Meng, H.L. Khoo / Transportation Research Part C 18 (2010) 489–506

497

The average travel delay of vehicles incurred at an on-ramp over the time horizon, shown in Eq. (3), can be calculated by the MCTM according to the formula:

PT Pla h Da ?C? ?

t?1 i?1

nai ?t? ?

P

hm 2C? ?ai ? yai hm ?t?

i ; a 2 Ak ; k ? 1; 2; . . . ; K on ?35?

V a ?T?

where Va(T) is the number of vehicles at on-ramp a 2 A? [ A? over time horizon [0, T]. In reality, Eq. (35) determines the on on average travel delay of the vehicles at on-ramps by dividing the total travel delay of all vehicles with the total number of vehicles. According to the ramp metering equity index de?ned by Eq. (4), it is straightforward to de?ne a function for a particular group of on-ramps, k = 1, 2, . . . , K, as follows:

minfDa ?C?g F k ?C? ? 1 ? Ik ?C? ? 1 ?

a2Ak on a2Ak on

maxfDa ?C?g

;

k ? 1; 2; . . . ; K

?36?

Eq. (36) implies that maximizing the equity index for a speci?c group of on-ramps is equivalent to the minimization of the function above. According to Eq. (5), it follows that

0 6 F k ?C? 6 1;

k ? 1; 2; . . . ; K

?37?

However, ?nding a dynamic ramp metering rate solution that minimizes the total system delay expressed by Eq. (34) is not adequate to capture the equity of the system. This is clear that such an objective is biased to vehicles traveling on expressway rather than vehicles at on-ramps since traf?c demand on expressway is usually much higher than vehicles at on-ramps. Nevertheless, the objective may ensure the ef?ciency of the system after the implementation of ramp metering. To capture the equity issue for a group of on-ramps, k, we have to seek a dynamic ramp metering rate solution that maximizes the equity index Ik(C) or minimizes function Fk(C). This is because Ik(C) de?nes the degree of equity of the system. This objective may ensure that the ramps within the same group k may have some degree of even distribution of the average delay. Since the fair ramp metering problem aims to determine a ramp metering rate solution that takes into account both the ef?ciency (for the bene?t of overall system) and the equity (for the bene?t of drivers using on-ramps) issue, it can be thus formulated as the multiobjective minimization model:

3 F 0 ?C? 6 F 1 ?C? 7 7 6 7 min 6 . 7 C 6. 5 4. 2 F K ?C?

?38?

subject to

g a ?C a ?t?; t? 6 0; na1 ?0? ?

T?1 X t?0

8metered on-ramp a 2 A? ; t ? 0; 1; . . . ; T ? 1 on 8on-ramp a 2 A? [ A? on on

?39? ?40? ?41? ?42?

qa ?t?;

Q a2 ?t? ? qa ?t?;

8on-ramp a 2 A? [ A? ; t ? 0; . . . ; T ? 1 on on 8oridinary link ai ai?1 2 Xordinary ; t ? 0; 1; . . . ; T ? 1

? ? yai ai?1 ?t? ? min Sai ?t?; Rai?1 ?t? ; (

ybi cj ?t? ? bbi cj ?t? ? minfSbi ?t?; Rcj ?t?=bbi cj ?t?; Rdk ?t?=bbi dk ?t?g ybi dk ?t? ? bbi dk ?t? ? minfSbi ?t?; Rcj ?t?=bbi cj ?t?; Rdk ?t?=bbi dk ?t?; g ?43? t ? 0; 1; . . . ; T ? 1 yai hm ?t?; i ? 1; 2; . . . ; la ; a 2 A; t ? 0; 1; . . . ; T ? 1 ?44?

8paired diverging links?bi cj ; bi dk ? 2 Xdiv erge ;

nai ?t ? 1? ? nai ?t? ? X

hm 2C? ?ai ?

yhm ai ?t? ?

X

hm 2C? ?ai ?

8 > M 2 ? zci ?t? ? e 6 Sej ?t? ? Sgp ?t? ? Rci ?t? 6 M 1 ? ?1 ? zci ?t?? > > > zc ?t? ? 0 or 1 > i < hPse ?t? i j > yej ci ?t? ? ?1 ? zci ?t?? ? Sej ci ?t? ? zci ?t? ? s?1 yej ci s ?t; Uei g p cj ?t; Rcj ?t??? > > > > Psgp ?t? : ygp ci ?t? ? ?1 ? zci ?t?? ? Sgp ci ?t? ? zci ?t? ? s?1 ygp ci s ?t; Uei gp cj ?t; Rcj ?t???;

?45?

8paried merging links?ej ci ; g p ci ? 2 Xmerge ; t ? 0; 1; . . . ; T ? 1

498

Q. Meng, H.L. Khoo / Transportation Research Part C 18 (2010) 489–506

where M1 is a large constant; M2 is a large negative constant; and e is a very small positive constant. For the purpose of illustration, one could imagine these three constants as: M1 ? + 1; M2 ? ?1; e ! 10M2 . Constraint (39) is the generic expression for the dynamic ramp metering rate constraints. Constraints (40)–(45) are alternative concise representations of the MCTM. Constraints (40) indicate that the ?rst cell of an on-ramp at time t = 0 stores the total demand that intends to enter the expressway network like a big parking lot (Lo, 1999). Constraint (41) implies that the in?ow capacity of the second cell of the on-ramp is set to the exogenous dynamic demand. Vehicles will enter the network according to the dynamic demand if space is available in the second cell. These two constraints mimic dynamic traf?c demand generated at an on-ramp. The purpose of binary variable zi(t) involved in Eq. (45) is to express the dynamic traf?c ?ow on the pair of merge links in concise mathematical expressions rather than ‘‘if-then” logical conditions shown in Eqs. (18) and (25) (Lo, 1999). This is shown as:

zci ?t? ? 1 if and only if Sej ?t? ? Sgp ?t? 6 Rci ?t? zci ?t? ? 0 if and only if Sej ?t? ? Sgp ?t? > Rci ?t?

?46? ?47?

The multiobjective minimization model (38)–(45), in general, does not possess a universal optimal solution due to tradeoffs among the multiple objectives. In fact, the scalar concept of ‘‘optimality” cannot be directly applied for a multiobjective optimization model. Because of the seminal work of Edgeworth and Pareto in late 19th century, the Pareto-optimality has been utilized to characterize a solution of a multiobjective optimization model (Deb, 2001). A feasible dynamic ramp metering rate solution satisfying the Pareto-optimality condition for the multiobjective optimization model (38)–(45) is referred to as the Pareto-optimal dynamic ramp metering rate solution, which is illustrated hereafter. 4.3. Pareto-optimal dynamic ramp metering rate solutions Let C be the set of all feasible dynamic ramp metering rate solutions for the multiobjective minimization model (38)– (45), namely,

C ? fC ? ?C a ?t?; a 2 A? ; t ? 0; 1; . . . T ? 1?g a ?C a ?t?; t? 6 0; a 2 A? ; t ? 0; 1; . . . ; T ? 1g on on

?48?

Any two feasible dynamic ramp metering rate solutions are comparable in terms of the Pareto-dominance relation de?ned by the multiple objective functions shown in Eq. (38): De?nition 1 (Pareto-dominance). The feasible dynamic ramp metering rate solution C1 is said to dominate another feasible dynamic ramp metering solution C2 if and only if

F k ?C1 ? 6 F k ?C2 ?;

k ? 0; 1; 2 . . . ; K

?49?

and there is at least one k e {0, 1, 2, ..., K} such that

F k ?C1 ? < F k ?C2 ?

?50?

In view of multiple objective functions, the Pareto-dominance is a partial mathematical ordering relation between two ramp metering rate solutions. Based on the Pareto-dominance relation, the Pareto-optimality condition for the multiobjective minimization model (38)–(45) can be de?ned as follows (see, Steuer, 1986): De?nition 2 (Pareto-optimality). Let C e C be a feasible dynamic ramp metering rate solution: . (i) The feasible dynamic ramp metering solution C is said to be non-dominated regarding a subset C0 # C if and only if there is no solution in C0 which dominates C. (ii) The feasible dynamic ramp metering solution C is called a Pareto-optimal dynamic ramp metering rate solution if and only if C is non-dominated regarding the whole set C.

In general, the Pareto-optimal dynamic ramp metering rate solution is not unique and it cannot be improved with respect to any objective without worsening at least one other objective. Let C? denote a set of all Pareto-optimal dynamic ramp metering rate solutions, and the corresponding vectors of the objective function values, denoted by f?F 0 ?C?; F 1 ?C?; . . . ; F K ?C??jC 2 C? g, is called Pareto-front. 5. Solution algorithm The K + 1 objective functions in the multiobjective minimization model (38)–(45) do not possess the conventional analytical expressions, and calculation of these objective function values at any dynamic ramp metering rate solution necessitates the dynamic traf?c ?ow pattern formulated by MCTM or constraints (40)–(45). For any given ramp metering rate solution, however, MCTM can be solved numerically rather than analytically. These two features determine that an evolutionary algorithm based solution method is the best choice to ?nd the set of Pareto-optimal dynamic ramp metering rate solutions because it merely requires values of functions involved in the objective and constraints. Among a few categories

Q. Meng, H.L. Khoo / Transportation Research Part C 18 (2010) 489–506

499

of evolutionary algorithms, multiobjetive genetic algorithms (GAs) are the most popular solution methods for solving multiobjective optimization problems (Jones et al., 2002). The ?rst multiobjective GA was proposed by Schaffer (1985). Subsequently, more than 13 multiobjective GAs have been developed (Coello, 2000), including the niched Pareto genetic algorithm (NPGA) (Horn et al., 1994), the random weightbased genetic algorithm (RWGA) (Murata and Ishibuchi, 1995), the non-dominated sorting genetic algorithm (NSGA) (Srinivas and Deb, 1995) and the fast non-dominated sorting genetic algorithm (NSGA-II) (Deb et al., 2002). Generally, these multiobjective GAs differ based on their ?tness assignment procedures, elitism choice strategies and population diversity mechanisms. According to the recent comparison made by Konak et al. (2006), NSGA-II is an ef?cient and well-tested multiobjective GA. Therefore, NSGA-II is adopted for solving the multiobjective minimization model (38)–(45). NSGA-II operates with a collection of chromosomes, called a population. A chromosome corresponds to a unique solution of a problem of interest in the solution space by a chromosome decoding scheme. As for the multiobjective minimization model (38)–(45), a dynamic ramp metering rate solution C ? ?C a ?t?; a 2 A? ; t ? 0; 1; . . . ; T ? 1? can be easily encoded into on a binary string, of which a speci?ed portion represents a metering rate for a particular on-ramp at time t. More specially, the metering ratios, fqa ; a 2 A? g, or the reserve receiving capacity split ratios, fla ; a 2 A? g, for the period-dependent ramp on on metering rate schemes shown in Eqs. (29) and (31) can be encoded as the binary chromosomes. With such a chromosome encoding scheme, the corresponding dynamic ramp metering rate solution can be decoded by means of Eqs. (29) and (31). Given a dynamic ramp metering rate solution decoded from the binary chromosome, MCTM can be solved numerically. The K + 1 objective function values with respect to the dynamic ramp metering rate solution can be evaluated accordingly. The NSGA-II embedding with MCTM for solving the multiobjective optimization model (38)–(45) is described below in brief. For details, readers are encouraged to refer to the original studies (Srinivas and Deb, 1995; Deb et al., 2002).

5.1. NSGA-II embedding with MCTM Step 1: (Initialization) Randomly create a parent population P0 of size L in the dynamic ramp metering rate solution space. Set the number of generations x = 0. Step 2: (Generate an initial offspring population) Randomly select chromosome from population P0 to perform crossover and mutation to generate offspring population B0 of size L. Step 3: (Stopping criterion checking) If a stopping criterion is satis?ed, stop and return to Px. Otherwise, go to Step 4. Step 4: Set Hx = Px [ Bx. Step 5: (Invoke MCTM) Decode each chromosome in set Hx into a dynamic ramp metering rate solution and then run MCTM to evaluate the K + 1 objective function values corresponding the dynamic ramp metering rate solution, according to Eqs. (34)–(36). Step 6: (Allocate ?tness value) Apply the fast non-dominate sorting algorithm (Deb et al., 2002) to identify all the non dominated fronts in set Hx, denoted by H1 ; H2 ; . . . ; HMx where Mx is a positive integer, in terms of the K + 1 objective function values evaluated in Step 4. Step 7: (Maintain elitist chromosomes) (i) Let set Px+1 = / (ii) For fronts m = 1–Mx do the following steps: Step 7.1: (Crowding distance assignment) Calculate the crowding distance of each chromosome in the non-dominated front Hm , de?ned by Deb et al. (2002). Step 7.2: (Create parent population for next generation) Create Px+1 as follows: Case 1: If jP x?1 j ? jHm j 6 L, then set Px+1 = Px+1 [ fg Case 2: If |Px+1| + |Hm| > L, then add the least crowded L ? |Px+1| solutions from Hm to set Px+1. Step 8: (Crossover) Set Bx+1 = / and generate an offspring population Bx+1 of size L as follows: Step 8.1: (Parent selection with diversity mechanism). Use binary tournament selection method (Goldberg, 1989) based on the crowding distance to select parents from Px+1. Step 8.2: Use a crossover operator to generate offspring to add them to set Bx+1. Step 9: (Mutation) Mutate each chromosome in set Bx+1 with a prede?ned mutation rate. Let the number of generations x = x + 1 and go to Step 3.

6. Numerical example To numerically evaluate the proposed model and solution method, a stretch of Interstate 210 W expressway-ramp network system comprising 21 metered on-ramps and 18 off-ramps of Pasadena, California is adopted. Google Earth was utilized to estimate the length of each on-ramp and identify the number of lanes for the expressway’s mainline and the ramps. Fig. 1 schematically depicts the expressway network system with eight mainline sections. The time horizon of interest is assumed to be one hour and the time interval d = 10 s. Fig. 2 gives the cell-transmission network encoded for the expressway network system shown in Fig. 1. The size of a cell in the cell-transmission network is the distance a vehicle can travel with free-?ow speed in a time interval. The parameters used by the MCTM – free-?ow speed for expressway mainline segment (100 km/h), free-?ow speed for ramp (60 km/h), backward shock wave speed (28 km/h) and jam density (17 veh/km/lane) – are taken from Munoz et al. (2004) who have calibrated the cell-transmission

500

Q. Meng, H.L. Khoo / Transportation Research Part C 18 (2010) 489–506

Mainline segment 1

Mainline segment 2

Mainline segment 3

1

1

2

3

2

3

4

5

4

5

6

7

6

8

7

9

Mainline segment 4

Mainline segment 5

Mainline segment 6

8

10

11

9

12

13

10 14

15

16

11 17

12

18

19

13

Mainline segment 7

Mainline segment 8

Legend: : On-ramp no. i i : Off-ramp no.j

14 20

15 21

16

17

18

j

Fig. 1. The expressway network topological structure with eight mainline segments.

network. Because free-?ow speeds of the mainline and the ramps are different, the size of the expressway mainline cells (0.28 km) is not the same as the ramp’s cells (0.17 km). The average hourly traf?c demand on the mainline is assumed as 1500 veh/lane while the average travel demand at an on-ramp is between 480 veh/h and 1300 veh/h depending on the number of lanes the on-ramp has. The two-lane on-ramps have higher traf?c demand than one-lane on-ramps. Traf?c ?ow split ratio between the mainline and an off-ramp is arbitrarily assumed between 0.4 and 0.6. Capacity of the expressway mainline is set to 2200 veh/h/lane and ramp capacity is 2000 veh/h for one-lane ramp with free-?ow speed of 60 km/h and 2400 veh/h for two-lane ramp according to HCM (2000). Given an average hourly traf?c demand for an on-ramp, it is assumed that dynamic traf?c is generated from the ?rst cell of the on-ramp, shown in Eq. (40), by obeying the Poisson distribution, i.e. the time headway between two consecutive vehicles follows the negative exponential distribution. To investigate the impact of various parameters involved in formulating the multiobjective minimization model, a benchmark scenario is con?gured below. Note that the expressway mainline is divided into eight segments indicated in Fig. 1, and the eighth segment does not have any on-ramp while each of the other seven segments has three on-ramps respectively. Therefore, three vicinity on-ramps in each section are classi?ed in a group for the benchmark scenario. In other words, the benchmark scenario possesses seven equity indexes, namely K = 7. The benchmark scenario determines the period-dependent ramp metering rate scheme by adopting Eq. (29) as the ramp metering constraints, which is governed by the average queuing length. Length of each ramp metering period is 5 min, namely, the ramp metering rates are updated every ?ve minutes although the time interval in MCTM is set to be 10 s. Thus, there are totally 12 ramp metering periods over the one hour time horizon. According to Eq. (29), each ramp metering ratio, ? 0 6 qa 6 1; a 2 Aon , is encoded by a 7-bit binary chromosome. With a total of 21 on-ramps, the length of a chromosome is 147 genes in the NSGA-II embedded with the MCTM. The parameters used by the NSGA-II embedded with the MCTM are set as follows – the population size is 100, the maximum number of generations (i.e., stopping criterion) is 30, and the crossover probability and the mutation probability are 0.7 and 0.03, respectively. A Pareto-optimal dynamic ramp metering rate solution denoted by CP correspond to the total system travel delay F0(CP) and K equity index values, Ik(CP), k = 1, 2, ? ? ?, K. For the purpose of comparison among the Pareto-optimal solutions, the average equity index for a Pareto-optimal dynamic ramp metering rate solution is de?ned below.

P? ? I?C

PK

P k?1 I k ?C ?

K

?51?

Eq. (51) is an indicator to quantify the average performance of ramp metering equity index among groups. For a particular solution, some groups may have lower equity index value while some may have higher. Hence, a consistent performance indicator is necessary to judge the quality of the results. 6.1. Numerical results for the benchmark scenario There are a total of 24 Pareto-optimal dynamic ramp metering rate solutions obtained for the benchmark scenario by implementing the NSGA-II embedding with the MCTM. The total system delay and the seven equity indexes for these solutions are present in Table 1.

Q. Meng, H.L. Khoo / Transportation Research Part C 18 (2010) 489–506

(42,1)

501

(41,1)

(42,2)

(43,1)

(45,3)

(41,2)

(42,3)

(43,2)

(42,3)

(45,2)

(41,3)

(42,2)

(43,3)

(44,4)

(45,1)

(41,4)

(42,1)

(43,4)

(1,1)

(1,2)

(2,1)

(48,1)

(2,2)

(2,3)

(2,4)

(3,1)

(3,1)

(4,1)

(44,5)

(4,2)

(5,1)

(5,2)

(5,3)

(46,1)

(7,1)

(46,2)

(46,3)

(5,4)

(6,1)

(7,2)

(7,3)

(48,2)

(47,1)

(48,3)

(49,3)

(50,3)

(51,1)

(52,2)

(52,1)

(47,2)

(48,4)

(49,2)

(47,3)

(50,2)

(51,3)

(51,2)

(52,3)

(53,2)

(53,3)

(48,5)

(49,1)

(47,4)

(48,6)

(50,1)

(51,4)

(52,4)

(8,1)

(9,1)

(9,2)

(10,1)

(10,2 )

(11,1)

(11,2 )

(12,1 )

(12,2 )

(13,1)

(54,4)

(53,1)

(54,3)

(54,2)

(54,1)

(13,2 )

(14,1)

(14,2 )

(14,3 )

(15,1 )

(15,2 )

(15,3)

1)

,1 )

, 1)

(56,1)

(5 6 , 2)

(5 9

(5 8,

(6 1

(55,3)

(57,3)

(6 2,

1)

(59,2)

(60,3)

(61,2)

(56,3)

(55,2)

(57,2)

(58,2)

(62,2)

(56,4)

(58,3)

(59,3)

(60,2)

(61,3)

(55,1)

(57,1)

(62,3)

(56,5)

(58,4)

(59,4)

(61,4)

(15,4)

(16,1)

(16,2)

(17,1)

(17,2)

(17,3)

(18,1)

(18,2)

(19,1)

(20,1)

(20,2)

(20,3)

(21,1)

(62,4)

(60,1)

(21,2)

(22,1)

(23,1)

(23,2)

(70,1)

(69,3)

(71,2)

(71,1)

(64,1)

(65,1)

(66,1)

(67,3)

(68,1)

(69,2)

(70,2)

(71,3)

(64,2)

(65,2)

(66,2)

(67,2)

(68,2)

(70,3)

(71,4)

(64,3)

(65,3)

(66,3)

(67,1)

(68,3)

(69,1)

(24,1)

(25,1)

(26,1)

(27,1)

(28,1)

(28,2)

(29,1)

(29,2)

(30,1)

(70,4)

(72,1)

(72,2)

(72,3)

(30,2)

(30,3)

(31,1)

(31,2)

(32,1)

(33,1)

(33,2)

(74,1)

(73,3)

(76,1)

(77,3)

(78,3)

(74,2)

(75,3)

(76,2)

(77,2)

(78,2)

(75,2)

(76,3)

(73,2)

(74,3)

(77,1)

(78,1)

(73,1)

(74,4)

(75,1)

(76,4)

(79,1)

(79,2)

(79,3)

Legend Big parking lot Cell

(33,3 )

(34,1)

(34,2)

(34,3)

(35,1)

(35,2)

(36,1)

(36,2)

(36,3)

(37,1)

(38,1)

( 39,1)

(40,1)

(40,2)

Sinking Cell

Fig. 2. The cell-transmission network.

The average total system travel delay for the best three solutions in terms of the system ef?ciency (in bold font) is 6.3 veh h, while the average equity index is 0.55. On the other hand, the best three solutions in terms of the system equity

(63,1)

(63,2)

(63,3)

502

Q. Meng, H.L. Khoo / Transportation Research Part C 18 (2010) 489–506

Table 1 Total system travel delay F0(CP) and equity index Ik(CP) of 16 Pareto-optimal dynamic ramp metering rate solutions for the benchmark scenario. CP No. F0(CP) (veh h) Equity index Ik(CP) k=1 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 6.16 6.36 6.38 6.43 6.76 6.77 6.78 6.88 7.00 7.14 7.21 7.22 7.33 7.36 7.44 7.53 7.84 7.85 7.88 7.89 7.95 8.05 8.06 8.08 8.10 0.846 0.504 0.51 0.495 0.89 0.356 0.383 0.506 0.442 0.505 0.548 0.497 0.463 0.407 0.486 0.503 0.467 0.498 0.509 0.491 0.789 0.42 0.433 0.912 0.441 k=2 0.548 0.543 0.295 0.639 0.374 0.541 0.849 0.847 0.266 0.462 0.463 0.556 0.545 0.536 0.527 0.67 0.39 0.282 0.468 0.309 0.286 0.555 0.85 0.459 0.532 k=3 0.497 0.292 0.476 0.722 0.49 0.381 0.437 0.752 0.8 0.196 0.517 0.36 0.376 0.78 0.795 0.2 0.909 0.387 0.463 0.372 0.794 0.78 0.299 0.297 0.373 k=4 0.391 0.875 0.897 0.427 0.762 0.465 0.391 0.475 0.793 0.399 0.442 0.383 0.301 0.796 0.918 0.393 0.485 0.399 0.758 0.482 0.387 0.901 0.9 0.884 0.754 k=5 0.426 0.392 0.283 0.341 0.462 0.772 0.681 0.42 0.453 0.376 0.561 0.302 0.568 0.391 0.33 0.397 0.565 0.401 0.388 0.421 0.511 0.449 0.402 0.42 0.463 k=6 0.276 0.279 0.217 0.278 0.404 0.343 0.401 0.396 0.398 0.338 0.277 0.244 0.237 0.275 0.251 0.252 0.372 0.399 0.401 0.4 0.367 0.395 0.396 0.397 0.404 k=7 0.981 0.972 0.962 0.969 0.975 0.978 0.984 0.946 0.965 0.937 0.612 0.614 0.581 0.587 0.503 0.508 0.615 0.618 0.626 0.58 0.591 0.507 0.507 0.512 0.516 0.566 0.551 0.52 0.553 0.622 0.548 0.59 0.62 0.588 0.459 0.488 0.422 0.438 0.539 0.544 0.418 0.544 0.426 0.516 0.436 0.532 0.572 0.541 0.554 0.497 Average equity index, P ? I?C

(in Italic bold font) yield an average equity index of 0.61, and the average total system travel delay is 6.8 veh h. Based on this ?nding, it clearly provides insight on the trade-off relationship of the equity and ef?ciency issues. In such a case, an 8% reduction in total system bene?t is a price pay for an improvement of 10.9% in equity. This trade-off relationship is in some extent similar to those found by Levinson and Zhang (2004). Given the large set of the Pareto-optimal dynamic ramp metering rate solution, this offers great ?exibility for system managers to decide the trade-off that they could accept. They could do so assuming that there is some established guidelines or criteria that they could follow. Using the proposed methodology, system engineers could actually observe and quantify the price they traded off in order to have a more equitable ramp metering system. Table 2 shows the best period-dependent dynamic ramp metering rate pattern in terms of the average equity index, which can guide traf?c control operators to set an appropriate metering rate solution. 6.2. Impact of the equity issue To further demonstrate the impact of the equity issue, two other scenarios are established. One of them is the system optimal solution, in which the optimal ramp metering rate is obtained by minimizing the total system travel delay alone, while the other one is the no-metering scenario. Table 3 shows the total system travel delay and equity index value for these cases. It is observed that the system optimal solution yields a total delay which is 14.7% less than the no-metering case, while the Pareto-solution has a 6.1% reduction in total delay. This shows that the system optimal solution gives the highest ef?ciency. Although the Pareto-solution ranks the second place, it is still more ef?cient than the no-metering case. In terms of equity, the Pareto-solution has an equity value that is very close to the no-metering case. It is only 7% less equity compared to the no-metering case. If we assume that the nometering case represents the perceived perfect equity (most acceptable by drivers), the Pareto-solution is very close to it, compared to the system optimal solutions. This means that the Pareto-solutions obtained from the proposed methodology is more equitable and with an acceptable system ef?ciency level. It is interesting to note that, the system optimal solution shown in Table 3 which is obtained by running a separate program is similar to the solution found using the proposed methodology as shown in Table 1 (solution No. 1). This shows that the results obtained using the proposed methodology for the system optimal is as good as the results obtained concerning the system ef?ciency alone. 6.3. On-ramp grouping effect A close study on the proposed multiobjective minimization model reveals the fact that Pareto-optimal dynamic ramp metering solutions are dependent on the on-ramp grouping strategy. Intuitively, one can expect that a smaller number of group members in a group will give a better equity index performance. This is because, with lesser members in a group, it reduces the travel delay variability among the group members. Table 4 con?rms this argument.

Q. Meng, H.L. Khoo / Transportation Research Part C 18 (2010) 489–506 Table 2 The Pareto-optimal dynamic metering rate solution with the best average equity index. Ramp metering index Ramp metering period 1 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 6 7 7 7 7 6 7 6 6 7 6 7 7 6 6 6 7 7 7 7 7 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 3 5 10 9 5 8 6 8 4 1 4 6 3 1 1 1 10 13 1 2 4 3 4 1 1 1 1 2 1 2 1 1 1 1 1 2 1 9 1 2 12 2 4 3 5 5 6 9 11 1 6 1 1 1 4 1 3 1 2 1 1 2 4 14 6 3 6 1 1 1 1 5 1 5 1 1 1 1 1 4 7 3 9 13 18 29 6 3 7 5 10 8 15 1 6 1 3 12 3 3 3 19 9 8 10 13 24 29 6 3 8 1 1 1 1 9 1 9 1 12 4 6 3 19 9 16 10 13 24 29 6 3 9 5 6 11 6 6 6 6 4 12 4 6 3 19 9 28 10 13 24 29 6 3 10 1 1 1 1 16 6 16 4 12 4 6 3 19 9 29 10 13 24 29 6 3 11 5 10 9 9 16 6 16 4 12 4 6 3 19 9 29 10 13 24 29 6 3

503

12 1 1 1 15 16 6 16 4 12 4 6 3 19 9 29 10 13 24 29 6 3

Table 3 System ef?ciency and equity for no-metering case, system optimal only case, and Pareto-solution case. Type No metering System optimal Pareto-solutions Total travel delay (veh h) 7.20 6.14 6.76 Equity index, Ik(CP) 0.67 0.56 0.62

It shows value for the best three dynamic ramp metering rate solutions in terms of ef?ciency and equity respectively for different number of members in a group. By multiplying the value of average equity index column in Table 4 into percentages, one can obtain the degree of equity. It can be seen that for the group of three nearby on-ramps, it can achieve an average of 61.1% equity. For a grouping of 4 and 5 members, 7 members, and 10 members, show an average of 62.9%, 54.5%, 53.8% and 40.56% of equity respectively, by taking the average value of the three best solutions in terms of equity for each group of solutions. It can be observed clearly that the percentage of equity deteriorates with the increment of the number of members in a group. This is logical, since there are many factors affecting the equity characteristics of ramp metering. Fewer members in a group may reduce the variability and thus higher equity may be achieved. In addition, we should not expect those ramps that are apart far away to have same characteristic and should behave equally. As mentioned beforehand, the results present herein are obtained by grouping the on-ramps considering their geographical factor. Besides geographical factor, traf?c control operators can also consider arrival rate pattern and on-ramp demand as the factors to group the on-ramps. For example, they can group the on-ramps with similar arrival rate in a group. Hence, it is dependent on their judgment and experience to decide how to de?ne the on-ramp groups. The proposed methodology does not restrict the choice of the on-ramp grouping method as well as to allow the group members to be superimposed. 6.4. Temporal equity issue According to Eq. (9), three different values of time interval D are tried, i.e. 10 min, 20 min and 30 min respectively. Table 5 shows these results. It shows the impact of different values of D on the total delay and average equity index values. It is observed that the temporal equity index value is quite low compared to the benchmark case. Nevertheless, the results show that the proposed methodology could take into consideration the temporal equity issue, besides the spatial equity. 6.5. Remarks It can be seen that a perfect equity cannot be achieved using the proposed methodology. This is reasonable because there are many factors affecting the performance of an on-ramp such as the geometrical layout (i.e. the number of lanes), the arrival rate, and the location of the ramp from the prevailing bottleneck location, the number of vicinity ramps and their

504

Q. Meng, H.L. Khoo / Transportation Research Part C 18 (2010) 489–506

Table 4 Total system travel delay F0(CP) and equity index Ik(CP) for the Pareto-optimal dynamic ramp metering rate solutions with different on-ramp grouping strategies. On-ramp grouping strategy F0(CP) (veh h) Equity index, Ik(CP) k=1 Three on-ramps (K = 7) 1a 2a 3a 1b 2b 3b Four on-ramps (K = 5) 1a 2a 3a 1b 2b 3b Five on-ramps (K = 4) 1a 2a 3a 1b 2b 3b Seven on-ramps (K = 3) 1a 2a 3a 1b 2b 3b Ten on-ramps (K = 2) 1a 2a 3a 1b 2b 3b

a b

Average equity index, P ? I?C k=3 0.497 0.292 0.476 0.49 0.437 0.752 0.345 0.411 0.405 0.844 0.808 0.831 0.483 0.339 0.262 0.596 0.447 0.504 0.277 0.279 0.076 0.346 0.345 0.351 k=4 0.391 0.875 0.897 0.762 0.391 0.475 0.476 0.391 0.39 0.638 0.56 0.638 0.274 0.244 0.217 0.303 0.378 0.386 k=5 0.426 0.392 0.283 0.462 0.681 0.42 0.636 0.605 0.679 0.912 0.85 0.91 k=6 0.276 0.279 0.217 0.404 0.401 0.396 k=7 0.981 0.972 0.962 0.975 0.984 0.946 0.566 0.551 0.520 0.622 0.590 0.620 0.467 0.458 0.458 0.645 0.628 0.616 0.494 0.462 0.462 0.604 0.515 0.515 0.360 0.336 0.306 0.549 0.541 0.524 0.316 0.291 0.276 0.411 0.407 0.399

k=2 0.548 0.543 0.295 0.374 0.849 0.847 0.459 0.371 0.348 0.386 0.467 0.236 0.722 0.786 0.827 0.767 0.734 0.787 0.325 0.341 0.339 0.797 0.810 0.742 0.198 0.122 0.191 0.38 0.381 0.374

6.16 6.36 6.38 6.76 6.78 6.88 5.62 5.67 5.77 6.74 7.02 6.74 6.16 6.18 6.19 6.76 7.00 6.76 5.13 5.62 5.58 6.78 6.76 6.22 5.94 5.58 5.98 6.33 6.73 6.55

0.846 0.504 0.51 0.890 0.383 0.506 0.420 0.492 0.468 0.443 0.457 0.466 0.497 0.481 0.541 0.751 0.502 0.384 0.478 0.390 0.503 0.502 0.467 0.480 0.434 0.461 0.362 0.444 0.431 0.423

Best dynamic ramp metering rate solution in terms of the total system delay. Best dynamic ramp metering rate solution in terms of the average equity index.

Table 5 Total system travel delay F0(CP) and equity index Ik(CP) of Pareto-optimal time dependent dynamic ramp metering rate solutions for different time interval, D. On-ramp grouping strategy F0(CP, D) (veh h) Temporal equity index, Ik(CP, D) k=1 k=2 0.41 0.49 0.45 0.38 0.34 0.34 0.36 0.33 0.35 0.40 0.51 0.62 0.56 0.60 0.50 k=3 0.42 0.37 0.44 0.35 0.34 0.31 0.30 0.36 0.29 0.23 0.15 0.23 0.32 0.13 0.38 k=4 0.34 0.41 0.43 0.45 0.38 0.52 0.57 0.42 0.36 0.60 0.33 0.43 0.20 0.48 0.49 k=5 0.3 0.33 0.31 0.21 0.34 0.40 0.46 0.44 0.34 0.41 0.40 0.22 0.41 0.28 0.23 k=6 0.23 0.24 0.25 0.26 0.31 0.27 0.17 0.14 0.18 0.22 0.21 0.09 0.11 0.20 0.13 k=7 0.16 0.29 0.24 0.25 0.32 0.33 0.17 0.32 0.21 0.19 0.50 0.30 0.31 0.49 0.29 0.38 0.42 0.34 0.39 0.39 0.37 0.36 0.41 0.38 0.37 0.38 0.36 0.33 0.40 0.35 Average equity index, P ; D? I?C

D = 10 min 1 2 3 4 5 D = 20 min 1 2 3 4 5 D = 30 min 1 2 3 4 5

7.09 7.26 8.25 8.45 8.94 7.59 8.31 7.27 9.34 8.83 7.71 8.03 8.75 8.82 9.03

0.77 0.81 0.28 0.80 0.67 0.40 0.48 0.84 0.92 0.56 0.54 0.60 0.42 0.61 0.43

Q. Meng, H.L. Khoo / Transportation Research Part C 18 (2010) 489–506

505

distance. Based on the Pareto-optimality conditions, the proposed methodology gives the best dynamic ramp metering rate solutions taking into account the system ef?ciency and the equity issue. In addition, the proposed methodology also cannot guarantee perfect equity across the groups. The benchmark scenario requires about 2 h of computational time to ?nd the set of Pareto-optimal dynamic ramp metering solutions on a desktop computer with Intel Pentium IV 3.2 GHz and Ram memory of 3 GB. In view of the computational time, the proposed methodology is more appropriate to be used during off-line decision-making stage. 7. Conclusions This paper has systematically dealt with the fair ramp metering problem. Firstly, a novel ramp metering equity index is proposed. By maximizing the equity index, a more equitable dynamic ramp metering rate solution can be obtained. Secondly, a multiobjective minimization model is formulated to simultaneously address the system ef?ciency and equity issue. The model offers great ?exibility for land transport authorities makers to decide the trade-off between these objectives. Thirdly, this paper has modi?ed the CTM to incorporate the ramp metering strategy and have derived a group of formulae to calculate dynamic traf?c ?ow on a pair of merging links. The hybrid NSGA with the MCTM is then applied for solving the multiobjective minimization model. Finally, the proposed model and solution method are tested and evaluated using a real network with hypothetical traf?c demand. Various interesting scenarios are developed and tested. It is also shown that the proposed equity index and methodology can be easily extended to capture the temporal equity issue. In future work, a dynamic traf?c assignment model that can describe behavior of drivers in route choice will be used to further examine the equity issue associated with the length of trip rather than the ramp location. Acknowledgement The authors wish to thank four anonymous referees and the editor for their helpful comments and suggestions for improvement of the paper. We also would like to express our sincere thanks to Dr. Raymond Ong Ghim Ping from Department of Civil Engineering at Purdue University for his kindness in proof-reading the paper. This research has been supported by Singapore Ministry of Education through Research Grant of National University of Singapore (R-264-000-200-112). References

Alkadri, M., 1998. Ramp metering: a systems approach pilot survey of acceptability by freeway users. ITE Journal on the Web, 75–80. Beegala, A., Hourdakis, J., Michalopoulus, P.G., 2005. A methodology for performance optimization of ramp control strategies through micro-simulation. In: 84th Transportation Research Board Annual Meeting, Washington, DC (CD-ROM). Bellemans, T., De Schutter, B., De Moor, B., 2003. Anticipative model predictive control for ramp metering in freeway networks. In: Proceedings of the American Control Conference, pp. 4077–4082. Benmohamed, L., Meerkov, S.M., 1994. Feedback control of highway congestion by a fair on-ramp metering. In: Proceedings of the 33rd Conference on Decision and Control, Lake Buena Vista, pp. 2437–2442. Cambridge Systematics Inc., 2000. Twin Cities Ramp Metering Effectiveness Study: ‘‘Before” and ‘‘After” Qualitative Research with Travelers. Technical Report. <http://www.dot.state.mn.us/rampmeterstudy/reports.html> (assessed 10.05.07). Chu, L., Liu, H.X., Recker, W., Zhang, H.M., 2004. Performance evaluation of adaptive ramp-metering algorithms using microscopic traf?c simulation model. Journal of Transportation Engineering ASCE 130 (3), 330–338. Coello, C.A.C., 2000. An updated survey of GA-based multiobjective optimization techniques. ACM Computing Surveys 32 (2), 109–143. Daganzo, C.F., 1995. The cell transmission model. Part II: network traf?c. Transportation Research Part B 29 (2), 79–93. Daganzo, C.F., 1994. The cell transmission model: a dynamic representation of highway traf?c consistent with the hydrodynamic theory. Transportation Research Part B 28 (4), 269–287. Deb, K., 2001. Multiobjective Optimization Using Evolutionary Algorithms. John Wiley& Sons, New York. Deb, K., Pratap, A., Agarwal, S., Meyarivan, T., 2002. A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Transactions on evolutionary computation 6 (2), 182–197. Erera, A., Daganzo, C., Lovell, D., 1999. The Access Control Problem on Capacitated FIFO Networks with Unique OD Path is Hard. California PATH Program, Institute of Transportation Studies, UCB-ITS-PRR-99-35. Goldberg, D., 1989. Genetic algorithms in search, optimization and machine learning. Addison-Wesley. Gomes, G., Horowitz, R., 2006. Optimal freeway ramp metering using the asymmetric cell transmission model. Transportation Research Part C 14, 244–262. Hasan, M., Jha, M., Ben-Akiva, M., 2002. Evaluation of ramp control algorithms using microscopic traf?c simulation. Transportation Research Part C 10, 229– 256. Hegyi, A., De Schutter, B., Hellendoorn, H., Van Den Boom, T., 2002. Optimal coordination of ramp metering and variable speed control – an MPC approach. In: Proceedings of the American Control Conference, pp. 3600–3605. Hellinga, B., Van-Aerde, M., 1995. Examining the potential of using ramp metering as a component of an ATMS. Transportation Research Record 1494, 169– 172. Highway Capacity Manual, 2000. Transportation Research Board, National Research Council, Washington, DC. Horn, J., Nafpliotis, N., Goldberg, D.E., 1994. A niched Pareto generic algorithm for multiobjective optimization. In: Proceedings of the ?rst IEEE conference on evolutionary computation, IEEE world congress on computational intelligence, pp. 82–87. Iida, Y., Hasegawa, T., Asakura, Y., Shao, C., 1989. A formulation of on-ramp traf?c control system with route guidance for urban expressway. In: Proceedings of the IFAC/IFIP/IFORS Symposium, Paris, September 19–21, pp. 229–236. Jacobson, L., Henry, K., Mehyar, O., 1989. Real time metering algorithm for centralized control. Transportation Research Record 1232, 17–26. Jones, D.F., Mirrazavi, S.K., Tamiz, M., 2002. Multiobjective meta-heuristics: an overview of the current state-of-the art. European Journal of Operational Research 137 (1), 1–9. Konak, A., Coit, D.W., Smith, A.E., 2006. Multi-objective optimization using genetic algorithms: a tutorial. Reliability Engineering and System Safety 91, 992– 1007. Kotsialos, A., Papageorgiou, M., 2004. Nonlinear optimal control applied to coordinated ramp metering. IEEE Transactions on control systems technology 12 (6), 920–933.

506

Q. Meng, H.L. Khoo / Transportation Research Part C 18 (2010) 489–506

Kotsialos, A., Papageorgiou, M., Mangeas, M., Hadj-Salem, H., 2002. Coordinated and integrated control of motorway networks via nonlinear optimal control. Transportation Research Part C 10 (1), 65–84. Lau, R., 1997. Ramp Metering by Zone-the Minnesota Algorithm. Minnesota Dept. of Transportation, USA. Levinson, D., Zhang, L., 2004. Evaluating the effectiveness of ramp meters. In: Gillen, D., Levinson, D. (Eds.), Assessing the Bene?ts and Costs of ITS. Kluwer Academic, Dordrecht, The Netherlands. Levinson, D., Zhang, L., 2006. Ramp meters on trial: evidence from the Twin Cities metering holiday. Transportation Research Part A 40, 810–828. Levinson, D., Harder, K., Bloom?eld, J., Carlson, K., 2006. Waiting tolerance. Ramp delay vs freeway congestion. Transportation Research Part F 9, 1–13. Lighthill, M.J., Whitham, J.B., 1955. On kinematic waves. I: ?ow movement in long rivers; II: four traf?c ?ow on long crowded roads. Proceedings of Royal Society, A 229, 281–345. Lipp, L.E., Corcoran, L.J., Hickman, G.A., 1991. Bene?ts of central computer control for Denver ramp metering system. Transportation Research Record 1320, 3–6. Lo, H., 1999. A dynamic traf?c assignment formulation that encapsulates the cell transmission model. In: Ceder, A. (Ed.), Transportation and Traf?c Theory: Proceedings of the 14th International Symposium on Transportation and Traf?c Theory. Pergamon, New York, pp. 327–395. Mun, J.-S., 2007. Traf?c Performance models for dynamic traf?c assignment: an assessment of existing models. Transportation Review 27 (2), 231–249. Munoz, L., Sun, X., Sun, D., Gomes, G., Horowitz, R., 2004. Methodological calibration of the cell transmission model. In: Proceeding of the 2004 American Control Conference, Boston, Massachusetts, June 30–July 2, 2004, pp. 798–803. Murata, T., Ishibuchi, H., 1995. MOGA: multi-objective generic algorithms. In: Proceedings of the 1995 IEEE International Conference On Evolutionary Computation, pp. 289–294. Paesani, G., Kerr, J., Perovich, P., Khosravi, F.E., 1997. System wide adaptive ramp metering (SWARM). In: CD-ROM. ITS America 7th Annual Meeting, California. Papageorgiou, M., Kotsialos, A., 2002. Freeway ramp metering: an overview. IEEE Transactions on Intelligent Transportation Systems 3 (4), 271–281. Papageorgiou, M., Habib, H.S., Blosseville, J.M., 1991. ALINEA: a local feedback control law for on-ramp metering. Transportation Research Record 1320, 58– 64. Papageorgiou, M., Kotsialos, A., 2001. Ef?ciency versus fairness in network-wide ramp metering. In: Proceedings of the IEEE Intelligent Transportation Systems Conference, August 25–29, Oakland (CA) USA, pp. 1189–1194. Papageorgiou, M., Blosseville, J.M., Habib, H.S., 1990. Modeling and real-time control of traf?c ?ow on the southern part of boulevard peripherique in Paris: part II: coordinated on-ramp metering. Transportation Research Part A 24, 361–370. Papageorgiou, M., Salem, H., Middelham, F., 1997. ALINEA local ramp metering: summary of ?eld results. Transportation Research Record 1603, 90–98. Pinnel, C., Drew, D., McCasland, W., Wattleworth, J., 1967. Evaluation of entrance ramp control on a six-mile freeway section. Highway Research Record 157, 22–76. Richards, P.I., 1956. Shockwaves on the highway. Operations Research 4, 42–51. Schaffer, J.D., 1985 Multiple objective optimization with vector evaluated generic algorithm. In: Proceedings of the 1st International Conference on Genetic Algorithms and their Applications, pp. 93–100. Srinivas, N., Deb, K., 1995. Multiobjective function optimization using nondominated sorting genetic algorithms. Evolutionary Computing 2 (3), 221–248. Stephanedes, Y.J., Chang, K.K., 1993. Optimal control of freeway corridors. Journal of Transportation Engineering 119 (4), 504–514. Steuer, R.E., 1986. Multiple criteria optimization: theory, computation, and application. John Wiley, New York. Wattleworth, J.A., Berry, D.S., 1965. Peak-period control of a freeway system-some theoretical investigations. Highway Research Record 89 (1), 1–25. Yang, H., Yagar, S., 1994. Traf?c assignment and traf?c control in general freeway areterial corridor systems. Transportation Research Part B 28 (6), 463–486. Yin, Y., Liu, H., Benouar, H., 2004. A note on equity of ramp metering. In: Proceedings of IEEE Intelligent Transportation Systems Conference, Washington DC, October 3–6, 2004, pp. 497–502. Zhang, H.M., Recker, W.W., 1999. On optimal freeway ramp control policies for congested traf?c corridors. Transportation Research Part B 33, 417–436. Zhang, H.M., Ritchie, S.G., Recker, W.W., 1996. Some general results on the optimal ramp control problem. Transportation Research Part C 4 (2), 51–69. Zhang, H.M., Ritchie, S.G., Jayakrishnan, R., 2001. Coordinated traf?c-responsive ramp control via nonlinear state feedback. Transportation Research Part C 9, 337–352. Zhang, L., Levinson, D., 2004. Optimal freeway ramp control without origin–destination information. Transportation Research Part B 38, 869–887. Zhang, L., Levinson, D., 2005. Balancing ef?ciency and equity of ramp meters. Journal of Transportation Engineering 131 (6), 477–481.

您现在的位置：首页 > >

# A Pareto-optimization approach for a fair ramp metering

发布时间:★相关文章：

- PDE A Pareto frontier differential evolution approach for multiobjective optimization probl
- A theoretical approach for Pareto-Zipf law
- Self-organizing maps for pareto optimization of airfoils
- SPEA2 IMPROVING THE STRENGTH PARETO EVOLUTIONARY ALGORITHM FOR MULTIOBJECTIVE OPTIMIZATION
- A Niched Pareto Genetic Algorithm for Multiobjective Optimization
- A multisine approach for trajectory optimization based on information gain
- [2008]A novel particle swarm optimization approach for product design and manufacturing
- A Particle Swarm Optimization-based Approach for Hyperspectral Band Selection
- A Centralized Simulated Annealing Approach for Self-optimization of Coverage and Capacity in LTE
- Use of a Self-Adaptive Penalty Approach for Engineering Optimization Problems
- PDE A Pareto frontier differential evolution approach for multiobjective optimization probl
- A theoretical approach for Pareto-Zipf law
- Self-organizing maps for pareto optimization of airfoils
- SPEA2 IMPROVING THE STRENGTH PARETO EVOLUTIONARY ALGORITHM FOR MULTIOBJECTIVE OPTIMIZATION
- A Niched Pareto Genetic Algorithm for Multiobjective Optimization
- A multisine approach for trajectory optimization based on information gain
- [2008]A novel particle swarm optimization approach for product design and manufacturing
- A Particle Swarm Optimization-based Approach for Hyperspectral Band Selection
- A Centralized Simulated Annealing Approach for Self-optimization of Coverage and Capacity in LTE
- Use of a Self-Adaptive Penalty Approach for Engineering Optimization Problems