# Boundedly Rational User Equilibrium with Restricted Unused Routes

Authors: Chao Sun; Menghui Li; Lin Cheng; Senlai Zhu; Zhaoming Chu
Journal: Discrete Dynamics in Nature and Society
 (2016)

---

## Abstract

A boundedly rational user equilibrium model with restricted unused routes (R-BRUE) considering the restrictions of both used route cost and unused route cost is proposed. The proposed model hypothesizes that for each OD pair no traveler can reduce his/her travel time by an indifference band by unilaterally changing route. Meanwhile, no route is unutilized if its travel time is lower than sum of indifference band and the shortest route cost. The largest and smallest used route sets are defined using mathematical expression. We also show that, with the increase of the indifference band, the largest and smallest used route sets will be augmented, and the critical values of indifference band to augment these two path sets are identified by solving the mathematical programs with equilibrium constraints. Based on the largest and smallest used route sets, the R-BRUE route set without paradoxical route is generated. The R-BRUE solution set can then be obtained by assigning all traffic demands to the corresponding generated route set. Various numerical examples are also provided to illustrate the essential ideas of the proposed model and structure of R-BRUE route flow solution set.


---

## Body

## 1. Introduction

Perfect rationality is widely used in studying traditional transportation network models in which traveler always chooses the shortest (i.e., least utility) route, such as user equilibrium (UE [1]) and stochastic user equilibrium (SUE [2]) traffic assignment models. However, travelers may not always choose shortest route due to (1) lack of perfect travel information; (2) incapability of obtaining the shortest route with the complex traffic situations; and (3) certain “inertia” in decision making. Therefore people do not always choose the route with the maximum utility. They tend to seek a satisfactory route instead.In the literature of evaluating habitual routes in route choice behavior, only 30% of respondents from Boston [3], 59% from Cambridge, Massachusetts [4], and 86.8% from Turin, Italy [5] chose the shortest routes. Based on GPS studies, Zhu [6] found that 90% of subjects in the Minneapolis-St. Paul region choose routes one-fifth longer than average commute time. All findings above revealed that people do not usually take the shortest routes and the used routes generally have higher costs than shortest ones.It is more practical that traveler is boundedly rational (BR); traveler will not change his/her route if his/her travel time is a little longer than the shortest route. A series of experiments were conducted to empirically validate bounded rationality [7–13]. The results showed that, in the repeated learning process, commuters would not change their routes unless the difference between preferred arrival time and actual arrival time exceeded a threshold. And boundedly rational route choice modeling observed from experiments provided a valid description of actual commuter daily behavior.Simon, in 1957 [14], first proposed the notion of bounded rationality. And in 1987 [7], Mahmassani and Chang introduced it to traffic modeling. Since then, bounded rationality has received considerable attention in various transportation models, such as traffic safety [15], transportation planning [16, 17], traffic policy making [18–20], traffic assignment, and network design [21–28]. All these studies indicated that traveler is boundedly rational in his/her decision-making process.Boundedly rational user equilibrium (BRUE) is a network state such that travelers can take any route whose travel time is within a threshold of the shortest route time [22, 23, 25–28]. Such a threshold is phrased by Mahmassani and Chang [7] as “indifference band.” In other words, no one can reduce his/her travel time by an indifference band by unilaterally changing his/her route. The indifference band is estimated from either laboratory experiment data or a behavioral study of road users (e.g., by surveys [7, 29]). By introducing indifference band for each OD pair, the BRUE relaxes UE assumption that travelers only take the shortest routes at equilibrium.However, unlike the conventional UE model, the traffic flow under BRUE may not utilize any shortest or least-cost route; in another word the unused route cost may be lower than the used one. For example, the route flows are 0, 5, and 7 for three different routes on one OD pair, and the travel times are 10, 12, and 13, respectively. If the indifference band is 3, the above route flow solution is a BRUE solution. From the behavioral point of view, one might question the plausibility of this that the least travel time route has no traffic on it. Therefore, to make the model become behavioral more defensible, not only the used route cost should be restricted, but also the unused route cost should be restricted.Uncertainties are unavoidable in transportation systems and make people become boundedly rational. Travelers do not know exactly the time that they arrive at the destination due to the travel time variability which is made by uncertainties. However, in many cases (such as going to work, having a meeting, and catching the train), travelers care more about arrive time than travel time; no one wants to be late; thus the largest and smallest route sets exist in travels’ trip process.This paper makes contributions in three major areas:(1) considering both the restrictions of used route cost and unused route cost in the route decision process, we present a boundedly rational user equilibrium model with restricted unused routes (R-BRUE). This new model hypothesizes that for each OD pair no traveler can reduce his/her travel time by an indifference band by unilaterally changing route. Meanwhile, no route is unutilized if its travel time is lower than sum of indifference band and the shortest route cost. (2) We propose the largest and smallest used route sets which can be used to generate the used route set of R-BRUE model. These two used route sets are defined as the union and intersection of all R-BRUE solution set patterns, respectively. And (3) we develop two mathematical programs (MP) with equilibrium constraint to solve the critical values which is used to augment the largest and smallest used route sets.The remainder of the paper is organized as follows. In Section2, ε-R-BRUE (ε denotes the indifference band) is defined and its mathematical formulation is established. In Section 3, the largest and smallest ε-used route sets are defined, and their properties are studied. In Section 4, ε-R-BRUE route set without paradoxical route is generated. In Section 5, ε-R-BRUE route flow set without paradoxical route is constructed, and some examples are presented to illustrate the essential ideas of proposed model and the structure of R-BRUE route flow solution set. Finally, some conclusions and future work are provided.


## 2. Definition ofε-R-BRUE and Mathematical Formulation

In this section, we proposeε-boundedly rational user equilibrium model with restricted unused routes (R-BRUE) and the mathematical formulation of proposed model.


### 2.1. Definition ofε-R-BRUE

Consider a transportation networkG=N,A, where N and A denote the sets of nodes and links, respectively. Let W denote the set of OD pairs for which travel demand qω is generated between OD pair ω∈W, and let fkω denote the traffic flow on route k∈Kω, where Kω is the set of routes connecting OD pair ω and all Kω constitute K. The feasible route flow set is to assign the traffic demand on the feasible routes: F≜f:f≥0,∑k∈Kωfkω=qω,∀ω∈W. Below is formal definition of ε-boundedly rational user equilibrium with restricted unused routes (R-BRUE).Definition 1.
ε-boundedly rational user equilibrium with restricted unused routes (ε-R-BRUE) is a network state such that the travel cost of all used route is less than or equal to the sum of given indifference band ε=εωω∈W≥0 and the shortest route cost; meanwhile, the travel cost of the unused route is greater than or equal to the sum of ε and the shortest route cost; that is,(1)fkω>0⟹Ckωf≤mini∈KωCiωf+εω,∀k∈Kω,ω∈W,fkω=0⟹Ckωf≥mini∈KωCiωf+εω,∀k∈Kω,ω∈W,where f is the vector form of traffic flow fkω:f=…,fkω,…T and Ckω· is the route cost function on route k between OD pair ω.We should point out that boundedly rational user equilibrium (BRUE) model only considersfkω>0⇒Ckωf≤mini∈KωCiωf+εω which do not take the cost of unused route into consideration. We first use fkω=0⇒Ckωf≥mini∈KωCiωf+εω to restrict the “irrational solutions.”Equation (1) gives a necessary condition judging whether a flow pattern is R-BRUE and is equivalent to the following condition:(2)Ckωf>mini∈KωCiωf+εω⟹fkω=0,Ckωf<mini∈KωCiωf+εω⟹fkω>0.In other words, a used route has lower cost than an unused one, which is the same as that in the UE (user equilibrium) setting. Whenεω=0 for each ω, the R-BRUE definition is reduced to the UE problem.Theorem 2.
Anyε-R-BRUE solution is also a ε-BRUE solution. ε-BRUE solution may not, however, necessarily fulfill ε-R-BRUE conditions.Proof.
letf be a route flow pattern to ε-R-BRUE model. Then, for fkω>0, Ckωf≤mini∈KωCiωf+εω hold for all k∈Kω and ω∈W; that is, fkω>0⇒Ckωf≤mini∈KωCiωf+εω, ∀k∈Kω, ω∈W, which satisfies ε-BRUE model.
For the converse situation, suppose that a flow allocation satisfiesε-BRUE conditions and in addition has an unused route which has a cost less than the sum of ε and the shortest route. Then ε-R-BRUE conditions are violated.Usuallyε-R-BRUE is nonunique. Denote a set containing all route flow patterns satisfying Definition 1 as ε-R-BRUE route flow solution set:(3)FR-BRUEε≜f∈F:fkω>0⟹Ckωf≤mini∈KωCiωf+εω,fkω=0⟹Ckωf≥mini∈KωCiωf+εω,∀k∈Kω,ω∈W.Theorem 3.
If the link cost function is continuous,ε-R-BRUE solution (ε≥0) is nonempty.Proof.
First, Patriksson [30] showed that, when the link cost function is continuous, UE solution exists. Let fUE∈FUE be one UE route flow pattern, and set f1≜fi:fi∈fUE,fi>0, f0≜fi+δ:fi∈fUE,fi=0,Ckωfi<mini∈KωCiωfUE+εω, where δ is a very small positive parameter. Let f=f0,f1, when ε≥0,(4)fkω>0⟹Ckωf<mini∈KωCiωf+εω≤mini∈KωCiωf+εω,fkω=0⟹Ckωf≥mini∈KωCiωf+εω,∀k∈Kω,ω∈W.So f is ε-R-BRUE solution (ε≥0); that is, f∈FR-BRUEε. Given the continuous link cost function, at least one ε-R-BRUE flow pattern exists, and therefore FR-BRUEε≠⌀.


