Netw Spat Econ DOI 10.1007/s11067-014-9234-x

A Continuous DUE Algorithm Using the Link Transmission Model N. Nezamuddin · Stephen D. Boyles

© Springer Science+Business Media New York 2014

Abstract This paper describes a continuous-flow, continuous-time model for which a dynamic Wardrop equilibrium provably exists. This formulation is general, but is particularly designed to include the link and node models of Yperman’s Link Transmission Model as a special case. Rather than using path flows to describe route choice, travelers are aggregated by destination and node-specific routing parameters are used to reduce the number of control variables needed. Furthermore, this formulation allows efficient solution methods from static traffic assignment, such as Linear User Cost Equilibrium (LUCE), to be applied in a fairly straightforward manner. Demonstrations on a small network verify the effectiveness of this dynamic LUCE algorithm in our model, showing favorable performance comapred to the method of successive averages. Keywords Link transmission model · Newton-based algorithm · Continuous flow model

1 Introduction Despite several decades of active research and growing acceptance among practitioners, dynamic traffic assignment (DTA) models have yet to reach their full potential in transforming traffic assignment in the field. While explicitly representing the timedependent nature of travel demand and congested behavior can model important

N. Nezamuddin Department of Civil Engineering, Valparaiso University, Valparaiso, IN 46383, USA S. D. Boyles () Department of Civil, Architectural & Environmental Engineering, The University of Texas at Austin, 301 E. Dean Keeton St. Stop C1761, Austin, TX 78712, USA e-mail: [email protected]

N. Nezamuddin, S.D. Boyles

phenomena more accurately, including traffic control and queue spillbacks, doing so introduces a host of additional modeling difficulties not present in static models. Broadly speaking, two major difficulties concern the nature of the traffic flow model employed, and the nature of dynamic equilibrium itself. These are briefly explained below; readers seeking additional detail can consult Peeta and Ziliaskopoulos (2001) for a more thorough review of DTA approaches. These difficulties can be highlighted by comparing approaches which have been developed to date. The first class of DTA models was based on analytic representation of link delay using “exit functions” (Merchant and Nemhauser 1978a, b). While such functions lend themselves to convergence analysis, properly enforcing first-in firstout (FIFO) discipline results in nonconvex constraints (Carey 1992) which form an obstacle to large-scale application. Another class of DTA formulations attempts to simplify a traffic-flow model so that it can scale tractably to large-scale systems; such efforts often approximate the hydrodynamic model of Lighthill and Whitham (1955) by introducing a piecewise-linear flow-density diagram, and applying a space-time discretization to form the cell-transmission model (Daganzo 1994, 1995), or methods based on cumulative counts (Newell 1993a, b, c), as in the link transmission model (LTM) (Yperman 2007). Questions have been raised about whether discretization should be spatial or trajectory-based (Bar-Gera 2005), or how to ensure consistency between link and path models (Blumberg and Bar-Gera 2009), or whether certain stochastic or adaptive features should be modeled (Qian and Zhang 2013, Waller et al. 2013). These issues are further compounded when questions of traffic control arise, including signals, roundabouts, or stop-controlled junctions. In all cases, a tension exists between accuracy and tractability, and the lack of consensus among researchers likely hinders adoption of DTA in practice. The second, more subtle difficulty is central to the definition of dynamic equilibrium. Many practical DTA packages employ a mesoscopic simulator to represent traffic flow, in which individual vehicles are propagated through the network. From a mathematical standpoint, these models are discontinuous in the representation of vehicles, and often discontinuous in the representation of traffic control as well (in the case of signals, for instance). In such cases, it is not difficult to produce examples where no dynamic equilibrium exists. Even when continuous models are employed, the equilibrium solution need not be unique (see, for instance Nie 2010). These may seem to be technical issues more than practical ones, but are in fact fundamental to the application and interpretation of DTA models in practice—if multiple equilibria exist, or no equilibria, then what should planners design for? This paper describes a continuous-vehicle, continuous-time dynamic equilibrium formulation which addresses these issues. The corresponding traffic flow model is relatively general; for concreteness the demonstrations in this paper use the link transmission model (LTM) developed by Yperman (2007) and further developed by Gentile (2010) and others. The LTM is amenable to representing traffic control, building on established results from traffic operations, such as the Highway Capacity Manual. In particular, continuity can be provided by representing average delay due to traffic control, rather than explicitly simulating gap acceptance and signal control. This reduces computational delay and, as Yperman (2007) argues, travelers presumably base route choice on average control delay anyway, so the loss of “accuracy” is

A Continuous DUE Algorithm Using the Link Transmission Model

