Detecting Braess Paradox Based on Stable Dynamics in General Congested Transportation Networks

Abstract

This study examined the detection of the Braess Paradox by stable dynamics in general congested transportation networks. Stable dynamics, suggested by Nesterov and de Palma (2003), is a new model which describes and provides a stable state of congestion in urban transportation networks. In comparison with the user equilibrium model, which is based on the arc travel time function in analyzing transportation networks, stable dynamics requires few parameters and is coincident with intuitions and observations on congestion. It is therefore expected to be a useful analysis tool for transportation planners. The phenomenon whereby increasing network capacity, for example creating new routes, known as arcs, may decrease its performance is called the Braess Paradox. It has been studied intensively under user equilibrium models with the arc travel time function since it was first demonstrated by Braess (1968). However, the development of a general model to detect the Braess Paradox under stable dynamics models remains an open problem. In this study, we suggest a model to detect the paradox in general networks under stable dynamics. In our model, we decide whether the Braess Paradox will occur in a given network, detect Braess arcs or Braess crosses if the network permits the paradox, and present a numerical example of the application of the model to a given network.

1 Introduction

1.1 Stable dynamics

In this study, we develop a model for detecting the Braess paradox in general congested transportation networks. Our proposed study is based on the stable dynamics suggested by Nesterov and de Palma (2003). They pointed out that the arc travel time function, which is generally assumed in user equilibrium models, is not appropriate for observations and intuitions on road congestion. And a re-calibration process is required in the real application of a user equilibrium model to congested road networks. The re-calibration, which is the adjustment of parameters of the arc travel function, is often a long and expensive task for many transportation planners. Therefore, they introduced a new and simple model based on physical concepts to enable stable dynamics, i.e., easy and proper description on the congestion. The model does not require any arc travel time function, but simply two basic physical terms are assumed: the maximal flow($\overline {\mathbf{f}} _{\mathbf{i}}$) and the minimal travel time($\overline {\mathbf{t}} _{\mathbf{i}}$) for each arc i. These are also assumed as constants of each arc travel time function in user equilibrium models. The maximal flow is the capacity of the road, and the minimal travel time is the free-flow travel time according to the limited maximal speed on the road. Then, the following is assumed as of a theory of physics: If an arc flow is under the maximum flow, it runs at the maximal speed. If the flow reaches the maximum flow, it runs under the maximal speed. In other words, if ${{\bf{f}}_{{\bf{i}}} {\bf{ < }}\overline{{\bf{f}}} _{{\bf{i}}} }$, then ${{\bf{t}}_{{\bf{i}}} {\bf{ = }}\overline{{\bf{t}}} _{{\bf{i}}} }$ and if ${{\bf{f}}_{{\bf{i}}} {\bf{ = }}\overline{{\bf{f}}} _{{\bf{i}}} }$, then ${{\bf{t}}_{{\bf{i}}} \ge \overline{{\bf{t}}} _{{\bf{i}}} }$, where f _i is a flow and t _i is a arc travel time for each arc i. The stable dynamics model is developed with the above simple axiom and the well-known Wardrop Principle (Wardrop 1952). (See Section 1.2 below for the Wardrop Principle.) However, the new and simple model, stable dynamics model, provides surprisingly good results coincident with observation and intuition on traffic congestion. Furthermore, the network equilibrium of the model is given by an efficient mathematical programming problem. See (Nesterov and de Palma 2000, 2003, 2006) for the detailed development of the stable dynamics model.

1.2 Studies on the Braess paradox in user equilibrium models

Studies on the Braess paradox in user equilibrium models are based on the arc travel time function, which is a function of an arc flow that it is assumed to be nondecreasing. Two kinds of equilibrium models use arc travel time functions. One is the user equilibrium model in which each driver finds the shortest path to his destination and goes along the path without any cooperation with other drivers. The equilibrium in this model is defined as the situation that each driver cannot decrease his travel time by changing his path. See (Bernstein and Smith 1994). The other is the system equilibrium in which a single user or a control unit determines all paths and assigns flows to the paths. The total travel time is minimized at the system equilibrium. The Braess paradox is a terminology denoting the situation in which the total travel time increases when the network capacity increases. This situation occurs in a user equilibrium model rather than in a system equilibrium model. The equilibrium flow of the user equilibrium model can be represented by the Wardrop Principle: for each origin-destination, the traffic-assigned paths have the same path travel time and no traffic-unassigned path with a smaller travel time exists. The equilibrium flow represented by the Wardrop Principle can be formulated as a minimization problem known as the Beckmann et al. (1956) model or a Variational Inequality (Nagurney 1993).

The Braess paradox is an old research topic in user equilibrium models that has attracted many approaches and studies. Braess (1968) asserted that even if every driver takes the path that looks most favorable to him, the resultant travel times may not be minimal. Furthermore, he indicated for the first time, by an example, that an extension of the road network may cause a redistribution of the traffic that actually results in longer individual travel times. The example introduced by Braess has the same network topology of Fig. 3 of this study, and 10x, 50 + x, and 10 + x for the arc travel time functions, where x is the arc flow.

Murchland (1970) demonstrated the occurrence of the paradox in the same network topology with different arc travel time functions (${{{\mathbf{23x}}} \mathord{\left/ {\vphantom {{{\mathbf{23x}}} {\mathbf{3}}}} \right. \kern-\nulldelimiterspace} {\mathbf{3}}}$, 46, 0). Frank (1981) assumed general linear functions for arc travel times for the same network topology and analyzed in detail to suggest sufficient and necessary conditions for the existence of the paradox. Braess, Murchland and Frank introduced the paradox in the sense that an extension of a network can increase travel times. However, Fisk (1979) introduced a paradox in a different sense by showing that the travel times may increase as a result of a decrease in traffic demand while maintaining the same network capacity.

Up to that time, studies on the Braess paradox were done in special or simple networks, until Steinberg and Zangwill (1983), for the first time, studied the existence condition of the Braess paradox in general networks. They developed a condition of existence of the Braess paradox when a new arc is added to a general network. They also assumed a general linear function for an arc travel time function. Dafermos and Nagurney (1984) studied the existence condition of the paradox in the general network with nonsymmetric arc travel times. The travel time of each arc is regarded as a function of the flows of all arcs and is also assumed to be nonsymmetric Jacobian on all arc flows. With the assumed linearity and monotonicity of the functions, they developed two formulas: one showing the effect on travel time when the demand is changed and the other giving the existence condition of the Braess paradox when a new arc is added to the network.

Pas and Principio (1997) analyzed the relationship between the Braess paradox and its causes, the arc travel time function and the traffic demand. They demonstrated that there exists a range of traffic demand which can exhibit the Braess paradox. The lower and upper limits of the range are functions of the parameters of the given linear travel time function. In their study, they assumed the same network as first introduced by Braess. In a slightly different approach, Yang and Bell (1998) demonstrated that the Braess paradox can be avoided if the arc which causes the paradox has the opposite direction.

Static models are assumed in most studies on the Braess paradox. However, Akamatsu (2000) gave an example of the Braess paradox in a dynamic user equilibrium model while Akamatsu and Heydecker (2003) developed a necessary and sufficient condition for the Braess paradox in a general dynamic user equilibrium model. The dynamic user equilibrium in Akamatsu (2000) entails exogeneous time-varing traffic inflows and no schedule delay costs, and is thus limited to route decisions and aggregate travel time as the measure of network performance. As in the static model, the Braess paradox in the dynamic model denotes the situation that increased network capacity decreases the network performance.

From a different point of view, a game-theoretic approach for traffic assignment and equilibrium in transportation networks has been introduced. Devarajan (1981) showed that the user equilibrium in the transportation network is a pure Nash equilibrium of a noncooperative game. Friesz (1985) also showed that a user equilibrium is an extreme system consisting of many noncooperative players while a system equilibrium is another extreme system with one player who controls the entire network. Harker (1988) presented a mixed behavior network equilibrium model in which each origin-destination pair is either controlled by a noncooperative game player or a cooperative game player. Catoni and Pallottino (1991) studied another intermediate model which was modeled on the Cournot-Nash equilibrium model. With one player, the model is reduced to the system equilibrium model. By increasing the number of players, the model approximates the user equilibrium model. Intuitively, increasing the cooperation will apparently reduce the congestion, but they present an example of a paradoxical situation.

Recently, Roughgarden (2006) studied approximation algorithms for the network design problems that remove Braess arcs in a given network. In his study, he regarded drivers as the selfish and noncooperative players of the Nash equilibrium. He proved that there is no approximation algorithm with an approximation ratio of less than ${{\mathbf{n}} \mathord{\left/ {\vphantom {{\mathbf{n}} {\mathbf{2}}}} \right. \kern-\nulldelimiterspace} {\mathbf{2}}}$ for networks with n nodes and nondecreasing arc travel functions unless P = NP. For networks with a linear travel time function on each arc, he proved that there is no $\left( {{{\mathbf{4}} \mathord{\left/ {\vphantom {{\mathbf{4}} {\mathbf{3}}}} \right. \kern-\nulldelimiterspace} {\mathbf{3}}}{\mathbf{ - \varepsilon }}} \right)$-approximation algorithm for any ɛ > 0 unless P = NP. Here the approximation ratio means that the total travel time provided by the approximation algorithm within the polynomial time cannot exceed the exact optimal total travel time multiplied by the ratio. He also suggested an approximation algorithm, called the ‘trivial algorithm’ since it generates the entire network.

1.3 User equilibrium model vs stable dynamics model in determining arc travel time

