Measuring Inefficiency in Dynamic Traffic Networks: A Numerical

Study
Kien Doan∗, Satish Ukkusuri†

Abstract
In traffic assignment, the network inefficiency is described as the ratio of total system cost in user
equilibrium solution and that in system optimal solution. The worst case of the network inefficiency
is represented by the price of anarchy. An understanding of the range of network inefficiency in traffic
networks is very useful in the design of new mechanisms to bridge the inefficiency. In this study, we
systematically explore the trends in network inefficiency for dynamic equilibrium problems. We begin
our analysis with the single bottleneck model and show that the network inefficiency converges to a
certain value when demand increases. Then, we explore general networks with multiple origins and
destinations. We observe that the network inefficiency tapers off to a steady value with increase in
demand keeping all else the same. Extensive computational analysis illustrates the results in various
traffic networks with different levels of demand. Open questions of interest to the research community
will be discussed.

Keywords: Network inefficiency, price of anarchy, dynamic user equilibrium, dynamic system
optimal, single bottleneck, cell transmission model

1 Introduction
Equilibrium is used as a governing framework for studying many networked systems including trans-
portation, telecommunication, internet and other engineering and social systems. It is well known that
equilibria are often inefficient due to uninternalized positive externalities from a social welfare solution
in network games. Over the last ten years, researchers have focused on computing this inefficiency in
various network games. In the context of transportation networks, the network inefficiency is the ratio
of the user equilibrium travel cost with the system optimal travel cost (of entire network). A special case
of this network inefficiency is dubbed the price of anarchy - the worst-case ratio (or maximum ratio)
between the objective function value of an equilibrium solution and that of the optimal solution.
The network inefficiency (NI) and price of anarchy (POA) was first studied by Koutsoupias and
Papadimitriou (1999) for the congestion games. There are a number of studies focusing on the network
inefficiency and the price of anarchy within the context of static network assignment. Some important
results have been obtained for the static equilibrium. For example, the price of anarchy is 4/3 if the link
performance function is linear and it was shown that the the worst-case example is the Braess’s Paradox
network or two-node two-link network (Roughgarden and Tardos, 2002). If link performance function
is polynomial with degree at most p, the price of anarchy is O(p/lnp) (Roughgarden, 2002). This result
implies that, theoretically, the network inefficiency increases when the degree of the congestion cost
function increases. In addition, with respect to the fixed link performance function, the price of anarchy
is obtained with the simple networks such as two-node and two-link network, or network with two nodes
and parallel links. Karakostas et al. (2011) extended the problem with oblivious users. The authors
showed that if the fraction of oblivious users is high, the price of anarchy is greater than 4/3 which is
∗
School of Civil Engineering, Purdue University, West Lafayette, Indiana, 47907–2051 ; kdoan@purdue.edu
†
Corresponding Author, School of Civil Engineering, Purdue University, West Lafayette, Indiana, 47907–2051, U.S.A.;
sukkusur@purdue.edu

1
the POA for the same network with only selfish users. The series of above studies did not consider the
elastic demand assumption. Chau and Sim (2003) proposed several bounds for the price of anarchy in
the case of elastic demand and symmetric cost functions. After that, Han et al. (2008b) generalized the
results for the asymmetric cost functions. Han et al. (2008a) proved that the price of anarchy is lower
in the system with toll than without.
While there has been significant work in the last few years on measuring the network inefficiency
in static or time invariant networks, there is almost no work in measuring inefficiency in time varying
(dynamic) networks where congestion costs vary with flow over time (Anshelevich and Ukkusuri, 2009).
Individually, researchers have expended a great deal of effort in developing novel formulations for dynamic
user equilibrium (DUE) (Friesz et al., 1993; Ukkusuri, 2002; Nie and Zhang, 2010; Han et al., 2011;
Ukkusuri et al., 2012; Smith, 2013; Friesz et al., 2013) and dynamic system optimum (DSO) (Merchant
and Nemhauser, 1978a; Carey, 1987; Ghali and Smith, 1995; Doan and Ukkusuri, 2012; Qian et al., 2012).
There is a rich literature in the transportation community on developing analytical formulations based
on mathematical programming (Merchant and Nemhauser, 1978b; Carey, 1986, 1992; Ziliaskopoulos,
2000), variational inequality (Friesz et al., 1993; Lo and Szeto, 2002), control theory (Friesz et al., 1989;
Ran et al., 1993) and complementarity theory (Ban et al., 2008; Ramadurai et al., 2010). In addition,
there have been research works in developing efficient solution algorithms including simulation based
assignment models (Jayakrishnan et al., 1994; Peeta and Mahmassani, 1995; Lu et al., 2008).
In contrast to the static equilibrium models where most models are convex lending themselves to
neat analytical results, computing network inefficiency in dynamic equilibrium models is non trivial. The
reasons are: (1) A wide variety of traffic flow models: The underlying network loading model governs
the complexity of analysis depending on whether it is a point queue model, exit flow model or a more
advanced spatial queue model. From a traffic flow perspective, each model has its own advantages and
disadvantages with the spatial queue models being the most realistic; (2) Multitude of choice dimensions:
Dynamic equilibrium has been studied under various choice dimensions - route choice only; route and
departure time choice; route, activity and departure time choice; etc. Each of them leads to different
dynamic equilibrium models and have varying degree of complexity in the analysis; (3) Variety of solution
approaches: Since it is often difficult to solve the dynamic network problems to optimality, researchers
have developed different heuristic solution approaches which often lead to different final equilibrium
solutions for the same inputs depending on the technique. This is further complicated since dynamic
network problems have multiple equilibrium and optimum solutions and finding all of them is indeed a
hard problem. The basic elements of a dynamic assignment model are shown in Figure 1. This figure
shows three basic elements (supply, demand, and cost), which are required for the traffic assignment
problems (UE, SO) and computing the network inefficiency. Network topology, link capacity, jam density,
etc, represent the supply side in a transportation problem. For the demand side, the traffic demand and
the properties of traffic such as the value of travel time, the preferred arrival time determine the input
for the traffic assignment problem. Finally, the network loading procedure also impacts the results in
the problem.
This paper does not intend to study the POA in the dynamic networks. While it is interesting to
understand POA from a theoretical perspective, it does not provide a significant value from an engineer-
ing or economic perspective. Since POA is the worst case it determines the pathological instance of the
problem and does not reflect the most likely performance of the network inefficiency. Secondly, there
is no universal concept of POA. The POA should be understood within given underlying assumptions
of supply, demand, and cost. For example, Roughgarden and Tardos (2002) showed that if the link
performance function is linear, the POA is 4/3. The scenarios consider different networks and demand
levels. The underlying assumption is the linear cost function in static network. Without this specific
assumption, we will no longer obtain POA=4/3. We will show in this paper that, for the single bottle-
neck model with heterogeneous commuters, if we fix the demand and fix the cost function, there is a
unique value of NI and POA. However, if we allow demand or cost function vary, we may obtain a wide
range of network inefficiency and there is no conclusion for POA. The problem of studying POA is even
worse when considering the multiple OD networks with multiple solutions for both DUE and DSO. In

