# Bounding the Inefficiency of the Multiclass, Multicriteria C-Logit Stochastic User Equilibrium in a Transportation Network

Authors: Lekai Yuan; Xi Zhang; Chaofeng Shi
Journal: Complexity
 (2021)

---

## Abstract

We derive the exact inefficiency upper bounds of the multiclass C-Logit stochastic user equilibrium (CL-SUE) in a transportation network. All travelers are classified on the basis of different values of time (VOT) into M classes. The multiclass CL-SUE model gives a more realistic path choice probability in comparison with the logit-based stochastic user equilibrium model by considering the overlapping effects between paths. To find efficiency loss upper bounds of the multiclass CL-SUE, two equivalent variational inequalities for the multiclass CL-SUE model, i.e., time-based variational inequality (VI) and monetary-based VI, are formulated. We give four different methods to define the inefficiency of the multiclass CL-SUE, i.e., to compare multiclass CL-SUE with multiclass system optimum, or to compare multiclass CL-SUE with multiclass C-Logit stochastic system optimum (CL-SSO), under the time-based criterion and the monetary-based criterion, respectively. We further investigate the effects of various parameters which include the degree of path overlapping (the commonality factor), the network complexity, degree of traffic congestion, the VOT of user classes, the network familiarity, and the total demand on the inefficiency bounds.


---

## Body

## 1. Introduction

Concerning the path choice behavior in networks, Wardrop proposed two basic principles: one is the user equilibrium (UE) and the other is the system optimum (SO) [1]. The UE principle shows that all used paths have minimum and equal travel cost (or time), and all unused paths have higher or equal travel cost (or time). In addition, the UE principle assumes that every traveler has a full understanding of the network information and chooses the travel path accordingly to minimize their own travel cost. Later, the researchers have extended the UE model in different aspects, such as boundedly rational UE [2–4], fuzzy UE [5–7], and prospect‐based UE [8–10]. The concept of the boundedly rational user equilibrium (BRUE) was proposed in the 1980s. Lou et al. [3] investigated congestion pricing strategies in static networks with boundedly rational route choice behavior. Xuan et al. [4] studied mathematical formulation and solution sets of BRUE. Miralinaghi et al. [7] proposed an alternative approach for a traffic assignment problem that further extends the applications of the fuzzy theory in route choice behavior and network traffic modelling. Xu et al. [10] proposed a conjecture on travelers’ determination of reference points and encapsulates it into the prospect-based user equilibrium conditions. However, in practice, we cannot always assume that this assumption is true. More realistically, travelers who choose the same route may have different perceived travel times due to all kinds of unmeasured factors. Suppose that the perceived travel times are considered as independent and identical distributed (IID) Gumbel random variables [11], travelers’ path choices for minimizing their perceived travel time will lead to the stochastic user equilibrium (SUE) state [12]. Concerning the path choice problem in the network, two disadvantages of the logit-based SUE model are as follows: (1) it cannot explain overlapping between paths and (2) it cannot explain the perception variance of travels of different lengths [13, 14].To alleviate the above two disadvantages, some extended logit-based SUE models have been proposed in recent two decades, such as C-Logit SUE (CL-SUE) model [13–16], generalized nested logit SUE (GNL-SUE) model [17], cross-nested logit SUE (CNL-SUE) model [18, 19], and paired combinatorial logit SUE (PCL-SUE) model [20]. Other significant theoretical achievements in [21, 22] have also made a contribution to overcoming the disadvantages of the logit-based SUE model. CL-SUE model proposed by Cascetta et al. [13] can solve the overlapping problem by using a commonality factor reflecting path overlapping to modify the systematic part of the utility function. Zhou et al. [14] further provided equivalent variational inequality (VI) and mathematical programming (MP) formulations for the CL-SUE model.The CL-SUE model can overcome the disadvantages of the logit-based SUE model by considering the overlapping effects between paths and give a more realistic path choice probability. The SO state has the minimum inefficiency loss by definition. Therefore, the CL-SUE model is still inefficient compared with the SO model due to the users’ selfish routing. Recently, quantifying and bounding the inefficiency of the equilibrium assignment in the transportation environment has aroused great research interest, while less attention has been paid to multiclass CL-SUE. Koutsoupias and Papadimitriou first gave the concept of “price of anarchy (POA)” [23]. After that, the POA was first used in the traffic network by Roughgarden and Tardos [24]. In the next few years, other great theoretical achievements of POA proposed by Roughgarden [25–27] have greatly promoted the development of inefficiency in the transportation network. In recent years, the above works have been extensively investigated in many aspects [28–36]. Guo et al. [37] gave two efficiency loss bounds of the SUE against SO and stochastic system optimum (SSO) in a stochastic circumstance, respectively. Considering a transportation network with multiple classes of users, Yu et al. [38] studied the inefficiency of the multiclass SUE, which is the extension of research achievements in [37]. Based on the above main work, some researchers have also studied the inefficiency of the extended logit-based SUE. Yong et al. provided several efficiency loss upper bounds of the CL-SUE by considering the overlapping effects between paths [39], which is also the extension of research achievements in [37]. Zeng and Wang initially explored inefficiency upper bound of CNL-SUE in the taxed stochastic transportation network and further investigated inefficiency upper bounds for the low-degree travel time function [40]. For a transportation network with heterogeneous users who have different values of time (VOT), the network optimization usually has two objectives, i.e., minimizing total system travel time (TSTT) and minimizing total system travel cost (TSTC). Guo and Yang further measured the system optimal performance difference by the two different criteria, i.e., time-based criteria and monetary-based criteria [41]. Yu and Wang [42] derived the accurate inefficiency bounds of multiclass UE with elastic travel demand by making full use of equivalent VI under time-based criterion and cost-based criterion, respectively. Han and Yang [43] have given several bounds for the inefficiency of the multiclass traffic equilibrium assignment problem in the tolled network under the two different criteria, respectively. Huang et al. [44] further discussed the efficiency loss of the SUE where all travelers are classified into two main categories, one equipped with advanced traveler information systems (ATIS) and another unequipped. Yu et al. studied the inefficiency of the mixed equilibrium with heterogeneous users [45–47].Different from the existing studies, this study extends the logit-based SUE to the multiclass CL-SUE. The purpose of our study was to derive four efficiency loss upper bounds of the multiclass CL-SUE. The two corresponding models, i.e., multiclass SO model and multiclass C-Logit stochastic system optimum (CL-SSO) model, should be mentioned before exploring the efficiency loss of the multiclass CL-SUE. The multiclass SO model that minimizes the TSTT has been widely used in the literature. In this article, the multiclass CL-SSO model that minimizes the total perceived travel time (TPTT) is established based on the work in [39, 48, 49]. Therefore, there are four kinds of ways to define the efficiency loss of the multiclass CL-SUE, i.e., comparing multiclass CL-SUE with multiclass SO, or comparing multiclass CL-SUE with multiclass CL-SSO, under the time-based criterion and the monetary-based criterion, respectively. The highlights of our research focus on these four situations. In recent years, the effects of various parameters (e.g., degree of traffic congestion and total traffic demand of the network) on the inefficiency upper bound has been widely studied, while paying less attention to commonality factor reflecting path overlapping. This paper studies the effects of commonality factor reflecting path overlapping on the efficiency loss of the multiclass CL-SUE. The result shows that the commonality factor reflecting path overlapping has a significant impact on the inefficiency upper bound.The rest of this article is organized below. In Section2, we have a brief review of multiclass SUE and CL-SUE models, and then formulate the equivalent VI formulations of the multiclass CL-SUE model under time-based criterion and monetary-based criterion, respectively. In Sections 3 and 4, we derive four inefficiency upper bounds by using the equivalent VI formulations of the multiclass CL-SUE. Section 5 discusses the effects of various parameters on the efficiency loss bounds. In Section 6, we summarize the main research findings of this paper in tabular form. We give a numerical example to illustrate our conclusions in Section 7. Finally, Section 8 provides some conclusions and analyses the further research directions.


## 2. Review of Multiclass SUE and CL-SUE Models

### 2.1. Multiclass SUE Model

LetGN,A be a directed transportation network defined by a set N of nodes and a set A of directed links. All travelers are classified in terms of different VOT into M classes. Table 1 provides the notations used in the paper:Table 1
Notations.
NotationDescriptionWThe set of origin-destination (OD) pairsRwThe set of all feasible paths connecting OD pairw∈Wβmβm>0The average VOT for users of classmdwmThe travel demand of user classm between OD pair w∈WfrwmThe flow of user classm on path r∈Rw,w∈WfPath flow vector,f=frwm,r∈Rw,w∈W,m=1,2,…,MTvamThe flow of user classm on link a∈AvaThe total flow on linka∈AvLink flow vector,v=vam,a∈A,m=1,2,…,MTδarwThe link-path incidence indicator, which is equal to 1 if pathr∈Rw uses link a∈A, and 0 otherwiseΩfSet of feasible path flow vectors,Ωf=f|frwm≥0,∑r∈Rwfrwm=dwm,∀r∈Rw,∀w∈W,m=1,2,…,MΩvSet of feasible link flow vectors,Ωv=v|f∈Ωf,vam=∑w∈W∑r∈Rwfrwmδarw,va=∑m=1Mvam,∀a∈A,m=1,2,…,MtavaThe travel time function on linka∈A, which is supposed to be separable, convex, differentiable, and monotonically increasing with vacamvaThe actual travel time of user classm on link a∈A, which is assumed to be a monotonically increasing function of vacrwmThe actual travel time of user classm on path r∈Rw,w∈WAccording to Table1, the following relationships and constraints hold:(1)vam=∑w∈W∑r∈Rwfrwmδarw,∀a∈A,m=1,2,⋯,M,va=∑m=1Mvam,∀a∈A,m=1,2,⋯,M,∑r∈Rwfrwm=dwm,∀w∈W,m=1,2,⋯,M,frwm≥0,∀r∈Rw,w∈W,m=1,2,⋯,M,crwm=∑a∈Acamδarw,∀r∈Rw,w∈W,m=1,2,⋯,M.In a multiclass SUE model, assume that all users are utility-maximizers. LetUrwm denote the travel utility perceived by user class m on path r∈Rw,w∈W. Then, Urwm is given by(2)Urwm=−θCrwm=−θcrwm+ξrwm,r∈Rw,w∈W,m=1,2,⋯,M,where Crwm is the perceived travel time of user class m on path r∈Rw,w∈W, θ is a positive unit scaling parameter, −θcrwm is the measured utility, and ξrwm is a random term representing the user’s perception error. Let Prwm be the probability of user class m choosing path r∈Rw,w∈W, then the utility maximization theory shows that(3)Prwm=PrUrwm≥Ukwm,∀k∈Rw,r∈Rw,w∈W.Prwm has the two properties as follows:(4)0≤Prwm≤1,r∈Rw,w∈W,m=1,2,⋯,M,∑r∈RwPrwm=1,w∈W,m=1,2,⋯,M.All random termsξrwm in (2) are supposed to be IID Gumbel random variables. Then, the path choice probability for user class m is given by(5)Prwm=exp−θcrwm∑l∈Rwexp−θclwm,r∈Rw,w∈W,m=1,2,⋯,M.and frwm can be obtained by(6)frwm=dwmPrwm,r∈Rw,w∈W,m=1,2,⋯,M.Similar to that done in Fisk [12], the multiclass logit-based SUE model can be formulated as an equivalent MP problem below.(7)minf∈ΩfZf=∑a∈A∫0vataωdω+1θ∑w∈W∑r∈Rw∑m=1Mfrwmlnfrwm.The equivalent VI of problem (7) is presented in the lemma below.Lemma 1.
If the link time function,tava, a∈A is differentiable, convex, separable, and monotonically increasing with link flow va, a multiclass logit-based SUE model with fixed OD demand is equivalent to the following VI, i.e., find f⟶∈Ωf, such that(8)∑w∈W∑r∈Rw∑m=1Mcrwmf⟶+1θlnf⟶rwmfrwm−f⟶rwm≥0,∀f∈Ωf.The disadvantages of the multiclass SUE model have been found by some researchers. One of the disadvantages is that it cannot explain the overlapping effects between different paths, which means that the unrealistic path choice probability is given.