Although several types of function have been used for arc travel times in user equilibrium models, one of the most popular functions is the following BPR equation, which was recommended by the US BPR(Bureau of Public Roads 1964):

$${{\bf{t}}_{{\bf{i}}} {\bf{ = }}\overline{{\bf{t}}} _{{\bf{i}}} {\left( {{\bf{1 + A}} \cdot {\left( {{{{\bf{f}}_{{\bf{i}}} } \over {\overline{{\bf{f}}} _{{\bf{i}}} }}} \right)}^{{\bf{B}}} } \right)}.}$$

(1-1)

In the BPR equation, the minimal travel time ($\overline {\mathbf{t}} _{\mathbf{i}}$) and the maximal flow ($\overline {\mathbf{f}} _{\mathbf{i}}$) are constants, and A and B are parameters. Hence the arc travel time(t _i ) is a polynomial function of the type ‘constant term + the B-th degree term of arc flow(f _i )’. The parameters A = 0.15 and B = 4.0 have been suggested for the BPR equation. Numerous later studies have updated the parameters. One recent study suggested parameter values according to various road types. For example, A = 0.88, B = 9.8 in 70 mph freeways, and A = 1.0, B = 5.4 in 70 mph multilanes. The graphs of BPR equations are shown in Fig. 1. (See http://www.sierafoot.org)

Fig. 1

Graphs of arc travel time: the solid turned-up line is for the stable dynamics model and the dotted curves are the graphs of the BPR equations of the user equilibrium model

In addition to the BPR equation, other types of arc travel time function have also been applied in user equilibrium models. Nevertheless, parameters as coefficients and/or exponents are required in any type of function. Parameter estimation is very important in real applications, although a re-calibration process is required in real applications to road networks. This begins with measurement for gathering reliable road data, on the basis of which the parameters are estimated.

In stable dynamics models, the arc travel time is equal to the minimal travel time when the ratio of (flow/capacity) is less than 1, and it is greater than or equal to the minimal value when the ratio is equal to 1. Therefore, the graph of the arc travel time in stable dynamics models is given by the solid turned-up line in Fig. 1. To be accuracy, this is not a function since it has infinitely many values when the ratio of (flow/capacity) is equal to 1. Actually, the arc travel time in the congested situation (i.e., when the ratio is equal to 1) is determined by the model, an efficient mathematical program, and is given by the flows of all arcs in the network.

One advantage of the stable dynamics approach is its ability to forecast easily a new equilibrium when a network condition is changed. Assume a road construction. Some lanes of the road are closed and the maximum possible speed is decreased. In user equilibrium models, re-calibration processes are required before computing a new equilibrium. First, the parameters of the travel function of the road should be newly estimated on the basis of newly measured road data. Second, the re-calibration processes need to be applied to the other roads affected by the road. The influence on the other roads depends on the topology of the network, traffic demands and the sets of paths of origin-destination pairs. However, in stable dynamics models, only the new minimal travel time ($\overline {\mathbf{t}} _{\mathbf{i}}$) and maximal flow ($\overline {\mathbf{f}} _{\mathbf{i}}$) of the road are substituted and the mathematical program generates a new equilibrium. Here the new minimal travel time can be determined by the new limited maximum speed, and the maximal flow by the number of closed lanes. Therefore stable dynamics could be a useful tool for transportation planners to forecast the effect of the change of network condition.

Stable dynamics models are based on the premise, as of yet unproven, that if a network condition is changed, then the steady state will be represented by stable dynamics. Nevertheless, if this premise is true, then the stable dynamics model is the link between the static and dynamic network models and, furthermore, can be considered a basic analysis tool since it does not have any parameters in determining the arc travel time in the model. Apart from proving the premise, value remains in showing that the stable dynamics model is a useful tool to approximate traffic congestion in transportation networks. With this purpose, the present study and the park-and-ride model (Nesterov and de Palma 2006) were studied.

1.4 An open problem in stable dynamics models

The Braess paradox also exists in a stable dynamics model. Examples in simple networks were shown by Nesterov and de Palma (2003). In this study, we develop a general detection method for the Braess paradox in general networks. This is an open problem in stable dynamics models. Unlike user equilibrium models, stable dynamics models do not require any arc travel time function. Therefore, the studies in stable dynamics models are completely different from those in user equilibrium models. The characteristics of studies in both models are presented in Fig. 2.

Fig. 2

Research studies on the Braess paradox and their characteristics

The method developed in this study cannot detect the Braess paradox on the network with the conventional arc travel time functions described in Subsection 1.2. If linear functions are assumed in the network (for example, 10 + x where x is the arc flow), then there are no arc flow-capacities and hence no congestions occurs in the network in a strict sense. In stable dynamics models, there is no Braess paradox if there is no congestion in a network. The arc travel time is always equal to the minimal travel time at each arc in an uncongested network. We apply our detecting method to the network with the same topology as that shown in the literature, but in which congestion exists and is described by only arc maximal flow and arc minimal travel time without arc travel time functions.

The paper is organized as follows. In Section 2, we introduce a path flow-based formulation for the basic stable dynamics model. In Section 3, we introduce examples of the Braess paradox without arc travel time function. Our definition is represented as a Braess path. We also define three causes of Braess path: Braess arc, Braess cross and Braess combination. We also give a simple necessary condition for Braess arc. In Section 4, we develop a mathematical program, of which the solution plays a key role in detecting a Braess path in any given network. In Section 5, we offer an example of an application of our model to a network. In Section 6, the conclusions and directions for further research are presented.

2 A basic stable dynamics model based on path-flow formulation

In this section, we introduce the basic stable dynamics model developed by Nesterov and de Palma (2000, 2003, 2006). However, we modify the model by suggesting a path flow formulation since our detection model of the Braess paradox is based on paths.

2.1 Notations and assumptions

Initially, we assume a model with one origin-destination pair of nodes. Subsequently, the development in the model is directly generalized to a model with many origin-destination pairs. The straightforward generalization is due to our definition of the Braess paradox in Section 3, which is defined for a given origin-destination pair. The general model is introduced in Subsection 4.4. Now, the following notations are defined for one origin-destination pair model.

G :

G(N, E), the directional network,

N :

the set of nodes, |N| is the number of nodes,

E :

the set of directional arcs, |E| is the number of arcs,

d:

the demand from the origin node n _s to the destination node n _t ,

P :

the set of paths from n _s to n _t , |P| is the number of paths,

$\overline {\mathbf{f}} _{\mathbf{i}}$ :

the maximum flow of arc i ∈ E, $\overline {\mathbf{f}} \in {\mathbf{R}}^{\left| {\mathbf{E}} \right|}$ is its vector form, $\overline {\mathbf{f}} \geqslant {\mathbf{0}}$,

$\overline {\mathbf{t}} _{\mathbf{i}}$ :

the minimum travel time on arc i ∈ E, $\overline {\mathbf{t}} \in {\mathbf{R}}^{\left| {\mathbf{E}} \right|}$ is its vector form, $\overline {\mathbf{t}} \geqslant {\mathbf{0}}$,

F _j :

the flow of path j in P, F ∈ R ^|P| is its vector form,

f _i :

the flow of arc i, f ∈ R ^|E| is its vector form,

t _i :

the travel time on arc i, t ∈ R ^|E| is its vector form,

T :

the shortest path travel time from n _s to n _t , T ∈ R,

A :

|E| × |P| arc-path incidence matrix, A _ij = 1 if arc i is in path j, A _ij = 0 otherwise,

e _n :

the n-dimensional column vector with all unit elements, e _n = (1,⋯,1) ^T,

x·y :

the inner product of two vectors x,y, i.e., ${\mathbf{x}} \cdot {\mathbf{y = }}{\sum\nolimits_{\mathbf{i}} {{\mathbf{x}}_{{\mathbf{i}}} {\mathbf{y}}_{{\mathbf{i}}} } }$.

In a basic stable dynamics model, the network equilibrium is represented by the values of flow f and travel time t for a given maximum flow $\overline {\mathbf{f}}$ and minimum travel time $\overline {\mathbf{t}}$. The minimum travel time of an arc is the travel time with speed limit, that is, the free-flow travel time without any congestion on the arc. The maximum flow of an arc is the maximum flow capacity per unit time, which is determined by the number of lanes, the period of green light at the intersection, the weather condition, etc. The equilibrium is developed based on the following two assumptions.

Assumption 2-1

(Wardrop principle) Given the arc travel time t , each driver choose the shortest (with respect to t ) path to travel from origin to destination.

Assumption 2-2

On each arc i ∈ E , the flow f _i never exceeds $\overline f _i$ . For the travel time on the arc i , (i) if $f_i <\overline f _i$ , $t_i = \overline t _i$ . (ii) If $f_i = \overline f _i$ , $t_i \geqslant \overline t _i$ .

2.2 Stable dynamics model based on path flow formulation

In this subsection, we develop the path flow formulation of the basic stable dynamics model. If the arc travel time is assumed to be given by t, then the shortest path travel time from origin to destination is given by:

$${\mathbf{T}}\left( {\mathbf{t}} \right){\mathbf{ = min}}\left\{ {{\mathbf{A}}_{ \cdot {\mathbf{j}}} \cdot {\mathbf{t}}\left| {{\mathbf{j = 1,}} \cdots {\mathbf{,}}\left| {\mathbf{P}} \right|} \right.} \right\},$$

(2-1)

where A _·j is the jth column of A. T(t), as a function of t, is piecewise linear and concave. Therefore, the total travel time for the traffic demand is given by dT(t). From the definitions of $\overline {\mathbf{f}}$ and $\overline {\mathbf{t}}$, any equilibrium solution in a stable dynamics model should satisfy the following constraints (2-2):

$$0 \leqslant {\text{f}} \leqslant \overline {\text{f}} ,\,{\text{t}} \geqslant \overline {\text{t}} .$$

(2-2)

Proposition 2-3

The arc travel time t* and the arc flow f* are an equilibrium solution satisfying (2-2) if and only if t* is the solution to problem (2-3) and$f* = \overline f - s*$, where s* is a vector of optimal dual multipliers for inequality (2-3b).

$$\begin{array}{*{20}c}{Maximize} {dT - \overline f \cdot t} \\\end{array} $$

(2-3a)

$$\begin{array}{*{20}c}{Subject\,to} {t \geqslant \overline t ,} \\\end{array} $$

(2-3b)

$$A^T t \geqslant Te_{\left| p \right|} .$$

(2-3c)

Proof

By theorem 8 of (Nesterov and de Palma 2003), the arc travel time t* and the arc flow f* are an equilibrium solution satisfying (2-2) if and only if t* is the solution to the following problem (2-4) and ${\mathbf{f}}*{\mathbf{ = }}\overline {\mathbf{f}} - {\mathbf{s}}*$, where s* is a vector of optimal dual multipiers for inequality (2-4). As shown in the following equivalents, problem (2-4) is equivalent to final problem (2-7), which is same as problem (2-3) in the proposition.

$${\mathbf{max}}\left\{ {{\mathbf{dT}}\left( {\mathbf{t}} \right) - \overline {\mathbf{f}} \cdot {\mathbf{t}}\left| {\mathbf{t}} \right. \geqslant \overline {\mathbf{t}} } \right\}$$

(2-4)

$$= {\mathbf{max}}\left\{ {{\mathbf{dT}} - \overline {\mathbf{f}} \cdot {\mathbf{t}}\left| {{\mathbf{t}} \geqslant \overline {\mathbf{t}} ,{\mathbf{T}} = } \right.{\mathbf{min}}\left\{ {{\mathbf{A}}_{ \cdot {\mathbf{j}}} \cdot {\mathbf{t}}\left| {{\mathbf{j}} = {\mathbf{1}}, \cdots ,\left| {\mathbf{P}} \right|} \right.} \right\}} \right\}$$

(2-5)

$$= {\mathbf{max}}\left\{ {{\mathbf{dT}} - \overline {\mathbf{f}} \cdot {\mathbf{t}}\left| {{\mathbf{t}} \geqslant \overline {\mathbf{t}} ,{\mathbf{A}}_{ \cdot {\mathbf{j}}} \cdot {\mathbf{t}} \geqslant {\mathbf{T}}{\text{,}}\quad {\mathbf{j}} = {\mathbf{1}}, \cdots ,\left| {\mathbf{P}} \right|} \right.} \right\}$$

(2-6)

$$\begin{array}{*{20}c}{ = {\mathbf{max}}\left\{ {{\mathbf{dT}} - \overline {\mathbf{f}} \cdot {\mathbf{t}}\left| {{\mathbf{t}} \geqslant \overline {\mathbf{t}} ,\quad {\mathbf{A}}^{\mathbf{T}} {\mathbf{t}} \geqslant {\mathbf{Te}}_{\left| {\mathbf{P}} \right|} } \right.} \right\}.} {\left( {{\mathbf{QED}}} \right)} \\\end{array} $$

(2-7)

For a path flow formulation, Ω is denoted as the set of feasible path flows. Then it is defined by:

$${\mathbf{\Omega }} = \left\{ {{\mathbf{F}} \in {\mathbf{R}}^{\left| {\mathbf{P}} \right|} \left| {{\mathbf{AF}} \leqslant \overline {\mathbf{f}} ,{\mathbf{F}} \cdot {\mathbf{e}}_{\left| {\mathbf{P}} \right|} = {\mathbf{d}},{\mathbf{F}} \geqslant {\mathbf{0}}} \right.} \right\}.$$

(2-8)

Now, as we want to compute an equilibrium satisfying assumptions 2-1 and 2-2 in terms of path flows, we obtain the following (2-9) instead of the constraints (2-2) in applying Proposition 2-3:

$${\mathbf{t}} \geqslant \overline {\mathbf{t}} ,{\mathbf{F}} \in {\mathbf{\Omega }}{\text{.}}$$

(2-9)

3 Examples, definitions and a necessary condition of the Braess paradox

3.1 Examples of Braess paradox in stable dynamics model

This section presents three examples of the Braess paradoxes: one for the paradox with Braess arc, the second for the paradox with Braess cross, and the third for the paradox with Braess combination. Their definitions are presented below.

Figure 3 shows an example of the paradox with Braess arc. It has the same network topology of the example introduced by Braess (1968) except not having arc travel time functions. The units of time and flow are skipped. The network of Fig. 3(b) is generated by adding an arc (v, w) to the network of Fig. 3(a). The traffic demands from s to t of both networks (a) and (b) are 10. By applying problem (2-3) of proposition 2-3, equilibrium solutions to both networks are obtained. At the equilibria, two paths of s – v – t (path 1) and s – w – t (path 2) are used for network (a), and three paths of s – v – t (path 1), s – w – t (path 2) and s – v – w – t (path 3) are used for network (b).

Fig. 3

Braess arc in stable dynamics: An example. a Network before adding an arc (v, w). b Network after adding an arc (v, w)

Figure 4 shows the equilibrium solutions of the networks of Fig. 3. For network (a), we have an equilibrium solution of F ₁ = 5 for path 1(s – v – t) and F ₂ = 5 for path 2(s – w – t). And we have ${\mathbf{f}}_{{\mathbf{sv}}} = {\mathbf{5}} <\overline {\mathbf{f}} _{{\mathbf{sv}}} ,\,{\mathbf{t}}_{{\mathbf{sv}}} = {\mathbf{5}} = \overline {\mathbf{t}} _{{\mathbf{sv}}}$; ${\mathbf{f}}_{{\mathbf{vt}}} = {\mathbf{5}} <\overline {\mathbf{f}} _{{\mathbf{vt}}} ,\,{\mathbf{t}}_{{\mathbf{vt}}} = {\mathbf{10}} = \overline {\mathbf{t}} _{{\mathbf{vt}}}$; ${\mathbf{f}}_{{\mathbf{sw}}} = {\mathbf{5}} <\overline {\mathbf{f}} _{{\mathbf{sw}}} ,\,{\mathbf{t}}_{{\mathbf{sw}}} = {\mathbf{10}} = \overline {\mathbf{t}} _{{\mathbf{sw}}}$; ${\mathbf{f}}_{{\mathbf{wt}}} = {\mathbf{5}} <\overline {\mathbf{f}} _{{\mathbf{wt}}} ,\,{\mathbf{t}}_{{\mathbf{wt}}} = {\mathbf{5}} = \overline {\mathbf{t}} _{{\mathbf{wt}}}$. The shortest path travel time is T = 15. For network (b), we have an equilibrium solution of F ₁ = 4 for path 1(s – v – t), F ₂ = 4 for path 2(s – w – t) and F ₃ = 2 for path 3(s – v – w – t). And we have ${\mathbf{f}}_{{\mathbf{sv}}} = {\mathbf{6}} = \overline {\mathbf{f}} _{{\mathbf{sv}}} ,\,{\mathbf{t}}_{{\mathbf{sv}}} = {\mathbf{9}} >\overline {\mathbf{t}} _{{\mathbf{sv}}}$; ${\mathbf{f}}_{{\mathbf{vt}}} = {\mathbf{4}} <\overline {\mathbf{f}} _{{\mathbf{vt}}} ,\,{\mathbf{t}}_{{\mathbf{vt}}} = {\mathbf{10}} = \overline {\mathbf{t}} _{{\mathbf{vt}}}$; ${\mathbf{f}}_{{\mathbf{sw}}} = {\mathbf{4}} <\overline {\mathbf{f}} _{{\mathbf{sw}}} ,\,{\mathbf{t}}_{{\mathbf{sw}}} = {\mathbf{10}} = \overline {\mathbf{t}} _{{\mathbf{sw}}}$; ${\mathbf{f}}_{{\mathbf{wt}}} = {\mathbf{6}} = \overline {\mathbf{f}} _{{\mathbf{wt}}} ,\,{\mathbf{t}}_{{\mathbf{wt}}} = {\mathbf{9}} >\overline {\mathbf{t}} _{{\mathbf{wt}}}$; ${\mathbf{f}}_{{\mathbf{vw}}} = {\mathbf{2}} <\overline {\mathbf{f}} _{{\mathbf{vw}}} ,\,{\mathbf{t}}_{{\mathbf{vw}}} = {\mathbf{1}} = \overline {\mathbf{t}} _{{\mathbf{vw}}}$. The shortest path travel time is T = 19. In other words, the shortest path travel time is paradoxically increased from 15 to 19 by adding a new arc (v, w).

Fig. 4

Braess arc in stable dynamics: Two equilibrium solutions of Fig. 3. a With two paths, the shortest path travel time T = 15. b With one more path including arc (v, w), the shortest path travel time T = 19

Now consider a cross at a node, which is the road intersection with a signal in real transportation networks. A cross from one road to another is allowed according to the control of the signal. Figure 5 shows an example of a paradox with Braess cross at a node. The units of time and flow are skipped. Actually, the figure is the limit of Fig. 3(b). When the minimal travel time $\overline {\mathbf{t}} _{{\mathbf{vw}}}$ of the arc (v, w) decreases to 0, in other words, the arc (v, w) shrinks and disappears, then node v and node w are finally combined into node x. When a driver selects a path from s to t, he takes a cross at node x. For example, there are four crosses at node x in Fig. 5. Here a cross at a node is expressed as ‘arc-(node)-arc’.

Fig. 5

Braess cross at a node in stable dynamics: An example network.

To show a Braess cross at node x, first assume that only crosses 1 and 2 are allowed, which gives two possible paths from s to t: path 1(v1 – v2) and path 2(w1 – w2). (See Fig. 6(a), which corresponds to Fig. 4(a).) Then we get equilibrium flow 5 on each path and the path travel time on each path is 15. Hence the shortest path travel time is T = 15. Next, add cross 3, which gives three possible paths from s to t: path 1(v1 – v2), path 2(w1 – w2) and path 3(v1 – w2). (See Fig. 6(b), which corresponds to Fig. 4(b).) Then we get new equilibrium flows 4, 4 and 2 on paths 1, 2 and 3, respectively. In the equilibrium, the travel time on each arc is 10. Hence the shortest path travel time is T = 20. Paradoxically, the shortest path travel time is increased from 15 to 20 by allowing a new cross at node x, v1 – (x) – w2. Note that the equilibrium travel time rises by one more unit in this example than in the Braess arc example. This is because free-flow time is zero for the Braess cross, and one for the corresponding Braess arc.

Fig. 6

Braess cross in stable dynamics: Two equilibrium solutions of Fig. 5. a With two paths, the shortest path travel time T = 15. b With three paths after allowing one more cross v1 – (x) – w2, the shortest path travel time T = 20

Now we show a complex example of paradox. In this example the network has two inefficient arcs. But each arc of them is not a Braess arc. Figure 7 shows it. Suppose that all crosses at each node are allowed. The units of time and flow are skipped. The network of Fig. 7(b) is generated by adding two arcs (v, u), (u, w) to the network of Fig. 7(a). The traffic demands from s to t of both networks (a) and (b) are 10. By applying problem (2-3) of proposition 2-3, equilibrium solutions to both networks are obtained. At the equilibria, two paths of s – v – t (path 1) and s – w – t (path 2) are used for network (a), and three paths of s – v – t (path 1), s – w – t (path 2) and s – v – u – w – t (path 3) are used for network (b).”

Fig. 7

Braess paradox with inefficient arcs: A complex example. a Network before adding two arcs (v, u), (u, w)

Figure 8 shows the equilibrium solutions of the networks of Fig. 7. For network (a), we have same equilibrium solution as Fig. 4(a) since the path s – u – t has path travel time 20 which is longer than the shortest path travel time (T = 15). For network (b), we have an equilibrium solution of F ₁ = 4 for path 1 (s – v – t), F ₂ = 4 for path 2 (s – w – t) and F ₃ = 2 for path 3 (s – v – u – w – t). And we have ${\mathbf{f}}_{{\mathbf{sv}}} = {\mathbf{6}} = \overline {\mathbf{f}} _{{\mathbf{sv}}} ,\,{\mathbf{t}}_{{\mathbf{sv}}} = {\mathbf{9}} >\overline {\mathbf{t}} _{{\mathbf{sv}}}$; ${\mathbf{f}}_{{\mathbf{vt}}} = {\mathbf{4}} <\overline {\mathbf{f}} _{{\mathbf{vt}}} ,\,{\mathbf{t}}_{{\mathbf{vt}}} = {\mathbf{10}} = \overline {\mathbf{t}} _{{\mathbf{vt}}}$; ${\mathbf{f}}_{{\mathbf{sw}}} = {\mathbf{4}} <\overline {\mathbf{f}} _{{\mathbf{sv}}} ,\,{\mathbf{t}}_{{\mathbf{sw}}} = {\mathbf{10}} = \overline {\mathbf{t}} _{{\mathbf{sw}}}$; ${\mathbf{f}}_{{\mathbf{wt}}} = {\mathbf{6}} = \overline {\mathbf{f}} _{{\mathbf{wt}}} ,\,{\mathbf{t}}_{{\mathbf{wt}}} = {\mathbf{9}} >\overline {\mathbf{t}} _{{\mathbf{wt}}}$; ${\mathbf{f}}_{{\mathbf{vu}}} = {\mathbf{2}} <\overline {\mathbf{f}} _{{\mathbf{vu}}} ,\,{\mathbf{t}}_{{\mathbf{vu}}} = {\mathbf{0}}{\mathbf{.5}} = \overline {\mathbf{t}} _{{\mathbf{vu}}}$; ${\mathbf{f}}_{{{\mathbf{uw}}}} = {\mathbf{2}} < \overline{{\mathbf{f}}} _{{{\mathbf{uw}}}} ,\,{\mathbf{t}}_{{{\mathbf{uw}}}} = {\mathbf{0}}{\mathbf{.5}} = \overline{{\mathbf{t}}} _{{{\mathbf{uw}}}}$. The shortest path travel time is T = 19. In other words, the shortest path travel time is paradoxically increased from 15 to 19 by adding two new arcs (v, u) and (u, w). Note that we have same equilibrium solution as Fig. 8(a) if only one arc of them is added. Therefore each arc of them is not a Braess arc in isolation. But Braess paradox occurs when the two arcs added at once.

Fig. 8

Braess paradox with inefficient arcs: Two equilibrium solutions of Fig. 7. a With two paths, the shortest path travel time T = 15. b With one more path including arcs (v, u) and (u, w), the shortest path travel time T = 19

Now we show a more complex example of paradox. In this example the network has two inefficient arcs and three inefficient crosses. But each of them is not a Braess arc or a Braess cross. Figure 9 shows it. In Fig. 7, we supposed that all crosses at each node are allowed. Now limit this assumption. If we only allow three crosses s – (v) – t, s – (u) – t and s – (w) – t as shown in Fig. 9(a). Then the equilibrium solution is the same as Fig. 8(a). Now we add two arcs (v, u), (u, w) and three crosses s – (v) – u, v – (u) – w, u – (w) – t as shown in Fig. 9(b). Then the network includes the path s – v – u – w – t and the equilibrium solution is the same as Fig. 8(b). Therefore two arcs (v, u) and (u, w) and three crosses s – (v) – u, v – (u) – w, u – (w) – t occur in the Braess paradox.

Fig. 9

Braess paradox with inefficient arcs and inefficient crosses. a Network before adding arcs (v, u), (u, w) and crosses s – (v) – u, v – (u) – w, and u – (w) – t. b Network after adding arcs (v, u), (u, w) and crosses s – (v) – u, v – (u) – w, and u – (w) – t

3.2 Definitions of Braess path, Braess arc and Braess cross in stable dynamics model

Braess path, Braess arc, Braess cross and Braess combination are defined in the stable dynamics model in general networks.

Definition 3-1

(Braess path) For a source-destination pair, suppose that a new path is added to the existing set of paths. If the shortest travel time of the new set of paths is longer than that of the existing set of paths, then the new added path is defined as a Braess path.

Definition 3-2

(Braess arc) For a source-destination pair, assume that the given network does not have any Braess path. Now suppose that a new arc is added to the network. If the new network has a Braess path passing through the new arc, then the arc is defined as a Braess arc.

The arc (u, v) in Fig. 3(b) is an example of Braess arc.

Definition 3-3

(Braess cross) For a source-destination pair, assume that the given network does not have any Braess path. Now suppose that a new cross is added to the network. If the new network has a Braess path passing through the new cross, then the cross is defined as a Braess cross.

The cross v1 – (x) – w2 at node x in Fig. 6(b) is an example of Braess cross at a node.

Definition 3-4

(Braess combination) For a source-destination pair, assume that the given network does not have any Braess path. Now suppose that two or more new arcs and new crosses are added to the network. If the new network has a Braess path passing through the new arcs and crosses, then the new arcs and crosses are defined as a Braess combination.

Assume the original network is that of Fig. 7(a). Then the set of two arcs (v, u), (u, w) in Fig. 7(b) is an example of a Braess combination. The set of two arcs (v, u), (u, w) and three crosses s – (v) – u, v – (u) – w, u – (w) – t is another example of a Braess combination, which is shown in Fig. 9(b).

P is the set of paths which can lead the assigned flows from n _s to n _t . Then we have the following proposition. The proof is unnecessary since it is clear.

Proposition 3-1

A path${\mathbf{n}}_{{\mathbf{s}}} {\mathbf{ - n}}_{{\mathbf{1}}} {\mathbf{ - n}}_{{\mathbf{2}}} {\mathbf{ - \ldots - n}}_{{{\mathbf{p - 1}}}} {\mathbf{ - n}}_{{\mathbf{p}}} {\mathbf{ - n}}_{{\mathbf{t}}}$is in P if and only if the following conditions are satisfied (Fig. 10):

• a) All arcs along the path, i.e., arcs${\mathbf{n}}_{{\mathbf{s}}} {\mathbf{ - n}}_{{\mathbf{1}}} {\mathbf{,}}\,{\mathbf{n}}_{{\mathbf{1}}} {\mathbf{ - n}}_{{\mathbf{2}}} {\mathbf{,}}\,{\mathbf{ \ldots ,n}}_{{\mathbf{p}}} {\mathbf{ - n}}_{{\mathbf{t}}}$, exist.