### 2.2. R-BRUE Mathematical Formulation

We use slack variablesρkω to define R-BRUE mathematically. f is a R-BRUE distribution if and only if there exists πω whose physical meaning is the minimum route cost for every ω such that(5)Ckωf-πω-ρkω=0,∀k∈Kω,ω∈W,fkωεω-ρkω=0,ifεω≤ρkω,>0,o.w.,∀k∈Kω,ω∈W,∑k∈Kωfkω=qω,∀ω∈W,fkω≥0,∀k∈Kω,ω∈W,ρkω≥0,∀k∈Kω,ω∈W,where qω is the traffic demand between OD pair ω. Note that when ε=0 for all ω, (5) reduces to 0≤fkω⊥Ckωf-πω≥0, ∑k∈Kωfkω=qω which is the conventional UE conditions.


## 2.1. Definition ofε-R-BRUE

Consider a transportation networkG=N,A, where N and A denote the sets of nodes and links, respectively. Let W denote the set of OD pairs for which travel demand qω is generated between OD pair ω∈W, and let fkω denote the traffic flow on route k∈Kω, where Kω is the set of routes connecting OD pair ω and all Kω constitute K. The feasible route flow set is to assign the traffic demand on the feasible routes: F≜f:f≥0,∑k∈Kωfkω=qω,∀ω∈W. Below is formal definition of ε-boundedly rational user equilibrium with restricted unused routes (R-BRUE).Definition 1.
ε-boundedly rational user equilibrium with restricted unused routes (ε-R-BRUE) is a network state such that the travel cost of all used route is less than or equal to the sum of given indifference band ε=εωω∈W≥0 and the shortest route cost; meanwhile, the travel cost of the unused route is greater than or equal to the sum of ε and the shortest route cost; that is,(1)fkω>0⟹Ckωf≤mini∈KωCiωf+εω,∀k∈Kω,ω∈W,fkω=0⟹Ckωf≥mini∈KωCiωf+εω,∀k∈Kω,ω∈W,where f is the vector form of traffic flow fkω:f=…,fkω,…T and Ckω· is the route cost function on route k between OD pair ω.We should point out that boundedly rational user equilibrium (BRUE) model only considersfkω>0⇒Ckωf≤mini∈KωCiωf+εω which do not take the cost of unused route into consideration. We first use fkω=0⇒Ckωf≥mini∈KωCiωf+εω to restrict the “irrational solutions.”Equation (1) gives a necessary condition judging whether a flow pattern is R-BRUE and is equivalent to the following condition:(2)Ckωf>mini∈KωCiωf+εω⟹fkω=0,Ckωf<mini∈KωCiωf+εω⟹fkω>0.In other words, a used route has lower cost than an unused one, which is the same as that in the UE (user equilibrium) setting. Whenεω=0 for each ω, the R-BRUE definition is reduced to the UE problem.Theorem 2.
Anyε-R-BRUE solution is also a ε-BRUE solution. ε-BRUE solution may not, however, necessarily fulfill ε-R-BRUE conditions.Proof.
letf be a route flow pattern to ε-R-BRUE model. Then, for fkω>0, Ckωf≤mini∈KωCiωf+εω hold for all k∈Kω and ω∈W; that is, fkω>0⇒Ckωf≤mini∈KωCiωf+εω, ∀k∈Kω, ω∈W, which satisfies ε-BRUE model.
For the converse situation, suppose that a flow allocation satisfiesε-BRUE conditions and in addition has an unused route which has a cost less than the sum of ε and the shortest route. Then ε-R-BRUE conditions are violated.Usuallyε-R-BRUE is nonunique. Denote a set containing all route flow patterns satisfying Definition 1 as ε-R-BRUE route flow solution set:(3)FR-BRUEε≜f∈F:fkω>0⟹Ckωf≤mini∈KωCiωf+εω,fkω=0⟹Ckωf≥mini∈KωCiωf+εω,∀k∈Kω,ω∈W.Theorem 3.
If the link cost function is continuous,ε-R-BRUE solution (ε≥0) is nonempty.Proof.
First, Patriksson [30] showed that, when the link cost function is continuous, UE solution exists. Let fUE∈FUE be one UE route flow pattern, and set f1≜fi:fi∈fUE,fi>0, f0≜fi+δ:fi∈fUE,fi=0,Ckωfi<mini∈KωCiωfUE+εω, where δ is a very small positive parameter. Let f=f0,f1, when ε≥0,(4)fkω>0⟹Ckωf<mini∈KωCiωf+εω≤mini∈KωCiωf+εω,fkω=0⟹Ckωf≥mini∈KωCiωf+εω,∀k∈Kω,ω∈W.So f is ε-R-BRUE solution (ε≥0); that is, f∈FR-BRUEε. Given the continuous link cost function, at least one ε-R-BRUE flow pattern exists, and therefore FR-BRUEε≠⌀.


## 2.2. R-BRUE Mathematical Formulation

We use slack variablesρkω to define R-BRUE mathematically. f is a R-BRUE distribution if and only if there exists πω whose physical meaning is the minimum route cost for every ω such that(5)Ckωf-πω-ρkω=0,∀k∈Kω,ω∈W,fkωεω-ρkω=0,ifεω≤ρkω,>0,o.w.,∀k∈Kω,ω∈W,∑k∈Kωfkω=qω,∀ω∈W,fkω≥0,∀k∈Kω,ω∈W,ρkω≥0,∀k∈Kω,ω∈W,where qω is the traffic demand between OD pair ω. Note that when ε=0 for all ω, (5) reduces to 0≤fkω⊥Ckωf-πω≥0, ∑k∈Kωfkω=qω which is the conventional UE conditions.


## 3. Largest and Smallestε-Used Route Sets

In this section, we give the definition of the largest and smallestε-used route sets, and we also discuss the properties of two proposed route sets.


### 3.1. Definitions

Here we give three definitions of used route set, largestε-used route set (ε-URS) and smallest ε-URS of ε-R-BRUE model as follows.Definition 4.
Givenε-R-BRUE route pattern f∈FR-BRUEε, the used route carries flow, while its travel cost is within the shortest cost plus the indifference band; that is,(6)aεf=k∈Kω:fk>0,Ckωf≤mini∈KωCiωf+εω,∀ω∈W.Definition 5.
A largestε-URS contains all used routes for every flow pattern in ε-R-BRUE flow set, mathematically:(7)Klε=⋃f∈FR-BRUEεaεf.Definition 6.
A smallestε-URS contains the used routes which all flow patterns in ε-R-BRUE flow set have, mathematically:(8)Ksε=⋂f∈FR-BRUEεaεf.