negligible. Continuous vehicle flows are addressed by using node routing parameters, avoiding path enumeration and aggregating travelers by destination. The underlying traffic flow model implicitly maintains first-in first-out (FIFO) discipline and vehicles are assigned to user optimal paths based on their experienced path travel times. Equilibrium-seeking DTA models have to necessarily take into account travelers’ experienced travel time, rather than instantaneous travel time, to be consistent with their route-choice behavior learned in the network over a long period of time (Chiu et al. 2010). This model forms the main contribution of the paper. Its prime advantages are that it (1) uses continuous flows (and thus equilibrium can be assured) while (2) simultaneously introducing node routing parameters (obviating the need to enumerate paths), (3) enables derivative calculations to improve the speed of convergence to equilibrium; and (4) its node models are flexible and can admit a variety of traffic control. Section 2 presents the model and associated notation, and Section 3 defines and proves existence of at least one dynamic Wardrop equilibrium using a fixed-point theorem. Section 4 give two potential solution methods, the well-known method of successive averages, and a method resembling the LUCE algorithm from static traffic assignment, utilizing derivative information from the flow model. These methods are demonstrated on two networks in Section 5 before conclusions are given in Section 6. In these regards, the continuous DUE model presented differs from the earlier continuous DTA models, which typically use optimal control theory or variational inequalities. The DTA models using optimal control theory assign vehicles to paths based on instantaneous path travel times (Friesz et al. 1989, Wie 1991, Ran et al. 1993, Ban et al. 2012), implying that link travel times are invariant during the course of a vehicles journey. The quasi-continuous DTA model developed by Janson and Robles (1995) also falls into this class of DTA models using instantaneous travel times. The other class of continuous DTA models uses variational inequalities (Friesz et al. 1993, Ran and Boyce 1996, Ran et al. 1996, Bliemer and Bovy 2003, Ban et al. 2008) and differential variational inequalities (Friesz et al. 2011, 2013) to recognize the time-varying nature of link travel times. While such models assign demand based on vehicles experienced travel times, the propagation of traffic using link exit functions is limited in its representation of the queue spillback phenomenon, which is critical to dynamic modeling of congested networks. Another continuous DTA model developed by Mounce (2006) uses deterministic queues at link exits to model conditions when flow exceeds capacity. However, this model is only applicable to networks with a single bottleneck per route, which severely limits its application to congested urban traffic network. The continuous DUE model presented in this paper uses experienced path travel times and does not require the use of exit functions. Certain aspects of this model, such as avoiding path enumeration (by using node routing parameters), have been used by earlier researchers. Obviating path enumeration is achieved by using either arc-based formulations (Ran and Boyce 1996, 2012; Wie et al. 2002; Ban et al. 2008) or node routing parameters (Long et al. 2011) However this paper is unique in its calculation and use of travel time derivatives to speed convergence, and in its formulation of equilibrium as a fixed point rather than as a variational inequality.

N. Nezamuddin, S.D. Boyles

2 Notation and Model Let the network G = (N, A, Z) have node set N, link set A, and zone set Z. Let M denote the set of turning movements {(i, j, k) : (i, j ) ∈ A, (j, k) ∈ A}. Not all potential turning movements need exist in the set M; only those permissible for use by travelers need be included. Turning movements are used to represent control delay and capacity restrictions at intersections; links are used to represent delay and flow restrictions which do not occur at intersections. Let T = [0, T ] denote the temporal modeling period. For each origin r and destination s, d rs (t) denotes the rate of demand for travel between these zones at time t. The fundamental state variables are given by the flow at the upstream and down↑ ↓ stream ends of each link (qij (t) and qij (t), respectively) and turning movement ↑

↓

(qij k (t) and qij k (t)). These are supplemented by auxiliary state variables xij (t) and xijk (t) denoting exogenous parameters relevant to the traffic-flow model, such as free-flow times and capacities. The history of the system can beconveniently rept resented using cumulative vehicle counts of the form N(t) = 0 q(t  )dt  defined identically for the upstream and downstream ends of links and turning movements; the full history N[ti , tj ) represents the graph of the mapping N on the half-open interval [ti , tj ) ⊂ T , that is, N[ti , tj ) = {(t, n) : t ∈ [ti , tj ), n = N(t)}. Rather than representing route choice with an explicit path enumeration, travelers are aggregated by destination and their route choices represented by routing parameters φijs k (t) representing the proportion of travelers who arrive at node j from link (i, j ) at time t destined for zone s who choose to leave by link (j, k). A destinationbased approach is logical for the following reason: when a traveler arrives at a node, he or she must choose which turning movement to take. Travelers heading for different destinations make this choice based on different criteria (the travel time to their destinations will in general be different on each turning movement). However, travelers heading for the same destination choose turning movements using the same information (the travel times to the common destination), and so they can be meaningfully aggregated. This dramatically reduces the number of control variables required to represent all feasible route choices, without eliminating any potential equilibria. This equivalence is discussed in more detail following the presentation of the remainder of the flow model. The flow variables, cumulative counts, and full histories are disaggregated by des↑s tination; thus the full state of a link is given by Sij (t) = {xij (t), ×s∈Z (Nij [0, t), ↓s

Nij [0, t))}. Likewise, the full state of a node j is Sj (t) = {×(i,j,k)∈M (xijk (t), ↑s

↓s

×s∈Z (Nij k [0, t), Nij k [0, t)))} and the system evolution is governed by ↑s

↓s

qij k (t) = φijs k (t)qij  ↑s ↓s qij k qij (t) =

∀(i, j, k) ∈ M

(1)

∀(i, j ) ∈ A

(2)

(h,i,j )∈M ↓s

↑s

∀(i, j, k) ∈ M

(3)

↓s

↓s

∀(i, j ) ∈ A

(4)

qij k (t) = fj k (Sj (t), Sj k (t)) qij (t) = fij (Sj (t), Sij (t))

A Continuous DUE Algorithm Using the Link Transmission Model

where f ↑ and f ↓ represent the flow propagation functions at the upstream and downstream ends of the links; the upstream functions include the role of the upstream intersection. These four equations can be explained as follows; the reader may find it useful to consult Fig. 1 for a graphical depiction. Eq. 1 splits flow arriving at a node according to the proportions φ; note the disaggregation by destination. Conversely, Eq. 2 gathers flow leaving a node onto a particular arc from all corresponding turn movements. The two Eqs. 3 and 4 are the most interesting in the sense that these can distinguish one flow model from another. Equation 3 defines the rate at which vehicles exit turning movement (i, j, k), which can depend on the nature of the traffic control corresponding to this movement, the state of the node (for instance, the volume on conflicting movements), and the state of the downstream link (for instance, if the entire link is congested and no flow may enter). Equation 4 defines the rate at which vehicles exit a link to be split onto turning movements, as a function of the link parameters (such as capacity) and the state of the downstream node j . Origins and destinations can be handled in this framework without loss of generality by introducing additional turning movements. Trips originating at origin r begin at the downstream end of an artificial arc with r as its head whose downstream flows ↓s qir are given by the trip table, essentially forming a boundary condition. Likewise,

Fig. 1 Distinction between links and turning movements, and location where each equation acts. Note that not all turning movements are permissible

N. Nezamuddin, S.D. Boyles

upon arrival at a destination, trips are all routed onto an artificial turning movement with infinite capacity. The link transmission model developed by Yperman (2007) can be seen as a special case of the framework (1)–(4). The correspondence is as follows: assume that traffic flow on each link is governed by a triangular fundamental diagram of the form in Fig. 2. For each link, the parameters xij (t) contain the link’s free-flow time Tij0 , length Lij , jam density, Kij , capacity Qij , and backward wave time Tijb , that is,   ↑ ↓ xij (t) = Tij0 Lij Kij Qij Tijb . To propagate flow, the functions fij and fij must be specified for all links. These functions vary according to the upstream and downstream node type, respectively. These node types include homogeneous nodes (1 incoming link and 1 outgoing link), diverge nodes (1 incoming link and multiple outgoing links), merge nodes (multiple incoming links and 1 outgoing link), and general intersections (multiple incoming and outgoing links). ↑ ↓ We first define the aggregate flow functions fij and fij which give the total number of vehicles moving for each node type, followed by the disaggregate functions ↑s ↓s fij and fij by destination. In the LTM, the sending flow and receiving flow are used to determine the flows at each node. For use in this model, these discrete expressions must be converted to continuous equivalents as follows. Let Rij (t, t) and Rij (t, t) be the discrete sending and receiving flow for link (i, j ) at time t, with a time step of t, and let Rij (t) and Sij (t) be the corresponding continuous quantities. As defined in Yperman (2007), we have: ↑

↓

Sij (t, t) = min{Qij t, Nij (t − Tij0 + t) + −Nij (t)} ↓

(5) ↑

Rij (t, t) = min{Qij t, Nij (t − Tijb + t) + Kij Lij − Nij (t)}

Fig. 2 Triangular fundamental diagram assumed for all links

(6)

A Continuous DUE Algorithm Using the Link Transmission Model

Starting from the first of these, we have Sij (t, t)

Sij (t) = lim

t→0



t ↑

↓

Nij (t − Tij0 + t) − Nij (t)

= min Qij , lim

t

t→0



↑

= min Qij , lim

↑

t ↑

= min Qij , lim

↑

↓

Nij (t −Tij0 +t) − Nij (t − Tij0 ) + Nij (t − Tij0 )−Nij (t)

t→0





↑

Nij (t −Tij0 +t)−Nij (t −Tij0 ) t

t→0



 ↑ ↓ Nij (t −Tij0 )−Nij (t)

t→0

↑

↓

Nij (t − Tij0 ) − Nij (t)

↑

= min Qij , qij (t − Tij0 ) + lim



t

t

t→0

↑

+ lim



↓

There are two cases: if Nij (t − Tij0 ) = Nij (t) (that is, there is no queue), then the last ↑

↓

limit is zero. Or, if Nij (t − Tij0 ) > Nij (t) (a queue exists), the last limit diverges to infinity, and so Sij (t) will take the first value in the minimum. That is, ⎧ ⎨min{Qij , qij↑ (t − Tij0 )} if Nij↑ (t − Tij0 ) = Nij↓ (t) Sij (t) = ↑ ↓ ⎩Q if Nij (t − Tij0 ) > Nij (t) ij Likewise Rij (t) =

⎧ ⎨min{Qij , qij↓ (t − Tijb )}

if Nij (t − Tijb ) + Kij Lij = Nij (t)

⎩Q

if Nij (t − Tijb ) + Kij Lij < Nij (t)

ij

↓

↑

↓

↑

The flow functions for two node types are now discussed. For reasons of brevity, other node types can be defined in a similar way using these definitions of the sending and receiving flow, and the node models in Yperman (2007) and Tamp`ere et al. (2011). Consider a nonhomogeneous node j with sole upstream node i and sole downstream node k, vehicles are not stored in the turn movements (since there is only one “turn movement”) and instead pass instantaneously from the downstream end of link (i, j ), to the upstream end of turn movement (i, j, k), to the downstream end of turn movement (i, j, k), to the upstream end of link (j, k). In the LTM, this flow rate is defined by the minimum of the sending flow of (i, j ) and the receiving flow of (j, k), that is, ↓

↑

↓

↑

fij (t) = fij k (t) = fij k (t) = fj k (t) = min{Sij (t), Rj k (t)} These must be disaggregated by destination for use in the above formulation. To do ↑ ↓ this, define the inverse travel time σij (t) = supt  {Nij (t  ) = Nij (t)} to be the travel

N. Nezamuddin, S.D. Boyles

time of the vehicle leaving link (i, j ) at time t. Then the rate at which vehicles from destination s can move is given by  dσij (t) ↓s ↑s ↓ fij (t) = qij (σij (Nij (t))) 1 − dt as explained in Astarita (1996) and Ban et al. (2008). Consider a merge node j with upstream nodes h and i, and sole downstream node k. (This method easily generalizes to more than two upstream nodes.) If Shj (t) + ↓ ↑ ↓ Sij (t) ≤ Rj k (t), the merge is congested and fhj (t) = fhj k (t) = fhj k (t) = Shj (t), ↓

↑

↓

↑

fij (t) = fij k (t) = fij k (t) = Sij (t), and fj k (t) = Shj (t) + Sij (t). Otherwise, the ↑

merge is congested, fj k (t) = Rj k (t), and each approach can send flow in proportion to its capacity. If Shj (t) ≥ Qhj Rj k (t)/(Qhj + Qij ) and Sij (t) ≥ Qij Rj k (t)/(Qhj + ↓ ↑ ↓ Qij ), queues will grow on both approaches and fhj (t) = fhj k (t) = fhj k (t) = Qhj Rj k (t)/(Qhj + Qij ), with a similar equation for (i, j ). If one approach (without loss of generality say (h, j )) has less sending flow than its proportional share, a ↓ ↑ ↓ queue only grows on the other approach, and fhj (t) = fhj k (t) = fhj k (t) = Shj (t) ↓

↑

↓

and fij (t) = fij k (t) = fij k (t) = Rj k (t) − Sij (t). With the flow model specified, we can show that the routing parameter formulation is equivalent to a path-based formulation, in the following sense: given any particular set of time-dependent path departures, there exists a vector φ such that the node and link states Sj (t) and Sij (t) are identical for all i ∈ N, (i, j ) ∈ A, and t ∈ T . Let hrs π (t) denote the number of travelers departing origin r for destination ↑s s via path π at time t. Given these path flows, qij k (t) is uniquely determined for all s, i, j , k, and t from the model (2)–(4) (where Eq. 1 is not needed because the path ↑s ↓s flows determine route choices). Thus, we can define φijs k (t) ≡ qij k (t)/qij whenever ↓s

qij > 0, and arbitrarily otherwise; this clearly produces Eq. 1, which can be adopted instead of specifying path flows.

3 Equilibrium Formulation Together with boundary conditions representing the time-dependent OD matrix, the above system of equations defines a generic dynamic flow model. Define the leaving ↓ ↓ time of the n-th vehicle on link (i, j ) to be τij (n) = inft {Nij (t) = n} and the travel ↓

↑

time to be Tij (t) = max{τij (Nij (t)) − t, Tij0 (t)}. The travel time of a turning movement is defined similarly. The travel time to destination s from turning movement (i, j, k) is denoted as  φjs k (t + Tij k (t) Cijs k (t) = Tij k (t) + Tj k (t + Tij k (t)) + + Tj k (t

(j,k,)∈M s + Tij k (t)))Cj k (Tij k (t) + Tj k (t

together with the boundary condition Cjs ks ≡ 0.

+ Tij k (t)))

A Continuous DUE Algorithm Using the Link Transmission Model

With this in mind, the definition of Wardrop’s principle in the context of our model can be given as follows: Definition 1 Wardrop’s principle. The routing parameters φ satisfy Wardrop’s equilibrium principle if φijs k (t) > 0 ⇒ Cijs k (t) =

min {Cijs k  (t)}

(i,j,k  )∈M

for all s, i, j , k, and t, where the functions C are determined by φ as described above. Existence of equilibrium can be shown under regularity assumptions on the travel time functions Cijs k (t) which are satisfied if the flow propagation functions f are continuous. This is shown in the following proposition, which defines a correspondence Br(φ) returning the set of routing parameter functions placing positive weight only on minimum-cost turning movements, assuming that the travel times are determined by fixed routing parameters φ. Every fixed point of this correspondence (that is, every φ ∗ such that φ ∗ ∈ Br(φ ∗ )) is a Wardrop equilibrium. The remainder of this section establishes the existence of at least one fixed point to this mapping by establishing properties of the feasible sets of routing parameters and the correspondence Br and appealing to the Kakutani-Glicksberg-Fan Theorem (Kakutani 1941, Glicksberg 1952, Fan 1952). Proposition 1 If the flow propagation functions f are continuous in their arguments, there exist Wardrop equilibrium routing parameters satisfying Definition 1. Proof 1 Define the function norm ||f || = supt∈T |f (t)|, so a sequence of functions f k converges to a function f ∗ if this sequence converges uniformly over T . Let  denote the set of feasible routing parameter functions  = {φijs k (t) :

s s (j,k)∈A φij k (t) = 1, φij k (t) ≥ 0 ∀(i, j ) ∈ A, s ∈ Z, t ∈ T } and T(φ) the vector of travel time functions given routing parameters φ ∈  under the above definitions for a flow pattern satisfying the model (1)–(4). Note that these functions need not be continuous in t. Define the best response correspondence Br :  → 2 to be Br(T(φ)) = ×s∈Z,(i,j,k)∈M {φijs k (t) ∈  : φijs k (t) > 0 ⇒ Cijs k (t) =

min {Cijs k  (t)}∀t ∈ T }

(i,j,k  )∈M

(7)

 is clearly nonempty and compact, and is furthermore convex: consider any two functions φ1 ∈  and φ2 ∈  and any λ ∈ [0, 1]. At any time t ∈ T we have (λφ1 + (1 − λ)φ2 )(t) = λφ1 (t) + (1 − λ)φ2 (t), which is clearly nonnegative since φ1 (t) ≥ 0 and φ2 (t) ≥ 0. Furthermore for any (i, j ) ∈ A and s ∈ Z we have    λ(φ1 )sij k (t) + (1 − λ)(φ2 )sij k (t) = λ + (1 − λ) = 1 (j,k)∈A

so λφ1 + (1 − λ)φ2 ∈  as well.

N. Nezamuddin, S.D. Boyles

For any φ, the set Br(φ) is nonempty because the set of turning movements is finite. Furthermore, this set is convex: let φ1 and φ2 be arbitrary elements of Br(φ) (that is, vectors of the continuous-time routing parameter functions with components for each (i, j, k) and s), and consider λ ∈ [0, 1]. For any strictly positive component of λφ1 + (1 − λ)φ2 , we must have the corresponding component of either φ1 or φ2 to be strictly positive, and therefore representing a minimum-cost turning movement; thus λφ1 + (1 − λ)φ2 ∈ Br(φ) as well. Finally, the graph {φ, Br(φ)} is closed: consider any sequence (φn , Br(φn ) conˆ y). verging to the point (φ, ˆ Since  is closed, φˆ is a feasible vector of routing parameters. Consider any s, i, j , k, and t such that φˆ ijs k (t) > 0. There exists Nijs k (t) such that n > Nijs k (t) ⇒ (φn )sij k (t) > 0. For all such n and for all (i, j, k  ) ∈ M, we have Cijs k (t)−Cijs k  (t) ≤ 0 from the definition of the sequence. This holds at the limit if the mapping C is continuous, proving that the graph is closed. If the functions f ↑ and f ↓ in Eqs. 3 and 4 are continuous in their arguments, and if the node and movement parameters xij and xijk are continuous, τ is continuous in φ, in turn implying continuity of T and C. Thus, having established all of the necessary conditions, Kakutani’s Theorem asserts the existence of a fixed point of Br, which corresponds to a dynamic Wardrop equilibrium.  Of course, such an equilibrium may not be unique (Iryo 2013). It is worthwhile to ask whether the functions f ↑ and f ↓ are in fact continuous are in their arguments; most kinematic flow models (including LTM) are discontinuous due to queue spillback, and if queue spillback is modeled strictly the conditions of the above proposition are not satisfied. Consider Fig. 3, where the queue on link (i, k) obstructs the turn movement m1 = (h, i, k). With most node models, this obstruction would also prevent any flow on the turn movement m2 = (h, i, j ) as well, thus creating ↓ a discontinuity in qhij : an arbitrarily small change to the state of link (i, k) would ↓

increase qhij from zero to a larger value. Our solution is to smooth the discontinuity. As the link (i, k) approaches jam density (reflected in the state Sik through

Fig. 3 Queue spillback can create discontinuities in flow functions

A Continuous DUE Algorithm Using the Link Transmission Model

the upstream and downstream cumulative counts), the node model reduces the flow to all turn movements in a continuous manner (Fig. 4), rather than only after (i, k) has reached jam density. This “smoothing” can be done over a very small interval, approximating the original discontinuity as closely as desired. However, there may be some physical plausibility to the idea that entering volume reduces as a link approaches jam density: as the last physical space on a link is occupied by a queue, additional vehicles entering the link must do so at a slower and slower speed (since they must brake to a stop before reaching the tail of the queue). As speed of vehicles entering the link approaches zero, so will the volume at that point due to the fundamental flow equation.

4 Solution Methods In practice, the continuous model described above is solved by choosing a suitably fine time discretization and solving Eqs. 1–4 in increasing order of time, interpolating between time intervals as necessary.1 The remaining question is how to find equilibrium routing parameters. Given the generality of the flow model presented in the previous section, we do not aim to provide a provably convergent algorithm for all instances (a notion which in any case necessitate a careful definition given the potential nonuniqueness of equilibria); rather, the more modest aim in this paper is to present two heuristic strategies. Both strategies are tested in the following section in a small network, and appear to converge towards equilibrium. The first method is the well-known method of successive averages (MSA), which can be stated as follows: 1. 2. 3. 4. 5. 6.

Initialize φ by choosing some vector such that φijs k (t) = 1 and φijs k (t) ≥ 0 for all (i, j, k) ∈ M. Load flow by solving Eqs. 1–4 in increasing order of time. Calculate travel times T and times to destinations C. Choose a “best response” φ ∗ ∈ Br(T(φ)). Update routing parameters: φ ← λφ + (1 − λ)φ ∗ for some λ ∈ [0, 1]. Check for convergence; if not converged, return to step 2. A few notes on this procedure:

•

•

One natural choice for initializing the algorithm in Step 1 is to choose φ to place unit weight on the shortest path trees rooted at each destination, using free-flow travel times. Alternately, a “warm-start” can be applied if one has an equilibrium or approximate equilibrium on a similar network. See Nezamuddin (2011) for further discussion on warm-starting DTA models, and for empirical comparison of several options. Step 3 essentially finds a local best response; there is no shortest path algorithm which is run over the entire network.

1 Note that this may change the character of the underlying solutions somewhat, as discussed in Wie et al. (2002)

N. Nezamuddin, S.D. Boyles

ε Fig. 4 Smoothing the discontinuity due to spillback

• •

In step 5, λ is often taken to be the reciprocal of the iteration number, but other choices are possible as well. Bar-Gera and Boyce (2006) In step 6, one potential convergence measure is the average excess cost, defined in the following section.

The second method attempts to use derivative information from the mapping C(T(φ)) to improve the rate of convergence. Such methods have been found effective in other DTA algorithms, such as B-Dynamic (Ramadurai and Ukkusuri 2011). In particular, for now assume that Tij (t) ≡ ∂Tij (t)/∂qij (t) exists for all (i, j ), s, and t. Then we can define a derivative of the travel time from the upstream end of a turning movement to the destination using the recursion  (φjs k )2 (t + Tij k (t) Dijs k (t) = Tij k (t) + Tjk (t + Tij k (t)) + + Tj k (t

(j,k,)∈M s + Tij k (t)))Dj k (Tij k (t) + Tj k (t

+ Tij k (t)))

(8)

and the boundary condition Djs ks ≡ 0. Then, we can solve for an approximate local equilibrium using the linear approximations Cijs k (φijs∗k ) ≈ Cijs k + (φijs∗k − φijs k )Dijs k in a matter analogous to the LUCE algorithm (Gentile 2009) developed for static traffic assignment, such that φijs∗k > 0 ⇒ Cijs k (φijs∗k ) = minij k  Cijs k  (φijs∗k  ). This can be done extremely quickly, and the actual routing parameters updated using an averaging rule such as that in MSA. The algorithm can be presented as Initialize φ by choosing some vector such that φijs k (t) = 1 and φijs k (t) ≥ 0 for all (i, j, k) ∈ M. 2. Load flow by solving Eqs. 1–4 in increasing order of time. 3. Calculate travel times T, times to destinations C, and derivatives D. 4. Choose φ ∗ by solving “local” equilibrium problems using linear approximations based on C and D. 5. Update routing parameters: φ ← λφ + (1 − λ)φ ∗ for some λ ∈ [0, 1]. 6. Check for convergence; if not converged, return to step 2.

1.

A Continuous DUE Algorithm Using the Link Transmission Model

Because of the derivative information incorporated, the weighting factor λ can be higher than that in MSA. In the experiment reported in the following section, the algorithm starts with λ = 1, halving λ whenever a gap measure increases between successive iterations, and leaving it unchanged otherwise. Using λ < 1 may be necessary to ensure convergence; as discussed in Nie (2012), this method of calculating derivatives may underestimate the true values, leading to overly large step sizes. The model defined by Eqs. 1–4 may not be everywhere differentiable; however, when fij k and fij are given by the link transmission model, the mapping C(T(φ)) ↑ ↓ is piecewise differentiable with dTij /dqij = 1/fij if there is a downstream bottleneck and 0 otherwise. In the demonstration reported in the following section, one of these two values was chosen arbitrarily whenever a derivative was required at the intersection of these pieces; determining whether this is generally a wise strategy is a worthwhile topic for future research.

5 Demonstration Both of the algorithms described in the previous section are tested on the familiar Braess network (Fig. 5) containing four nodes and five links. Units are chosen so that each link is given unit length and free-flow time, a capacity of 50 vehicles per unit time, and a jam density of 200 vehicles per link. Travel demand is 100 vehicles per unit time for t ∈ [0, 11] and zero thereafter. The initial solution is generated by splitting flows evenly at every diverge, that is, φ·12 (t) = φ·13 (t) = φ123 (t) = φ124 (t) = 1/2. Figures 6 and 7 plot the progress of the two algorithms according to two metrics; numerical values can be found in Table 1. The average excess cost, used in Fig. 6, is the difference between the total experienced travel time, and the theoretical total travel time obtained if all travelers experienced the shortest possible travel times between their origin and destination among all available paths, scaled by the total travel demand. Mathematically, let the shortest path travel

Fig. 5 Network used in demonstration

N. Nezamuddin, S.D. Boyles 10

Average excess cost

1 MSA

0.1

LUCE

0.01

0.001 1

3

5

7

9

11

9

11

Iteration Fig. 6 Average excess cost for two solution methods

8000

Total system travel time

7000

6000

5000

4000 MSA

LUCE

3000 Equilibrium

2000

1

3

5

7

Iteration Fig. 7 Total system travel time for two solution methods

A Continuous DUE Algorithm Using the Link Transmission Model Table 1 Average excess cost and total system travel time for two solution methods

Iteration

MSA AEC

LUCE TSTT

AEC

TSTT

1

1.75

4625.0

1.75

4625.0

2

2.054

4504.1

4.739

7462.5

3

0.432

2841.7

2.685

5178.2

4

0.883

3194.8

1.297

3693.5

5

0.277

2605.0

0.462

2848.7

6

0.549

2819.9

0.389

2632.4

7

0.174

2462.4

0.288

2533.0

8

0.422

2676.8

0.108

2319.0

9

0.143

2412.9

0.031

2234.3

10

0.3

2540.2

0.011

2212.5

11

0.124

2382.1

0.004

2205.8

12

0.255

2488.3

0.001

2201.6

time from the upstream end of turning movement (i, j, k) to destination s be given by Uijs k (t) = Tij k (t) + Tj k (t + Tij k (t)) +

min (t + Tij k (t)

(j,k,)∈M

+ Tj k (t + Tij k (t)))Ujsk (Tij k (t) + Tj k (t + Tij k (t))) and the boundary condition Ujss· ≡ 0.

Fig. 8 Larger grid network used for comparison

(9)

N. Nezamuddin, S.D. Boyles

Fig. 9 Average excess cost for two solution methods

Then the average excess cost is given by

AEC =

T s s (r,j )∈A 0 (T·rj (t) − U·rj )dt

(r,s)∈Z 2

T (r,s)∈Z 2 0

Fig. 10 Total system travel time for two solution methods

d rs (t)dt

(10)

A Continuous DUE Algorithm Using the Link Transmission Model

while the total system travel time is simply T ST T =



 

(r,s)∈Z 2

(r,j )∈A 0

T

s T·rj dt

(11)

While the latter is not strictly a gap measure (since Wardrop equilibria do not generally correspond to system-optimal solutions) it nevertheless indicates the relative quality of the solutions. By either measure, the LUCE-based method reaches faster precision after the initial iterations. These algorithms are also tested on a larger grid network, containing 207 nodes, 287 links, and 7 zones (Fig. 8). Figures 9 and 10 show the average excess cost and total travel time obtained by the MSA and dynamic LUCE algorithms. Note that the dynamic LUCE algorithm is still able to attain the same linear convergence rate as on the Braess network despite the interaction between different destinations and more complex network topology.

6 Conclusions This paper described a generic continuous-flow DTA model for which (1) existence of dynamic Wardrop equilibrium is guaranteed; (2) node routing parameters obviate the need to enumerate paths; (3) generic solution methods can be easily developed and implemented; and (4) a variety of node models can be introduced to represent average traffic control delay. This model was demonstrated on two networks using dynamic versions of MSA and LUCE. In particular, the LUCE algorithm was easily adapted to our dynamic model, without reducing either its efficacy or its efficiency. Future research should explore solution algorithms in further depth, exploring issues of convergence, practical performance across a broader suite of test networks, and sensitivity analyses to various parameters. By presenting a generic model, our hope is that a variety of link and node models can be compared and calibrated using this model as a common framework.

References Astarita V (1996) A continuous link time model for dynamic network loading based on travel time function. In: Lesort J-B (ed) Transportation and traffic theory. Pergamon, pp 79–102 Ban XJ, Liu HX, Ferris MC, Ran B (2008) A link-node complementarity model and solution algorithm for dynamic user equilibria with exact flow propagations. Transp Res B 42:823–842 Ban XJ, Pang J-S, Liu HX, Ma R (2012) Modeling and solving continuous-time instantaneous dynamic user equilibria: a differential complementarity systems approach. Transp Res B 46(3):389–408 Bar-Gera H (2005) Continuous and discrete trajectory models for dynamic traffic assignment. Netw Spat Econ 5:41–70 Bar-Gera H, Boyce D (2006) Solving a non-convex combined travel forecasting model by the method of successive averages with constant step sizes. Transp Res B 40:351–367 Bliemer MCJ, Bovy PHL (2003) Quasi-variational inequality formulation of the multiclass dynamic traffic assignment problem. Transp Res B 37(6):501–519 Blumberg M, Bar-Gera H (2009) Consistent node arrival order in dynamic network loading models. Transp Res B 43(3):285–300

N. Nezamuddin, S.D. Boyles Carey M (1992) Nonconvexity of the dynamic assignment problem. Transp Res B 26(2):127–133 Chiu Y-C, Bottom J, Mahut M, Paz A, Balakrishna R, Waller T, Hicks J (2010) A primer for dynamic traffic assignment. Prepared by the Transportation Network Modeling Committee of the Transportation Research Board (ADB30) Daganzo CF (1994) The cell transmission model: a dynamic representation of highway traffic consistent with the hydrodynamic theory. Transp Res B 28(4):269–287 Daganzo CF (1995) The cell transmission model, part II: network traffic. Transp Res B 29(2):79–93 Fan K (1952) Fixed-point and minimax theorems in locally convex topological linear spaces. Proc Natl Acad Sci USA 38(2):121–126 Friesz T, Bernstein D, Smith TE, Tobin RL, Wie BW (1993) A variational inequality formulation of the dynamic network user equilibrium problem. Oper Res 41(1):179–191 Friesz T, Luque J, Tobin R, Wie B (1989) Dynamic network traffic assignment considered as a continuous time optimal control problem. Oper Res 37:893–901 Friesz TL, Han K, Neto PA, Meimand A, Yao T (2013) Dynamic user equilibrium based on a hydrodynamic model. Transp Res B 47:102–126 Friesz TL, Kim T, Kwon C, Rigdon MA (2011) Approximate network loading and dual-time-scale dynamic user equilibrium. Transp Res B 45(1):176–207 Gentile G (2009) Linear User Cost Equilibrium: a new algorithm for traffic assignment. Working paper Gentile G (2010) The general link transmission model for dynamic network loading and a comparison with the DUE algorithm. In: Immers LGH, Tampere CMJ, Viti F (eds) New developments in transport planning advances in dynamic traffic assignment. Edward Elgar Publishing Glicksberg IL (1952) A further generalization of the Kakutani fixed point theorem, with application to Nash equilibrium. Proc Am Math Soc 3(1):170–174 Iryo T (2013) Investigating factors for existence of multiple equilibria in dynamic traffic network. Accepted for publication in Networks and Spatial Economics. http://link.springer.com/article/10. 1007/s11067-013-9206-6 Janson BN, Robles J (1995) Quasi-continuous dynamic traffic assignment model. Transp Res Rec 1493:199–206 Kakutani S (1941) A generalization of Brouwer’s fixed point theorem. Duke Math J 8(3):457–459 Lighthill MJ, Whitham GB (1955) On kinematic waves II. A theory of traffic flow on long crowded roads. Proc R Soc A 229(1178):314–345 Long J, Huang H-J, Gao Z, Szeto WY (2011) An intersection-movement-based dynamic user optimal route choice problem. Oper Res 61(5):1134–1147 Merchant D, Nemhauser G (1978a) A model and an algorithm for the dynamic traffic assignment problems. Transp Sci 12:183–199 Merchant D, Nemhauser G (1978b) Optimality conditions for a dynamic traffic assignment model. Transp Sci 12:200–207 Mounce R (2006) Convergence in a continuous dynamic queueing model for traffic networks. Transp Res B 40(9):779–791 Newell GF (1993a) A simplified theory of kinematic waves in highway traffic, part I: general theory. Transp Res B 27(4):281–287 Newell GF (1993b) A simplified theory of kinematic waves in highway traffic, part II: queueing at freeway bottlenecks. Transp Res B 27(4):289–303 Newell GF (1993c) A simplified theory of kinematic waves in highway traffic, part III: multi-destination flows. Transp Res B 27(4):305–313 Nezamuddin (2011) Improving the efficiency of dynamic traffic assignment through computational methods based on combinatorial algorithm. Ph.D. thesis, The University of Texas at Austin Nie Y (2012) A note on Bar-Gera’s algorithm for the origin-based traffic assignment problem. Transp Sci 46(1):27–38 Nie YM (2010) Equilibrium analysis of macroscopic traffic oscillations. Transp Res B 44:62–72 Peeta S, Ziliaskopoulos AK (2001) Foundations of dynamic traffic assignment: the past, the present, and the future. Netw Spat Econ 1:233–265 Qian Z(S), Zhang HM (2013) A hybrid route choice model for dynamic traffic assignment. Netw Spat Econ 13(2):183–203 Ramadurai G, Ukkusuri SV (2011) B-dynamic: an efficient algorithm for dynamic user equilibrium assignment in activity-travel networks. Comput Aided Civ Infrastruct Eng 26(4):254–269

A Continuous DUE Algorithm Using the Link Transmission Model Ran B, Boyce DE (1996) A link-based variational inequality formulation of ideal dynamic user-optimal route choice problem. Transp Res C 4(1):1–12 Ran B, Boyce DE, LeBlanc LJ (1993) A new class of instantaneous dynamic user-optimal traffic assignment models. Oper Res 41(1):192–202 Ran B, Hall RW, Boyce DE (1996) A link-based variational inequality model for dynamic departure time/route choice. Transp Res B 30:31–46 Tamp`ere CMJ, Corthout R, Cattrysse D, Immers LH (2011) A generic class of first order node models for dynamic macroscopic simulation of traffic flows. Transp Res B 45:289–309 Waller ST, Fajardo D, Duell M, Dixit V (2013) Linear programming formulation for strategic dynamic traffic assignment. Netw Spat Econ 13(4):427–443 Wie BW (1991) Dynamic analysis of user optimized network flows with elastic travel demand. Presented at the 70th Annual Meeting of the Transportation Research Board, Washington, DC Wie B-W, Tobin RL, Carey M (2002) The existence, uniqueness and computation of an arc-based dynamic network user equilibrium formulation. Transp Res B 36(10):897–918 Yperman I (2007) The link transmission model for dynamic newtork loading. Ph.D. thesis, Katholieke Universiteit Leuven, Belgium