• b) All crosses at a node along the path, i.e., crosses $n_s - \left( {n_1 } \right) - n_2 ,\,n_{k - 1} - \left( {n_k } \right) - n_{k + 1} \left( {k = 2, \cdots ,p - 1} \right),\,n_{p - 1} - \left( {n_p } \right) - n_t$ , are allowed. ( ${\mathbf{n}}_{{{\mathbf{k - 1}}}} {\mathbf{ - }}{\left( {{\mathbf{n}}_{{\mathbf{k}}} } \right)}{\mathbf{ - n}}_{{{\mathbf{k + 1}}}}$ denotes a cross in a node n _k which connects n _{k – 1} and n _{k + 1} as shown in the Braess cross example in the previous subsection.)

Fig. 10

A path ${\mathbf{n}}_{\mathbf{s}} - {\mathbf{n}}_{\mathbf{1}} - {\mathbf{n}}_{\mathbf{2}} - \cdots - {\mathbf{n}}_{{\mathbf{p - 1}}} - {\mathbf{n}}_{\mathbf{p}} - {\mathbf{n}}_{\mathbf{t}}$ in P

Proposition 3-2

Braess path has at least one Braess arc, or at least one Braess cross, or at least one Braess combination. If all crosses at each node are allowed in a given network, Braess path has at least one Braess arc or at least one Braess combination with only arcs.