### 3.2. Monotonically Nondecreasing Largestε-URS

In the following, we will discuss the impact of the value ofε on the size of the largest ε-URS.Theorem 7.
If0≤ε<ε′, then Klε⊆Klε′, where Klε is defined in (7).Proof.
Letfε∈FM-BRUEε be one ε-R-BRUE route flow pattern, and set f1≜fi:fi∈fε,fi>0, f0≜fi+δ:fi∈fε,fi=0,Ckωfi<mini∈KωCiωfε+ε′, where δ is a very small positive parameter. Let fε′=f0,f1; then(9)fkω>0⟹Ckωf<mini∈KωCiωf+εω′≤mini∈KωCiωf+εω′,fkω=0⟹Ckωf≥mini∈KωCiωf+εω′,∀k∈Kω,ω∈W.So fε′ is ε′-R-BRUE solution, and aεf⊆aε′f. Based on (7), we can get that Klε⊆Klε′.


### 3.3. Paradoxical Route and Property of Smallestε-URS

We will give the definition of paradoxical route first.Definition 8.
With the increasing of OD demand, the traffic flow on routep first increases and then decreases at the UE state. And the route p is defined as a paradoxical route.This phenomenon contradicts our intuition. Following that, we use an example to illustrate this paradox.The network topology of the test network, link, and traffic demand characteristics are depicted in Figure1. The network consists of 4 nodes, 5 links, and 1 OD pair. Red curves on the right indicate 3 routes.Figure 1
Test network and routes characteristics.The equilibrium route flowf1 by varying the traffic demand q from zero to infinity is shown in Figure 2. When the traffic demand is lower than 4, all the travelers pick route 1; and f1 is increasing with the increasing of demand. While q reached to 4, f1 is decreasing with the increasing of q. And when the demand reaches to 24, the flow on route 1 becomes 0. Based on Definition 8, we can get that route 1 is the paradoxical route.Figure 2
The UE traffic flow of route 1 under different demand.When0≤ε<ε′, Ksε⊆Ksε′, where the network contains paradoxical route, monotonically nondecreasing property of smallest ε-URS may not be satisfied due to exiting paradoxical route in the network. Consider the test network in Figure 3 which consists of 4 nodes, 6 links, and 1 OD pair. The link travel time functions and traffic demand are reported in Figure 3. Red curves on the right indicate 4 routes.Figure 3
Test network and routes characteristics.Solving the UE whereε=0 for the R-BRUE, we have f1=0.25, f2=11.25, f3=11.25, and f4=9.25. Therefore, the smallest ε-URS is Ks0=1,2,3,4. When ε=48, f1=0, f2=15, f3=15, and f4=2, the travel time is C1=60, C2=57, C3=57, and C4=10. The minimum OD travel time is 10 and all the utilized routes have travel times of no more than 10 + 48 = 58. Therefore, the route flow pattern is a valid R-BRUE flow. However, the smallest ε-URS which is Ks48=2,3,4 does not satisfy the monotonically nondecreasing property.Theorem 9 (monotonically nondecreasing smallestε-URS without paradoxical route).
If0≤ε<ε′, then Ksε⊆Ksε′ for a network without paradoxical route, where Ksε is defined in (8).Proof.
Assume that there exist two bandsε and ε′ which satisfy that 0≤ε<ε′ such that Ksε⊄Ksε′. Then, there must exist a route k such that k∈Ksε and k∉Ksε′. In another word, fkε≥0 for all ε-R-BRUE route flow patterns, and fkε′ can be equal to 0 for some ε′-R-BRUE route flow patterns. And this contradicts the assumption that the network has no paradoxical route.Whenε varies from zero to infinity, the minimum number of routes the largest ε-URS and smallest ε-URS without paradoxical route contains is the UE shortest routes when ε=0; that is, Kl0=Ks0≜KUE. The maximum number of routes the largest ε-URS and smallest ε-URS without paradoxical route contains is all feasible routes, meaning all feasible routes will be utilized if the indifference band is too large. Then we have KUE⊆Klε⊆K and KUE⊆Ksε⊆K.Givenε, the largest ε-URS (defined in (7)) is a set of all used routes under ε-R-BRUE set. Andthe smallest ε-URS (defined in (8)) is a set of the used routes which must have traffic flows under all ε-R-BRUE set. It is possible that some used routes for one ε-R-BRUE flow pattern are not used for other flow patterns and vice versa. This necessitates the exploration of the interior structure of ε-R-BRUE route set. Theorems 7 and 9 provide us with one approach of analyzing the structure of ε-R-BRUE without paradoxical route by varying values of ε.


## 3.1. Definitions

Here we give three definitions of used route set, largestε-used route set (ε-URS) and smallest ε-URS of ε-R-BRUE model as follows.Definition 4.
Givenε-R-BRUE route pattern f∈FR-BRUEε, the used route carries flow, while its travel cost is within the shortest cost plus the indifference band; that is,(6)aεf=k∈Kω:fk>0,Ckωf≤mini∈KωCiωf+εω,∀ω∈W.Definition 5.
A largestε-URS contains all used routes for every flow pattern in ε-R-BRUE flow set, mathematically:(7)Klε=⋃f∈FR-BRUEεaεf.Definition 6.
A smallestε-URS contains the used routes which all flow patterns in ε-R-BRUE flow set have, mathematically:(8)Ksε=⋂f∈FR-BRUEεaεf.


## 3.2. Monotonically Nondecreasing Largestε-URS

In the following, we will discuss the impact of the value ofε on the size of the largest ε-URS.Theorem 7.
If0≤ε<ε′, then Klε⊆Klε′, where Klε is defined in (7).Proof.
Letfε∈FM-BRUEε be one ε-R-BRUE route flow pattern, and set f1≜fi:fi∈fε,fi>0, f0≜fi+δ:fi∈fε,fi=0,Ckωfi<mini∈KωCiωfε+ε′, where δ is a very small positive parameter. Let fε′=f0,f1; then(9)fkω>0⟹Ckωf<mini∈KωCiωf+εω′≤mini∈KωCiωf+εω′,fkω=0⟹Ckωf≥mini∈KωCiωf+εω′,∀k∈Kω,ω∈W.So fε′ is ε′-R-BRUE solution, and aεf⊆aε′f. Based on (7), we can get that Klε⊆Klε′.


## 3.3. Paradoxical Route and Property of Smallestε-URS