### 2.2. Multiclass CL-SUE Model

Cascetta et al. [13] proposed a CL-SUE model, which can overcome the disadvantages of the logit-based SUE by using a commonality factor reflecting path overlapping to modify the systematic part of the utility function. Similar to the work of Cascetta et al. [13], the multiclass CL-SUE model can be established. Then, the path choice probability of the multiclass CL-SUE model is provided by(9)Prwm=exp−θcrwm+cfrw∑l∈Rwexp−θclwm+cfrw,r∈Rw,w∈W,m=1,2,⋯,M,where cfrw is a commonality factor of path r∈Rw,w∈W. In this paper, the form of the commonality factor [13] is used as follows:(10)cfrw=β0ln∑l∈RwLrlwLrw⋅Llwγ0,∀r∈Rw,w∈W,where β0 and γ0 are the parameters; Lrlw denotes the common length of paths r and l between the OD pair w∈W; and Lrw and Llw denote the lengths of paths r and l between the OD pair w∈W, respectively. The length can be regarded as the free-flow travel time [14]. And frwm is provided by(11)frwm=dwmPrwm,r∈Rw,w∈W,m=1,2,⋯,M.Similar to that done in Zhou et al. [14], the multiclass CL-SUE model can be formulated as an equivalent MP problem below.(12)minf∈ΩfZf=∑a∈A∫0vataωdω+1θ∑w∈W∑r∈Rw∑m=1Mfrwmlnfrwm+∑w∈W∑r∈Rw∑m=1Mfrwmcfrw.To find efficiency loss upper bounds of the multiclass CL-SUE, the equivalent VI of problem (12) is presented in the lemma below.Lemma 2.
If the link time function,tava, a∈A is differentiable, convex, separable, and monotonically increasing with link flow va, a multiclass CL-SUE model with fixed OD demand is equivalent to the following VI, i.e., find f¯∈Ωf, such that(13)∑w∈W∑r∈Rw∑m=1Mcrwmf¯+1θlnf¯rwm+cfrwfrwm−f¯rwm≥0,∀f∈Ωf.Proof of Lemma 2.
Sincetava is monotonically increasing and Ωf is compact, the objective function (12) is strictly convex. Hence, the path flow solution of the problem (12) is unique. The necessary and sufficient condition, which can guarantee that f¯∈Ωf is the unique optimal solution of problem (12), is provided as follows:(14)∇fZf¯Tf−f¯≥0,for anyf∈Ωf.
Usingva=∑m=1Mvam=∑w∈W∑r∈Rw∑m∈Mfrwmδarw and substituting(15)∇fZf¯T=⋯,1θ+1θlnf¯rwm+∑a∈Atav¯aδarw+cfrw,⋯=⋯,1θ+1θlnf¯rwm+crwmf¯+cfrw,⋯.into (14), VI (13) can be obtained according to equation ∑w∈W∑r∈Rw∑m∈M1/θfrwm−f¯rwm=∑w∈W1/θdw−dw=0.
Under the time-based criterion,camva is given by(16)camva=tava,a∈A,m=1,2,⋯,M.
By contrast, under the monetary-based criterion,camva can be given by(17)camva=βmtava,a∈A,m=1,2,⋯,M.
Substituting (16) and (17) into (13), respectively, and using (1), we can get the following time-based VI and monetary-based VI, respectively.(18)∑a∈Atav¯va−v¯a+1θ∑w∈W∑r∈Rw∑m=1Mlnf¯rwm+θcfrwfrwm−f¯rwm≥0,∀f∈Ωf,∑a∈A∑m=1Mβmtav¯vam−v¯am+1θ∑w∈W∑r∈Rw∑m=1Mlnf¯rwm+θcfrwfrwm−f¯rwm≥0,∀f∈Ωf.


## 2.1. Multiclass SUE Model

LetGN,A be a directed transportation network defined by a set N of nodes and a set A of directed links. All travelers are classified in terms of different VOT into M classes. Table 1 provides the notations used in the paper:Table 1
Notations.
NotationDescriptionWThe set of origin-destination (OD) pairsRwThe set of all feasible paths connecting OD pairw∈Wβmβm>0The average VOT for users of classmdwmThe travel demand of user classm between OD pair w∈WfrwmThe flow of user classm on path r∈Rw,w∈WfPath flow vector,f=frwm,r∈Rw,w∈W,m=1,2,…,MTvamThe flow of user classm on link a∈AvaThe total flow on linka∈AvLink flow vector,v=vam,a∈A,m=1,2,…,MTδarwThe link-path incidence indicator, which is equal to 1 if pathr∈Rw uses link a∈A, and 0 otherwiseΩfSet of feasible path flow vectors,Ωf=f|frwm≥0,∑r∈Rwfrwm=dwm,∀r∈Rw,∀w∈W,m=1,2,…,MΩvSet of feasible link flow vectors,Ωv=v|f∈Ωf,vam=∑w∈W∑r∈Rwfrwmδarw,va=∑m=1Mvam,∀a∈A,m=1,2,…,MtavaThe travel time function on linka∈A, which is supposed to be separable, convex, differentiable, and monotonically increasing with vacamvaThe actual travel time of user classm on link a∈A, which is assumed to be a monotonically increasing function of vacrwmThe actual travel time of user classm on path r∈Rw,w∈WAccording to Table1, the following relationships and constraints hold:(1)vam=∑w∈W∑r∈Rwfrwmδarw,∀a∈A,m=1,2,⋯,M,va=∑m=1Mvam,∀a∈A,m=1,2,⋯,M,∑r∈Rwfrwm=dwm,∀w∈W,m=1,2,⋯,M,frwm≥0,∀r∈Rw,w∈W,m=1,2,⋯,M,crwm=∑a∈Acamδarw,∀r∈Rw,w∈W,m=1,2,⋯,M.In a multiclass SUE model, assume that all users are utility-maximizers. LetUrwm denote the travel utility perceived by user class m on path r∈Rw,w∈W. Then, Urwm is given by(2)Urwm=−θCrwm=−θcrwm+ξrwm,r∈Rw,w∈W,m=1,2,⋯,M,where Crwm is the perceived travel time of user class m on path r∈Rw,w∈W, θ is a positive unit scaling parameter, −θcrwm is the measured utility, and ξrwm is a random term representing the user’s perception error. Let Prwm be the probability of user class m choosing path r∈Rw,w∈W, then the utility maximization theory shows that(3)Prwm=PrUrwm≥Ukwm,∀k∈Rw,r∈Rw,w∈W.Prwm has the two properties as follows:(4)0≤Prwm≤1,r∈Rw,w∈W,m=1,2,⋯,M,∑r∈RwPrwm=1,w∈W,m=1,2,⋯,M.All random termsξrwm in (2) are supposed to be IID Gumbel random variables. Then, the path choice probability for user class m is given by(5)Prwm=exp−θcrwm∑l∈Rwexp−θclwm,r∈Rw,w∈W,m=1,2,⋯,M.and frwm can be obtained by(6)frwm=dwmPrwm,r∈Rw,w∈W,m=1,2,⋯,M.Similar to that done in Fisk [12], the multiclass logit-based SUE model can be formulated as an equivalent MP problem below.(7)minf∈ΩfZf=∑a∈A∫0vataωdω+1θ∑w∈W∑r∈Rw∑m=1Mfrwmlnfrwm.The equivalent VI of problem (7) is presented in the lemma below.Lemma 1.
If the link time function,tava, a∈A is differentiable, convex, separable, and monotonically increasing with link flow va, a multiclass logit-based SUE model with fixed OD demand is equivalent to the following VI, i.e., find f⟶∈Ωf, such that(8)∑w∈W∑r∈Rw∑m=1Mcrwmf⟶+1θlnf⟶rwmfrwm−f⟶rwm≥0,∀f∈Ωf.The disadvantages of the multiclass SUE model have been found by some researchers. One of the disadvantages is that it cannot explain the overlapping effects between different paths, which means that the unrealistic path choice probability is given.


## 2.2. Multiclass CL-SUE Model

Cascetta et al. [13] proposed a CL-SUE model, which can overcome the disadvantages of the logit-based SUE by using a commonality factor reflecting path overlapping to modify the systematic part of the utility function. Similar to the work of Cascetta et al. [13], the multiclass CL-SUE model can be established. Then, the path choice probability of the multiclass CL-SUE model is provided by(9)Prwm=exp−θcrwm+cfrw∑l∈Rwexp−θclwm+cfrw,r∈Rw,w∈W,m=1,2,⋯,M,where cfrw is a commonality factor of path r∈Rw,w∈W. In this paper, the form of the commonality factor [13] is used as follows:(10)cfrw=β0ln∑l∈RwLrlwLrw⋅Llwγ0,∀r∈Rw,w∈W,where β0 and γ0 are the parameters; Lrlw denotes the common length of paths r and l between the OD pair w∈W; and Lrw and Llw denote the lengths of paths r and l between the OD pair w∈W, respectively. The length can be regarded as the free-flow travel time [14]. And frwm is provided by(11)frwm=dwmPrwm,r∈Rw,w∈W,m=1,2,⋯,M.Similar to that done in Zhou et al. [14], the multiclass CL-SUE model can be formulated as an equivalent MP problem below.(12)minf∈ΩfZf=∑a∈A∫0vataωdω+1θ∑w∈W∑r∈Rw∑m=1Mfrwmlnfrwm+∑w∈W∑r∈Rw∑m=1Mfrwmcfrw.To find efficiency loss upper bounds of the multiclass CL-SUE, the equivalent VI of problem (12) is presented in the lemma below.Lemma 2.
If the link time function,tava, a∈A is differentiable, convex, separable, and monotonically increasing with link flow va, a multiclass CL-SUE model with fixed OD demand is equivalent to the following VI, i.e., find f¯∈Ωf, such that(13)∑w∈W∑r∈Rw∑m=1Mcrwmf¯+1θlnf¯rwm+cfrwfrwm−f¯rwm≥0,∀f∈Ωf.Proof of Lemma 2.
Sincetava is monotonically increasing and Ωf is compact, the objective function (12) is strictly convex. Hence, the path flow solution of the problem (12) is unique. The necessary and sufficient condition, which can guarantee that f¯∈Ωf is the unique optimal solution of problem (12), is provided as follows:(14)∇fZf¯Tf−f¯≥0,for anyf∈Ωf.
Usingva=∑m=1Mvam=∑w∈W∑r∈Rw∑m∈Mfrwmδarw and substituting(15)∇fZf¯T=⋯,1θ+1θlnf¯rwm+∑a∈Atav¯aδarw+cfrw,⋯=⋯,1θ+1θlnf¯rwm+crwmf¯+cfrw,⋯.into (14), VI (13) can be obtained according to equation ∑w∈W∑r∈Rw∑m∈M1/θfrwm−f¯rwm=∑w∈W1/θdw−dw=0.
Under the time-based criterion,camva is given by(16)camva=tava,a∈A,m=1,2,⋯,M.
By contrast, under the monetary-based criterion,camva can be given by(17)camva=βmtava,a∈A,m=1,2,⋯,M.
Substituting (16) and (17) into (13), respectively, and using (1), we can get the following time-based VI and monetary-based VI, respectively.(18)∑a∈Atav¯va−v¯a+1θ∑w∈W∑r∈Rw∑m=1Mlnf¯rwm+θcfrwfrwm−f¯rwm≥0,∀f∈Ωf,∑a∈A∑m=1Mβmtav¯vam−v¯am+1θ∑w∈W∑r∈Rw∑m=1Mlnf¯rwm+θcfrwfrwm−f¯rwm≥0,∀f∈Ωf.


