# A Traffic Assignment Model Based on Link Densities

Authors: Louis de Grange; Matthieu Marechal; Felipe González
Journal: Journal of Advanced Transportation
 (2019)

---

## Abstract

A new model is presented that determines the traffic equilibrium on congested networks using link densities as well as costs in a manner consistent with the fundamental traffic equation. The solution so derived satisfies Wardrop’s first principle. This density-based approach recognizes traffic flow reductions that may occur when network traffic congestion is high; also, it estimates queue lengths (i.e., the number of vehicles on saturated links), and it explicitly takes into account the maximum flow a link can handle, which is defined by the fundamental traffic equation. The model is validated using traffic microsimulations and implemented on a typical Nguyen-Dupuis network to compare it with a flow-based approach. System optimal assignment model based on link densities is also presented.


---

## Body

## 1. Introduction

This paper develops and implements a deterministic model that solves the traffic equilibrium problem for a congested road network using network link densities. More specifically, the proposed density-based model solves a variational inequality whose cost vector is a function of the number of vehicles seeking to travel on the network at a given instant, consistent with the relationship between flow, cost (the inverse of speed), and density given by the fundamental traffic equation (flow=speed×density) for each network link. The solution arrived at gives a network traffic equilibrium that satisfies Wardrop’s first principle [1] and whose costs depend on link densities.Using the link densities to obtain the traffic equilibrium on a congested network has several important advantages. In general terms, the modelling of the problem is more realistic than that achieved by the classical flow-based traffic assignment formulations employing monotonically increasing cost functions. More specifically, the density-based approach has the following desirable features.(i)
It recognizes that link capacity (or maximum flow) is neither fixed nor exogenous but rather depends on the density level. In other words, the maximum flow that can cross a link varies as a function of link density. This prevents the flow from exceeding the link’s physical capacity. The capacities or maximum flows of the links in a network are determined by each link’s traffic speed and density as determined by the fundamental traffic equation.(ii)
It determines whether a reduced flow level on a given link is due to low latent demand for its use (e.g., low density) or rather to the presence of traffic congestion (e.g., high density) limiting the amount of flow able to use the link and generating queues and longer delays.(iii)
The average queue length on each link can be estimated.(iv)
By generating estimates of the impact of densities on the flow levels that can circulate on network links, the approach provides important data for use in the design of road networks, highway entrance and exit ramps, and road pricing systems based on traffic saturation levels. This is a distinct advantage over flow-based models, which estimate only flows.However, the density-based approach has a disadvantage: to find a solution which satisfies the flow conservation along the network is, in general, complicated. The implementation of numerical methods which allows for solutions which satisfy the flow conservation to be found will be the topic of future works.The remainder of this paper is divided into four sections and three appendices. Section2 contains a brief review of the literature on traffic assignment models, emphasizing the limits of classical deterministic flow-based models that assume a monotonically increasing relationship between flow and cost on each network link. Section 3 introduces our density-based traffic equilibrium model satisfying Wardrop’s first principle and discusses the existence of an equilibrium solution. This section also suggests an analytic expression for estimating the benefits of a road system project or policy using the proposed model in terms of consumer surplus before and after implementation. Section 4 uses a numerical example to compare our density-based model with a flow-based model that assumes a monotonically increasing relationship between link flows and costs. Section 5 summarizes our main conclusions.AppendixA validates the proposed model using microsimulations of a small road network; Appendix B gives a more formal demonstration in support of the existence theorems given in Section 3; and finally, Appendix C presents the system optimal assignment model based on link densities, which will allow us to advance in future new lines of research.


## 2. Literature Review

A widely accepted result in the study of vehicles on congested road networks is the so-called Wardrop equilibrium, also known as Wardrop’s first principle of route choice [1]. It is equivalent to the concept put forward by Knight [2] as a simple behavioural rule for describing the way trips are distributed across alternative routes under congested conditions.Wardrop’s first principle states that the vehicle travel time or cost for every network route used will be equal to or less than the time or cost that would be experienced on any unused route. Each user attempts to minimize noncooperatively their trip cost or time. Traffic flows that satisfy this principle are generally referred to as “user equilibrium” (UE) flows since each user chooses the route they find best. In short, a user-optimal equilibrium is reached when no user can reduce their travel time or cost on the network through unilateral action.The first mathematical model of user equilibrium on a congested road network assuming a monotonically increasing relationship between the flows and costs along the network links was formulated by Beckmann et al. [3], using a nonlinear optimization problem. However, traffic assignment problems based on link flows have generally been addressed using variational inequality, to include asymmetric cost functions, or multivariable cost functions. Notable among works that treat the formulation of the equilibrium problem, the existence of a solution and the solution algorithm are the following: Dafermos and Sparrow [4], Smith [5], Dafermos [6, 7], Florian and Spiess [8], Fisk and Nguyen [9], Fisk and Boyce [10], Nagurney [11], Hammond [12], Marcotte and Guelatt [13], Auchmuty [14], Gabriel and Bernstein [15], and Patriksson [16]. All these works represent mainly theoretical contributions and algorithmic implementation.A variation on Wardrop is the stochastic user equilibrium (SUE), in which no user can unilaterally change routes to improve their perceived travel cost or time. Some stochastic or probabilistic approaches are used, under a similar theoretical framework, to represent different phenomena, such as uncertainty, randomness, and/or heterogeneity of users and route alternatives. The precise formulation depends on how these factors are incorporated. Surveys of this class of models are found in Daganzo and Sheffi [17], Hazelton [18], Ramming [19], Prashker and Bekhor [20], Karoonsoontawong and Lin [21], Li and Huang [22], and Batista et al. [23]. These formulations constitute an extension of the deterministic equilibrium models. Lim and Kim [24] combine trip distribution and route choice model into a single feedback process within a single framework.Both UE and SUE models typically assume a monotonically increasing relationship between cost and flow (see [25, 26]). This ensures that they are practical to implement and their results are easy to analyze and interpret, but for heavily or hypercongested situations they are greatly lacking in realism.Another major limitation of flow-based approaches is that they allow the assignment of flow levels that exceed link capacity. Notice that Beckmann model does not specify cost or capacity functions, but it does assume that these functions must be monotonous and growing. Depending on the cost function considered for network links, the flow may exceed the defined capacity, for example, with increasing monotonic functions [27]. This unrealistic result has been interpreted as the additional wait time (or queuing time to enter the network), but the main problem is that it overestimates the number of vehicles which can circulate on the network’s links in a given time period.A third important drawback with flow-based approaches is that they assume link maximum flows are fixed, exogenous parameters, yet, as the fundamental traffic equation indicates, maximum link flow depends on density which in turn is related to the demand for link use. In other words, link maximum flow is more like a variable than a fixed parameter.It is precisely these various shortcomings that are remedied by our density-based model, set out below in Section3.Note that extensions to flow-based assignment models incorporating an additional restriction barring each link’s flow from exceeding a fixed and exogenous capacity have been developed by Larsson and Patriksson [28], Ferrari [29], and Nie et al. [30]. These modifications do avoid the problem of physically overloaded links, but they still assume a monotonically increasing flow-delay relationship that, as already mentioned, is unrealistic when congestion is high.Dynamic assignment models have been comprehensively studied in the specialized literature but are not directly related to the approach we propose here. Ran and Boyce [31], Peeta and Ziliakopoulus [32], and Tampere and Viti [33] provide extensive references and discuss developments in dynamic transportation network modelling and analysis and associated computational methods. Surveys have also been published by Boyce et al. [34] and Szeto and Lo [35] and, more recently, by Liu et al [36].Another approach that better captures the flow-delay relationship (which is increasing under low congestion and decreasing under high congestion) in the fundamental traffic equation uses traffic microsimulation models. A recent survey on the state of the art in traffic assignment models using microsimulation may be found in Calvert et al. [37]. These tools allow physical road network restrictions and the effects of density on traffic flow and speed to be incorporated into the modelling, but they are difficult to apply to large networks. Furthermore, microsimulation models do not use the traffic equilibrium concept since by definition they are dynamic formulations for individual behaviour that base route choice rather on heuristics.For this reason, microsimulation is an approach that allows us to validate our new model, as we explain in AppendixA. Microsimulation considers each of the vehicles moving within the network as the unit of analysis. Each vehicle makes decisions based on its destination, the behavior of other vehicles, and the travel times perceived between alternative routes that are the result of vehicle interactions. Flow-delay functions in the links are not required; however, these flow-delay functions can be estimated as a result of the individual interactions of the vehicles traveling in the different arcs of the microsimulated network. These interactions include the effect of density on traffic circulation, crossing blocks, etc. Therefore, microsimulation is an approach that we can consider as a benchmark for our new model in small networks. In larger networks, with many vehicles circulating simultaneously, microsimulation has limitations, especially due to the increase in alternative routes, or convergence of results. It is in these cases where we consider that our new model presents the greatest advantages.


## 3. Formulation of the Proposed Traffic Assignment Model

### 3.1. General Definitions

Traffic flows typically are not uniform but rather vary across space and time, making them difficult to describe. Nevertheless, their behaviour has traditionally been explained in terms of the relationships between just three traffic variables: flow, speed, and density (the lattermost also known as concentration).In a deterministic approach, mean speed (V) is defined as the average speed of multiple vehicles crossing a specific point or link. The flow or volume (f) is defined as the number of vehicles crossing a given road or highway segment during a given period of time. Finally, density (D) is defined as the number of vehicles occupying that segment.For roads or highways with multiple lanes, flow is expressed as vehicles per time unit per number of lanes [38]. The same is true of density, which is also expressed in terms of the total width of the route. A good survey of these models may be consulted in Wang et al. [39] and Kucharski and Drabicki [40].The oldest and probably simplest macroscopic traffic flow model was proposed by Greenshield (1935). It assumes that, under uninterrupted flow conditions, speed and density are linearly related. Although Greenshield’s formulation is considered to be the tool with the widest scope for traffic flow modelling due to its simplicity and reasonable goodness-of-fit, it has not been universally accepted given that it does not provide a good fit when congestion is low. The formal expression of the Greenshield model is as follows:(1)V=v0·1-DDjam→V=α-βD,α=v0,β=1Djamwhere V is the speed corresponding to the density level D, v0 is the free-flow speed, and Djam is the so-called jam density. This last term refers to the extreme traffic density level associated with completely stopped traffic flow, usually in the range of 185–250 vehicles per mile per lane. In other words, it is the density when flow is zero. A very recent study relating speed to vehicles’ use of space in an equilibrium context is reported in Martínez-Díaz and Pérez [41]. There are other, more complex specifications of the relationship between speed and density, but for our purposes Equation (1) is sufficient.From the fundamental traffic equation, we can relate the flowfa for a given network link a with the flow’s speed Va and density (Da) as fa=Va·Da. The speed can in turn be related with the link’s cost or time ca and its length la as Va=la/ca→ca=la/Va→caDa=la/VaDa. Finally, if we define Na as the number of vehicles along a, then Na=la·Da.An advantage of using the expressionVa=VaDa is that it allows the cost of a link to be defined as a function of its density rather than its flow and can thereby capture the typical situation depicted in Figure 1 in which congestion results in a reversal of the flow-delay curve so that for a given flow level there may be two travel cost or time alternatives, such as ca∗ and ca∗∗ in the figure. This relationship may be compared with the less realistic portrayal in Figure 2 that is typical of traffic equilibrium models incorporating congestion [3]. Clearly, the assumption in such models of a monotonically increasing flow-cost relationship limits their ability to accurately represent heavily congested conditions.Figure 1
Relatively realistic flow-delay relationship on road link.Figure 2
Relatively unrealistic flow-delay relationship on road link.Another advantage of using density instead of flow is that it permanently incorporates a restriction on the maximum flow of the links or routes in the network. Such a restriction is illustrated in Figure1, where flow cannot exceed famax. For each link a, this maximum is associated with a given density Da∗. In other words, there exists a density Da∗ at which the link’s maximum flow, defined as famax, is obtained. As an example, assuming a typical relationship between speed and density such as that defined by Greenshield (1935) and De Grange et al. [42], in which VaDa=αa-βaDa, where αa>0 and βa>0, it is easily shown that Da∗=αa/2βa and famax=αa2/4βa. The maximum density a link can support, defined to be the density at which the speed across the link is 0, is also directly derivable as Damax=αa/βa. Therefore, 0≤Da<αa/βa.Finally, the cost-density relationship is as shown in Figure3. Note that substituting Na for Da would not change the properties illustrated in the figure.Figure 3
Density-delay relationship on road link.