Proof

By contradiction, assume that no Braess arc exists and no Braess cross exists and no Braess combination exists. Then all arcs in the Braess path already exist, and all crosses at each node along the Braess path are already allowed. By proposition 3-1, this implies that the path already exists in P and it cannot be a Braess path. (QED)

3.3 A necessary condition for Braess arc in stable dynamics

Assume that a given network G does not have any Braess path. Here G is a general network. Now we add a new arc to the given network and examine whether or not the new arc is Braessic.

Let t ^*, f ^*, T ^* be the optimal values of an equilibrium solution of the given network before adding an arc. They are obtained by solving problem (2-3) with the network. Now define the following notations:

i ₊ :

the added new arc,

$\overline {\mathbf{t}} _{\mathbf{ + }}$ :

the minimum travel time on arc i ₊ , $\overline {\mathbf{t}} _{\mathbf{ + }} \geqslant {\mathbf{0}}$,

Q :

the set of all paths from n _s to n _t passing through the arc i ₊ ,

B :

|E|×|Q| arc-path incidence matrix, B _ij = 1 if arc i is in path j ∈ Q, B _ij = 0 otherwise.

• (A, in Subsection 1.2, is the incidence matrix of paths without passing through the added arc i ₊ .)

Let Q ^* be denoted by the set of paths in Q with smaller path travel time than T ^*. Then it is given by:

