当前位置:首页 >> 交通运输 >>

Behavior of the cell transmission model and effectiveness of ramp metering


Available online at www.sciencedirect.com

Transportation Research Part C 16 (2008) 485–513 www.elsevier.com/locate/trc

Behavior of the cell transmission model and e?ectiveness of ramp metering
Gabriel Gomes a, Roberto Horowitz a, Alex A. Kurzhanskiy a, Pravin Varaiya a,*, Jaimyoung Kwon b
b a University of California, Berkeley, CA 94720-1770, United States California State University, East Bay, Hayward, CA 94542, United States

Received 5 June 2007; received in revised form 23 October 2007; accepted 29 October 2007

Abstract The paper characterizes the behavior of the cell transmission model of a freeway, divided into N sections or cells, each with one on-ramp and one o?-ramp. The state of the dynamical system is the N-dimensional vector n of vehicle densities in the N sections. A feasible stationary demand pattern induces a unique equilibrium ?ow in each section. However, there is an in?nite set—in fact a continuum—of equilibrium states, including a unique uncongested equilibrium nu in which free ?ow speed prevails in all sections, and a unique most congested equilibrium ncon. In every other equilibrium ne one or more sections are congested, and nu 6 ne 6 ncon. Every equilibrium is stable and every trajectory converges to some equilibrium state. Two implications for ramp metering are explored. First, if the demand exceeds capacity and the ramps are not metered, every trajectory converges to the most congested equilibrium. Moreover, there is a ramp metering strategy that increases discharge ?ows and reduces total travel time compared with the no-metering strategy. Second, even when the demand is feasible but the freeway is initially congested, there is a ramp metering strategy that moves the system to the uncongested equilibrium and reduces total travel time. The two conclusions show that congestion invariably indicates wastefulness of freeway resources that ramp metering can eliminate. ? 2007 Elsevier Ltd. All rights reserved.
Keywords: Cell transmission model; Stability; Macrosimulation; Ramp metering; Fundamental diagram; Congestion; Strictly monotone map; Convergent system

1. Introduction The paper presents a complete analysis of the qualitative properties of the cell transmission model (CTM). CTM is a ?rst-order discrete Godunov approximation (Godunov, 1959), proposed by Daganzo (1994) and Lebacque (1996), to the kinematic wave partial di?erential equation of Lighthill and Whitham (1955) and Richards (1956). The popularity of CTM is due to its very low computation requirements compared with
*

Corresponding author. E-mail addresses: gomes@path.berkeley.edu (G. Gomes), horowitz@me.berkeley.edu (R. Horowitz), akurzhan@eecs.berkeley.edu (A.A. Kurzhanskiy), varaiya@eecs.berkeley.edu (P. Varaiya), jaimyoung.kwon@csueastbay.edu (J. Kwon). 0968-090X/$ - see front matter ? 2007 Elsevier Ltd. All rights reserved. doi:10.1016/j.trc.2007.10.005

486

G. Gomes et al. / Transportation Research Part C 16 (2008) 485–513

micro-simulation models; the ease with which it can be calibrated using routinely available point detector data (Lin and Ahanotu, 1995; Munoz et al., 2004); its extensibility to networks (Buisson et al., 1996a) and urban roads with signalized intersections (Lo, 2001; Almasri and Friedrich, 2005); and the ?exibility with which it can be used to pose questions of tra?c assignment (Buisson et al., 1996b; Ziliaskopoulos, 2000) and ramp metering (Daganzo and Lin, 1993; Zhang et al., 1996; Gomes and Horowitz, 2006). These topics are also studied using di?erent discrete models (May, 1981; Papageorgiou et al., 1990; Payne, 1979). CTM is a widely used discrete macroscopic model today. The objective of this paper, however, is not to relate CTM to the kinematic wave equation nor to investigate its utility for simulation, but rather to study it as a class of nonlinear dynamical systems. From this viewpoint, the interest is to determine the structure of its equilibrium points, their stability, and the qualitative properties of the convergence of its trajectories. Surprisingly, these aspects of the cell transmission model have received no attention in the published literature. The paper ?lls this gap. Section 3 presents the model, taken from Gomes (2004) and Gomes and Horowitz (2006), which in turn is based on Daganzo (1994). The freeway is divided into N sections, indexed 0, . . . , N ? 1. Section i is characterized by a single state variable, its density ni, so the state of the freeway is the N-dimensional vector n = (n0, . . . , nN?1). Vehicle movement in a section is governed by the familiar triangular ‘fundamental diagram’, which gives ?ow as a function of vehicle density. If the density is below critical, vehicles move at free ?ow speed; if it is above critical, the section is congested, speed is lower, and ?ow from the immediately upstream section is constrained. Thus the state of a freeway obeys a N-dimensional nonlinear di?erence equation. When the exogenous demand pattern of on-ramp and o?-ramp ?ows is constant, the di?erence equation is time-invariant, and it is meaningful to study its equilibrium states. Theorem 4.1 in Section 4 fully characterizes the structure of the equilibrium ?ows and states in any CTM model. Each demand pattern induces a unique equilibrium ?ow vector f, and an in?nite set of equilibrium states E. Corresponding to f is the set of bottleneck sections at which ?ow equals capacity. If there are K bottlenecks, the freeway partitions into 1 + K segments, S0, . . . , SK, each of which, except S0, begins at a bottleneck, and decomposes the set E into the product E = E0 · ? ? ? · EK, with Ek being the equilibrium set for segment Sk. Each equilibrium in Ek determines an integer j so that the most downstream j sections in Sk are congested (density is above critical), and the remaining sections are uncongested. The equilibrium set E forms a topologically closed, connected, K-dimensional surface in the N-dimensional state space. Two equilibria are special: the unique uncongested equilibrium nu in which free ?ow speed prevails in all sections; and the unique most congested equilibrium ncon. Every other equilibrium ne 2 E is bounded by these, nu 6 ne 6 ncon. Theorem 4.1 provides an explicit closed form expression for E. In the special case that the demand is strictly feasible, i.e., the equilibrium ?ow in each section is strictly below capacity, E reduces to the unique uncongested equilibrium nu. Section 5 studies the qualitative behavior of all trajectories generated by the CTM model. The model induces a strictly monotone map and some of the trajectory behavior is a consequence of the general theory of strictly monotone maps (Hirsch and Smith, 2005). One interesting consequence is that the unique equilibrium nu for a strictly feasible demand pattern is globally asymptotically stable: every trajectory converges to nu (Theorem 5.1). A more surprising result is that every equilibrium is (Lyapunov) stable: trajectories starting near an equilibrium ne 2 E remain near it forever (Theorem 5.2). The most remarkable result is that the CTM model is convergent: every trajectory converges to some equilibrium state ne 2 E (Theorem 5.3). Section 6 explores two implications for ramp metering. First, if the demand is infeasible and there is nometering, every trajectory converges to the most congested equilibrium. However, there is a ramp metering strategy that increases ?ow in every section and reduces total travel time (Theorem 6.1). Second, even with feasible demand if the freeway is in a congested equilibrium, there is a ramp metering strategy that moves the freeway to the uncongested equilibrium while reducing total travel time (Theorem 6.2). Section 7 summarizes the most signi?cant results. Some proofs are collected in the Appendix. 2. Background of CTM The simplest continuous macroscopic model was proposed by Lighthill and Whitham (1955) and Richards (1956), hence called LWR. Based on the conservation of vehicles, LWR is described by a single partial

G. Gomes et al. / Transportation Research Part C 16 (2008) 485–513

487

di?erential equation in conservation form. A signi?cant literature proposes and extends discrete approximations to LWR. Second order models with two equations were proposed by Payne (1971) and Whitham (1974), which Daganzo (1995) showed to be unsuitable for describing tra?c, since in these models vehicles may exhibit negative speeds. Aw and Rascle (2000) proposed an improved second order model, further studied in Haut and Bastin (2005), Herty and Rascle (2006), Piccoli and Garavello (2006). A third order Navier–Stokes type model was introduced in Helbing (1995). As indicated in Godlewski and Raviart (1996), the best numerical method to solve the partial di?erential equations along roads is a Godunov scheme (Godunov, 1959), as it is ?rst-order, correctly predicts shock propagations, lacks oscillating behavior and has a physical interpretation. The spatial domain is divided into cells and the state is constant in each of them. For LWR, it leads to piecewise approximation of the state (density) q(x) at each time step, whose evolution is computed for small time intervals if we know the solution of initial value problems with Heaviside initial conditions  ? q ; x < 0; qi ?x? ? q? ; x > 0; wherein i is the initial cell. Such initial value or Riemann problems can be solved in closed form for scalar conservation laws. For a system of conservation laws—as occurs in a multi-cell freeway—when no closed form solution is available, an approximate solver such as the Roe average method is used (Godlewski and Raviart, 1996; LeVeque, 1992). Several numerical methods can be used as a Godunov scheme (LeVeque, 1992; Lebacque, 1996). The CTM (Daganzo, 1994) is a Godunov scheme in which the ?ow as a function of density (fundamental diagram) has triangular (or trapezoidal) form. However, the popularity of CTM is not due to its intellectual roots in LWR but from its ?exible use in macroscopic simulation. 3. The CTM model Fig. 1 shows the freeway divided into N sections, each with one on- and one o?-ramp. Vehicles move from right to left. Section i is upstream of section i ? 1. There are two boundary conditions. Free ?ow prevails downstream of section 0; upstream of the freeway is an ‘‘on-ramp’’ with an in?ow of rN. The ?ow accepted by section N ? 1 is fN(k) vehicles per period or time step k. The cumulative di?erence leads to a queue of size nN(k) in period k. Table 1 lists the model variables and parameters with plausible values. The length of all sections is normalized to 1 by absorbing di?erences in length in the speeds vi, wi. To be physically meaningful one must have 0 < vi, wi < 1. O?-ramp ?ows are modeled as a portion bi(k) of the total ?ow leaving the section si ?k? ? bi ?k??si ?k? ? fi ?k??; or si ?k? ? ?bi ?k?=?1 ? bi ?k???fi ?k?:

 We assume constant split ratios bi (bN = 0). With bi ? 1 ? bi , the CTM model is, for k P 0,  ni ?k ? 1? ? ni ?k? ? fi ?k?=bi ? fi?1 ?k? ? ri ?k?; 0 6 i 6 N ? 1;  fi ?k? ? minfbi vi ?ni ?k? ? ci ri ?k??; wi?1 ?i?1 ? ni?1 ?k? ? ci?1 ri?1 ?k??; F i g; n ?1? 1 6 i 6 N; ?2?

f0 0 s0 r0

fi-1 i-1

fi i si

fi+1 i+1 ri sN-1 N-1

fN nN rN-1

rN

Fig. 1. The freeway has N sections. Each section has one on- and one o?-ramp.

488 Table 1 Model parameters and variables Symbol

G. Gomes et al. / Transportation Research Part C 16 (2008) 485–513

Name Section length Period (time step) Capacity (per lane) Free ?ow speed Congestion wave speed Jam density Critical density Split ratio Complementary split ratio =1 ? bi On-ramp blending factor Period number Flow from section i to i ? 1 in period k O?-ramp, on-ramp ?ow in section i in period k Number of vehicles in section i in period k

Value 1 0.5 20 0.5 0.5/3 160 40 2[0, 1) 2(0, 1] 2[0, 1] Integer Variable Variable Variable

Unit miles min veh/period section/period section/period veh/section veh/section dimensionless dimensionless dimensionless dimensionless veh/period veh/period veh/section

Fi vi wi i n nc i bi  bi ci k fi(k) si(k), ri(k) ni(k)

 f0 ?k? ? minfb0 v0 ?n0 ?k? ? c0 r0 ?k??; F 0 g; nN ?k ? 1? ? nN ?k? ? fN ?k? ? rN ?k?: Flow conservation in section i 6 N ? 1 is expressed by

?3? ?4?