### 3.2. Analytic Formulation of Proposed Model Based on Link Densities

#### 3.2.1. Description of the Model

LetW be the set of all origin-destination (O-D) pairs, P the set of all routes across the network, and L the set of links. We define an incidence matrix Δ=δapa∈L,p∈P such that δap=1 if p passes through a; otherwise δap=0. For each route p there exists a unique O-D pair w∈Wsuch that p joins w.LetNp be the number of vehicles that travel on route p and Na the number of vehicles present on link a. We assume that the quantities Np and Na are related by the following relation:(2)Na=∑p∈PqapNpThe quantities qap=qap(N) satisfy the following: (1)
For alla∈L and p∈P, qap=0⇔δap=0.(2)
For alla∈L and p∈P, qap≥0.(3)
For allp∈P, ∑a∈Lqap=1.It is important to observe that ifqap=ta/tpδap, where ta is the time for travelling link a and tp=∑ataδap is the time for travelling route p, then we have Na/ta=∑p∈PδapNp/tp. Let fa be the flow of vehicles on link a and hp the flow of vehicles along route p; we have Na/ta=fa and Np/tp=hp, which implies that fa=∑p∈Pδaphp. Then the choice qap=ta/tpδap implies that flow conservation is satisfied.Actually the travel timeta depends on the quantity of vehicles Na on link a which makes the use of ta complicated.An expression forca is given by ta=la/va which is the time for travelling link a, with la the length of link a and va the average speed of the vehicles along link a. A typical expression for va is given by va=αa-βaDa, with αa and βa two positive constants and Da=Na/la the density of vehicles present on link a. Then we obtain (3)caNa=laαa-βaDa=laαa-βaNa/laGiven a vector of the quantities of vehicles on routes denoted N=Npp∈P, we define the cost of each route p as cpNp=∑a∈LcaNaδap, where caNa is a positive, continuous, and increasing function on the interval 0,Namax. The quantity Namax is the maximum amount of vehicles that can be present on link a, and we have(4)limNa→NamaxcaNa=+∞Based on the foregoing definitions, we can now express Wardrop’s first principle analytically as the conditions set out in (5) below, where λw is the cost of travelling the routes actually used that connect O-D pair w, and μp≥0 is the additional cost of travelling routes not used (the latter, according to the principle, having a higher cost). Consider(5)∑a∈LcaNa·δap=λw+μp,∀w∈W,∀p∈PwNa=∑p∈PNpqap∀a∈LNw=∑p∈PwNp∀w∈WNp≥0∀p∈Pμp≥0∀p∈PNpμp=0∀p∈PNa<Namax∀a∈LIn the third equation Nw is the quantity of vehicles that are travelling the origin-destination pair w and Pw is the set of routes joining the pair origin-destination w.The solution to this system of equations gives the traffic equilibrium based on densities that we are seeking. Since we assumeca(Namax)=+∞, the inequality relating Na with Namax is strict.


#### 3.2.2. Existence of a Solution

To prove the existence of a solution to the system of equations set forth in (5) that is consistent with Wardrop’s first principle, we adapt the system to the variational inequality format. To this end, we first define a set of feasibles K as(6)K=N=Npp∈P∣Na=∑p∈PNpqap,Np≥0,Na<Namax,Nw=∑p∈PwNpFinding an equilibrium solution consistent with Wardrop’s first principle is equivalent to solving the following variational inequality, that is, finding a vector of quantities of vehicles on routes N∗∈K such that, for all N∈K, we have ∑pcp(N∗)(Np-Np∗)≥0. Given the vector field C=CN=Cp(N)p∈P, the problem is to find a vector N∗∈K such that, for all N∈K, we have CN∗.N-N∗≥0. This latter form of the variational inequality will denote VI(C,K), where C is the vector field and K is the set of feasibles, both previously defined.It should be noted thatC is not a conservative vector field given that ∂cp/∂Np′=∑a∈L∂Na/∂Np′ca′(Na)δap. This expression is not symmetric with respect to p and p′ in general, so the Wardrop conditions are not in general the optimality conditions of an optimization problem. This implies that we cannot write an equivalent optimization problem (such as Beckmann’s transformation) for the density-based model.Since the setK is not in general closed due to the strict inequality Na<Namax, we define the set Kε for all ε>0 as (7)Kε=N=Npp∈p∣Na=∑p∈PNpqap,Np≥0,Na≤Namax-ε,Nw=∑p∈PwNpObserve that Kε⊂K, Kε⊂Kε′ if 0<ε′<ε, and also ⋃ε>0Kε=K. This implies that when ε>0 is small, Kε is a good approximation of the set K. Assume that the vector field C is continuous in set K. Then it is also continuous in set Kε for ε>0, given that Kε⊂K.The following theorem gives an existence result for the inequalityVIC,Kε, proving that there exists an N∗∈Kε such that, for all N∈Kε, we have CN∗.N-N∗≥0.Theorem 1 (letε>0).
IfKε≠⌀, then the variational inequality VIC,Kε has at least one solution.Proof.
Recall that vector fieldC is continuous in set Kε. Observe further that Kε is closed and convex. We now prove that it is bounded.
Letp be a route and a a link such that δap=1. Given an N∈Kε, the following inequality is true:(8)Namax-ε≥Na=∑p′∈PNp′qap′≥NpqapThis implies that, for allaonp, Np≤1/qapNamax-ε. Then Np≤min⁡{1/qapNamax-ε∣δap=1}. Furthermore, we know that Np≥0. Finally, we have (9)0≤Np≤min⁡1qapNamax-ε∣δap=1This expression is satisfied for all p, which proves that Kε is bounded. Since it is also closed, we deduce that it is compact (i.e., closed and bounded). And, given that it is convex and (by hypothesis) nonempty as well, we conclude by Harker and Pang [43] that the variational inequality VIC,Kε has at least one solution.However, being a solution ofVIC,Kε is not a sufficient condition for satisfying Wardrop’s first principle given that one of the Na≤Namax-ε restrictions may be active, which would imply the existence of a Lagrange multiplier that does not appear in the system of equations (5) expressing the principle. We must therefore also prove the existence of a solution of VIC,K. This is done in Theorem 2 below.Before setting out the formal proof, however, we defineK- as the closure of set K:(10)K¯=N=Npp∈P∣Na=∑p∈PNpqap,Np≥0,Na≤Namax,Nw=∑p∈PwNpTheorem 2 (assume thatK≠⌀).
IfK=K-, or if, for all N∗∈K-∖K, for every sequence Nn∈K that satisfies limn→∞Nn=N∗, there exists an element N∈K such that(11)limn→∞CNn.N-Nn<0then VIC,K has at least one solution.Proof.
Given thatK is a bounded and convex set, the set K- is compact and convex.
IfK=K-, then K is a compact, convex set. Given that C is continuous in K, we deduce that VIC,K has at least one solution.
Assume that≠K¯; that is, K¯∖K≠⌀. Given that K≠⌀, then K1/n≠⌀ for any sufficiently large n, and, therefore, by Theorem 1, VIC,K1/n has at least one solution.
LetNn be a solution of VIC,K1/n. Given that the set K- is compact, the sequence Nn has a subsequence Nnk that converges. We denote by N∗∈K¯ the limit of the sequence Nnk. Consider the following two cases:
Case 1 ( N ∗ ∈ K). Let N∈K. Given that K=⋃n≥1K1/n, there exists a k0≥1 such that, for all k≥k0, N∈K1/nk. Given that Nnk is a solution of VIC,K1/nk, we have CNnk.N-Nnk≥0. Since C is a continuous vector field in K, we have(12)CN∗.N-N∗=limk→∞CNnk.N-Nnk≥0Then N∗ is a solution of VIC,K.
Case 2 ( N ∗ ∈ K ¯ ∖ K). Let N∈K such that limk→∞CNnk.N-Nnk<0 (N exists by hypothesis since limk→∞Nnk=N∗ and N∗∈K¯∖K). Given that ∈K1/nk, for all sufficiently large k and that Nnk is a solution of VIC,K1/nk, then CNnk.N-Nnk≥0 for any sufficiently large k, which contradicts the inequality limk→∞CNnk.N-Nnk<0. Therefore, Case 2 cannot occur.
Thus, only Case 1 can occur, which implies the existence of at least one solution ofVIC,K.A proposition for a general example of a network that satisfies condition (11) is given in Appendix B.About the uniqueness, the following theorem gives us that the quantity of vehicles of arc is unique and, then, the cost of the route is also unique.Theorem 3.
LetN∗ and M∗ be two solutions of VIC,K. For each link a, we have Na∗=Ma∗, and for each route p, we have cpN∗=cpM∗.Proof (LetN∈K).
We haveCN∗.N-N∗≥0 which implies that ∑pcpN∗.Np-Np∗≥0. Given that cpNp=∑acaNaδap, we have (13)∑pcpN∗.Np-Np∗=∑p∑acaNa∗δap.Np-Np∗=∑acaNa∗∑pδapNp-Np∗=∑acaNa∗·Na-Na∗This implies that(14)∀N∈K′,∑acaNa∗·Na-Na∗≥0Where (15)K′=N′=Na∣∃N∈K,∀a∈L,Na=∑pNpqapDefine C′(N′)=caNaa∈L. From what we stand before, the vector Na∗ is a solution of VIC′,K′. By the same way, the vector Ma∗ is a solution of VIC′,K′. Given that each function ca is strictly increasing, we deduce that the vector field C′ is strictly monotone. Moreover, it is clear that K′ is a convex set; then VIC′,K′ admits a unique solution. We deduce that, for each arc a, we have Na∗=Ma∗.
We deduce that, for each arca, we have caNa∗=caMa∗, and then cpN∗=cpM∗.A big issue for this model is the fact that if we considerqap=ta/tpδap (this choice allows for flow conservation to be satisfied), then qap depend on Na which depends on qap. In what follows, we propose an algorithm for constructing iteratively a solution of VI(C,K) with qap=ta/tpδap. In the sequel, we consider αa>0 and βa>0 such that the average speed on link a is given by va=αa-βaDa, with Da=Na/la the density of vehicles present on link a. In this case we have ta=la/αa-βaDa.We consider the functionta(Na)=la/αa-βaDa=la2/laαa-βaNa, which is the average time for travelling the link a if there are Na vehicles, and the function tpN=∑a∈LtaNaδap which is the average time for travelling the route p if the vector of quantities of vehicles is N=Npp.Algorithm 4.
We construct the sequenceNn by the following way.
Step0. Let ta0=la/αa, tp0=∑ata0δap, qap0=ta0/tp0δap, n=1. Let ε>0.
Step 1. Given the quantity qapn-1, consider the set(16)Kn=N=Npp∈P∣Na=∑p∈PNpqapn-1,Np≥0,Na<Namax,Nw=∑p∈PwNp.Construct Nn=Npnp∈P as a solution of VI(C,Kn).
Step2. Consider Nan=∑p∈PNpnqapn-1 the quantity of vehicles on link a, fa=Nan/ta(Nan) the vehicles flow on link a, and hp=Npn/∑ata(Nan)δap the vehicles flow on route p. If ∑a∈Lfa-∑p∈Phpδap2/∑a∈Lfa2<ε2, then stop; else, go to step 3.
Step3. Construct (Na)a as a solution of the equations Na=∑p∈Pta(Na)/∑a′∈Lta′Na′δa′pNpnδap. Consider qapn=taNa/∑a′∈Lta′Na′δa′pδap, n=n+1, and go to Step 1.
Step 2 tests whether the relative error in the flow conservation law is small enough. This algorithm has been implemented to obtain the results of the following section.