$${\mathbf{Q}}* = \left\{ {{\mathbf{j}} \in {\mathbf{Q}}\left| {\left[ {_{\mathbf{1}}^{{\mathbf{B}}_{ \cdot {\mathbf{j}}} } } \right] \cdot \left[ {_{\overline {\mathbf{t}} _{\text{ + }} }^{{\mathbf{t}}*} } \right] <{\mathbf{T}}*} \right.} \right\}.$$

(3-1)

Theorem 3-3

Assume that a given network G has no Braess path. Let t*, f*, T* be the optimal solution to (2-3) of the given network before adding an arc. Then Q* ≠ ∅is a necessary condition for the new arc to be a Braess arc.

Proof

Obtain network G ₊ by adding a new arc to network G to G ₊. If Q* = ∅ then, we will show, arc i ₊ is not a Braess arc. Suppose, on the contrary, that i ₊ is a Braess arc. Then an equilibrium solution G ₊ , $\left[ {_{{\mathbf{t}}_{\text{ + }}^\prime }^{{\mathbf{t}}^\prime } } \right] \in {\mathbf{R}}^{\left| {\mathbf{E}} \right| + {\mathbf{1}}}$, $\left[ {_{\mathbf{0}}^{{\mathbf{f}}^\prime } } \right] \in {\mathbf{R}}^{\left| {\mathbf{E}} \right| + {\mathbf{1}}}$, has the corresponding equilibrium travel time T ^′ satisfying T ^′ >T*. But, since Q* = ∅, we have, $\left[ {_{\overline {\mathbf{t}} _ + }^{{\mathbf{t}}^ * } } \right] \in {\mathbf{R}}^{\left| {\mathbf{E}} \right| + {\mathbf{1}}}$, $\left[ {_{\mathbf{0}}^{{\mathbf{f}}^ * } } \right] \in {\mathbf{R}}^{\left| {\mathbf{E}} \right| + {\mathbf{1}}}$, and T* is a feasible solution on G ₊ . And the objective values satisfy ${\mathbf{dT}}* - \,\overline {\mathbf{f}} \cdot {\mathbf{t}}* - \,\overline {\mathbf{f}} _ + \overline {\mathbf{t}} _ + \geqslant {\mathbf{dT}}^\prime - \overline {\mathbf{f}} \cdot {\mathbf{t}}^\prime - \overline {\mathbf{f}} _ + \overline {\mathbf{t}} _ + \geqslant {\mathbf{dT}}^\prime - \overline {\mathbf{f}} \cdot {\mathbf{t}}^\prime - \overline {\mathbf{f}} _ + {\mathbf{t}}^\prime _ +$. The first inequality follows from the optimality of t ^*, T ^* for G, the second from ${\text{t}}_ + ^\prime >\overline {\text{t}} _ +$. Therefore, we get $\left[ {_{\overline {\mathbf{t}} _ + }^{{\mathbf{t}}*} } \right] \in {\mathbf{R}}^{\left| {\mathbf{E}} \right| + {\mathbf{1}}}$, $\left[ {_{\mathbf{0}}^{{\mathbf{f}}{\text{*}}} } \right] \in {\mathbf{R}}^{\left| {\mathbf{E}} \right| + {\mathbf{1}}}$, and T* is also optimal for G ₊ and we have T ^′ = T*. A contradiction to that T ^′ > T*. (QED)

4 A detection model of the Braess paradox

In this section, we develop a detection model of Braess path in general networks, based on the path flow formulation in the stable dynamics model.

4.1 Selfish routing and new assumptions

The Braess paradox is caused by selfish routing. In Fig. 3(a), the shortest path travel time before adding an arc is 15 time units for two paths. After a new arc is added to the network, the new path passing through the arc is considered by every driver since it is more favorable to him. Its travel time is shorter than 15 time units. Hence, drivers choose the new path and move from the old paths to the new path until the travel times of three paths become the same. However, the new common path travel times of the three paths become 19 time units, a paradoxical situation which arises due to selfish routing. A driver cannot yield the shorter path to others. Each driver just compares the times of the three paths and then chooses the shortest path. He cannot compare the equilibrium times before and after adding the arc. A similar situation occurs in Fig. 5 when a new cross is allowed. The difference between the old and new path travel times in the paradoxical situation is called ‘the price of anarchy in a network’. See (Roughgarden 2006).

In fact, assumption 2-1(Wardrop Principle) is the real reason for the paradoxical situation since it requires each driver to choose the shortest path in any situation. So selfish routing cannot be avoided under the assumption, which must be modified if we want to avoid selfish routing. Actually, the assumption is modified in developing a model to detect the Braess paradox. Now we replace assumption 2-1 with the following assumption 4-1 to avoid selfish routing. Notice that the new assumption cannot guarantee the Wardrop Principle any more. We term the new assumption as a ‘requirement of equality’ since it requires an equal travel time for every driver. Assumption 2-2 is rewritten as assumption 4-2 because of path flow formulation.

Assumption 4-1

(Requirement of equality) Given the arc travel time t , the path chosen by each driver to travel from an origin to a destination has the shortest travel time, under the condition that all the chosen paths for the origin-destination pair have the same travel time.

Assumption 4-2

The path flow F is assigned not to exceed the maximal arc flow $\overline f$ , that is, $f = AF <\overline f$ . For the travel time on the arc i , (i) if $f_i <\overline f _i ,\,t_i = \overline t _i$ , (ii) if $f_i = \overline f _i ,\,t_i \geqslant \overline t _{\mathbf{i}}$ .

Assumption 4-1 allows the existence of an unused path with smaller travel time than that of the used paths. Now we present an example of avoiding selfish routing under the assumption. Consider again Fig. 3. Under the new assumption, the new path (s – v – w – t) passing through the added arc (v, w) can be neglected even though it has the shortest travel time. If some drivers choose the new shorter path, it does not satisfy the requirement of equality of the assumption. Therefore, the existing two paths with the same travel time of 15 time units can satisfy assumption 4-1. In Fig. 11, we compare assumptions 2-1 or 4-1 from the points of view of requirements, consequences, exceptions and unexpected results.

Fig. 11

Comparison of assumptions 2-1 and 4-1

4.2 A model for equilibrium solution satisfying the new assumptions

In this subsection, we develop a model to find equilibrium solutions satisfying the new assumptions 4-1 and 4-2. We will show that the equilibrium solution has an important role in detecting a Braess path in the next subsection. In our model we suppose that the network can transport the traffic demand from its origin to its destination. In addition, we suppose that the traffic demand can also be transported in the network in which all the inefficient arcs and crosses that contain Braess paths have been removed. The development of this subsection is similar to that of Subsection 2.2, but differs in the introduction of assumption 4-1 instead of assumption 2-1.

Recall the notation Ω which was defined in (2-8).

$${\mathbf{\Omega }} = \left\{ {{\mathbf{F}} \in {\mathbf{R}}^{\left| {\mathbf{P}} \right|} \left| {{\mathbf{AF}} \leqslant \overline {\mathbf{f}} ,\,{\mathbf{F}} \cdot {\mathbf{e}}_{\left| {\mathbf{P}} \right|} = {\mathbf{d}},\,{\mathbf{F}} \geqslant {\mathbf{0}}} \right.} \right\}.$$