We will give the definition of paradoxical route first.Definition 8.
With the increasing of OD demand, the traffic flow on routep first increases and then decreases at the UE state. And the route p is defined as a paradoxical route.This phenomenon contradicts our intuition. Following that, we use an example to illustrate this paradox.The network topology of the test network, link, and traffic demand characteristics are depicted in Figure1. The network consists of 4 nodes, 5 links, and 1 OD pair. Red curves on the right indicate 3 routes.Figure 1
Test network and routes characteristics.The equilibrium route flowf1 by varying the traffic demand q from zero to infinity is shown in Figure 2. When the traffic demand is lower than 4, all the travelers pick route 1; and f1 is increasing with the increasing of demand. While q reached to 4, f1 is decreasing with the increasing of q. And when the demand reaches to 24, the flow on route 1 becomes 0. Based on Definition 8, we can get that route 1 is the paradoxical route.Figure 2
The UE traffic flow of route 1 under different demand.When0≤ε<ε′, Ksε⊆Ksε′, where the network contains paradoxical route, monotonically nondecreasing property of smallest ε-URS may not be satisfied due to exiting paradoxical route in the network. Consider the test network in Figure 3 which consists of 4 nodes, 6 links, and 1 OD pair. The link travel time functions and traffic demand are reported in Figure 3. Red curves on the right indicate 4 routes.Figure 3
Test network and routes characteristics.Solving the UE whereε=0 for the R-BRUE, we have f1=0.25, f2=11.25, f3=11.25, and f4=9.25. Therefore, the smallest ε-URS is Ks0=1,2,3,4. When ε=48, f1=0, f2=15, f3=15, and f4=2, the travel time is C1=60, C2=57, C3=57, and C4=10. The minimum OD travel time is 10 and all the utilized routes have travel times of no more than 10 + 48 = 58. Therefore, the route flow pattern is a valid R-BRUE flow. However, the smallest ε-URS which is Ks48=2,3,4 does not satisfy the monotonically nondecreasing property.Theorem 9 (monotonically nondecreasing smallestε-URS without paradoxical route).
If0≤ε<ε′, then Ksε⊆Ksε′ for a network without paradoxical route, where Ksε is defined in (8).Proof.
Assume that there exist two bandsε and ε′ which satisfy that 0≤ε<ε′ such that Ksε⊄Ksε′. Then, there must exist a route k such that k∈Ksε and k∉Ksε′. In another word, fkε≥0 for all ε-R-BRUE route flow patterns, and fkε′ can be equal to 0 for some ε′-R-BRUE route flow patterns. And this contradicts the assumption that the network has no paradoxical route.Whenε varies from zero to infinity, the minimum number of routes the largest ε-URS and smallest ε-URS without paradoxical route contains is the UE shortest routes when ε=0; that is, Kl0=Ks0≜KUE. The maximum number of routes the largest ε-URS and smallest ε-URS without paradoxical route contains is all feasible routes, meaning all feasible routes will be utilized if the indifference band is too large. Then we have KUE⊆Klε⊆K and KUE⊆Ksε⊆K.Givenε, the largest ε-URS (defined in (7)) is a set of all used routes under ε-R-BRUE set. Andthe smallest ε-URS (defined in (8)) is a set of the used routes which must have traffic flows under all ε-R-BRUE set. It is possible that some used routes for one ε-R-BRUE flow pattern are not used for other flow patterns and vice versa. This necessitates the exploration of the interior structure of ε-R-BRUE route set. Theorems 7 and 9 provide us with one approach of analyzing the structure of ε-R-BRUE without paradoxical route by varying values of ε.


## 4. Generation ofε-R-BRUE Route Set without Paradoxical Route

The route set is finite, whileε is treated as a continuous parameter for the time being. Starting with the UE route set when ε=0, provided the network topology and the link cost functions, UE can be determined by some established algorithms, for example, simplicial decomposition with disaggregated (DSD) algorithm [31], gradient projection algorithm [32], or origin-based algorithm [33]. According to Theorems 7 and 9, when ε is gradually increased, more routes will be included in the largest and smallest ε-URS, and we should be able to identify those used routes one by one, until all alternative routes are included. This offers the theoretical foundation for deriving different combinations of used routes by varying ε subsequently.


### 4.1. Definition of Critical Points inε-R-BRUE

It is assumed that there aren alternative routes for OD pair ω; that is, K=1,…,n and K=n, where K is the cardinality of set K. Among these n routes, there are r shortest routes at the UE; that is, KUE=1,…,r and KUE=r≤n. Below are the definitions of critical points of the largest and smallest ε-URS in R-BRUE without paradoxical route.Definition 10.
The largest/smallestε-URS will remain the same until ε reaches a special value, and we define this value as critical points of the largest/smallest ε-URS for OD pair Omega; that is,(10)εl,1∗≜infε>0KUE⊂Klε;⋮εl,j∗≜infε>0Klεl,j-1∗⊂Klε,⋮εl,J∗≜infε>0Klε=K.(11)εs,1∗≜infε>0KUE⊂Ksε;⋮εs,i∗≜infε>0Ksεs,i-1∗⊂Ksε;⋮εs,I∗≜infε>0Ksε=K,where j=1,…,J, i=1,…,I are the unique sequences of finite critical points εl∗ and εs∗, with εl,0∗=εs,0∗=0, εl,J+1∗=εs,I+1∗=∞.We give the physical meaning ofεl∗ and εs∗. A “newly added route” of the largest ε-URS is defined as the route which is unavailable under εl,j-1∗ but available when ε=εl,j∗. And a “newly added route” of the smallest ε-URS is defined as the route which is available under εs,z∗:∀z≥i for all route flow patterns, but unavailable under εs,i-1∗ for some route flow patterns. We can define their “newly added route” as rj∗≜k∈K:k∈Klεl,j∗,k∉Klεl,j-1∗ and ti∗≜k∈K:k∈Ksεs,i∗,k∉Ksεs,i-1∗, respectively. We should notice that the number of “newly added routes” may be two or more at the same time.We use Figure4 to more intuitively illustrate the definition of critical points of the largest and smallest ε-URS in R-BRUE without paradoxical route.Figure 4
Monotonically nondecreasing property of critical points.Clearly, from Figure4, we can observe that the largest and smallest ε-URS can be described as Klε=KUE,Klε1∗,…,KlεP∗ and Ksε=KUE,Ksε1∗,…,KsεQ∗ with a fixed indifference band ε, where εl,M∗≤ε<εl,M+1∗, εs,N∗≤ε<εs,N+1∗, P=min⁡M,J, and =min⁡N,I.


### 4.2.ε-R-BRUE Route Set without Paradoxical Route for One OD Pair

Definition10 says that the largest and smallest ε-URS in R-BRUE without paradoxical route includes more routes when ε increases to some critical values. Thus, the mathematical programs (MP) with equilibrium constraint can be developed to solve these critical values in largest and smallest ε-URS. Below is the MP equation for calculating largest ε-URS:(12)minεl,j(13a)s.t.Ckf-π-ρk=0,∀k∈K,(13b)fkεl,j-ρk=0,ifεl,j≤ρk,>0,o.w.,∀k∈K,(13c)∑k∈Kfk=q,(13d)fk≥0,∀k∈K,(13e)ρk≥0,∀k∈K,(13f)∑j∈Klεl,j-1∗fj<q,where j=1,…,J. Equations (13a)–(13e) are to guarantee the route flow pattern is a feasible R-BRUE; (13f) tries to push a small amount of flow from the largest used route set Klεl,j-1∗ to some newly largest used route if εl is increased a little bit. When (13a), (13b), (13c), (13d), (13e), and (13f) are solved, optimal solutions f∗,εl,j∗,π∗ will be obtained. And the newly added route rj∗ can be derived from the traffic flow f∗.For any routei∈K, following MP equation is used to get the smallest ε-URS:(14)maxεs,i(15a)s.t.Ckf-π-ρk=0,∀k∈K,(15b)fkεs,i-ρk=0,ifεs,i≤ρk,>0,o.w.,∀k∈K,(15c)∑k∈Kfk=q,(15d)fk≥0,∀k∈K,(15e)ρk≥0,∀k∈K,(15f)fi=0.Equations (15a)–(15e) are to guarantee the route flow pattern is a feasible R-BRUE; and (15f) is to insure that no traffic flow travels on route i. When εs,i for all routes are worked out, εs,i are sorted by their size. Then we get the form of εs,i as (11). When (15a), (15b), (15c), (15d), (15e), and (15f) are solved, optimal solutions f∗,εs,i∗,π∗ will be obtained. And the newly added route ti∗ can be derived from the traffic flow f∗.Equations (13b), (13f), and (15b) are inequalities without equal sign. A small positive parameter δ (such as 0.01) is introduced to deal with this problem. And (13b), (13f), and (15b) are replaced by (16)fkεl,j-ρk=0,ifεl,j≤ρk,≥δ,o.w.,-∑j∈Klεl,j-1∗fj≥δ-1q,fkεs,i-ρk=0,ifεs,i≤ρk,≥δ,o.w.Equations (13a), (13b), (13c), (13d), (13e), (13f), (15a), (15b), (15c), (15d), (15e), and (15f) can be solved by GAMS software [25, 34].


### 4.3. Instance ofε-R-BRUE Route Set without Paradoxical Route