## 3. Bounding the Inefficiency of the Multiclass CL-SUE Compared with the Multiclass SO

### 3.1. Time Units

The multiclass SO problem in time units that minimizes the TSTT is presented as follows:(19)minv∈Ωv∑a∈Atavava.Letv^∈Ωv be the link flow solution of problem (19), the corresponding path flow solution is denoted by f^∈Ωf. Let v¯t∈Ωv be the link flow solution of the VI (18), the corresponding path flow solution is denoted by f¯t∈Ωf. The efficiency loss of the multiclass CL-SUE compared with the multiclass SO under time-based criterion is defined as(20)ρCL−SUEt=TCL−SUEtTSOt,where TCL−SUEt=∑w∈W∑r∈Rw∑m=1Mcrwmf¯tf¯rwm,t=∑a∈Atav¯atv¯at is the TSTT at the multiclass CL-SUE and TSOt=∑a∈Atav^av^a is the TSTT at the multiclass SO. Clearly, ρCL−SUEt≥1.Settingf¯=f¯t and f=f^ in VI (18), we can obtain inequality as follows:(21)∑a∈Atav¯atv^a−v¯at+1θ∑w∈W∑r∈Rw∑m=1Mlnf¯rwm,t+θcfrwf^rwm−f¯rwm,t≥0.This leads to(22)TCL−SUEt≤TSOt+∑a∈Atav¯at−tav^av^a+1θ∑w∈W∑r∈Rw∑m=1Mlnf¯rwm,t+θcfrwf^rwm−f¯rwm,t.Now, we begin to find the upper bound of the term∑a∈Atav¯at−tav^av^a in (22). To achieve this, we give the same way which has been used in [37]. For completeness, a brief introduction is given here. Because tava is increasing, we have tav¯at−tavava≤0 for va≥v¯at. Hence, we just need to pay attention to tav¯at−tavava for va<v¯at. As shown in Figure 1, let tav¯atv¯at denote the area of the large rectangle and tav¯at−tavava denote the area of the blue rectangle.Figure 1
Geometric illustration of the definition ofγφ.Next, an upper bound of the ratiotav¯at−tavava/tav¯atv¯at needs to be determined. To complete this, for each link time function ta=taza and nonnegative link flow za≥0, we let(23)γata,za=maxva≥0taza−tavavatazaza,a∈A.Sincetaza−tavava≤tazava when 0≤va≤za and taza−tavava≤0 when va>za, we can obtain 0≤γata,za≤1. Let φ denote a class of link time functions, we define(24)γφ=maxta∈φ,za≥0γata,zaWith definitions (23) and (24), the lemma is given as follows:Lemma 3.
Letv¯t be link flow at the multiclass CL-SUE and v denote an arbitrary nonnegative link flow. Then,(25)∑a∈Atav¯at−tavava≤γφTCL−SUEt.Proof of Lemma 3.
Settingza=v¯at in (23) and (24), we then obtain(26)∑a∈Atav¯at−tavava≤∑a∈Aγata,v¯attav¯atv¯at≤∑a∈Aγφtav¯atv¯at=γφTCL−SUEt.
This completes the proof.
Letva=v^a, we have(27)∑a∈Atav¯at−tav^av^a≤∑a∈Aγφtav¯atv¯at=γφTCL−SUEt.
We now begin to seek the upper bound on the third term of the right-hand side of (22). To achieve this, we give the lemma which has been proved in [39] below.Lemma 4.
The maximization problem is considered as follows:(28)maxFx,y=∑i=1nyi−xilnxi+θcfi,subject to(29)∑i=1nxi=d,∑i=1nyi=d,xi,yi≥0,i=1,2,⋯,n,where d>0 is a constant. Fmax=kd is the maximum value of Fx,y, where k solves equation kexpk+1=∑i=1,i≠jnexpθcfj−cfi and j=argmaxicfi,i=1,2,⋯,n.From Lemma4, we have(30)∑r∈Rwlnf¯rwm,t+θcfrwf^rwm−f¯rwm,t≤kwCL−SUEdwm,where kwCL−SUE solves the equation kexpk+1=∑r=1,r≠jRwexpθcfjw−cfrw with j=argmaxrcfrw,r∈Rw, w∈W, and Rw is the number of paths connecting OD pair w∈W. Substituting (27) and (30) into (22), it yields(31)TCL−SUEt≤TSOt+γφTCL−SUEt+1θ∑w∈W∑m=1MkwCL−SUEdwm.LetD=∑w∈W∑m=1Mdwm denote the total traffic demand, k¯=∑w∈W∑m=1Mdwm/DkwCL−SUE be the average of kwCL−SUE, and w∈W. Then, we can rewrite (31) as(32)TCL−SUEt≤TSOt+γφTCL−SUEt+1θk¯D.In addition, we further definec¯=TSOt/D as the actual average travel time of all travelers at multiclass SO. Then, the theorem is presented as follows:Theorem 1.
Letφ denote a class of differentiable, separable, convex, and monotonically increasing link time functions tava. Let TCL−SUEt be the TSTT at the multiclass CL-SUE and TSOt be the TSTT at the multiclass SO under time-based criterion. Then,(33)ρCL−SUEt=TCL−SUEtTSOt≤11−γφ1+k¯θc¯.Furthermore, we can have the following corollary by comparing the efficiency loss upper bounds of the multiclass CL-SUE and the multiclass SUE.Corollary 1.
In a transportation network, the efficiency loss upper bound against the multiclass SO by the multiclass CL-SUE under time-based criterion is not less than that by the multiclass SUE.Proof of Corollary 1.
Letv⟶∈Ωv be link flow solution of the VI (8), the corresponding path flow solution is denoted by f⟶∈Ωf. TSUEt=∑w∈W∑r∈Rw∑m=1Mcrwmf⟶f⟶rwm=∑a∈Atav⟶av⟶a is the TSTT at the multiclass SUE. The inefficiency upper bound of the multiclass SUE against the multiclass SO under time-based criterion was given by Yu et al. [38], i.e.,(34)ρSUEt=TSUEtTSOt≤11−γφ1+k⟶θc¯,where k⟶=∑w∈W∑m=1Mdwm/DkwSUE is the average of kwSUE, w∈W, and kwSUE solves the equation kexpk+1=Rw−1,w∈W.
We can see that the difference between (33) and (34) is only dependent upon the difference between k¯ and k⟶, or kwCL−SUE and kwSUE. kwCL−SUE is the solution of kexpk+1=∑r=1,r≠jRwexpθcfjw−cfrw with j=argmaxrcfrw,r∈Rw, w∈W. We always have ∑r=1,r≠jRwexpθcfjw−cfrw≥Rw−1, when j=argmaxrcfrw,r∈Rw, w∈W. Since fk=kexpk+1 is a nondecreasing function of k, we can obtain kwCL−SUE≥kwSUE, which implies that k¯≥k⟶. Hence, the upper bound (33) is not less than the upper bound (34). This completes the proof.
The above analyses show that the commonality factor reflecting path overlapping has a significant impact on the inefficiency upper bound (33). Therefore, it is meaningful to study the efficiency loss of the multiclass CL-SUE model, which provides a more realistic upper bound than the multiclass SUE model by considering the path overlapping problem.


### 3.2. Monetary Units

The multiclass SO problem in monetary units that minimizes the TSTC is presented as follows:(35)minv∈Ωv∑a∈A∑m=1Mβmtavavam.Letv˜∈Ωv be link flow solution of problem (35), the corresponding path flow solution is denoted by f˜∈Ωf. Let v¯c∈Ωv be link flow solution of the VI (18), the corresponding path flow solution is denoted by f¯c∈Ωf. The efficiency loss of the multiclass CL-SUE compared with the multiclass SO under monetary-based criterion is defined as(36)ρCL−SUEc=TCL−SUEcTSOc,where TCL−SUEc=∑w∈W∑r∈Rw∑m=1Mcrwmf¯cf¯rwm,c=∑a∈A∑m=1Mβmtav¯acv¯am,c is the TSTC at the multiclass CL-SUE and TSOc=∑a∈A∑m=1Mβmtav˜av˜am is the TSTC at the multiclass SO. Clearly, ρCL−SUEc≥1.Settingf¯=f¯c and f=f˜ in VI (18), we can obtain inequality as follows:(37)∑a∈A∑m=1Mβmtav¯acv˜am−v¯am,c+1θ∑w∈W∑r∈Rw∑m=1Mlnf¯rwm,c+θcfrwf˜rwm−f¯rwm,c≥0.This leads to(38)TCL−SUEc≤TSOc+∑a∈A∑m=1Mβmv˜amtav¯ac−tav˜a+1θ∑w∈W∑r∈Rw∑m=1Mlnf¯rwm,c+θcfrwf˜rwm−f¯rwm,c.To derive the upper bound of the term∑a∈A∑m=1Mβmv˜amtav¯ac−tav˜a in (38), we need to define a new parameter [43]. For each link time function ta=taza, nonnegative link flow za≥0, and the VOT βm,m=1,2,⋯,M, we define(39)γaza,ta,β=1∑m=1Mβmzamtazamaxvam≥0∑m=1Mβmvamtaza−tava.Here, suppose that0/0=0 always holds. For guaranteeing γaza,ta,β<1, we further define(40)γ¯φ,β=supta∈φ,a∈A1maxv¯am,c≥0γaza,ta,β,where A1=a∈A|γaza,ta,β<1.Define(41)γ˜φ,β=supta∈φgza,ta,β.And(42)gza,ta,β=maxvam≥0,a∉A1hx=∑m=1Mβmvamtaza−tava∑m=1Mβmvamtava.Hence, we can obtainγ˜φ,β>−1. Furthermore, hx⟶−1 when vam⟶+∞ and hx⟶+∞ when vam⟶0, m=1,2,⋯,M.Letva=v˜a and za=v¯ac in definition (39), we then have(43)∑m=1Mβmv˜amtav¯ac−tav˜a≤γav¯ac,ta,β∑m=1Mβmv¯am,ctav¯ac.Thus, we can obtain(44)∑a∈A∑m=1Mβmv˜amtav¯ac−tav˜a=∑a∈A1∑m=1Mβmv˜amtav¯ac−tav˜a+∑a∉A1∑m=1Mβmv˜amtav¯ac−tav˜a≤γ¯φ,βTCL−SUEc+γ˜φ,βTSOc.From Lemma4, the upper bound on the last term of the right-hand side of (38) can be provided by(45)∑r∈Rwlnf¯rwm,c+θcfrwf˜rwm−f¯rwm,c≤kwCL−SUEdwm.Substituting (44) and (45) into (38), it yields(46)TCL−SUEc≤TSOc+γ¯φ,βTCL−SUEc+γ˜φ,βTSOc+1θ∑w∈W∑m=1MkwCL−SUEdwm.In the same way, letD=∑w∈W∑m=1Mdwm denote the total traffic demand, k¯=∑w∈W∑m=1Mdwm/DkwCL−SUE denote the average of kwCL−SUE, and w∈W. Then, we can rewrite (46) as(47)TCL−SUEc≤TSOc+γ¯φ,βTCL−SUEc+γ˜φ,βTSOc+1θk¯D.Furthermore, we definec˜=TSOc/D as the actual average travel cost of all travelers at multiclass SO. Then, the theorem is presented as follows.Theorem 2.
Letφ denote a class of differentiable, separable, convex, and monotonically increasing link time functions tava. Let TCL−SUEc be the TSTC at the multiclass CL-SUE and TSOc be the TSTC at the multiclass SO under monetary-based criterion. Then,(48)ρCL−SUEc=TCL−SUEcTSOc≤1+γ˜φ,β+k¯/θc˜1−γ¯φ,β.