2
 SUPPLY DEMAND
((Network topology)
p gy) ((Traffic))

NETWORK INEFFICIENCY
AND PRICE OF ANARCHY

COST
(Network loading )

Figure 1: Basic elements for the network inefficiency and the price of anarchy

addition, we will see in the paper that a single point of POA is less meaningful as compared to showing
the trend of the network inefficiency.
Therefore, instead of studying POA, our goal is to conduct a systematic analysis of the network
inefficiency in dynamic networks. This is done to identify the range in network inefficiency in typical
transportation networks and discern patterns of network inefficiency under varying levels of congestion,
cost functions, time intervals and network sizes. By studying the network inefficiency in the cases that
demand or network size gradually increases, we can better understand the trend of how much network
performance suffers from the selfish behavior.
This paper will start with the departure time choice model in single bottleneck model. The network
inefficiency patterns are thoroughly studied. One advantage of using the single bottleneck model is that
since the equilibrium and optimum solutions are unique, the network inefficiency pattern is unique. We
will show that the network inefficiency for the single bottleneck model with homogeneous users is always
2. For the single bottleneck model with heterogeneous users, the network inefficiency stabilizes at certain
values as demand increases. The results from the single bottleneck models are used as the basis to extend
the investigation to the multiple OD traffic networks. For this, we will use an advanced spatial queuing
model based on a variant of the cell transmission model and compute the dynamic user equilibrium and
dynamic system optimum solutions under the same conditions. We show that the network inefficiency
varies from 1 to a certain value but never exceeds that of most congested single bottleneck. In addition,
for a certain demand level, the network inefficiency for simpler network topologies is usually higher as
compared to more complex network topologies.
The structure of this paper is as follows. Section 2 discusses the network inefficiency in different
single bottleneck models. Section 3 provides the brief formulations and solution approach for the DUE
and DSO models. Section 4 shows the numerical experiments conducted for different test networks with
different level of demand. The conclusions are drawn and open questions are discussed in the last section.

2 Network inefficiency in single bottleneck model

The single bottleneck (SB) model (Vickrey, 1969) is the first dynamic traffic assignment model which
has been well-studied by researchers for decades. It can be considered the simplest DTA model due to
the one-link-one-bottleneck assumption. The single bottleneck model is a departure time choice model
since the users can select only one route. It captures the congestion effect on a single road way which is
a typical representation of a morning/evening commute problem. Each traveler chooses an appropriate
departure time to obtain certain objectives. At user equilibrium behavior, the travelers optimize their
departure time choice to minimize individual cost (including queuing time and schedule delay costs). On

3
the other hand, at the system optimal state, the travelers follow the centralized assignments to minimize
the total system cost.
There are two approaches to solve the single bottleneck models in literature. They are categorized into
continuous and discrete time setting models. The models using continuous time setting appear in Vickrey
(1969); Daganzo (1985); Arnott et al. (1988, 1993), etc. Although these models can provide concrete
solutions for both user equilibrium and system optimal, it is limited to the homogeneous commuter
cases. Several studies extended the results for heterogeneous commuters (Arnott et al., 1994; Liu and
Nie, 2010). However the results are still limited to a certain number of commuter groups. Different from
the continuous time SB model, the discrete time SB model can handle heterogeneity for unlimited number
of groups. Ramadurai et al. (2010) was the first to propose the DUE complementarity formulation for
heterogeneous commuter SB model based on the discrete time setting. Doan et al. (2011) proposed the
linear programing approach to solve the system optimal problem user heterogeneity and proved that the
fine tolls can be obtained directly. Solving both DUE and DSO with a same set of assumptions is the
foundation to study the network inefficiency for the single bottleneck model. These results suggest some
valuable insights for studying the network inefficiency for the generalized DTA problems.

2.1 Homogeneous commuter single bottleneck model

In this section we will show that the network inefficiency in the homogeneous commuter SB model is
equal to 2 regardless the levels of demand or the delay penalty (α, β, γ) as long as β < α < γ where
parameters α, β, γ are the queuing time penalty, early schedule delay penalty and late schedule delay
penalty, respectively. At the user equilibrium assignment, the total system cost is T C e = αT T + βe + γl
(Figure 2a), where T T is the total queuing time and equal to AreaABC , e is total early schedule delay
and equal to AreaADE , and l is total early schedule delay and equal to AreaCDF . In the equilibrium
condition, the total queuing cost (αT T ) is equal to the total schedule delay cost (βe+γl), or αAreaABC =
βAreaADE + γAreaCDF .
On the other hand, in the system optimal assignment (Figure 2b), the departure rate is exactly equal
to the capacity. Hence the cumulative departure pattern and the cumulative arrival pattern overlap
each other and there is no queuing time in the network. The total system cost is computed by only the
schedule delay cost T C s = βe + γl = βAreaADE + γAreaCDF . Thus, T C s = 21 T C e . In addition, it is
shown that both UE and SO solution is unique. Therefore, the network inefficiency has only one value
e
which in this particular case is also equal to the price of anarchy (N I = P OA = TT TT C
C s = 2).

Cumulative Cumulative Cumulative Cumulative

departures arrivals departures arrivals

F C F C

B
D D

Time t* Time
t*
0 0
A E A E
a)) User
U equilibrium
ilib i b) S
System
t optimal
ti l

Figure 2: Continuous time setting single bottleneck model

Ramadurai et al. (2010) and Doan et al. (2011) showed that, for the homogeneous commuter SB
model, the solutions for DUE and DSO are similar for both discrete and continuous time settings if

4
the period of a time interval goes to zero. In general, the network inefficiency of the discrete time
homogeneous SB model may not be exactly equal to 2 because of the time discretization but it will be
close to 2.
In the homogeneous single bottleneck model above, we usually assume that there is a congestion at
the bottleneck when the time dependent demand is greater than the capacity. In the trivial case when
all time dependent demand is less than or equal to the capacity, the network inefficiency is equal to 1
because the DUE and DSO solutions are identical.

2.2 Heterogeneous commuter single bottleneck model

In this problem, we assume that there are G groups using the transportation bottleneck. Each group
g has demand Ng , a set of delay penalty αg , βg , γg such that (βg < αg < γg ), (Small (1982)), preferred
arrival time t∗g , and equilibrium cost Cg∗ . The dynamic user equilibrium assignment for this problem can
be obtained by using the following complementarity formulation (Ramadurai et al., 2010):

