# The Analysis of Braess’ Paradox and Robustness Based on Dynamic Traffic Assignment Models

Authors: Bai-Bai Fu; Chun-Xue Zhao; Shu-bin Li
Journal: Discrete Dynamics in Nature and Society
 (2013)

---

## Abstract

The investigation of the paradox and robustness about the traffic network is an important branch of the traffic assignment. In this paper, Braess’ paradox and robustness of the dynamic traffic network are analyzed by the dynamic traffic assignment models. In addition, the relationship of total costs with different traffic assignment models is discussed. The results show that the paradox only occurs in certain range; the robustness of the network and the relationship of total traffic costs are changed as the traffic demand changes, which provides theoretical guidance for the urban transportation planning.


---

## Body

## 1. Introduction

In recent years, the proposal of the intelligent transportation system (ITS) forces people to investigate the dynamic traffic assignment (DTA). The mathematical programming [1, 2], the optimal control [3, 4], and the variational inequality (VI) [5, 6] were proposed, respectively, and labeled as three main analytical approaches. Specially, the optimal control includes dynamic user equilibrium (DUE) [7–11] and dynamic system optimal (DSO) [12].Braess’ paradox is an important phenomenon during the traffic assignment [13], which has been widely investigated in the scientific literatures [14–16], such as X. Zhang and H. M. Zhang [17] studied the route choices and a novel paradox in queuing networks; Pas and Principio [18] gained the specific range that the paradox occurs when the link cost only depends on the link flow. Braess’ paradox is rooted in the essence of the user equilibrium (UE) assignment where each user minimizes his/her own travel time between an origin and a destination. The most previous work mainly focuses on the paradox under the static traffic. In recent years, the paradox of the dynamic traffic assignment began to develop, such that Arnott et al. [19] discussed the properties of the dynamic traffic equilibrium including a paradox; Hallefjord et al. [20] analyzed the traffic paradox when the travel demand is elastic; Zhang et al. [21] investigated Braess’ paradox in the dynamic traffic assignment. In this paper, we investigate the paradox phenomenon of the dynamic traffic network using VI method and assuming the link cost at time t is related to the flow of this link and the adjacent links at the same paths at time t.The robustness, as an important index valuing the stability of the system, is usually used to study the network under the partial degradation. In the process of studying the robustness, it is generally classified into the following two classes according to whether the system structure remains intact: (i) certain component of the network is removed; (ii) no component is removed, but the function of certain portion of the network falls into the perturbations. Based on different classes, different network function measures are proposed to examine the robustness of the network. In this paper, we use the relative total cost index to measure the robustness of the dynamic network considering the influence of the flow on other links when certain component (node or link) is removed.The paper is organized as follows. We first briefly recall main analytical models of the traffic assignment; then we discuss whether the paradox occurs or not under the given link cost and investigate the relationship between the total cost under DUE and that under DSO; subsequently, we investigate the robustness of the dynamic network; at last, the conclusions about the results of the paper are given.


## 2. Main Analytical Models

### 2.1. The DUE

In this section, we briefly reviewed dynamic equilibrium models [8–11] of the traffic network. Assume that the traffic network includes a set W of origin/destination (O/D) pairs with nW elements and a set P of paths joining O/D pairs; DUE is based on the behavioral assumption that only the minimum cost routes are used at each time t, whose mathematical expression is given as follows:
(1)Cp(x*(t))=λw(t),ifxp*(t)>0,Cp(x*(t))≥λw(t),ifxp*(t)=0,
where Cp(·) is the cost on the path p under the DUO, λw(t) is the minimal path costs at time t, x*(t) is a path flow pattern satisfying the flow conservation at time t, and [0,T] denotes the time interval under consideration.Under the equilibrium state, the link flows and the route flows satisfy the following conservation of flow equations:(2)fa(t)=∑p∈Pxp(t)δap,∀a∈L,
where fa(t) is the flow on the link a, xp(t) is the flow on the rout p, δap=1 if link a is contained in route p, and δap=0, otherwise. The traffic demand at time t must satisfy the following conservation of flow:
(3)dw(t)=∑p∈Pwxp(t),∀w∈W.
In addition, the model meets the following nonnegative constraint and boundary initial condition:
(4)xa(t)≥0,xa(0)=0.


### 2.2. The DSO

DSO calls for the flow pattern that minimizes the total travel time in the system at each timet, whose mathematical expression is shown as follows:
(5)Cp′(x*(t))=μw(t),ifxp*(t)>0,Cp′(x*(t))≥μw(t),ifxp*(t)=0,
where Cp′(·) is the cost on the path p under the DSO and μw(t) is the minimal marginal path costs at time t. The constraint under the DSO is the same as that under DUE and is omitted here.In addition, the link costs under DUE and DSO satisfy the relationship as follows:(6)ca′(fa(t))=ca(fa(t))+fa(t)dca(fa(t))dfa(t),
where ca(·), ca′(·) are costs on link a under DUE and DSO, respectively; the link cost under the DSO is also known as the marginal link cost.


### 2.3. The Variational Inequalities Equivalent to DUE

Compared with the mathematical programming and optimal control, the variational inequality is the more effective way to describe the dynamic traffic assignment problem. The extensive investigation has gone ahead, such that Frieza and Smith proposed the variational inequality of the dynamic assignment program based on the path cost; Ran and Boyce proposed the variational inequality of the dynamic user optimal model based on the link cost. DUO based on the path cost is equivalent to the variational inequality as follows:(7)∫0T∑rs∑pλprs*(t)[fprs(t)-fprs*(t)]dt≥0,
where λprs*(t) is the path cost on O/D pair rs at time t satisfying DUO, fprs(t) is the path flow on O/D pair rs at time t, and fprs*(t) is the path flow on O/D pair rs at time t satisfying DUE.


## 2.1. The DUE

In this section, we briefly reviewed dynamic equilibrium models [8–11] of the traffic network. Assume that the traffic network includes a set W of origin/destination (O/D) pairs with nW elements and a set P of paths joining O/D pairs; DUE is based on the behavioral assumption that only the minimum cost routes are used at each time t, whose mathematical expression is given as follows:
(1)Cp(x*(t))=λw(t),ifxp*(t)>0,Cp(x*(t))≥λw(t),ifxp*(t)=0,
where Cp(·) is the cost on the path p under the DUO, λw(t) is the minimal path costs at time t, x*(t) is a path flow pattern satisfying the flow conservation at time t, and [0,T] denotes the time interval under consideration.Under the equilibrium state, the link flows and the route flows satisfy the following conservation of flow equations:(2)fa(t)=∑p∈Pxp(t)δap,∀a∈L,
where fa(t) is the flow on the link a, xp(t) is the flow on the rout p, δap=1 if link a is contained in route p, and δap=0, otherwise. The traffic demand at time t must satisfy the following conservation of flow:
(3)dw(t)=∑p∈Pwxp(t),∀w∈W.
In addition, the model meets the following nonnegative constraint and boundary initial condition:
(4)xa(t)≥0,xa(0)=0.


## 2.2. The DSO

DSO calls for the flow pattern that minimizes the total travel time in the system at each timet, whose mathematical expression is shown as follows:
(5)Cp′(x*(t))=μw(t),ifxp*(t)>0,Cp′(x*(t))≥μw(t),ifxp*(t)=0,
where Cp′(·) is the cost on the path p under the DSO and μw(t) is the minimal marginal path costs at time t. The constraint under the DSO is the same as that under DUE and is omitted here.In addition, the link costs under DUE and DSO satisfy the relationship as follows:(6)ca′(fa(t))=ca(fa(t))+fa(t)dca(fa(t))dfa(t),
where ca(·), ca′(·) are costs on link a under DUE and DSO, respectively; the link cost under the DSO is also known as the marginal link cost.


## 2.3. The Variational Inequalities Equivalent to DUE

Compared with the mathematical programming and optimal control, the variational inequality is the more effective way to describe the dynamic traffic assignment problem. The extensive investigation has gone ahead, such that Frieza and Smith proposed the variational inequality of the dynamic assignment program based on the path cost; Ran and Boyce proposed the variational inequality of the dynamic user optimal model based on the link cost. DUO based on the path cost is equivalent to the variational inequality as follows:(7)∫0T∑rs∑pλprs*(t)[fprs(t)-fprs*(t)]dt≥0,
where λprs*(t) is the path cost on O/D pair rs at time t satisfying DUO, fprs(t) is the path flow on O/D pair rs at time t, and fprs*(t) is the path flow on O/D pair rs at time t satisfying DUE.


## 3. Application of Analytical Models

### 3.1. The Analysis about Paradox

#### 3.1.1. The Equilibrium Solution of the Four-Link Network under DUE

As we know, the paradox phenomenon exists in many networks with different topologies; Braess’ network has been investigated by a large number of researchers; it is representative because it can simplify the problem and clearly explain traffic phenomena. In this paper, we also consider Braess’ network with a single origino and a single destination r in this paper. Figure 1 depicts the network before the addition of the new link pq. Let the total demand for the travel from origin o to destination r be dw(t) and dw(t)=t; further, assume that the link cost is a function of the flow not only on this link but also on other links. Because the influence of the adjacent links is dominant, we assume that the other links are only limited to the adjacent links on the same path in this work. At the same time, assume that the problem is symmetric; further, the travel time is link-flow dependent and it increases rapidly as a function of the flow on the link.Figure 1
The four-link network.Specifically, the link cost functions of the four-link network in Figure1 are
(8)cop(t)=10(γfop(t)+fpr(t)),cqr(t)=10(γfqr(t)+foq(t)),coq(t)=(γfoq(t)+fqr(t))+50,cpr(t)=(γfpr(t)+fop(t))+50,
where cij(t) is the travel cost on link ij at time t, fij(t) is the flow on link ij at time t, γ is the scaling parameter which differentiates the influence between the given link only and others, generally, γ≥1. In the four-link network, there are two paths from the origin o to the destination r and the costs along the paths are given as follows:
(9)C1(t)=cop(t)+cpr(t)=11(γ+1)f1(t)+50,C2(t)=coq(t)+cqr(t)=11(γ+1)f2(t)+50,
where Ck(t) is the travel cost from o to r along path k at time t; in addition,
(10)f1(t)=fop(t)=fpr(t),f2(t)=foq(t)=fqr(t),
where fk(t) is the flow from o to r along path k at time t, the total demand satisfies the following conservation of the flow: dw(t)=f1(t)+f2(t). According to the definition of the UE, it is easy to get
(11)f1*(t)=f2*(t)=t2,C1(t)=C2(t)=11(γ+1)t2+50,
where fk*(t) is the equilibrium flow from o to r along path k at time t. Hence, the total system travel time under DUE before the addition of the new link is given as follows:
(12)C4(t)=11(γ+1)t22+50t,
where C4(t) is the total system travel cost under DUE for the four-link network.


#### 3.1.2. The Equilibrium Solution of the Five-Link Network under DUE

After adding the linkpq, there appears a new path opqr from o to r in Figure 2.Figure 2
The five-link network.The link cost functions are given as follows:(13)cop(t)=10(γfop(t)+fpr(t)+fpq(t)),cqr(t)=10(γfqr(t)+foq(t)+fpq(t)),coq(t)=(γfoq(t)+fqr(t))+50,cpr(t)=(γfpr(t)+fop(t))+50,cpq(t)=(γfpq(t)+fop(t)+fqr(t))+10.
The traffic flow on each link is as follows:
(14)fop(t)=f1(t)+f3(t),fpr(t)=f1(t),foq(t)=f2(t),fqr(t)=f2(t)+f3(t),fpq(t)=f3(t).
The costs on the paths are
(15)C1(t)=11(γ+1)f1(t)+(10γ+11)f3(t)+50,C2(t)=11(γ+1)f2(t)+(10γ+11)f3(t)+50,C3(t)=(10γ+1)(f1(t)+f2(t))+(21γ+22)f3(t)+10.
The total demand satisfies the conservation of the flow as follows: dw(t)=f1(t)+f2(t)+f3(t).The variational inequality of the five-link dynamic traffic network overt∈[0,T] is given as follows:
(16)∫0T(11(γ+1)f1*(t)+(10γ+11)f3*(t)+50)×(f1(t)-f1*(t))+(11(γ+1)f2*(t)+(10γ+11)f3*(t)+50)×(f2(t)-f2*(t))+((10γ+1)(f1*(t)+f2*(t))+(21γ+22)f3*(t)+10(10γ+1)(f1*(t)+f2*(t)))(f3(t)-f3*(t))dt≥0.
Because
(17)dw(t)=f1(t)+f2(t)+f3(t),dw(t)=f1*(t)+f2*(t)+f3*(t),f1*(t)=f2*(t),
we have
(18)∫0T((13γ+11)f1*(t)-11(γ+1)t+40)×(f1(t)+f2(t)-2f1*(t))dt≥0;
if f1*(t)=0, and we have -11(γ+1)t+40≥0, then t≤40/11(γ+1); if f3*(t)=0, and at this time, f1*(t)=t/2, then t>80/(9γ+11); when t∈(40/11(γ+1),80/(9γ+11)],
(19)f1*(t)=f2*(t)=11(γ+1)t-4013γ+11,f3*(t)=-(9γ+11)t+8013γ+11.Assumeγ=2; the equilibrium flow of the five-link network is pictured in Figure 3, in ranges I and II [0,33/40], only the new path is used; in range III (33/40,80/29), all three are used; in range IV [80/29,+∞), only the first two paths are used; that is, the third path is never used when t>80/29.Figure 3
The equilibrium flow of the dynamic network.Corresponding to different ranges, the total travel cost of five-link network is given as follows:(20)C5(t)={(21γ+22)t2+10t,ift≤4011(γ+1),t[(31γ2+33γ)t+40(9γ+11)13γ+11+50(31γ2+33γ)t+40(9γ+11)13γ+11],if4011(γ+1)if<t<809γ+11,11(γ+1)t22+50t,ift≥809γ+11,
where C5(t) is the total system travel cost under DUE for the five-link network.


#### 3.1.3. The Paradox of Dynamic Traffic Networks

LettingC5(t)>C4(t), we get t∈(80/(31γ+33),80/(9γ+11)); letting γ=2, the paradox occurs in ranges II and III in Figure 3.In order to capture the trend of the paradox when we take different values ofγ, we give the definition of the average difference of two functions F1,F2 in range [a,b]((a,b][a,b),(a,b)), a>b as follows:
(21)D(F1,F2)=|F1-F2|b-a.
We assume that the severity of the paradox is proposal to the average difference and use of the average difference of C4,C5 in range (80/(31γ+33),80/(9γ+11)) to represent the severity of the paradox.In Figure4, we discuss the situations when γ=1,2,5, respectively, and find that the areas where the paradox occurs are different when the values of γ are different; thus we may take some measures to control the influence between the links as time and traffic demand change in order to avoid or decrease the occurrence of the paradox; in addition, in most range, the greater γ is, the smaller the range of the traffic demand in which the paradox occurs is; that is, the severity and the range in which the paradox occurs increase with the influence of other links decreasing, which reminds us to let down the influence between links as much as possible if we wish to decrease the occurrence of the paradox.Figure 4
The severity that the paradox occurs whenγ is different.


#### 3.1.4. The Effect of the Adding Link under DSO

As known, when the given link cost is a function of the flow on the given link only, adding a new link did not reduce the total system travel time even under SO [18]. When the link cost does not only depend on the flow on the given link only, we discuss whether the phenomenon occurs or not in the following. As we know, DSO is obtained by charging users the marginal cost of traveling (see formula (6)); for the link cost in this work, the corresponding path marginal cost equations are given as follows:
(22)cop′(t)=10(2γfop(t)+fpr(t)+fpq(t)),cqr′(t)=10(2γfqr(t)+foq(t)+fpq(t)),coq′(t)=(2γfoq(t)+fqr(t))+50,cpr′(t)=(2γfpr(t)+fop(t))+50,cpq′(t)=(2γfpq(t)+fop(t)+fqr(t))+10.
The cost on the paths is as follows:
(23)C1′(t)=11(2γ+1)f1(t)+(20γ+11)f3(t)+50,C2′(t)=11(2γ+1)f2(t)+(20γ+11)f3(t)+50,C31(t)=(20γ+11)(f1(t)+f2(t))+2(21γ+11)f3(t)+10.Then the variational inequality of the five-link dynamic traffic network overt∈[0,T] under DSO is given as follows:
(24)∫0T(11(2γ+1)f1*(t)+(20γ+11)f3*(t)+50)×(f1(t)-f1*(t))+(11(2γ+1)f2*(t)+(20γ+11)f3*(t)+50)×(f2(t)-f2*(t))+((20γ+11)(f1*(t)+f2*(t))+2(21γ+11)f3*(t)+10(f1*(t)+f2*(t)))×(f3(t)-f3*(t))dt≥0.
Because of formula (17), the equation can be given as follows:
(25)∫0T((26γ+11)f1*(t)-11(2γ+1)t+40)×(f1(t)+f2(t)-2f1*(t))dt≥0.
Let f3*(t)=0; at this time, f1*(t)=f2*(t)=t/2 and (26γ+11)(t/2)-11(2γ+1)t+40≥0; we have t≤80/(18γ+11); when t∈[0,80/(18γ+11)], the adding link makes sense under DSO.In the following, we give the trend of the upper bound under which the adding link works under DSO as the parameterγ changes in Figure 5 and find that the bound becomes smaller as γ increases, which explains that the less the influence of the other links is, the less the possibility that the adding link works under DSO, which warns us of improving the influence between the links appropriately if we want to make the adding link work under DSO.Figure 5
The bound above which an adding link cannot make the total costs increase under DSO.


#### 3.1.5. Relationship between the Total Cost under DUE and DSO

There is much research about the relationship of the total costs under different assignments, in which [22] we know that the solution under DUE and that under DSO are close under the free flow state, and the difference between both assignments is great when the traffic is congested in the kind of networks. In this section, we discuss the situation of the dynamic network when the link cost is related to the flow of the link and the flow of other links. Define TDUE-TDSO as the distance of the total costs between DUE and DSO. In this paper, we capture the gap of the total costs between the two assignments using the distance of the total costs between DUE and DSO. In Figure 6, we give the trend of the gap when γ is 1, 3, and 5, respectively and find that the gap increases with the time being over and demand accumulating; in addition, the gap increases with γ increasing in the area of the great demand. It shows, with γ increasing, that the influence of other links decreases; that is, it is reverse with the idea of DSO ignoring the influence of other links; thus the gap increases.Figure 6
Trend ofTDUE-TDSO with t changing when the values of γ are different.


### 3.2. Robustness of the Dynamic Network

The network robustness has been widely investigated in many literatures, in which the importance identification of the network components is an important branch [23, 24]. In this section, we use the relative total cost index to determine the importance of the components of the dynamic network.The total cost on the linka is denoted as follows:
(26)c^ij(t)=cij(t)fij(t),
where c^ij(t) is the total cost on the link ij at time t, cij(t) is the unit cost on the link ij at the time t, and fij(t) is the flow on the link ij at time t. Hence, the total cost TC(t) on a network at time t is given by
(27)TC(t)=∑ij∈Lc^oj(t),
where L is the set of the links. The link flows f(t) satisfy the nonnegativity and conservation of the flow conditions. Then we have the relative total cost index as follows:
(28)Γl(t)=TCG-l(t)-TC(t)TC(t),
where Γl(t) denotes the important indicator for the link l under the DUE at time t and TCG-l(t) denotes the total cost generated under DUE when the link l is removed from the network at time t. Similarly, the importance indicator for the node M is denoted as follows:
(29)ΓM(t)=TCG-M(t)-TC(t)TC(t),
where ΓM(t) is the importance indicator for the node M under DUE at time t, TCG-M(t) is the total cost when the node M is removed from the network under DUE at time t.In the following, we use the network in Figure2 and assume γ=2 to investigate the importance of components of the dynamic network. During the process of the calculation, it can be found that the different traffic demands correspond to different traffic assignments with different importance components; the range of t is divided into four different ranges as follows.Demand Range I:(30)t∈[0,1619).We know that, in this demand range, only the third path is used at the equilibrium; hence, we have the equilibrium path flow patternf(t)1=f2(t)=0, f3(t)=t, and the total cost is TC(t)=64t2+10t.Demand Range II:(31)t∈[1619,4033).We know that, in this demand range, only the third path is used at the equilibrium, hence; we have the equilibrium path flow patternf(t)1=f2(t)=0, f3(t)=t, and the total cost is TC(t)=64t2+10t.Demand Range III:(32)t∈[4033,8029).We know that, in this range of the demand, all three paths are used at the equilibrium; we now have thatf1(t)=f2(t)=(33t-40)/37, f3(t)=(80-29t)/37, and the total cost is TC(t)=(190t2+2640t)/37.Demand Range IV:(33)t∈[8029,+∞).We know that only the first two paths are used at the equilibrium and the Braess’ paradox vanishes. Hence, we have the equilibrium path flow patternf1(t)=f2(t)=t/2, f3(t)=0, and the total cost is TC(t)=(33t2/2)+50t.The ranking of the component is the sequence of its important value. Then the important values and rankings of different components in different ranges are given in Tables1, 2, 3, and 4.Table 1
Important values of links in different ranges.
I
II
III
IV
o
p
40
-
31
t
64
t
+
10
40
-
31
t
64
t
+
10
1031
t
-
1160
190
t
+
3010
33
t
33
t
+
100
o
q
0
0
35937
t
-
43560
6650
t
+
105350
1147
t
-
160
1155
t
+
3500
p
r
0
0
35937
t
-
43560
6650
t
+
105350
1147
t
-
160
1155
t
+
3500
q
r
40
-
31
t
64
t
+
10
40
-
31
t
64
t
+
10
1031
t
-
1160
190
t
+
3010
33
t
33
t
+
100
p
q
5
(
18
-
19
t
)
4
(
32
t
+
5
)
5
(
18
-
19
t
)
4
(
32
t
+
5
)
841
t
-
2320
380
t
+
6020
0Table 2
Important rankings of links in different ranges.
I
II
III
IV
o
p
1
1
1
1
o
q
3
2
2
2
p
r
3
2
2
2
q
r
1
1
1
1
p
q
2
3
3
3Table 3
Important values of nodes in different ranges.
I
II
III
IV
o
+
∞
+
∞
+
∞
+
∞
p
40
-
31
t
64
t
+
10
40
-
31
t
64
t
+
10
1031
t
-
1160
190
t
+
3010
33
t
33
t
+
100
q
40
-
31
t
64
t
+
10
40
-
31
t
64
t
+
10
1031
t
-
1160
190
t
+
3010
33
t
33
t
+
100
r
+
∞
+
∞
+
∞
+
∞Table 4
Important rankings of nodes in different ranges.
I
II
III
IV
o
1
1
1
1
p
2
2
2
2
q
2
2
2
2
r
1
1
1
1From Tables1–4, the important values and the rankings of the different components are different; at the same time, the important rankings of the component are different in different ranges of the time, which show the robustness of the network changes when different components collapse.Owing to considering the influence of other links and using different efficiency measures, we find that the important values of the corresponding nodes and links are different from the results of Nagurney and Qiang [25], but the important ranking of the corresponding components is the same as their results; there are two possible reasons as follows: (i) the purpose and essence of the different efficiency measures are consistent; (ii) in this work, we assume γ=2; that is, the influence of other links is secondary.In addition, from Sections3.1.3 and 3.2, we find that the importance of the adding link is small in the area that Braess’ paradox occurs and the adding link is not used, which shows that the robustness of the network is related to whether the paradox occurs. Based on the preceding study, we consider the influence of other links in this paper, which better provide the guidance of the traffic assignment.


## 3.1. The Analysis about Paradox

### 3.1.1. The Equilibrium Solution of the Four-Link Network under DUE

As we know, the paradox phenomenon exists in many networks with different topologies; Braess’ network has been investigated by a large number of researchers; it is representative because it can simplify the problem and clearly explain traffic phenomena. In this paper, we also consider Braess’ network with a single origino and a single destination r in this paper. Figure 1 depicts the network before the addition of the new link pq. Let the total demand for the travel from origin o to destination r be dw(t) and dw(t)=t; further, assume that the link cost is a function of the flow not only on this link but also on other links. Because the influence of the adjacent links is dominant, we assume that the other links are only limited to the adjacent links on the same path in this work. At the same time, assume that the problem is symmetric; further, the travel time is link-flow dependent and it increases rapidly as a function of the flow on the link.Figure 1
The four-link network.Specifically, the link cost functions of the four-link network in Figure1 are
(8)cop(t)=10(γfop(t)+fpr(t)),cqr(t)=10(γfqr(t)+foq(t)),coq(t)=(γfoq(t)+fqr(t))+50,cpr(t)=(γfpr(t)+fop(t))+50,
where cij(t) is the travel cost on link ij at time t, fij(t) is the flow on link ij at time t, γ is the scaling parameter which differentiates the influence between the given link only and others, generally, γ≥1. In the four-link network, there are two paths from the origin o to the destination r and the costs along the paths are given as follows:
(9)C1(t)=cop(t)+cpr(t)=11(γ+1)f1(t)+50,C2(t)=coq(t)+cqr(t)=11(γ+1)f2(t)+50,
where Ck(t) is the travel cost from o to r along path k at time t; in addition,
(10)f1(t)=fop(t)=fpr(t),f2(t)=foq(t)=fqr(t),
where fk(t) is the flow from o to r along path k at time t, the total demand satisfies the following conservation of the flow: dw(t)=f1(t)+f2(t). According to the definition of the UE, it is easy to get
(11)f1*(t)=f2*(t)=t2,C1(t)=C2(t)=11(γ+1)t2+50,
where fk*(t) is the equilibrium flow from o to r along path k at time t. Hence, the total system travel time under DUE before the addition of the new link is given as follows:
(12)C4(t)=11(γ+1)t22+50t,
where C4(t) is the total system travel cost under DUE for the four-link network.


### 3.1.2. The Equilibrium Solution of the Five-Link Network under DUE

After adding the linkpq, there appears a new path opqr from o to r in Figure 2.Figure 2
The five-link network.The link cost functions are given as follows:(13)cop(t)=10(γfop(t)+fpr(t)+fpq(t)),cqr(t)=10(γfqr(t)+foq(t)+fpq(t)),coq(t)=(γfoq(t)+fqr(t))+50,cpr(t)=(γfpr(t)+fop(t))+50,cpq(t)=(γfpq(t)+fop(t)+fqr(t))+10.
The traffic flow on each link is as follows:
(14)fop(t)=f1(t)+f3(t),fpr(t)=f1(t),foq(t)=f2(t),fqr(t)=f2(t)+f3(t),fpq(t)=f3(t).
The costs on the paths are
(15)C1(t)=11(γ+1)f1(t)+(10γ+11)f3(t)+50,C2(t)=11(γ+1)f2(t)+(10γ+11)f3(t)+50,C3(t)=(10γ+1)(f1(t)+f2(t))+(21γ+22)f3(t)+10.
The total demand satisfies the conservation of the flow as follows: dw(t)=f1(t)+f2(t)+f3(t).The variational inequality of the five-link dynamic traffic network overt∈[0,T] is given as follows:
(16)∫0T(11(γ+1)f1*(t)+(10γ+11)f3*(t)+50)×(f1(t)-f1*(t))+(11(γ+1)f2*(t)+(10γ+11)f3*(t)+50)×(f2(t)-f2*(t))+((10γ+1)(f1*(t)+f2*(t))+(21γ+22)f3*(t)+10(10γ+1)(f1*(t)+f2*(t)))(f3(t)-f3*(t))dt≥0.
Because
(17)dw(t)=f1(t)+f2(t)+f3(t),dw(t)=f1*(t)+f2*(t)+f3*(t),f1*(t)=f2*(t),
we have
(18)∫0T((13γ+11)f1*(t)-11(γ+1)t+40)×(f1(t)+f2(t)-2f1*(t))dt≥0;
if f1*(t)=0, and we have -11(γ+1)t+40≥0, then t≤40/11(γ+1); if f3*(t)=0, and at this time, f1*(t)=t/2, then t>80/(9γ+11); when t∈(40/11(γ+1),80/(9γ+11)],
(19)f1*(t)=f2*(t)=11(γ+1)t-4013γ+11,f3*(t)=-(9γ+11)t+8013γ+11.Assumeγ=2; the equilibrium flow of the five-link network is pictured in Figure 3, in ranges I and II [0,33/40], only the new path is used; in range III (33/40,80/29), all three are used; in range IV [80/29,+∞), only the first two paths are used; that is, the third path is never used when t>80/29.Figure 3
The equilibrium flow of the dynamic network.Corresponding to different ranges, the total travel cost of five-link network is given as follows:(20)C5(t)={(21γ+22)t2+10t,ift≤4011(γ+1),t[(31γ2+33γ)t+40(9γ+11)13γ+11+50(31γ2+33γ)t+40(9γ+11)13γ+11],if4011(γ+1)if<t<809γ+11,11(γ+1)t22+50t,ift≥809γ+11,
where C5(t) is the total system travel cost under DUE for the five-link network.


### 3.1.3. The Paradox of Dynamic Traffic Networks

LettingC5(t)>C4(t), we get t∈(80/(31γ+33),80/(9γ+11)); letting γ=2, the paradox occurs in ranges II and III in Figure 3.In order to capture the trend of the paradox when we take different values ofγ, we give the definition of the average difference of two functions F1,F2 in range [a,b]((a,b][a,b),(a,b)), a>b as follows:
(21)D(F1,F2)=|F1-F2|b-a.
We assume that the severity of the paradox is proposal to the average difference and use of the average difference of C4,C5 in range (80/(31γ+33),80/(9γ+11)) to represent the severity of the paradox.In Figure4, we discuss the situations when γ=1,2,5, respectively, and find that the areas where the paradox occurs are different when the values of γ are different; thus we may take some measures to control the influence between the links as time and traffic demand change in order to avoid or decrease the occurrence of the paradox; in addition, in most range, the greater γ is, the smaller the range of the traffic demand in which the paradox occurs is; that is, the severity and the range in which the paradox occurs increase with the influence of other links decreasing, which reminds us to let down the influence between links as much as possible if we wish to decrease the occurrence of the paradox.Figure 4
The severity that the paradox occurs whenγ is different.


### 3.1.4. The Effect of the Adding Link under DSO

As known, when the given link cost is a function of the flow on the given link only, adding a new link did not reduce the total system travel time even under SO [18]. When the link cost does not only depend on the flow on the given link only, we discuss whether the phenomenon occurs or not in the following. As we know, DSO is obtained by charging users the marginal cost of traveling (see formula (6)); for the link cost in this work, the corresponding path marginal cost equations are given as follows:
(22)cop′(t)=10(2γfop(t)+fpr(t)+fpq(t)),cqr′(t)=10(2γfqr(t)+foq(t)+fpq(t)),coq′(t)=(2γfoq(t)+fqr(t))+50,cpr′(t)=(2γfpr(t)+fop(t))+50,cpq′(t)=(2γfpq(t)+fop(t)+fqr(t))+10.
The cost on the paths is as follows:
(23)C1′(t)=11(2γ+1)f1(t)+(20γ+11)f3(t)+50,C2′(t)=11(2γ+1)f2(t)+(20γ+11)f3(t)+50,C31(t)=(20γ+11)(f1(t)+f2(t))+2(21γ+11)f3(t)+10.Then the variational inequality of the five-link dynamic traffic network overt∈[0,T] under DSO is given as follows:
(24)∫0T(11(2γ+1)f1*(t)+(20γ+11)f3*(t)+50)×(f1(t)-f1*(t))+(11(2γ+1)f2*(t)+(20γ+11)f3*(t)+50)×(f2(t)-f2*(t))+((20γ+11)(f1*(t)+f2*(t))+2(21γ+11)f3*(t)+10(f1*(t)+f2*(t)))×(f3(t)-f3*(t))dt≥0.
Because of formula (17), the equation can be given as follows:
(25)∫0T((26γ+11)f1*(t)-11(2γ+1)t+40)×(f1(t)+f2(t)-2f1*(t))dt≥0.
Let f3*(t)=0; at this time, f1*(t)=f2*(t)=t/2 and (26γ+11)(t/2)-11(2γ+1)t+40≥0; we have t≤80/(18γ+11); when t∈[0,80/(18γ+11)], the adding link makes sense under DSO.In the following, we give the trend of the upper bound under which the adding link works under DSO as the parameterγ changes in Figure 5 and find that the bound becomes smaller as γ increases, which explains that the less the influence of the other links is, the less the possibility that the adding link works under DSO, which warns us of improving the influence between the links appropriately if we want to make the adding link work under DSO.Figure 5
The bound above which an adding link cannot make the total costs increase under DSO.


### 3.1.5. Relationship between the Total Cost under DUE and DSO

There is much research about the relationship of the total costs under different assignments, in which [22] we know that the solution under DUE and that under DSO are close under the free flow state, and the difference between both assignments is great when the traffic is congested in the kind of networks. In this section, we discuss the situation of the dynamic network when the link cost is related to the flow of the link and the flow of other links. Define TDUE-TDSO as the distance of the total costs between DUE and DSO. In this paper, we capture the gap of the total costs between the two assignments using the distance of the total costs between DUE and DSO. In Figure 6, we give the trend of the gap when γ is 1, 3, and 5, respectively and find that the gap increases with the time being over and demand accumulating; in addition, the gap increases with γ increasing in the area of the great demand. It shows, with γ increasing, that the influence of other links decreases; that is, it is reverse with the idea of DSO ignoring the influence of other links; thus the gap increases.Figure 6
Trend ofTDUE-TDSO with t changing when the values of γ are different.


## 3.1.1. The Equilibrium Solution of the Four-Link Network under DUE

As we know, the paradox phenomenon exists in many networks with different topologies; Braess’ network has been investigated by a large number of researchers; it is representative because it can simplify the problem and clearly explain traffic phenomena. In this paper, we also consider Braess’ network with a single origino and a single destination r in this paper. Figure 1 depicts the network before the addition of the new link pq. Let the total demand for the travel from origin o to destination r be dw(t) and dw(t)=t; further, assume that the link cost is a function of the flow not only on this link but also on other links. Because the influence of the adjacent links is dominant, we assume that the other links are only limited to the adjacent links on the same path in this work. At the same time, assume that the problem is symmetric; further, the travel time is link-flow dependent and it increases rapidly as a function of the flow on the link.Figure 1
The four-link network.Specifically, the link cost functions of the four-link network in Figure1 are
(8)cop(t)=10(γfop(t)+fpr(t)),cqr(t)=10(γfqr(t)+foq(t)),coq(t)=(γfoq(t)+fqr(t))+50,cpr(t)=(γfpr(t)+fop(t))+50,
where cij(t) is the travel cost on link ij at time t, fij(t) is the flow on link ij at time t, γ is the scaling parameter which differentiates the influence between the given link only and others, generally, γ≥1. In the four-link network, there are two paths from the origin o to the destination r and the costs along the paths are given as follows:
(9)C1(t)=cop(t)+cpr(t)=11(γ+1)f1(t)+50,C2(t)=coq(t)+cqr(t)=11(γ+1)f2(t)+50,
where Ck(t) is the travel cost from o to r along path k at time t; in addition,
(10)f1(t)=fop(t)=fpr(t),f2(t)=foq(t)=fqr(t),
where fk(t) is the flow from o to r along path k at time t, the total demand satisfies the following conservation of the flow: dw(t)=f1(t)+f2(t). According to the definition of the UE, it is easy to get
(11)f1*(t)=f2*(t)=t2,C1(t)=C2(t)=11(γ+1)t2+50,
where fk*(t) is the equilibrium flow from o to r along path k at time t. Hence, the total system travel time under DUE before the addition of the new link is given as follows:
(12)C4(t)=11(γ+1)t22+50t,
where C4(t) is the total system travel cost under DUE for the four-link network.


## 3.1.2. The Equilibrium Solution of the Five-Link Network under DUE

After adding the linkpq, there appears a new path opqr from o to r in Figure 2.Figure 2
The five-link network.The link cost functions are given as follows:(13)cop(t)=10(γfop(t)+fpr(t)+fpq(t)),cqr(t)=10(γfqr(t)+foq(t)+fpq(t)),coq(t)=(γfoq(t)+fqr(t))+50,cpr(t)=(γfpr(t)+fop(t))+50,cpq(t)=(γfpq(t)+fop(t)+fqr(t))+10.
The traffic flow on each link is as follows:
(14)fop(t)=f1(t)+f3(t),fpr(t)=f1(t),foq(t)=f2(t),fqr(t)=f2(t)+f3(t),fpq(t)=f3(t).
The costs on the paths are
(15)C1(t)=11(γ+1)f1(t)+(10γ+11)f3(t)+50,C2(t)=11(γ+1)f2(t)+(10γ+11)f3(t)+50,C3(t)=(10γ+1)(f1(t)+f2(t))+(21γ+22)f3(t)+10.
The total demand satisfies the conservation of the flow as follows: dw(t)=f1(t)+f2(t)+f3(t).The variational inequality of the five-link dynamic traffic network overt∈[0,T] is given as follows:
(16)∫0T(11(γ+1)f1*(t)+(10γ+11)f3*(t)+50)×(f1(t)-f1*(t))+(11(γ+1)f2*(t)+(10γ+11)f3*(t)+50)×(f2(t)-f2*(t))+((10γ+1)(f1*(t)+f2*(t))+(21γ+22)f3*(t)+10(10γ+1)(f1*(t)+f2*(t)))(f3(t)-f3*(t))dt≥0.
Because
(17)dw(t)=f1(t)+f2(t)+f3(t),dw(t)=f1*(t)+f2*(t)+f3*(t),f1*(t)=f2*(t),
we have
(18)∫0T((13γ+11)f1*(t)-11(γ+1)t+40)×(f1(t)+f2(t)-2f1*(t))dt≥0;
if f1*(t)=0, and we have -11(γ+1)t+40≥0, then t≤40/11(γ+1); if f3*(t)=0, and at this time, f1*(t)=t/2, then t>80/(9γ+11); when t∈(40/11(γ+1),80/(9γ+11)],
(19)f1*(t)=f2*(t)=11(γ+1)t-4013γ+11,f3*(t)=-(9γ+11)t+8013γ+11.Assumeγ=2; the equilibrium flow of the five-link network is pictured in Figure 3, in ranges I and II [0,33/40], only the new path is used; in range III (33/40,80/29), all three are used; in range IV [80/29,+∞), only the first two paths are used; that is, the third path is never used when t>80/29.Figure 3
The equilibrium flow of the dynamic network.Corresponding to different ranges, the total travel cost of five-link network is given as follows:(20)C5(t)={(21γ+22)t2+10t,ift≤4011(γ+1),t[(31γ2+33γ)t+40(9γ+11)13γ+11+50(31γ2+33γ)t+40(9γ+11)13γ+11],if4011(γ+1)if<t<809γ+11,11(γ+1)t22+50t,ift≥809γ+11,
where C5(t) is the total system travel cost under DUE for the five-link network.


## 3.1.3. The Paradox of Dynamic Traffic Networks

LettingC5(t)>C4(t), we get t∈(80/(31γ+33),80/(9γ+11)); letting γ=2, the paradox occurs in ranges II and III in Figure 3.In order to capture the trend of the paradox when we take different values ofγ, we give the definition of the average difference of two functions F1,F2 in range [a,b]((a,b][a,b),(a,b)), a>b as follows:
(21)D(F1,F2)=|F1-F2|b-a.
We assume that the severity of the paradox is proposal to the average difference and use of the average difference of C4,C5 in range (80/(31γ+33),80/(9γ+11)) to represent the severity of the paradox.In Figure4, we discuss the situations when γ=1,2,5, respectively, and find that the areas where the paradox occurs are different when the values of γ are different; thus we may take some measures to control the influence between the links as time and traffic demand change in order to avoid or decrease the occurrence of the paradox; in addition, in most range, the greater γ is, the smaller the range of the traffic demand in which the paradox occurs is; that is, the severity and the range in which the paradox occurs increase with the influence of other links decreasing, which reminds us to let down the influence between links as much as possible if we wish to decrease the occurrence of the paradox.Figure 4
The severity that the paradox occurs whenγ is different.


## 3.1.4. The Effect of the Adding Link under DSO

As known, when the given link cost is a function of the flow on the given link only, adding a new link did not reduce the total system travel time even under SO [18]. When the link cost does not only depend on the flow on the given link only, we discuss whether the phenomenon occurs or not in the following. As we know, DSO is obtained by charging users the marginal cost of traveling (see formula (6)); for the link cost in this work, the corresponding path marginal cost equations are given as follows:
(22)cop′(t)=10(2γfop(t)+fpr(t)+fpq(t)),cqr′(t)=10(2γfqr(t)+foq(t)+fpq(t)),coq′(t)=(2γfoq(t)+fqr(t))+50,cpr′(t)=(2γfpr(t)+fop(t))+50,cpq′(t)=(2γfpq(t)+fop(t)+fqr(t))+10.
The cost on the paths is as follows:
(23)C1′(t)=11(2γ+1)f1(t)+(20γ+11)f3(t)+50,C2′(t)=11(2γ+1)f2(t)+(20γ+11)f3(t)+50,C31(t)=(20γ+11)(f1(t)+f2(t))+2(21γ+11)f3(t)+10.Then the variational inequality of the five-link dynamic traffic network overt∈[0,T] under DSO is given as follows:
(24)∫0T(11(2γ+1)f1*(t)+(20γ+11)f3*(t)+50)×(f1(t)-f1*(t))+(11(2γ+1)f2*(t)+(20γ+11)f3*(t)+50)×(f2(t)-f2*(t))+((20γ+11)(f1*(t)+f2*(t))+2(21γ+11)f3*(t)+10(f1*(t)+f2*(t)))×(f3(t)-f3*(t))dt≥0.
Because of formula (17), the equation can be given as follows:
(25)∫0T((26γ+11)f1*(t)-11(2γ+1)t+40)×(f1(t)+f2(t)-2f1*(t))dt≥0.
Let f3*(t)=0; at this time, f1*(t)=f2*(t)=t/2 and (26γ+11)(t/2)-11(2γ+1)t+40≥0; we have t≤80/(18γ+11); when t∈[0,80/(18γ+11)], the adding link makes sense under DSO.In the following, we give the trend of the upper bound under which the adding link works under DSO as the parameterγ changes in Figure 5 and find that the bound becomes smaller as γ increases, which explains that the less the influence of the other links is, the less the possibility that the adding link works under DSO, which warns us of improving the influence between the links appropriately if we want to make the adding link work under DSO.Figure 5
The bound above which an adding link cannot make the total costs increase under DSO.


## 3.1.5. Relationship between the Total Cost under DUE and DSO

There is much research about the relationship of the total costs under different assignments, in which [22] we know that the solution under DUE and that under DSO are close under the free flow state, and the difference between both assignments is great when the traffic is congested in the kind of networks. In this section, we discuss the situation of the dynamic network when the link cost is related to the flow of the link and the flow of other links. Define TDUE-TDSO as the distance of the total costs between DUE and DSO. In this paper, we capture the gap of the total costs between the two assignments using the distance of the total costs between DUE and DSO. In Figure 6, we give the trend of the gap when γ is 1, 3, and 5, respectively and find that the gap increases with the time being over and demand accumulating; in addition, the gap increases with γ increasing in the area of the great demand. It shows, with γ increasing, that the influence of other links decreases; that is, it is reverse with the idea of DSO ignoring the influence of other links; thus the gap increases.Figure 6
Trend ofTDUE-TDSO with t changing when the values of γ are different.


## 3.2. Robustness of the Dynamic Network

The network robustness has been widely investigated in many literatures, in which the importance identification of the network components is an important branch [23, 24]. In this section, we use the relative total cost index to determine the importance of the components of the dynamic network.The total cost on the linka is denoted as follows:
(26)c^ij(t)=cij(t)fij(t),
where c^ij(t) is the total cost on the link ij at time t, cij(t) is the unit cost on the link ij at the time t, and fij(t) is the flow on the link ij at time t. Hence, the total cost TC(t) on a network at time t is given by
(27)TC(t)=∑ij∈Lc^oj(t),
where L is the set of the links. The link flows f(t) satisfy the nonnegativity and conservation of the flow conditions. Then we have the relative total cost index as follows:
(28)Γl(t)=TCG-l(t)-TC(t)TC(t),
where Γl(t) denotes the important indicator for the link l under the DUE at time t and TCG-l(t) denotes the total cost generated under DUE when the link l is removed from the network at time t. Similarly, the importance indicator for the node M is denoted as follows:
(29)ΓM(t)=TCG-M(t)-TC(t)TC(t),
where ΓM(t) is the importance indicator for the node M under DUE at time t, TCG-M(t) is the total cost when the node M is removed from the network under DUE at time t.In the following, we use the network in Figure2 and assume γ=2 to investigate the importance of components of the dynamic network. During the process of the calculation, it can be found that the different traffic demands correspond to different traffic assignments with different importance components; the range of t is divided into four different ranges as follows.Demand Range I:(30)t∈[0,1619).We know that, in this demand range, only the third path is used at the equilibrium; hence, we have the equilibrium path flow patternf(t)1=f2(t)=0, f3(t)=t, and the total cost is TC(t)=64t2+10t.Demand Range II:(31)t∈[1619,4033).We know that, in this demand range, only the third path is used at the equilibrium, hence; we have the equilibrium path flow patternf(t)1=f2(t)=0, f3(t)=t, and the total cost is TC(t)=64t2+10t.Demand Range III:(32)t∈[4033,8029).We know that, in this range of the demand, all three paths are used at the equilibrium; we now have thatf1(t)=f2(t)=(33t-40)/37, f3(t)=(80-29t)/37, and the total cost is TC(t)=(190t2+2640t)/37.Demand Range IV:(33)t∈[8029,+∞).We know that only the first two paths are used at the equilibrium and the Braess’ paradox vanishes. Hence, we have the equilibrium path flow patternf1(t)=f2(t)=t/2, f3(t)=0, and the total cost is TC(t)=(33t2/2)+50t.The ranking of the component is the sequence of its important value. Then the important values and rankings of different components in different ranges are given in Tables1, 2, 3, and 4.Table 1
Important values of links in different ranges.
I
II
III
IV
o
p
40
-
31
t
64
t
+
10
40
-
31
t
64
t
+
10
1031
t
-
1160
190
t
+
3010
33
t
33
t
+
100
o
q
0
0
35937
t
-
43560
6650
t
+
105350
1147
t
-
160
1155
t
+
3500
p
r
0
0
35937
t
-
43560
6650
t
+
105350
1147
t
-
160
1155
t
+
3500
q
r
40
-
31
t
64
t
+
10
40
-
31
t
64
t
+
10
1031
t
-
1160
190
t
+
3010
33
t
33
t
+
100
p
q
5
(
18
-
19
t
)
4
(
32
t
+
5
)
5
(
18
-
19
t
)
4
(
32
t
+
5
)
841
t
-
2320
380
t
+
6020
0Table 2
Important rankings of links in different ranges.
I
II
III
IV
o
p
1
1
1
1
o
q
3
2
2
2
p
r
3
2
2
2
q
r
1
1
1
1
p
q
2
3
3
3Table 3
Important values of nodes in different ranges.
I
II
III
IV
o
+
∞
+
∞
+
∞
+
∞
p
40
-
31
t
64
t
+
10
40
-
31
t
64
t
+
10
1031
t
-
1160
190
t
+
3010
33
t
33
t
+
100
q
40
-
31
t
64
t
+
10
40
-
31
t
64
t
+
10
1031
t
-
1160
190
t
+
3010
33
t
33
t
+
100
r
+
∞
+
∞
+
∞
+
∞Table 4
Important rankings of nodes in different ranges.
I
II
III
IV
o
1
1
1
1
p
2
2
2
2
q
2
2
2
2
r
1
1
1
1From Tables1–4, the important values and the rankings of the different components are different; at the same time, the important rankings of the component are different in different ranges of the time, which show the robustness of the network changes when different components collapse.Owing to considering the influence of other links and using different efficiency measures, we find that the important values of the corresponding nodes and links are different from the results of Nagurney and Qiang [25], but the important ranking of the corresponding components is the same as their results; there are two possible reasons as follows: (i) the purpose and essence of the different efficiency measures are consistent; (ii) in this work, we assume γ=2; that is, the influence of other links is secondary.In addition, from Sections3.1.3 and 3.2, we find that the importance of the adding link is small in the area that Braess’ paradox occurs and the adding link is not used, which shows that the robustness of the network is related to whether the paradox occurs. Based on the preceding study, we consider the influence of other links in this paper, which better provide the guidance of the traffic assignment.


## 4. Conclusion

In this work, we investigate the paradox phenomenon and the robustness of the dynamic traffic network, in which the cost influenced by other link flows is considered. The four-link network and the five-link network are used in the analysis, which reveal that the paradox occurs only in certain range. The difference of the total costs between DUE and DSO changes as the traffic demand changes. The important values and important rankings of network components are changing at different demand levels. The results show that whether the paradox occurs or not and the robustness are both affected by the traffic demand, and the robustness of the network is related to the occurrence of the paradox, which provides a theoretical basis to the traffic assignment. The more complex networks are closer to the reality and needed to be further investigated.



---

*Source: 796842-2013-12-09.xml*