### 3.3. Estimation of Road Project Benefits and Summary of Model Characteristics

The proposed model can be used to conduct a social cost-benefit analysis of a road system project. If we letC0w be the equilibrium cost before the project is implemented and let C1w be the equilibrium cost after implementation, the change in consumer surplus (∆EC) is estimated directly by the following formula:(17)ΔEC=∑w∫C0wC1wTwdCw=∑w∫C0wC1wNwCwdCw=∑wNwln⁡C1wC0wwhere Tw is the trip matrix (vehicle flows per hour). In the classical flow-based model, on the other hand, where Tw is exogenous, the change in consumer surplus is given by (18)ΔEC=TwC1w-C0wBriefly, in (17) the social benefit of a transport project or policy derives from the greater number of individuals benefiting in the same period of time whereas in (18) the social benefit consists in the same number of individuals experiencing lower trip costs.A summary of the main characteristics of the classical flow-based and proposed density-based models and the differences between them is laid out in Table1.Table 1
Summary of Main Differences between Flow-Based and Density-Based Models.
Characteristic Flow-Based Model Density-Based Model General concept Assigns vehicles per hour among the different network links for a representative time period. Assigns vehicles per kilometre among the different network links for a representative instant in time.  Equilibrium condition Satisfies Wardrop’s first principle for all network routes. Satisfies Wardrop’s first principle for all network routes.  State of system Assumes that all trips in the trip matrix are assigned to the network and that all trips enter and exit within a given modelled period. Assumes that the total number of vehicles on the network at a given instant is the same at the instant immediately preceding and immediately following.  Link capacity Each link is assumed to have a fixed, exogenous capacity or maximum flow. This capacity will often be exceeded. Each link’s maximum flow, rather than being a fixed parameter, depends on vehicle density and speed across it and will vary with traffic conditions. Maximum flow is finite.  Trip matrix Assumes a trip matrix (flows between O-D pairs) for the period modelled that is fixed and exogenous to equilibrium cost. Assumes the number of vehicles for the instant modelled is fixed and exogenous but the trip matrix (flows between O-D pairs) is a result of the equilibrium.  Conservation of flow By construction, assumes conservation of flow at all network nodes including cases where route time or cost is greater than the period modelled (i.e., there are travellers who do not arrive at their destination). Withqap=ta/tpδap the conservation of flow is satisfied.  Densities and queue lengths under congestion Does not satisfactorily estimate either densities or queue lengths under high congestion. Always correctly estimates densities and queue lengths, whether under low or high congestion.  Fundamental traffic equation Under high congestion, thef=V·D relationship does not hold. By construction, thef=V·D relationship always holds.  Estimation of benefits of road system project or policy Benefits are estimated in terms of network user time savings. Benefits are estimated as the change in consumer surplus.


## 3.1. General Definitions

Traffic flows typically are not uniform but rather vary across space and time, making them difficult to describe. Nevertheless, their behaviour has traditionally been explained in terms of the relationships between just three traffic variables: flow, speed, and density (the lattermost also known as concentration).In a deterministic approach, mean speed (V) is defined as the average speed of multiple vehicles crossing a specific point or link. The flow or volume (f) is defined as the number of vehicles crossing a given road or highway segment during a given period of time. Finally, density (D) is defined as the number of vehicles occupying that segment.For roads or highways with multiple lanes, flow is expressed as vehicles per time unit per number of lanes [38]. The same is true of density, which is also expressed in terms of the total width of the route. A good survey of these models may be consulted in Wang et al. [39] and Kucharski and Drabicki [40].The oldest and probably simplest macroscopic traffic flow model was proposed by Greenshield (1935). It assumes that, under uninterrupted flow conditions, speed and density are linearly related. Although Greenshield’s formulation is considered to be the tool with the widest scope for traffic flow modelling due to its simplicity and reasonable goodness-of-fit, it has not been universally accepted given that it does not provide a good fit when congestion is low. The formal expression of the Greenshield model is as follows:(1)V=v0·1-DDjam→V=α-βD,α=v0,β=1Djamwhere V is the speed corresponding to the density level D, v0 is the free-flow speed, and Djam is the so-called jam density. This last term refers to the extreme traffic density level associated with completely stopped traffic flow, usually in the range of 185–250 vehicles per mile per lane. In other words, it is the density when flow is zero. A very recent study relating speed to vehicles’ use of space in an equilibrium context is reported in Martínez-Díaz and Pérez [41]. There are other, more complex specifications of the relationship between speed and density, but for our purposes Equation (1) is sufficient.From the fundamental traffic equation, we can relate the flowfa for a given network link a with the flow’s speed Va and density (Da) as fa=Va·Da. The speed can in turn be related with the link’s cost or time ca and its length la as Va=la/ca→ca=la/Va→caDa=la/VaDa. Finally, if we define Na as the number of vehicles along a, then Na=la·Da.An advantage of using the expressionVa=VaDa is that it allows the cost of a link to be defined as a function of its density rather than its flow and can thereby capture the typical situation depicted in Figure 1 in which congestion results in a reversal of the flow-delay curve so that for a given flow level there may be two travel cost or time alternatives, such as ca∗ and ca∗∗ in the figure. This relationship may be compared with the less realistic portrayal in Figure 2 that is typical of traffic equilibrium models incorporating congestion [3]. Clearly, the assumption in such models of a monotonically increasing flow-cost relationship limits their ability to accurately represent heavily congested conditions.Figure 1
Relatively realistic flow-delay relationship on road link.Figure 2
Relatively unrealistic flow-delay relationship on road link.Another advantage of using density instead of flow is that it permanently incorporates a restriction on the maximum flow of the links or routes in the network. Such a restriction is illustrated in Figure1, where flow cannot exceed famax. For each link a, this maximum is associated with a given density Da∗. In other words, there exists a density Da∗ at which the link’s maximum flow, defined as famax, is obtained. As an example, assuming a typical relationship between speed and density such as that defined by Greenshield (1935) and De Grange et al. [42], in which VaDa=αa-βaDa, where αa>0 and βa>0, it is easily shown that Da∗=αa/2βa and famax=αa2/4βa. The maximum density a link can support, defined to be the density at which the speed across the link is 0, is also directly derivable as Damax=αa/βa. Therefore, 0≤Da<αa/βa.Finally, the cost-density relationship is as shown in Figure3. Note that substituting Na for Da would not change the properties illustrated in the figure.Figure 3
Density-delay relationship on road link.


## 3.2. Analytic Formulation of Proposed Model Based on Link Densities

### 3.2.1. Description of the Model

LetW be the set of all origin-destination (O-D) pairs, P the set of all routes across the network, and L the set of links. We define an incidence matrix Δ=δapa∈L,p∈P such that δap=1 if p passes through a; otherwise δap=0. For each route p there exists a unique O-D pair w∈Wsuch that p joins w.LetNp be the number of vehicles that travel on route p and Na the number of vehicles present on link a. We assume that the quantities Np and Na are related by the following relation:(2)Na=∑p∈PqapNpThe quantities qap=qap(N) satisfy the following: (1)
For alla∈L and p∈P, qap=0⇔δap=0.(2)
For alla∈L and p∈P, qap≥0.(3)
For allp∈P, ∑a∈Lqap=1.It is important to observe that ifqap=ta/tpδap, where ta is the time for travelling link a and tp=∑ataδap is the time for travelling route p, then we have Na/ta=∑p∈PδapNp/tp. Let fa be the flow of vehicles on link a and hp the flow of vehicles along route p; we have Na/ta=fa and Np/tp=hp, which implies that fa=∑p∈Pδaphp. Then the choice qap=ta/tpδap implies that flow conservation is satisfied.Actually the travel timeta depends on the quantity of vehicles Na on link a which makes the use of ta complicated.An expression forca is given by ta=la/va which is the time for travelling link a, with la the length of link a and va the average speed of the vehicles along link a. A typical expression for va is given by va=αa-βaDa, with αa and βa two positive constants and Da=Na/la the density of vehicles present on link a. Then we obtain (3)caNa=laαa-βaDa=laαa-βaNa/laGiven a vector of the quantities of vehicles on routes denoted N=Npp∈P, we define the cost of each route p as cpNp=∑a∈LcaNaδap, where caNa is a positive, continuous, and increasing function on the interval 0,Namax. The quantity Namax is the maximum amount of vehicles that can be present on link a, and we have(4)limNa→NamaxcaNa=+∞Based on the foregoing definitions, we can now express Wardrop’s first principle analytically as the conditions set out in (5) below, where λw is the cost of travelling the routes actually used that connect O-D pair w, and μp≥0 is the additional cost of travelling routes not used (the latter, according to the principle, having a higher cost). Consider(5)∑a∈LcaNa·δap=λw+μp,∀w∈W,∀p∈PwNa=∑p∈PNpqap∀a∈LNw=∑p∈PwNp∀w∈WNp≥0∀p∈Pμp≥0∀p∈PNpμp=0∀p∈PNa<Namax∀a∈LIn the third equation Nw is the quantity of vehicles that are travelling the origin-destination pair w and Pw is the set of routes joining the pair origin-destination w.The solution to this system of equations gives the traffic equilibrium based on densities that we are seeking. Since we assumeca(Namax)=+∞, the inequality relating Na with Namax is strict.


### 3.2.2. Existence of a Solution