The network topology of the test network, travel time functions, and traffic demand are depicted in Figure5. The network consists of 3 nodes, 5 links, and 1 OD pair. Red curves on the right indicate 4 routes. The UE is f1=10, f2=10, f3=0, and f4=0.Figure 5
Test network and routes characteristics.Solving (13a), (13b), (13c), (13d), (13e), (13f), (15a), (15b), (15c), (15d), (15e), and (15f), we have the largest critical values εl,0∗=0, εl,1∗=1, εl,2∗=1.1, and εl,3∗=∞ and the smallest critical values εs,0∗=0, εs,1∗=2.85, εs,2∗=4.9, and εs,3∗=∞. There are three cases for the largest ε-URS:(1)
0≤ε<1:Klε=1,2, and when ε=0, f=10,10,0,0, C=10,10,10,11.1.(2)
1≤ε<1.1:Klε=1,2,3, and when ε=1, f=10,10,0+,0, C=10,10,10,11.1.(3)
ε≥1.1:Klε=1,2,3,4, and when ε=1.1, f=10,10,0+,0+, C=10,10,10,11.1.And there are three cases for the smallestε-URS: (1)
0≤ε<2.85:Ksε=1,2, and when ε=0, f=10,10,0,0, C=10,10,10,11.1.(2)
2.85≤ε<4.9:Ksε=1,2,4, and when ε=2.85, f=11.1,7.6,1.3,0+, C=11.1,8.25,11.1,11.1.(3)
ε≥4.9:Ksε=1,2,3,4, and when ε=4.9, f=7.1,12,0+,0.9, C=7.1,12,12,12.All largest and smallestε-URS are also illustrated in Figure 6. For route 3, we can see that when the critical value ε reaches 1, route 3 will join in the used route set for some route flow patterns; and when ε reaches 4.9, route 3 will be the used route for all route flow patterns. In other words, the yellow bar in Figure 6 means the route is either the used route or unused route in different route flow patterns, while the blue bar represents the route must be a used route for all route flow patterns. If ε is calibrated from empirical data as 3, then Kl3=1,2,3,4, Ks3=1,2,4. Therefore, routes 1, 2, and 4 must be the used routes, and route 3 may carry traffic flow or not. The used route can be described as K3=1,2,4,1,2,3,4.Figure 6
ε-URS under all the critical points.


### 4.4.ε-R-BRUE Route Set without Paradoxical Route for Multiple OD Pairs

For a network with totalW OD pairs, let εl,j∗ω and εs,i∗ω be the largest and smallest critical points for OD pair ω∈W, j=0,1,…,Jω, i=0,1,…,Iω, respectively. Then, εl,j∗≜εl,j∗ω and εs,i∗≜εs,i∗ω are the sets of largest and smallest critical points for all OD pairs.For one OD pairv∈W, we also can use (13a), (13b), (13c), (13d), (13e), (13f), (15a), (15b), (15c), (15d), (15e), and (15f) to solve the largest and smallest critical points. The only difference is route costs need the information of route flows across all OD pairs. And route flows fω, ω∈W, ω≠v are parameters when calculating the critical points of v. Then, we modify (13a), (13b), (13c), (13d), (13e), (13f), (15a), (15b), (15c), (15d), (15e), and (15f) as follows:(17)minεl,jvs.t.Ckvf-πv-ρkv=0,∀k∈Kv,fkvεl,jv-ρkv=0,ifεl,jv≤ρkv,>0,o.w.,∀k∈Kω,∑k∈Kωfkω=qω,∀ω∈W,fkv≥0,∀k∈Kv,ρkv≥0,∀k∈Kv,∑j∈Klεl,j-1∗vfjv<qv,maxεs,ivs.t.Ckvf-πv-ρkv=0,∀k∈Kv,fkvεs,iv-ρkv=0,ifεs,iv≤ρkv,>0,o.w.,∀k∈Kω,∑k∈Kωfkω=qω,∀ω∈W,fkv≥0,∀k∈Kv,ρkv≥0,∀k∈Kv,fiv=0.Then the same approach can be used to generate theε-R-BRUE route set without paradoxical route for multiple OD pairs.By far we have proposed how to solveε-R-BRUE route set without paradoxical route for both single OD pair and multiple OD pairs. The following will discuss the methodology of constructing ε-R-BRUE route flow set without paradoxical route.


## 4.1. Definition of Critical Points inε-R-BRUE

It is assumed that there aren alternative routes for OD pair ω; that is, K=1,…,n and K=n, where K is the cardinality of set K. Among these n routes, there are r shortest routes at the UE; that is, KUE=1,…,r and KUE=r≤n. Below are the definitions of critical points of the largest and smallest ε-URS in R-BRUE without paradoxical route.Definition 10.
The largest/smallestε-URS will remain the same until ε reaches a special value, and we define this value as critical points of the largest/smallest ε-URS for OD pair Omega; that is,(10)εl,1∗≜infε>0KUE⊂Klε;⋮εl,j∗≜infε>0Klεl,j-1∗⊂Klε,⋮εl,J∗≜infε>0Klε=K.(11)εs,1∗≜infε>0KUE⊂Ksε;⋮εs,i∗≜infε>0Ksεs,i-1∗⊂Ksε;⋮εs,I∗≜infε>0Ksε=K,where j=1,…,J, i=1,…,I are the unique sequences of finite critical points εl∗ and εs∗, with εl,0∗=εs,0∗=0, εl,J+1∗=εs,I+1∗=∞.We give the physical meaning ofεl∗ and εs∗. A “newly added route” of the largest ε-URS is defined as the route which is unavailable under εl,j-1∗ but available when ε=εl,j∗. And a “newly added route” of the smallest ε-URS is defined as the route which is available under εs,z∗:∀z≥i for all route flow patterns, but unavailable under εs,i-1∗ for some route flow patterns. We can define their “newly added route” as rj∗≜k∈K:k∈Klεl,j∗,k∉Klεl,j-1∗ and ti∗≜k∈K:k∈Ksεs,i∗,k∉Ksεs,i-1∗, respectively. We should notice that the number of “newly added routes” may be two or more at the same time.We use Figure4 to more intuitively illustrate the definition of critical points of the largest and smallest ε-URS in R-BRUE without paradoxical route.Figure 4
Monotonically nondecreasing property of critical points.Clearly, from Figure4, we can observe that the largest and smallest ε-URS can be described as Klε=KUE,Klε1∗,…,KlεP∗ and Ksε=KUE,Ksε1∗,…,KsεQ∗ with a fixed indifference band ε, where εl,M∗≤ε<εl,M+1∗, εs,N∗≤ε<εs,N+1∗, P=min⁡M,J, and =min⁡N,I.


## 4.2.ε-R-BRUE Route Set without Paradoxical Route for One OD Pair

Definition10 says that the largest and smallest ε-URS in R-BRUE without paradoxical route includes more routes when ε increases to some critical values. Thus, the mathematical programs (MP) with equilibrium constraint can be developed to solve these critical values in largest and smallest ε-URS. Below is the MP equation for calculating largest ε-URS:(12)minεl,j(13a)s.t.Ckf-π-ρk=0,∀k∈K,(13b)fkεl,j-ρk=0,ifεl,j≤ρk,>0,o.w.,∀k∈K,(13c)∑k∈Kfk=q,(13d)fk≥0,∀k∈K,(13e)ρk≥0,∀k∈K,(13f)∑j∈Klεl,j-1∗fj<q,where j=1,…,J. Equations (13a)–(13e) are to guarantee the route flow pattern is a feasible R-BRUE; (13f) tries to push a small amount of flow from the largest used route set Klεl,j-1∗ to some newly largest used route if εl is increased a little bit. When (13a), (13b), (13c), (13d), (13e), and (13f) are solved, optimal solutions f∗,εl,j∗,π∗ will be obtained. And the newly added route rj∗ can be derived from the traffic flow f∗.For any routei∈K, following MP equation is used to get the smallest ε-URS:(14)maxεs,i(15a)s.t.Ckf-π-ρk=0,∀k∈K,(15b)fkεs,i-ρk=0,ifεs,i≤ρk,>0,o.w.,∀k∈K,(15c)∑k∈Kfk=q,(15d)fk≥0,∀k∈K,(15e)ρk≥0,∀k∈K,(15f)fi=0.Equations (15a)–(15e) are to guarantee the route flow pattern is a feasible R-BRUE; and (15f) is to insure that no traffic flow travels on route i. When εs,i for all routes are worked out, εs,i are sorted by their size. Then we get the form of εs,i as (11). When (15a), (15b), (15c), (15d), (15e), and (15f) are solved, optimal solutions f∗,εs,i∗,π∗ will be obtained. And the newly added route ti∗ can be derived from the traffic flow f∗.Equations (13b), (13f), and (15b) are inequalities without equal sign. A small positive parameter δ (such as 0.01) is introduced to deal with this problem. And (13b), (13f), and (15b) are replaced by (16)fkεl,j-ρk=0,ifεl,j≤ρk,≥δ,o.w.,-∑j∈Klεl,j-1∗fj≥δ-1q,fkεs,i-ρk=0,ifεs,i≤ρk,≥δ,o.w.Equations (13a), (13b), (13c), (13d), (13e), (13f), (15a), (15b), (15c), (15d), (15e), and (15f) can be solved by GAMS software [25, 34].