## 3.1. Time Units

The multiclass SO problem in time units that minimizes the TSTT is presented as follows:(19)minv∈Ωv∑a∈Atavava.Letv^∈Ωv be the link flow solution of problem (19), the corresponding path flow solution is denoted by f^∈Ωf. Let v¯t∈Ωv be the link flow solution of the VI (18), the corresponding path flow solution is denoted by f¯t∈Ωf. The efficiency loss of the multiclass CL-SUE compared with the multiclass SO under time-based criterion is defined as(20)ρCL−SUEt=TCL−SUEtTSOt,where TCL−SUEt=∑w∈W∑r∈Rw∑m=1Mcrwmf¯tf¯rwm,t=∑a∈Atav¯atv¯at is the TSTT at the multiclass CL-SUE and TSOt=∑a∈Atav^av^a is the TSTT at the multiclass SO. Clearly, ρCL−SUEt≥1.Settingf¯=f¯t and f=f^ in VI (18), we can obtain inequality as follows:(21)∑a∈Atav¯atv^a−v¯at+1θ∑w∈W∑r∈Rw∑m=1Mlnf¯rwm,t+θcfrwf^rwm−f¯rwm,t≥0.This leads to(22)TCL−SUEt≤TSOt+∑a∈Atav¯at−tav^av^a+1θ∑w∈W∑r∈Rw∑m=1Mlnf¯rwm,t+θcfrwf^rwm−f¯rwm,t.Now, we begin to find the upper bound of the term∑a∈Atav¯at−tav^av^a in (22). To achieve this, we give the same way which has been used in [37]. For completeness, a brief introduction is given here. Because tava is increasing, we have tav¯at−tavava≤0 for va≥v¯at. Hence, we just need to pay attention to tav¯at−tavava for va<v¯at. As shown in Figure 1, let tav¯atv¯at denote the area of the large rectangle and tav¯at−tavava denote the area of the blue rectangle.Figure 1
Geometric illustration of the definition ofγφ.Next, an upper bound of the ratiotav¯at−tavava/tav¯atv¯at needs to be determined. To complete this, for each link time function ta=taza and nonnegative link flow za≥0, we let(23)γata,za=maxva≥0taza−tavavatazaza,a∈A.Sincetaza−tavava≤tazava when 0≤va≤za and taza−tavava≤0 when va>za, we can obtain 0≤γata,za≤1. Let φ denote a class of link time functions, we define(24)γφ=maxta∈φ,za≥0γata,zaWith definitions (23) and (24), the lemma is given as follows:Lemma 3.
Letv¯t be link flow at the multiclass CL-SUE and v denote an arbitrary nonnegative link flow. Then,(25)∑a∈Atav¯at−tavava≤γφTCL−SUEt.Proof of Lemma 3.
Settingza=v¯at in (23) and (24), we then obtain(26)∑a∈Atav¯at−tavava≤∑a∈Aγata,v¯attav¯atv¯at≤∑a∈Aγφtav¯atv¯at=γφTCL−SUEt.
This completes the proof.
Letva=v^a, we have(27)∑a∈Atav¯at−tav^av^a≤∑a∈Aγφtav¯atv¯at=γφTCL−SUEt.
We now begin to seek the upper bound on the third term of the right-hand side of (22). To achieve this, we give the lemma which has been proved in [39] below.Lemma 4.
The maximization problem is considered as follows:(28)maxFx,y=∑i=1nyi−xilnxi+θcfi,subject to(29)∑i=1nxi=d,∑i=1nyi=d,xi,yi≥0,i=1,2,⋯,n,where d>0 is a constant. Fmax=kd is the maximum value of Fx,y, where k solves equation kexpk+1=∑i=1,i≠jnexpθcfj−cfi and j=argmaxicfi,i=1,2,⋯,n.From Lemma4, we have(30)∑r∈Rwlnf¯rwm,t+θcfrwf^rwm−f¯rwm,t≤kwCL−SUEdwm,where kwCL−SUE solves the equation kexpk+1=∑r=1,r≠jRwexpθcfjw−cfrw with j=argmaxrcfrw,r∈Rw, w∈W, and Rw is the number of paths connecting OD pair w∈W. Substituting (27) and (30) into (22), it yields(31)TCL−SUEt≤TSOt+γφTCL−SUEt+1θ∑w∈W∑m=1MkwCL−SUEdwm.LetD=∑w∈W∑m=1Mdwm denote the total traffic demand, k¯=∑w∈W∑m=1Mdwm/DkwCL−SUE be the average of kwCL−SUE, and w∈W. Then, we can rewrite (31) as(32)TCL−SUEt≤TSOt+γφTCL−SUEt+1θk¯D.In addition, we further definec¯=TSOt/D as the actual average travel time of all travelers at multiclass SO. Then, the theorem is presented as follows:Theorem 1.
Letφ denote a class of differentiable, separable, convex, and monotonically increasing link time functions tava. Let TCL−SUEt be the TSTT at the multiclass CL-SUE and TSOt be the TSTT at the multiclass SO under time-based criterion. Then,(33)ρCL−SUEt=TCL−SUEtTSOt≤11−γφ1+k¯θc¯.Furthermore, we can have the following corollary by comparing the efficiency loss upper bounds of the multiclass CL-SUE and the multiclass SUE.Corollary 1.
In a transportation network, the efficiency loss upper bound against the multiclass SO by the multiclass CL-SUE under time-based criterion is not less than that by the multiclass SUE.Proof of Corollary 1.
Letv⟶∈Ωv be link flow solution of the VI (8), the corresponding path flow solution is denoted by f⟶∈Ωf. TSUEt=∑w∈W∑r∈Rw∑m=1Mcrwmf⟶f⟶rwm=∑a∈Atav⟶av⟶a is the TSTT at the multiclass SUE. The inefficiency upper bound of the multiclass SUE against the multiclass SO under time-based criterion was given by Yu et al. [38], i.e.,(34)ρSUEt=TSUEtTSOt≤11−γφ1+k⟶θc¯,where k⟶=∑w∈W∑m=1Mdwm/DkwSUE is the average of kwSUE, w∈W, and kwSUE solves the equation kexpk+1=Rw−1,w∈W.
We can see that the difference between (33) and (34) is only dependent upon the difference between k¯ and k⟶, or kwCL−SUE and kwSUE. kwCL−SUE is the solution of kexpk+1=∑r=1,r≠jRwexpθcfjw−cfrw with j=argmaxrcfrw,r∈Rw, w∈W. We always have ∑r=1,r≠jRwexpθcfjw−cfrw≥Rw−1, when j=argmaxrcfrw,r∈Rw, w∈W. Since fk=kexpk+1 is a nondecreasing function of k, we can obtain kwCL−SUE≥kwSUE, which implies that k¯≥k⟶. Hence, the upper bound (33) is not less than the upper bound (34). This completes the proof.
The above analyses show that the commonality factor reflecting path overlapping has a significant impact on the inefficiency upper bound (33). Therefore, it is meaningful to study the efficiency loss of the multiclass CL-SUE model, which provides a more realistic upper bound than the multiclass SUE model by considering the path overlapping problem.


## 3.2. Monetary Units