To prove the existence of a solution to the system of equations set forth in (5) that is consistent with Wardrop’s first principle, we adapt the system to the variational inequality format. To this end, we first define a set of feasibles K as(6)K=N=Npp∈P∣Na=∑p∈PNpqap,Np≥0,Na<Namax,Nw=∑p∈PwNpFinding an equilibrium solution consistent with Wardrop’s first principle is equivalent to solving the following variational inequality, that is, finding a vector of quantities of vehicles on routes N∗∈K such that, for all N∈K, we have ∑pcp(N∗)(Np-Np∗)≥0. Given the vector field C=CN=Cp(N)p∈P, the problem is to find a vector N∗∈K such that, for all N∈K, we have CN∗.N-N∗≥0. This latter form of the variational inequality will denote VI(C,K), where C is the vector field and K is the set of feasibles, both previously defined.It should be noted thatC is not a conservative vector field given that ∂cp/∂Np′=∑a∈L∂Na/∂Np′ca′(Na)δap. This expression is not symmetric with respect to p and p′ in general, so the Wardrop conditions are not in general the optimality conditions of an optimization problem. This implies that we cannot write an equivalent optimization problem (such as Beckmann’s transformation) for the density-based model.Since the setK is not in general closed due to the strict inequality Na<Namax, we define the set Kε for all ε>0 as (7)Kε=N=Npp∈p∣Na=∑p∈PNpqap,Np≥0,Na≤Namax-ε,Nw=∑p∈PwNpObserve that Kε⊂K, Kε⊂Kε′ if 0<ε′<ε, and also ⋃ε>0Kε=K. This implies that when ε>0 is small, Kε is a good approximation of the set K. Assume that the vector field C is continuous in set K. Then it is also continuous in set Kε for ε>0, given that Kε⊂K.The following theorem gives an existence result for the inequalityVIC,Kε, proving that there exists an N∗∈Kε such that, for all N∈Kε, we have CN∗.N-N∗≥0.Theorem 1 (letε>0).
IfKε≠⌀, then the variational inequality VIC,Kε has at least one solution.Proof.
Recall that vector fieldC is continuous in set Kε. Observe further that Kε is closed and convex. We now prove that it is bounded.
Letp be a route and a a link such that δap=1. Given an N∈Kε, the following inequality is true:(8)Namax-ε≥Na=∑p′∈PNp′qap′≥NpqapThis implies that, for allaonp, Np≤1/qapNamax-ε. Then Np≤min⁡{1/qapNamax-ε∣δap=1}. Furthermore, we know that Np≥0. Finally, we have (9)0≤Np≤min⁡1qapNamax-ε∣δap=1This expression is satisfied for all p, which proves that Kε is bounded. Since it is also closed, we deduce that it is compact (i.e., closed and bounded). And, given that it is convex and (by hypothesis) nonempty as well, we conclude by Harker and Pang [43] that the variational inequality VIC,Kε has at least one solution.However, being a solution ofVIC,Kε is not a sufficient condition for satisfying Wardrop’s first principle given that one of the Na≤Namax-ε restrictions may be active, which would imply the existence of a Lagrange multiplier that does not appear in the system of equations (5) expressing the principle. We must therefore also prove the existence of a solution of VIC,K. This is done in Theorem 2 below.Before setting out the formal proof, however, we defineK- as the closure of set K:(10)K¯=N=Npp∈P∣Na=∑p∈PNpqap,Np≥0,Na≤Namax,Nw=∑p∈PwNpTheorem 2 (assume thatK≠⌀).
IfK=K-, or if, for all N∗∈K-∖K, for every sequence Nn∈K that satisfies limn→∞Nn=N∗, there exists an element N∈K such that(11)limn→∞CNn.N-Nn<0then VIC,K has at least one solution.Proof.
Given thatK is a bounded and convex set, the set K- is compact and convex.
IfK=K-, then K is a compact, convex set. Given that C is continuous in K, we deduce that VIC,K has at least one solution.
Assume that≠K¯; that is, K¯∖K≠⌀. Given that K≠⌀, then K1/n≠⌀ for any sufficiently large n, and, therefore, by Theorem 1, VIC,K1/n has at least one solution.
LetNn be a solution of VIC,K1/n. Given that the set K- is compact, the sequence Nn has a subsequence Nnk that converges. We denote by N∗∈K¯ the limit of the sequence Nnk. Consider the following two cases:
Case 1 ( N ∗ ∈ K). Let N∈K. Given that K=⋃n≥1K1/n, there exists a k0≥1 such that, for all k≥k0, N∈K1/nk. Given that Nnk is a solution of VIC,K1/nk, we have CNnk.N-Nnk≥0. Since C is a continuous vector field in K, we have(12)CN∗.N-N∗=limk→∞CNnk.N-Nnk≥0Then N∗ is a solution of VIC,K.
Case 2 ( N ∗ ∈ K ¯ ∖ K). Let N∈K such that limk→∞CNnk.N-Nnk<0 (N exists by hypothesis since limk→∞Nnk=N∗ and N∗∈K¯∖K). Given that ∈K1/nk, for all sufficiently large k and that Nnk is a solution of VIC,K1/nk, then CNnk.N-Nnk≥0 for any sufficiently large k, which contradicts the inequality limk→∞CNnk.N-Nnk<0. Therefore, Case 2 cannot occur.
Thus, only Case 1 can occur, which implies the existence of at least one solution ofVIC,K.A proposition for a general example of a network that satisfies condition (11) is given in Appendix B.About the uniqueness, the following theorem gives us that the quantity of vehicles of arc is unique and, then, the cost of the route is also unique.Theorem 3.
LetN∗ and M∗ be two solutions of VIC,K. For each link a, we have Na∗=Ma∗, and for each route p, we have cpN∗=cpM∗.Proof (LetN∈K).
We haveCN∗.N-N∗≥0 which implies that ∑pcpN∗.Np-Np∗≥0. Given that cpNp=∑acaNaδap, we have (13)∑pcpN∗.Np-Np∗=∑p∑acaNa∗δap.Np-Np∗=∑acaNa∗∑pδapNp-Np∗=∑acaNa∗·Na-Na∗This implies that(14)∀N∈K′,∑acaNa∗·Na-Na∗≥0Where (15)K′=N′=Na∣∃N∈K,∀a∈L,Na=∑pNpqapDefine C′(N′)=caNaa∈L. From what we stand before, the vector Na∗ is a solution of VIC′,K′. By the same way, the vector Ma∗ is a solution of VIC′,K′. Given that each function ca is strictly increasing, we deduce that the vector field C′ is strictly monotone. Moreover, it is clear that K′ is a convex set; then VIC′,K′ admits a unique solution. We deduce that, for each arc a, we have Na∗=Ma∗.
We deduce that, for each arca, we have caNa∗=caMa∗, and then cpN∗=cpM∗.A big issue for this model is the fact that if we considerqap=ta/tpδap (this choice allows for flow conservation to be satisfied), then qap depend on Na which depends on qap. In what follows, we propose an algorithm for constructing iteratively a solution of VI(C,K) with qap=ta/tpδap. In the sequel, we consider αa>0 and βa>0 such that the average speed on link a is given by va=αa-βaDa, with Da=Na/la the density of vehicles present on link a. In this case we have ta=la/αa-βaDa.We consider the functionta(Na)=la/αa-βaDa=la2/laαa-βaNa, which is the average time for travelling the link a if there are Na vehicles, and the function tpN=∑a∈LtaNaδap which is the average time for travelling the route p if the vector of quantities of vehicles is N=Npp.Algorithm 4.
We construct the sequenceNn by the following way.
Step0. Let ta0=la/αa, tp0=∑ata0δap, qap0=ta0/tp0δap, n=1. Let ε>0.
Step 1. Given the quantity qapn-1, consider the set(16)Kn=N=Npp∈P∣Na=∑p∈PNpqapn-1,Np≥0,Na<Namax,Nw=∑p∈PwNp.Construct Nn=Npnp∈P as a solution of VI(C,Kn).
Step2. Consider Nan=∑p∈PNpnqapn-1 the quantity of vehicles on link a, fa=Nan/ta(Nan) the vehicles flow on link a, and hp=Npn/∑ata(Nan)δap the vehicles flow on route p. If ∑a∈Lfa-∑p∈Phpδap2/∑a∈Lfa2<ε2, then stop; else, go to step 3.
Step3. Construct (Na)a as a solution of the equations Na=∑p∈Pta(Na)/∑a′∈Lta′Na′δa′pNpnδap. Consider qapn=taNa/∑a′∈Lta′Na′δa′pδap, n=n+1, and go to Step 1.
Step 2 tests whether the relative error in the flow conservation law is small enough. This algorithm has been implemented to obtain the results of the following section.


## 3.2.1. Description of the Model

LetW be the set of all origin-destination (O-D) pairs, P the set of all routes across the network, and L the set of links. We define an incidence matrix Δ=δapa∈L,p∈P such that δap=1 if p passes through a; otherwise δap=0. For each route p there exists a unique O-D pair w∈Wsuch that p joins w.LetNp be the number of vehicles that travel on route p and Na the number of vehicles present on link a. We assume that the quantities Np and Na are related by the following relation:(2)Na=∑p∈PqapNpThe quantities qap=qap(N) satisfy the following: (1)
For alla∈L and p∈P, qap=0⇔δap=0.(2)
For alla∈L and p∈P, qap≥0.(3)
For allp∈P, ∑a∈Lqap=1.It is important to observe that ifqap=ta/tpδap, where ta is the time for travelling link a and tp=∑ataδap is the time for travelling route p, then we have Na/ta=∑p∈PδapNp/tp. Let fa be the flow of vehicles on link a and hp the flow of vehicles along route p; we have Na/ta=fa and Np/tp=hp, which implies that fa=∑p∈Pδaphp. Then the choice qap=ta/tpδap implies that flow conservation is satisfied.Actually the travel timeta depends on the quantity of vehicles Na on link a which makes the use of ta complicated.An expression forca is given by ta=la/va which is the time for travelling link a, with la the length of link a and va the average speed of the vehicles along link a. A typical expression for va is given by va=αa-βaDa, with αa and βa two positive constants and Da=Na/la the density of vehicles present on link a. Then we obtain (3)caNa=laαa-βaDa=laαa-βaNa/laGiven a vector of the quantities of vehicles on routes denoted N=Npp∈P, we define the cost of each route p as cpNp=∑a∈LcaNaδap, where caNa is a positive, continuous, and increasing function on the interval 0,Namax. The quantity Namax is the maximum amount of vehicles that can be present on link a, and we have(4)limNa→NamaxcaNa=+∞Based on the foregoing definitions, we can now express Wardrop’s first principle analytically as the conditions set out in (5) below, where λw is the cost of travelling the routes actually used that connect O-D pair w, and μp≥0 is the additional cost of travelling routes not used (the latter, according to the principle, having a higher cost). Consider(5)∑a∈LcaNa·δap=λw+μp,∀w∈W,∀p∈PwNa=∑p∈PNpqap∀a∈LNw=∑p∈PwNp∀w∈WNp≥0∀p∈Pμp≥0∀p∈PNpμp=0∀p∈PNa<Namax∀a∈LIn the third equation Nw is the quantity of vehicles that are travelling the origin-destination pair w and Pw is the set of routes joining the pair origin-destination w.The solution to this system of equations gives the traffic equilibrium based on densities that we are seeking. Since we assumeca(Namax)=+∞, the inequality relating Na with Namax is strict.


## 3.2.2. Existence of a Solution