## 4.3. Instance ofε-R-BRUE Route Set without Paradoxical Route

The network topology of the test network, travel time functions, and traffic demand are depicted in Figure5. The network consists of 3 nodes, 5 links, and 1 OD pair. Red curves on the right indicate 4 routes. The UE is f1=10, f2=10, f3=0, and f4=0.Figure 5
Test network and routes characteristics.Solving (13a), (13b), (13c), (13d), (13e), (13f), (15a), (15b), (15c), (15d), (15e), and (15f), we have the largest critical values εl,0∗=0, εl,1∗=1, εl,2∗=1.1, and εl,3∗=∞ and the smallest critical values εs,0∗=0, εs,1∗=2.85, εs,2∗=4.9, and εs,3∗=∞. There are three cases for the largest ε-URS:(1)
0≤ε<1:Klε=1,2, and when ε=0, f=10,10,0,0, C=10,10,10,11.1.(2)
1≤ε<1.1:Klε=1,2,3, and when ε=1, f=10,10,0+,0, C=10,10,10,11.1.(3)
ε≥1.1:Klε=1,2,3,4, and when ε=1.1, f=10,10,0+,0+, C=10,10,10,11.1.And there are three cases for the smallestε-URS: (1)
0≤ε<2.85:Ksε=1,2, and when ε=0, f=10,10,0,0, C=10,10,10,11.1.(2)
2.85≤ε<4.9:Ksε=1,2,4, and when ε=2.85, f=11.1,7.6,1.3,0+, C=11.1,8.25,11.1,11.1.(3)
ε≥4.9:Ksε=1,2,3,4, and when ε=4.9, f=7.1,12,0+,0.9, C=7.1,12,12,12.All largest and smallestε-URS are also illustrated in Figure 6. For route 3, we can see that when the critical value ε reaches 1, route 3 will join in the used route set for some route flow patterns; and when ε reaches 4.9, route 3 will be the used route for all route flow patterns. In other words, the yellow bar in Figure 6 means the route is either the used route or unused route in different route flow patterns, while the blue bar represents the route must be a used route for all route flow patterns. If ε is calibrated from empirical data as 3, then Kl3=1,2,3,4, Ks3=1,2,4. Therefore, routes 1, 2, and 4 must be the used routes, and route 3 may carry traffic flow or not. The used route can be described as K3=1,2,4,1,2,3,4.Figure 6
ε-URS under all the critical points.


## 4.4.ε-R-BRUE Route Set without Paradoxical Route for Multiple OD Pairs

For a network with totalW OD pairs, let εl,j∗ω and εs,i∗ω be the largest and smallest critical points for OD pair ω∈W, j=0,1,…,Jω, i=0,1,…,Iω, respectively. Then, εl,j∗≜εl,j∗ω and εs,i∗≜εs,i∗ω are the sets of largest and smallest critical points for all OD pairs.For one OD pairv∈W, we also can use (13a), (13b), (13c), (13d), (13e), (13f), (15a), (15b), (15c), (15d), (15e), and (15f) to solve the largest and smallest critical points. The only difference is route costs need the information of route flows across all OD pairs. And route flows fω, ω∈W, ω≠v are parameters when calculating the critical points of v. Then, we modify (13a), (13b), (13c), (13d), (13e), (13f), (15a), (15b), (15c), (15d), (15e), and (15f) as follows:(17)minεl,jvs.t.Ckvf-πv-ρkv=0,∀k∈Kv,fkvεl,jv-ρkv=0,ifεl,jv≤ρkv,>0,o.w.,∀k∈Kω,∑k∈Kωfkω=qω,∀ω∈W,fkv≥0,∀k∈Kv,ρkv≥0,∀k∈Kv,∑j∈Klεl,j-1∗vfjv<qv,maxεs,ivs.t.Ckvf-πv-ρkv=0,∀k∈Kv,fkvεs,iv-ρkv=0,ifεs,iv≤ρkv,>0,o.w.,∀k∈Kω,∑k∈Kωfkω=qω,∀ω∈W,fkv≥0,∀k∈Kv,ρkv≥0,∀k∈Kv,fiv=0.Then the same approach can be used to generate theε-R-BRUE route set without paradoxical route for multiple OD pairs.By far we have proposed how to solveε-R-BRUE route set without paradoxical route for both single OD pair and multiple OD pairs. The following will discuss the methodology of constructing ε-R-BRUE route flow set without paradoxical route.


## 5. Construction ofε-R-BRUE Route Flow Set without Paradoxical Route

We have already analyzed the interior structure ofε-R-BRUE route set without paradoxical route last section. As the indifference band gradually increases, more routes will begin to carry flows (the largest R-BRUE route set), and more routes must carry flows (the smallest R-BRUE route set). Based on this characteristic, we decompose ε-R-BRUE route set into small subsets which are easier to study.


### 5.1.ε-R-BRUE Flow Set without Paradoxical Route for One OD Pair