ni ?k ? 1? ? ni ?k? ? fi ?k? ? fi?1 ?k? ? ri ?k? ? si ?k?;  which is equivalent to (1), using si ?k? ? bi =bi fi ?k?. Flow conservation at N is expressed by (4). The ?ow fi(k)  from section i to i ? 1 is governed by the fundamental diagram (2) with this interpretation: bi vi ?ni ?k? ? ci ri ?k?? is the number of vehicles that can move from section i to i ? 1 in period k; wi?1 ?i?1 ? ni?1 ?k? ? ci?1 ri?1 ?k?? is n the number that i ? 1 can accept; and Fi is the capacity or maximum ?ow from section i to i ? 1. Eq. (3) indicates there is no congestion downstream of section 0. Lastly, it is tacitly assumed that the ?ows si(k) are not constrained by o?-ramp capacity. The parameter values in Table 1 correspond to the fundamental diagram of Fig. 2. Its triangular form incorporates the assumption that is frequently used in our analysis  F i ? bi vi nc ? wi?1 ?i?1 ? nc ?: n ?5?
i i?1

 Assumption (5) may appear paradoxical as it relates the capacity Fi to a tra?c demand parameter bi . Howi vi ni ?k? is the ?ow from section i to section i ? 1 downstream of ever, the paradox disappears upon noting that b the o?-ramp ?ow si(k) = bivini(k). The state of the system is the N-dimensional vector n(k) = (n0(k), . . . , nN?1(k)). The queue size nN(k) is not included in the state. Section i is said to be uncongested or congested in period k accordingly as 0 6 ni ?k? 6 nc i or ni ?k? > nc . i Remarks. Two reviewers make the following important observations. First, there is empirical evidence of a capacity drop (of about ?ve percent) when the density exceeds its critical value. The triangular fundamental

slope = vi = 0.5 20 slope = wi = 0.5/3 c Fi = βivinic = wi-1 (ni-1-ni-1) 40 nc i 160 ni

Fig. 2. The fundamental diagram is characterized by the maximum ?ow Fi and speeds vi, wi.

G. Gomes et al. / Transportation Research Part C 16 (2008) 485–513

489

diagram of Fig. 2 then takes the shape of an ‘inverse k’. By neglecting this capacity drop, the bene?ts of ramp metering evaluated in Section 6 underestimate the true bene?ts. Some emerging research considers the introduction of mainline metering just upstream of each on-ramp, aimed at preserving capacity ?ow downstream of the on-ramp. Under these conditions, there is no capacity drop (thanks to mainline metering) and the CTM model may be applied for modeling or analysis without change. Second, taking vi < 1, instead of vi = 1, introduces a numerical error with respect to LWR incurred by the Godunov scheme, as discussed by Leclercq et al. (2005). The choice of vi < 1, wi < 1, needed to accommodate sections of different size, has no impact on the analysis of Sections 4 and 5. The results of Section 6 are also valid, except that the total travel time (due to queuing) would be different from that in LWR. 4. Structure of equilibria The parameters ci 2 [0, 1] in (2) and (3) re?ect the relative position of the on-ramp in section i (Gomes, 2004; Gomes and Horowitz, 2006). For simplicity we assume ci = 0, indicating that the on-ramp is at the beginning of each section as in Fig. 1. (However, the results below hold for a di?erent choice of ci.) With ci = 0, Eqs. (1)–(4) simplify  ni ?k ? 1? ? ni ?k? ? fi ?k?=bi ? fi?1 ?k? ? ri ?k?; 0 6 i 6 N ? 1;  fi ?k? ? fi ?n?k?? ? minfbi vi ni ?k?; wi?1 ?i?1 ? ni?1 ?k??; F i g; 1 6 i 6 N ; n 0 v0 n0 ?k?; F 0 g; f0 ?k? ? f0 ?n?k?? ? minfb nN ?k ? 1? ? nN ?k? ? fN ?k? ? rN ?k?: In view of (5) a useful alternative to (7) is  fi ?k? ? minfbi vi ni ?k?; F i ? wi?1 ?ni?1 ?k? ? nc ?; F i g; i?1 and if section i ? 1 is uncongested ?ni?1 ?k? 6 nc ?, (10) simpli?es to i?1 i vi ni ?k?; F i g: fi ?k? ? minfb ?6? ?7? ?8? ?9?

?10?

?11?

Fix the split ratios b0 . . . , bN?1. Assume stationary demands ri(k)  ri. Each on-ramp demand vector r = (r0, . . . , rN) induces a unique equilibrium ?ow vector f(r) = (f0, . . . , fN) calculated as fN ? rN ;  fi ? bi ?fi?1 ? ri ?; ?12? 0 6 i 6 N ? 1: ?13?

The function r # f(r) de?ned by (12) and (13) is one-to-one. A demand r is said to be feasible if 0 6 fi 6 Fi, 0 6 i 6 N; it is strictly feasible if 0 6 fi < Fi, 0 6 i 6 N. A strictly feasible demand induces an equilibrium ?ow with excess capacity in every section. A state n = (n0, . . . , nN?1) is an equilibrium for a feasible demand r with induced ?ow f = f(r), if the constant trajectory n(k)  n is a solution of (6)–(8)  fi ? minfbi vi ni ; F i ? wi?1 ?ni?1 ? nc ?; F i g; i?1 0 v0 n0 ; F 0 g: f0 ? minfb 1 6 i 6 N ? 1; ?14? ?15?

An equilibrium n is said to be uncongested if all sections are uncongested; otherwise it is congested. Let E = E(r) be the set of equilibria, i.e., all solutions of the nonlinear system of Eqs. (14) and (15), corresponding to a demand r. This section is devoted to characterizing E(r) and the pattern of congested sections for each n 2 E(r). If r is not feasible, there is no solution to (14) and (15), so E(r) = ;. Lemma 4.1 implies that E(r) 5 ; if r is feasible. Lemma 4.1. A feasible demand r has a unique uncongested equilibrium nu(r). Proof. Existence: Let f = f(r) be the equilibrium ?ow. De?ne

490

G. Gomes et al. / Transportation Research Part C 16 (2008) 485–513

 nu ? ?bi vi ? fi ; i

?1

0 6 i 6 N ? 1:

?16?

 Then ni ?k?  nu satis?es (6), because (6) is equivalent to (13). Next, because 0 6 fi 6 Fi and F i ? bi vi nc (see i i u i vi ??1 fi 6 ?bi vi ??1 F i ? nc . So nu is uncongested. It remains to prove that nu is an equilibrium,  (5)), ni ? ?b i  i.e., satis?es (14), which simpli?es to (11) because nu is uncongested. From (16), fi ? bi vi nu , and since r is feai sible, fi 6 Fi. So (11) holds. Uniqueness: Suppose f0 6 ni 6 nc ; 0 6 i 6 N ? 1g is an equilibrium, i.e., satis?es (14) and (15). Since i   ni 6 nc , bi vi ni 6 bi vi nc ? F i , therefore (14) reduces to i i  fi ? minfbi vi ni ; wi?1 ?i?1 ? ni?1 ?g: n    If fi 6? bi vi ni , it must be that bi vi ni > wi?1 ?i?1 ? ni?1 ? P wi?1 ?i?1 ? nc ? ? F i . This contradicts bi vi ni 6 F i , n n i?1 i vi ni , so ni ? nu . h hence fi must equal b i Proposition 4.1. Suppose at equilibrium n, section i ? 1 is uncongested and sections i, . . . , i + j are congested. Then  fi ? F i ; b?1 F i ? ri ? fi?1 < F i?1 ; . . . ; fi?j?1 < F i?j?1 : ?17? i Proof. Since ni?1 6 nc , from (11), i?1  fi ? minfbi vi ni ; F i g:  Since ni > nc , one has bi vi ni > F i from (5); and since r is feasible, Fi P fi. Hence fi = Fi and, by (13), i   fi?1 ? b?1 fi ? ri ? b?1 F i ? ri :
i i

Again, as ni >

nc , i

(14) implies

 fi?1 ? minfbi?1 vi?1 ni?1 ; F i?1 ? wi ?ni ? nc ?; F i?1 g < F i?1 : i Lastly, if section i + k is congested, ni?k > nc , hence i?k  fi?k?1 ? minfbi?k?1 vi?k?1 ni?k?1 ; F i?k?1 ? wi?k ?nc ? ni?k ?; F i?k?1 g < F i?k?1 ;
i?k

and the remainder of the assertion follows.

h

Corollary 4.1. A strictly feasible demand r has a unique equilibrium, so E(r) = {nu}. Proof. If the equilibrium n = (n0, . . . , nN?1) is uncongested, then n = nu by Lemma 4.1. So suppose there is at least one congested section. There are two cases to consider. In the ?rst case, section 0 is congested. Since  f0 ? minfb0 v0 n0 ; F 0 g < F 0 by strict feasibility, so n0 < nc , which means section 0 is not congested. In the 0 remaining case, there must exist a pair of adjacent sections i ? 1, i with i ? 1 uncongested and i congested. But then by Proposition 4.1, fi = Fi, which contradicts strict feasibility of r. h The next result is a partial converse to Proposition 4.1. Proposition 4.2. Suppose fi = Fi, fi+1 < Fi+1, . . . , fi+j < Fi+j. Suppose at equilibrium n section i + j is congested. Then sections i, i + 1, . . . , i + j are all congested at n. Proof. Because section i + j is congested, i.e., ni?j > nc , and fi+j < Fi+j, i?j  ?; F i?j g ? F i?j ? wi?j?1 ?ni?j?1 ? nc fi?j ? minfbi?j vi?j ni?j ; F i?j ? wi?j?1 ?ni?j?1 ? nc
i?j?1

i?j?1 ?

< F i?j ;

so ni?j?1 > nc h i?j?1 , i.e., section i + j ? 1 is congested. The result follows by induction. We say that i is a bottleneck section for demand r (or induced ?ow f) if fi = Fi. (The reason for the name will become clear in Theorem 4.1.) Suppose there are K P 0 bottleneck sections at 0 6 I1 < I2 ? ? ? < IK 6 N ? 1. Partition the freeway into 1 + K segments S0, . . . , SK comprising contiguous sections as follows:

G. Gomes et al. / Transportation Research Part C 16 (2008) 485–513

491

S 0 ? f0; . . . ; I 1 ? 1g; S 1 ? fI 1 ; . . . ; I 2 ? 1g; . . . ; S K ? fI K ; . . . ; N ? 1g:

?18?

If there are no bottleneck sections, K = 0, I1 = N, and S0 = {0, . . . , N ? 1} is the entire freeway. On the other hand, if the most downstream section is congested, I1 = 0, and S0 is the empty segment. Proposition 4.3. The sections immediately downstream of the segments S0, . . . , SK are uncongested. Consequently, for k = 1, . . . , K,  ?19? fI ? minfbI vI nI ; F I g:
k k k k k

Proof. The assertion is true of segment S0 because downstream of section 0 is free ?ow by assumption. Consider segment Sk. Since  fI k ? minfbI k vI k nI k ; F I k ? wI k ?1 ?nI k ?1 ? nck ?1 ?; F I k g ? F I k ; I we must have nI k ?1 6 nck ?1 , i.e., section Ik ? 1 is uncongested, and (19) holds. I h

Partition the N-dimensional state n = (n0, . . . , nN?1) into sub-vectors n = (n0, . . . , nK) in conformity with the segments S0, . . . , SK, so nk has components {ni, i 2 Sk}. Since the equilibrium ?ow immediately upstream of segment Sk is known (it is equal to capacity) and the section immediately downstream of Sk is uncongested, the equilibrium conditions (14) and (15) partition into 1 + K decoupled conditions, one for each segment. Thus n0 satis?es  f0 ? minfb0 v0 n0 ; F 0 g;  fi ? minfbi vi ni ; F i ? wi?1 ?ni?1 ? nc ?; F i g; i?1 nk satis?es for k = 1, . . . , K,  fI k ? minfbI k vI k nI k ; F I k g;  fi ? minfbi vi ni ; F i ? wi?1 ?ni?1 ? nc ?; F i g; i?1 ?22? I k ? 1 6 i 6 I k?1 ? 1: ?23? ?20? 1 6 i 6 I 1 ? 1; ?21?