To prove the existence of a solution to the system of equations set forth in (5) that is consistent with Wardrop’s first principle, we adapt the system to the variational inequality format. To this end, we first define a set of feasibles K as(6)K=N=Npp∈P∣Na=∑p∈PNpqap,Np≥0,Na<Namax,Nw=∑p∈PwNpFinding an equilibrium solution consistent with Wardrop’s first principle is equivalent to solving the following variational inequality, that is, finding a vector of quantities of vehicles on routes N∗∈K such that, for all N∈K, we have ∑pcp(N∗)(Np-Np∗)≥0. Given the vector field C=CN=Cp(N)p∈P, the problem is to find a vector N∗∈K such that, for all N∈K, we have CN∗.N-N∗≥0. This latter form of the variational inequality will denote VI(C,K), where C is the vector field and K is the set of feasibles, both previously defined.It should be noted thatC is not a conservative vector field given that ∂cp/∂Np′=∑a∈L∂Na/∂Np′ca′(Na)δap. This expression is not symmetric with respect to p and p′ in general, so the Wardrop conditions are not in general the optimality conditions of an optimization problem. This implies that we cannot write an equivalent optimization problem (such as Beckmann’s transformation) for the density-based model.Since the setK is not in general closed due to the strict inequality Na<Namax, we define the set Kε for all ε>0 as (7)Kε=N=Npp∈p∣Na=∑p∈PNpqap,Np≥0,Na≤Namax-ε,Nw=∑p∈PwNpObserve that Kε⊂K, Kε⊂Kε′ if 0<ε′<ε, and also ⋃ε>0Kε=K. This implies that when ε>0 is small, Kε is a good approximation of the set K. Assume that the vector field C is continuous in set K. Then it is also continuous in set Kε for ε>0, given that Kε⊂K.The following theorem gives an existence result for the inequalityVIC,Kε, proving that there exists an N∗∈Kε such that, for all N∈Kε, we have CN∗.N-N∗≥0.Theorem 1 (letε>0).
IfKε≠⌀, then the variational inequality VIC,Kε has at least one solution.Proof.
Recall that vector fieldC is continuous in set Kε. Observe further that Kε is closed and convex. We now prove that it is bounded.
Letp be a route and a a link such that δap=1. Given an N∈Kε, the following inequality is true:(8)Namax-ε≥Na=∑p′∈PNp′qap′≥NpqapThis implies that, for allaonp, Np≤1/qapNamax-ε. Then Np≤min⁡{1/qapNamax-ε∣δap=1}. Furthermore, we know that Np≥0. Finally, we have (9)0≤Np≤min⁡1qapNamax-ε∣δap=1This expression is satisfied for all p, which proves that Kε is bounded. Since it is also closed, we deduce that it is compact (i.e., closed and bounded). And, given that it is convex and (by hypothesis) nonempty as well, we conclude by Harker and Pang [43] that the variational inequality VIC,Kε has at least one solution.However, being a solution ofVIC,Kε is not a sufficient condition for satisfying Wardrop’s first principle given that one of the Na≤Namax-ε restrictions may be active, which would imply the existence of a Lagrange multiplier that does not appear in the system of equations (5) expressing the principle. We must therefore also prove the existence of a solution of VIC,K. This is done in Theorem 2 below.Before setting out the formal proof, however, we defineK- as the closure of set K:(10)K¯=N=Npp∈P∣Na=∑p∈PNpqap,Np≥0,Na≤Namax,Nw=∑p∈PwNpTheorem 2 (assume thatK≠⌀).
IfK=K-, or if, for all N∗∈K-∖K, for every sequence Nn∈K that satisfies limn→∞Nn=N∗, there exists an element N∈K such that(11)limn→∞CNn.N-Nn<0then VIC,K has at least one solution.Proof.
Given thatK is a bounded and convex set, the set K- is compact and convex.
IfK=K-, then K is a compact, convex set. Given that C is continuous in K, we deduce that VIC,K has at least one solution.
Assume that≠K¯; that is, K¯∖K≠⌀. Given that K≠⌀, then K1/n≠⌀ for any sufficiently large n, and, therefore, by Theorem 1, VIC,K1/n has at least one solution.
LetNn be a solution of VIC,K1/n. Given that the set K- is compact, the sequence Nn has a subsequence Nnk that converges. We denote by N∗∈K¯ the limit of the sequence Nnk. Consider the following two cases:
Case 1 ( N ∗ ∈ K). Let N∈K. Given that K=⋃n≥1K1/n, there exists a k0≥1 such that, for all k≥k0, N∈K1/nk. Given that Nnk is a solution of VIC,K1/nk, we have CNnk.N-Nnk≥0. Since C is a continuous vector field in K, we have(12)CN∗.N-N∗=limk→∞CNnk.N-Nnk≥0Then N∗ is a solution of VIC,K.
Case 2 ( N ∗ ∈ K ¯ ∖ K). Let N∈K such that limk→∞CNnk.N-Nnk<0 (N exists by hypothesis since limk→∞Nnk=N∗ and N∗∈K¯∖K). Given that ∈K1/nk, for all sufficiently large k and that Nnk is a solution of VIC,K1/nk, then CNnk.N-Nnk≥0 for any sufficiently large k, which contradicts the inequality limk→∞CNnk.N-Nnk<0. Therefore, Case 2 cannot occur.
Thus, only Case 1 can occur, which implies the existence of at least one solution ofVIC,K.A proposition for a general example of a network that satisfies condition (11) is given in Appendix B.About the uniqueness, the following theorem gives us that the quantity of vehicles of arc is unique and, then, the cost of the route is also unique.Theorem 3.
LetN∗ and M∗ be two solutions of VIC,K. For each link a, we have Na∗=Ma∗, and for each route p, we have cpN∗=cpM∗.Proof (LetN∈K).
We haveCN∗.N-N∗≥0 which implies that ∑pcpN∗.Np-Np∗≥0. Given that cpNp=∑acaNaδap, we have (13)∑pcpN∗.Np-Np∗=∑p∑acaNa∗δap.Np-Np∗=∑acaNa∗∑pδapNp-Np∗=∑acaNa∗·Na-Na∗This implies that(14)∀N∈K′,∑acaNa∗·Na-Na∗≥0Where (15)K′=N′=Na∣∃N∈K,∀a∈L,Na=∑pNpqapDefine C′(N′)=caNaa∈L. From what we stand before, the vector Na∗ is a solution of VIC′,K′. By the same way, the vector Ma∗ is a solution of VIC′,K′. Given that each function ca is strictly increasing, we deduce that the vector field C′ is strictly monotone. Moreover, it is clear that K′ is a convex set; then VIC′,K′ admits a unique solution. We deduce that, for each arc a, we have Na∗=Ma∗.
We deduce that, for each arca, we have caNa∗=caMa∗, and then cpN∗=cpM∗.A big issue for this model is the fact that if we considerqap=ta/tpδap (this choice allows for flow conservation to be satisfied), then qap depend on Na which depends on qap. In what follows, we propose an algorithm for constructing iteratively a solution of VI(C,K) with qap=ta/tpδap. In the sequel, we consider αa>0 and βa>0 such that the average speed on link a is given by va=αa-βaDa, with Da=Na/la the density of vehicles present on link a. In this case we have ta=la/αa-βaDa.We consider the functionta(Na)=la/αa-βaDa=la2/laαa-βaNa, which is the average time for travelling the link a if there are Na vehicles, and the function tpN=∑a∈LtaNaδap which is the average time for travelling the route p if the vector of quantities of vehicles is N=Npp.Algorithm 4.
We construct the sequenceNn by the following way.
Step0. Let ta0=la/αa, tp0=∑ata0δap, qap0=ta0/tp0δap, n=1. Let ε>0.
Step 1. Given the quantity qapn-1, consider the set(16)Kn=N=Npp∈P∣Na=∑p∈PNpqapn-1,Np≥0,Na<Namax,Nw=∑p∈PwNp.Construct Nn=Npnp∈P as a solution of VI(C,Kn).
Step2. Consider Nan=∑p∈PNpnqapn-1 the quantity of vehicles on link a, fa=Nan/ta(Nan) the vehicles flow on link a, and hp=Npn/∑ata(Nan)δap the vehicles flow on route p. If ∑a∈Lfa-∑p∈Phpδap2/∑a∈Lfa2<ε2, then stop; else, go to step 3.
Step3. Construct (Na)a as a solution of the equations Na=∑p∈Pta(Na)/∑a′∈Lta′Na′δa′pNpnδap. Consider qapn=taNa/∑a′∈Lta′Na′δa′pδap, n=n+1, and go to Step 1.
Step 2 tests whether the relative error in the flow conservation law is small enough. This algorithm has been implemented to obtain the results of the following section.


## 3.3. Estimation of Road Project Benefits and Summary of Model Characteristics

The proposed model can be used to conduct a social cost-benefit analysis of a road system project. If we letC0w be the equilibrium cost before the project is implemented and let C1w be the equilibrium cost after implementation, the change in consumer surplus (∆EC) is estimated directly by the following formula:(17)ΔEC=∑w∫C0wC1wTwdCw=∑w∫C0wC1wNwCwdCw=∑wNwln⁡C1wC0wwhere Tw is the trip matrix (vehicle flows per hour). In the classical flow-based model, on the other hand, where Tw is exogenous, the change in consumer surplus is given by (18)ΔEC=TwC1w-C0wBriefly, in (17) the social benefit of a transport project or policy derives from the greater number of individuals benefiting in the same period of time whereas in (18) the social benefit consists in the same number of individuals experiencing lower trip costs.A summary of the main characteristics of the classical flow-based and proposed density-based models and the differences between them is laid out in Table1.Table 1
Summary of Main Differences between Flow-Based and Density-Based Models.
Characteristic Flow-Based Model Density-Based Model General concept Assigns vehicles per hour among the different network links for a representative time period. Assigns vehicles per kilometre among the different network links for a representative instant in time.  Equilibrium condition Satisfies Wardrop’s first principle for all network routes. Satisfies Wardrop’s first principle for all network routes.  State of system Assumes that all trips in the trip matrix are assigned to the network and that all trips enter and exit within a given modelled period. Assumes that the total number of vehicles on the network at a given instant is the same at the instant immediately preceding and immediately following.  Link capacity Each link is assumed to have a fixed, exogenous capacity or maximum flow. This capacity will often be exceeded. Each link’s maximum flow, rather than being a fixed parameter, depends on vehicle density and speed across it and will vary with traffic conditions. Maximum flow is finite.  Trip matrix Assumes a trip matrix (flows between O-D pairs) for the period modelled that is fixed and exogenous to equilibrium cost. Assumes the number of vehicles for the instant modelled is fixed and exogenous but the trip matrix (flows between O-D pairs) is a result of the equilibrium.  Conservation of flow By construction, assumes conservation of flow at all network nodes including cases where route time or cost is greater than the period modelled (i.e., there are travellers who do not arrive at their destination). Withqap=ta/tpδap the conservation of flow is satisfied.  Densities and queue lengths under congestion Does not satisfactorily estimate either densities or queue lengths under high congestion. Always correctly estimates densities and queue lengths, whether under low or high congestion.  Fundamental traffic equation Under high congestion, thef=V·D relationship does not hold. By construction, thef=V·D relationship always holds.  Estimation of benefits of road system project or policy Benefits are estimated in terms of network user time savings. Benefits are estimated as the change in consumer surplus.


## 4. Comparative Application of Models and Results

In this section we discuss the application of the classical flow-based and proposed density-based models to a numerical example of a road network and compare their results. Both low and high congestion scenarios are considered. The two approaches are also used to estimate the benefits of a road system project. Notice that, in the absence of congestion, the density-based model will always provide identical results as the flow-based model.


### 4.1. The Nguyen-Dupuis Network