Define a sequence of setsFkε, k=0,…,M-N, where M and N are the cardinalities of largest and smallest ε-URS. Then we assign all the traffic demands as follows:(18)F0ε≜f∈F:∀i1,i2∈Ksε:fi1,fi2>0,Ci1-Ci2≤ε,∑fi=q;∀j∈Klε∖i:fj=0,Cj-min⁡Ci≥ε,F1ε≜f∈F:∀h∈Klε∖Ksε;∀p1,p2∈Ksε,h:fp1,fp2>0,Cp1-Cp2≤ε,∑fp=q;∀j∈Klε∖p:fj=0,Cj-min⁡Cp≥ε,h=Kl,1ε,…,Kl,M-Nε∖Ksε,Fkε≜f∈F:∀h1,…,hk∈Klε∖Ksε;∀p1,p2∈Ksε,h1,…,hk:fp1,fp2>0,Cp1-Cp2≤ε,∑fp=q;∀j∈Klε∖p:fj=0,Cj-min⁡Cp≥ε,h1,…,hk:everykroutesinKl,1ε,…,Kl,M-NεexcludeKsε,k=0,…,M-N.We use a bridge network to illustrate (18) in detail. The network topology of the test network, travel time functions, and traffic demand are depicted in Figure 7. The network consists of 4 nodes, 6 links, and 1 OD pair. Red curves on the right indicate 4 routes. The indifference band ε is set as 4, 10, 15, 30, and 60.Figure 7
A bridge network and routes characteristics.The UE isf1=10, f2=0, f3=0, and f4=10. That is, routes 1 and 4 are utilized under UE. Substitute Klεl,0∗=Ksεs,0∗=1,4, route costs, and the demand into (13a), (13b), (13c), (13d), (13e), and (13f), we obtain the largest critical values εl,0∗=0, εl,1∗=5, εl,2∗=11.3, and εl,3∗=∞. Solving (15a), (15b), (15c), (15d), (15e), and (15f), then we obtain the smallest critical values εs,0∗=0, εs,1∗=17.5, εs,2∗=52.5, and εs,3∗=∞. There are three cases for the largest ε-URS:(1)
0≤ε<5:Klε=1,4, and when ε=0, f=10,0,0,10, C=50,65,55,50.(2)
5≤ε<11.3:Klε=1,3,4, and when ε=5, f=10,0,0+,10, C=50,65,55,50.(3)
ε≥11.3:Klε=1,2,3,4, and when ε=11.3, f=9.26,0+,2.59,8.15, C=49.63,60.93,60.93,49.63.And there are three cases for the smallestε-URS:(1)
0≤ε<17.5:Ksε=1,4, and when ε=0, f=10,0,0,10, C=50,65,55,50.(2)
17.5≤ε<52.5:Ksε=1,3,4, and when ε=17.5, f=7.5,0,0+,12.5, C=40,60,57.5,57.5.(3)
ε≥52.5:Ksε=1,2,3,4, and when ε=52.5, f=17.5,0+,0+,2.5, C=80,80,47.5,27.5.Then we assign all the traffic demands with diffidentε as follows.(1)
Whenε=4, Kl4=Ks4=1,4, and M=N=2, then (19)F04≜f∈F:f1,f4>0,C1f-C4f≤4,f1+f4=20.(2)
Whenε=10, Kl10=1,3,4, Ks10=1,4, M=3, and N=2, then (20)F010≜f∈F:f1,f4>0,C1f-C4f≤10,f1+f4=20;f3=0,C3f-min⁡C1f,C4f≥10,F110≜f∈F:∀i1,i2∈1,4,h∈3;∀p1,p2∈1,3,4:fp1,fp2>0,Cp1f-Cp2f≤10,f1+f3+f4=20.(3)
Whenε=15, Kl15=1,2,3,4, Ks15=1,4, M=4, and N=2, then(21)F015≜f∈F:f1,f4>0,C1f-C4f≤15,f1+f4=20;∀j∈2,3:fj=0,Cj-min⁡C1f,C4f≥15,F115≜f∈F:∀h∈2,3;∀p1,p2∈1,4,h:fp1,fp2>0,Cp1f-Cp2f≤15,∑fp=20;∀j∈1,2,3,4∖p:fj=0,Cj-min⁡Cp≥15,h=2,3,F215≜f∈F:∀h1,h2∈2,3;∀p1,p2∈1,2,3,4:fp1,fp2>0,Cp1f-Cp2f≤15,∑fp=20.(4)
Whenε=30, Kl30=1,2,3,4, Ks30=1,3,4, M=4, and N=3, then(22)F030≜f∈F:∀i1,i2∈1,3,4:fi1,fi2>0,Ci1f-Ci2f≤30,f1+f3+f4=20;f2=0,C2f-min⁡Ci≥30,F130≜f∈F:h∈2;∀p1,p2∈1,2,3,4:fp1,fp2>0,Cp1f-Cp2f≤30,f1+f2+f3+f4=20.(5)
Whenε=60, Kl60=Ks60=1,2,3,4, and M=N=4, then (23)F060≜f∈F:∀i1,i2∈1,2,3,4:fi1,fi2>0,Ci1f-Ci2f≤60,f1+f2+f3+f4=20.For convenience, we only show the R-BRUE solution sets withε=4,10,15 in Figure 8. Due to the flow conservation of the fixed demand, its R-BRUE solution sets can be characterized by routes 1, 3, and 4 in Figures 8(b) and 8(c). Figure 8(a) is composed of a 2-route green subset; Figure 8(b) is composed of a 2-route green subset and 3-route yellow subset; Figure 8(c) is composed of a 2-route green subset, 3-route yellow subset, and 4-route blue subset. The magenta legend denotes that the solutions do not satisfy ε-R-BRUE.Figure 8
R-BRUE solution sets illustration.
(a)
R-BRUE solution set withε=4 (b)
R-BRUE solution set withε=10 (c)
R-BRUE solution set withε=15From Figure8, we can see that (1) when ε=15, in F015 (green subset), only routes 1 and 4 carry flow, so the subset is a line. In F115 (yellow subset), route 3 begins to carry flow and f3>0. In F215 (blue subset), route 2 begins to carry flow and f2>0; (2) the solution set is bounded; this is because FR-BRUEε⊂F:F≜f:f≥0,∑k∈Kωfkω=qω,∀ω∈W, while its closeness cannot be guaranteed due to Ckωf<mini∈KωCiωf+εω⇒fkω>0. In Figure 8(b), the travel time of the UE solution fUE=10,0,0,10 on the magenta line is CUE=50,65,55,50, and C3=55<50+15, so f3 should be greater than 0 in R-BRUE model; hence CUE do not satisfy 10-R-BRUE; (3) without considering the boundary point of ε-R-BRUE, the solution set is monotonically nondecreasing with the increase of ε; and (4) the subset is not necessarily convex even though the link performance function is affine linear; this is because the constraint condition of Cj-min⁡Ci≥ε is nonconvex. This property can be seen in the yellow block which is nonconvex in Figure 8(c). Hence, we cannot guarantee the convexity of ε-R-BRUE solution set.


### 5.2.ε-R-BRUE Flow Set without Paradoxical Route for Multiple OD Pairs

In the last section, we obtainε-R-BRUE route set without paradoxical route for multiple OD pairs. Then, it is not difficult to generalize the methodology of constructing ε-R-BRUE flow set without paradoxical route for a single OD pair to multiple OD pairs. We assign all the traffic demands to the routes as follows:(24)F0ε≜f∈F:∀ω∈W,∀i1ω,i2ω∈Ksεω:fi1ω,fi2ω>0,Ci1ω-Ci2ω≤εω,∑fiω=qω;∀jω∈Klεω∖iω:fjω=0,Cjω-min⁡Ciω≥εω,Fkε≜f∈F:∀ω∈W,∀h1ω,…,hkωω∈Klεω∖Ksεω;∀p1ω,p2ω∈Ksεω,h1ω,…,hkωω:fp1ω,fp2ω>0,Cp1ω-Cp2ω≤εω,∑fiω=qω;∀jω∈Klεω∖pω:fjω=0,Cjω-min⁡Cpω≥εω,h1ω,…,hkωω:everykωroutesinKl,1εω,…,Kl,M-NεωexcludeKsεω,∑kω=k,k=0,…,M-N.


## 5.1.ε-R-BRUE Flow Set without Paradoxical Route for One OD Pair