The multiclass SO problem in monetary units that minimizes the TSTC is presented as follows:(35)minv∈Ωv∑a∈A∑m=1Mβmtavavam.Letv˜∈Ωv be link flow solution of problem (35), the corresponding path flow solution is denoted by f˜∈Ωf. Let v¯c∈Ωv be link flow solution of the VI (18), the corresponding path flow solution is denoted by f¯c∈Ωf. The efficiency loss of the multiclass CL-SUE compared with the multiclass SO under monetary-based criterion is defined as(36)ρCL−SUEc=TCL−SUEcTSOc,where TCL−SUEc=∑w∈W∑r∈Rw∑m=1Mcrwmf¯cf¯rwm,c=∑a∈A∑m=1Mβmtav¯acv¯am,c is the TSTC at the multiclass CL-SUE and TSOc=∑a∈A∑m=1Mβmtav˜av˜am is the TSTC at the multiclass SO. Clearly, ρCL−SUEc≥1.Settingf¯=f¯c and f=f˜ in VI (18), we can obtain inequality as follows:(37)∑a∈A∑m=1Mβmtav¯acv˜am−v¯am,c+1θ∑w∈W∑r∈Rw∑m=1Mlnf¯rwm,c+θcfrwf˜rwm−f¯rwm,c≥0.This leads to(38)TCL−SUEc≤TSOc+∑a∈A∑m=1Mβmv˜amtav¯ac−tav˜a+1θ∑w∈W∑r∈Rw∑m=1Mlnf¯rwm,c+θcfrwf˜rwm−f¯rwm,c.To derive the upper bound of the term∑a∈A∑m=1Mβmv˜amtav¯ac−tav˜a in (38), we need to define a new parameter [43]. For each link time function ta=taza, nonnegative link flow za≥0, and the VOT βm,m=1,2,⋯,M, we define(39)γaza,ta,β=1∑m=1Mβmzamtazamaxvam≥0∑m=1Mβmvamtaza−tava.Here, suppose that0/0=0 always holds. For guaranteeing γaza,ta,β<1, we further define(40)γ¯φ,β=supta∈φ,a∈A1maxv¯am,c≥0γaza,ta,β,where A1=a∈A|γaza,ta,β<1.Define(41)γ˜φ,β=supta∈φgza,ta,β.And(42)gza,ta,β=maxvam≥0,a∉A1hx=∑m=1Mβmvamtaza−tava∑m=1Mβmvamtava.Hence, we can obtainγ˜φ,β>−1. Furthermore, hx⟶−1 when vam⟶+∞ and hx⟶+∞ when vam⟶0, m=1,2,⋯,M.Letva=v˜a and za=v¯ac in definition (39), we then have(43)∑m=1Mβmv˜amtav¯ac−tav˜a≤γav¯ac,ta,β∑m=1Mβmv¯am,ctav¯ac.Thus, we can obtain(44)∑a∈A∑m=1Mβmv˜amtav¯ac−tav˜a=∑a∈A1∑m=1Mβmv˜amtav¯ac−tav˜a+∑a∉A1∑m=1Mβmv˜amtav¯ac−tav˜a≤γ¯φ,βTCL−SUEc+γ˜φ,βTSOc.From Lemma4, the upper bound on the last term of the right-hand side of (38) can be provided by(45)∑r∈Rwlnf¯rwm,c+θcfrwf˜rwm−f¯rwm,c≤kwCL−SUEdwm.Substituting (44) and (45) into (38), it yields(46)TCL−SUEc≤TSOc+γ¯φ,βTCL−SUEc+γ˜φ,βTSOc+1θ∑w∈W∑m=1MkwCL−SUEdwm.In the same way, letD=∑w∈W∑m=1Mdwm denote the total traffic demand, k¯=∑w∈W∑m=1Mdwm/DkwCL−SUE denote the average of kwCL−SUE, and w∈W. Then, we can rewrite (46) as(47)TCL−SUEc≤TSOc+γ¯φ,βTCL−SUEc+γ˜φ,βTSOc+1θk¯D.Furthermore, we definec˜=TSOc/D as the actual average travel cost of all travelers at multiclass SO. Then, the theorem is presented as follows.Theorem 2.
Letφ denote a class of differentiable, separable, convex, and monotonically increasing link time functions tava. Let TCL−SUEc be the TSTC at the multiclass CL-SUE and TSOc be the TSTC at the multiclass SO under monetary-based criterion. Then,(48)ρCL−SUEc=TCL−SUEcTSOc≤1+γ˜φ,β+k¯/θc˜1−γ¯φ,β.


## 4. Bounding the Inefficiency of the Multiclass CL-SUE Compared with the Multiclass CL-SSO

Before analyzing the inefficiency of the multiclass CL-SUE against the multiclass CL-SSO, we first give a brief introduction to the corresponding multiclass CL-SSO model. Considering commonality factor reflecting path overlapping, we establish the multiclass CL-SSO model, which is the extension of research achievements in [39, 48]. The definition of SSO given by Maher et al. [48] states that the SSO problem is to minimize the TPTT. Therefore, the multiclass CL-SSO problem is also to minimize the TPTT. For the multiclass CL-SUE model, the TPTT in the transportation network can be provided by (the process of proof is shown in Appendix A)(49)Ff=∑w∈W∑r∈Rw∑m=1Mfrwmcrwmf+cfrw+1θ∑w∈W∑r∈Rw∑m=1Mfrwmlnfrwm−1θ∑w∈W∑m=1Mdwmlndwm.Substituting (16) and (17) into (49), respectively, and in view of (1), the minimization of TPTT can be formulated as the following minimization problem under time-based criterion and monetary-based criterion, respectively.(50)minf∈ΩfFtf=∑a∈Atavava+∑w∈W∑r∈Rw∑m=1Mcfrwfrwm+1θ∑w∈W∑r∈Rw∑m=1Mfrwmlnfrwm−1θ∑w∈W∑m=1Mdwmlndwm.(51)minf∈ΩfFcf=∑a∈A∑m=1Mβmtavavam+∑w∈W∑r∈Rw∑m=1Mcfrwfrwm+1θ∑w∈W∑r∈Rw∑m=1Mfrwmlnfrwm−1θ∑w∈W∑m=1Mdwmlndwm.Letf⌢∈Ωf be path flow solution of problem (50), the corresponding link flow solution is denoted by v⌢∈Ωv. Then, the minimum TPTT is denoted by FCL−SSOt=Ftf⌢. Let f⌣∈Ωf be path flow solution of problem (51), the corresponding link flow solution is denoted by v⌣∈Ωv. Then, the minimum total perceived travel cost (TPTC) is denoted by FCL−SSOc=Fcf⌣. They are given by(52)FCL−SSOt=∑a∈Atav⌢av⌢a+∑w∈W∑r∈Rw∑m=1Mcfrwf⌢rwm+1θ∑w∈W∑r∈Rw∑m=1Mf⌢rwmlnf⌢rwm−1θ∑w∈W∑m=1Mdwmlndwm.(53)FCL−SSOc=∑a∈A∑m=1Mβmtav⌣av⌣am+∑w∈W∑r∈Rw∑m=1Mcfrwf⌣rwm+1θ∑w∈W∑r∈Rw∑m=1Mf⌣rwmlnf⌣rwm−1θ∑w∈W∑m=1Mdwmlndwm.Correspondingly, letFCL−SUEt and FCL−SUEc denote the TPTT and the TPTC at the multiclass CL-SUE, respectively. Then, we have(54)FCL−SUEt=∑a∈Atav¯atv¯at+∑w∈W∑r∈Rw∑m=1Mcfrwf¯rwm,t+1θ∑w∈W∑r∈Rw∑m=1Mf¯rwm,tlnf¯rwm,t−1θ∑w∈W∑m=1Mdwmlndwm,FCL−SUEc=∑a∈A∑m=1Mβmtav¯acv¯am,c+∑w∈W∑r∈Rw∑m=1Mcfrwf¯rwm,c+1θ∑w∈W∑r∈Rw∑m=1Mf¯rwm,clnf¯rwm,c−1θ∑w∈W∑m=1Mdwmlndwm.By definition, we easily haveFCL−SUEt≥FCL−SSOt and FCL−SUEc≥FCL−SSOc. However, it can be found from (52)–(54) that FCL−SSOt, FCL−SSOc, FCL−SUEt, and FCL−SUEc may be negative, which implies that the ratio FCL−SUEt/FCL−SSOt and FCL−SUEc/FCL−SSOc may be meaningless. Therefore, instead of using the ratio FCL−SUEt/FCL−SSOt and FCL−SUEc/FCL−SSOc, we use the terms FCL−SUEt−FCL−SSOt≥0 and FCL−SUEc−FCL−SSOc≥0 to quantify the absolute inefficiency of the multiclass CL-SUE against the multiclass CL-SSO under time-based criterion and monetary-based criterion, respectively. They are defined as(55)ρCL−SUE/CL−SSOt=FCL−SUEt−FCL−SSOt,ρCL−SUE/CL−SSOc=FCL−SUEc−FCL−SSOc.


### 4.1. Time Units

Settingf¯=f¯t and f=f⌢ in VI (18), we can obtain inequality as follows:(56)∑a∈Atav¯atv⌢a−v¯at+1θ∑w∈W∑r∈Rw∑m=1Mlnf¯rwm,t+θcfrwf⌢rwm−f¯rwm,t≥0.This leads to(57)∑a∈Atav¯atv¯at+∑w∈W∑r∈Rw∑m=1Mcfrwf¯rwm,t+1θ∑w∈W∑r∈Rw∑m=1Mf¯rwm,tlnf¯rwm,t≤∑a∈Atav⌢av⌢a+∑w∈W∑r∈Rw∑m=1Mcfrwf⌢rwm+1θ∑w∈W∑r∈Rw∑m=1Mf⌢rwmlnf⌢rwm+∑a∈Atav¯at−tav⌢av⌢a+1θ∑w∈W∑r∈Rw∑m=1Mf⌢rwmlnf¯rwm,t−lnf⌢rwm.Thus,(58)FCL−SUEt−FCL−SSOt≤∑a∈Atav¯at−tav⌢av⌢a+1θ∑w∈W∑r∈Rw∑m=1Mf⌢rwmlnf¯rwm,t−lnf⌢rwm.We can get the upper bound of the term∑a∈Atav¯at−tav⌢av⌢a in (58) from Lemma 3. Let va=v⌢a, we can obtain inequality below.(59)∑a∈Atav¯at−tav⌢av⌢a≤γφTCL−SUEt.The upper bound on the last term of the right-hand side of (58) is equal to zero from Gibbs’ inequality. Therefore, the following inequality holds:(60)∑r∈Rwf⌢rwmlnf¯rwm,t−lnf⌢rwm≤0,w∈W,m∈M.Here,∑r∈Rwf⌢rwmlnf¯rwm,t−lnf⌢rwm=0 if and only if f¯rwm,t=f⌢rwm. Substituting (59) and (60) into (58), the following theorem can be obtained.Theorem 3.
Letφ denote a class of differentiable, separable, convex, and monotonically increasing link time functions tava. Then, the absolute inefficiency of the multiclass CL-SUE against the multiclass CL-SSO under time-based criterion, ρCL−SUE/CL−SSOt, is upper bounded, i.e.,(61)ρCL−SUE/CL−SSOt=FCL−SUEt−FCL−SSOt≤γφTCL−SUEt.We now begin to discuss the tightness of the bound given in (61) and provide Corollary 2 (the similar process of proof is shown in Guo et al. [37]).Corollary 2.
FCL−SUEt−FCL−SSOt=γφTCL−SUEt if and only if γφ=0.Corollary2 It states that the upper bound (61) is tight if and only if γφ=0 (without traffic congestion). Here, we have f¯t=f⌢ and FCL−SUEt−FCL−SSOt. However, traffic congestion is a common phenomenon in a realistic transportation network. As a result, we always have FCL−SUEt−FCL−SSOt<γφTCL−SUEt, which means that the upper bound (61) is usually not tight in most cases.


### 4.2. Monetary Units