(4-1)

Here F is a vector form of F _j which is the flow of path j in P(the set of paths from the origin to the destination) as defined in the Subsection 2.1. The path flow F and the arc travel time t are decision variables of our developing model. Suppose that feasible path flow F and arc travel time t are given. And let the set of paths that are assigned a positive flow be denoted by ${\mathbf{P}}_{\mathbf{ + }} \left( {\mathbf{F}} \right) = \left\{ {{\text{j}} \in {\mathbf{P}}\left| {{\text{F}}_{\mathbf{j}} >{\mathbf{0}}} \right.} \right\}$. We can allow the unchosen paths with smaller travel time under the new assumptions. Therefore, we consider the paths in P ₊ (F) instead of P. So the shortest path travel time in our concerns is computed by the following:

$${\mathbf{\Gamma }}\left( {{\mathbf{t}},{\mathbf{F}}} \right) = {\mathbf{min}}\left\{ {{\mathbf{A}}_{ \cdot {\mathbf{j}}} \cdot {\mathbf{t}}\left| {{\mathbf{j}} \in {\mathbf{P}}_ + \left( {\mathbf{F}} \right)} \right.} \right\}$$

(4-2)

Like T(t) in Subsection 2.2, Γ(t, F) is piecewise linear in t and concave; hence its super differential can be defined by denoting I ₊ (t, F) as:

$${\mathbf{I}}_ + \left( {{\mathbf{t}}{\text{,}}{\mathbf{F}}} \right) = \left\{ {{\mathbf{j}} \in {\mathbf{P}}_ + \left( {\mathbf{F}} \right)\left| {{\mathbf{\Gamma }}\left( {{\mathbf{t}}{\text{,}}{\mathbf{F}}} \right)} \right. = {\mathbf{A}}_{ \cdot {\mathbf{j}}} \cdot {\mathbf{t}}} \right\}.$$

(4-3)

Then the super differential of Γ(t, F) with respect to t is given by the following, see (Clarke 1983), where ‘conv’ means the convex hull:

$$\partial _{\mathbf{t}} {\mathbf{\Gamma }}\left( {{\mathbf{t}}{\text{,}}{\mathbf{F}}} \right) = {\mathbf{conv}}\left\{ {{\mathbf{A}}_{ \cdot {\mathbf{j}}} ,\quad {\mathbf{j}} \in {\mathbf{I}}_{\text{ + }} \left( {{\mathbf{t}}{\text{,}}{\mathbf{F}}} \right)} \right\}.$$

(4-4)

Let the cost function be C(t, F) = dΓ(t, F). To obtain the equilibrium solutions satisfying assumptions 4-1 and 4-2, the basic constraints for the solution are:

$$\begin{array}{*{20}c}{{\mathbf{t}} \geqslant \overline {\mathbf{t}} } {{\mathbf{F}} \in {\mathbf{\Omega }}} \\\end{array} .$$

(4-5)

Theorem 4-3

The arc travel time t* and path flow F* satisfying (4-5) are the equilibrium solution of assumptions 4-1 and 4-2 if and only if t* is the optimal solution to problem (4-6) and$AF* = \overline f - s*$, where s* is the optimal dual multiplier for inequality (4-6b).

$$\begin{array}{*{20}c}{Maximize} {{\mathbf{C}}\left( {{\mathbf{t}}{\text{,}}{\mathbf{F}}} \right)} \\\end{array} - \overline {\mathbf{f}} \cdot {\mathbf{t}}$$

(4-6a)

$$\begin{array}{*{20}c}{subject\,to} {{\mathbf{t}} \geqslant \overline {\mathbf{t}} ,} \\\end{array} $$

(4-6b)

Proof

Let us denote as s the multiplier for inequality (4-6b). Then the Lagrangian for problem (4-6) is given by:

$$\mathcal{L}\left( {{\mathbf{t}}{\text{,}}\,{\mathbf{F}}{\text{,}}\,{\mathbf{s}}} \right) = {\mathbf{C}}\left( {{\mathbf{t}}{\text{,}}\,{\mathbf{F}}} \right) - \overline {\mathbf{f}} \cdot {\mathbf{t}} - {\mathbf{s}} \cdot \left( {{\mathbf{t}} - \overline {\mathbf{t}} } \right).$$

(4-7)

Then problem (4-6) is solvable if and only if the minimax problem ${{\bf{min}}_{{{\bf{s}} \ge {\bf{0}}}} \,{\bf{max}}_{{\bf{t}}} \,{\cal L}{\left( {{\bf{t}}{\rm{, }}{\bf{F}}{\rm{,}}\,{\bf{s}}} \right)}}$ has a saddle point for F ∈ Ω. This means that there exists AF* ∈ ∂ _t C(t*, F*) such that:

$${\mathbf{f}}* = {\mathbf{AF}}* = \overline {\mathbf{f}} - {\mathbf{s}}*,$$

(4-8a)

$${\mathbf{s}} \cdot \left( {{\mathbf{t}} - \overline {\mathbf{t}} } \right) = {\mathbf{0}},\,{\mathbf{t}}* \geqslant \overline {\mathbf{t}} ,\,{\mathbf{s}}* \geqslant {\mathbf{0}}.$$

(4-8b)

Now we claim that f = AF with respect to t is an equilibrium flow satisfying assumptions 4-1 and 4-2 if and only if f = AF = ∂ _t C(t, F). For the proof of claim, first we want to show that the path flow F with respect to t is an equilibrium solution satisfying assumptions 4-1 and 4-2 if and only if there exists some g ∈ ∂ _t Γ(t, F) such that AF = d g. To show this, consider the subnetwork G ^′ (N ^′, E ^′ ) of G(N, E) where ${\mathbf{E}}^\prime = \left\{ {{\mathbf{i}} \in {\mathbf{E}}\left| {{\mathbf{f}}_{\mathbf{i}} = \left( {{\mathbf{AF}}} \right)_{\mathbf{i}} >{\mathbf{0}}} \right.} \right\}$ and N ^′ is the set of all nodes that are heads or tails of arcs in E ^′. And let P ^′ be the set of paths defined in G ^′ (N ^′, E ^′ ) as a subset of P. Then from (4-4) the path flow F with respect to t is an equilibrium solution satisfying assumptions 4-1 and 4-2 if and only if any path in P ^′ has the same path travel time, Γ(t, F). Now any path P ^′ in has the same path travel time, Γ(t, F), and AF = d g if and only if there exist λ _j ≥ 0 for j ∈ I ₊ (t, F) such that ${\sum\limits_{{\mathbf{j}} \in {\mathbf{I}}_{ + } {\left( {{\mathbf{t}}{\text{, }}{\mathbf{F}}} \right)}} {{\mathbf{\lambda }}_{{\mathbf{j}}} = {\mathbf{1}}} }$ and ${\mathbf{AF}} = {\mathbf{d}}{\sum\limits_{{\mathbf{j}} \in {\mathbf{I}}_{ + } {\left( {{\mathbf{t}}{\text{, }}{\mathbf{F}}} \right)}} {{\mathbf{\lambda }}_{{\mathbf{j}}} {\mathbf{A}}_{{ \cdot {\mathbf{j}}}} } }$, that is equivalently, there exists some g ∈ ∂ _t Γ(t, F) such that AF = d g. Hence, the proof of claim is completed. Now by the claim f ^* = AF ^* with respect to t ^* is an equilibrium flow satisfying assumptions 4-1 and 4-2. (QED)

Problem (4-6) is a model to give an equilibrium solution satisfying assumptions 4-1 and 4-2. Now the following corollary gives another problem (4-9) by path flow formulation.

Corollary 4-4

The arc travel time t* and path flow F* satisfying (4-5) are the equilibrium solution of assumptions 4-1 and 4-2 if and only if t* is the solution to problem (4-9) and$AF^* = \overline f - s^*$, where s* is the optimal dual multiplier for inequality (4-9b) andΓ* is the shortest travel time, under the condition that all the chosen paths have the same travel time.

$$\begin{array}{*{20}c}{Maximize} {{\mathbf{d\Gamma }} - \overline {\mathbf{f}} \cdot {\mathbf{t}}} \\\end{array} $$

(4-9a)

$$\begin{array}{*{20}c}{subject\,to} {{\mathbf{t}} \geqslant \overline {\mathbf{t}} ,} \\\end{array} $$

(4-9b)

$$\begin{array}{*{20}c}{\left( {{\mathbf{\Gamma }} - {\mathbf{A}}_{ \cdot {\mathbf{j}}} \cdot {\mathbf{t}}} \right){\mathbf{F}}_{\mathbf{j}} \leqslant {\mathbf{0}},} {{\mathbf{j}} \in {\mathbf{P}}} \\\end{array} ,$$

(4-9c)

$${\mathbf{AF}} \leqslant \overline {\mathbf{f}} ,$$

(4-9d)

$${\mathbf{F}} \cdot {\mathbf{e}}_{\left| {\mathbf{P}} \right|} = {\mathbf{d}},$$

(4-9e)

$${\mathbf{F}} \geqslant {\mathbf{0}}.$$

(4-9f)

Proof

Consider (4-9c). For some j ∈ P, F _j > 0 implies A _·j ·t ≥ Γ. Hence from (4-9c) we have dΓ = dΓ(t, F) = C(t, F). Therefore, problem (4-9) is equivalent to problem (4-6) for F ∈ Ω. (QED)