These decoupled conditions decompose the equilibrium set. Proposition 4.4. The set of equilibria E(r) factors into the product set, E?r? ? E0 ?r? ? ? ? ? ? EK ?r?; ?24? in which E0(r) is the set of solutions n0 of (20) and (21) and Ek(r) is the set of solutions nk of (22) and (23) for k P 1. We now fully characterize the components E0(r), . . . , EK(r). Recall that the ?ow in all non-bottleneck sections is strictly below capacity: fi < F i ; i 62 fI 1 ; . . . ; I K g: ?25?

Lemma 4.2. E0(r) = {nu,0} consists of a single point, the component of the uncongested equilibrium nu corresponding to segment S0. Hence nu,0 is given by  nu;0 ? ?bi vi ??1 fi ; i 0 6 i 6 I 1 ? 1: ?26?

Proof. Because of (25) the equilibrium ?ows f0 ; . . . ; fI 1 ?1 are strictly below capacity and so, by Corollary 4.1, E0(r) = {nu,0}, and (26) follows from (16). h The next result gives an explicit expression for the equilibrium set Ek(r). Lemma 4.3. nk 2 Ek(r) if and only if either (i) there is no congested segment at nk and nk = nu,k, or (ii) there exists j 2 {Ik, . . . , Ik+1 ? 1} such that at nk sections Ik, . . . , j are congested, sections j + 1, . . . , Ik+1 ? 1 are uncongested and nk is given by (see Fig. 3)

492

G. Gomes et al. / Transportation Research Part C 16 (2008) 485–513

Fig. 3. Equilibrium satisfying (27)–(29) (top) or (30) (bottom).

nk ? nc ? w?1 ?F i?1 ? fi?1 ?; I k 6 i 6 j ? 1; i i i  ?1 nk ? nu ? ?bi vi ? fi ; j ? 2 6 i 6 I k?1 ? 1;
i i

?27? ?28?
?1

nk ? nc ? w?1 ?F j?1 ? fj?1 ? and j j j nk j 2 ?nc ; nc j j ? w?1 ?F j?1 j ? fj?1 ??

 nk 2 ??bj?1 vj?1 ? fj?1 ; nc ?; or j?1 j?1 k u j?1 vj?1 ??1 fj?1 and n ? n ? ?b
j?1 j?1

?29? ?30?

Proof. Let nk 2 Ek(r) be an equilibrium. Then (i) follows from Lemma 4.1. Next, according to Proposition 4.2 there exists j such that sections Ik, . . . , j are congested and j + 1, . . . , Ik+1 ? 1 are uncongested. Hence for i 6 j ? 1,  fi ? minfbi vi nk ; F i ? wi?1 ?nk ? nc ?; F i g ? F i ? wi?1 ?nk ? nc ?;
i i?1 i?1 i?1 i?1

because > For i P j + 2,

nk i

nc ; nk i i?1

>

nc , i?1

which proves (27).

  fi ? minfbi vi nk ; F i ? wi?1 ?nk ? nc ?; F i g ? bi vi nk ; i i?1 i?1 i because nk 6 nc ; nk 6 nc , which proves (28). i i i?1 i?1 Lastly, because fj+1 < Fj+1,   fj?1 ? minfbj?1 vj?1 nk ; F j?1 ? wj ?nk ? nc ?; F j?1 g ? minfbj?1 vj?1 nk ; F j?1 ? wj ?nk ? nc ?g j?1 j j j?1 j j  Hence either fj?1 ? F j?1 ? wj ?nk ? nc ? and then (29) holds, or fj?1 ? bj?1 vj?1 nk and then (30) holds. j j j?1
k