0 ≤ rt,g ⊥ αg T Tt + βg et,g + γg (et,g − (t∗g − t − T Tt )) − Cg∗ ≥ 0

∀t = 0, · · · , T ; g = 1, · · · , G (1)
G
X
r0,g − s
g=1
0 ≤ T T0 ⊥ T T0 − ≥0 (2)
s
G
X
rt,g − s
g=1
0 ≤ T Tt ⊥ T Tt − T Tt−1 − ≥0 ∀t = 1, · · · , T (3)
s
0 ≤ et,g ⊥ et,g − (t∗g − t − T Tt ) ≥ 0 ∀t = 0, · · · , T ; g = 1, · · · , G (4)
T
X
0 ≤ Cg∗ ⊥ rt,g − Ng ≥ 0 ∀g = 1, · · · , G (5)
t=0

Where rt,g is the rate of departure for group g at time t; T Tt is the travel time experienced by the
traffic departing at time t; et,g is the early arrival time for traffic of group g departing at time t; and s
is the capacity of the bottleneck.
This complementarity formulation find the equilibrium state in which no traffic can be better-off if
he/she unilaterally shift his/her departure time. In other words, traffic of any group pays the minimum
and equal cost for their group. Ramadurai et al. (2010) proved that the solution always exists by using
the complementarity formulation (1)-(5). In addition, the equilibrium cost for each group is unique.
With a same set of input parameters including demand (Ng ), delay penalties (βg < αg < γg ) and
preferred arrival time (t∗g ) for each group, we can solve the dynamic system optimal for the single
bottleneck model by using the linear programming proposed in Doan et al. (2011):

5
  ∗ 
G tg T
X X X
Minimize  rt,g βg (t∗g − t) + rt,g γg (t − t∗g ) (6)
g=1 t=0 t=t∗g +1
G
X
Subject to rt,g ≤ s ∀t = 0, · · · , T (7)
g=1
T
X
rt,g = Ng ∀g = 1, · · · , G (8)
t=0
rt,g ≥ 0 ∀t = 0, · · · , T ; g = 1, · · · , G (9)

Due to the linearity form, this model can easily assign all traffic to the certain departure time intervals
so that the total cost of the entire system is minimum. The solution for linear program (6)-(9) always
exists and the total system cost is unique. Therefore, the network inefficiency is unique for each set of
input parameters.
In this paper, we conduct a series of experiments for different level of demand and different number
of groups. In the first scenario, we keep the number of groups, delay penalties and preferred arrival time
unchanged, and vary the total demand. The formulations (1)-(5) and (6)-(9) are used to solve the DUE
and DSO, respectively. Then the ratio of total system cost in two solutions is computed and plotted.
We vary the total demand from 40 units to 4000 units. The results are illustrated in Figure 3 and 4:

Table 1: Input parameters for two scenarios

α β γ t∗ % demand
Group 1 0.1 0.08 0.25 570 50
Scenario a) Group 2 0.11 0.07 0.2 565 20
Group 3 0.12 0.11 0.15 575 30
Group 1 0.05 0.03 0.1 570 50
Scenario b) Group 2 0.11 0.055 0.22 565 20
Group 3 0.12 0.09 0.2 575 30

4
x 10
10 4
Total cost in DUE
Total cost in DSO
Network inefficiency
Network inefficiency ratio
Total system cost

5 2

0 0
0 500 1000 1500 2000 2500 3000 3500 4000
Demand

Figure 3: Network inefficiency trend for the SB model with user heterogeneity - Scenario a)

6
 4
x 10
6 3
Total cost in DUE
Total cost in DSO
Network inefficiency

Network inefficiency ratio

Total system cost 4 2

2 1

0 0
0 500 1000 1500 2000 2500 3000 3500 4000
Demand

Figure 4: Network inefficiency trend for the SB model with user heterogeneity - Scenario b)

Figure 3 and 4 show the results of two scenarios based on the input parameters in Table 1. The
value of travel time and schedule delay are different in two scenarios. Notice that in the scenarios tested
above for the total demand level from 40 to 4000, the single bottleneck is at the congested level. It is
obvious that the dynamic user equilibrium and dynamic system optimal solutions are the same if there
is no congestion in the network (in this case, the inefficiency ratio is 1). From Figure 3, it is observed
that for the lower level of demand (N < 400), the inefficiency ratio varies from 1.74 to 2.42. Then it
gradually decreases to 2. In the second scenario in Figure 4, the inefficiency ratio goes from 1.90 to 2.73
when the demand is less than 400 and stabilizes at 2.38 when the demand is more than 1600. When the
demand is low (less than 500) the NI pattern oscillates due to the time discretization. If we use smaller
time units, we obtain smoother patterns.
In a trivial case, t∗ for three groups are different such that there is no interaction between any two
groups in both DUE and DSO. Then the problem is equivalent to having three homogeneous groups and
the network inefficiency ratio is close to 2 as in the homogeneous case.
From scenario a) of Table 1, if we increase all α, β, γ with a fixed value, we will obtain a slightly
higher NI convergence. For example, if 0.15 is add to all values of α, β, γ in scenario a) of Table 1,
the network inefficiency will converge to 2.01 instead of 2.00. If all values of α, β, γ is multiplied by
a scalar, the network inefficiency pattern will show the same results. In these two cases, the order of
group departures in both DUE and DSO does not change significantly, which makes the NI ratios almost
identical.
On the other hand, if the values of α, β, γ are changed arbitrarily as in Scenario b) of Table 1, we
may obtain different stabilized value of NI (2.38 instead of 2.00 at Scenario a). The reason is that the
different order of departing groups in the DUE and DSO solutions leads to different network inefficiency.
In DUE, the departure order depends on the ratio of βg /αg and γg /αg while in DSO, it depends on the
absolute value of βg and γg (Arnott et al., 1994; Ramadurai et al., 2010; Doan et al., 2011).

7
 Total cost in DUE
Total cost in DSO
Network inefficiency

Network inefficiency ratio

2000
Total system cost

0 0
3 4 5 6 7 8 9 10
Number of groups

Figure 5: Network inefficiency trend when increasing the number of groups with fixed total demand