Problem (2-3) is a linear program, whereas problem (4-9) is not a convex program. The left hand side of inequality (4-9c) is a non-convex quadratic function. Therefore, usual commercial solvers may offer only local optimal solutions to problem (4-9). In this study, we assume a global optimal solution to the problem. We will briefly discuss a solution method to find the global optimal solution in Section 6.

4.3 A detection method for the Braess paradox in general networks

As described in Subsection 4.1, the Braess paradox occurs under assumption 2-1. Now we show that a Braess paradox under assumption 2-1 corresponds to an unchosen path with a smaller travel time under assumption 4-1. Then, by using the correspondence, we suggest an algorithm to detect the Braess paradox in general networks. Problem (2-3) is a model under assumption 2-1, whereas problem (4-9) is a model under assumption 4-1.

Recall that t*, F* and Γ* are the solution of problem (4-9). Now denote by ${\mathbf{P}}_{\mathbf{o}}^*$ the set of unused paths with smaller path travel time than Γ*, thus giving:

$${\mathbf{P}}_{\mathbf{o}}^{\text{*}} = \left\{ {{\mathbf{j}} \in {\mathbf{P}}\left| {{\mathbf{F}}_{\mathbf{j}}^{\text{*}} = {\mathbf{0}},\,{\mathbf{A}}_{ \cdot {\mathbf{j}}} \cdot {\mathbf{t}}{\text{* $<$ }}{\mathbf{\Gamma }}{\text{*}}} \right.} \right\}.$$

(4-10)

Theorem 4-5

Let t*, F* andΓ^*be the global solution to (4-9). Then any path in$P_o^*$is a Braess path.

Proof

Let $\mathop {\mathbf{P}}\limits^ \sim = {\mathbf{P}}\backslash {\mathbf{P}}_{\mathbf{o}}^{\text{*}}$. If we solve problem (2-3) with ${\mathbf{\tilde P}}$ instead of P, then the shortest path travel time of the solution should be Γ*. We select any path ${\mathbf{p}}_{\mathbf{o}} \in {\mathbf{P}}_{\mathbf{o}}^{\text{*}}$ and let $\mathop {\mathbf{P}}\limits^ \approx = \mathop {\mathbf{P}}\limits^ \sim \cup \left\{ {{\mathbf{p}}_{\mathbf{o}} } \right\}$. If we solve problem (2-3) again with $\mathop {\mathbf{P}}\limits^ \approx$ instead of P, then selfish routing is caused by assumption 2-1. Therefore, some positive flow is assigned to the path and the shortest path travel time of the solution is greater than Γ* as a consequence. Therefore, p _o is a Braess path. (QED)

Now we develop an algorithm to find Braess paths in general networks. Let P be the set of all possible paths for the given origin-destination pair and ‘Solver’ be the solution method able to find the global solution to problem (4-9). For a more practical algorithm with a commercial solver providing a local solution, see the brief discussion in Section 6. Now we suggest a method to find the Braess path in general networks.

Algorithm 4-6

• (Step 1) Solve problem (4-9) with P by using Solver, and let t*, F* and Γ* be the solution.

• (Step 2) Find the shortest path p _min in P with respect to the arc travel time t*. Denote T _min by the travel time of p _min . If T _min < Γ*, p _min is a Braess path. Otherwise, a Braess path does not exist.

Theorem 4-7

If T _min < Γ*, the shortest pathp _min is a Braess path.

Proof

The proof is straightforward from theorem 4-5 since T _min < Γ* implies ${\mathbf{p}}_{{\mathbf{min}}} \in {\mathbf{P}}_{\mathbf{o}}^{\text{*}}$. If is a used path, the path travel time T _min cannot be less than Γ*. It should be equal to Γ*. Hence p _min is a Braess path. (QED)

Theorem 4-8

The Braess path found by algorithm 4-6 has at least one unused Braess arc, or at least one unused Braess cross, or at least one unused Braess combination.

Proof

By proposition 3-2, the Braess path found by the algorithm has a Braess arc, or a Braess cross, or a Braess combination. We now show that at least one Braess arc or at least one Braess cross or at least one Braess combination is unused at the solution given by step 1 of the algorithm. If all Braess arcs and all Braess crosses are used, then the path should be a used path. It cannot be a Braess path since the path travel time ≥ Γ ^*. (QED)

4.4 A model with many origin-destination pairs

In order to represent the problem with many origin-destination pairs, modify the previously defined notations as follows. The superscript is used for the specific origin-destination pair.

K :

the set of origin-destination pairs,

d ^k :

the demand of the k-th origin-destination pair,

P ^k :

the set of given paths for the k-th origin-destination pair,

${\mathbf{F}}_{\mathbf{j}}^{\mathbf{k}}$ :

the flow of the j(∈ P ^k )-th path for the k-th pair, ${\mathbf{F}}^{\mathbf{k}} \in {\mathbf{R}}^{\left| {{\mathbf{p}}^{\mathbf{k}} } \right|}$ is a vector form,

T ^k :

the shortest path travel time for the k-th origin-destination pair under the Wardrop Principle,

Γ ^k :

the shortest path travel time for the k-th origin-destination pair under requirement of equality,

A ^k :

|E|×|P ^k| matrix, if path j includes arc i, ${\mathbf{A}}_{{\mathbf{ij}}}^{\mathbf{k}} = {\mathbf{1}}$. Otherwise, ${\mathbf{A}}_{{\mathbf{ij}}}^{\mathbf{k}} = {\mathbf{0}}$.

e ^k :

the |P ^k|-dimensional column vector with all unit elements, e ^k = (1,⋯,1) ^T.

Then problem (2-3) to find an equilibrium solution satisfying assumptions 2-1 and 2-2 for one origin-destination pair becomes the following problem (4-11) for many origin-destination pairs:

$${{\bf{Maximize}}\quad {\sum\limits_{{\bf{k}} \in {\bf{K}}} {{\bf{d}}^{{\bf{k}}} {\bf{T}}^{{\bf{k}}} - \overline{{\bf{f}}} \cdot {\bf{t}}} }}$$

(4-11a)

$$\begin{array}{*{20}c}{{\mathbf{Subject}}\,{\mathbf{to}}} {{\mathbf{t}} \geqslant \overline {\mathbf{t}} ,} \\\end{array} $$

(4-11b)

$$\left( {{\mathbf{A}}^{\mathbf{k}} } \right)^{\mathbf{T}} {\mathbf{t}} \geqslant {\mathbf{T}}^{\mathbf{k}} {\mathbf{e}}^{\mathbf{k}} {\text{,}}\,{\mathbf{k}} \in {\mathbf{K}}{\text{,}}$$

(4-11c)

Problem (4-9) to find an equilibrium solution satisfying assumptions 4-1 and 4-2 for one origin-destination pair becomes the following problem (4-12) for many origin-destination pairs.

$${\mathbf{Maximize}}\quad {\sum\limits_{{\mathbf{k}} \in {\mathbf{K}}} {{\mathbf{d}}^{{\mathbf{k}}} {\mathbf{\Gamma }}^{{\mathbf{k}}} - \overline{{\mathbf{f}}} \cdot {\mathbf{t}}} }$$

(4-12a)

$$\begin{array}{*{20}c}{{\mathbf{Subject}}\,{\mathbf{to}}} {{\mathbf{t}} \geqslant \overline {\mathbf{t}} ,} \\\end{array} $$

(4-12b)

$$\left( {{\mathbf{\Gamma }}^{\mathbf{k}} - {\mathbf{A}}_{ \cdot {\mathbf{j}}}^{\mathbf{k}} \cdot {\mathbf{t}}} \right){\mathbf{F}}_{\mathbf{j}}^{\mathbf{k}} \leqslant {\mathbf{0}},\,{\mathbf{j}} \in {\mathbf{P}}^{\mathbf{k}} ,\,{\mathbf{k}} \in {\mathbf{K}},$$

(4-12c)

$${\sum\limits_{{\mathbf{k}} \in {\mathbf{K}}} {{\mathbf{A}}^{{\mathbf{k}}} {\mathbf{F}}^{{\mathbf{k}}} \leqslant \overline{{\mathbf{f}}} ,} }$$

(4-12d)

$${\mathbf{F}}^{\mathbf{k}} \cdot {\text{e}}_{\left| {{\mathbf{p}}^{\mathbf{k}} } \right|}^{\mathbf{k}} = {\mathbf{d}}^{\mathbf{k}} ,\,{\mathbf{k}} \in {\mathbf{K}},$$

(4-12e)

$${\mathbf{F}}^{\mathbf{k}} \geqslant {\mathbf{0}},\,{\mathbf{k}} \in {\mathbf{K}}.$$

(4-12f)

Let t*, F*^k and Γ*^k (k ∈ K) be the solution of problem (4-12). Let ${\mathbf{P}}_{\mathbf{o}}^{*{\mathbf{k}}}$ denote the set of unused paths with smaller path travel time than Γ ^*k. Then it is given by:

$${\mathbf{P}}_{\mathbf{o}}^{*{\mathbf{k}}} = \left\{ {{\mathbf{j}} \in {\mathbf{P}}^{\mathbf{k}} \left| {{\mathbf{F}}_{\mathbf{j}}^{*{\mathbf{k}}} = {\mathbf{0}},\,{\mathbf{A}}_{ \cdot {\mathbf{j}}}^{\mathbf{k}} \cdot {\mathbf{t}}* <\Gamma *^{\mathbf{k}} } \right.} \right\}.$$