Settingf¯=f¯c and f=f⌣ in VI (18), we can obtain the inequality as follows:(62)∑a∈A∑m=1Mβmtav¯acv⌣am−v¯am,c+1θ∑w∈W∑r∈Rw∑m=1Mlnf¯rwm,c+θcfrwf⌣rwm−f¯rwm,c≥0.This leads to(63)∑a∈A∑m=1Mβmtav¯acv¯am,c+∑w∈W∑r∈Rw∑m=1Mcfrwf¯rwm,c+1θ∑w∈W∑r∈Rw∑m=1Mf¯rwm,clnf¯rwm,c≤∑a∈A∑m=1Mβmtav⌣av⌣am+∑w∈W∑r∈Rw∑m=1Mcfrwf⌣rwm+1θ∑w∈W∑r∈Rw∑m=1Mf⌣rwmlnf⌣rwm+∑a∈A∑m=1Mβmv⌣amtav¯ac−tav⌣a+1θ∑w∈W∑r∈Rw∑m=1Mf⌣rwmlnf¯rwm,c−lnf⌣rwm.Thus,(64)FCL−SUEc−FCL−SSOc≤∑a∈A∑m=1Mβmv⌣amtav¯ac−tav⌣a+1θ∑w∈W∑r∈Rw∑m=1Mf⌣rwmlnf¯rwm,c−lnf⌣rwm.We can get the upper bound of the term∑a∈A∑m=1Mβmv⌣amtav¯ac−tav⌣a in (64) by applying the definitions (39)–(42). Let va be v⌣a and za be v¯ac, then we have(65)∑a∈A∑m=1Mβmv⌣amtav¯ac−tav⌣a=∑a∈A1∑m=1Mβmv⌣amtav¯ac−tav⌣a+∑a∉A1∑m=1Mβmv⌣amtav¯ac−tav⌣a≤γ¯φ,βTCL−SUEc+γ˜φ,βTCL−SSOc,where TCL−SSOc=∑a∈A∑m=1Mβmtav⌣av⌣am is the TSTC at the multiclass CL-SSO.The upper bound on the last term of the right-hand side of (64) is equal to zero from Gibbs’ inequality. Therefore, the following inequality holds:(66)∑r∈Rwf⌣rwmlnf¯rwm,c−lnf⌣rwm≤0,w∈W,m∈M.Here,∑r∈Rwf⌣rwmlnf¯rwm,c−lnf⌣rwm=0 if and only if f¯rwm,c=f⌣rwm. Substituting (65) and (66) into (64), we can obtain the theorem as follows.Theorem 4.
Letφ denote a class of differentiable, separable, convex, and monotonically increasing link time functions tava. Then, the absolute inefficiency of the multiclass CL-SUE against the multiclass CL-SSO under monetary-based criterion, ρCL−SUE/CL−SSOc, is upper bounded, i.e.,(67)ρCL−SUE/CL−SSOc=FCL−SUEc−FCL−SSOc≤γ¯φ,βTCL−SUEc+γ˜φ,βTCL−SSOc.Next, we will discuss the tightness of the bound given in (67) and provide Corollary 3 as follows.Corollary 3.
FCL−SUEc−FCL−SSOc=γ¯φ,βTCL−SUEc+γ˜φ,βTCL−SSOc if and only if γ¯φ,β=γ˜φ,β=0.Proof of Corollary 3.
Firstly, ifγ¯φ,β=γ˜φ,β=0, we can obtain FCL−SUEc−FCL−SSOc≤0 from Theorem 4. According to the definition of the multiclass CL-SSO, we have FCL−SUEc≥FCL−SSOc. Hence, we can obtain FCL−SUEc=FCL−SSOc, which means that FCL−SUEc−FCL−SSOc=0. Since γ¯φ,β=γ˜φ,β=0, we have γ¯φ,βTCL−SUEc+γ˜φ,βTCL−SSOc=0. Therefore, FCL−SUEc−FCL−SSOc=γ¯φ,βTCL−SUEc+γ˜φ,βTCL−SSOc if γ¯φ,β=γ˜φ,β=0. Secondly, we assume that FCL−SUEc−FCL−SSOc=γ¯φ,βTCL−SUEc+γ˜φ,βTCL−SSOc holds. From the specific derivation process of (67), FCL−SUEc−FCL−SSOc=γ¯φ,βTCL−SUEc+γ˜φ,βTCL−SSOc implies that inequality (66) takes equality; i.e., f¯c=f⌣. Since f¯c=f⌣, we can have v¯c=v⌣, FCL−SUEc=FCL−SSOc, and TCL−SUEc=TCL−SSOc. With definitions (39)–(42), if v¯c=v⌣ holds, we can obtain γ¯φ,β=γ˜φ,β=0. The proof is completed.
Corollary 3 shows that the upper bound (67) is tight if and only if γ¯φ,β=γ˜φ,β=0. The expression γ¯φ,β=γ˜φ,β=0 means that the multiclass CL-SUE state is equivalent to the multiclass CL-SSO state. Here, we have f¯c=f⌣, v¯c=v⌣, FCL−SUEc=FCL−SSOc, and TCL−SUEc=TCL−SSOc, which are usually not satisfied in a realistic transportation network. As a result, we always have FCL−SUEc−FCL−SSOc<γ¯φ,βTCL−SUEc+γ˜φ,βTCL−SSOc, which means that the upper bound (67) is usually not tight in most cases.


## 4.1. Time Units

Settingf¯=f¯t and f=f⌢ in VI (18), we can obtain inequality as follows:(56)∑a∈Atav¯atv⌢a−v¯at+1θ∑w∈W∑r∈Rw∑m=1Mlnf¯rwm,t+θcfrwf⌢rwm−f¯rwm,t≥0.This leads to(57)∑a∈Atav¯atv¯at+∑w∈W∑r∈Rw∑m=1Mcfrwf¯rwm,t+1θ∑w∈W∑r∈Rw∑m=1Mf¯rwm,tlnf¯rwm,t≤∑a∈Atav⌢av⌢a+∑w∈W∑r∈Rw∑m=1Mcfrwf⌢rwm+1θ∑w∈W∑r∈Rw∑m=1Mf⌢rwmlnf⌢rwm+∑a∈Atav¯at−tav⌢av⌢a+1θ∑w∈W∑r∈Rw∑m=1Mf⌢rwmlnf¯rwm,t−lnf⌢rwm.Thus,(58)FCL−SUEt−FCL−SSOt≤∑a∈Atav¯at−tav⌢av⌢a+1θ∑w∈W∑r∈Rw∑m=1Mf⌢rwmlnf¯rwm,t−lnf⌢rwm.We can get the upper bound of the term∑a∈Atav¯at−tav⌢av⌢a in (58) from Lemma 3. Let va=v⌢a, we can obtain inequality below.(59)∑a∈Atav¯at−tav⌢av⌢a≤γφTCL−SUEt.The upper bound on the last term of the right-hand side of (58) is equal to zero from Gibbs’ inequality. Therefore, the following inequality holds:(60)∑r∈Rwf⌢rwmlnf¯rwm,t−lnf⌢rwm≤0,w∈W,m∈M.Here,∑r∈Rwf⌢rwmlnf¯rwm,t−lnf⌢rwm=0 if and only if f¯rwm,t=f⌢rwm. Substituting (59) and (60) into (58), the following theorem can be obtained.Theorem 3.
Letφ denote a class of differentiable, separable, convex, and monotonically increasing link time functions tava. Then, the absolute inefficiency of the multiclass CL-SUE against the multiclass CL-SSO under time-based criterion, ρCL−SUE/CL−SSOt, is upper bounded, i.e.,(61)ρCL−SUE/CL−SSOt=FCL−SUEt−FCL−SSOt≤γφTCL−SUEt.We now begin to discuss the tightness of the bound given in (61) and provide Corollary 2 (the similar process of proof is shown in Guo et al. [37]).Corollary 2.
FCL−SUEt−FCL−SSOt=γφTCL−SUEt if and only if γφ=0.Corollary2 It states that the upper bound (61) is tight if and only if γφ=0 (without traffic congestion). Here, we have f¯t=f⌢ and FCL−SUEt−FCL−SSOt. However, traffic congestion is a common phenomenon in a realistic transportation network. As a result, we always have FCL−SUEt−FCL−SSOt<γφTCL−SUEt, which means that the upper bound (61) is usually not tight in most cases.


## 4.2. Monetary Units

Settingf¯=f¯c and f=f⌣ in VI (18), we can obtain the inequality as follows:(62)∑a∈A∑m=1Mβmtav¯acv⌣am−v¯am,c+1θ∑w∈W∑r∈Rw∑m=1Mlnf¯rwm,c+θcfrwf⌣rwm−f¯rwm,c≥0.This leads to(63)∑a∈A∑m=1Mβmtav¯acv¯am,c+∑w∈W∑r∈Rw∑m=1Mcfrwf¯rwm,c+1θ∑w∈W∑r∈Rw∑m=1Mf¯rwm,clnf¯rwm,c≤∑a∈A∑m=1Mβmtav⌣av⌣am+∑w∈W∑r∈Rw∑m=1Mcfrwf⌣rwm+1θ∑w∈W∑r∈Rw∑m=1Mf⌣rwmlnf⌣rwm+∑a∈A∑m=1Mβmv⌣amtav¯ac−tav⌣a+1θ∑w∈W∑r∈Rw∑m=1Mf⌣rwmlnf¯rwm,c−lnf⌣rwm.Thus,(64)FCL−SUEc−FCL−SSOc≤∑a∈A∑m=1Mβmv⌣amtav¯ac−tav⌣a+1θ∑w∈W∑r∈Rw∑m=1Mf⌣rwmlnf¯rwm,c−lnf⌣rwm.We can get the upper bound of the term∑a∈A∑m=1Mβmv⌣amtav¯ac−tav⌣a in (64) by applying the definitions (39)–(42). Let va be v⌣a and za be v¯ac, then we have(65)∑a∈A∑m=1Mβmv⌣amtav¯ac−tav⌣a=∑a∈A1∑m=1Mβmv⌣amtav¯ac−tav⌣a+∑a∉A1∑m=1Mβmv⌣amtav¯ac−tav⌣a≤γ¯φ,βTCL−SUEc+γ˜φ,βTCL−SSOc,where TCL−SSOc=∑a∈A∑m=1Mβmtav⌣av⌣am is the TSTC at the multiclass CL-SSO.The upper bound on the last term of the right-hand side of (64) is equal to zero from Gibbs’ inequality. Therefore, the following inequality holds:(66)∑r∈Rwf⌣rwmlnf¯rwm,c−lnf⌣rwm≤0,w∈W,m∈M.Here,∑r∈Rwf⌣rwmlnf¯rwm,c−lnf⌣rwm=0 if and only if f¯rwm,c=f⌣rwm. Substituting (65) and (66) into (64), we can obtain the theorem as follows.Theorem 4.
Letφ denote a class of differentiable, separable, convex, and monotonically increasing link time functions tava. Then, the absolute inefficiency of the multiclass CL-SUE against the multiclass CL-SSO under monetary-based criterion, ρCL−SUE/CL−SSOc, is upper bounded, i.e.,(67)ρCL−SUE/CL−SSOc=FCL−SUEc−FCL−SSOc≤γ¯φ,βTCL−SUEc+γ˜φ,βTCL−SSOc.Next, we will discuss the tightness of the bound given in (67) and provide Corollary 3 as follows.Corollary 3.
FCL−SUEc−FCL−SSOc=γ¯φ,βTCL−SUEc+γ˜φ,βTCL−SSOc if and only if γ¯φ,β=γ˜φ,β=0.Proof of Corollary 3.
Firstly, ifγ¯φ,β=γ˜φ,β=0, we can obtain FCL−SUEc−FCL−SSOc≤0 from Theorem 4. According to the definition of the multiclass CL-SSO, we have FCL−SUEc≥FCL−SSOc. Hence, we can obtain FCL−SUEc=FCL−SSOc, which means that FCL−SUEc−FCL−SSOc=0. Since γ¯φ,β=γ˜φ,β=0, we have γ¯φ,βTCL−SUEc+γ˜φ,βTCL−SSOc=0. Therefore, FCL−SUEc−FCL−SSOc=γ¯φ,βTCL−SUEc+γ˜φ,βTCL−SSOc if γ¯φ,β=γ˜φ,β=0. Secondly, we assume that FCL−SUEc−FCL−SSOc=γ¯φ,βTCL−SUEc+γ˜φ,βTCL−SSOc holds. From the specific derivation process of (67), FCL−SUEc−FCL−SSOc=γ¯φ,βTCL−SUEc+γ˜φ,βTCL−SSOc implies that inequality (66) takes equality; i.e., f¯c=f⌣. Since f¯c=f⌣, we can have v¯c=v⌣, FCL−SUEc=FCL−SSOc, and TCL−SUEc=TCL−SSOc. With definitions (39)–(42), if v¯c=v⌣ holds, we can obtain γ¯φ,β=γ˜φ,β=0. The proof is completed.
Corollary 3 shows that the upper bound (67) is tight if and only if γ¯φ,β=γ˜φ,β=0. The expression γ¯φ,β=γ˜φ,β=0 means that the multiclass CL-SUE state is equivalent to the multiclass CL-SSO state. Here, we have f¯c=f⌣, v¯c=v⌣, FCL−SUEc=FCL−SSOc, and TCL−SUEc=TCL−SSOc, which are usually not satisfied in a realistic transportation network. As a result, we always have FCL−SUEc−FCL−SSOc<γ¯φ,βTCL−SUEc+γ˜φ,βTCL−SSOc, which means that the upper bound (67) is usually not tight in most cases.


