The Classical Braess Paradox Problem Revisited: A Generalized Inverse Method on Non-Unique Path Flow Cases

Abstract

The classical Braess paradox problem refers to a user-equilibrium assignment model which all started with Braess’s (Unternehmensforschung 12; 258–268, 1968) demonstrated example network. Some variants of Braess paradox and related theories were subsequently developed to detect this paradoxical phenomenon on a general network. In this paper, the authors are devoted to the classical Braess paradox problem involving situations whenever considering new links to be added to a network. Historical literature told us that existing theories for this problem were limited to networks which admit unique path flow solution. A generalized inverse approach is suggested to solve this problem without the assumption of unique path flow solution in this study. The change of equilibrium cost after link additions is derived as a generalized inverse formulation of which solution possesses the non-uniqueness and flow conservation over all perturbed paths. Based on this generalized inverse formulation of the change of equilibrium cost, the authors show that there exists at least one of the O/D pairs, connected by new added routes, such that Braess paradox doesn’t (does) occur if the proposed test matrix is positive (negative) semi-definite. The derivations extend existing theories towards the situations when multiple routes are arbitrarily generated after link additions. These new theories deliver prior information to foresee Braess paradox taking place on a class of transportation networks which is more general than before and never reached by existing studies on the indicated classical Braess paradox problem.

1 Introduction

Braess (1968), or the English version of the original German paper translated by Braess et al. (2005), presented two principles of traffic assignment currently known as system optimal and user equilibrium which are similar but independent to the paper of Wardrop (1952), as mentioned in Nagurney and Boyce (2005). In this well-known paper, Braess described a paradoxical phenomenon, the so called “Braess paradox”: In expanding a road network to mitigate congestion by addition of a new route seems to make the situation worse. The paper of Braess paradox created significant concerns and variants of Braess paradox, such as Murchland (1970), Stewart (1980), Frank (1981) and Pas and Principio (1997). These efforts examined mathematical characterizations in the context of the example network presented by Braess in 1968. Meanwhile, several directions different from the original case of Braess paradox were also developed. For instances, Smith (1978) showed another example of paradox: a reduction in total travel cost by increasing the travel cost along the uncongested link. This result is of particular relevance to a town with a good outer ring road or bypass. Fisk (1979) presented some examples to contrast the belief that travel costs are sensitive to changes in input traffic. An example demonstrated that the total travel cost is mitigated when increasing the input flow of an origin–destination (O/D) pair. The travel cost of the associated O/D pair get worse; however, the effect on the travel costs of other O/D pairs are diversified (see also Steinberg and Zangwill 1983; Dafermos and Nagurney 1984a). Fisk (1979) also provided a case for a two-mode equilibrium network to show that a reduction in auto traffic may lead to an increase in transit cost. In summation, these existing studies suggest that in order to prevent traffic congestion from becoming worse unexpectedly, evaluations should be performed on networks before doing something as a matter of course even these findings are based on several specific example networks.

Steinberg and Zangwill (1983) derived necessary and sufficient conditions for Braess paradox to occur after the addition of a new route on a general transportation network where the link cost function is affine with respective to the link flow itself. The proposed formulation is a system of linear equations that preserves user equilibrium and flow conservations. However, they assumed that the derived linear equations could be solved by applying Cramer’s Rule. It is equivalent to assume that the linear system guarantees a unique solution (denoted as the assumption A1 hereafter). Steinberg and Stone (1988) considered a new paradox where an increase of the congestion effect along a route can result in decreasing volumes to zero on another path connecting the same O/D pair. In particular, the results were obtained by formulating the question as a parametric linear complementarity problem (PLCP) for a general transportation network with affine cost functions. The PLCP model can study the general conditions that lead to the paradox by supposing that there is a unique path flow solution, similar to assumption A1. Dafermos (1980) considered the asymmetric equilibrium problem on a general transportation network where the travel cost depends on the flow of every link in the network. Existence and uniqueness of an equilibrium link flow pattern was then provided with the assumption of strong monotonicity of link cost function. Following the theory mentioned above, Dafermos and Nagurney (1984a) extended the results found in Steinberg and Zangwill (1983) to networks with asymmetric link cost functions by deriving formulas to describe the change in travelers’ cost for all origin–destination (O/D) pairs induced by the addition of a new route. The results can be used to determine whether Braess paradox occurs only if assumption A1 is held.

In addition to the aforementioned studies, there are some methods generally called sensitivity analysis of traffic equilibrium (SATE) which approximates a new equilibrium solution due to a variety of concurrent perturbations in model parameters. If the SATE methods are applied to the classical Braess paradox problem whenever considering new links to be added to a network, one may assume that the new links were there all the time but their costs were so high that they were not used by any user (see Dafermos and Nagurney 1984b). Under this treatment, two facts about the new added paths in the equilibrium state of this assumed network can be observed further: 1) the flow is zero and 2) the cost is greater than the corresponding equilibrium cost. However, we know that those SATE methods (e.g., Tobin and Friesz 1988; Cho et al. 2000) calculate sensitivity information locally only for those paths with equilibrium cost and positive flow. Patriksson (2004) presented another SATE method to compute sensitivity information by directional derivative which deals with the additional case involving those paths with equilibrium cost and zero flow. Hence, local sensitivity of the new added paths will be declared void if these SATE methods are applied to this assumed network. The authors refer readers to Chung et al. (2014) for a detail clarification of the regularity conditions governing application of those SATE methods presented in Tobin and Friesz (1988) and re-derived in Cho et al. (2000).

Recently, there are various studies about Braess paradox, sensitivity analysis of traffic equilibrium, and their applications. Kameda (2009) addressed the degree of coincident cost improvement by adding connections to a general Braess network with nonlinear link cost functions can extend without bound. Three Braess paradoxes occurring in a status different from static user equilibrium are as the followings. Zhang and Zhang (2010) illustrated a new Braess paradox in a dynamic traffic assignment problem with simultaneous departure time/route competitions among individuals. Park (2011) developed a general model to detect the Braess paradox under stable dynamics (Nesterov and de Palma 2003). Di et al. (2014a) explored the occurrence of the Braess paradox in the setting of the boundedly rational user equilibrium (e.g., Mahmassani nad Chang 1987; Cho et al. 2004; Cho and Hwang 2005; Di et al. 2014b) which relaxes the perfect rational behavioral assumption from the Wardrop’s first principle of traffic assignment.

Connors and Watling (2014) evaluated the demand vulnerability of stochastic equilibrium networks based a combination of sensitivity analysis (Connors et al. 2007) and network aggregation. Lin et al. (2014) presented an assessment criterion that can be acquired by solving a bi-level programming problem with environmental constraints. In some cases, such as setting an environmental constraint in the middle link of Braess’s paradox network, it may occur that the local environmental constraint is beneficial to the total system cost. Similarly, the evaluation goals of sustainability can also be multiple objectives (Szeto et al. 2013).