(4-13)

A Braess path is defined for a given specific origin-destination pair, as given in definition 3-1. Therefore, theorem 4-5 can be extended to the model with many origin-destination pairs. The proof is skipped since it is almost the same as for the one origin-destination pair.

Theorem 4-9

Let t*, F*^k andΓ*^k (k∈K) be the solution of problem (4-12). Then any path in$P_o^{*k}$is a Braess path for the k-th origin-destination pair.

5 An application of the algorithm

In Subsection 3.1, we showed the Braess paradox in stable dynamics model with the same network topology introduced by Braess (1968). In this section, we apply algorithm 4-6 to a network with 6 nodes and 9 arcs in Fig. 12. Its topology is the same as in Fig. 11 as introduced by Roughgarden (2006).

Fig. 12

An example network with 6 nodes and 9 arcs.

Assume one origin-destination pair, s – t, and assume its demand 15. P = {p1, p2, p3, p4, p5} is the set of all possible paths, where ${\mathbf{p1}} = {\mathbf{s}} - {\mathbf{v1}} - {\mathbf{t}}$, ${\mathbf{p2}} = {\mathbf{s}} - {\mathbf{v1}} - {\mathbf{w1}} - {\mathbf{t}}$, ${\mathbf{p3}} = {\mathbf{s}} - {\mathbf{v2}} - {\mathbf{w1}} - {\mathbf{t}}$, ${\mathbf{p4}} = {\mathbf{s}} - {\mathbf{v2}} - {\mathbf{w2}} - {\mathbf{t}}$, and ${\mathbf{p5}} = {\mathbf{s}} - {\mathbf{w2}} - {\mathbf{t}}$. Let the 9 arcs be denoted by ${{\bf{a1}} = {\left( {{\bf{s}}{\rm{,}}\,{\bf{v1}}} \right)},{\bf{a2}} = {\left( {{\bf{s}}{\rm{,}}\,{\bf{v2}}} \right)},{\bf{a3}} = {\left( {{\bf{s}}{\rm{,}}\,{\bf{w2}}} \right)},{\bf{a4}} = {\left( {{\bf{v1}},\,{\bf{w1}}} \right)},{\bf{a5}} = {\left( {{\bf{v2}}{\rm{,}}\,{\bf{w1}}} \right)},{\bf{a6}} = {\left( {{\bf{v2}},\,{\bf{w2}}} \right)},{\bf{a7}} = {\left( {{\bf{v1}}{\rm{,}}\,{\bf{t}}} \right)},{\bf{a8}} = {\left( {{\bf{w1}}{\rm{,}}\,{\bf{t}}} \right)},{\bf{a9}} = {\left( {{\bf{w2}},\,{\bf{t}}} \right)}}$. The maximum arc flow vector $\overline {\mathbf{f}}$ and the minimum arc travel time vector $\overline {\mathbf{t}}$ are given by (5-1):

$$\overline {\mathbf{f}} ^{\mathbf{T}} = \left( {{\mathbf{6}},\,{\mathbf{6}},\,{\mathbf{15}},\,{\mathbf{15}},\,{\mathbf{6}},\,{\mathbf{15}},\,{\mathbf{15}},\,{\mathbf{6}},\,{\mathbf{6}}} \right)\,{\text{and}}\,\overline {\mathbf{t}} ^{\mathbf{T}} = \left( {{\mathbf{5}},\,{\mathbf{5}},\,{\mathbf{10}},\,{\mathbf{1}},\,{\mathbf{5}},\,{\mathbf{1}},\,{\mathbf{10}},\,{\mathbf{5}},\,{\mathbf{5}}} \right)$$

(5-1)

The transpose of the arc-path incidence matrix A is given by (5-2).

$$A^T = \left( {\begin{array}{*{20}c}{\mathbf{1}}{\mathbf{0}}{\mathbf{0}}{\mathbf{0}}{\mathbf{0}}{\mathbf{0}}{\mathbf{1}}{\mathbf{0}}{\mathbf{0}} \\{\mathbf{1}}{\mathbf{0}}{\mathbf{0}}{\mathbf{1}}{\mathbf{0}}{\mathbf{0}}{\mathbf{0}}{\mathbf{1}}{\mathbf{0}} \\{\mathbf{0}}{\mathbf{1}}{\mathbf{0}}{\mathbf{0}}{\mathbf{1}}{\mathbf{0}}{\mathbf{0}}{\mathbf{1}}{\mathbf{0}} \\{\mathbf{0}}{\mathbf{1}}{\mathbf{0}}{\mathbf{0}}{\mathbf{0}}{\mathbf{1}}{\mathbf{0}}{\mathbf{0}}{\mathbf{1}} \\{\mathbf{0}}{\mathbf{0}}{\mathbf{1}}{\mathbf{0}}{\mathbf{0}}{\mathbf{0}}{\mathbf{0}}{\mathbf{0}}{\mathbf{1}} \\\end{array} } \right)$$

(5-2)

Now apply algorithm 4-6 to the network with P. Figure 13 summarizes the results of the algorithm.

Fig. 13

The summarized result of Algorithm 4-6 to the network of Fig. 12

• (Step 1) Solving problem (4-9) generates the solution as (5-3). That is, the optimal flows are 5 for path 1, 6 for path 3, 4 for path 5, and 0 for paths 2 and 4. The shortest travel time is 15 time units.

  $${\mathbf{t}}*^{\mathbf{T}} = \left( {{\mathbf{5}},\,{\mathbf{5}},\,{\mathbf{10}},\,{\mathbf{1}},\,{\mathbf{5}},\,{\mathbf{1}},\,{\mathbf{10}},\,{\mathbf{5}},\,{\mathbf{5}}} \right)$$

  (5-3a)

$${\mathbf{f}}*^{\mathbf{T}} = \left( {{\mathbf{5}},{\mathbf{6}},\,{\mathbf{4}},\,{\mathbf{0}},\,{\mathbf{6}},\,{\mathbf{0}},\,{\mathbf{5}},\,{\mathbf{6}},\,{\mathbf{4}}} \right)$$

(5-3b)

$${\mathbf{F}}{\text{*}}^{\mathbf{T}} = \left( {{\mathbf{5}},\,{\mathbf{0}},\,{\mathbf{6}},\,{\mathbf{0}},\,{\mathbf{4}}} \right)$$

(5-3c)

$${\mathbf{\Gamma }}* = {\mathbf{15}}.$$

(5-3d)

• (Step 2) After determining the shortest path in P to be either path 2 or 4, select path 2 (path 4) as P _min . Then T _min = 11 time units. Since T _min < Γ ^*, path 2 (path 4) is a Braess path.

As paths 2 and 4 have a smaller travel time than Γ ^*, they are Braess paths by theorem 4-7. Furthermore, a4 is a Braess arc since it is the only unused arc in Braess path 2, while a6 is similarly a Braess arc of Braess path 4. For confirmation, problem (2-3) is applied to the network. Firstly, the problem is applied to the network without a4 and a6, and then the problem is again applied to the network with a4 and a6. The optimal solution of problem (2-3) without arcs a4 and a6 is the same solution of Fig. 13 if the rows of paths 2 and 4 and the columns of a4 and a6 are deleted. Next, the optimal solution of problem (2-3) with arcs a4 and a6 is given by Fig. 14. Adding the arcs increased T ^* by 8 (from 15 to 23 time units). Hence, we can confirm that a4 and a6 are Braess arcs.

Fig. 14

The optimal solution of problem (2-3) with the network of Fig. 12

6 Conclusions and further research

In this paper we have developed a model capable of detecting the Braess paradox in stable dynamics models with general networks. Unlike user equilibrium models, the stable dynamics model introduced by Nesterov and de Palma (2003) does not require any arc travel time function. With only two basic ‘physical’ quantities, it can express well the congestion of transportation networks. In this study, we defined the Braess paradox in the stable dynamics model in terms of Braess path, Braess arc, Braess cross, and Braess combination.

We suggested a model for detecting the presence of any Braess path in a given network. In order to develop the model, we replaced assumption 2-1 with assumption 4-1, which no longer allowed the Wardrop Principle to be guaranteed, but avoided selfish routing. Our detection method was based on the relation that the Braess paradox under assumption 2-1 corresponds to an unused path with smaller travel time under assumption 4-1. We firstly developed a mathematical program providing an equilibrium solution satisfying assumption 4-1. Next, we found an unused path with a smaller time from the solution. We also applied the method to a network with 6 nodes and 9 arcs, which has the same topology as that of the network introduced by Roughgarden (2006).

In further research, we will develop a solution method for global optimization of problem (4-9). The objective function and all constraints except (4-9c) are linear. The constraint (4-9c) is quadratic, but not convex. One approach for global optimization is a penalty function method. If we send the constraints (4-9c) to the objective function by some penalty function, the problem will be a non-convex quadratic programming problem with linear constraints. Then we can apply a branch-bound technique via semidefinite programming relaxation, such as (Burer and Vandenbussche 2008), to the problem. In another research direction, we can consider a practical, iterative method with a local optimal solver. We also start with a simple P, rather than a full set of all feasible paths. Assume that problem (4-9) with simple P is solved by the local solver. Then, if all unused paths are longer than the shortest path given by the solution, there will be no Braess path. However, the unused path with smaller time may not be a Braess path since the solution is only locally optimal. Then we need to generate the next iteration and update P. Future research will focus on developing the method in greater detail. Although it cannot guarantee an efficient and exact solution for detecting a Braess path which is known to be NP-hard, it opens the possibility of applying various integer programming based methods.