## 5. Effects of Parameters on the Inefficiency Bounds

This section discusses the effects of various parameters on the upper bounds (33), (48), (61), and (67), namely, γφ, γ¯φ,β, γ˜φ,β, k¯, θ, c¯, and c˜.γφ∈0,1 is a dimensionless coefficient defined only by the class of link time functions. Both the upper bounds (33) and (61) are monotonically increasing functions of γφ. Consider a widely used class of link travel time functions, tava=ta0+αavap,a∈A, where ta0≥0 denotes free-flow travel time on link a∈A, αa≥0 is a constant, and p≥0 reflects the degree of traffic congestion. Roughgarden [27] provided a specific expression of γφ as follows:(68)γφ=pp+11p+11/p.Equation (68) shows that γφ⟶0 when p⟶0 (without traffic congestion) and γφ⟶0 when p⟶+∞ (with severe congestion). When p=1 and 4, γφ=0.25 and 0.535, respectively. So, the upper bounds (33) and (61) are both monotonically increasing functions of p. When the value of p can be reduced, we will have more space to improve the congestion in the traffic network by driving the multiclass CL-SUE state to the multiclass SO or the multiclass CL-SSO state.Bothγ¯φ,β and γ˜φ,β are dimensionless coefficients depending on the class of link time functions and VOT β. Both the upper bounds (48) and (67) are monotonically increasing functions of γ¯φ,β and γ˜φ,β.Recall thatkwCL−SUE solves the equation kexpk+1=∑r=1,r≠jRwexpθcfjw−cfrw with j=argmaxrcfrw,r∈Rw, w∈W, and k¯=∑w∈W∑m=1Mdwm/DkwCL−SUE. So, k¯ is a dimensionless coefficient, which increases with the relative values of the commonality factors of paths and the number of feasible paths. Hence, k¯ can reflect the degree of network complexity. Let j′=argminrcfrw,r∈Rw, w∈W, then we have kwCL−SUEexpkwCL−SUE+1≤Rw−1expθcfjw−cfj′w. If each OD pair has only one available path in a transportation network, i.e., Rw=1, we can obtain kwCL−SUE=0 and thus k¯=0. When Rw=1, we have ρCL−SUEt≤1−γφ−1 and ρCL−SUEc≤1+γ˜φ,β/1−γ¯φ,β. When Rw>1, the value of kwCL−SUE (and hence k¯) is greatly limited only if values of θ and cfrw are given (the similar discussion is shown in Guo et al. [37]). Even though the effect is small, both the upper bounds (33) and (48) are increasing with the degree of network complexity.Parameterθ is the perception error of travel time, which can reflect the degree of network familiarity. Both the upper bounds (33) and (48) decrease with θ. When θ⟶+∞, we have ρCL−SUEt≤1−γφ−1 and ρCL−SUEc≤1+γ˜φ,β/1−γ¯φ,β, which are the results of the standard multiclass UE problem under time-based criterion and monetary-based criterion, respectively.Theorems1 and 2 show that the upper bound (33) decreases with c¯ and the upper bound (48) decreases with c˜, respectively. Since c¯=TSOt/D and c˜=TSOc/D, both the upper bounds (33) and (48) will increase when the total demand, D, goes up.Finally, the results of the above discussions are summarized in Table2.Table 2
Effects of various parameters on the upper bounds.
Congestion degreeγ¯φ,βγ˜φ,βNetwork complexityNetwork familiarityTotal demandBound (33)+NoNo+—+Bound (48)No+++—+Bound (61)+NoNoNoNoNoBound (67)No++NoNoNo


## 6. Summary of the Main Research Findings

In Sections3 and 4, we have derived four inefficiency bounds of the multiclass CL-SUE, and given four theorems. In this section, we provide a table to summarize the main research findings of four theorems in this article. These findings are shown in Table 3.Table 3
The main research findings of four theorems.
TheoremThe upper boundsMain research findingsTheorem1ρCL−SUEt=TCL−SUEt/TSOt≤1/1−γφ1+k¯/θc¯(1) The upper bound (33) depends on four parameters, namely, γφ, k¯, θ, and c¯(2) Corollary 1: in a transportation network, the efficiency loss upper bound against the multiclass SO by the multiclass CL-SUE under time-based criterion is not less than that by the multiclass SUE. Corollary 1 shows that the multiclass CL-SUE model provides a more realistic upper bound than the multiclass SUE model by considering the path overlapping problem.Theorem2ρCL−SUEc=TCL−SUEc/TSOc≤1+γ˜φ,β+k¯/θc˜/1−γ¯φ,β(1) The upper bound (48) depends on five parameters, namely, γ¯φ,β, γ˜φ,β, k¯, θ, and c˜.(2) Similar to the proof of Corollary 1, we can find that the efficiency loss upper bound against the multiclass SO by the multiclass CL-SUE under monetary-based criterion is not less than that by the multiclass SUE.Theorem3ρCL−SUE/CL−SSOt=FCL−SUEt−FCL−SSOt≤γφTCL−SUEt(1) The upper bound (61) depends on two parameters, namely, γφ and TCL−SUEt. The commonality factor reflecting path overlapping has no impact on the inefficiency upper bound (61).(2) Corollary 2 (FCL−SUEt−FCL−SSOt=γφTCL−SUEt if and only if γφ=0). It states that the upper bound (61) is tight if and only if γφ=0 (without traffic congestion), which means that the upper bound (61) is usually not tight in most cases.Theorem4ρCL−SUE/CL−SSOc=FCL−SUEc−FCL−SSOc≤γ¯φ,βTCL−SUEc+γ˜φ,βTCL−SSOc(1) The upper bound (67) depends on four parameters, namely, γ¯φ,β, γ˜φ,β, TCL−SUEc, and TCL−SSOc. The commonality factor reflecting path overlapping has no impact on the inefficiency upper bound (67).(2) Corollary 3 (FCL−SUEc−FCL−SSOc=γ¯φ,βTCL−SUEc+γ˜φ,βTCL−SSOc if and only if γ¯φ,β=γ˜φ,β=0): It shows that the upper bound (67) is tight if and only if γ¯φ,β=γ˜φ,β=0, which means that the upper bound (67) is usually not tight in most cases.


## 7. Numerical Example

The Nguyen and Dupuis network [50] shown in Figure 2 is used to further illustrate the above conclusions. The network consists of 19 links, 13 nodes, 25 paths, and 4 OD pairs. All users are classified on the basis of different VOTs into three main classes. Let β1=1.0 (¥/min) (denoted by “1”) be VOT for users of class 1, β2=2.0 (¥/min) (denoted by “2”) be VOT for users of class 2, and β3=3.0 (¥/min) (denoted by “3”) be VOT for users of class 3. As shown in Figure 2, the network has 4 OD pairs: 1⟶2 (denoted by “w1”), 1⟶3 (denoted by “w2”), 4⟶2 (denoted by “w3”), and 4⟶3 (denoted by “w4”). Suppose that the traffic demand is dw11=120, dw12=200, dw13=80, dw21=240, dw22=400, dw23=160, dw31=180, dw32=300, dw33=120, dw41=60, dw42=100, and dw43=40. Assume that parameters θ=0.5, β0=1, and γ0=1.Figure 2
Nguyen and Dupuis network.The link time functions use the following BPR (Bureau of Public Road) form, with free-flow travel timeta0 and link capacity Ca provided in Table 4:(69)tava=ta01+0.15×vaCa4.Table 4
Parameters of links.
Link no.Free-flow travel timeCapacityLink no.Free-flow travel timeCapacity179001110700287001210700397001396004149001487005580015970069600168700759001773008135001815700953001911700109400The relationship between paths and nodes in the network is shown in Table5. The commonality factor cfrw can be calculated by (10). In this paper, the free-flow travel time is used instead of length to calculate cfrw. The results are also shown in Table 5.Table 5
Parameters between four OD pairs.
OD pairPath no.Node sequenceThe value ofcfrw1-211-12-8-20.820221-5-6-7-8-21.122631-5-6-7-11-21.243741-5-6-10-11-21.210551-5-9-10-11-21.020661-12-6-7-8-21.162171-12-6-7-11-21.274481-12-6-10-11-21.24391-391-5-9-13-30.5843101-5-6-7-11-31.0851111-5-6-10-11-31.1507121-5-9-10-11-31.0777131-12-6-7-11-30.9550141-12-6-10-11-31.04094-2154-9-10-11-20.8153164-5-6-7-8-20.7551174-5-6-7-11-21.0217184-5-6-10-11-21.0704194-5-9-10-11-21.05924-3204-9-13-30.6606214-9-10-11-30.9540224-5-9-13-30.9012234-5-6-7-11-30.8922244-5-6-10-11-31.0088254-5-9-10-11-31.1190The link flow, path flow, and path cost solutions of the multiclass CL-SUE model are shown in Tables6 and 7 by solving VI (18), respectively. The link flow solutions of the multiclass SO and CL-SSO models are shown in Table 8 by solving the minimization problems (19), (35), (50), and (51).Table 6
Path results of the multiclass CL-SUE model.
Path no.The multiclass CL-SUEPath flowPath costTime-basedMonetary-basedTime-basedMonetary-basedm = 1m = 2m = 3m = 1m = 2m = 3m = 1m = 2m = 3m = 1m = 2m = 3185.0141.656.696.8197.179.933.533.533.533.567.0100.5221.135.214.110.31.90.132.832.832.832.865.698.431.52.61.02.50.10.036.436.436.436.472.8109.240.81.40.60.80.00.044.444.444.444.288.3132.550.60.90.40.70.00.051.951.951.950.8101.5152.369.916.56.66.70.80.035.335.335.335.370.6105.970.71.20.51.60.00.038.938.938.938.977.8116.780.40.60.30.50.00.046.946.946.946.693.3139.99160.5267.5107.0141.3362.5157.156.256.256.257.6115.3172.91030.150.220.140.523.22.234.634.634.634.669.3103.91116.828.111.213.92.60.142.642.642.642.484.8127.21212.220.48.212.02.10.150.150.150.149.098.0147.01313.021.68.623.98.60.537.137.137.137.174.3111.4147.312.24.98.31.00.045.145.145.144.989.8134.61534.256.922.855.280.023.044.744.744.744.589.1133.616126.3210.584.287.1205.095.634.134.134.134.268.3102.5179.916.56.623.012.51.337.837.837.837.875.5113.3185.59.23.77.81.40.145.745.745.745.591.0136.5194.16.92.77.01.10.053.353.353.352.1104.2156.42049.081.732.748.098.039.948.948.948.951.4102.8154.2213.45.62.33.70.50.042.942.942.942.885.6128.3225.99.83.96.11.40.157.657.657.659.0118.0177.0230.91.40.61.30.10.036.036.036.036.072.0108.0240.50.80.30.50.00.044.044.044.043.887.5131.2250.40.70.30.50.00.051.551.551.550.4100.7151.1Table 7
Link results of the multiclass CL-SUE model.
Link no.The multiclass CL-SUELink flowTime-basedMonetary-basedm = 1m = 2m = 3m = 1m = 2m = 31243.8406.3162.5222.2392.4159.52116.2193.777.5137.8207.680.53153.5255.8102.3133.1221.597.1486.5144.257.7106.9178.562.95213.6355.9142.4187.8246.899.46183.7306.2122.5167.5367.1157.27213.5355.8142.3197.0252.299.8831.452.320.931.85.10.29157.3262.2104.9104.0207.795.71056.193.637.492.944.54.111242.3403.8161.5200.9404.8175.61254.891.436.679.083.723.113215.4359.0143.6195.4461.9197.11486.2143.657.5110.988.823.21557.796.238.599.295.224.41684.6141.056.4104.638.13.01731.352.120.941.010.50.61885.0141.656.696.8197.179.919215.4359.0143.6195.4461.9197.1Table 8
Link results of the multiclass SO and CL-SSO models.
Link no.The multiclass SOThe multiclass CL-SSOLink flowLink flowTime-basedMonetary-basedTime-basedMonetary-basedm = 1m = 2m = 3m = 1m = 2m = 3m = 1m = 2m = 3m = 1m = 2m = 31287.1478.6191.4282.6471.0188.4255.4425.7170.3255.4428.8171.8272.9121.448.677.4129.051.6104.6174.369.7104.7171.268.2370.7117.947.187.0145.158.0111.7186.274.5111.9171.768.04169.3282.1112.9153.0254.9102.0128.3213.885.5128.1228.392.05212.1353.6141.4238.0396.7158.7217.3362.1144.8217.6365.4146.56145.7242.997.1131.6219.487.7149.9249.899.9149.7235.193.37212.1353.6141.4238.0396.7158.7239.3398.8159.5239.6401.0160.080.00.00.00.00.00.08.514.15.78.56.32.49117.9196.478.6123.9206.582.6106.7177.971.2106.7179.971.91094.3157.162.9114.1190.276.1132.5220.988.3132.9221.188.111190.7317.9127.1201.3335.5134.2180.9301.4120.6180.8309.2124.212109.3182.172.998.7164.565.898.1163.565.498.2152.560.813205.7342.9137.1185.9309.8123.9180.1300.1120.0179.7310.9124.514109.3182.172.998.7164.565.8106.6177.771.1106.7158.863.215109.3182.172.998.7164.565.8119.2198.679.4119.2190.875.81694.3157.162.9114.1190.276.1120.0199.980.0120.4189.175.5170.00.00.00.00.00.030.550.820.330.641.915.91872.9121.448.677.4129.051.674.1123.549.474.1129.452.319205.7342.9137.1185.9309.8123.9180.1300.1120.0179.7310.9124.5From Tables6 and 7, we can obtain TCL−SUEt=∑w∈W∑r∈Rw∑m=1Mcrwmf¯tf¯rwm,t=86316.9550, TCL−SUEc=∑w∈W∑r∈Rw∑m=1Mcrwmf¯cf¯rwm,c=171413.1091, FCL−SUEt=74528.8734, and FCL−SUEc=144177.3510. From Table 8, we can obtain TSOt=77678.1637, TSOc=146623.4458, TCL−SUEc=145869.2905, FCL−SSOt=74296.2072, and FCL−SSOc=143566.4683. Thus, we have ρCL−SUEt=TCL−SUEt/TSOt=1.1112, ρCL−SUEc=TCL−SUEc/TSOc=1.1691, ρCL−SUE/CL−SSOt=FCL−SUEt−FCL−SSOt=232.6662, and ρCL−SUE/CL−SSOc=FCL−SUEc−FCL−SSOc=610.8827.For the link time function withp=4 in this example, it is easy to obtain that γφ=0.535. Since kwCL−SUE is the solution of kexpk+1=∑r=1,r≠jRwexpθcfjw−cfrw with j=argmaxrcfrw,r∈Rw, w∈W, then we can obtain kw1CL−SUE=1.0767, kw2CL−SUE=0.9412, kw3CL−SUE=0.8441, and kw4CL−SUE=0.9469. Hence, we can have k¯=0.9397 by k¯=∑w∈W∑m=1Mdwm/DkwCL−SUE and D=∑w∈W∑m=1Mdwm. We can also obtain c¯=38.8391 and c˜=73.3117 by c¯=TSOt/D and c˜=TSOc/D, respectively.From Table7, we can have v¯11,c=222.2, v¯12,c=392.4, v¯13,c=159.5, and v¯1c=774.1. Based on definition γaza,ta,β=1/∑m=1Mβmzamtazamaxvam≥0∑m=1Mβmvamtaza−tava and t1v1=71+0.15×v1/9004, we can obtain γ1z1,t1,β=maxvam≥01⋅v11+2⋅v12+3⋅v137.5748−71+0.15v1/9004/1⋅222.17+2⋅392.44+3⋅159.53⋅7.5748. When v11=0, v12=0, v13=517.7044, and v1=517.7044, the above optimization problem reaches at the maximum γ1z1,t1,β=0.0635. By the same way, we obtain γ2z2,t2,β=0.0173, γ3z3,t3,β=0.0212, γ4z4,t4,β=0.0029, γ5z5,t5,β=0.0253, γ6z6,t6,β=0.1694, γ7z7,t7,β=0.0179, γ8z8,t8,β=0.000012, γ9z9,t9,β=0.2739, γ10z10,t10,β=0.0027, γ11z11,t11,β=0.1540, γ12z12,t12,β=0.0007, γ13z13,t13,β=0.3058, γ14z14,t14,β=0.0015, γ15z15,t15,β=0.0014, γ16z16,t16,β=0.0003, γ17z17,t17,β=0.0002, γ18z18,t18,β=0.0099, and γ19z19,t19,β=0.2002. Then, we have γ¯φ,β=0.3058 and γ˜φ,β=0.Thus, bound (33) becomes ρCL−SUEt=1.1112≤1/1−γφ1+k¯/θc¯=2.2546 according to Theorem 1. Bound (48) becomes ρCL−SUEc=1.1691≤1+γ˜φ,β+k¯/θc˜/1−γ¯φ,β=1.4774 according to Theorem 2. Bound (61) becomes ρCL−SUE/CL−SSOt=232.6662≤γφTCL−SUEt=46179.5710 according to Theorem 3. Bound (67) becomes ρCL−SUE/CL−SSOc=610.8827≤γ¯φ,βTCL−SUEc+γ˜φ,βTCL−SSOc=52418.1288 according to Theorem 4.In summary, the numerical results show that Theorems1–4 are correct and valid.Next, we will select three representative parameters for sensitivity analysis. The sensitivities of the upper bounds with respect to parametersγφ, k¯, and θ are addressed in the following. According to the above results, we can obtain γφ=0.535, γ¯φ,β=0.3058, γ˜φ,β=0, k¯=0.9397, θ=0.5, c¯=38.8391, c˜=73.3117, and TCL−SUEt=86316.9550. Since (33) and (68), it is easy to know that bound (33) as a function of p and the function expression is ρCL−SUEtp=1.04841−p/p+11/p+11/p−1. By the same way, we can obtain the other five function expressions: (1) bound (33) as a function of k¯ and the function expression is ρCL−SUEtk¯=1/0.4651+k¯/19.4196; (2) bound (33) as a function of θ and the function expression is ρCL−SUEtθ=1/0.4651+0.0242/θ; (3) bound (48) as a function of k¯ and the function expression is ρCL−SUEck¯=1/0.69421+k¯/36.6559; (4) bound (48) as a function of θ and the function expression is ρCL−SUEcθ=1/0.69421+0.0128/θ; and (5) bound (61) as a function of p and the function expression is ρCL−SUE/CL−SSOtp=86317p/p+11/p+11/p. The following figures present the sensitivities of upper bounds subject to parameters p, k¯, and θ (see Figures 3–5).Figure 3
Bound (33) and bound (61) as a function of p.
(a)(b)Figure 4
Bound (33) and bound (48) as a function of k¯.Figure 5
Bound (33) and bound (48) as a function of θ.Figure3 shows both bound (33) and bound (61) increase with p; Figure 4 shows both bound (33) and bound (48) increase with k¯, and bound (48) is always smaller than bound (33); and Figure 5 shows both bound (33) and bound (48) decrease with θ, and bound (48) is always smaller than bound (33). Therefore, our sensitivity analysis results are consistent with the conclusions given in Section 5, which means that the conclusions given in Section 5 are valid.


## 8. Conclusions

We have derived four inefficiency bounds of the multiclass CL-SUE by making full use of equivalent VI formulations and provide some main conclusions as follows.When comparing multiclass CL-SUE with multiclass SO, the upper bound under time-based criterion depends on the class of link time functions, the network complexity (including the commonality factor reflecting path overlapping and the number of feasible paths), the perception error of travel time, and the total demand. The upper bound will be underestimated in a realistic transportation network, if the commonality factor is not considered. By contrast, besides the factors mentioned above, the upper bound under monetary-based criterion is dependent upon the VOT of user classes.When comparing multiclass CL-SUE with multiclass CL-SSO, the upper bound under monetary-based criterion depends on the class of link time functions and the VOT of user classes. However, the upper bound under time-based criterion only depends on the class of link time functions. Moreover, our research results suggest that the upper bound will increase when the degree of traffic congestion goes up. The upper bound is usually not tight in most cases because traffic congestion is inevitable, which means that there is more space to improve the congestion in the traffic network.Furthermore, the effects of various parameters on the bounds have been further studied, especially the commonality factor. The results of the above discussions are shown in Table2.Our study can be further extended in two ways: (1) to explore more accurate upper bounds when more detailed network information is known and (2) to investigate the inefficiency of the multiclass CL-SUE with elastic demand under different decision criteria.



---

*Source: 2601184-2021-12-27.xml*