To sum up, this paper focuses on the classical Braess paradox problem whenever considering new links to be added to a network. The underlying scenario for this problem assumes that: Given a network and its equilibrium flow, can one provide a method to foresee whether Braess paradox happens or not if new links are supposed to be added to a network. The target method should allow “what if” analyses in advance without having to re-solve the new equilibrium solution (Tobin and Friesz 1988). As presented previously, the SATE methods are infeasible to this problem while the other approaches are limited due to the assumption A1. Then, the main concern of this study is to follow the underlying research scenario and to provide a method that detects Braess’ paradox from the aimed network without the restrictive assumption A1. Generalized inverse (see Moore 1920; Penrose 1955; Graybill 1969) is a generalization of the inverse of a non-singular matrix to deal with linear systems of which solution is non-unique. The method is utilized in this study to provide a solution formula involving the non-uniqueness of path flow.

The next section gives a brief review of the existing results on the classical Braess paradox problem. The third section contains the proposed approach embedded with generalized inverse formulations without assumed unique path flow. Based on this formulation, a testing matrix is proposed to detect whether Braess paradox occurs. This theory is also extended to cases that multiple routes are generated after geometry change. Finally, numerical examples are prepared to demonstrate the effectiveness of the proposed method and followed by conclusions and remarks.

2 A Brief Review of the Essential Results on the Classical Braess Paradox Problem

We briefly present the main results of historical studies on the classical Braess paradox problem, particularly those in Steinberg and Zangwill (1983) and in Dafermos and Nagurney (1984a). The notation system adopted in the later is also utilized in this section. Consider a network N, composed of a set of links A, a set of paths P, and a set of O/D pairs W. Accordingly, the links, paths, and O/D pairs of a network N are denoted by a, p, and w respectively. The link cost function c, in vector form, is affine with respective to link flow vector f

$$ c=c(f)=L+Gf $$

(1)

where L is the fixed link cost and G is the Jacobian matrix G = [(∂c/∂f)]. Under the strong monotonicity assumption, it is equivalent to the statement that the Jacobian matrix G = [(∂c/∂f)] is positive definite at every feasible f. Then at user equilibrium, there is a unique link flow pattern f* that satisfies the incidence relations and flow conservations

$$ {f}^{*}=\varDelta h,\ T=\varLambda h $$

(2)

where h and T are the path flow vector and demands of O/D pairs respectively; and matrices Δ and Λ are the link-path incidence matrix and O/D pair-path incidence matrix respectively. The mentioned existing studies assumed situations in which (2) admits only unique path flow solutions, i.e.,

$$ rank\left[\frac{\varDelta }{\varLambda}\right]= number\ of\ paths. $$

(3)

If a network geometry change in the form of an addition of a new path r connecting the O/D pair w is considered, the change in equilibrium cost of O/D pair δU and the change in path flow δh can be formulated simultaneously as

$$ \left[\frac{\varDelta^{\prime }G\varDelta }{\varLambda}\left|\frac{\varLambda^{\prime }}{0}\right.\right]\left[\frac{\delta h}{-\delta U}\right]=\left[\frac{-\varDelta^{\prime }G{\varDelta}_r}{-e}\right]{h}_r, $$

(4)

where Δ′ and Λ′ are the transpose of Δ and Λ respectively; Δ _r , e and h _r are the link(not including new links)-path incidence matrix for path r, the O/D pair-path incidence matrix for path r and the flow of path r respectively. Under the assumption (3) and letting w denote the first O/D pair in the list, linear system (4) can be solved by utilizing Cramer’s rule as

$$ \delta {U}_w=\frac{det\left[\left.\frac{H}{\varLambda_1}\right|\frac{\varLambda_1^{\prime }}{0}\right]}{det\left[\frac{\varDelta^{\prime }G\varDelta }{\varLambda}\left|\frac{\varLambda^{\prime }}{0}\right.\right]}{h}_r, $$

(5)

where matrix Λ ₁ is given by removing the first row of matrix Λ; and matrices H and Y are

$$ H=\varDelta^{\prime }G\varDelta -\varDelta^{\prime }GY $$

(6)

and

$$ Y=\left[{\varDelta}_r\left|\cdots \left|{\varDelta}_r\left|0\right.\right.\right.\right] $$

(7)

respectively, where the number of vectors Δ _r appearing in (7) equals the number of paths connecting the O/D pair w, and the null matrix, 0. Under the assumed monotonicity condition, the rank condition (3), and path flow h _r positive, Dafermos and Nagurney (1984a) showed that for positive semi-definite matrix H, δU _w  ≤ 0, which means the paradox doesn’t exist. A corollary also claimed that if the added route r contains none of the original links of the network, then the result would be a decrease in travel cost for users of the O/D pair w. A formula similar to (5) and the case of multiple routes added can also be found in Steinberg and Zangwill (1983). However, their results all rely on the assumption of $det\left[\frac{\varDelta^{\prime }G\varDelta }{\varLambda}\left|\frac{\varLambda^{\prime }}{0}\right.\right]\ne 0$.

3 The Generalized Inverse Approach

The results of (4) and (5) are mainly based on the assumption of affine link cost functions and the unique path flow solution of (2) or equivalently the assumption of (3). However, the configuration of a transportation network usually encapsulates notorious non-uniqueness in nature when it is formulated as a linear matrix equation system, for instance, see (4). Hence, the generalized inverse approach is employed to solve the linear system (4) without the uniqueness assumption in this paper. The generalized inverse matrix is a generalization of the inverse of a non-singular matrix historically proposed to solve singular problems. It is used here for solving linear matrix Eq. (4), which describes traffic equilibrium and whether paradoxes turn up. The main definitions and theorems of the generalized inverse matrix are briefly introduced at the start of this section. Let A be an m × n matrix and I the identity matrix. If a matrix A ⁻ exists that satisfies the four conditions below, we call A ⁻ a generalized inverse of A. The notation, A ⁻, denotes the generalized inverse of matrix A in this paper hereafter.

Definition 3.1 (Penrose (1955) and Graybill (1969))

• (i) AA ⁻ is symmetric.

• (ii) A ⁻ A is symmetric.

• (iii) AA ⁻ A = A

• (iv) A ⁻ AA ⁻ = A ⁻

Theorem 3.1 gives the existence and uniqueness of a generalized matrix, see Graybill (1969). The computing formula of the generalized inverse is placed in Theorem 3.2. Theorem 3.2 with our proof discusses the row rank cases which meet our concerns.

Theorem 3.1

For each matrix A, there exists a unique matrix A ⁻ which satisfies the conditions of Definition 3.1.

Proof: The proof of Theorem 3.1 is referred to the proof of Theorem 6.2.4 in Graybill (1969).

Theorem 3.2

If A is an m × n matrix of rank m, then

$$ {A}^{-}=A^{\prime }{\left(AA\prime \right)}^{-1} $$

(8)

, and AA ⁻ = I.

Proof: To prove the theorem, we first prove Eq. (8) satisfying the four conditions of Definition 3.1. For condition (i), calculate (AA ⁻) ′ by replacing

A ⁻ with the formula of A ⁻ in (8). Because matrix A is a m × n matrix of rank m, AA′ is a nonsingular m × m matrix. Thus, we have

$$ \left(A{A}^{-}\right)^{\prime }=\left( AA^{\prime }{\left( AA\prime \right)}^{-1}\right)^{\prime }=\left({\left( AA\prime \right)}^{-1}\right)^{\prime } AA^{\prime }={\left( AA\prime \right)}^{-1}AA^{\prime }=AA^{\prime }{\left( AA\prime \right)}^{-1}=A{A}^{-}. $$

(9)

This result admits AA ⁻ is symmetric. For condition (ii), similar treatments are provided as

$$ \left({A}^{-}A\right)^{\prime }=\left(A^{\prime }{\left( AA\prime \right)}^{-1}A\right)^{\prime }=A^{\prime}\left(A^{\prime }{\left( AA\prime \right)}^{-1}\right)^{\prime }=A^{\prime}\left({\left( AA\prime \right)}^{-1}A\right)=A^{\prime }{\left( AA\prime \right)}^{-1}A={A}^{-}A. $$

(10)

Equation (10) is equivalent to saying A ⁻ A is symmetric. For condition (iii), calculate AA ⁻ A by replacing A ⁻ with the formula of A ⁻ in (8). Then we have

$$ A{A}^{-}A=A\left(A^{\prime }{\left( AA\prime \right)}^{-1}\right)A=AA^{\prime }{\left( AA\prime \right)}^{-1}A=A. $$

(11)

For condition (iv), calculate A ⁻ AA ⁻ by replacing A ⁻ with the formula of A ⁻ in (8). Then again, we have

$$ {A}^{-}A{A}^{-}=A^{\prime }{\left( AA\prime \right)}^{-1}AA^{\prime }{\left( AA\prime \right)}^{-1}=A^{\prime }{\left( AA\prime \right)}^{-1}={A}^{-} $$

(12)

Collecting the results from (9) to (12) conclude that A ⁻ = A′(AA′)^− 1 agrees with the definition of a generalized inverse.

Then, we prove AA ⁻ = I. Calculate AA ⁻ by replacing A ⁻ with the formula of A ⁻ in (8). We immediately have AA ⁻ = A(A ′ (AA′)^− 1) = AA ′ (AA′)^− 1 = I, due to AA ′ being a nonsingular m × m matrix. Now, the proof of Theorem 3.2 is complete.

The following theorem provides an answer for linear systems if non-unique solutions exist.

Theorem 3.3

Let the system of equations Ax = g have a solution, where A is an m × n matrix with rank m and g is an m × 1 vector. For each n × 1 vector k, the vector y ₀ is a solution, where

$$ {y}_0={A}^{-}g+\left(I-{A}^{-}A\right)k. $$

(13)

Additionally, each solution to the system can be written in the form of (13) for some n × 1 vector k.

Proof: First, for the sufficient condition: If Ay ₀ = g is given, then we have Ay ₀ = g + (A − A)k, where k is an arbitrary n × 1 vector. By utilizing the results of Theorem 3.2 and Definition 3.1, there exists a generalized inverse matrix A ⁻ such that Ay ₀ = AA ⁻ g + (A − AA ⁻ A)k, and therefore Ay ₀ = A(A ⁻ g + (I − A ⁻ A)k). This is equivalent to y ₀ = A ⁻ g + (I − A ⁻ A)k.

Secondly, for the necessary condition: Suppose Eq. (13) is presumed, then Ay ₀ = AA ⁻ g + A(I − A ⁻ A)k is obtained by multiplying on both sides of (13) by A. Together with Theorem 3.2 and Definition 3.1, that jointly imply A(I − A ⁻ A) = 0 and AA ⁻ g = g, we have Ay ₀ = g accordingly. The proof is finished entirely

Now, the material about the generalized inverse matrix is ready to solve a linear system that describes traffic equilibrium paradoxes on a network. First, we give a formula to solve the equilibrium solution directly according to the generalized inverse matrix. Given a set of link cost functions defined in (1), the equilibrium state can be formulated as

$$ \left\{\begin{array}{c}\hfill \varDelta^{\prime}\left(G\varDelta h+L\right)=\varLambda^{\prime }U\hfill \\ {}\hfill T=\varLambda h\hfill \end{array}\right. $$

(14a)

where U is the equilibrium cost vector of O/D pairs. The first equation in (14a) gives the condition that path cost is equal to the respective O/D pair cost if the equilibrium state is reached. The incidence relations presented in (2) are built implicitly on this equation, and the flow conservations presented in (2) are set in the second equation of (14a). Without loss of generality, we assume that Eq. (14a) is in reduced row rank form and rewrite it equivalently as (14b)

$$ \left[\frac{\varDelta^{\prime }G\varDelta \left|-\right.\varLambda^{\prime }}{\kern0.5em \varLambda \left|\kern0.5em 0\right.}\right]\left[\frac{h}{U}\right]=\left[\frac{-\varDelta^{\prime }L}{T}\right]. $$

(14b)

Applying the results of Theorem 3.3, the solution of (14b) is obtained as

$$ \left[\frac{h}{U}\right]={\left[\frac{\varDelta \prime G\varDelta \left|-\right.\varLambda \prime }{\ \varLambda \left|\kern0.5em 0\right.}\right]}^{-}\left[\frac{-\varDelta^{\prime }L}{T}\right]+\left(I-{\left[\frac{\varDelta \prime G\varDelta \left|-\right.\varLambda \prime }{\ \varLambda \left|\kern0.5em 0\right.}\right]}^{-}\left[\frac{\varDelta^{\prime }G\varDelta \left|-\right.\varLambda^{\prime }}{\ \varLambda \left|\kern0.5em 0\right.}\right]\right)k. $$

(15)

Equation (15) works without non-unique path flow assumption, and provides a formula to calculate non-unique solutions numerically. Due to the condition of row rank in (14b), (15) will provide multiple answers of path flow h. However, both the equilibrium cost of O/D pairs and link flow patterns are unique if a feasible solution can be found. It should be noted that path flows delivered by (15) are not guaranteed to be positive. The following program proposes an alternative to solving Eq. (14b) with non-negative path flows, if it is feasible. (Tobin and Friesz 1988)

$$ \begin{array}{c}\hfill Minimize{\displaystyle \sum_{p\in P}{h}_p}\ \hfill \\ {}\hfill s.\kern0.5em t.\kern0.5em \left[\frac{\varDelta^{\prime }G\varDelta \left|-\right.\varLambda^{\prime }}{\ \varLambda \left|\kern0.5em 0\right.}\right]\left[\frac{h}{U}\right]=\left[\frac{-\varDelta^{\prime }L}{T}\right]\hfill \\ {}\hfill h=\left({h}_1,\cdots, {h}_p,\cdots, {h}_{\left|P\right|}\right)\ge 0, and\ U\ge 0\hfill \end{array} $$

(16)

where h _p is the flow of path p, and P is the set of whole paths. Similarly, we replace Eq. (4) with generalized inverse formulation as

$$ \left[\frac{\delta h}{-\delta U}\right]={\left[\frac{\varDelta \prime G\varDelta }{\varLambda}\left|\frac{\varLambda \prime }{0}\right.\right]}^{-}\left[\frac{-\varDelta^{\prime }G{\varDelta}_r}{-e}\right]{h}_r+\left(\mathrm{I}-{\left[\frac{\varDelta \prime G\varDelta \left|-\right.\varLambda \prime }{\ \varLambda \left|\kern0.5em 0\right.}\right]}^{-}\left[\frac{\varDelta^{\prime }G\varDelta \left|-\varLambda^{\prime}\right.}{\ \varLambda \left|\kern0.5em 0\right.}\right]\right)k, $$

(17)

where k is an arbitrary real vector. Because of the uniqueness of equilibrium path cost, the computation of δU in (17) is expected to be independent of vector k. Then as ${\left[\frac{\varDelta \prime G\varDelta }{\varLambda}\left|\frac{\varLambda \prime }{0}\right.\right]}^{-}\left[\frac{-\varDelta^{\prime }G{\varDelta}_r}{-e}\right]$ is calculated, the sign of δU in (17) can be determined concurrently with an assumed positive h _r .It would be more helpful to seek conditions under which the sign of δU in (17) can be disclosed prior to a lengthy computation with ${\left[\frac{\varDelta \prime G\varDelta }{\varLambda}\left|\frac{\varLambda \prime }{0}\right.\right]}^{-}\left[\frac{-\varDelta^{\prime }G\;{\varDelta}_r}{-e}\right]$. Before doing so, we have realized that the analysis thus far goes not beyond adding only one new route to a network. However, it is highly possible that more than one path might be generated after placing additional links on a transportation network. We now proceed to search out circumstances of determining the sign of δU in (17) under the case of multiple new routes generated after some geometric changes of a network. Let us consider a set of new paths P _R generated after the addition of an arc set A _R and the number of paths of P _R is indicated as |P _R |. The path flow vector of the path set P _R is denoted as h _R and assumed positive. The set of O/D pairs for P _R is expressed as W _R and the number of O/D pairs of W _R is denoted as |W _R |. The set of new paths P _R can be partitioned into |W _R | disjoint sets denoted as ${D}_{w_R}$ for all w _R  ∈ W _R . The number of elements in each ${D}_{w_R}$ is expressed as $\left|{D}_{w_R}\right|$. Let Δ _R and e _R be the link-path incidence matrix (not including A _R ) and the O/D pair-path incidence matrix for P _R respectively. Then, the Eq. (4) is redeveloped as

$$ \left[\frac{\varDelta^{\prime }G\varDelta }{\varLambda}\left|\frac{\varLambda^{\prime }}{0}\right.\right]\left[\frac{\delta h}{-\delta U}\right]=\left[\frac{-\varDelta^{\prime }G{\varDelta}_R}{-{e}_R}\right]{h}_R. $$

(18)

The upper part of (18) after some algebraic manipulations is indicated as

$$ \varLambda^{\prime}\delta U=\varDelta^{\prime } G\varDelta \delta h+\varDelta^{\prime }G{\varDelta}_R{h}_R. $$

(19a)

The left-hand-side of (19a) represents the change of equilibrium cost, and the right-hand-side of (19a) decomposes the change of equilibrium cost into two terms. The first term shows the change of cost of the original paths due to the change of path flows after the addition of new links. The second term describes the change of cost of the original paths resulting from the new generated path flows . The lower part of (18) exhibits flow conservations as

$$ {e}_R{h}_R=-\varLambda \delta h. $$

(19b)

The solution of (19b) is non-unique and can be transferred to a reduced form with row rank |W _R |. Then, according to Theorem 3.3 again, the solution of h _R in (19b) can be presented as

$$ {h}_R=-{e}_R^{-}\varLambda \delta h+\left(I-{e}_R^{-}{e}_R\right){k}_R, $$

(19c)

where k _R is an arbitrary |P _R | ×1 real vector. If all nonzero entries in each row of e _R are placed at successive columns, as the example shown in Fig. 1, then the result of (I − e ⁻ _R e _R ) is a staircase matrix (Fourer 1984) such that all nonzero elements lie on |W _R | square diagonal blocks B _i , i = 1, 2, ⋯, |W _R |, as shown in Fig. 2. That means if |W _R | O/D pairs are additionally connected by a newly generated path set P _R then the number of diagonal blocks will also be |W _R |. The order of each diagonal block B _i will be $\left|{D}_{w_R}\right|$ if w _R is the ith O/D pair of the set W _R .

Fig. 1

An illustrating example of the O/D pair-path incidence matrix for P _R

Fig. 2

An illustrating example of a staircase matrix (I − e ⁻ _R e _R )

In particular, each row sum of B _i is zero.¹ Then, it is helpful to let (I − e ⁻ _R e _R )k _R zero in (19c) by just selecting a vector k _R of which elements are the same. Now, (19c) can be reduced to

$$ {h}_R=-{e}_R^{-}\varLambda \delta h $$

(19d)

without loss of generality. By (19d), and hence then (19c) is rewritten as

$$ \varLambda^{\prime}\delta U=\varDelta^{\prime } G\varDelta \delta h-\varDelta^{\prime }G{\varDelta}_R{e}_R^{-}\varLambda \delta h $$

(20)

It can be examined from (20) that each element in vector Δ ′ GΔδh − Δ ′ GΔ _R e ⁻ _R Λδh is equal to one corresponding element in vector Λ ′ δU. Furthermore, the elements in vector Δ ′ GΔδh − Δ ′ GΔ _R e ⁻ _R Λδh have a unique value if they belong to the same O/D pair. After further treatments of (20) and collecting terms together for each O/D pair we have

$$ \delta h^{\prime}\varLambda^{\prime}\delta U=\delta h^{\prime}\left[\varDelta^{\prime }G\varDelta -\varDelta^{\prime }G{\varDelta}_R{e}_R^{-}\varLambda \right]\delta h={\displaystyle {\sum}_{w\in W}\left(\delta {U}_w{\displaystyle {\sum}_{i\in w}\delta {h}_i}\right)} $$

(21)

If supposing that matrix M = Δ ′ GΔ − Δ ′ GΔ _R e ⁻ _R Λ is positive semi-definite, it follows that δh ′ Mδh = δh ′ [Δ ′ GΔ − Δ ′ GΔ _R e ⁻ _R Λ]δh ≥ 0. Applying this to (21), we have

$$ {\displaystyle {\sum}_{w\in W}\left(\delta {U}_w{\displaystyle {\sum}_{i\in w}\delta {h}_i}\right)\ge 0}. $$

(22)

Because the value of ∑ _i ∈ w δh _i is negative for O/D pairs belonging to W _R and zero for O/D pairs not belonging to W _R , it is impossible for δU _w  > 0, ∀ w ∈ W _R if assuming matrix M is positive semi-definite. It is sufficient to say that there exists at least one O/D pair w _NB  ∈ W _R such that $\delta {U}_{w_{NB}}<0\ \left( paradox\ doesn\mathit{\hbox{'}}t\ exist\right)$ to prevent breaking the positive semi-definiteness of matrix M. Finally, we conclude these results with the following theorem and corollaries.

Theorem 3. 4

Under the assumed strict monotone and affine cost function, and where each path flow is positive before and after the addition of routes, it follows that for matrix

$$ M=\varDelta^{\prime }G\varDelta -\varDelta^{\prime }G{\varDelta}_R{e}_R^{-}\varLambda $$

(23)

that is positive semi-definite, there exists at least one O/D pair w _NB  ∈ W _R such that $\delta {U}_{w_{NB}}<0.\kern0.5em \left( paradox\ doesn\mathit{\hbox{'}}t\ exist\right)$

Proof: The proof follows immediately based on the analysis just mentioned.

Corollary 3.1

With the same assumptions of Theorem 3.4, it follows that for matrix M = Δ ′ GΔ − Δ ′ GΔ _R e ⁻ _R Λ that is negative semi-definite, there exists at least one O/D pair w _B  ∈ W _R such that $\delta {U}_{w_B}>0.\kern0.5em \left( paradox\ does\ exist\right)$

Proof: If supposing that matrix M = Δ ′ GΔ − Δ ′ GΔ _R e ⁻ _R Λ is negative semi-definite, it follows that δh ′ Mδh = δh ′ [Δ ′ GΔ − Δ ′ GΔ _R e ⁻ _R Λ]δh ≤ 0. Applying this to (21) again, we have ∑ _w ∈ W (δU _w ∑ _i ∈ w δh _i ) ≤ 0. Because the value of ∑ _i ∈ w δh _i is negative for O/D pairs w ∈ W _R and zero for O/D pairs w∉W _R , it is impossible that δU _w  < 0, ∀ w ∈ W _R if assuming matrix M is negative semi-definite. It is equivalent to say that there exists at least one O/D pair w _B  ∈ W _R such that $\delta {U}_{w_B}>0$ to prevent breaking the negative semi-definiteness of matrix M.

Corollary 3.2

If the change of network geometry results in only one new route joining an O/D pair w _NB (w _B ), then $\delta {U}_{w_{NB}}<0\ \left(\delta {U}_{w_B}>0\right)$ provided that matrix M is positive (negative) semi-definite.

Proof: As the case for only one new route being produced, there would exist only one term in (21). Then, we have $\delta {U}_{w_{NB}}<0\kern0.5em \left(\delta {U}_{w_B}>0\right)$ immediately by following Theorem 3.4 (Corollary 3.1).

Corollary 3.3

If the change of network geometry results in only one new route joining an O/D pair w _NB , and the new route contains none of the original links of the network then $\delta {U}_{w_{NB}}<0$.

Proof: Since the new route includes none of the old links of the network, it reveals Δ _R to be a zero matrix in (23). Thus, we have the consequent facts that the testing matrix M reduces to Δ ′ GΔ which is positive semi-definite. Then $\delta {U}_{w_{NB}}<0$ for O/D pair w _NB immediate follows Corollary 3.2.

The results of Corollary 3.2 (the part for positive semi-definite testing matrix) and Corollary 3.3 are similar to Theorem 4.1 and Corollary 4.1 proposed by Dafermos and Nagurney (1984a) but with a different form of testing matrix which makes it successful in solving the classical Braess paradox problem involving non-unique path flow solutions. The proofs of the proposed corollaries are based on the main results of Theorem 3.4, which is an extension of existing theories towards networks where multiple routes are arbitrarily generated after link additions. Corollary 3.1 delivers essential information that provides an alarm to anticipate the paradox taking place. It agrees with suggestions, made by existing studies, that in order to prevent situations from becoming worse, evaluations should be performed on a network before policy-makings.

Consider the case of nonlinear cost function c(f), and let $\overline{f}$, $\overline{\overline{f}}$ be the equilibrium link flow before and after the addition of links. By applying the mean value theorem, for the cost function of link i, we have

$$ {c}_i\left(\overline{\overline{f}}\right)-{c}_i\left(\overline{f}\right)={\displaystyle {\sum}_{j\in A}\left[{\displaystyle {\int}_0^1\frac{\partial {c}_i(f)}{\partial {f}_j}\ dt}\right]\left(\overline{\overline{f_j}}-\overline{f_j}\right)} $$

(24)

where $\overline{f_j}$ is the jth element in $\overline{f}$ and

$$ f=\overline{f}+t\left(\overline{\overline{f}}-\overline{f}\right). $$

We re-express (24) in matrix and vector form as

$$ c\left(\overline{\overline{f}}\right) - c\left(\overline{f}\right)=G\left(\overline{\overline{f}}-\overline{f}\right) $$

(25)

where

$$ G={\displaystyle {\int}_0^1\frac{\partial c}{\partial f}\ dt} $$

and

$$ f=\overline{f}+t\left(\overline{\overline{f}}-\overline{f}\right). $$

The integral of matrix $\frac{\partial c}{\partial f}$ in (25) is to be understood component-wise. Equation (25) is the same as the nonlinear case suggested in Dafermos and Nagurney (1984a). The matrix G is now dependent on the change of flows such that the linearity of (4) disappears. In contrast to the case of affine cost function, the matrix G is no longer known in advance. However, (19a) can still be re-written as

$$ \begin{array}{l}\varLambda^{\prime}\delta U=\varDelta^{\prime}\left(c\left(\overline{\overline{f}}\right) - c\left(\overline{f}\right)\right)=\varDelta^{\prime }G\left(\overline{\overline{f}}-\overline{f}\right)\hfill \\ {}\kern3.5em =\varDelta^{\prime }G\left(\varDelta \delta h+{\varDelta}_R{h}_R\right)=\varDelta^{\prime } G\varDelta \delta h+\varDelta^{\prime }G{\varDelta}_R{h}_R.\hfill \end{array} $$

And, the re-derivations of Theorem 3.4 and Corollaries 3.1, 3.2, and 3.3 under this nonlinear case can still be applied immediately. These results can be interpreted as a new version of qualitative analysis of traffic equilibria sensitivity.

4 Numerical Examples

In this section, two numerical examples are presented to demonstrate the effectiveness of the proposed methods. Consider the first example network illustrated in Fig. 3. It consists of four links {L₁, L₂, L₃, L₄} and three O/D pairs {(O₁-D), (O₂-D), (O₃-D)} with demands 6, 1, 1, respectively. The O/D pair (O₁-D) is connected by two paths {P1 = (L₁,L₄),P2 = (L₃,L₂)}, and the O/D pair (O₂-D) by path P3 = (L₄), and the O/D pair (O₃-D) by path P4 = (L₂).

Fig. 3

The first example network before adding link 5

The four link cost functions are c ₁(f ₁) = 50 + f ₁, c ₂(f ₂) = 50 + f ₂, c ₃(f ₃) = 10f ₃, and c ₄(f ₄) = 10f ₄ respectively. Before adding link L₅ from node O₃ to O₂, the equilibrium solution can be solved with Eq. (15). After some treatments of matrix manipulations, we have

$$ \left[\frac{h}{U}\right]=\left[\begin{array}{ccccccc}\hfill 0.045\hfill & \hfill -0.045\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 0.5\hfill & \hfill -0.454\hfill & \hfill 0.045\hfill \\ {}\hfill -0.045\hfill & \hfill 0.045\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 0.5\hfill & \hfill 0.454\hfill & \hfill -0.045\hfill \\ {}\hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 1\hfill & \hfill 0\hfill \\ {}\hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 1\hfill \\ {}\hfill -.05\hfill & \hfill -.05\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 5.5\hfill & \hfill 5\hfill & \hfill 0.5\hfill \\ {}\hfill 0.454\hfill & \hfill -0.454\hfill & \hfill -1\hfill & \hfill 0\hfill & \hfill 5\hfill & \hfill 5.454\hfill & \hfill 0.454\hfill \\ {}\hfill 0.045\hfill & \hfill 0.045\hfill & \hfill 0\hfill & \hfill -1\hfill & \hfill 0.5\hfill & \hfill 0.454\hfill & \hfill 0.954\hfill \end{array}\right]\left[\begin{array}{c}\hfill -50\hfill \\ {}\hfill -50\hfill \\ {}\hfill 0\hfill \\ {}\hfill -50\hfill \\ {}\hfill 6\hfill \\ {}\hfill 1\hfill \\ {}\hfill 1\hfill \end{array}\right]+\left(I-I\right)k=\left[\begin{array}{c}\hfill 2.5909\hfill \\ {}\hfill 3.4909\hfill \\ {}\hfill 1\hfill \\ {}\hfill 1\hfill \\ {}\hfill 88.5\hfill \\ {}\hfill 35.909\hfill \\ {}\hfill 54.409\hfill \end{array}\right]. $$

(26)

The equilibrium path flow is unique and can be solved easily. If link 5 (L₅) is added into the network shown as Fig. 4, and the cost function of L₅ is c ₅(f ₅) = 10 + f ₅. Two paths are generated: P5 = (L₃,L₅,L₄) connecting the O/D pair (O₁-D) and P6 = (L₅,L₄) the O/D pair (O₃-D).

Fig. 4

The first example network after adding link 5

By utilizing Eq. (15) again, the equilibrium solution after the network expanding from building L₅ is presented as

$$ \begin{array}{l}\left[\frac{h}{U}\right]=\left[\begin{array}{cccccccc}\hfill 0.08\hfill & \hfill -0.08\hfill & \hfill 0\hfill & \hfill 0.08\hfill & \hfill -0.08\hfill & \hfill 0.85\hfill & \hfill -0.07\hfill & \hfill 0.01\hfill \\ {}\hfill -0.02\hfill & \hfill 0.02\hfill & \hfill 0\hfill & \hfill 0.02\hfill & \hfill -0.02\hfill & \hfill 0.46\hfill & \hfill 0.44\hfill & \hfill 0.21\hfill \\ {}\hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 1\hfill & \hfill 0\hfill \\ {}\hfill 0.02\hfill & \hfill -0.02\hfill & \hfill 0\hfill & \hfill 0.06\hfill & \hfill -0.06\hfill & \hfill 0.38\hfill & \hfill 0.4\hfill & \hfill 0.71\hfill \\ {}\hfill -0.06\hfill & \hfill 0.06\hfill & \hfill 0\hfill & \hfill -0.1\hfill & \hfill 0.1\hfill & \hfill -0.31\hfill & \hfill -0.37\hfill & \hfill -0.21\hfill \\ {}\hfill -0.02\hfill & \hfill 0.02\hfill & \hfill 0\hfill & \hfill -0.06\hfill & \hfill 0.06\hfill & \hfill -0.38\hfill & \hfill -0.4\hfill & \hfill 0.29\hfill \\ {}\hfill -0.85\hfill & \hfill -0.15\hfill & \hfill 0\hfill & \hfill -0.69\hfill & \hfill 0.69\hfill & \hfill 2.38\hfill & \hfill 1.54\hfill & \hfill 0.85\hfill \\ {}\hfill 0.07\hfill & \hfill -0.07\hfill & \hfill -1\hfill & \hfill -0.77\hfill & \hfill 0.77\hfill & \hfill 1.54\hfill & \hfill 1.61\hfill & \hfill 0.84\hfill \\ {}\hfill 0.01\hfill & \hfill 0.01\hfill & \hfill 0\hfill & \hfill -0.92\hfill & \hfill -0.08\hfill & \hfill 0.85\hfill & \hfill 0.84\hfill & \hfill 0.82\hfill \end{array}\right]\left[\begin{array}{c}\hfill -50\hfill \\ {}\hfill -50\hfill \\ {}\hfill 0\hfill \\ {}\hfill -50\hfill \\ {}\hfill -10\hfill \\ {}\hfill 6\hfill \\ {}\hfill 1\hfill \\ {}\hfill 1\hfill \end{array}\right]+\left[\begin{array}{ccccccccc}\hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill \\ {}\hfill 0\hfill & \hfill 0.25\hfill & \hfill 0\hfill & \hfill -0.25\hfill & \hfill -0.25\hfill & \hfill 0.25\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill \\ {}\hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill \\ {}\hfill 0\hfill & \hfill -0.25\hfill & \hfill 0\hfill & \hfill 0.25\hfill & \hfill 0.25\hfill & \hfill -0.25\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill \\ {}\hfill 0\hfill & \hfill -0.25\hfill & \hfill 0\hfill & \hfill 0.25\hfill & \hfill 0.25\hfill & \hfill -0.25\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill \\ {}\hfill 0\hfill & \hfill 0.25\hfill & \hfill 0\hfill & \hfill -\mathbf{0.25}\hfill & \hfill -\mathbf{0.25}\hfill & \hfill 0.25\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill \\ {}\hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill \\ {}\hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill \\ {}\hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill \end{array}\right]k\\ {}=\left[\begin{array}{c}\hfill 1.937\hfill \\ {}\hfill 2.643\hfill \\ {}\hfill 1\hfill \\ {}\hfill 1.112\hfill \\ {}\hfill 1.419\hfill \\ {}\hfill -\mathbf{0.112}\hfill \\ {}\hfill 94.384\hfill \\ {}\hfill 42.447\hfill \\ {}\hfill 53.755\hfill \end{array}\right]+\left[\begin{array}{ccccccccc}\hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill \\ {}\hfill 0\hfill & \hfill 0.25\hfill & \hfill 0\hfill & \hfill -0.25\hfill & \hfill -0.25\hfill & \hfill 0.25\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill \\ {}\hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill \\ {}\hfill 0\hfill & \hfill -0.25\hfill & \hfill 0\hfill & \hfill 0.25\hfill & \hfill 0.25\hfill & \hfill -0.25\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill \\ {}\hfill 0\hfill & \hfill -0.25\hfill & \hfill 0\hfill & \hfill 0.25\hfill & \hfill 0.25\hfill & \hfill -0.25\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill \\ {}\hfill 0\hfill & \hfill 0.25\hfill & \hfill 0\hfill & \hfill -\mathbf{0.25}\hfill & \hfill -\mathbf{0.25}\hfill & \hfill 0.25\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill \\ {}\hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill \\ {}\hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill \\ {}\hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill \end{array}\right]\ k.\end{array} $$

(27a)

The path flow solutions found in (27a) are not unique. It depends on vector k. We select a vector k with its elements randomly generated between zero and one. But let the fourth element and the fifth element of vector k be both negative to remove the negative value h ₆ in (27a) as indicated in boldface. Then, we have an equilibrium solution as

$$ \left[\frac{h}{U}\right]=\left[\begin{array}{c}\hfill 1.937\hfill \\ {}\hfill 2.643\hfill \\ {}\hfill 1\hfill \\ {}\hfill 1.112\hfill \\ {}\hfill 1.419\hfill \\ {}\hfill -0.112\hfill \\ {}\hfill 94.384\hfill \\ {}\hfill 42.447\hfill \\ {}\hfill 53.755\hfill \end{array}\right]+\left[\begin{array}{c}\hfill 0\hfill \\ {}\hfill 0.317\hfill \\ {}\hfill 0\hfill \\ {}\hfill -0.317\hfill \\ {}\hfill -0.317\hfill \\ {}\hfill 0.317\hfill \\ {}\hfill 0\hfill \\ {}\hfill 0\hfill \\ {}\hfill 0\hfill \end{array}\right]=\left[\begin{array}{c}\hfill 1.937\hfill \\ {}\hfill 2.960\hfill \\ {}\hfill 1\hfill \\ {}\hfill 0.794\hfill \\ {}\hfill 1.102\hfill \\ {}\hfill 0.205\hfill \\ {}\hfill 94.384\hfill \\ {}\hfill 42.447\hfill \\ {}\hfill 53.755\hfill \end{array}\right]. $$

(27b)

It is also found that the equilibrium cost is independent to vector k. In particular, the reduced form of the system has row rank = 8 which reveals singularity. Paradoxical symptoms occur on the O/D pairs (O₁-D) and (O₂-D) after the addition of link 5. The equilibrium costs of these two O/D pairs are both increased at levels of 5.884 and 6.538 respectively. However, the equilibrium cost of the third O/D pair (O₃-D) is lower than that before adding link 5 at a level of 0.653. The detecting of the paradox can be made by employing Eq. (17) as

$$ \left[\frac{\delta h}{-\delta U}\right]={\left[\frac{\varDelta \prime G\varDelta }{\varLambda}\left|\frac{\varLambda \prime }{0}\right.\right]}^{-}\left[\frac{-\varDelta^{\prime }{G}_R}{-{e}_R}\right]{h}_R=\left[\begin{array}{ccccccc}\hfill 0.045\hfill & \hfill -0.045\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 0.5\hfill & \hfill -0.454\hfill & \hfill 0.045\hfill \\ {}\hfill -0.045\hfill & \hfill 0.045\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 0.5\hfill & \hfill 0.454\hfill & \hfill -0.045\hfill \\ {}\hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 1\hfill & \hfill 0\hfill \\ {}\hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 1\hfill \\ {}\hfill 0.05\hfill & \hfill 0.05\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill -5.5\hfill & \hfill -5\hfill & \hfill -0.5\hfill \\ {}\hfill -0.454\hfill & \hfill 0.454\hfill & \hfill 1\hfill & \hfill 0\hfill & \hfill -5\hfill & \hfill -5.454\hfill & \hfill -0.454\hfill \\ {}\hfill 0.045\hfill & \hfill -0.045\hfill & \hfill 0\hfill & \hfill 1\hfill & \hfill -0.5\hfill & \hfill -0.454\hfill & \hfill -0.954\hfill \end{array}\right]\left[\begin{array}{cc}\hfill -10\hfill & \hfill -10\hfill \\ {}\hfill -10\hfill & \hfill 0\hfill \\ {}\hfill -10\hfill & \hfill -10\hfill \\ {}\hfill 0\hfill & \hfill 0\hfill \\ {}\hfill -1\hfill & \hfill 0\hfill \\ {}\hfill 0\hfill & \hfill 0\hfill \\ {}\hfill 0\hfill & \hfill -1\hfill \end{array}\right]\left[\begin{array}{c}\hfill {h}_5\hfill \\ {}\hfill {h}_6\hfill \end{array}\right]=\left[\begin{array}{cc}\hfill -0.5\hfill & \hfill -0.5\hfill \\ {}\hfill -0.5\hfill & \hfill 0.5\hfill \\ {}\hfill 0\hfill & \hfill 0\hfill \\ {}\hfill 0\hfill & \hfill -1\hfill \\ {}\hfill -4.5\hfill & \hfill -4.5\hfill \\ {}\hfill -5\hfill & \hfill -5\hfill \\ {}\hfill 0.5\hfill & \hfill 0.5\hfill \end{array}\right]\left[\begin{array}{c}\hfill {h}_5\hfill \\ {}\hfill {h}_6\hfill \end{array}\right] $$

(28)

Because of the assumption that sboth h ₅ and h ₆ are positive, the sign of δU can be determined directly from (28) without the previous computations of (26) and (27). The sign of $\updelta {U}_{O_1-D}$ is positive since $-\updelta {U}_{O_1-D}=-4.5\left({h}_5+{h}_6\right)\le 0$. By similar treatments, the sign of $\updelta {U}_{O_2-D}$ and $\updelta {U}_{O_3-D}$ are positive and negative respectively. Finally, the second example network is designed to know the usefulness of the testing matrix M in Eq. (23) numerically. This example has the same topology of the example illustrated in Fig. 3, but only one O/D pair (O₁-D) remained with demand 6. The four link cost functions are replaced with c ₁(f ₁) = 50 + f ₁, c ₂(f ₂) = 50 + f ₂, c ₃(f ₃) = f ₃, c ₄(f ₄) = f ₄, respectively. The addition of L₅ remains unchanged. Following the testing matrix M in (23), we have

$$ M=\varDelta^{\prime }G\varDelta -\varDelta^{\prime }G{\varDelta}_R{e}_R^{-}\varLambda =\left[\begin{array}{cc}\hfill 1\hfill & \hfill -1\hfill \\ {}\hfill -1\hfill & \hfill 1\hfill \end{array}\right]. $$

(29)

Then, it can be further derived that

$$ \left[\begin{array}{cc}\hfill {x}_1\hfill & \hfill {x}_2\hfill \end{array}\right]\left[\begin{array}{cc}\hfill 1\hfill & \hfill -1\hfill \\ {}\hfill -1\hfill & \hfill 1\hfill \end{array}\right]\left[\begin{array}{c}\hfill {x}_1\hfill \\ {}\hfill {x}_2\hfill \end{array}\right]={x}_1^2-2{x}_1{x}_2+{x}_2^2={\left({x}_1-{x}_2\right)}^2\ge 0. $$

(30)

Equation (30) shows positive semi-definiteness of the testing matrix M. Meanwhile, the equilibrium O/D pair costs before and after the addition of link 5 are 56 and 28 respectively, which coincides with the result by utilizing the testing matrix M.

5 Conclusions

A generalized inverse approach is proposed to detect Braess’ paradox without the assumption of a unique equilibrium path flow solution for the classical Braess paradox problem indicated in this study. Based on this idea, two computing methods are suggested to calculate the equilibrium solution and to determine the sign of the change of equilibrium cost. In addition, when network geometry is changed in a way that multiple routes are newly supplied, we prove that there exists at least one O/D pair connected by new routes such that Braess’ paradox does not occur if the corresponding test matrix is positive semi-definite. In particular, Corollary 3.1 supplies information that can predict the paradox taking place. It agrees with suggestions, made by existing studies, that in order to prevent situations from becoming worse, evaluations should be performed on a network before policy-makings. The derivation of the test matrix M is intuitively established by the equilibrium formulation of the classical Braess paradox problem. It states that the change of equilibrium cost for the used paths is composed of two parts. One made by the flow changes of the used paths after link additions. The other one is from the increased flows of the new routes. Finally, we find that the conservation between flow changes of the used paths and increased flows of the new routes gives non-unique solutions. However the change of equilibrium cost is unique and can be determined by any one of the non-unique-path flow solutions which is successfully expressed as a generalized inverse formulation in this study.

Appendix

This appendix gives an example to describe that the result of (I − e ⁻ _R e _R ) is a staircase matrix such that all nonzero elements lie on |W _R | square diagonal blocks B _i , i = 1, 2, ⋯, |W _R |. In particular, each row sum of B _i is zero. Now, let us consider an O/D pair-path incidence matrix for a set of newly added paths P _R , denoted as e _R , being reduced to

$$ {e}_R=\left[\begin{array}{c}\hfill 1\ 1\ 1\ 0\ 0\hfill \\ {}\hfill 0\ 0\ 0\ 1\ 1\hfill \end{array}\right]. $$

(a1)

For this instance, the number of paths in the set P _R is five. The set of O/D pairs W _R possesses two O/D pairs accordingly, namely |W _R |=2. The set P _R is partitioned into two disjoint sets denoted as ${D}_{w_1}$ and ${D}_{w_2}$. And, we have $\left|{D}_{w_1}\right|=3$ and $\left|{D}_{w_2}\right|=2$, subsequently. By using Theorem 3.2 to compute e ⁻ _R , we apply

$$ {e}_R^{-}={e}_R^{\prime }{\left({e}_R{e}_R^{\prime}\right)}^{-1}. $$

(a2)

First, calculate the result of ${e}_R{e}_R^{\prime }$ as

$$ {e}_R{e}_R^{\prime }=\left[\begin{array}{c}\hfill 1\ 1\ 1\ 0\ 0\hfill \\ {}\hfill 0\ 0\ 0\ 1\ 1\hfill \end{array}\right]\left[\begin{array}{c}\hfill 1\ 0\hfill \\ {}\hfill 1\ 0\hfill \\ {}\hfill 1\ 0\hfill \\ {}\hfill 0\ 1\hfill \\ {}\hfill 0\ 1\hfill \end{array}\right]=\left[\begin{array}{c}\hfill 3\ 0\hfill \\ {}\hfill 0\ 2\hfill \end{array}\right]. $$

(a3)

The two diagonal elements are actually the values of $\left|{D}_{w_1}\right|$ and $\left|{D}_{w_2}\right|$ respectively. Then, we have the inverse

$$ {\left({e}_R{e}_R^{\prime}\right)}^{-1}=\left[\begin{array}{c}\hfill \frac{1}{3}\kern0.5em 0\hfill \\ {}\hfill 0\kern0.5em \frac{1}{2}\hfill \end{array}\right]. $$

(a4)

It follows that

$$ {e}_R^{-}={e}_R^{\prime }{\left({e}_R{e}_R^{\prime}\right)}^{-1}=\left[\begin{array}{c}\hfill 1\ 0\hfill \\ {}\hfill 1\ 0\hfill \\ {}\hfill 1\ 0\hfill \\ {}\hfill 0\ 1\hfill \\ {}\hfill 0\ 1\hfill \end{array}\right]\left[\begin{array}{c}\hfill \frac{1}{3}\kern0.5em 0\hfill \\ {}\hfill 0\kern0.5em \frac{1}{2}\hfill \end{array}\right]=\left[\begin{array}{c}\hfill \frac{1}{3}\ 0\hfill \\ {}\hfill \frac{1}{3}\ 0\hfill \\ {}\hfill \frac{1}{3}\ 0\hfill \\ {}\hfill 0\ \frac{1}{2}\hfill \\ {}\hfill 0\ \frac{1}{2}\hfill \end{array}\right]. $$

(a5)

Finally, the result of (I − e ⁻ _R e _R ) is as

$$ I-{e}_R^{-}{e}_R=I-\left[\begin{array}{c}\hfill \frac{1}{3}\ 0\hfill \\ {}\hfill \frac{1}{3}\ 0\hfill \\ {}\hfill \frac{1}{3}\ 0\hfill \\ {}\hfill 0\ \frac{1}{2}\hfill \\ {}\hfill 0\ \frac{1}{2}\hfill \end{array}\right]\left[\begin{array}{c}\hfill 1\ 1\ 1\ 0\ 0\hfill \\ {}\hfill 0\ 0\ 0\ 1\ 1\hfill \end{array}\right]=I-\left[\begin{array}{c}\hfill \frac{1}{3}\ \frac{1}{3}\ \frac{1}{3}\ 0\ 0\hfill \\ {}\hfill \frac{1}{3}\ \frac{1}{3}\ \frac{1}{3}\ 0\ 0\hfill \\ {}\hfill \frac{1}{3}\ \frac{1}{3}\ \frac{1}{3}\ 0\ 0\hfill \\ {}\hfill 0\ 0\ 0\ \frac{1}{2}\ \frac{1}{2}\hfill \\ {}\hfill 0\ 0\ 0\ \frac{1}{2}\ \frac{1}{2}\hfill \end{array}\right]=\left[\begin{array}{c}\hfill \frac{2}{3}\kern0.5em \left(\frac{-1}{3}\right)\ \left(\frac{-1}{3}\right)\kern0.5em 0\kern1.25em 0\hfill \\ {}\hfill \left(\frac{-1}{3}\right)\kern0.75em \frac{2}{3}\kern0.75em \left(\frac{-1}{3}\right)\kern0.5em 0\kern1.25em 0\hfill \\ {}\hfill\ \left(\frac{-1}{3}\right)\ \left(\frac{-1}{3}\right)\kern0.5em \frac{2}{3}\kern1.25em 0\kern1.25em 0\kern0.5em \hfill \\ {}\hfill 0\kern1.5em 0\kern1.75em 0\kern1.25em \frac{1}{2}\ \left(\frac{-1}{2}\right)\hfill \\ {}\hfill 0\kern1.5em 0\kern1.75em 0\kern1em \left(\frac{-1}{2}\right)\ \frac{1}{2}\hfill \end{array}\right]. $$

(a6)

Equation (a6) shows that each row sum of the diagonal blocks, i.e., B ₁ and B ₂, is equal to zero without loss of generality. It shows that the structure of e _R , encapsulating the disjoint sets of P _R with respect to the O/D pairs, produces the advantageous results of (I − e ⁻ _R e _R ) that we demonstrated in this appendix.