h

 Three densities appear in the expression of E (r), namely ? ?bi vi ? fi , the uncongested equilibrium density; nc , the critical density; and the congested equilibrium density i nu i ncon ? nc ? w?1 ?F i?1 ? fi?1 ?: i i i By Lemma 4.3 Ek ?r? ? fnu;k g [
j2S k

?1

?31?

Ek ?r?; j

?32?

in which Ek ?r? is the set of nk satisfying (27)–(30): j Ek ?r? ? f?ncon ; . . . ; ncon ; nj ; nu ; . . . ; nuk?1 ?1 ?jnj 2 ?nc ; ncon ?g j I j?1 j?1 I j j [ k f?ncon ; . . . ; ncon ; nj?1 ; nu ; . . . ; nuk?1 ?1 ?jnj?1 2 ?nu ; nc ?g: Ik j j?2 I j?1 j?1
?1

?33?

 Observe that fI k ? F I k , nuk ? ?bI k vI k ? F i ? nck . So it follows from (33) that nu;k 2 Ekk ?r?. Hence (32) simpli?es I I I to [ Ek ?r? ? Ek ?r?: ?34? j
j2S k

G. Gomes et al. / Transportation Research Part C 16 (2008) 485–513

493

Observe next that the ?rst set on the right hand side in (33) forms a straight line segment Ek connecting the j? points nk ?j?? ? ?ncon ; . . . ; ncon ; nc ; nu ; . . . ; nuk?1 ?1 ? Ik j?1 j j?1 I and nk ?j? ? ?ncon ; . . . ; ncon ; nu ; . . . ; nuk?1 ?1 ?: Ik j j?1 I Denote this line segment in terms of its endpoints as Ek ?r? ? ?nk ?j??; nk ?j??: j? ?37? ?36? ?35?

Similarly, the second set on the right hand side in (33) forms a straight line segment connecting the points nk(j) and nk ?j?? ? ?ncon ; . . . ; ncon ; nc ; nu . . . ; nuk?1 ?1 ?; Ik j j?1 j?2 I and denoted as Ek ?r? ? ?nk ?j?; nk ?j???: j? The two line segments have exactly one point, nk(j), in common. Thus Ek ?r? ? Ek ?r? [ Ek ?r?; j j? j? and, by comparing (35) and (38) one sees that nk ?j?? ? nk ?j ? 1??; ?41? so that Ek ?r? and Ek ?r? have exactly this point in common. Lastly, since the densities nu 6 nc 6 ncon are i i i j ?j?1? ordered, so are the endpoints: ? ? ? 6 nk ?j?? 6 nk ?j? 6 nk ?j?? ? nk ??j ? 1??? 6 nk ?j ? 1? 6 ? ? ? ?42? ?40? ?39? ?38?

(For vectors x and y, x 6 y means xi 6 yi for all components i.) Fig. 4 depicts the projection of Ek ?r? ? Ek ?r? [ Ek ?r? on the two-dimensional space spanned by nk ; nk j j? j? j j?1 k k k and the projection of Ek ? Ek j?1 ?j?1?? ?r? [ E ?j?1?? ?r? on the space spanned by nj?1 ; nj?2 . According to (41) the two highlighted points in the ?gure are the same. Observe lastly that the straight line segments E(j+1)? and Ej+ are aligned. Theorem 4.1 follows from Proposition 4.4, and Lemmas 4.2 and 4.3. Theorem 4.1. Let r be a feasible demand, f the induced equilibrium ?ow, and E(r) the equilibrium set. If r is strictly feasible, E(r) consists of the unique uncongested equilibrium nu. Otherwise, partition the freeway into

Fig. 4. Projection of Ek ?r? on coordinates nk ; nk (left) and projection of Ek ?r? on coordinates nk ; nk (right). j j?1 j?1 j?2 j j?1

494

G. Gomes et al. / Transportation Research Part C 16 (2008) 485–513
f < F0 0 f = FI I 1 f = FI I 2

1

2 N-1

S0

S1

S2

Fig. 5. The demand induces two bottleneck sections and three segments. S0 is uncongested. In the depicted equilibrium S1 has one congested section and S2 has three congested sections.

segments S0, . . . , SK corresponding to the bottleneck sections 0 6 I1 < ? ? ? < IK 6 N ? 1. Then E(r) is the direct product (24): E?r? ? E0 ?r? ? ? ? ? ? EK ?r?: Each Ek(r) decomposes as the union (34): [ E0 ?r? ? fnu;0 g; Ek ?r? ? Ek ?r?; k P 1: j
j2S k

Each Ek ?r? is the union of two connected line segments, given by the ‘closed form’ expression (37), (39) and (40). j Ek (r) is the union of jSkj connected straight line segments. (jSkj = jIk+1 ? Ikj is the number of sections in Sk.) Consecutive sets Ek ?r? and Ek ?r? have exactly one point in common, and they are ordered: if nk 2 Ek ?r? and j j?1 j 0k n 2 Ek , then nk 6 n 0 k. In particular, the most congested equilibrium in Ek(r) is ncon,k with components j?1 ncon ; i 2 S k , given by (31). Every nk 2 Ek(r) lies between the uncongested equilibrium nu,k and ncon,k, i.e., i nu,k 6 nk 6 ncon,k. Hence for all n 2 E(r), nu 6 n 6 ncon ; in which the most congested equilibrium is ncon = (nu,0, ncon,1, . . . , ncon,K). Lastly, E(r) forms a connected, topologically closed surface of dimension K in the N-dimensional state space. Proof. Only the last assertion needs proof, which follows from the observation that E(r) is the product of 1 + K sets, E0(r), . . . , EK(r), the ?rst of which being a single point has dimension 0, and each of the rest being a union of connected line segments has dimension 1. h Fig. 5 illustrates the use of Theorem 4.1. The demand induces a ?ow that gives rise to bottlenecks at I1, I2 which partition the freeway into three segments S0, S1, S2. S0 is uncongested. An equilibrium determines the number of congested sections in the other segments. The ?gure illustrates an equilibrium in which one section in S1 and three sections in S2 are congested (depicted by shaded rectangles); the others are uncongested. The congested sections must lie immediately upstream of the corresponding bottleneck. This simple consequence of the CTM model, which conforms to empirical observations, has surprisingly not been previously noticed. 5. Dynamic behavior Theorem 4.1 fully characterizes the equilibrium behavior of any CTM model. This section is devoted to the complete description of the qualitative behavior of all trajectories of the N-dimensional di?erence equation system (6)–(8). We assume a constant feasible demand r and write (6)–(8) as ni ?k ? 1? ? gi ?n?k??; 0 6 i 6 N ? 1: ?43? ?44? Let g = (g0, . . . , gN?1). We will consider initial conditions n n 2 R ? fnj0 6 ni 6 i ; 0 6 i 6 N ? 1g: Each initial condition n(0) 2 R generates a trajectory {n(k), k P 0} according to n(k + 1) = g(n(k)).

G. Gomes et al. / Transportation Research Part C 16 (2008) 485–513

495

For two vectors x, y in RN, write x 6 y ( xi 6 y i ; ) x < y ( x 6 y; x 6? y; ) x ( y ( xi < y i : ) Following Hirsch and Smith (2005) say that g is strictly monotone if, for x, y 2 R, x < y ) g?x? < g?y?; g is strongly monotone if x < y ) g?x? ( g?y?: The Proof of Lemma 5.1 can be found in the Appendix. Lemma 5.1. The map g is strictly monotone, but it is not strongly monotone. Hirsch and Smith (2005) survey the theory of monotone maps. The most powerful results, however, require strong monotonicity, and do not apply to the CTM model. Let the equilibrium ?ow induced by the demand r result in bottlenecks at 0 6 I1 < ? ? ? < IK 6 N ? 1, and let S0, . . . , SK be the corresponding freeway partition. By Theorem 4.1 every equlibrium lies between the uncongested equilibrium nu and the most congested equilibrium ncon, nu 6 n 6 ncon ; n 2 E?r?: ?45? ^ Let ^?k?; k P 0 be the trajectory starting with the empty freeway, n?0? ? 0, and let ?k?; k P 0 be the trajecn n tory starting with the completely jammed freeway, i ?0? ? i ; 0 6 i 6 N ? 1. Let n(k) be a trajectory starting n n in any state n(0) 2 R. The next result shows how much monotonicity of g constrains the trajectories of the CTM model. Lemma 5.2 (i) Every trajectory lies between f^?k?g and f?k?g: n n ^?k? 6 n?k? 6 ?k?; n n n lim ^?k? ? nu : k P 0:
u

?46? ?47?

(ii) The trajectory starting with the empty freeway converges to the uncongested equilibrium n :
k!1

(iii) The trajectory starting with the completely jammed freeway converges to the most congested equilibrium ncon:
k!1

n lim ?k? ? ncon :

?48?

Proof ^ (i) Since n?0? 6 n?0? 6 ?0?, monotonicity implies ^?1? 6 n?1? 6 ?1?, and then (46) follows by induction. n n n (ii) Since ^?1? P ^?0? ? 0, monotonicity implies ^?2? ? g?^?1?? P g?^?0?? ? ^?1?. By induction, the trajecn n n n n n tory is increasing: ^?k ? 1? P ^?k?. Since the trajectory is bounded above by the jam density, it must conn n verge to some equilibrium point, say ^e . Furthermore, since n(k)  nu is also a trajectory, by (46) one n must have ^e 6 nu , and so (45) implies ^e ? nu . n n (iii) Since  ? ?0? P ?1?, monotonicity implies that the trajectory is decreasing: ?k ? 1? 6 ?k?. Since the n n n n n trajectory is bounded below by 0, it must converge to an equilibrium, say e . As n(k)  ncon is also a tran jectory, by (46) one must have e P ncon , and so (45) implies e ? ncon . h n n Lemma 5.2 leads to the ?rst interesting result, Theorem 5.1: If the demand is strictly feasible, then nu is a globally, asymptotically stable equilibrium.

496

G. Gomes et al. / Transportation Research Part C 16 (2008) 485–513

Theorem 5.1. Suppose r is strictly feasible. Then every trajectory converges to nu. Proof. By Lemma 4.1 E(r) = {nu}, so ncon = nu. Hence both ^?k? and ?k? converge to nu. By (46), every tran n jectory n(k) converges to nu as well. h If r is not strictly feasible, the equilibrium set E(r) is in?nite and there is no easy way to analyze how trajectories behave. The main result of this section, Theorem 5.3, is that every trajectory converges to some equilibrium. Before getting into the complexities of the proof, we pause to study three examples. 5.1. Examples Example 1 is a freeway with two identical sections, each one mile long. The fundamental diagram, equilibrium ?ow, and equilibrium set E are shown in Fig. 6. The critical density nc ? 100 veh=mile; the jam density i i ? 400 veh=mile; free ?ow speed v = 60 mph and the congestion wave speed w = 20 mph. n The demand vector r = (r0 = 1200, r1 = 0, r2 = 4800), all in vehicles per hour (vph). The upstream ?ow r2 = f2 = 4800 vph, and f0 = F0 = 6000 vph. Thus section 0 is the only bottleneck. The uncongested equilibrium nu = (100, 80) and the most congested equilibrium ncon = (160, 160). By Theorem 4.1, the equilibrium set E consists of two straight line segments shown in the ?gure (also see Fig. 4). The phase portrait of Fig. 7 displays the orbits of the two-dimensional state with initial conditions on the boundary of the square R = [0, 400] · [0, 400]. An orbit is the set of states {n(k)jk P 0} traversed by a trajectory k ! n(k). We analyze the orbit structure displayed in the ?gure. The observations made below hold in general. 1. Every trajectory converges to an equilibrium point in E. As a consequence, the state space R is partitioned as [ R? R?n?;
n2E

in which R(n) is the set of all initial states whose trajectories converge to the equilibrium n. By monotonicity R(nu) includes all initial states n 6 nu, and R(ncon) includes all initial states n P ncon. By contrast, for all other equilibrium states R(n) is simply a one-dimensional manifold. (In the general case, R(n) is a (N ? K)-dimensional manifold, Corollary 5.1.) 2. The ?gure shows four equi-time contour plots, labeled k = 12 s, . . . , 600 s. For example, the contour plot k = 60 s is the set of points reached by all trajectories at k = 60 s. As k increases, the contour plots converge towards the equilibrium set E. As might be expected, the contours initially converge rapidly and the convergence slows down as E is approached. More interestingly, consider the orbit going through the state n = (340, 50) on the k = 60 contour. In this state section 0 is congested but section 1 is not. However, by time 200 (whose contour plot is not shown) the state has moved to approximately (250, 150), indicating

6000

0

4800

1

4800

1200 f 0 6000 f1 4800 E nu = (100, 80) 100 160 n 0 400 80 160 n1 n 0 n 1 ncon = (160, 160)

Fig. 6. Freeway, equilibrium ?ows, fundamental diagram, and equilibrium set E of Example 1.

G. Gomes et al. / Transportation Research Part C 16 (2008) 485–513

497

Fig. 7. Equilibrium set and orbits of Example 1.

both sections are congested. The time di?erence of 200 ? 60 = 140 s is roughly predictable: because the congestion wave speed is 20 mph it takes about 3 min for the congestion wave to travel the one mile-long section. 3. According to Theorem 4.1 the equilibrium set is ordered: if n, n 0 are two equilibria, either n 6 n 0 or n 0 6 n. Consequently, downstream sections must get congested before an upstream section. As seen in the ?gure, every trajectory in which section 1 is getting congested also congests section 0. The unshaded area in the ?gure is the set of all initial states from which trajectories converge to an equilibrium in which the upstream section is not congested. 4. All equilibria support the same equilibrium ?ows. However at equilibrium nu the speed is v = 60 mph throughout, whereas in ncon the speed is 4800/160 (?ow/density) or 30 mph. Thus, although both nu and ncon achieve the same throughput, the freeway travel time in nu is one-half of that in ncon. In Example 2 the ?ow r2 is slightly reduced from 4800 to 4750 vph, so the demand becomes strictly feasible and the equilibrium set collapses to the single uncongested equilibrium nu. The resulting phase portrait in Fig. 8 can be compared with Fig. 7. The trajectories are nearly identical, except that when they approach the equilibrium set of Example 1 they turn and converge to nu % (100, 80). Example 3 shown in Fig. 9 is a modi?cation of Example 1 in that there are three identical sections. The fundamental diagram is the same as in Example 1. The demand r0 = 1200, r1 = r2 = 0, r3 = 4800. Again section 0 is the only bottleneck. The equilibrium set now comprises three straight line segments, connecting the uncongested equilibrium nu = (100, 80, 80) and the most congested equilibrium ncon = (160, 160, 160). The orbit structure supports the observations made earlier: although it is less apparent in the ?gure, R(n) is a two-dimensional manifold if n 5 nu, ncon. We resume the general discussion. As before let r be a demand vector and / the resulting equilibrium ?ow vector, i.e. (see (12) and (13))

498
400

G. Gomes et al. / Transportation Research Part C 16 (2008) 485–513

350

300

density in section 1

250

t = 300
200

t = 600
150

t = 1200

100

50

t = 60 t = 12

0 0 50 100 150 200 250 300 350 400

density in section 0
Fig. 8. Equilibrium set and orbits of Example 2.

6000

0

4800 1200

1

4800

2

4800

400 350 300 section 2 250 200 150 100 50 0 0 100 section 0 200 nu 300 100 ncon 400 0 200 section 1 300 400

Fig. 9. Freeway, equilibrium set and orbits of Example 3.

G. Gomes et al. / Transportation Research Part C 16 (2008) 485–513

499

/N ? rN ;

 /i ? bi ?/i?1 ? ri ?;

0 6 i 6 N ? 1:

?49?

Let 0 6 I1 < ? ? ? < IK 6 N ? 1 be the bottlenecks, and S0, . . . , SK the corresponding freeway partition. By Theorem 4.1 the equilibrium set decomposes as E?r? ? fnu;0 g ? E1 ?r? ? ? ? ? ? EK ?r?: ?50?

Let ^?k?; k P 0; be the trajectory starting at 0 and converging to nu. Let ?k? be the trajectory starting at  and n n n converging to ncon. Fix an initial condition n 2 R and let n(k),k P 0, be the trajectory starting at n. We recall some facts from the general theory of dynamical systems. The x-limit set of n is the set of all limit points of the trajectory {n(k)}: n o x?n? ? p 2 Rjthere is a subsequence k m with lim n?k m ? ? p :
m!1

x(n) is non-empty, compact, and invariant, i.e., if p 2 x(n) the trajectory starting at p stays within x (n). Furthermore the trajectory converges to x(n), i.e., limkd(n(k), x(n)) = 0, with d(x, x(n)) = min{jx ? pjjp 2 x(n)}. Our objective is to prove that the trajectory {n(k)} converges to an equilibrium, which is achieved in two steps. The ?rst step shows that x(n) always contain an equilibrium (Lemma 5.4). The second step shows that every equilibrium is stable (Theorem 5.2). We adopt the following notation. For any p 2 R, (  minfb0 v0 p0 ; F 0 g; i ? 0; fi ?p? ?  minfbi vi p ; wi?1 ?i?1 ? p ?; F i g; i P 1; n
i i?1

and fi ?k? ? fi ?n?k??: Lemma 5.3 (i) Suppose nu 6 p 6 ncon. Then fi ?p? P /i ; all i; and f i ?p? ? F i ; i 2 fI 1 ; . . . ; I K g: ?51? (ii) If p 2 x(n), nu 6 p 6 ncon. (iii) Along the trajectory {n(k)}
k!1

lim inf fi ?k? P /i ;

all i;

and

k!1

lim fi ?k? ? F i ;

i 2 fI 1 ; . . . ; I K g:

?52?

 Proof. Evaluate the three alternatives in fi ?p? ? minfbi vi pi ; wi?1 ?i?1 ? pi?1 ?; F i g: n   fi ?p? ? bi vi pi P bi vi nu ? /i ; by ?16?; or i ? wi?1 ?i?1 ? pi?1 ? P wi?1 ?i?1 ? ncon ? ? /i ; n n i?1 ? F i P /i ; always: Hence fi(p) P /i and assertion (i) follows since for bottleneck sections /i = Fi. (ii) follows from the observations that ^?k? 6 n?k? 6 ?k? and ^?k? ! nu ; ?k? ! ncon by Lemma 5.2; hence every limit point p of {n(k)} n n n n satis?es nu 6 p 6 ncon. To prove (iii) consider a subsequence {km} along which fi(km) ! lim inf fi(k) and n(km) ! p 2 x(n). Then lim inf fi(k) = fi(p) P /i, by (i) and (ii). h To simplify the discussion we assume that nN, the upstream ramp queue, is always so large as to maintain fN ?k?  rN ? /N ; k P 0: ?53? by ?31?; or

500

G. Gomes et al. / Transportation Research Part C 16 (2008) 485–513

Lemma 5.4. x(n) \ E(r) 5 ;. Proof. Let p0 2 x(n) and p(k), k P 0, the trajectory starting at p0. Rewrite (6) in terms of this trajectory, and (49) as  pi ?k ? 1? ? pi ?k? ? b?1 fi ?p?k?? ? fi?1 ?p?k?? ? ri i ?1  ri ? b / ? / :
i i i?1

Adding these together gives  pi ?k ? 1? ? pi ?k? ? b?1 ?/i ? fi ?p?k??? ? ?/i?1 ? fi?1 ?p?k???: i Summing this equation for i = j, . . . , N ? 1 and using (53) leads to
N ?1 X i?j

pi ?k ? 1? ? ?

N ?1 X i?j N ?1 X i?j

pi ?k? ?

N ?1 X i?j

 b?1 ?/i ? fi ?p?k??? ? i
N ?1 X i?j

N ?1 X i?j

?/i?1 ? fi?1 ?p?k???

pi ?k? ? ?/j ? fj ?p?k??? ?

 bi b?1 ?/i ? fi ?p?k???: i

PN By Lemma 5.3, and taking j = 1, shows that 1 ?1 pi ?k? is decreasing, and since it is positive, it converges. 1 0 Hence fi(p(k)) ! /i for each i. So if p 2 x(p ), f ?p1 ? ? /; i:e:; p1 2 E?r?; h from which the assertion follows since p1 2 x(p0) & x(n), because x(n) is invariant.

Recall the de?nition of (Lyapunov) stability: An equilibrium ne is stable if for every  > 0 there is d > 0 such that jn ? nej < d implies jn(k) ? nej <  for all k, in which {n(k)} is the trajectory starting at n. Fix an equilibrium ne. By Theorem 4.1 ne has the form ne ? ?ne;0 ; ne;1 ; . . . ; ne;K ?; with ne,0 = nu,0, ne;m 2 Em ?r? for some j 2 Sm, 1 6 m 6 K. j Lemmas 5.5 and 5.6 will prove that if jn ? nej < d, and n(k) = (n0(k), n1(k), . . . , nK(k)), k P 0 is the trajectory starting at n, then there exists an equilibrium ne, possibly di?erent from ne, such that ? j~e;m ? ne;m j < ; n
k!1

lim nm ?k? ? ~e;m ; n

0 6 m 6 K;

?54?

Lemma 5.5. (54) holds for m = 0. In fact
k!1

lim n0 ?k? ? nu;0 ? ne;0 :

?55?

Proof. By Lemma 5.2, ^?k? 6 n?k? 6 ?k?, ^?k? ! nu , ?k? ! ncon . Then (55) follows because, by (50), n n n n ncon,0 = nu,0. h Lemma 5.6. Suppose (54) holds for m ? 1 P 0. Then it holds for m. Proof. Consider (54) for m P 1. By Theorem 4.1 ne;m 2 Emm ?j ?r? for some j P 0, so that sections Im, . . . , Im + j I are congested and Im + j + 1, . . . , Im+1 ? 1 are uncongested as indicated in Fig. 10.
FIm

Im

Im+j

Im+1-1 FI m+1

Fig. 10. In equilibrium ne,m sections Im, . . . ,Im + j of Sm are congested.

G. Gomes et al. / Transportation Research Part C 16 (2008) 485–513

501

The proof, which separately analyzes the three cases, j = Im+1 ? 1, j = Im, and Im < j < Im+1 ? 1, is long and placed in the Appendix. h Theorem 5.2. Every equilibrium ne 2 E(r) is stable. In fact for  > 0 there is d > 0 such that if jn ? nej < d, the trajectory {n(k)} starting at n converges to an equilibrium ne with jne ? nej < . ? ? Proof. Lemmas 5.5 and 5.6 prove the second part of the assertion which implies stability. h

Fig. 7 illustrates Theorem 5.1. Trajectories starting close to an equilibrium all converge to some nearby equilibrium. Theorem 5.3. The CTM model is a convergent system, i.e. every trajectory converges to some equilibrium in E(r). Proof. Consider any trajectory {n(k)}. By Lemma 5.4 there is an equilibrium ne and a subsequence {km} along which n(km) ! ne as m ! 1. By Theorem 5.2 the trajectory must converge to this equilibrium. h Recall that the stable manifold R(ne) of an equilibrium ne 2 E(r) comprises all n 2 R whose trajectories converge to ne. The next result characterizes the orbit structure. Corollary 5.1. If r is strictly feasible, E(r) = {nu} and R (nu) = R. If r is not strictly feasible, E(r) is a K-dimensional manifold and R(ne) is a (N ? K)-dimensional manifold for ne 5 nu, ncon, whereas R(nu), R(ncon) are N-dimensional manifolds with boundary. Proof. By Theorem 4.1 E(r) is a K-dimensional manifold. By Theorem 5.3 [ R? R?n?:
ne 2E?r?

By Lemma 5.2 every trajectory starting at n 6 nu converges to nu and every trajectory starting at n P ncon converges to ncon. Because E(r) is ordered, it is not very dif?cult to show, using monotonicity, that the stable manifolds of all equilibria ne 5 nu, ncon are diffeomorphic. The assertion then follows. h 6. Implications for ramp metering We explore two implications for ramp metering. The ?rst considers the case when the demand vector r is infeasible, i.e., the associated equilibrium ?ow / given by (49) is such that it exceeds the capacity in some section. Peak hour demand may be infeasible in this sense. We begin with an example to illustrate the issues.

Fig. 11. Freeway, on-ramp and o?-ramp ?ows of example: feasible demand (top); excess demand (bottom).

502

G. Gomes et al. / Transportation Research Part C 16 (2008) 485–513

Example. The upper part of Fig. 11 displays a freeway with four identical sections, each with capacity 6000 vph. The demand vector r = (r0 = 1200, r1 = 0,r2 = 2700, r3 = 2000, r4 = 4000). All split ratios are the   same: bi = b = 0.2, so b ? 0:8 and a ? b?b??1 ? 0:25. The demand r is feasible and the equilibrium ?ow / = (/0 = 6000, /1 = 4800, /2 = 6000, /3 = 4800, /4 = 4000). The off-ramp ?ow in section i is a/i. Sections 0 and 2 are bottleneck sections, with equilibrium ?ows equal to capacity. Now consider the demand ~ in which ~0 ? 1300 > r1 and ~i ? ri ; i P 0. This demand is not feasible because r r r it would increase /0 to /1 ? ~0 ? 6100, which exceeds capacity. Evidently, the increased on-ramp ?ow in secr tion 0 will create congestion in section 0 and force a reduction in the ?ow out of section 1 from /1 = 4800 to ~ ~ /1 ? 4700. This reduction from /1 to /1 is achieved by a reduction in the ?ow from section 2 from /2 = 6000 ~ ~ to /2 ? 5875, which in turn reduces the ?ow from section 3 from /3 = 4800 to /3 ? 4643:75, and ultimately ~ the ?ow from section 4 from /4 = 4000 to /4 ? 3804:6875. As a result the on-ramp queue n4 will grow at the rate of 4000 ? 3804.6875 = 195.3125 vph. All sections will become congested. ~ The reductions in the equilibrium ?ow from / to / will proportionately reduce the discharge at the o?~ ramps from a/i to a/i . The new equilibrium ?ows are displayed in the lower part of the ?gure. The example suggests some observations. ~ 1. The infeasible demand ~ leads to a unique equilibrium ?ow /. This is the ?ow corresponding to the feasible r ~ demand ~f , which is the same as ~, except that the upstream ?ow is reduced from /4 = 4000 to /4 % 3804. r r The system converges to the (unique) most congested equilibrium corresponding to ~f . r 2. The reduction in the ?ow at the upstream ramp of about 196 = 4000 ? 3804 vph is nearly twice the ‘excess’ demand of 1300 ? 1200 = 100 vph at the ramp in section 0. Suppose that we meter the on-ramp in section 0 and admit only 1200 vph. The queue at this ramp will now grow at 100 vph, but the resulting equilibrium ?ow and the o?-ramp discharges will be the same as in the top of the ?gure; hence the total discharge will be higher by 196 ? 100 = 96 vph.

400

350

density in upstream section 1

300

250

k = 300
200

150

k = 600 k = 1200

100

50

k = 60 k = 12

0 0 50 100 150 200 250 300 350 400

density in downstream section 0
Fig. 12. Orbits of the infeasible demand example.

G. Gomes et al. / Transportation Research Part C 16 (2008) 485–513

503

3. Fig. 12 shows the phase portrait of the freeway considered in Fig. 6 except that the on-ramp ?ow in section 0 is increased to 1250 so that the demand becomes infeasible. The ?gure also displays the equilibrium set E?~f ?. All of the trajectories converge to the most congested equilibrium in E?~f ?. There is a pleasing symr r metry with the case of strictly feasible demand, in which every trajectory converges to the uncongested equilibrium as in Fig. 8. The next result places the example above in a general setting. The freeway structure is the same as in Sections 3–5. Let r = (r0, . . . , rN) be a demand vector. Let / be the solution of (49): /N ? rN ;  /i ? bi ?/i?1 ? ri ?; 0 6 i 6 N ? 1:

Suppose that r is infeasible, so that /i > Fi for some i. To simplify the notation we make two assumptions. First /0 > F0, and if r0 = 0 the demand becomes feasible. Second, if rN = 0 (zero in?ow from the upstream ramp) the demand again becomes feasible. Since /0 > F0, under demand r the entire freeway will become congested as in the example. Since with rN = 0 the demand is feasible, ~N ? maxfq P 0j the demand ?r0 ; . . . ; rN ?1 ; q? is feasibleg r is well-de?ned, i.e., ~N P 0. Since with r0 = 0 the demand is feasible, r ^0 ? maxfq P 0j the demand ?q; r1 ; . . . ; rN ? is feasibleg r is similarly well-de?ned. Theorem 6.1 ?57? ?56?

(i) ~N < rN is the largest upstream ?ow for which the demand ~ ? ?r0 ; . . . ; rN ?1 ; ~N ? is feasible. The correspondr r r ~ ing equilibrium ?ow / is ~ /N ? ~N ; r  ~ /i ? bi ?/i?1 ? ri ?; 0 6 i 6 N ? 1:

(ii) With demand r, under the no-metering strategy every trajectory converges to the (unique) most congested equilibrium ncon 2 E?~? corresponding to demand ~. Moreover, the queue nN(k) at the upstream ramp grows r r inde?nitely at the rate of ?rN ? ~N ? vehicles per period. r (iii) ^0 < r0 is the largest ?ow for which the demand ^ ? ?^0 ; r1 ; . . . ; rN ? is feasible. The corresponding equilibr r r ^ rium ?ow / is ^ /N ? rN ; ^  ^ /i ? bi ?/i?1 ? ri ?; 1 6 i 6 N ? 1; ^  ^ /0 ? b0 ?/1 ? ^0 ?: r

r Under the ramp metering strategy that reduces the on-ramp ?ow in section 0 from r0 to ^0 , every trajectory converges to some equilibrium in E?^?. The queue at the on-ramp in section 0 grows inde?nitely at the rate of r ?r0 ? ^0 ? vehicles per period. r (iv) Flows under the ramp metering strategy are larger throughout the freeway: ~ ^ /i < /i ; 1 6 i 6 N and ~ ^ /0 ? /0 ? F 0 :

Suppose bi > 0 for some i P 1, so that there is non-zero off-ramp ?ow in at least one section. Then the total discharge under the ramp metering strategy is strictly larger than under the no-metering strategy. Moreover, l? rN ? ~N r   ?1 ? ?b1 ; . . . ; bN ? > 1: r0 ? ^0 r ?58?

Proof. (i) follows from (56) and (49). Since the entire freeway becomes congested under r, every trajectory converges to ncon ?~? by (48) and, by (i), vehicles accumulate at the upstream ramp at the rate of ?rN ? ~N ? r r per period. This proves (ii).

504

G. Gomes et al. / Transportation Research Part C 16 (2008) 485–513

 To prove (iii) we solve (49) recursively for ~ and ^, setting bN ? 1, to get r r N ?1 X ~     r /i ? ?bi ; . . . ; bj ?rj ? ?bi ; . . . ; bN ?~N ; 0 6 i 6 N ? 1; j?i 8 PN ?1     > j?i ?bi ; . . . ; bj ?rj ? ?bi ; . . . ; bN ?rN ; 1 6 i 6 N ? 1; < ^ N ?1 P  /i ?     > b0^0 ? ?b0 ; . . . ; bj ?rj ? ?b0 ; . . . ; bN ?rN ; i ? 0: : r
j?1

?59?

?60?

~ ^ Since ~N < rN it follows from (59) and (60) that /i < /i ; 1 6 i 6 N . Also, since ^0 is the largest ?ow that keeps r r ^ ~ ^ 0 6 F 0 , it must be that /0 ? F 0 . Similarly /0 ? F 0 . Hence if bi > 0 for some i P 1, then b /i > b /i , i.e., the ^ ~ / i i off-ramp discharge under ramp metering is strictly larger in at least one section. Lastly, from (59) and (60), N ?1 X ~     r ?b0 ; . . . ; bj ?rj ? ?b0 ; . . . ; bN ?~N ; F 0 ? /0 ?
j?0

^  r F 0 ? /0 ? b0^0 ?

N ?1 X j?1

    ?b0 ; . . . ; bj ?rj ? ?b0 ; . . . ; bN ?rN ;

which, upon subtraction, gives    b0 ?r0 ? ^0 ? ? ?b0 ; . . . ; bN ??rN ? ~N ?; r r and so   r r r0 ? ^0 ? ?b1 ; . . . ; bN ??rN ? ~N ?;  which implies (58) because bi < 1 for at least one i. h Theorem 6.1 prompts some observations. 1. The discussion of infeasible demand above assumes that the on-ramp ?ow in a section takes priority over the ?ow from the upstream section: the latter cannot block an on-ramp ?ow, even if the section is congested. This priority is implicit in the treatment of ri(k) in (1). 2. The unserved demand under the ramp metering strategy is ?r0 ? ^0 ? vehicles per period; the unserved r demand under the no-metering strategy is ?rN ? ~N ?. By (58), the no-metering strategy magni?es the r   ?1 unserved demand under the ramp strategy by l ? ?b1 ; . . . ; bN ? . The larger are the split ratios, the larger is the ‘multiplier’ l, and worse is the no-metering strategy. (In the example of Fig. 11 l = (0.8 · 0.8 · 0.8)?1 % 2). ^ ~ 3. The ramp metering strategy increases speed in every section i (hence reduces travel time). Because /i > /i and the freeway is congested under the no-metering strategy, the fundamental diagram implies that the density ^i < ~i which, in turn, implies that the speed (=?ow/density) under ramp metering is higher: n n ^ n ~ n /i =^i > /i =~i . 4. Because of (58) the total travel time under the no-metering strategy grows arbitrarily larger than under the no-metering strategy. This contradicts the conclusion of Zhang et al. (1996) that the no-metering strategy minimizes total travel time ‘‘if tra?c is uniformly congested’’ as is the case when the demand is infeasible. There is no contradiction with a similar conclusion of Daganzo and Lin (1993) which considers the very  special case with no o?-ramps, so bi ? 1 for all i, and hence l = 1 in (58). The special case with one o?-ramp is graphically analyzed in Yperman et al. (2004) and Lago and Daganzo (2007). 5. An intuitive explanation of the increased o?-ramp discharge under the ramp metering strategy might be that the no-metering strategy creates a congestion ‘‘queue’’ that blocks the o?-ramps. This explanation is too crude. Note that under the ramp metering strategy, the system can converge to any equilibrium in E?^?, including the most congested equilibrium ncon ?^?, and under the no-metering strategy it converges r r to the most congested equilibrium ncon ?~?. Thus the entire freeway may be congested under both strategies. r Nevertheless, the ?ows in every section, and hence the o?-ramp ?ows, are larger under the ramp metering strategy. Thus a more accurate (but less intuitive) explanation is that the congestion queue under ramp metering ‘‘moves faster’’ than the queue under the no-metering strategy.

G. Gomes et al. / Transportation Research Part C 16 (2008) 485–513

505

While Theorem 6.1 is intuitively evident, the second implication of the theory is surprising: Theorem 6.2 says that ramp metering can reduce total travel time even when the demand is feasible. Fix a feasible (but not strictly feasible demand) r; let / be its equilibrium ?ow given by (49) and E(r) its equilibrium set. Recall that f(ne) = / for all ne 2 E(r). To simplify the notation we assume that under r the only bottleneck is section 0; hence /0 = F0, /i < Fi, 1 6 i 6 N ? 1, /N = rN 6 FN. Suppose the freeway is initially in a congested equilibrium n(0) = ne in which sections 0, . . . , j are congested for some j P 1, with ne ?0? ? ncon ; 0 6 i 6 j, and sections j + 1, . . . , N ? 1 are i i uncongested with ne ? nu ; i P j ? 1. For any p 2 R write nu 0 p 0 ne if i i nu < pi < ne ; 0 6 i 6 j; i i Lemma 6.1. If nu 0 p 0 ne, f0 ?p? ? /0 ? F 0 ; f i ?p? > /i ; 0 < i 6 j; Proof. First,   f0 ?p? ? minfb0 v0 p0 ; F 0 g P minfb0 v0 nu ; F 0 g ? /0 ? F 0 : 0  Next, for 0 < i 6 j evaluate the three terms in fi ?p? ? minfbi vi pi ; F i ? wi?1 ?i?1 ? pi?1 ?; F i g gives n u   fi ?p? ? bi vi pi > bi vi ni ? /i ; or ? F i ? wi?1 ?i?1 ? pi?1 ? > F i ? wi?1 ?i?1 ? ncon ? ? /i ; or n n i?1 ? F i > /i ; so fi(p) > /i. The last clause in (62) follows from nu ? pi ; i > j. h i We assume strictly positive demand in the congested sections, so q ? minfri ; 0 6 i 6 jg > 0: We construct a ramp metering strategy that selects the on-ramp ?ow values as follows:  ri ? li ?k?; 0 6 i 6 j; ri ?k? ? ri ; j < i 6 N ? 1: and f i ?p? ? /i ; i > j: ?62? and nu ? pi ? ne ; i > j: i i ?61? Lemma 6.1 re?nes Lemma 5.3(i).

?63?

(The {li} are speci?ed below in (67).) Denote by p(k), k P 0, the trajectory starting at p(0) = ne under the metering strategy (63). Lemma 6.2. There is a ?nite time horizon K and a metering strategy {li(k), k = 0, . . . , K} such that the resulting (controlled) trajectory p(k),k = 0, . . . , K, satis?es nu 0 p?k? 0 ne ; and p?K? ? nu :
e

k ? 1; . . . ; K ? 1;

?64? ?65?

In particular, the ramp metering strategy steers the state from the initial congested equilibrium n to the uncongested equilibrium nu. Proof. Set li(k)  0, i > j. Following (6), the controlled trajectory is given by  pi ?k ? 1? ? pi ?k? ? b?1 fi ?p?k? ? fi?1 ?p?k?? ? ri ? li ?k?; 0 6 i 6 N ? 1; k P 0: i

?66?

Observe that for i > j, pi ?0? ? ne ? nu and ri(k) = ri. Hence under any metering strategy of the form (63), i i pi ?k?  ne ; i > j. Thus the metering strategy affects the densities only in sections 0, . . . , j. i Rewrite (66) as pi ?k ? 1? ? gi ?p?k?? ? li ?k?; 0 6 i 6 N ? 1; k P 0;

506

G. Gomes et al. / Transportation Research Part C 16 (2008) 485–513

and de?ne the metering strategy by  q; if gi ?p?k?? P nu ? q; i li ?k? ? gi ?p?k?? ? nu ; if nu 6 gi ?p?k?? < nu ? q: i i i

?67?

Since ri ? li(k) P ri(k) ? q P 0, the metering strategy is feasible (on-ramp ?ows are non-negative). By construction of l, nu 0 p(k). By monotonicity, if p(k) 0 ne then p(k + 1) = g(p(k)) ? l(k) 0 g(ne) ? l(k), so (64) holds by induction. We now prove (65). Recall that  ri ? b?1 /i ? /i?1 ; i and substitute for ri in (66) to get  pi ?k ? 1? ? pi ?k? ? b?1 ?/i ? fi ?p?k?? ? ?/i?1 ? fi?1 ?p?k??? ? li ?k?; i Adding these equations gives
j X i?0 j X i?0 j X i?0 j X i?0

0 6 i 6 j:
j X i?0

pi ?k ? 1? ? ?

pi ?k? ? pi ?k? ?

 b?1 ?/i ? fi ?p?k?? ? i

?/i?1 ? fi?1 ?p?k??? ?
j X i?0

li ?k?

j X i?0

j X i?0

 ?b?1 ? 1??/i ? fi ?p?k?? ? i

 li ?k? ? b?1 ?/0 ? f0 ?p?k?? 0

? ?/j?1 ? fj?1 ?p?k??? ?
j X i?0

pi ?k? ?

j X i?0

 ?b?1 ? 1??/i ? fi ?p?k?? ? i

j X i?0

li ?k? < ?

j X i?0

li ?k?;

Pj because f0(p(k)) = /0 = F0, fj+1(p(k)) = /j+1 and /i ? fi(p(k)) < 0 by (62). Moreover, from (67), i?0 li ?k? P q P e for each k for which gi ?p?k? P nu ? q for some i. It follows that p(K) = nu for some K 6 ? i ?ni ? nu ??=q. h i i Theorem 6.2. Suppose the freeway begins in a congested equilibrium ne in which sections 0, . . . , j are congested and sections j + 1, . . . , N ? 1 are uncongested. Then there exists a ramp metering strategy over a ?nite horizon K at the end of which the freeway is in the uncongested equilibrium nu. Furthermore, the ?ows during k = 0, . . . , K are larger than the equilibrium ?ows. Finally, if the split ratio bi > 0 for some 0 6 i 6 j, then the total discharge ?ow is strictly larger and the total travel time is strictly smaller than in the no-metering strategy. Proof. By Lemma 6.2 in each section i the ?ow fi(p(k)) > /i for at least one k. Hence the difference in the total discharge
K X k?0

 bi b?1 ?fi ?p? ? /i ? > 0; i h

from which the assertion follows.

Two observations are worth making. 1. If the split ratios in the congested sections are all zero, bi = 0, i = 0, . . . , j, the ramp metering strategy does not increase the P discharge, but it moves the system to the uncongested equilibrium nu by ‘moving’ the total ‘excess’ vehicles j ?ne ? nu ? from the congested sections to their on-ramps. The resulting total travel time i i?0 i is unchanged but tra?c in the freeway moves at free ?ow speeds. If some of the tra?c in the queues is diverted to alternative routes, perhaps along arterials, there will be a decline in total travel time just as with non-zero split ratios. 2. There is another compelling reason for maintaining the freeway in free ?ow. The example of Fig. 6 illustrates a common situation in which the congestion density of 160 vehicles/mile (and speed of 30 mph) compares with the uncongested density of 80 vehicles/mile (and speed of 60 mph) for a three-lane freeway.

G. Gomes et al. / Transportation Research Part C 16 (2008) 485–513
congestion trajectory

507

n1

ncon decongestion trajectory

0

1
E nu

n0

Fig. 13. By creating the cycle from ncon ! nu ! ncon a ramp metering strategy can increase o?-ramp discharge.

Storing the 80 additional vehicles would require a 3/4 mile-long one-lane on-ramp (at 50 feet vehicle spacing). Clearly congestion causes the freeway to be used as a very expensive parking place. 3. A ‘free lunch’ result lurks behind Theorem 6.2. The result can be understood with the help of Fig. 13 of a two-section freeway whose equilibrium set E is shown on the right. By Lemma 6.2 the ?ow in section 1 is larger than the equilibrium ?ow in the rectangle {nu < p < ncon}. The ‘decongestion’ trajectory constructed in Lemma 6.2 moves the system from ncon to nu and causes some additional vehicles to leave the freeway from the o?-ramp in section 1. The remainder of the ??ncon ? nu ? ? ?ncon ? nu ?? vehicles causing the initial 1 1 0 0 congestion are ‘stored’ on the on-ramps in sections 0 and 1. Once the sections become uncongested, the ramp metering strategy can now be changed to release the stored vehicles onto the freeway, thereby creating the congestion and moving the state from nu to ncon as indicated by the ‘congestion’ trajectory in the ?gure. Since this trajectory is inside {nu < p < ncon} there will again be an additional o?-ramp ?ow. Repeating the two-phase decongestion–congestion cycle provides a free lunch.

7. Conclusions Despite the widespread use of the CTM model for simulation and analysis of problems in freeway planning and operations, theoretical understanding of the model is spotty. This paper ?lls this gap by providing a complete analysis of the behavior of the CTM model of a freeway with stationary demand. The key to the behavior is the location of bottlenecks—sections where ?ow equals capacity. The bottlenecks partition the freeway into ‘decoupled’ segments. Each segment starts with a bottleneck and ends just before the next upstream bottleneck. Each segment determines its own equilibrium set; and each equilibrium in the set determines the number of congested sections in the segment. It is characteristic of the CTM model that within each segment congested segments must lie immediately upstream of the bottleneck. Another characteristic is that congestion must propagate upstream from the bottleneck. Both characteristics are readily observed empirically (Chen et al., 2004; PeMS website, 2007). Of course, as a consequence, as a segment becomes uncongested, upstream sections are relieved before downstream sections. Bottlenecks may be caused by physical features that reduce capacity. More often, however, bottlenecks depend on the pattern of demand. As the pattern of demand changes by time of day and day of week, bottleneck locations change as well. This characteristic, too, is widely observed. One surprising conclusion of the analysis is that depending on initial conditions, the same demand may leave a segment uncongested or it may congest one or more sections, or even the entire segment. Thus congestion is not a sign that capacity exceeds demand, as is commonly believed. If, however, the demand does exceed capacity in a segment the entire segment will become congested. If ramps are not metered when there is excess demand, freeway utilization will drop and congestion deepen, in comparison with conditions that would prevail under an appropriate ramp metering strategy. When there is excess demand, which typically occurs in every rush hour, proper ramp metering always reduces total travel time because of larger discharge ?ows, and increases ?ow and freeway speed. It is a false belief that metering merely transfers delay from a congested freeway to queuing delay on the ramp (except in the singular case of a freeway in which everyone gets o? at the same exit).

508

G. Gomes et al. / Transportation Research Part C 16 (2008) 485–513

Surprisingly, even when there is no excess demand, ramp metering can eliminate congestion and reduce total travel time. Thus the most important practical conclusion of the analysis is that the presence of sustained congestion is a sure indication of the wastefulness of freeway capacity and of travelers’ time. Appropriate ramp metering can eliminate this waste. The bene?t of ramp metering reported here may underestimate the true bene?t if there is a capacity drop in a section when density exceeds its critical value. Acknowledgements The authors thank Tarek Hatata, Alex Skabardonis, Fred Dial, Pat Weston and John Wolf for their critical encouragement. This paper is a report of the TOPL (Tools for Operations Planning) Development Group, whose work is supported by the California Department of Transportation through the California PATH Program. Appendix Proof of Lemma 5.1. Suppose x 6 y. We must show gi ?xi?1 ; xi ; xi?1 ? 6 gi ?y i?1 ; y i ; y i?1 ?: ?68?

We verify the inequality one coordinate at a time. Suppose ?rst that xi?1 6 yi?1 but xi = yi, xi+1 = yi+1. Then from (6) and (7) gi ?xi?1 ; xi ; xi?1 ? ? gi ?y i?1 ; y i ; y i?1 ?   ? ?b?1 minfbi vi xi ; wi?1 ?i?1 ? xi?1 ?; F i g n
i

  ? b?1 minfbi vi y i ; wi?1 ?i?1 ? xi?1 ?; F i g 6 0: n i Suppose next that xi+1 6 yi+1 but xi?1 = yi?1,xi = yi. Then from (6) and (7) gi ?xi?1 ; xi ; xi?1 ? ? gi ?y i?1 ; y i ; y i?1 ?   ? b?1 minfbi?1 vi?1 xi?1 ; wi ?i ? xi ?; F i?1 g n
i?1  ? b?1 i?1

 minfbi?1 vi?1 y i?1 ; wi ?i ? xi ?; F i?1 g 6 0: n

Lastly suppose xi 6 yi but xi?1 = yi?1, xi+1 = yi+1. To show (68) consider three separate cases. Case 1: xi < y i 6 nc . Then from (6), (7) and (11) i gi ?xi?1 ; xi ; xi?1 ? ? gi ?y i?1 ; y i ; y i?1 ?     n n ? xi ? b?1 minfbi vi xi ; wi?1 ?i?1 ? xi?1 ?; F i g ? y i ? b?1 minfbi vi y i ; wi?1 ?i?1 ? xi?1 ?; F i g i i (   ? xi ? y i if bi vi xi P minfbi vi xi ; wi?1 ?i?1 ? xi?1 ?; F i g n   n 6 ?1 ? vi ?xi ? ?1 ? vi ?y if bi vi xi ? minfbi vi xi ; wi?1 ?i?1 ? xi?1 ?; F i g
i

6 0; because 0 < vi < 1: Case 2: xi 6 nc < y i . Then from (6), (7) and (11) i gi ?xi?1 ; xi ; xi?1 ? ? gi ?y i?1 ; y i ; y i?1 ?    ? xi ? b?1 minfbi vi xi ; wi?1 ?i?1 ? xi?1 ?; F i g ? minfbi?1 vi?1 xi?1 ; wi ?i ? xi ?; F i g n n
i

   ? y i ? b?1 minfbi vi y i ; wi?1 ?i?1 ? xi?1 ?; F i g ? minfbi?1 vi?1 xi?1 ; wi ?i ? y i ?; F i g n n i

G. Gomes et al. / Transportation Research Part C 16 (2008) 485–513

509

  If bi vi xi P minfbi vi xi ; wi?1 ?i?1 ? xi?1 ?; F i g, n gi ?xi?1 ; xi ; xi?1 ? ? gi ?y i?1 ; y i ; y i?1 ?   n n ? xi ? y i ? minfbi?1 vi?1 xi?1 ; wi ?i ? xi ?; F i g ? minfbi?1 vi?1 xi?1 ; wi ?i ? y i ?; F i g  i?1 vi?1 xi?1 ; F i g 6 xi ? y i 6 0 if wi ?i ? xi ? 6 minfb n  n ? ?1 ? wi ??xi ? y i ? 6 0; if wi ?i ? xi ? ? minfbi?1 vi?1 xi?1 ; F i g; because 0 < vi < 1;   n and if bi vi xi < minfbi vi xi ; wi?1 ?i?1 ? xi?1 ?; F i g, gi ?xi?1 ; xi ; xi?1 ? ? gi ?y i?1 ; y i ; y i?1 ?   6 xi ? y i ? minfbi?1 vi?1 xi?1 ; wi ?i ? xi ?; F i g ? minfbi?1 vi?1 xi?1 ; wi ?i ? y i ?; F i g 6 0; as before: n n Case 3: nc 6 xi < y i 6 nc . Then from (6), (7) and (11) i i gi ?xi?1 ; xi ; xi?1 ? ? gi ?y i?1 ; y i ; y i?1 ?   n n ? xi ? y i ? minfbi?1 vi?1 xi?1 ; wi ?i ? xi ?g ? minfbi?1 vi?1 xi?1 ; wi ?i ? y i ?g  i?1 vi?1 xi?1 n ? xi ? y i 6 0; if wi ?i ? y i ? > b  6 ?1 ? wi ??xi ? y i ? 6 0; if wi ?i ? y i ? 6 bi?1 vi?1 xi?1 ; because 0 < vi < 1: n Thus g is strictly monotone, because if x 6 y, gi ?xi?1 ; xi ; xi?1 ? 6 gi ?y i?1 ; xi ; xi?1 ? 6 gi ?y i?1 ; y i ; xi?1 ? 6 gi ?y i?1 ; y i ; y i?1 ?; moreover, it is trivial to check that if x 5 y then g(x) 5 g(y). Lastly g is not strongly monotone, because if x < y but xi?1 = yi?1, xi = yi, xi+1 = yi+1, then gi(x) = gi(y). h Proof of Lemma 5.6. Suppose, as induction hypothesis, that (54) holds for m ? 1P0. Fix m P 1. By Theorem 4.1 ne;m 2 Emm ?j ?r? for some j P 0, so that at ne,m sections Im, . . . , Im + j are congested and sections I Im + j + 1, . . . , Im+1 ? 1 are not congested as in Fig. 10. We will prove (54) for m, separately analyzing the three cases: j = Im+1 ? 1, j = Im, and Im < j < Im+1 ? 1. Case (i): j = Im+1 ? 1. In this case at ne,m the entire segment Sm is congested. The induction hypothesis is not used for this case.By Theorem 4.1 ne,m = ncon,m and, by (31), ne;m ? nc ? w?1 ?F i?1 ? /i?1 ? > nc ; i i i i i 2 Sm: ?69?

By (52) for g > 0 we can select d > 0 so that jnm ? ne;m j < d ) 0 6 F I m ? fI m ?k? ? g?k? < g: Assume for now that nm ?k? > nc ; i i so that  fi ?k? ? minfbi vi nm ?k?; F i ? wi?1 ?nm ?k? ? nc ?; F i g i i?1 i?1 ? F i ? wi?1 ?nm ?k? ? nc ?; i?1 i?1 i ? I m ? 1; . . . ; I m?1 : ?72? Substituting (69), (70), (72) and (49) in   nm ?k ? 1? ? nm ?k? ? b?1 fi ?k? ? fi?1 ?k? ? ri ? nm ?k? ? b?1 ?fi ?k? ? /i ? ? fi?1 ?k? ? /i?1 ; i i i i i k P 0; i 2 S m ; ?71? ?70?

510

G. Gomes et al. / Transportation Research Part C 16 (2008) 485–513

gives, for i = Im,  nm ?k ? 1? ? nm ?k? ? b?1 ?F I m ? g?k? ? /i ? ? F i?1 ? wi ?nm ?k? ? nc ? ? /i?1 i i i i i m m c ?1 ?1 g?k?; as F I ? / ? ni ?k? ? wi ?ni ?k? ? ni ? wi ?F i?1 ? /i?1 ?? ? bi Im m e;m m m ?1 g?k?; ? n ?k? ? wi ?n ?k? ? n ? ? b
i i i i

?73?

and, for i = Im + 1, . . . , Im+1 ? 1,  nm ?k ? 1? ? nm ?k? ? b?1 ?F i ? wi?1 ?nm ?k? ? nc ? ? /i ? ? F i?1 ? wi ?nm ?k? ? nc ? ? /i?1 i i i i?1 i?1 i i  ? nm ?k? ? b?1 wi ?nm ?k? ? nc ? w?1 ?F i ? / ?? ? wi ?nm ?k? ? nc ? w?1 ?F i?1 ? /
i i i?1 i?1 ??

?

nm ?k? i

?

 b?1 wi?1 ?nm ?k? i i

?

i?1 ne;m ? i

i

i

i

i

i

?

wi ?nm ?k? i

?

nie;m ?:

?74?

De?ne the vectors xm(k) with components xm ?k? ? nm ?k? ? ne;m ; i 2 S m . In terms of xm(k) the difference Eqs. i i i (73) and (74) can be written as 3 3 2 ?1 2 1 ? wI m 0 0 ... 0 bI m g?k? 7 7 6 6 ?1 7 7 6 6 bI ?1 wI m 1 ? wI m ?1 0 ... 0 0 7 7 m 6 6 m m ?75? x ?k ? 1? ? 6 7: 7x ?k? ? 6 7 7 6 6 ? ? ? ? ? ? 5 5 4 4 0 ? ? b?1 wI m?1 ?2 I m?1 1 ? wI m?1 ?1 0 The di?erence Eq. (75) is of the form xm ?k ? 1? ? Axm ?k? ? u?k?; and has the solution xm ?k? ? Ak ?nm ? ne;m ? ?
k?1 X l?0

xm ?0? ? nm ? ne;m ;

Ak?1?l u?l?:

The eigenvalues of A are ?1 ? wI m ?; . . . ; ?1 ? wI m?1 ?1 ?, all of which lie in (0, 1), since 0 < wi < 1. Hence  kAk k 6 Mkk for some M < 1 and 0 < k < 1. Also j u?l? j6 ?bI m ??1 g. It follows that if jnm ? ne,mj < d, suf?m ciently small, then (71) holds and jx (k)j 6  for all k P 0. Case (ii): j = Im. In this case sections j + 1 = Im + 1, . . . , Im+1 ? 1 are not congested; so /j = Fj, /i < Fi, i > j, i 2 Sm. By the induction hypothesis, for  > 0 there is d > 0 such that for jn ? nej < d, there is an equilibrium ne such that ? jnm?1 ?k? ? ~e;m?1 j < ; n By Proposition 4.3, ~j?1 ne;m?1 k P 0:

< nc ; hence, for  > 0 small j?1 ?76?

nm?1 ?k? < ~e;m?1 ?  < nc : nj?1 j?1 j?1 Next, by (52) we can select d > 0 so that jn ? ne j < d ) 0 6 F I m ?1 ? fI m ?1 ?k? ? g?k? ! 0: By Lemma 4.3, n has the form (see bottom part of Fig. 3) ( c nj ? ?1 ? 2w?w?1 ?F j?1 ? /j?1 ?; i ? j; for some 0 6 w 6 1=2; j e;m ni ? u i vi ??1 / < nc ; i P j ? 1; i 2 S m : ni ? ? b i i We now examine the trajectory {n(k)} starting at n. Assume for now that nm ?k? < ne;m ? ww?1 ?F j?1 ? /j?1 ? ? nc ? ?1 ? w?w?1 ?F j?1 ? /j?1 ?; j j j j j e;m m i vi ??1 ?nc ? ne;m ?; i P j ? 1; i 2 S m : n ?k? < n ? w?b
i i i i

?77?

e,m

?78? ?79?

G. Gomes et al. / Transportation Research Part C 16 (2008) 485–513

511

From (76) and (78) m?1  fj ?k? ? minfbj vj nm ?k?; F j ? wj?1 ?nj?1 ?k? ? nc ?; F j g j j?1 ( m F j ; if nj ?k? > nc j  ? minfbj vj nm ?k?; F j g ?  : j m m bj vj nj ?k?; if nj ?k? 6 nc j Next,  fj?1 ?k? ? minfbj?1 vj?1 nm ?k?; F j?1 ? wj ?nm ?k? ? nc ?; F j?1 g: j?1 j j From (79),
?1 e;m    bj?1 vj?1 nm ?k? < bj?1 vj?1 ?ne;m ? w?bj?1 vj?1 ? ?nc ? nj?1 ?? ? /j?1 ? w?F j?1 ? /j?1 ?; j?1 j?1 j?1

?80?

?81?

and from (78) F j?1 ? wj ?nm ?k? ? nc ? P F j?1 ? wj ??1 ? w?w?1 ?F j?1 ? /j?1 ?? ? wF j?1 ? ?1 ? w?/j?1 : j j j Substituting the preceding two inequalities into (81) gives  fj?1 ?k? ? bj?1 vj?1 nm ?k?:
j?1

?82?

Lastly, for i P j + 2, i 2 S , from (79)   fi ?m? ? minfbi vi nm ?k?; F i ? wi?1 ?nm ?k? ? nc ; F i g ? bi vi nm ?k?: i i?1 i?1 i Substituting (80), (82), (83) and (49) in   nm ?k ? 1? ? nm ?k? ? b?1 fi ?k? ? fi?1 ?k? ? ri ? nm ?k? ? b?1 ?fi ?k? ? /i ? ? ?fi?1 ?k? ? /i?1 ?; i i i i i gives the di?erence equation system for {nm(k)}: e;m     nm ?k ? 1? ? nm ?k? ? b?1 ?minfbj vj nm ?k?; F j g ? bj vj nj ? ? bj?1 vj?1 ?nm ?k? ? ne;m ?k?? j?1 j j j j j?1 e;m m m m i?1 vi?1 ?nm ? ne;m ?; i ? j ? 1; . . . ; I m?1 ? 2 n ?k ? 1? ? n ?k? ? vi ?n ?k? ? n ?k?? ? b
i nmm?1 ?1 ?k I i

m

?83?

? 1? ?

i m nI m?1 ?1 ?k?

i

?

vI m?1 ?1 ?k??nmm?1 ?1 ?k? I nm ?k? i ? ne;m ; i i

i?1 i?1 e;m ? nI m?1 ?1 ?k?? m

? g?k?:

In terms of the variables
j j

P j; i 2 S , this system can be rewritten as     xm ?k ? 1? ? xm ?k? ? b?1 ?minfbj vj nm ?k?; F j g ? bj vj ne;m ? ? bj?1 vj?1 xm ?k?
j j j j?1

xm ?k? i

?

?84? 3 ?85?

and 2 xj?1 ?k ? 1? 3 2 1 ? vj?1 0 ? 0  bj?2 vj?2 1 ? vj?2 ? ? 0  bj?3 vj?3 ? ? ... ... ? 0 0 0 ? 32 xj?1 ?k? 3 2 6 xj?2 ?k ? 1? 6 6 4 ? xI m?1 ?1 ?k ? 1? z?k ? 1? ? Az?k? ? bg?k?; and has the solution z?k? ? Ak z?0? ?
k?1 X l?0

7 6 7 6 7?6 5 4

7 76 xj?2 ?k? 7 6 7 76 7 6 7: 76 7?6 54 5 4 ? 5 ? xI m?1 ?1 ?k? ?g?k? 1 ? vI m?1 ?1

0 0

The di?erence Eq. (85) is of the form

Ak?1?l bg?l?:

The eigenvalues of A are ?1 ? vj?1 ?; . . . ; ?1 ? vI m?1 ?1 ?, all of which lie in (0, 1), since 0 < vi < 1. By (77), g(l) ! 0, g(l) P 0. Hence z(k) ! z* 6 0, and (79) is assured by induction. Furthermore, because g(l) P 0, xm ?k? 6 Mkk ; j?1 for some M < 1 and 0 < k < 1. ?86?

512

G. Gomes et al. / Transportation Research Part C 16 (2008) 485–513

Lastly, rewrite (84) as (  ?1 ? vj ?xm ? bj?1 vj?1 xm ?k?; j j?1 xm ?k ? 1? ? j m j?1 vj?1 xm ?k?; x ?k? ? D ? b
j j?1

if xm 6 ?D; j if xm P ?D; j

?87?

in which D ? ?1 ? 2w?w?1 ?F j?1 ? /j?1 ?. j Because D > 0 and xm ! 0, the second alternative in (87) cannot hold for k P K, for some ?nite K, and so j?1 xm ?k? ? ?1 ? vj ? j
k?K m xj ?K?

?

k?1 X l?K

?1 ? vj ?

k?1?l 

bj?1 vj?1 xm ?l?; j?1

can be made arbitrarily small, proving (78). Case (iii): Im < j < Im+1 ? 1. In this case at ne,m sections Im, . . . ,j are congested and sections j + 1, . . . ,Im+1 ? 1 are uncongested. The proof for this case combines the argument in Case (i) for the congested sections and the argument in Case (ii) for the uncongested sections. The details are omitted. h

References
Almasri, E., Friedrich, B., 2005. Online O?set Optimisation in Urban Networks Based on Cell Transmission Model. ITS Hanover. Aw, A., Rascle, M., 2000. Resurrection of ‘second order’ models of tra?c ?ow. SIAM Journal on Applied Mathematics 63 (1), 916–938. Buisson, C., Lebacque, J.-P., Lesort, J.B., 1996a. STRADA, a discretized macroscopic model of vehicular tra?c ?ow in complex networks based on the Godunov scheme. In: CESA’96 IMACS Multiconference. Buisson, C., Lebacque, J.-P., Lesort, J.B., Mongeot, H., 1996b. The STRADA dynamic assignment model. In: Proceedings of the 1996 ITS Conference. Chen, C., Skabardonis, A., Varaiya, P., 2004. Systematic identi?cation of freeway bottlenecks. Transportation Research Record 1867, 46– 52. Daganzo, C., 1994. The cell transmission model: a dynamic representation of highway tra?c consistent with the hydrodynamic theory. Transportation Research, Part B 28 (4), 269–287. Daganzo, C., 1995. Requiem for second-order ?uid approximations of tra?c ?ow. Transportation Research Part B 29, 277–286. Daganzo, C.F., Lin, W.-H., 1993. The spatial evolution of queues during the morning commute in a single corridor. Working Paper UCBITS-PWP-93-7, California PATH, University of California, Berkeley, CA 94720. Godlewski, E., Raviart, P.-A., 1996. Numerical Approximation of Hyperbolic Systems of Conservation Laws. Springer-Verlag. Godunov, S., 1959. A di?erence method for numerical calculation of discontinuous solutions of hydrodynamic equations. Matematicheskii Sbornik 47, 271–290. Gomes, G., 2004. Optimization and microsimulation of on-ramp metering for congested freeways. Ph.D. Thesis, University of California, Department of Mechanical Engineering, Berkeley, CA. Gomes, G., Horowitz, R., 2006. Optimal freeway ramp metering using the asymmetric cell transmission model. Transportation Research, Part C 14 (4), 244–262. Haut, B., Bastin, G., 2005. A second order model for road tra?c networks. In: Proceedings of the IEEE Intelligent Transportation Systems Conference, pp. 178–184. Helbing, D., 1995. Improved ?uid dynamic model for vehicular tra?c. Physical Review E, 3164–3169. Herty, M., Rascle, M., 2006. Coupling conditions for a class of second order models for tra?c ?ow. SIAM Journal on Mathematical Analysis 38 (2), 595–616. Hirsch, M.W., Smith, H., 2005. Monotone maps: a review. Journal of Di?erence Equations and Applications 11 (4–5), 379–398. Also <http://repositories.cdlib.org/postprints/977/>. Lago, A., Daganzo, C.F., 2007. Spillovers, merging tra?c and the morning commute. Transportation Research Part B 41, 670–683. Lebacque, J.P., 1996. The Godunov scheme and what it means for ?rst order tra?c ?ow models. In: Lesort, J.B. (Ed.), Proceedings of the 13th International Symposium on Transportation and Tra?c Theory. Pergamon, pp. 647–677. Leclercq, L., Laval, J., Chevallier, E., 2005. The Lagrangian coordinates and what it means for ?rst order tra?c ?ow models. In: Allsop, B.R., Bell, M.G.H., Heydecker (Eds.), Proceedings of the 17th International Symposium on Transportation and Tra?c Theory. Elsevier. LeVeque, R.J., 1992. Numerical Methods for Conservation Laws. Birkhauser. ¨ Lighthill, M., Whitham, G., 1955. On kinematic waves I: Flow movement in long rivers. II: A theory of tra?c ?ow on long crowded roads. Proceedings of the Royal Society of London, Part A 229 (1178), 281–345. Lin, W.-H., Ahanotu, D., 1995. Validating the Basic Cell Transmission Model on a Single Freeway Link. Technical Note 95-03, California PATH, University of California, Berkeley, CA 94720. Lo, H.K., 2001. A cell-based tra?c control formulation: strategies and bene?ts of dynamic timing plans. Transportation Science 35 (2), 148–164.

G. Gomes et al. / Transportation Research Part C 16 (2008) 485–513

513

May, A.D., 1981. Models for freeway corridor analysis. Technical report. Transportation Research Special Report 194. Munoz, L., Sun, X., Sun, D., Gomes, G., Horowitz, R., 2004. Methodological calibration of the cell transmission model. In: Proceedings of American Control Conference, pp. 798–803. Papageorgiou, M., Blosseville, J.-M., Hadj-Salem, H., 1990. Modelling and real-time control of tra?c ?ow on the southern part of Boulevard Peripherique in Paris. I: Modelling. II: Coordinated on-ramp metering. Transportation Research, Part A 24A (5), 345–370. Payne, H., 1971. Models of freeway tra?c and control. Mathematical Models of Public Systems 28 (1), 51–61. Payne, H., 1979. FREEFLO: A macroscopic simulation model of freeway tra?c. Transportation Research Record 722, 68–77. PeMS. PeMS website, 2007. <http://pems.eecs.berkeley.edu> (accessed 8/28/2007). Piccoli, B., Garavello, M., 2006. Tra?c Flow on Networks. American Institute of Mathematical Sciences. Richards, P., 1956. Shock waves on the highway. Operations Research 4 (1), 42–51. Whitham, G.B., 1974. Linear and Nonlinear Waves. Wiley-Interscience. Yperman, I., Logghe, S., Immers, B., 2004. Dynamic congestion pricing in a network with queue spillover. <http://www.kuleuven.be/ tra?c/stats/>. Zhang, 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. Ziliaskopoulos, A.K., 2000. A linear programming model for the single destination system optimum dynamic tra?c assignment problem. Transportation Science 34 (1), 37–49.


相关文章:
更多相关标签: