Some Properties of a Multi-Lane Extension \ of the Kinematic Wave Model

Some Properties of a Multi-Lane Extension
of the Kinematic Wave Model

Jorge A. Laval 1

Abstract. This paper extends an existing continuum multi-lane formulation for traffic flow, provides a discrete formulation for its numerical solution, and shows initial results. The new formulation enables a natural treatment of boundary conditions such as merges, diverges, lane-drops and moving bottlenecks. The proposed model needs few extra parameters and is parsimonious. The look-ahead distance, for example, induces the anticipation of traffic conditions, causing smooth regime changes and fast waves. We find that as the look-ahead distance tends to zero, the solution tends to the kinematic wave one. The example of a lane-drop is analyzed and also used to demonstrate the convergence of the discrete model.
Jorge Laval ©2004


1  Introduction
2  The continuum formulation
    2.1  The multi-lane CT rule
    2.2  Partial Demand
3  The discrete formulation
    3.1  Additional assumptions
4  Example: Lane-drops
5  Convergence
    5.1  Stability
    5.2  Consistency
6  Discussion

1  Introduction

This paper proposes a discrete formulation for a first-order multi-lane traffic flow model. Among the extensions of the kinematic wave (KW) model [1,[2] the multi-lane extension has received little attention in the literature. This extension was already devised in 1971 by Munjal and Pipes [3] for a two-lane highway. The drawback of Munjal's model lane-changing flows are computed ignoring competing flows; ie, lane-changing flows have priority over the through flow on the target lane as they are assumed proportional to the difference in density w.r.t the target lane.
Munjal's model was first extended in [4] who added a source terms to include ramp flows explicitly. Unfortunately, the "priority" drawback still persists. Notably, the first discretization of the multi-lane model is presented, but the numerical scheme used at that time (Lax-Wendroff) is unable to treat discontinuities and boundary conditions properly. This reference also develops a second-order and a two-dimensional formulation, but results favor the simpler first-order model.
No other first-order macroscopic multi-lane models have been developed. Rather, existing multi-lane KW theories address problems [5,[6,[7] including different user classes and/or driver psychology. In these models, traffic rules are simple enough so that graphical KW solutions are still tractable. Additionally, problems with no more than two user types and two lane types can be solved. notice that in [5,[6] numerical methods are developed to solve the specific problems.
Second-order multi-lane models are also available [8,[9]. This approach is not pursued in this paper given that second-order models suffer from important drawbacks still not resolved [10,[11,[12,[11,[13] while first-quarter models are simpler and drawback-free. We can also mention the stochastic models in [14,[15] that aim to describe the steady-state conditions rather than traffic dynamics.
During the last decade much has been learned for dealing with complex boundary conditions in the KW model. Particularly, [16] pointed out that the flow at the origin of the Riemann problem in the Godunov scheme [17], g(ku,kd), is the acclaimed cell transmission (CT) rule [18]:
g(ku,kd)= min
where Q(t,x) is the capacity of the road at (t,x); ku and kd are the densities upstream and downstream of the time-space point of interest; and l(k,t,x) and m(k,t,x) are two monotonic functions that uniquely define the fundamental diagram; Fig. 1a.
A recent interpretation for the fundamental diagram was provided by Daganzo [18] in the context of numerical methods. He points out that in free-flow, l(·) represents the ability of a segment to send flow to the segment downstream; in congestion, m(·) gives the ability of a segment to receive flow from the upstream segment. Later, Lebacque [16] argues that the sending ability represents the demand for advancing to the downstream segment while the receiving ability is a simile for the supply for serving upstream demand. In this paper we adopt the latter terminology because central to the formulation is the existence of a "demand for lane-changing" curve in the sense of discrete-choice modeling.
To overcome the limitations of Munjal's model and its current discrete formulation [4], we propose an extension of the CT rule where through and lane-changing flows are a result of supply-demand interactions. The main findings are that the proposed formulation predicts (i) smooth shocks and (ii) fast waves.
Smooth shocks appear due to the look-ahead distance, which makes the model non-local since it induces the anticipation of traffic conditions. Non-local and anticipatory models are not new in the literature of microsimulation [19,[20] and gas-kinetic models [21]. The added value of the proposed formulation is that it is the discrete version of a continuum first-order model, the simplest approach consistent with vehicle conservation and where parameters have a meaningful physical interpretation. Additionally, its reduced number of parameters allows us to establish stability and convergence numerically.
The prediction of "fast backward waves" prior to the smooth transition is in agreement with existent observations [7,[22], at least qualitatively since they occur at the onset of congestion. This ability of the model is due to the spatial nature of the anticipation process proposed herein, as opposed to microscopic models, where drivers estimate their leaders' velocities for future time-steps. In our model anticipation arises because drivers perceive traffic conditions on each lane (speed or density) as the average over the look-ahead distance.
This paper is organized as follows: §§ 2 and 3 present the continuum resp. discrete formulation followed by a lane-drop bottleneck example in § 4 and a demonstration of convergence in § 5. Finally, some discussion is provided in § 6.

2  The continuum formulation

Consider a freeway with N identical lanes where identical vehicles flow. Let k=.[k1,kN] where kl(t,x) is the density of vehicles on lane l = 1,N. At each (t,x,l)-point we assume three possible movements: (i) change to the left lane l=l-1; (ii) stay in the same lane; and (iii) change to the right lane l=l+1.
Let qll(k) be the flows on movement ll, and ql(k) the total flow across movements, ie

We call qll the through flows and qll,l l, the lane-changing flows.
Note that qll,l l has units of vehicles per unit-time per unit-distance.
Physically, if one were to measure lane-changing rates on a given time period T, one would count vehicles changing lanes over a small road section of length L , and divide this number by T L .
On a segment without entrances or exits, the conservation equation for total flows becomes

+ ql(k)

=0,        "l.
Combining (3) and (2) gives

+ qll(k)


l l 

,     "l.
Munjal's model [3] is similar to (4) but the lane-changing flows are computed independently of other competing flows; ie, they are assumed proportional to (kl-kl), as in the early Gazis' model [23]. The following section presents a proposition for overcoming this limitation.

2.1  The multi-lane CT rule

Let the partial demand for movement ll be lll(k) and the total supply on l be ml(k). In this section we assume that lll and ml are known but we need to determine the actual flow for each movement.
This is a well known problem in the literature of multi-class KW models [24,[25,[26,[27,[28,[29] where the solution to the Riemann problems can be obtained after simplifying assumptions. The problem with these methods is that priorities are not properly included, mainly because the simplifying assumptions. A more applicable framework seems to be the merge model incorporated in the CT model [30]. However, it was developed for only two competing demands, whereas in a general lane-changing setting one needs to consider three competing demands. Moreover, maximum merge ratios have a clear interpretation for merges, but become unclear for lane-changing; demands on merges have only one alternative (going through the merge) but in the case of lane-changing one could decide not to change lanes.
Alternatively, we propose to split the supply on lane l by analogy of a deterministic server of capacity ml facing multiple customer types arriving at rates lll with identical service times; see Fig. 1b. In direct analogy with the CT rule (1) one could postulate
qll= min
where all gives the probability of a departure being type ll and Q is the one-lane capacity, assumed constant for simplicity. When all movements have the same priority then
all= lll

should be used in (5). The problem with (5)-(6) is that whenever ml > nlnl then there will always be a movement such that
lll allml,                 for some movement ll,
and some supply will be lost if another movement could have used it. This would violate the flow-maximizing character of the entropy condition, possibly yielding an unstable model. To overcome this limitation, we propose the following algorithm that explicitly checks for (7) and reassigns supply.
Proposition 1 [Algorithm F] Given ll-1,l, lll, ll+1,l and ml, the following algorithm yields FIFO supply split:
1. Compute auxiliary flow fll using (5)-(6) "l,
2. Update ml:=ml-l fll. If ml=0 stop, else
3. Update lll:=lll-fll, "l. If "l:lll=0 then stop, else go to Step 1.
At each iteration, n, this algorithm allocates total supply using (5)-(6). If (7) is satisfied at n=1, the remaining supply will be split between the other movements, as sought. Notice that this algorithm converges in at most n=3 iterations. The final flows are obtained adding up the auxiliary flows at every iteration, ie

Next, we formalize the computation of partial demands.

2.2   Partial Demand

At the discrete vehicle level, lane-changing decisions are assumed given by a discrete-choice process [31] that repeats continuously in time. The basic assumption is that drivers' willingness to change to an adjacent lane can be obtained knowing the current state of the freeway; ie, knowing {k(t,x), x >  0}. Let Pll(t,x) be the proportion of users that would like to change to lane l at a given (t,x,l)-point.
We assume that lane-changing decisions occur every t time-units, so that the choice function in continuous time, ~Pll, can be defined as

Pll/t,         l l.
In this fashion, we insure that the number of vehicles wanting to change lanes predicted by the continuum choice function will be consistent with the predictions of the discrete-choice model, when compared over a time period of interest.
Finally, partial demands for lane-changing can be computed as
lll = kl

,                 l l,
while the through demand is the remaining demand, ie,

l l 

3  The discrete formulation

The discrete model for (4) is now presented. As in most discrete traffic flow models, we use the finite difference method [18,[32,[30,[33,[34,[35,[36]. In these methods, the highway is partitioned into small sections of length Dx and time into discrete time steps of duration Dt, related by
for stability, where u is the fastest characteristic in (4). Additionally, we partition the freeway in cells (i,l) as shown in Fig. 1c, where i is the section along the roadway and l is the lane index. The resulting numerical grid is denoted (tj=.jDt, xi=.iDx,l).
Let kilj and qillj be the numerical approximation of kl(jDt, iDx) resp. qll(jDt,iDx). Let lill be the partial demand for changing from (i,l) to (i+1,l) during time step j and let mil be the total supply in (i,l). The proposed numerical scheme consists of the following independent loops indexed by section i and lane l:
qill=F(li,l-1,l ;lill; li,l+1,l;mi+1,l),                 "l

kil:=kil + Dt

where Sil=.l qill and Eil=.l qi-1,ll are the flows that exit and enter (i,l) in time-step j, respectively. Eqn. (13) represents the discrete analog of (5), while (14) ensures the conservation of vehicles.
Note that (13) can be rewritten as
kilj+1- kilj

+ qill-qi-1,ll

= -

l l 
qill- qi-1,ll

showing the correspondence with the continuum model (4).
Notice that discrete lane-changing flows need to reflect the flows of the entire cell, thus
lill .

Dx kil

if l l,

l l 
if l = l.

3.1  Additional assumptions

Up to this point the formulation has been as general as possible. To illustrate the procedure we need to specify functional forms and parameter values.
The FD on each lane obeys is triangular, with free-flow speed u mph, congested wave speed -w mph and jam density for one lane k vphpl. Thus, it follows that

mil = w(k-kil).
In keeping with simplicity, lane-choice probabilities Pll are supposed proportional to the (positive) speed gain by changing to l at (t,x) , defined as Dvll(t,x):
Pll=Dvllp/u                 if l l.
where p is the maximum lane-changing prob. The speed gain is defined as Dvll=.|vl-vl|, where vl is the speed on lane l, computed using
vl= min
where kl(t,x) is the average density at (t,x,l) measured across a look-ahead distance, La, ie
(t,x) .




4  Example: Lane-drops

The following numerical demonstrations assumed t = 6 sec, p = 100 % and La=0.3 miles, u=-w = 60 mph and k = 150 vpmpl. We use w=-u because the numerical method becomes exact and therefore one can focus exclusively on the effects of the model presented herein.
Consider a 1.2-mile, 2-lane freeway segment that has a lane-drop at D=1.2 miles on lane 2; see Fig. 2a. At t=0 the freeway is empty and the input demand is capacity Q=4500 vpmpl. The KW solution consists of an instantaneous transition between states C and B in part (b) of the figure.
The numerical N-curves with Dt= 0.2 sec are shown in part (c), measured at the 7 evenly-spaced locations shown part (a). It is clear how state B is a smooth transition compared to the KW solution shown as a doted line on top of N1. The thin lines on the figure indicate the beginning and ending times of the transition, which lasts for approx. 50 sec at every station. The reader can verify that the slope of this lines is 2wk=18,000 vph, as expected from a backward wave.
The k-maps of the numerical solution are shown in part (d) of Fig. 2 for each lane separately and both lanes averaged. The figure reveals that:
To see the intuition behind the solution, note that the first lane changes takes place from lane 2 to lane 1 at point a in the figure, (ta=(D-La)/u,xa=D-La). This is the point where the leader first sees the lane drop. This induces a bottleneck in lane 1 that propagates upstream as suggested by the white dotted line starting at a. Interestingly, the bottleneck also moves downstream as a fan and, hitting the lane-drop triggering the activation of the "real" bottleneck, which propagates upstream as shown by the white dotted lines.
To see how the model produces smoothing, let us examine what happens after the very first lane-changing. To this end, let p=.Dt~P21(ta,xa) for clarity in notation and let i be the section containing point a . It can be verified that the lane-changing flow qi21j=[(Qp)/(1+p)] causes a queue in cell (i,1) carrying a flow qi2j=Q-qi21j=[(Q)/(1+p)] at a speed
v= uw

Notice that qij+1 is still 2Q but qi-1j+1=[(Q)/(1+p)]+Q=Q[(2+p)/(1+p)] 2Q. Thus, "small" bottlenecks caused by lane-changing induce local flow reductions before the actual wave passes, smoothing-out the BOQ. It follows that the capacity of the bottleneck remains unchanged.

5  Convergence

This section demonstrates that the discrete model is a convergent numerical schemes for the continuum model. To this end, let M be the discrete model (-19), and K the continuum model (4). Also let an N-profile Nt(x) be the N-values along the road for a given t.
According to the Lax Equivalence Theorem [37], to show the convergence of M one must show that it is stable and consistent. This is done on the following two sections using the lane-drop example.

5.1  Stability

Let N0(x) and ~N0(x) be two initial N-profiles. Let Mj be the operator obtained after j iterations of the numerical scheme (-19). The model is stable if the following is true for all j:
||N0 -

|| e ||MjN0 - Mj

|| e.
for some norm ||·|| and some e > 0 . Condition (23) states that errors in the input data do not grow with time.
For the demonstration, N0 corresponds to the values at t=60 sec for the lane-drop example in § 4. The perturbed profile ~N0 is similar but the input in density is 75.001 instead 75 vpmpl on the first cell of the freeway on lane 1. Fig. 3a shows the values of the errors ||MjN0 - Mj~N0|| with Dt= 0.5 sec. It is clear how (23) is satisfied since the errors decay as time passes. Notice how the error is confined to the first two loop-detectors.

5.2  Consistency

Let MjDt be the operator obtained after j iterations of M with time-step Dt, and let Kj be the continuum operator up to time tj, ie, gives the exact continuum solution at time tj using (4).
The model is consistent if
||MjDt N0 - Kj N0 || 0                 as Dt 0.
Condition (24) indicates that the solution of M tends to the continuum solution as the grid is refined.
In general when La > 0 the continuous solution is not easy to obtain, but experiments indicate that as the mesh is refined M tends to "a" unique solution. Fig. 4 shows the k-maps of the lane-drop example for different mesh sizes. It becomes clear that the solution tends to Fig. 2d, obtained with Dt= 0.2 sec.
Fig. 3b shows the total number of lane-changes as a function of Dt. The total number of lane-changes, h, can be computed as
h =

It is clear how this number converges to approximately 386 lane-change as Dt 0.

6  Discussion

This paper proposed a discrete first-order multi-lane traffic flow model, showed some of its properties, and demonstrated its convergence. The main finding is that the inclusion of the look-ahead distance La induces the propagation of fast waves caused by anticipation and the smoothing of the BOQ, all of which does not affect the discharge rate of the bottleneck.
As opposed to conventional single-pipe waves, fast waves propagate across adjacent lanes in the form of "small" bottlenecks induced by lane-changers. Notice that "fast waves" are magnified with the number of lanes. For example, if lane 3 terminates, the first lane-changing will occur on lane 3 (to 2) at a distance La from the lane-drop, and this induces in turn lane-changing from lane 2 to 1 up to 2La miles upstream of the first lane-changing.
Further research is needed to investigate other functional forms for the choice function P(·), but not deviate too much from the simple specification (19) used in this paper. These functions should be easy to calibrate for the BOQ is readily observable in the field and we have identified how the parameters affect the BOQ. Notice that one does not need sophisticated lane-changing models as traffic interactions are captured by the traffic model.
The analogy with a queueing system for splitting supplies could be used in more complicated situations, such as special lanes, different vehicle length and speeds. It may be advantageous to generalize the FIFO rule by extending the incremental transfer principle introduced in [6].
We showed the case of a lane-drop, but the model has been successfully tested with moving bottlenecks by including the method in ] for single-pipe models. In fact, the modeling of moving bottlenecks is simpler in the multi-lane framework. Lane-changing can be modeled as a moving bottleneck using the lane-changing flows generated by the procedure on this paper, as the rate of a discrete two-dimensional stochastic process. Ongoing research shows, encouragingly, that losses in capacity comparable to the elusive capacity drop are observed when cars changing lanes are modeled as moving bottlenecks. When this concept is applied to vehicles passing a moving bottleneck, we observe capacities that depend on the speed of the original moving bottleneck, and the relations match the empirical observations in [38].


The author is grateful to Carlos Daganzo for all the comments and suggestions, and to three anonymous referees who provided very helpful comments and insights.
Figure 1: (a) Demand and supply functions; (b) A deterministic server of capacity facing multiple customer types; (c) Discretized freeway representation.
Figure 2: (a) A 2x1 lane-drop; (b) relevant states in the FD; (c) numerical N-curves; (d) numerical k-map with Dt= 0.2 sec.
Figure 3: (a)Error propagation showing stability of M; (b) number of lane-changes for different mesh sizes.
Figure 4: k-maps of the lane-drop example for Dt= 2 sec (top,) Dt= 1 sec (middle) and Dt= 0.5 sec (bottom.)



MJ Lighthill and GB Whitham. On kinematic waves. i flow movement in long rivers. ii a theory of traffic flow on long crowded roads. Proc. Roy. Soc., 229 (A): 281-345, 1955.
P I Richards. Shockwaves on the highway. Opns. Res., (4): 42-51, 1956.
PK Munjal and LA Pipes. Propagation of on-ramp density perturbations on unidirectional two- and three-lane freeways. Transportation Research B, 5 (4): 241-255, 1971.
PG Michalopoulos, DE Beskos, and Y Yamauchi. Multilane traffic dynamics: Some macroscopic considerations. Trans. Res. B, (18): 377-395, 1984.
C F Daganzo. A continuum theory of traffic dynamics for freeways with special lanes. Trans. Res. B, 2 (31): 83-102, 1997.
CF Daganzo, W Lin, and J Del Castillo. A simple physical principle for the simulation of freeways with special lanes and priority vehicles. Trans. Res. B, 2 (31): 105-125, 1997.
C F Daganzo. A behavioral theory of multi-lane traffic flow part i: Long homogeneous freeway sections. Trans. Res. B, 2 (36): 131-158, 2002.
D Helbing. Modeling multi-lane traffic flow with queuing effects. Physica A, 242 (1-2): 175-194, 1997.
JM Greenberg, A Klar, and M Rascle. Congestion on multilane highways. SIAM journal of applied mathematics., 63 (3): 813-818, 2003.
M Cremer, F Meissner, and S Schrieber. On predictive control schemes in dynamic rerouting strategies. In 12th International Symposium on Transportation and Traffic Theory, pages 407-426, Berkeley, CA, 1993. Elsevier.
C F Daganzo. Requiem for second-order fluid approximation of traffic flow. Trans. Res. B, B (29): 277-286, 1995a.
J M Del Castillo. A formulation for the reaction time of traffic flow models. In C. Daganzo, editor, 2th Int. Symp. on Transportation and Traffic Theory, Elsevier, New York, 1993.
JP Lebacque and JB Lesort. Macroscopic traffic flow models: a question of order. In A. Ceder, editor, 14th Int. Symp. on Transportation and Traffic Theory, pages 3-25, Pergamon, New York, N.Y., 1999.
J Roberch. The multi-lane traffic flow process: An evaluation of queuing and lane-changing patterns based on a markov model. Transportation Research B, 10 (2): 135-136, 1976.
H Cho and S Lo. Modeling self-consistent multi-class dynamic traffic flow. Physica A, 312 (3-4): 342-362, 2002.
J P Lebacque. Les modeles macroscopic du traffic. Annales des Ponts., (67): 24-45, 1993.
S Godunov. A difference scheme for numerical computation of discontinuous solutions of equations of fluid dynamics. Mat. Sb., 89 (47): 271-306, 1959.
C F Daganzo. The cell-transmission model: A dynamic representation of highway traffic consistent with the hydrodynamic theory. Technical Report UCB-ITS-RR-93-7, Inst. Trans. Studies, Univ. of California, Berkeley, CA, 1993.
N Eissfeldt and P Wagner. Effects of anticipatory driving in a traffic flow model. In European Physical Journal B, number 33, pages 121-129. 2003.
J Schmeider and A Ebersbach. Anticipatory drivers in the nagel-schreckenberg model. International Journal of Modern Physics C, 13 (1), 2002.
M Treiber, A Hennecke, and D Helbing. Derivation, properties and simulation of a gas-kinetic-based, non-local traffic model. Phys. Rev. E, 59 (1): 239-253, 1999.
B S Kerner and H Rehborn. Experimental properties of complexity in traffic flow. Phys. Rev., 53 (E): R4275-R4278, 1996.
DC Gazis, R Herman, and G Weiss. Density oscillations between lanes of a multi-lane highway. Operations Research, (10): 658-667, 1962.
GCK Wong and SC Wong. A multi-class traffic flow model : an extension of lwr model with heterogeneous drivers. Trans. Res. A, (36): 827-841, 2002.
HM Zhang and WL Jin. A kinematic wave traffic flow model for mixed traffic. presented at TRB 2002 Annual Meeting. (In press, Transportation Research Record.), 2002.
S Benzoni-Gavage and RM Colombo. An n-population model for traffic flow. European Journal of Applied Mathematics, in Press, 2002.
E Chanut and C Buisson. Godunov discretization of a two-flow macroscopic model for mixed traffic with distinguished speeds and lengths. Preprint 82st Annual meeting TRB, 2003.
Z Zhu, G Chang, and T Wu. Numerical analysis of freeway traffic flow dynamics under multiclass drivers. Preprint 82st Annual meeting TRB, 2003.
S Logghe. Dynamic modeling of heterogeneous vehicular traffic. PhD thesis, Dept. of Civil Engineering, Catholic University of Leuven, 2003.
C F Daganzo. The cell transmission model. part ii: Network traffic. Trans. Res. B, 2 (29): 79-93, 1995b.
C F Daganzo. Multinomial Probit. Academic Press, 1979.
C F Daganzo. The cell transmission model: A dynamic representation of highway traffic consistent with the hydrodynamic theory. Trans. Res. B, 4 (28): 269-287, 1994.
C F Daganzo. A finite difference approximation of the kinematic wave model of traffic flow. Transportation Research, B (29): 261-276, 1995c.
J P Lebacque. The godunov scheme and what it means for first order traffic flow models. In J. B. Lesort, editor, 13th Int. Symp. on Transportation and Traffic Theory, pages 647-678, Elsevier, New York, 1996.
C F Daganzo. The lagged cell transmission model,. In A. Ceder, editor, 14th Int. Symp. on Transportation and Traffic Theory, pages 81-104, Pergamon, New York, N.Y., 1999a.
C F Daganzo. Remarks on traffic flow modeling and its applications. In J. B. Lesort, editor, 13th Int. Symp. on Transportation and Traffic Theory, pages 105-115, Elsevier, New York, 1999b.
R L LeVeque. Numerical methods for conservation laws. Birkhauser Verlag, 1993.
JC Muñoz and CF Daganzo. Moving bottlenecks: a theory grounded on experimental observation. In M.A.P. Taylor, editor, 15th Int. Symp. on Transportation and Traffic Theory, pages 441-462, Pergamon-Elsevier, Oxford,U.K., 2002.


1Department of Civil and Environmental Engineering,Transportation Group, University of California,Berkeley

File translated from TEX by TTHgold, version 3.59.
On 27 May 2004, 00:42.