The road network assumed for this application is an adaptation of the one developed by Nguyen and Dupuis [44], depicted here in Figure 4. It consists of 13 nodes and 19 links. Four O-D pairs are defined: A-K, A-M, C-K, and C-M. There are 23 different possible routes for the four pairs as set out in Table 2.Table 2
Possible Routes for Origin-Destination Pairs.
Route No. O-D Pair Route (link sequence) 1 A-K 1-7-12 2 A-K 2-4-5-6-12 3 A-K 2-4-5-11-15 4 A-K 2-4-10-14-15 5 A-K 2-9-13-14-15 6 A-K 2-9-13-14-18-19 7 A-K 2-9-16-17-19 8 A-M 2-4-5-11-18 9 A-M 2-4-10-14-18 10 A-M 2-9-13-14-18 11 A-M 2-9-16-17 12 C-K 3-4-5-6-12 13 C-K 3-4-5-11-15 14 C-K 3-4-10-14-15 15 C-K 3-9-13-14-15 16 C-K 8-13-14-15 17 C-K 8-13-14-18-19 18 C-K 8-16-17-19 19 C-M 3-4-5-11-18 20 C-M 3-4-10-14-18 21 C-M 3-9-13-14-18 22 C-M 8-13-14-18 23 C-M 8-16-17Figure 4
Nguyen-Dupuis Network (Adaptation).We define the relationship between speed and density on each link defined by (1) as Va=50-Da. This implies that the free-flow speed is 50 km/h, the density that generates the maximum flow is 25 vehicles per kilometre Da∗=25, and the maximum density is 50 vehicles per kilometre Damax=50. The lengths in kilometres of the 19 links, ordered by number as shown in Figure 4, are as follows: la=5110329210510222223322. The maximum flow is famax=625.For the proposed density-based model, the flow of vehicles travelling between each of the four O-D pairs is defined by matricesT1 and T2 representing, respectively, the high congestion case and the low congestion case, as follows:(19)T1=TA-KTA-MTC-KTC-M=810400450800T2=TA-KTA-MTC-KTC-M=500500500500In order to compute the quantity of vehicles Nw, which are travelling the O-D pair w, we solve the flow-based model. To achieve this goal, we solve the equation(20)Hh,λ,μ=Ch+Δtλ-μΔh-Th⊗μ=0with h≥0 and μ≥0. Notice that ∆ is the OD-route incidence matrix, h=hp is the vector of flow on routes, T=Tw is the vector of flow demands, ⊗ is the Hadamard product which is defined as h⊗μ=hp·μp, and Ch=Cph is the vector of cost on routes using flow-based model.The gap function that we consider isHh,λ,μ. The convergence criterion we use is Hh,λ,μ<10-4. The gap function is necessary to guarantee the convergence of the results of the models in the equilibrium. Our gap function, specifically, measures how much Wardrop's balance is violated.We solved (20) using a reduction potential method [45]. For this approach we estimate flow-delay functions that must satisfy two conditions. First, they must be as similar as possible to the flow-delay functions used for the density-based assignments and, second, they have to be monotonically increasing.A function that meets both conditions is the black curve shown in Figure5, where it is graphed together with the grey curve representing the flow-delay relationship of our density-based model. The grey curve is constructed assuming parameter values αa=50,βa=1, for a link of length la=1. For the black curve, on the other hand, each linka is defined by an exponential function of the form cafa=ta0+laηaexp⁡ρa·fa, where ta0 is the free-flow time ofa and ηa,ρa are positive parameters estimated so as to follow as closely as possible the increasing segment of the grey curve. The actual parameter values used are ηa=0.00053302,ρa=0.0054674137. With these two flow-delay functions representing the two approaches, we would expect them to produce similar results in low congestion situations but significantly different results with high congestion.Figure 5
Flow-Delay Curves for Flow-Based and Density-Based Approaches.Using the sameT1 (high congestion) and T2 (low congestion) matrix values given in (19) and the corresponding equilibrium costs for each O-D pair (Tables 3 and 5), we estimate two vectors N1 and N2 of quantity of vehicles travelling between each of the four O-D pairs multiplying the vectors of flows T1 and T2 by the time for travelling the O-D pairs computed using the flow-based model. We obtain, for high congestion, the following time for travelling the O-D pairs with flow-based model:(21)c1=cA-KcA-McC-KcC-M=0.36030.36290.63870.6413c2=cA-KcA-McC-KcC-M=0.25380.30750.52010.5219The quantity of vehicles travelling between each of the four O-D pairs is defined by matrices N1 and N2 representing, respectively, the high congestion case and the low congestion case, as follows:(22)N1=810×0.3603400×0.3629450×0.6387800×0.6413=291.82145.16287.41513.05N2=500×0.2538500×0.3075500·×0.5201500×0.5219=126.91153.75260.04260.97We solve the density-based model solving the equation(23)HN,λ,μ=CN+Δtλ-μΔN-NwN⊗μ=0with N≥0 and μ≥0. Notice that ∆ is the OD-route incidence matrix, N=Np is the vector of quantities on routes, Nw is the vector of quantities demands between OD pairs, N⊗μ=Np·μp, and CN=CpN is the vector of cost on routes using density-based model. The gap function we use is HN,λ,μ. The convergence criterion we use is HN,λ,μ<10-4.Table 3
Equilibrium Route Assignments, Density-Based Approach (high congestion).
Route O-D Pair N p C p 1 A-K 224.3485 0.3592 2 A-K 0.0000 0.4872 3 A-K 36.4514 0.3592 4 A-K 0.0000 0.4919 5 A-K 31.0230 0.3592 6 A-K 0.0000 0.3937 7 A-K 0.0000 0.3937 8 A-M 41.6268 0.3537 9 A-M 0.0000 0.4864 10 A-M 34.6943 0.3537 11 A-M 68.8369 0.3537 12 C-K 0.0000 0.8222 13 C-K 144.2187 0.6942 14 C-K 0.0000 0.8269 15 C-K 85.1820 0.6942 16 C-K 58.0120 0.6942 17 C-K 0.0000 0.7288 18 C-K 0.0000 0.7288 19 C-M 126.0871 0.6888 20 C-M 0.0000 0.8214 21 C-M 78.5134 0.6888 22 C-M 54.8398 0.6888 23 C-M 253.6105 0.6888For high congestion scenario, the gap function for density-based model is equal at the equilibrium to0.7614·10-10. The equilibrium route and link assignment results for the high congestion case are set out in Tables 3 and 4. From Table 3 we see that, for O-D pair A-K, 3 of the 7 possible routes are used and all 3 have the same cost, satisfying Wardrop’s first principle (routes 2, 4, 6, and 7 are not used, show higher costs). Regarding the other three pairs, 3 of the 4 possible routes are used for A-M, 3 of the possible 7 are used for C-K, and 4 of the possible 5 are used for C-M.Table 4
Equilibrium Link Assignments, Density-Based Approach (high congestion).
Link N a l a D a D a ∗ V a c a f a 1 126.5223 5 25.3045 25 24.6955 0.2025 624.9073 2 17.9292 1 17.9292 25 32.0708 0.0312 575.0042 3 226.9215 10 22.6921 25 27.3079 0.3662 619.6738 4 84.1265 3 28.0422 25 21.9578 0.1366 615.7452 5 37.1041 2 18.5520 25 31.4480 0.0636 583.4237 6 0.0000 9 0.0000 25 50.0000 0.1800 0.0000 7 50.6089 2 25.3045 25 24.6955 0.0810 624.9073 8 306.1953 10 30.6195 25 19.3805 0.5160 593.4209 9 83.0978 5 16.6196 25 33.3804 0.1498 554.7684 10 0.0000 10 0.0000 25 50.0000 0.2000 0.0000 11 36.7618 2 18.3809 25 31.6191 0.0633 581.1875 12 47.2174 2 23.6087 25 26.3913 0.0758 623.0643 13 26.1439 2 13.0720 25 36.9280 0.0542 482.7217 14 32.8045 2 16.4023 25 33.5977 0.0595 551.0790 15 38.0592 2 19.0296 25 30.9704 0.0646 589.3545 16 45.8212 3 15.2737 25 34.7263 0.0864 530.3997 17 45.8212 3 15.2737 25 34.7263 0.0864 530.3997 18 32.3097 2 16.1549 25 33.8451 0.0591 546.7634 19 0.0000 2 0.0000 25 50.0000 0.0400 0.0000Table 5
Equilibrium Route Assignments, Density-Based Approach (low congestion).
Route O-D Pair N p C p 1 A-K 126.9098 0.2507 2 A-K 0.0000 0.4214 3 A-K 0.0000 0.3031 4 A-K 0.0000 0.4280 5 A-K 0.0000 0.3031 6 A-K 0.0000 0.3451 7 A-K 0.0000 0.3451 8 A-M 77.0756 0.3051 9 A-M 0.0000 0.4300 10 A-M 24.9098 0.3051 11 A-M 51.7650 0.3051 12 C-K 0.0000 0.6404 13 C-K 122.2635 0.5221 14 C-K 0.0000 0.6470 15 C-K 28.2865 0.5221 16 C-K 109.4890 0.5221 17 C-K 0.0000 0.5640 18 C-K 0.0000 0.5640 19 C-M 38.6385 0.5240 20 C-M 0.0000 0.6489 21 C-M 18.8462 0.5240 22 C-M 37.2549 0.5240 23 C-M 166.2343 0.5240Table4 shows that 3 of the 19 links are not used and thus their vehicle numbers and flows are 0. Also apparent is that 4 links (1, 4, 7, and 8) have densities greater than the critical density level Da∗=25. This means that these links’ flows are located on the decreasing segment of the curve in Figure 1.For the low congestion case, Table5 shows that 1 of the 7 possible routes is used for pair A-K, 3 of the 4 possible routes are used for A-M, 3 of the 7 possible routes are used for C-K, and 4 of the 5 possible routes are used for C-M. According to Table 6, of the 19 links there are 3 unused and no link has a density greater than the maximum flow level Da∗. Thus, the flows on these links are located on the increasing segment of the curve in Figure 1. In this case, the gap function for density-based model is equal at the equilibrium to 0.7756·10-10.Table 6
Equilibrium Link Assignments, Density-Based Approach (low congestion).
Link N a l a D a D a ∗ V a c a f a 1 70.5055 5 14.1011 25 35.8989 0.1393 506.2138 2 13.7323 1 13.7323 30 36.2677 0.0276 498.0380 3 94.3981 10 9.4398 30 40.5602 0.2465 382.8805 4 55.1230 3 18.3743 25 31.6257 0.0949 581.1005 5 36.7487 2 18.3743 25 31.6257 0.0632 581.1005 6 0.0000 9 0.0000 30 50.0000 0.1800 0.0000 7 28.2022 2 14.1011 25 35.8989 0.0557 506.2138 8 226.1471 10 22.6147 25 27.3853 0.3652 619.3104 9 39.2293 5 7.8459 25 42.1541 0.1186 330.7354 10 0.0000 10 0.0000 25 50.0000 0.2000 0.0000 11 36.7487 2 18.3743 30 31.6257 0.0632 581.1005 12 28.2022 2 14.1011 30 35.8989 0.0557 506.2138 13 22.1236 2 11.0618 25 38.9382 0.0514 430.7267 14 22.1236 2 11.0618 30 38.9382 0.0514 430.7267 15 26.1893 2 13.0947 30 36.9053 0.0542 483.2632 16 36.7122 3 12.2374 30 37.7626 0.0794 462.1156 17 36.7122 3 12.2374 25 37.7626 0.0794 462.1156 18 28.7754 2 14.3877 30 35.6123 0.0562 512.3795 19 0.0000 2 0.0000 30 50.0000 0.0400 0.0000


### 4.2. Comparison of Density-Based Model with Flow-Based Model

We now compare the above results for the density-based model with those of a classical flow-based model.We would expect the link flow and cost results obtained forT1 under this approach to differ significantly from those obtained above forN1 under the density-based approach, reflecting the difference between the two approaches when congestion is high. WhenT2 andN2 are compared, however, the link flow and cost results should be relatively similar, mirroring the greater similarity between the two approaches when congestion is low.The link costs and flows under the two approaches for the high congestion case are brought together in Table7 and the two sets of values are charted separately in Figures 6 and 7. As can be seen in the table, both flows and costs for the two models are significantly different. Some of the links under the flow-based model have flows considerably greater than the theoretical capacity of 625 (links 1, 4, 5, 7, 8, 11, and 12), whereas, under the density-based model, this never occurs. Costs under the two approaches also differ appreciably, the density-based model always showing higher cost levels.Table 7
Equilibrium Link Assignments, Both Approaches (high congestion).
Link Maximum flow for Density-Based model Flow-Based Model Density-Based Model f a m a x c a f a c a f a 1 625 0.2002 663.2872 0.2025 624.9073 2 625 0.0306 546.7128 0.0312 575.0042 3 625 0.3090 551.9899 0.3662 619.6738 4 625 0.1122 637.6172 0.1366 615.7452 5 625 0.0748 637.6116 0.0636 583.4237 6 625 0.1848 0.0028 0.1800 0.0000 7 625 0.0801 663.2872 0.0810 624.9073 8 625 0.4422 698.0101 0.5160 593.4209 9 625 0.1332 461.0855 0.1498 554.7684 10 625 0.2053 0.0056 0.2000 0.0000 11 625 0.0748 637.6089 0.0633 581.1875 12 625 0.0801 663.2899 0.0758 623.0643 13 625 0.0643 572.2073 0.0542 482.7217 14 625 0.0643 572.2129 0.0595 551.0790 15 625 0.0678 596.6946 0.0646 589.3545 16 625 0.0996 586.8883 0.0864 530.3997 17 625 0.0996 586.8883 0.0864 530.3997 18 625 0.0705 613.1272 0.0591 546.7634 19 625 0.0411 0.0154 0.0400 0.0000Figure 6
Link Costs, Both Approaches (high congestion).Figure 7
Link Flows, Both Approaches (high congestion).A metric which can compare both models is the relative distance between the link costs and the link flows of the density-based model and the flow-based model. More precisely, we can consider the following quantities, wherefD and fF are the flow vectors in, respectively, the density-based model and the flow-based model, where cD and cF are the flow vectors in, respectively, the density-based model and the flow-based model: (24)distfD,ff=2fD-fFfD+fF,distcD,cf=2cD-cFcD+cFWe can observe that both quantities are relative distances between the results obtained with the density-based model and the flow-based model. The relative distances that we obtain for the high congestion case are(25)distfD,fF=0.0994,distcD,cF=0.1382For the low congestion case, the link costs and flows under the flow-based (matrixT2) and density-based (matrixN2) approaches are given in Table 8, and the two sets of values are charted separately in Figures 8 and 9. The table shows that both flows and costs for each model are relatively similar. Note, however, that on every link the cost under the density-based model is equal to or higher than that for the flow-based model. The relative distances that we obtain for the low congestion case are(26)distfD,ff=0.0303,distcD,cf=0.0219These data for the two cases confirm our expectation that the results of the two approaches are similar under low congestion but differ when congestion is high.Table 8
Equilibrium Link Assignments, Both Approaches (low congestion).
Link Maximum flow for Density-Based model Flow-Based Model Density-Based Model f a m a x c a f a c a f a 1 625 0.1410 499.9880 0.1393 506.2138 2 900 0.0282 500.0120 0.0276 498.0380 3 900 0.2426 380.2809 0.2465 382.8805 4 625 0.0947 562.9694 0.0949 581.1005 5 625 0.0631 562.9647 0.0632 581.1005 6 900 0.1848 0.0024 0.1800 0.0000 7 625 0.0564 499.9880 0.0557 506.2138 8 625 0.3579 619.7191 0.3652 619.3104 9 625 0.1151 317.3234 0.1186 330.7354 10 625 0.2053 0.0048 0.2000 0.0000 11 900 0.0631 562.9623 0.0632 581.1005 12 900 0.0564 499.9904 0.0557 506.2138 13 625 0.0530 456.7820 0.0514 430.7267 14 900 0.0530 456.7867 0.0514 430.7267 15 900 0.0564 499.9982 0.0542 483.2632 16 900 0.0821 480.2606 0.0794 462.1156 17 625 0.0821 480.2606 0.0794 462.1156 18 900 0.0583 519.7509 0.0562 512.3795 19 900 0.0411 0.0115 0.0400 0.0000Figure 8
Link Costs, Both Approaches (low congestion).Figure 9
Link Flows, Both Approaches (low congestion).The relative difference obtained for costs and flows in both scenarios are reported in Table9. They confirm that, as congestion declines, link costs and flows under the two approaches grow increasingly similar but, as congestion rises, they increasingly diverge.Table 9
Costs and Flows Relative Difference, Both Approaches (two congestion scenarios).
Scenario N° of vehicles Flows Link Cost Relative distance Link Flow Relative distance high congestion N 1 = 1237.4 T 1 =2460 0.1382 0.0994 low congestion N 2 = 801.67 T 2 = 2000 0.0219 0.0303Finally, the gap function for flow-based model with high congestion is9.1915·10-4, and for low congestion is 9.4065·10-4.