In another test, we fix the total demand (e.g., 200 units) and vary the number of groups (from
3 to 10). For each new group, its parameters are specified by a multiplication of the previous group
parameters. For example, αg = 1.1α(g−1) , βg = 1.05β(g−1) , γg = 1.01γ(g−1) . Since the total demand is
fixed, the amount of traffic in each group = 200 / number of group. So the amount of traffic for each group
decreases over time as number of group increases. The DUE and DSO are solved and the inefficiency ratio
is calculated. Figure 5 illustrates the trend when α, β, γ increase for each additional group. The total
system cost increases for both DUE and DSO solutions. However, the inefficiency ratio is around 2. We
also test the cases when the parameters α, β, γ decrease for each additional group. For example, different
from the previous experiment, now we use αg = 0.9α(g−1) , βg = 0.95β(g−1) , γg = 0.99γ(g−1) . Then we
obtain the same result for the network inefficiency trend. It suggests that the network inefficiency does
not depend on the number of groups as long as the total demand is fixed.
The results obtained from the single bottleneck model are important for the next step of studying
the multiple OD networks with simultaneous route and departure time choice. There are some similarity
between the single bottleneck and the multiple OD models in terms of delay cost function (α, β, γ),
preferred arrival time (t∗ ), complementarity formulation for dynamic equilibrium, etc. We will see the
insight that when the network is too congested, the multiple OD network problem is casted into a series
of only departure time choice problem.

3 Dynamic user equilibrium and dynamic system optimal

3.1 Dynamic network loading model
In dynamic traffic assignment, dynamic network loading (DNL) model is used as the method to load
the traffic, propagate them throughout the network, and compute travel time, delay, cost for the traffic.
There are several DNL in literature such as link exit function model (Merchant and Nemhauser, 1978a),
link delay function model (Friesz et al., 1989), cell transmission model (Daganzo, 1994, 1995), (Daganzo,
1994, 1995), polymorphic model (Nie, 2006), link transmission model (Yperman, 2007), etc. In this
paper, we embed the path-based cell transmission model (CTM) which is an extension of the original
cell transmission model (Daganzo, 1994, 1995). There are several features in this dynamic network
loading model:

8
 • The DNL keeps track of dynamic traffic on different paths in the network. The cells and cell-
connectors store the values of cell occupancy and flow, respectively, for different paths.
• The merging and diverging flows are computed based on demand at the upstream cells and supply
at downstream cells rather than using the exogenous ratios of turning movements (Daganzo, 1995).
• For given departure rate (or path flow) pattern r, there is a unique traffic state in terms of cell
occupancy vector x and traffic flow vector y. The results from DNL will be used to compute travel
time, schedule delay, and individual cost for traffic departing at time t and choosing path p for
t = 0, · · · , Tf and p ∈ P .
• The DNL guarantees there is no traffic holding (holding back issue) because the traffic always
advances forward if there is available capacity downstream.
• First-in-first-out (FIFO) is satisfied at path level and O-D level in DUE. However there may be a
FIFO violation at cell level such as at the diverging cells but this violation is reasonable in real
world traffic network.
• The limitation of this DNL is the path enumeration for reasonable size networks. The number of
paths for each O-D must be pre-defined and input as parameters.
The details of the path-based CTM are discussed in Ukkusuri et al. (2012) and Doan and Ukkusuri
(2012). Hence, they are omitted here and we will briefly describe the dynamic user equilibrium (DUE)
and dynamic system optimal (DSO) in the next two subsections. Notice that both route choice and
departure time choice are considered in the DUE and DSO models.

3.2 Dynamic user equilibrium

The dynamic user equilibrium problem is to find the departure rate (path flow) pattern such a way that
no one have an incentive to shift either his/her route or departure time. In this paper, we use the average
travel time method because it can accurately determine the average travel time for the traffic flow and it
does not overestimate travel time like the maximum travel time method (Ramadurai, 2009; Han et al.,
2011; Ukkusuri et al., 2012). Although the average travel time leads to the non-linear constraints which
increase the model complexity, it can be computed as efficiently as the maximum travel time model
since we use the heuristic projection algorithm proposed by Ukkusuri et al. (2012). Notice that, while
the single bottleneck model considers heterogeneous users based on different group g (αg , βg , γg , t∗g ), our
network-wide DTA models drop the notion of group g due to the complexity of the entire formulation.
However, the network-wide formulation includes other type of heterogeneity which is O-D based groups
(αw , β w , γ w , t∗w where w is O-D pair) in Eq. (15)-(16)
The formulation to compute average travel time is described as follows:

t
!
X
νp,t,t0 = max 0, rp,h − xsp,t0 ∀p ∈ P ; s ∈ p ∩ CS ; t = 0, · · · , T ; t0 = t, · · · , Tf (10)
h=0

Tf −1
X
(νp,0,h − νp,0,h+1 )h
h=0
T Tp,0 = ∀p ∈ P (11)
rp,0 + µ

Tf −1
X
(νp,t,h − νp,t,h+1 + νp,t−1,h+1 − νp,t−1,h )(h − t)
h=t
T Tp,t = ∀p ∈ P ; s ∈ p ∩ CS ; t = 0, · · · , T (12)
rp,t + µ

9
 Where p is a certain path. P is the set of all paths in the network. CS is the set of sink cells. T is
the maximum departure time and Tf is the maximum time horizon. rp,t and T Tp,t are departure rate
and travel time, respectively, for the flow using path p and departing at time t. νp,t,t0 is the auxiliary
variable to compute average travel time. µ is the infinitesimal parameter to avoid zero denominator in
the case rp,t = 0.
After travel time is computed, it is easy to determine the early and late schedule delays for the
departures of each path at each time interval:

ep,t = max{0, t∗w − T Tp,t − t} ∀p ∈ P ; t ∈ 0, · · · , T (13)

lp,t = max{0, t + T Tp,t − t∗w } ∀p ∈ P ; t ∈ 0, · · · , T (14)

The individual cost is the summation of travel time and schedule delay multiplied by the appropriate
penalties:

T Cp,t = αw × T Tp,t + β w × ep,t + γ w × lp,t ∀p ∈ P ; t ∈ 0, · · · , T (15)

Then, the dynamic equilibrium can be formulated by using the complementarity formulation which
guarantees dynamic user equilibrium conditions:

0 ≤ rp,t ⊥ αw T Tp,t + β w ep,t + γ w lp,t − Cw∗ ≥ 0 ∀w ∈ W ; p ∈ P w ; t ∈ 0, · · · , Tf (16)

0 ≤ ep,t ⊥ ep,t − (t∗w − t − T Tp,t ) ≥ 0 ∀w ∈ W ; p ∈ P w ; t ∈ 0, · · · , Tf (17)

T
X X
0 ≤ Cw∗ ⊥ rp,t − dw ≥ 0 ∀w ∈ W (18)
p∈Pw t=0