Define a sequence of setsFkε, k=0,…,M-N, where M and N are the cardinalities of largest and smallest ε-URS. Then we assign all the traffic demands as follows:(18)F0ε≜f∈F:∀i1,i2∈Ksε:fi1,fi2>0,Ci1-Ci2≤ε,∑fi=q;∀j∈Klε∖i:fj=0,Cj-min⁡Ci≥ε,F1ε≜f∈F:∀h∈Klε∖Ksε;∀p1,p2∈Ksε,h:fp1,fp2>0,Cp1-Cp2≤ε,∑fp=q;∀j∈Klε∖p:fj=0,Cj-min⁡Cp≥ε,h=Kl,1ε,…,Kl,M-Nε∖Ksε,Fkε≜f∈F:∀h1,…,hk∈Klε∖Ksε;∀p1,p2∈Ksε,h1,…,hk:fp1,fp2>0,Cp1-Cp2≤ε,∑fp=q;∀j∈Klε∖p:fj=0,Cj-min⁡Cp≥ε,h1,…,hk:everykroutesinKl,1ε,…,Kl,M-NεexcludeKsε,k=0,…,M-N.We use a bridge network to illustrate (18) in detail. The network topology of the test network, travel time functions, and traffic demand are depicted in Figure 7. The network consists of 4 nodes, 6 links, and 1 OD pair. Red curves on the right indicate 4 routes. The indifference band ε is set as 4, 10, 15, 30, and 60.Figure 7
A bridge network and routes characteristics.The UE isf1=10, f2=0, f3=0, and f4=10. That is, routes 1 and 4 are utilized under UE. Substitute Klεl,0∗=Ksεs,0∗=1,4, route costs, and the demand into (13a), (13b), (13c), (13d), (13e), and (13f), we obtain the largest critical values εl,0∗=0, εl,1∗=5, εl,2∗=11.3, and εl,3∗=∞. Solving (15a), (15b), (15c), (15d), (15e), and (15f), then we obtain the smallest critical values εs,0∗=0, εs,1∗=17.5, εs,2∗=52.5, and εs,3∗=∞. There are three cases for the largest ε-URS:(1)
0≤ε<5:Klε=1,4, and when ε=0, f=10,0,0,10, C=50,65,55,50.(2)
5≤ε<11.3:Klε=1,3,4, and when ε=5, f=10,0,0+,10, C=50,65,55,50.(3)
ε≥11.3:Klε=1,2,3,4, and when ε=11.3, f=9.26,0+,2.59,8.15, C=49.63,60.93,60.93,49.63.And there are three cases for the smallestε-URS:(1)
0≤ε<17.5:Ksε=1,4, and when ε=0, f=10,0,0,10, C=50,65,55,50.(2)
17.5≤ε<52.5:Ksε=1,3,4, and when ε=17.5, f=7.5,0,0+,12.5, C=40,60,57.5,57.5.(3)
ε≥52.5:Ksε=1,2,3,4, and when ε=52.5, f=17.5,0+,0+,2.5, C=80,80,47.5,27.5.Then we assign all the traffic demands with diffidentε as follows.(1)
Whenε=4, Kl4=Ks4=1,4, and M=N=2, then (19)F04≜f∈F:f1,f4>0,C1f-C4f≤4,f1+f4=20.(2)
Whenε=10, Kl10=1,3,4, Ks10=1,4, M=3, and N=2, then (20)F010≜f∈F:f1,f4>0,C1f-C4f≤10,f1+f4=20;f3=0,C3f-min⁡C1f,C4f≥10,F110≜f∈F:∀i1,i2∈1,4,h∈3;∀p1,p2∈1,3,4:fp1,fp2>0,Cp1f-Cp2f≤10,f1+f3+f4=20.(3)
Whenε=15, Kl15=1,2,3,4, Ks15=1,4, M=4, and N=2, then(21)F015≜f∈F:f1,f4>0,C1f-C4f≤15,f1+f4=20;∀j∈2,3:fj=0,Cj-min⁡C1f,C4f≥15,F115≜f∈F:∀h∈2,3;∀p1,p2∈1,4,h:fp1,fp2>0,Cp1f-Cp2f≤15,∑fp=20;∀j∈1,2,3,4∖p:fj=0,Cj-min⁡Cp≥15,h=2,3,F215≜f∈F:∀h1,h2∈2,3;∀p1,p2∈1,2,3,4:fp1,fp2>0,Cp1f-Cp2f≤15,∑fp=20.(4)
Whenε=30, Kl30=1,2,3,4, Ks30=1,3,4, M=4, and N=3, then(22)F030≜f∈F:∀i1,i2∈1,3,4:fi1,fi2>0,Ci1f-Ci2f≤30,f1+f3+f4=20;f2=0,C2f-min⁡Ci≥30,F130≜f∈F:h∈2;∀p1,p2∈1,2,3,4:fp1,fp2>0,Cp1f-Cp2f≤30,f1+f2+f3+f4=20.(5)
Whenε=60, Kl60=Ks60=1,2,3,4, and M=N=4, then (23)F060≜f∈F:∀i1,i2∈1,2,3,4:fi1,fi2>0,Ci1f-Ci2f≤60,f1+f2+f3+f4=20.For convenience, we only show the R-BRUE solution sets withε=4,10,15 in Figure 8. Due to the flow conservation of the fixed demand, its R-BRUE solution sets can be characterized by routes 1, 3, and 4 in Figures 8(b) and 8(c). Figure 8(a) is composed of a 2-route green subset; Figure 8(b) is composed of a 2-route green subset and 3-route yellow subset; Figure 8(c) is composed of a 2-route green subset, 3-route yellow subset, and 4-route blue subset. The magenta legend denotes that the solutions do not satisfy ε-R-BRUE.Figure 8
R-BRUE solution sets illustration.
(a)
R-BRUE solution set withε=4 (b)
R-BRUE solution set withε=10 (c)
R-BRUE solution set withε=15From Figure8, we can see that (1) when ε=15, in F015 (green subset), only routes 1 and 4 carry flow, so the subset is a line. In F115 (yellow subset), route 3 begins to carry flow and f3>0. In F215 (blue subset), route 2 begins to carry flow and f2>0; (2) the solution set is bounded; this is because FR-BRUEε⊂F:F≜f:f≥0,∑k∈Kωfkω=qω,∀ω∈W, while its closeness cannot be guaranteed due to Ckωf<mini∈KωCiωf+εω⇒fkω>0. In Figure 8(b), the travel time of the UE solution fUE=10,0,0,10 on the magenta line is CUE=50,65,55,50, and C3=55<50+15, so f3 should be greater than 0 in R-BRUE model; hence CUE do not satisfy 10-R-BRUE; (3) without considering the boundary point of ε-R-BRUE, the solution set is monotonically nondecreasing with the increase of ε; and (4) the subset is not necessarily convex even though the link performance function is affine linear; this is because the constraint condition of Cj-min⁡Ci≥ε is nonconvex. This property can be seen in the yellow block which is nonconvex in Figure 8(c). Hence, we cannot guarantee the convexity of ε-R-BRUE solution set.


## 5.2.ε-R-BRUE Flow Set without Paradoxical Route for Multiple OD Pairs

In the last section, we obtainε-R-BRUE route set without paradoxical route for multiple OD pairs. Then, it is not difficult to generalize the methodology of constructing ε-R-BRUE flow set without paradoxical route for a single OD pair to multiple OD pairs. We assign all the traffic demands to the routes as follows:(24)F0ε≜f∈F:∀ω∈W,∀i1ω,i2ω∈Ksεω:fi1ω,fi2ω>0,Ci1ω-Ci2ω≤εω,∑fiω=qω;∀jω∈Klεω∖iω:fjω=0,Cjω-min⁡Ciω≥εω,Fkε≜f∈F:∀ω∈W,∀h1ω,…,hkωω∈Klεω∖Ksεω;∀p1ω,p2ω∈Ksεω,h1ω,…,hkωω:fp1ω,fp2ω>0,Cp1ω-Cp2ω≤εω,∑fiω=qω;∀jω∈Klεω∖pω:fjω=0,Cjω-min⁡Cpω≥εω,h1ω,…,hkωω:everykωroutesinKl,1εω,…,Kl,M-NεωexcludeKsεω,∑kω=k,k=0,…,M-N.


## 6. Conclusions

In this paper, a boundedly rational user equilibrium model with restricted unused routes (R-BRUE) was proposed. This new model assumes that travel cost of all used route is less than or equal to the sum of given indifference band and the shortest route cost; meanwhile, the travel cost of the unused route is greater than or equal to the sum of indifference band and the shortest route cost. The mathematical formulation of the proposed model was then established.Before constructing the R-BRUE flow set, largest and smallest used route sets were explored first. As the value of the indifference band increases, some routes which were not utilized before will be taken, and thus the route set that contains the equilibrium flow was named as the largest used route set. As the value of the indifference band increases, some routes which must be utilized for all R-BRUE flow patterns will be taken, and this route set was defined as the smallest used route set. Paradoxical route is defined as that with the increasing of OD demand; the UE flow on the paradoxical route increases first and then decreases. The monotonically nondecreasing property of largest and smallest used route sets without paradoxical route is proved.The critical values of the indifference band to augment the largest and smallest used route sets can be identified by sequentially solving a class of mathematical programs. After the largest and smallest used route sets are obtained, the whole R-BRUE flow set can be obtained by assigning all traffic demands to the corresponding generated route set.The proposed model is appealing in modeling realistic travel behavior. But due to the nonconvexity of the feasible region, it is difficult to get the solution using mathematical programming method, and our method which is separation of the solution sets takes heavy computational burdens. In future research, we will study the solution algorithm and then apply the built model to real traffic network, such as the autonomous vehicles. Also, it is worthwhile to extend the proposed model to the network design problem, such as enhancing capacities of the established links, congestion pricing, and adding new links to an existing road network.



---

*Source: 9848916-2016-12-05.xml*