### 4.3. Obtaining theNw Matrix Elements

Both the flow matrix containing theTw and the vehicle matrix containing the Nw can be obtained from trip surveys that capture trip origins and destinations and the corresponding departure and arrival times. To estimate the Nw values from such a survey, consider the diagram in Figure 10.Figure 10
Trip Diagram from a Survey.On the vertical axis are the 7 individuals surveyed after expanding the representative sample while on the horizontal axis is the time of day. As can be seen, Individual 1 departed at about 6:45 and arrived at 8:00. Individual 2 set out at 6:30 and arrived between 7:15 and 7:30. Individual 3 made two trips, the first one starting shortly after 7:00 and ending at 7:45 and the second one beginning soon after 8:15 and ending at about 8:45. By proceeding in this manner, the individuals or vehicles in the network at a given moment can be successively identified. For example, at 7:30 there were 6 individuals in the network. Since the survey also gathered the trip origins and destinations, an estimate ofNw can then be obtained.


## 4.1. The Nguyen-Dupuis Network

The road network assumed for this application is an adaptation of the one developed by Nguyen and Dupuis [44], depicted here in Figure 4. It consists of 13 nodes and 19 links. Four O-D pairs are defined: A-K, A-M, C-K, and C-M. There are 23 different possible routes for the four pairs as set out in Table 2.Table 2
Possible Routes for Origin-Destination Pairs.
Route No. O-D Pair Route (link sequence) 1 A-K 1-7-12 2 A-K 2-4-5-6-12 3 A-K 2-4-5-11-15 4 A-K 2-4-10-14-15 5 A-K 2-9-13-14-15 6 A-K 2-9-13-14-18-19 7 A-K 2-9-16-17-19 8 A-M 2-4-5-11-18 9 A-M 2-4-10-14-18 10 A-M 2-9-13-14-18 11 A-M 2-9-16-17 12 C-K 3-4-5-6-12 13 C-K 3-4-5-11-15 14 C-K 3-4-10-14-15 15 C-K 3-9-13-14-15 16 C-K 8-13-14-15 17 C-K 8-13-14-18-19 18 C-K 8-16-17-19 19 C-M 3-4-5-11-18 20 C-M 3-4-10-14-18 21 C-M 3-9-13-14-18 22 C-M 8-13-14-18 23 C-M 8-16-17Figure 4
Nguyen-Dupuis Network (Adaptation).We define the relationship between speed and density on each link defined by (1) as Va=50-Da. This implies that the free-flow speed is 50 km/h, the density that generates the maximum flow is 25 vehicles per kilometre Da∗=25, and the maximum density is 50 vehicles per kilometre Damax=50. The lengths in kilometres of the 19 links, ordered by number as shown in Figure 4, are as follows: la=5110329210510222223322. The maximum flow is famax=625.For the proposed density-based model, the flow of vehicles travelling between each of the four O-D pairs is defined by matricesT1 and T2 representing, respectively, the high congestion case and the low congestion case, as follows:(19)T1=TA-KTA-MTC-KTC-M=810400450800T2=TA-KTA-MTC-KTC-M=500500500500In order to compute the quantity of vehicles Nw, which are travelling the O-D pair w, we solve the flow-based model. To achieve this goal, we solve the equation(20)Hh,λ,μ=Ch+Δtλ-μΔh-Th⊗μ=0with h≥0 and μ≥0. Notice that ∆ is the OD-route incidence matrix, h=hp is the vector of flow on routes, T=Tw is the vector of flow demands, ⊗ is the Hadamard product which is defined as h⊗μ=hp·μp, and Ch=Cph is the vector of cost on routes using flow-based model.The gap function that we consider isHh,λ,μ. The convergence criterion we use is Hh,λ,μ<10-4. The gap function is necessary to guarantee the convergence of the results of the models in the equilibrium. Our gap function, specifically, measures how much Wardrop's balance is violated.We solved (20) using a reduction potential method [45]. For this approach we estimate flow-delay functions that must satisfy two conditions. First, they must be as similar as possible to the flow-delay functions used for the density-based assignments and, second, they have to be monotonically increasing.A function that meets both conditions is the black curve shown in Figure5, where it is graphed together with the grey curve representing the flow-delay relationship of our density-based model. The grey curve is constructed assuming parameter values αa=50,βa=1, for a link of length la=1. For the black curve, on the other hand, each linka is defined by an exponential function of the form cafa=ta0+laηaexp⁡ρa·fa, where ta0 is the free-flow time ofa and ηa,ρa are positive parameters estimated so as to follow as closely as possible the increasing segment of the grey curve. The actual parameter values used are ηa=0.00053302,ρa=0.0054674137. With these two flow-delay functions representing the two approaches, we would expect them to produce similar results in low congestion situations but significantly different results with high congestion.Figure 5
Flow-Delay Curves for Flow-Based and Density-Based Approaches.Using the sameT1 (high congestion) and T2 (low congestion) matrix values given in (19) and the corresponding equilibrium costs for each O-D pair (Tables 3 and 5), we estimate two vectors N1 and N2 of quantity of vehicles travelling between each of the four O-D pairs multiplying the vectors of flows T1 and T2 by the time for travelling the O-D pairs computed using the flow-based model. We obtain, for high congestion, the following time for travelling the O-D pairs with flow-based model:(21)c1=cA-KcA-McC-KcC-M=0.36030.36290.63870.6413c2=cA-KcA-McC-KcC-M=0.25380.30750.52010.5219The quantity of vehicles travelling between each of the four O-D pairs is defined by matrices N1 and N2 representing, respectively, the high congestion case and the low congestion case, as follows:(22)N1=810×0.3603400×0.3629450×0.6387800×0.6413=291.82145.16287.41513.05N2=500×0.2538500×0.3075500·×0.5201500×0.5219=126.91153.75260.04260.97We solve the density-based model solving the equation(23)HN,λ,μ=CN+Δtλ-μΔN-NwN⊗μ=0with N≥0 and μ≥0. Notice that ∆ is the OD-route incidence matrix, N=Np is the vector of quantities on routes, Nw is the vector of quantities demands between OD pairs, N⊗μ=Np·μp, and CN=CpN is the vector of cost on routes using density-based model. The gap function we use is HN,λ,μ. The convergence criterion we use is HN,λ,μ<10-4.Table 3
Equilibrium Route Assignments, Density-Based Approach (high congestion).
Route O-D Pair N p C p 1 A-K 224.3485 0.3592 2 A-K 0.0000 0.4872 3 A-K 36.4514 0.3592 4 A-K 0.0000 0.4919 5 A-K 31.0230 0.3592 6 A-K 0.0000 0.3937 7 A-K 0.0000 0.3937 8 A-M 41.6268 0.3537 9 A-M 0.0000 0.4864 10 A-M 34.6943 0.3537 11 A-M 68.8369 0.3537 12 C-K 0.0000 0.8222 13 C-K 144.2187 0.6942 14 C-K 0.0000 0.8269 15 C-K 85.1820 0.6942 16 C-K 58.0120 0.6942 17 C-K 0.0000 0.7288 18 C-K 0.0000 0.7288 19 C-M 126.0871 0.6888 20 C-M 0.0000 0.8214 21 C-M 78.5134 0.6888 22 C-M 54.8398 0.6888 23 C-M 253.6105 0.6888For high congestion scenario, the gap function for density-based model is equal at the equilibrium to0.7614·10-10. The equilibrium route and link assignment results for the high congestion case are set out in Tables 3 and 4. From Table 3 we see that, for O-D pair A-K, 3 of the 7 possible routes are used and all 3 have the same cost, satisfying Wardrop’s first principle (routes 2, 4, 6, and 7 are not used, show higher costs). Regarding the other three pairs, 3 of the 4 possible routes are used for A-M, 3 of the possible 7 are used for C-K, and 4 of the possible 5 are used for C-M.Table 4
Equilibrium Link Assignments, Density-Based Approach (high congestion).
Link N a l a D a D a ∗ V a c a f a 1 126.5223 5 25.3045 25 24.6955 0.2025 624.9073 2 17.9292 1 17.9292 25 32.0708 0.0312 575.0042 3 226.9215 10 22.6921 25 27.3079 0.3662 619.6738 4 84.1265 3 28.0422 25 21.9578 0.1366 615.7452 5 37.1041 2 18.5520 25 31.4480 0.0636 583.4237 6 0.0000 9 0.0000 25 50.0000 0.1800 0.0000 7 50.6089 2 25.3045 25 24.6955 0.0810 624.9073 8 306.1953 10 30.6195 25 19.3805 0.5160 593.4209 9 83.0978 5 16.6196 25 33.3804 0.1498 554.7684 10 0.0000 10 0.0000 25 50.0000 0.2000 0.0000 11 36.7618 2 18.3809 25 31.6191 0.0633 581.1875 12 47.2174 2 23.6087 25 26.3913 0.0758 623.0643 13 26.1439 2 13.0720 25 36.9280 0.0542 482.7217 14 32.8045 2 16.4023 25 33.5977 0.0595 551.0790 15 38.0592 2 19.0296 25 30.9704 0.0646 589.3545 16 45.8212 3 15.2737 25 34.7263 0.0864 530.3997 17 45.8212 3 15.2737 25 34.7263 0.0864 530.3997 18 32.3097 2 16.1549 25 33.8451 0.0591 546.7634 19 0.0000 2 0.0000 25 50.0000 0.0400 0.0000Table 5
Equilibrium Route Assignments, Density-Based Approach (low congestion).
Route O-D Pair N p C p 1 A-K 126.9098 0.2507 2 A-K 0.0000 0.4214 3 A-K 0.0000 0.3031 4 A-K 0.0000 0.4280 5 A-K 0.0000 0.3031 6 A-K 0.0000 0.3451 7 A-K 0.0000 0.3451 8 A-M 77.0756 0.3051 9 A-M 0.0000 0.4300 10 A-M 24.9098 0.3051 11 A-M 51.7650 0.3051 12 C-K 0.0000 0.6404 13 C-K 122.2635 0.5221 14 C-K 0.0000 0.6470 15 C-K 28.2865 0.5221 16 C-K 109.4890 0.5221 17 C-K 0.0000 0.5640 18 C-K 0.0000 0.5640 19 C-M 38.6385 0.5240 20 C-M 0.0000 0.6489 21 C-M 18.8462 0.5240 22 C-M 37.2549 0.5240 23 C-M 166.2343 0.5240Table4 shows that 3 of the 19 links are not used and thus their vehicle numbers and flows are 0. Also apparent is that 4 links (1, 4, 7, and 8) have densities greater than the critical density level Da∗=25. This means that these links’ flows are located on the decreasing segment of the curve in Figure 1.For the low congestion case, Table5 shows that 1 of the 7 possible routes is used for pair A-K, 3 of the 4 possible routes are used for A-M, 3 of the 7 possible routes are used for C-K, and 4 of the 5 possible routes are used for C-M. According to Table 6, of the 19 links there are 3 unused and no link has a density greater than the maximum flow level Da∗. Thus, the flows on these links are located on the increasing segment of the curve in Figure 1. In this case, the gap function for density-based model is equal at the equilibrium to 0.7756·10-10.Table 6
Equilibrium Link Assignments, Density-Based Approach (low congestion).
Link N a l a D a D a ∗ V a c a f a 1 70.5055 5 14.1011 25 35.8989 0.1393 506.2138 2 13.7323 1 13.7323 30 36.2677 0.0276 498.0380 3 94.3981 10 9.4398 30 40.5602 0.2465 382.8805 4 55.1230 3 18.3743 25 31.6257 0.0949 581.1005 5 36.7487 2 18.3743 25 31.6257 0.0632 581.1005 6 0.0000 9 0.0000 30 50.0000 0.1800 0.0000 7 28.2022 2 14.1011 25 35.8989 0.0557 506.2138 8 226.1471 10 22.6147 25 27.3853 0.3652 619.3104 9 39.2293 5 7.8459 25 42.1541 0.1186 330.7354 10 0.0000 10 0.0000 25 50.0000 0.2000 0.0000 11 36.7487 2 18.3743 30 31.6257 0.0632 581.1005 12 28.2022 2 14.1011 30 35.8989 0.0557 506.2138 13 22.1236 2 11.0618 25 38.9382 0.0514 430.7267 14 22.1236 2 11.0618 30 38.9382 0.0514 430.7267 15 26.1893 2 13.0947 30 36.9053 0.0542 483.2632 16 36.7122 3 12.2374 30 37.7626 0.0794 462.1156 17 36.7122 3 12.2374 25 37.7626 0.0794 462.1156 18 28.7754 2 14.3877 30 35.6123 0.0562 512.3795 19 0.0000 2 0.0000 30 50.0000 0.0400 0.0000