Where t∗w is the preferred arrival time for the traffic of O-D pair w. Cw∗ is the equilibrium cost for
each O-D pair w. ep,t and lp,t are early and late, respectively, schedule delay for the flow using path p and
departing at time t. dw is the demand for each O-D pair w. αw , β w , γ w are the penalties for travel time,
early schedule delay and late schedule delay, respectively, for each O-D. Assume that β w < αw < γ w .
Complementarity constraint (16) shows that, if rp,t > 0 the right hand side must be equal to zero.
In other words, the traffic at (p, t) has to pay a cost (travel time + schedule delay) which is equal to
the equilibrium cost Cw∗ . On the other hand, if rp,t = 0, the cost at (p, t) is greater than or equal to
the equilibrium cost Cw∗ . This constraint guarantees the dynamic equilibrium condition for the road
users. In constraint (17), the traffic departing at (p, t) pays either early or late penalty. Constraint
(18) represents the demand satisfaction condition. The overall formulation for dynamic user equilibrium
includes:

• Dynamic network loading (Section 3.1)

• Travel time (10)-(12), schedule delay (13)-(14), and individual cost computation (15)

• Dynamic equilibrium (16)-(18)

By using the projection algorithm (Ukkusuri et al., 2012), we can efficiently solve the DUE problem
above. In this paper, we will solve a series of DUE scenarios for different networks with increasing
demand levels.

10
3.3 Dynamic system optimal
The dynamic system optimal (DSO) problem is to find the traffic assignment to minimize the total
system cost. In this assignment, the users are supposed to follow the centralized rules even though some
may pay more cost than others. Although there are many DSO formulation in literature, this paper uses
the formulation proposed by Doan and Ukkusuri (2013). The advantages of using this model include: 1)
it computes the path marginal cost more accurately than previous models, 2) the assumptions are similar
to the DUE formulation (from DNL, supply and demand assumptions), which is required to further study
the network inefficiency and price of anarchy, 3) it can be solved by using projection algorithm similar to
the DUE model. The overall dynamic system optimal formulation is briefly described here. It contains
the objective function, the demand satisfaction constraints, the dynamic network loading model, and
the travel time and schedule delay computation.
Objective function:
X X
min TSC = rp,t × T Cp,t (19)
p∈P t∈0,··· ,T

Demand satisfaction constraint:

X X
rp,t = dw ∀w ∈ W (20)
p∈P w t∈0,··· ,T

Non-negativity constraint:

rp,t ≥ 0 ∀p ∈ P ; t ∈ 0, · · · , T (21)

Dynamic network loading model: Section 3.1

Travel time, schedule delay and individual cost computations: (10)-(12), (13)-(14), (15)

By temporally removing the DNL, travel time, schedule delay, and cost computation constraints, the
relaxed form of the model is used to derive the Lagrangian function and end up with the path marginal
cost condition:

∂T SC(r∗ )
 
∗ w
rp,t × −u = 0 ∀p ∈ P w ; w ∈ W ; t ∈ 0, · · · , T (22)
∂rp,t
∂T SC(r∗ )
− uw ≥ 0 ∀p ∈ P w ; w ∈ W ; t ∈ 0, · · · , T (23)
∂rp,t
X X
rp,t − dw = 0 ∀w ∈ W (24)
p∈P w t∈0,··· ,T
rp,t ≥ 0 ∀p ∈ P ; t ∈ 0, · · · , T (25)

∂T SC(r∗ )
∂rp,t is the path marginal cost at path p time t. It stands for the increase in the total system cost
if one unit of additional flow is perturbed at (p, t). uw is the equilibrium path marginal cost corresponding
to each O-D w. Constraints (22) and (23) show that, at the DSO solution if rp,t > 0, the path marginal
cost is minimum and equal for all traffic within an O-D pair. On the other hand, if rp,t > 0, the path
marginal cost at (p, t) may be greater than or equal to the equilibrium path marginal cost. Equations
(24) and (25) are only the demand satisfaction and non-negativity constraints. Notice that, although
condition (22)-(25) is not exactly the original DSO model described above, it is an approximation to

11
the DSO problem and this method is well-accepted in the transportation network modeling community
(Peeta and Mahmassani, 1995; Shen et al., 2006, 2007; Qian et al., 2012).
By solving the DSO problem with the same set of assumptions with the DUE problem, it is possible
to investigate the network inefficiency based on different networks with different levels of traffic demand,
which is presented in the next section.

4 Numerical results for network inefficiency in Multiple O-D Net-

works
Section 2 draws some conclusions about the network inefficiency in the single bottleneck models. In this
section, we conduct numerous tests to explore the network inefficiency patterns in different networks with
a spatial queue based model to capture traffic congestion. The average travel time method (Ukkusuri
et al., 2012) is used as the delay operator of the DNL since it can estimates the travel time more
accurately. For a given network and given user parameters (such as travel time, schedule delay penalty,
preferred arrival time), we vary the OD demand and solve both DUE problem (Section 3.2) and DSO
problem (Section 3.3) for each demand input. Then the total system costs corresponding to the DUE
and DSO solution are observed for network inefficiency computation. As the results, we will observe the
trend of network inefficiency pattern as demand increases.
The procedure for conducting the numerical experiment is showed in Figure 6. This is a general
procedure to study the trend of network inefficiency for a given network with different level of demand.
In the simultaneous route and departure time choice problems, a certain amount of OD traffic desires
to traverse the network. Road users may value the travel time and schedule delay differently, and they
may have a different preferred arrival time at their destinations. In the user equilibrium, the traffic is
assigned such a way that the experienced cost is minimized while in the system optimal, the total system
cost is optimized.

Step 0: Given
-Network topology (cells
(cells, cell connectors,
connectors capacity
capacity, jam density,
density etc)
-User characteristics (travel time, schedule delay penalty, preferred arrival time)

Step
p 1: Define demand level for each scenario i from 1 to n

Step 2: Solve DUE problem (Section 3.2) Step 3: Solve DSO problem (Section 3.3)
-Using projection algorithm -Using projection algorithm
-Obtain total system cost -Obtain total system cost

Step 4: Compute network inefficiency

-As the ratio of total system cost in DUE and that in DSO

Step 5: Consider scenario i = i + 1,

1 go to Step 2

Step 6: Stop if i = n
Plot the network inefficiency pattern for n scenarios

Figure 6: Test procedure for each network

It is well known that the dynamic traffic assignment problem, in general, can have multiple solutions.
There is no study so far make a clear conclusion about the uniqueness or multiple solution properties.

12
One of the reason stems from the difficulty to obtain an exact solution for multiple OD networks with
high demand level. All of the heuristic algorithms in literature can only solve the problem approximately,
i.e. they cannot obtain a zero relative gap. While we can employ the exact solution methods to solve
DUE (1)-(5) and DSO (6)-(9) in the single bottleneck models, we use the heuristic algorithms to solve
DUE (10)-(18) and DSO (19)-(25) in the network-wide models. For each scenario, we may obtain several
approximate solutions (in terms of departure rate) based on different stopping criteria such as relative
gap or solution difference between two consecutive iterations. Especially with higher demand level, we
need to solve the DUE and DSO for several times before taking the average values as final solution.
In this paper, we use four test networks with different sizes and number of OD pairs (Figure 7). The
single link network is an extension of the single bottleneck model. The second network consists a single
O-D with three paths. The third one includes multiple O-D but there is no route choice for each O-D.
The last one is a medium-sized network and has multiple O-D pairs with several paths for each O-D.
This network is more general than the other three.

13
 Figure 7: Several test networks: a) Single link, b) X-shape, c) Ziliaskopoulos’, d) Nguyen-Dupuis’

The first network contains only a single link divided into 7 cells (Figure 7a). We create a bottleneck
with half of the regular capacity at cell 6. There is a departure time choice dimension but no route choice
available for the travelers. We solve the DUE and DSO problems with the demand level varying from
100 to 2000. Figure 8 shows that both DUE and DSO total system costs increase non-linearly and the
DUE cost raises faster than DSO cost, which is similar to the result from the single bottleneck model.
It is observed that the network inefficiency ratio goes up from NI = 1 at demand d = 100 to NI = 1.80
at d = 1400. The network inefficiency seem to stabilize at this value regardless how much demand is
added.

14
 5
x 10
2 2

Total cost in DUE

Total cost in DSO
Network inefficiency

1.5 1.5

Network inefficiency ratio

Total system cost

1 1

0.5 0.5

0 0
0 200 400 600 800 1000 1200 1400 1600 1800 2000
Demand for OD 1−7

Figure 8: Network inefficiency for single link network

It is not surprise that the network inefficiency converges in the single link network because it is a
direct extension of the single bottleneck model in Section 2. Two differences are in 1) the spatial queue-
based model and 2) the physical distance with free-flow travel time feature in this network. The spatial
queue feature does not affect the out come of the single link model because the spill-back effect does
not influence any traffic in any other link. In stead, if it is very congested, the traffic only spill-backs
to the origin cell with infinite capacity. Thus the outcome of the spatial-queue single link is exactly the
same as the point queue single link where we assume free-flow travel time in entire physical link and
traffic only queues vertically at the bottleneck point. In fact, the physical distance between the origin
and destination is the cause of the lower network inefficiency as showed belows.
In the single bottleneck model, we assume that free flow travel time is zero and there is only queuing
time taken into account. The queuing cost is equal to the queuing time multiplied by penalty parameter
α. The trade-off between queuing cost and schedule delay cost is considered for the final departure time
choice solution. In DSO, the queuing time is zero and the total cost now is only based on the schedule
delay cost. As the result, we can obtain high inefficient ratios (such as 2 or 2.38 in Figure 3, 4). On the
other hand, in the cell-based networks, the travel time penalty α is multiplied by not only queuing time
but also free flow travel time. Therefore the network inefficiency ratio in physical network is less that in
single bottleneck only. For example, the network inefficiency ratio is 10/5 = 2 for the single bottleneck.
If the free flow travel time is considered for the entire path, a free flow travel cost c is added to both
numerator and denominator, which generates a smaller network inefficiency, i.e. (10 + c)/(5 + c) < 2.
We also expect to see that the network inefficiency in bigger network is usually less than that in the
smaller one.
In Figure 9, three patterns: Total cost in DUE, Total cost in DSO and Network inefficiency are
similar to those in Figure 8. If we excludes the free flow travel time cost from the total system cost of
both DUE and DSO, we obtain a new Network Inefficiency at the bottleneck only (the purple line) which
is higher than the original Ratio of UE/SO (blue line). In addition, the squared-dot pattern stabilizes
around 2 which is similar to the single bottleneck model.

15
 5
x 10
2

Total cost in DUE

Total cost in DSO
Network inefficiency
NI without FFTT 2

Network inefficiency ratio

Total system cost

0 0
0 200 400 600 800 1000 1200 1400 1600 1800 2000
Demand for OD 1−7

Figure 9: The effect of free flow travel time (FFTT) to the network inefficiency computation

The X-shaped network in Figure 7b includes four O-D pairs. However, there is no route choice for
any traffic because there is only one path for each OD pair. There are a merges and a diverge in the
network and the traffic propagation are handled by the DNL module (Section 3.1. We vary the origin
demand level from 100 to 2000. For example, in the first scenario, 67 vehicles travel from 1 to 8, 33
vehicles travel from 1 to 10. For each given value of demand, DUE and DSO are solved and the results
are presented in Figure 10. The network inefficiency ratio increases from 1 and seems to stabilize around
1.6.
The network inefficiency pattern in this case has similar form to the one in Figure 8 except that the
convergence value is smaller (1.6 compared to 1.8). The first observation can be explained by the same
departure time choice feature. Traffic cannot choose other route for their utility. Hence in the network
with departure time choice only, the relative difference between dynamic user equilibrium and dynamic
system optimal may be bigger.

16
 5
x 10
4 2
Total cost in DUE
Total cost in DSO
Network inefficiency

3 1.5

Network inefficiency ratio

Total system cost

2 1

1 0.5

0 0
0 200 400 600 800 1000 1200 1400 1600 1800 2000
Demand for Origin 1 and Demand for Origin 4

Figure 10: Network inefficiency for X-shaped network

The third test network contains one OD pair with three paths (Figure 7c). Similarly to the X-shaped
network in Figure 7b, this network has both merges and diverges. The interaction between traffic at
those cells are handled by the path-based DNL. The DUE and DSO problems for this network include
both route and departure time choice dimensions. Again, for a given set of network topology and user
penalty functions, we vary the OD demand from 100 to 2000 and solve both DUE and DSO for each
demand level. The DUE and DSO total system costs and the network inefficiency are plotted with
demand. We also observe that the network inefficiency stabilizes around 1.2 as the demand increases.
This numerical test shows that, with the route choice phenomenon, the relative difference between
DUE and DSO reduces, which leads to a lower network inefficiency.

5
x 10
2 2
Total cost in DUE
Total cost in DSO
Network inefficiency
Network inefficiency ratio
Total system cost

1 1

0 0
0 200 400 600 800 1000 1200 1400 1600 1800 2000
Demand for OD 1−10

Figure 11: Network inefficiency for Ziliaskopoulos network

The last series of tests are based on the Nguyen-Dupuis network (Figure 7d). In the cell-based form,
it includes 57 cells and 63 cell connectors. There are two origins and two destinations forming four O-D

17
pairs. Each O-D is predefined with three paths. We test the total demand level from 200 to 3000 with
the increasing step of 200. Both DUE and DSO are solved and the results are plotted in Figure 12. The
network inefficiency goes from 1 to around 1.11. The relative difference between the DUE and DSO total
system cost is not significant.

4
x 10
14 1.4
Total cost in DUE
Total cost in DSO
12 Network inefficiency 1.2

10 1

Network inefficiency ratio

Total system cost

8 0.8

6 0.6

4 0.4

2 0.2

0 0
0 500 1000 1500 2000 2500 3000
Total demand

Figure 12: Network inefficiency for Nguyen-Dupuis network

In summary, within a network, when the network capacity and the user parameters are fixed, we
observe that the network inefficiency increases from 1 and stabilizes at a certain value. In the single
bottleneck model, we obtain a value of 2 for homogeneous case and different values heterogeneous cases
(Figure 3, 4). In the single link, the convergent ratio is about 1.8 (Figure 8). That for the X-shaped
network is 1.6 (Figure 11) and that for the Ziliaskopoulos network is 1.2 (Figure 10). For the Nguyen-
Dupuis network, the inefficiency ratio does not exceed 1.1 (Figure 12).
An interesting phenomenon that we observe after all the extensive analysis is that the network
inefficiency stabilizes to a fixed value for each network. This is hardly surprising since at low congestion
(free flow conditions) the equilibrium and system optimum solutions are typically the same. Similarly,
at very high congestion (as demand increases for a given network), the degrees of freedom in terms of
the route choice reduce significantly. And the road users depend only on their departure time decision.
Fortunately, we showed in Section 2 that, in the single bottleneck model with pure departure time choice,
the network inefficiency will definitely converge with unique NI for each demand level. Therefore the
network inefficiency in general networks ultimately stabilizes to a fixed value.

5 Conclusions and future work

This paper focuses on a systematic numerical study to explore the trend of the network inefficiency for
the dynamic traffic networks. We also observe that the price of anarchy may not be a good measure
in a practical point of view when one desires to understand the inefficiency in typical dynamic traffic
networks. The worst case of network inefficiency usually corresponds to an extreme case and under
specific assumptions which are hardly found in reality. It may not be necessary to design the system
for the worst case in the economics point of view. In addition, the single value of POA may be less
meaningful than the trend of network inefficiency when varying each dimension such as demand or
network size. By considering the pattern of network inefficiency, the researchers and practitioners may
be able to determine which level of inefficiency should be tackled to improve the network performance.

18
 We start from the single bottleneck model and show that the network inefficiency is constantly
2 for the homogeneous commuter model regardless demand level, preferred arrival time and penalty
functions. For the heterogeneous single bottleneck model, computing the network inefficiency is not as
straight forward as the homogeneous case, and it requires to solve both DUE and DSO problems. This
network inefficiency varies based on the values of queuing time and schedule delay penalties. When
the total demand increases, the network inefficiency converges to a certain value. When we vary the
number of groups and keep the total demand unchanged, the network inefficiency stabilizes around a
certain value, too. After the single bottleneck, four test networks are taken into account. The path-based
CTM is embedded as the dynamic network loading model and we use the average travel time method to
compute user travel cost. For each network, we vary the demand and solve the DUE and DSO problems
for each level of demand to determine the network inefficiency. The trend of the network inefficiency
is plotted for each network. By increasing the demand, the network inefficiency increase from 1 to a
certain value. By increasing the network size, the network inefficiency reduces. It is because of the free
flow travel time included in the travel time cost function of each user, which reduces the relative gap
between DUE and DSO solutions. We also observe that the route choice dimension helps to reduce
the network inefficiency. And finally, the network inefficiency stabilizes to a certain value because of
the decrease in the degrees of freedom for route choice when network is too congested, which turns the
system to the departure time choice problem. The above results are obtained from specific configurations
including: CTM network representation, path-based network loading, simultaneous route and departure
time choice, single or multiple O-D network, O-D based heterogeneous users, similar input parameters
for both DUE and DSO, etc. Other model configuration can use similar framework to obtain the network
inefficiency trend for each test.
By studying the network inefficiency, researchers can have a better understanding on the performance
of the traffic network based on the stable equilibrium state and the efficient system optimal state.
The network inefficiency suggests how much the network performance can be improved. By providing
incentive for the road users, they may shift to the designed routes and departure times to guarantee:
1) the equilibrium in the user cost, and 2) the optimum in the total system cost. The methods to
reduce the gap between DUE and DSO are typically based on mechanism design techniques. It includes
congestion pricing, signal optimization, network design, etc. Based on the trend of network inefficiency
observed in this study, researchers may have better schemes to apply the mechanism design in particular
networks and specify demand conditions. In addition, a theoretical treatment of the network inefficiency
in dynamic traffic networks is an open area of research. It is our hope that this paper will stoke further
interest on this important topic.

Acknowledgements
This research was partly funded by the U.S. National Science Foundation grants 1017933 and 1004528.
The authors are grateful for the support. The conclusions for this study reflect the opinions of authors,
not NSF. The authors also appreciate the constructive comments of two anonymous reviewers which
improves the quality of this work.

References
Anshelevich, E., Ukkusuri, S., 2009. Equilibria in dynamic selfish routing. Lecture Notes in Computer
Science 5814, 171–182.

Arnott, R., de Palma, A., Lindsey, R., 1988. Schedule delay and departure time decisions with hetero-
geneous commuters. Transportation Research Record 1197, 56–67.

Arnott, R., de Palma, A., Lindsey, R., 1993. A structural model of peak-period congestion: a traffic
bottleneck with elastic demand. The American Economic Review 83 (1), 161–179.

19
Arnott, R., de Palma, A., Lindsey, R., 1994. A welfare congestion tolls with heterogenous commuters.
Journal of Transportation Economics and Policy 28 (2), 139–161.
Ban, X. J., Liu, H. X., Ferris, M. C., Ran, B., 2008. A link-node complementarity model and solution
algorithm for dynamic user equilibria with exact flow propagations. Transportation Research Part B
42 (9), 823–842.
Carey, M., 1986. A constraint qualification for a dynamic traffic assignment model. Transportation
Science 20 (1), 55–58.
Carey, M., 1987. Optimal time varying flows on congested network. Operation Research 35 (1), 58–69.
Carey, M., 1992. Nonconvexity of the dynamic traffic assignment problem. Transportation Research Part
B 26 (2), 127–133.
Chau, C. K., Sim, K. M., 2003. The price of anarchy for non-atomic congestion games with symmetric
cost maps and elastic demands. Operations Research Letters 31 (5), 327–334.
Daganzo, C. F., 1985. The uniqueness of a time-dependent equilibrium distribution of arrivals at a single
bottleneck. Transportation Science 19 (1), 29–37.
Daganzo, C. F., 1994. The cell transmission model: a simple dynamic representation of highway traffic.
Transportation Research Part B 28 (4), 269–287.
Daganzo, C. F., 1995. The cell transmission model, part ii: Network traffic. Transportation Research
Part B 29 (2), 79–93.
Doan, K., Ukkusuri, S., 2012. On the holding-back problem in the cell transmission based dynamic traffic
assignment models. Transportation Research Part B 46 (9), 1218–1238.
Doan, K., Ukkusuri, S., 2013. Dynamic system optimal for general network embedding cell transmission
model. In review.
Doan, K., Ukkusuri, S., Han, L., 2011. On the existence of pricing strategies in the discrete time hetero-
geneous single bottleneck model. Transportation Research Part B 45 (9), 1483–1500.
Friesz, T. L., Bernstein, D., Smith, T. E., Tobin, R. L., Wie, B., 1993. A variational inequality formulation
of the dynamic network user equilibrium problem. Operation Research 41 (1), 179–191.
Friesz, T. L., Han, K., Neto, P. A., Meimand, A., Yao, T., 2013. Dynamic user equilibrium based on a
hydrodynamic model. Transportation Research Part B 47, 102–126.
Friesz, T. L., Luque, J., Tobin, R. L., Wie, B.-W., 1989. Dynamic network traffic assignment considered
as a continuous time optimal control problem. Operations Research 37 (6), 893–901.
Ghali, M. O., Smith, M. J., 1995. A model for the dynamic system optimum traffic assignment problem.
Transportation Research Part B 29 (3), 155–170.
Han, D., Lo, H. K., Sun, J., Yang, H., 2008a. The toll effect on price of anarchy when costs are nonlinear
and asymmetric. European Journal of Operational Research 186 (1), 300–316.
Han, D., Lo, H. K., Yang, H., 2008b. On the price of anarchy for non-atomic congestion games under
asymmetric cost maps and elastic demands. Computers and Mathematics with Applications 56 (10),
2737–2743.
Han, L., Ukkusuri, S. V., Doan, K., 2011. Complementarity formulations for the cell transmission model
based dynamic user equilibrium with departure time choice, elastic demand and user heterogeneity.
Transportation Research Part B 45 (10), 1749–1767.

20
Jayakrishnan, R., Mahmassani, H. S., Hu, T.-Y., 1994. An evaluation tool for advanced traffic informa-
tion and management systems in urban networks. Transportation Research Part C 2 (3), 129–147.

Karakostas, G., Kim, T., Viglas, A., Xia, H., 2011. On the degradation of performance for traffic networks
with oblivious users. Transportation Research Part B 45 (2), 364–371.

Koutsoupias, E., Papadimitriou, C., 1999. Worst-case equilibria. In: Proceedings of the 16th Annual
Symposium on Theoretical Aspects of Computer Science,.

Liu, Y., Nie, Y. M., 2010. Morning commute problem considering route choice, user heterogeneity and
alternative system optima. Transportation Research Part B 45 (4), 619–642.

Lo, H. K., Szeto, W., 2002. A cell-based variational inequality formulation of the dynamic user optimal
assignment problem. Transportation Research Part B 36 (5), 421–443.

Lu, C.-C., Mahmassani, H. S., Zhou, X., 2008. A bi-criterion dynamic user equilibrium traffic assignment
model and solution algorithm for evaluating dynamic road pricing strategies. Transportation Research
Part C 16, 371–389.

Merchant, D. K., Nemhauser, G. L., 1978a. A model and an algorithm for the dynamic traffic assignment
problems. Transportation Science 12 (3), 183–199.

Merchant, D. K., Nemhauser, G. L., 1978b. Optimality conditrions for a dynamic traffic assignment
model. Transportation Science 12 (3), 200–207.

Nie, Y. M., 2006. A variational inequality approach for inferring dynamic origin-destination travel de-
mands. Ph.D. thesis, University of California, Davis.

Nie, Y. M., Zhang, H. M., 2010. Solving the dynamic user optimal assignment problem considering queue
spillback. Net 10 (1), 49–71.

Peeta, S., Mahmassani, H. S., 1995. System optimal and user equilibrium time-dependent traffic assign-
ment in congested networks. Annals of Operations Research 60 (1), 81–113.

Qian, Z. S., Shen, W., Zhang, H., 2012. System-optimal dynamic traffic assignment with and with-
out queue spillback: Its path-based formulation and solution via approximate path marginal cost.
Transportation Research Part B 46 (7), 874–893.

Ramadurai, G., 2009. Novel dynamic user equilibrium models: analytical formulations, multi-dimensional
choice, and an efficient algorithm. Ph.D. thesis, Department of civil and environmental engineering,
Rensselaer Polytechnic Institute (Troy, NY).

Ramadurai, G., Ukkusuri, S. V., Zhao, S., Pang, J.-S., 2010. Linear complementarity formulation for
single bottleneck model with heterogeneous commuters. Transportation Research Part B 44 (2), 193–
214.

Ran, B., Boyce, D. E., LeBlanc, L. J., 1993. A new class of instantaneous dynamic user-optimal traffic
assignment models. Operations Research 41 (1), 192–202.

Roughgarden, T., 2002. Selfish routing. Ph.D. thesis, Cornell University.

Roughgarden, T., Tardos, E., 2002. How bad is selfish routing? Journal of the ACM 49 (2), 236—259.

Shen, W., Nie, Y. M., Zhang, H., 2006. Path-based system optimal dynamic traffic assignment models:
formulation and solution methods. In: Proceedings of the IEEE ITSC 2006. pp. 1298–1303.

21
Shen, W., Nie, Y. M., Zhang, H., 2007. On path marginal cost analysis and its relation to dynamic
system-optimal traffic assignment. In: Proceedings of the 17th International Symposium of Transport
and Traffic Theory. pp. 327–360.

Small, K., 1982. Small, 1982. the scheduling of consumer activities: work trips. The American Economic
Review 72 (3), 467–479.

Smith, M., 2013. A link-based elastic demand equilibrium model with capacity constraints and queueing
delays. Transportation Research Part C 29, 131–147.

Ukkusuri, S., 2002. Linear programs for the user optimal dynamic traffic assignment problem. Master’s
thesis, University of Illinois at Urbana-Champaign.

Ukkusuri, S., Han, L., Doan, K., 2012. Dynamic user equilibrium with a path based cell transmission
model for general traffic networks. Transportation Research Part B 46 (10), 1657–1684.

Vickrey, W. S., 1969. Congestion theory and transport investment. The American Economic Review
59 (2), 251–261.

Yperman, I., 2007. The link transmission model for dynamic network loading. Ph.D. thesis, University
of Leuven Energy Institute.

Ziliaskopoulos, A. K., 2000. A linear programming model for the single destination system optimum
dynamic traffic assignment problem. Transportation Science 34 (1), 37–49.

22