## 4.2. Comparison of Density-Based Model with Flow-Based Model

We now compare the above results for the density-based model with those of a classical flow-based model.We would expect the link flow and cost results obtained forT1 under this approach to differ significantly from those obtained above forN1 under the density-based approach, reflecting the difference between the two approaches when congestion is high. WhenT2 andN2 are compared, however, the link flow and cost results should be relatively similar, mirroring the greater similarity between the two approaches when congestion is low.The link costs and flows under the two approaches for the high congestion case are brought together in Table7 and the two sets of values are charted separately in Figures 6 and 7. As can be seen in the table, both flows and costs for the two models are significantly different. Some of the links under the flow-based model have flows considerably greater than the theoretical capacity of 625 (links 1, 4, 5, 7, 8, 11, and 12), whereas, under the density-based model, this never occurs. Costs under the two approaches also differ appreciably, the density-based model always showing higher cost levels.Table 7
Equilibrium Link Assignments, Both Approaches (high congestion).
Link Maximum flow for Density-Based model Flow-Based Model Density-Based Model f a m a x c a f a c a f a 1 625 0.2002 663.2872 0.2025 624.9073 2 625 0.0306 546.7128 0.0312 575.0042 3 625 0.3090 551.9899 0.3662 619.6738 4 625 0.1122 637.6172 0.1366 615.7452 5 625 0.0748 637.6116 0.0636 583.4237 6 625 0.1848 0.0028 0.1800 0.0000 7 625 0.0801 663.2872 0.0810 624.9073 8 625 0.4422 698.0101 0.5160 593.4209 9 625 0.1332 461.0855 0.1498 554.7684 10 625 0.2053 0.0056 0.2000 0.0000 11 625 0.0748 637.6089 0.0633 581.1875 12 625 0.0801 663.2899 0.0758 623.0643 13 625 0.0643 572.2073 0.0542 482.7217 14 625 0.0643 572.2129 0.0595 551.0790 15 625 0.0678 596.6946 0.0646 589.3545 16 625 0.0996 586.8883 0.0864 530.3997 17 625 0.0996 586.8883 0.0864 530.3997 18 625 0.0705 613.1272 0.0591 546.7634 19 625 0.0411 0.0154 0.0400 0.0000Figure 6
Link Costs, Both Approaches (high congestion).Figure 7
Link Flows, Both Approaches (high congestion).A metric which can compare both models is the relative distance between the link costs and the link flows of the density-based model and the flow-based model. More precisely, we can consider the following quantities, wherefD and fF are the flow vectors in, respectively, the density-based model and the flow-based model, where cD and cF are the flow vectors in, respectively, the density-based model and the flow-based model: (24)distfD,ff=2fD-fFfD+fF,distcD,cf=2cD-cFcD+cFWe can observe that both quantities are relative distances between the results obtained with the density-based model and the flow-based model. The relative distances that we obtain for the high congestion case are(25)distfD,fF=0.0994,distcD,cF=0.1382For the low congestion case, the link costs and flows under the flow-based (matrixT2) and density-based (matrixN2) approaches are given in Table 8, and the two sets of values are charted separately in Figures 8 and 9. The table shows that both flows and costs for each model are relatively similar. Note, however, that on every link the cost under the density-based model is equal to or higher than that for the flow-based model. The relative distances that we obtain for the low congestion case are(26)distfD,ff=0.0303,distcD,cf=0.0219These data for the two cases confirm our expectation that the results of the two approaches are similar under low congestion but differ when congestion is high.Table 8
Equilibrium Link Assignments, Both Approaches (low congestion).
Link Maximum flow for Density-Based model Flow-Based Model Density-Based Model f a m a x c a f a c a f a 1 625 0.1410 499.9880 0.1393 506.2138 2 900 0.0282 500.0120 0.0276 498.0380 3 900 0.2426 380.2809 0.2465 382.8805 4 625 0.0947 562.9694 0.0949 581.1005 5 625 0.0631 562.9647 0.0632 581.1005 6 900 0.1848 0.0024 0.1800 0.0000 7 625 0.0564 499.9880 0.0557 506.2138 8 625 0.3579 619.7191 0.3652 619.3104 9 625 0.1151 317.3234 0.1186 330.7354 10 625 0.2053 0.0048 0.2000 0.0000 11 900 0.0631 562.9623 0.0632 581.1005 12 900 0.0564 499.9904 0.0557 506.2138 13 625 0.0530 456.7820 0.0514 430.7267 14 900 0.0530 456.7867 0.0514 430.7267 15 900 0.0564 499.9982 0.0542 483.2632 16 900 0.0821 480.2606 0.0794 462.1156 17 625 0.0821 480.2606 0.0794 462.1156 18 900 0.0583 519.7509 0.0562 512.3795 19 900 0.0411 0.0115 0.0400 0.0000Figure 8
Link Costs, Both Approaches (low congestion).Figure 9
Link Flows, Both Approaches (low congestion).The relative difference obtained for costs and flows in both scenarios are reported in Table9. They confirm that, as congestion declines, link costs and flows under the two approaches grow increasingly similar but, as congestion rises, they increasingly diverge.Table 9
Costs and Flows Relative Difference, Both Approaches (two congestion scenarios).
Scenario N° of vehicles Flows Link Cost Relative distance Link Flow Relative distance high congestion N 1 = 1237.4 T 1 =2460 0.1382 0.0994 low congestion N 2 = 801.67 T 2 = 2000 0.0219 0.0303Finally, the gap function for flow-based model with high congestion is9.1915·10-4, and for low congestion is 9.4065·10-4.


## 4.3. Obtaining theNw Matrix Elements

Both the flow matrix containing theTw and the vehicle matrix containing the Nw can be obtained from trip surveys that capture trip origins and destinations and the corresponding departure and arrival times. To estimate the Nw values from such a survey, consider the diagram in Figure 10.Figure 10
Trip Diagram from a Survey.On the vertical axis are the 7 individuals surveyed after expanding the representative sample while on the horizontal axis is the time of day. As can be seen, Individual 1 departed at about 6:45 and arrived at 8:00. Individual 2 set out at 6:30 and arrived between 7:15 and 7:30. Individual 3 made two trips, the first one starting shortly after 7:00 and ending at 7:45 and the second one beginning soon after 8:15 and ending at about 8:45. By proceeding in this manner, the individuals or vehicles in the network at a given moment can be successively identified. For example, at 7:30 there were 6 individuals in the network. Since the survey also gathered the trip origins and destinations, an estimate ofNw can then be obtained.


## 5. Conclusions

This paper developed, validated, and implemented a deterministic traffic assignment model based on link densities. The proposed formulation solves a variational inequality in a manner consistent with the relationship between flow, cost (the inverse of speed), and density given by the fundamental traffic equation for each network link. The solution thus derived is a network traffic equilibrium of link densities that satisfies Wardrop’s first principle.The model’s use of link densities to determine traffic equilibrium has a number of advantages over the traditional flow-based approach. Firstly, it recognizes that link capacity (or maximum flow) is not fixed but rather is a function of density levels. In other words, the maximum flow that can cross a link is variable and depends on demand, that is, density. Secondly, and, as a consequence of the foregoing, the proposed approach prevents flows from exceeding the links’ theoretical maximum capacities. These maximum flows or capacities are determined as a function of the speed and density on each link as given by the fundamental traffic equation. Thirdly, the density-based model identifies whether a reduced flow level on a given link is due to low latent demand for its use (e.g., low density) or, on the contrary, to high congestion (e.g., high density) reducing the flow that can use the link, thereby generating traffic queues and longer delays.An added benefit is that the estimates the model generates of link densities and their impacts on flow levels that can effectively use network links provide important data for planning road networks, calculating toll road revenues, and designing road pricing mechanisms based on traffic saturation levels.The proposed model was validated using a traffic microsimulator (see Appendix A) and applied to a numerical example based on the well-known Nguyen-Dupuis network. It was then compared to the classical flow-based approach for a road system project involving the addition of a link. The results showed that flow-based models tend to underestimate network equilibrium cost and allow flows that often exceed the links’ theoretical capacities even in low congestion scenarios. Furthermore, by underestimating costs the traditional approach also underestimates the net benefits of road system expansion projects or policies such as road pricing that lower vehicles use. These benefits arise from the reduction in the use of hypercongested networks attendant upon the implementation of a new link or a vehicle use disincentive policy, which as well as cutting costs increases road network capacity. The density-based approach, by contrast, takes these improvements into account.In light of the above, we believe our proposed model based on densities constitutes a new and innovative methodology for analyzing and evaluating road and other transport projects and policies involving networks subject to congestion. The model’s density-based approach overcomes a number of limitations inherent in the classical methodologies based on route flows.A disadvantage is the difficulty in applying an algorithm whose solution satisfies the flow conservation property. A future work on this topic could consist of minimizing the relative error in flow conservation over the set of solutions ofVIC,K, which lead to a MPEC (Mathematical Programming with Equilibrium Constraints). The numerical resolution of MPECs has been studied by many authors (see, e.g., [46–48]).



---

*Source: 5282879-2019-06-27.xml*