# Stochastic Congestion Pricing among Multiple Regions: Competition and Cooperation

Authors: Hua Wang; Wei Mao; Hu Shao
Journal: Journal of Applied Mathematics
 (2013)

---

## Abstract

Previous studies of road congestion pricing problem assume that transportation networks are managed by a central administrative authority with an objective of improving the performance of the whole network. In practice, a transportation network may be comprised of multiple independent local regions with relative independent objectives. In this paper, we investigate the cooperative and competitive behaviors among multiple regions in congestion pricing considering stochastic conditions; especially demand uncertainty is taken into account in transportation modelling. The corresponding congestion pricing models are formulated as a bilevel programming problem. In the upper level, congestion pricing model either aims to maximize the regional social welfare in competitive schemes or attempts to maximize the total social welfare of multiple regions in cooperative schemes. In the lower level, travellers are assumed to follow a reliability-based stochastic user equilibrium principle considering risks of late arrival under uncertain conditions. Numerical examples are carried out to compare the effects of different pricing schemes and to analyze the impact of travel time reliability. It is found that cooperative pricing strategy performs better than competitive strategy in improving network performance, and the pricing effects of both schemes are quite sensitive to travel time reliability.


---

## Body

## 1. Introduction

Congestion pricing is widely regarded as an effective strategy to alleviate traffic congestion in transportation networks. It is also viewed as one of the most efficient means by transportation economists as it employs the price mechanism. Congestion pricing, thus, has been paid extensive attention in the literature [1]. In the congestion pricing scheme, the decision maker (e.g. road authority) aims to optimize system performance, where the travelers’ path choice decisions are considered.Previous studies of congestion pricing mainly focused on enhancing the system performance of the entire transportation network [2–8] and few of them considered interactions among different stakeholders [9]. Researchers also studied parking pricing and parking permission management, based on the assumption that all parking facilities are controlled by a central authority [6, 7, 10, 11]. Actually, a transportation network may be comprised of several regions, where the authority in each region manages its own subnetwork independently. Thus conventional pricing models may be inapplicable for the pricing problem in a real network spanning multiple regions, because the regional authorities optimize the toll levels in order to achieve their selfish objectives rather than improve the performance of the whole network [9]. There are a number of significant efforts on the investigation of such competition of road pricing problem (e.g., [9, 12–14]). However, these analyses are carried out under deterministic condition; that is, the demand and supply sides of a transportation network are assumed to be deterministic. As such, traffic demand is either treated as a deterministic value in the fixed demand case or assumed as a deterministic function of the average travel time/cost in the elastic demand case [15]. On the supply side, the link capacity is also treated as a fixed value. The congestion pricing problem under deterministic condition could be perfectly solved by the theory of marginal cost pricing (MPC) [16, 17]. Specifically, if a marginal cost toll is allowed to be charged on each link of the network, the corresponding traffic flow pattern will be driven toward a social optimum (SO) under deterministic user equilibrium (UE) path choice principle [18] or stochastic user equilibrium (SUE) path choice principle [19]. Regardless of the perfect features of MPC, congestion pricing under deterministic condition cannot capture the uncertain factors of transportation networks.It is well known that transportation networks are inherently stochastic in reality. In recent studies, more and more researchers found that network uncertainty might exert an important impact on the transportation management and overlooking this factor leads to a suboptimal optimization scheme [20, 21]. Therefore, in this paper, we aim to study the pricing problem of multiple regions on a stochastic network with demand uncertainty. The literature review provided here by no means presents a comprehensive survey to general pricing problems; instead, it focuses on the pricing model and the traffic equilibrium with network uncertainty, particularly demand uncertainty.In the past decades, network uncertainties have been widely recognized and extensively studied in the literature of transportation field. In a realistic transportation network, there are a variety of uncertainty sources in both demand and supply sides. In demand side, traffic demand of a study period (e.g. morning peak) fluctuates from day to day due to travelers’ variant activities. In supply side, the link capacities degrade due to various incidents, such as traffic accidents, road works, earthquakes, and signal failures. Under uncertain conditions, the travel time during a particular period varies from day to day. Confronted with the travel time variations, travelers have to consider the risk of being late to their destination while making their path choice decisions. To resist the disturbance of network uncertainties, travelers take into account not only the travel time/cost but also the travel time reliability for path choices. That is to say, travel time reliability also exerts an important impact on travelers’ path choice decisions. The corresponding reliability-based traffic assignment problems have been attracting an increasing attention in the literature [22–28]. From the viewpoint of a decision maker, the enhancement of network reliability is also an important target while making road pricing schemes. Thus, under network uncertainties, how to formulate the congestion pricing model is an interesting and practical topic.A few studies have been carried out to account for the congestion pricing problem under uncertainty. For example, Li et al. [29] proposed a reliability-based optimal toll design model with respect to stochastic link capacities and OD demand with varied toll levels. Boyles et al. [30] obtained first-best tolls in static transportation networks with day-to-day variation in network capacity. Sumalee and Xu [15] proposed a closed-form formulation to calculate the first-best marginal cost toll for the stochastic network under demand uncertainty. Gardner et al. [31] presented a road pricing framework for representing uncertainty in long-term travel demand and in day-to-day network capacity. All these studies indicated that the congestion pricing scheme under network uncertainties is different from that under a deterministic condition. Therefore, the investigation of congestion pricing problem under network uncertainties could help the decision maker make appropriate toll design.The task of this study is to model the competitive and cooperative behaviors of pricing problem among multiple regions under demand uncertainty. The network uncertainty may bring two challenges for the road pricing problem among multiple regions. On the one hand, road pricing can alleviate the traffic congestion in terms of minimizing the expected total travel time related to the stochastic flows. On the other hand, travelers’ reliability-based path choice behaviors may play an important role in the pricing scheme by influencing the flow pattern and the optimization objective simultaneously. To account for the two potential impacts, we formulated the stochastic pricing models among multiple regions based on the conceptual framework proposed by Zhang et al. [9].The rest of the paper is organized as follows. In the next section, the road congestion pricing optimization models are formulated to characterize the competitive and cooperative behaviors among multiple regions. Then, a heuristic solution algorithm is proposed in Section3. Numerical examples and results are discussed in Section 4. Finally, conclusions and further studies are given in Section 5.


## 2. Model Formulation

This section builds the road congestion pricing models among multiple regions on the stochastic network with day-to-day demand fluctuations. It first investigates the impact of demand uncertainty on the flow patterns in terms of the mean and covariance of the flow distributions. A reliability-based traffic assignment model based on the stochastic flow patterns is proposed to characterize the travelers’ path choice behaviors considering their own risk preference. Subsequently, we propose the competitive and cooperative pricing schemes for stochastic road pricing problem among multiple regions. The optimization objective for the pricing model is to maximize the social welfare (equal to the total user benefit minus the mean total travel time).


### 2.1. Demand Uncertainty and Flow Distribution

It is assumed that the daily traffic demands during the same study period (e.g. morning peak, 8:00 am-9:00 am) between all OD pairs are multivariate random variables. For each OD pairrs∈R, the random traffic demand is expressed as
(1)Qrs=qrs+εrs,∀rs∈R,cvrs=σrsqqrs,∀rs∈R,
where qrs is the mean (or expected) OD demand between OD pair rs,  E[Qrs]=qrs;  εrs is the random term with E[εrs]=0;  R is the set of OD pairs. For convenience, denote Q and q as the |R|-vectors of (…,Qrs,…)T and (…,qrs,…)T for all rs∈R, respectively. The covariance between OD demand Qrs and Qrs′ is denoted as
(2)σrs,rs′q=cov[Qrs,Qrs′],∀rs,rs′∈R.
The corresponding covariance matrix of traffic demands of all OD pairs can be expressed as
(3)Σq={σrs,rs′q}|R|×|R|.
The value of σrs,rs′q may be positive, zero, or negative. It is assumed that the OD demands of all OD pairs follow multivariate normal distribution, that is Q~MVN(q,Σq,), where q and Σq are fixed and known. Let Frsk be the random traffic flow on path k∈Krs with its mean frsk=E[Frsk], where Krs is the path set between OD pair rs and K=⋃rs∈RKrs. For convenience, F and f are denoted as the |K|-vectors of (…,Frsk,…)T and (…,frsk,…)T for all k∈Krs and rs∈R, respectively. The path flows and OD demands satisfy the following flow conservation condition:
(4)Q=ΛF,
where Λ is the OD-path incidence matrix. Then, the following conservation conditions hold:
(5)q=E[Q]=E[ΛF]=ΛE[F]=Λf.
Equation (5) can be rewritten as
(6)qrs=∑k∈Krsfrsk,∀rs∈R.
It is assumed that the path flow is a product of the corresponding path choice proportion and the OD demand as follows [27]:
(7)Frsk=prskQrs,∀k∈Krs,rs∈R,
where prsk is the path choice proportion of the traffic flow on path k∈Krs of vehicle, which is assumed to be constant of the probability [24]. Then, it follows from (7) that
(8)frsk=prskqrs,∀k∈Krs,rs∈R.
The covariance between Frsk and Frs′k′ can be deduced as
(9)σrs,rs′f,k,k′=cov[Frsk,Frs′k′]=prskprs′k′cov[Qrs,Qrs′]=prskprs′k′σrs,rs′q,∀k∈Krs,k′∈Krs′,rs,rs′∈R.
The corresponding covariance matrix of path flows can be expressed as
(10)Σf={σrs,rs′f,k,k′}|K|×|K|.
According to (4), the covariance conservation condition between path flows and OD demands is expressed as
(11)Σq=ΛΣfΛT.
Denote δrsk,a as the element of the link-path incidence matrix. δrsk,a=1, if path k uses link a; otherwise, δrsk,a=0. Then, the conservation condition of the estimated link and path flows is expressed as
(12)Va=∑rs∈R∑k∈Krsδrsk,aFrsk,∀a∈A,
where Va is the random traffic flow on link a. The mean link flow is denoted as va=E[Va]. It follows from (12) that
(13)va=∑rs∈R∑k∈Krsδrsk,afrsk=∑rs∈R∑k∈Krsδrsk,aprskqrs,∀a∈A.
It can be seen from (13) that the mean link flow is a linear function with respect to the path choice proportions, which can be expressed as follows:
(14)va=va(p),∀a∈A,
where p is denoted as the |K|-vector of path choice proportions (…,prsk,…)T, all k∈Krs and rs∈R. Also, the conservation condition of the link and path flow covariance can be obtained as
(15)σa,a′v=cov[Va,Va′]=cov[∑rs∈R∑k∈Kδrsk,aFrsk,∑rs′∈R∑k′∈Kδrs′k′,a′Frs′k′]=∑rs∈R∑k∈K∑rs′∈R∑k′∈Kδrsk,aδrs′k′,a′cov[Frsk,Frs′k′]=∑rs∈R∑k∈K∑rs′∈R∑k′∈Kδrsk,aδrs′k′,a′σrs,rs′f,k,k′=∑rs∈R∑k∈K∑rs′∈R∑k′∈Kδrsk,aδrs′k′,a′prskprs′k′σrs,rs′q,∀a,a′∈A,
where σa,a′v is the covariance between link flows Va and Va′, a,a′∈A. It can be seen from (15) that the covariance of link flows is a function with respect to the path choice proportions, which is expressed as:
(16)σa,a′v=σa,a′v(p),∀a,a′∈A.


### 2.2. Reliability-Based Traffic Assignment Problem

Under demand uncertainty, the link and path travel times stochastically fluctuate from day to day, indicated asTa(Va(p),ua) and Trsk, respectively. Let A¯⊆A be a subset of links which are implemented the congestion pricing scheme and u=(…,ua,…)Ta∈A¯ denote the vector of link tolls, where ua is the toll on link a∈A¯. Then, the link travel time function for link a∈A¯ can be defined as the following modified Bureau of Public Roads (BPR) function:
(17)Ta(Va(p),ua)=ta0(1+α(Va(p)ca)n)+1βua,∀a∈A¯,
where α is a parameter of link performance function and β>0 is a constant which represents the value of time (VOT). To facilitate the presentation of the essential idea, it is assumed that the VOTs of all travelers are same. For other links, the original BPR function is used as the link time function:
(18)Ta(Va(p),ua)=ta0(1+α(Va(p)ca)n),∀a∈A¯∖A,
where A¯∖A represents the link set, for which toll is not charged on the link. According to the method in Clark and Watling [24], (16) and (17), the mean and covariance of link travel times can be deduced, which are the functions with respect to p and u. The mean path travel time can be expressed as a function with respect to p and u as follows:
(19)trsk(p,u)=∑a∈Aδrsk,ata(p,u),∀k∈Krs,rs∈R,
where ta(p,u) is the travel cost on a∈A; trsk(p,u) is the travel cost on path k∈Krs. Similarly, the variance of path travel times can be expressed as
(20)σrst,k(p,u)=cov[Trsk,Trsk]=cov[∑a∈Aδrsk,aTa(p,u),∑a′∈Aδrsk,a′Ta′(p,u)]=∑a∈A∑a′∈Aδrsk,aδrsk,a′cov[Ta(p,u),Ta′(p,u)]=∑a∈A∑a′∈Aδrsk,aδrsk,a′σa,a′t(p,u),∀k∈K,rs∈R,
where Trsk is the path travel time on path k∈Krs, E[Trsk]=trsk; Ta and Ta′ are link travel times on links a∈A and a′∈A, respectively; σa,a′t is the covariance of link travel times on a∈A and a′∈A.Since travelers’ path choice decisions will be influenced by the uncertain OD demand variations, the decision of road pricing is also dependent on such stochasticity. To consider this effect, a reliability-based stochastic user equilibrium (RSUE) model [27] is adopted to account for the travelers’ reliability-based path choice behaviors in the road pricing problem. In this RSUE model, the effective travel time, t^rsk, is used as the path choice criterion, which is defined as the summation of the mean travel time, trsk, and the safety margin srsk [32]:
(21)t^rsk(p,u)=trsk(p,u)+srsk(p,u),∀k∈K,rs∈R.
The value of srsk can be obtained by solving the following chance-constrained minimization problem:
(22)minsrskt^rsk=trsk+srsks.t.Pr[Trsk≤t^rsk]≥ρ∀k∈K,rs∈R,
where ρ is the confidence level of travel time reliability. A high value of ρ means that the travelers would prefer setting a large safety margin of path travel time in order to guarantee a high on-time arrival probability. On the other hand, a low value of ρ means the travelers would prefer tolerating a high risk of on-time arrival. The effective path travel time can be calculated that
(23)t^rsk(p,u)=trsk(p,u)+Φ-1(ρ)σrst,k(p,u),∀k∈K,rs∈R,
where Φ-1(·) is the inverse of cumulative function of standard normal distribution.The reliability-based stochastic user equilibrium could be reached, in which for each OD pair no traveler can decrease his/her perceived disutility by unilaterally changing their paths. In the Logit-based RSUE model, the path choice proportionprsk, which is defined in (7), can thus be specified by the following formula:
(24)prsk=exp(-θt^rsk(p,u))∑j∈Krsexp(-θt^rsj(p,u))=wrsk(p,u),∀k∈K,rs∈R,
where θ is the dispersion parameter on travelers’ perception errors of effective travel time. For the sake of convenience, we denote the path choice function prsk as wrsk(p,u) and the set notation can be denoted as:
(25)W(p,u)=(…,wrsk(p,u),…)T.
Meanwhile, it is well known that level of service on the network would exert an impact on the OD demand [33]. Therefore, the mean OD demand is viewed as a function with respect to the expected disutility of travel for each OD pair:
(26)qrs(π)=qrs¯exp(-ηπ),
where qrs¯ indicates the potential demand for OD pair rs, and η denotes the elastic coefficient. The expected disutility can be attained by
(27)πrs=-1θIn∑iexp(-θ·t^rsk(p,u)).
Then, the vector form of (24) considering elastic demand yields the following fixed point problem:
(28)(pq)=(W(p,u)q(t^rsk(p,u))).


### 2.3. Optimization of Congestion Charges in a Single Region

Recently, an increasing number of transportation researchers have recognized that demand uncertainty plays an important role in the decision making of transportation management. Under demand uncertainty, the expected value of total system travel time, as an important measure, is always adopted to evaluate the system performance. Meanwhile, the variation of total network travel time could bring troubles for transportation planning as well as the mean total travel time. Theoretically, the uncertainty of demand will directly lead to variation of the travel time, which influences decision making for administrators and travelers. For decision maker, it is difficult to evaluate the level of service of the road as travel time stochastically fluctuates from day to day. On the other hand, for the travelers, the variation of the travel time may result in late arrival to the destination, which influences their path and departure time choices. In this regard, the variation of total travel time should be considered in the optimization objective for the pricing problem. To facilitate the model formulation, we only take into account the minimization of mean total travel time as the objective of the pricing problem. This is not to deny the importance of the higher moment of the total travel time.The congestion models in previous studies are assumed to alleviate the traffic congestion over the whole network, which is managed by a central authority. Therefore, the central authority will be concerned with the mean total travel time cost on the network. The corresponding road pricing is objectived comprises of the total user benefit and the mean total travel time cost:(29)maxuSW=∑rs∈R∫0qrs(u)qrs-1(ω)dω-E[TTT(p,u)],
where at RSUE the mean of total travel time (E[TTT(p,u)]) can be calculated as
(30)E[TTT(p,u)]=E[∑a∈A(Ta(p)-1αua)·Va(p(u))].
Equation (30) can be calculated using the method proposed by Clark and Watling [24]. It is noticeable that the following mathematical inequality generally holds:
(31)E[∑a∈A(Ta(p)-1αua)·Va(p(u))]≠∑a∈AE[Ta(p)-1αua]·E[Va(p(u))].
In practice, the regional road systems may be freely managed by the separate transportation authorities on the optimizations of toll level and toll location. Here, we introduce the stochastic pricing problem where only one local region performs pricing scheme. As stated by Zhang et al. [9], the optimization objective function for single region pricing scheme is different from that of the centric pricing scheme with a central authority. The former aims to maximize the social welfare just for its own residents, who live in its local administrative region whereas the later concerns the social benefit of all users on the whole network. In this study, we extend the objective function to the stochastic traffic network and consider the stochastic flows resulted from the demand uncertainty. The regional authority only takes into account the trips with origins that locate at its own regime. The pricing problem considering reliability-based user equilibrium can be formulated as follows (Model A):
(32)maxuSW=∑rs∈Ri∫0qrs(u)qrs-1(ω)dω+E[∑a∈A¯iua·Va(p(ui))∑a∈A¯iua·Va(p(ui))-∑rs∈Ri∑k∈KFrsk(p(u))·Trsk(p(u))]
subject to
(33)(pq)=(W(p,u)q(t^rsk(p,u))),(34)u_a≤ua≤u¯a,∀a∈A-i,
where Ri denotes the OD pairs with the origins in region; A¯i denotes the links in region i. In the optimization problem, u is the decision variable, and the path choice proportion (p) is the constant probability, which can be determined by the fixed point problem in (33). The constraint (34) sets the upper and lower bounds for the toll charges.It should be stressed that the social benefit expressed in (32) concerns only the local region i that implements congestion pricing, while the stochastic equilibrium flow pattern is characterized by the choice decisions of all users in all regions in the network.


### 2.4. Competitive Behavior of Pricing Problem among Multiple Regions

In this section, we study the competitive behavior of the scenario that several local authorities implement congestion pricing independently. LetI={1,2,…,|I|} indicate the set of regions in which congestion pricing schemes are implemented, and i∈I. Let Ri denote the set of O-D pairs for all residents living in this region, which is a subset of R, and R=∪i∈IRi. The set of candidate toll links A¯i is a subset of A-. Let ui be the set of tolls ua on the links a∈A-i, and u=∪i∈Iui. Based on the current decisions of other regions, each region designs its own pricing scheme with the objective of maximizing its own social benefit. Once an authority makes change of it’s toll levels, other authorities will make their best responses of adjusting their toll levels. The competition with theses mutual responses can be characterized as a Nash game.The optimal toll levels for a specific regional authorityi can be obtained by solving a similar optimization model as proposed in Section 2.3. For region i, its authority aims to maximize its own social welfare by setting toll charges in its regime, in which the network users follow the reliability-based stochastic user equilibrium principle. Taking the viewpoint of region i, the Nash equilibrium model is formulated as follows (Model B):
(35)maxuiSW(ui∣ui∖u)=∑rs∈Ri∫0qrs(ui)qrs-1(ω)dω+E[∑a∈A¯iua·Va(p(ui))∑a∈A¯iua·Va(p(ui))-∑rs∈Ri∑k∈KFrsk(p(ui))·Trsk(p(ui))]
subject to constraints (33) and (34).In this pricing scheme, eventually, all the regions are self-best responding to each other, named a Nash equilibrium, that no player can change his pricing strategy unilaterally to obtain a better result. The outcome of the Nash game can be obtained by iteratively solving the above pricing problem for all the players.


### 2.5. Cooperative Congestion Pricing among Multiple Regions

In Section2.4, we propose a Nash equilibrium model to capture the competitive behavior among the authorities in different regions. Each authority sets its own pricing objective to improve the social welfare independently. But such competition may actually be detrimental to the travelers from other regions of the increasing travel burden. In this regard, the competitive pricing scheme may do harms to traffic efficiency of the whole network. Therefore, the cooperative manner is recommended. We propose a pricing model in which the local authorities cooperate to maximize the total social welfare of travelers in the regions that implement the pricing schemes. All elements used in this subsection are the same as those in Section 2.4, except that the regional authorities behave in a cooperative manner. The congestion pricing model is formulated as follows (Model C):
(36)maxuiSW=∑i∈I{∑rs∈Ri∫0qrs(ui)qrs-1(ω)dω}+∑i∈I{E[∑a∈A¯iua·Va(p(ui))∑a∈A¯iua·Va(p(ui))-∑rs∈Ri∑k∈KFrsk(p(ui))·Trsk(p(ui))]},
where the constraints are also the traffic flow equilibrium constraint and the boundary constraint for the design variable, which is formulated by (33) and (34).It should be stressed that, as pointed out by Zhang et al. [9], whether such cooperation can be achieved depends on the benefit gain of each player under the cooperative manner. If all regional authorities can benefit from the cooperation, the agreement of the cooperation would be achieved easily. In contrast, when some regions suffer a loss in the cooperative scheme, they prefer competing with other regions. However, if the regions that gain more benefit are willing to compensate the regions that suffer loss, the alliance may still hold.In this section, we propose the competitive and cooperative congestion pricing models under demand uncertainty. To the best of our knowledge, Zhang et al. [9] have made comprehensive analyses of noncooperative behaviors of the road pricing problem among multiple regions. The proposed models differ from the most related studies, such as Zhang et al. [9], of the traffic conditions. Our models are based on the stochastic traffic flows and the corresponding RSUE principle, while the model in Zhang et al. [9] is based on the deterministic traffic flows following the user equilibrium principle. This study makes twofold contribution to the literature. First, travelers’ reliability-based path choice behaviors can be reflected by the RSUE constraint (33). It makes an obvious difference from the user equilibrium principle in previous studies by considering travelers’ risk-taking behavior. Generally, the risk-taking preference is important for a stochastic transport system because it exerts an important impact on both individual travel activity and system-level decision making. Furthermore, the competitive and cooperative behaviors of the pricing problem on a stochastic network have been discussed by incorporating the mean total travel time into the optimization objectives.


## 2.1. Demand Uncertainty and Flow Distribution

It is assumed that the daily traffic demands during the same study period (e.g. morning peak, 8:00 am-9:00 am) between all OD pairs are multivariate random variables. For each OD pairrs∈R, the random traffic demand is expressed as
(1)Qrs=qrs+εrs,∀rs∈R,cvrs=σrsqqrs,∀rs∈R,
where qrs is the mean (or expected) OD demand between OD pair rs,  E[Qrs]=qrs;  εrs is the random term with E[εrs]=0;  R is the set of OD pairs. For convenience, denote Q and q as the |R|-vectors of (…,Qrs,…)T and (…,qrs,…)T for all rs∈R, respectively. The covariance between OD demand Qrs and Qrs′ is denoted as
(2)σrs,rs′q=cov[Qrs,Qrs′],∀rs,rs′∈R.
The corresponding covariance matrix of traffic demands of all OD pairs can be expressed as
(3)Σq={σrs,rs′q}|R|×|R|.
The value of σrs,rs′q may be positive, zero, or negative. It is assumed that the OD demands of all OD pairs follow multivariate normal distribution, that is Q~MVN(q,Σq,), where q and Σq are fixed and known. Let Frsk be the random traffic flow on path k∈Krs with its mean frsk=E[Frsk], where Krs is the path set between OD pair rs and K=⋃rs∈RKrs. For convenience, F and f are denoted as the |K|-vectors of (…,Frsk,…)T and (…,frsk,…)T for all k∈Krs and rs∈R, respectively. The path flows and OD demands satisfy the following flow conservation condition:
(4)Q=ΛF,
where Λ is the OD-path incidence matrix. Then, the following conservation conditions hold:
(5)q=E[Q]=E[ΛF]=ΛE[F]=Λf.
Equation (5) can be rewritten as
(6)qrs=∑k∈Krsfrsk,∀rs∈R.
It is assumed that the path flow is a product of the corresponding path choice proportion and the OD demand as follows [27]:
(7)Frsk=prskQrs,∀k∈Krs,rs∈R,
where prsk is the path choice proportion of the traffic flow on path k∈Krs of vehicle, which is assumed to be constant of the probability [24]. Then, it follows from (7) that
(8)frsk=prskqrs,∀k∈Krs,rs∈R.
The covariance between Frsk and Frs′k′ can be deduced as
(9)σrs,rs′f,k,k′=cov[Frsk,Frs′k′]=prskprs′k′cov[Qrs,Qrs′]=prskprs′k′σrs,rs′q,∀k∈Krs,k′∈Krs′,rs,rs′∈R.
The corresponding covariance matrix of path flows can be expressed as
(10)Σf={σrs,rs′f,k,k′}|K|×|K|.
According to (4), the covariance conservation condition between path flows and OD demands is expressed as
(11)Σq=ΛΣfΛT.
Denote δrsk,a as the element of the link-path incidence matrix. δrsk,a=1, if path k uses link a; otherwise, δrsk,a=0. Then, the conservation condition of the estimated link and path flows is expressed as
(12)Va=∑rs∈R∑k∈Krsδrsk,aFrsk,∀a∈A,
where Va is the random traffic flow on link a. The mean link flow is denoted as va=E[Va]. It follows from (12) that
(13)va=∑rs∈R∑k∈Krsδrsk,afrsk=∑rs∈R∑k∈Krsδrsk,aprskqrs,∀a∈A.
It can be seen from (13) that the mean link flow is a linear function with respect to the path choice proportions, which can be expressed as follows:
(14)va=va(p),∀a∈A,
where p is denoted as the |K|-vector of path choice proportions (…,prsk,…)T, all k∈Krs and rs∈R. Also, the conservation condition of the link and path flow covariance can be obtained as
(15)σa,a′v=cov[Va,Va′]=cov[∑rs∈R∑k∈Kδrsk,aFrsk,∑rs′∈R∑k′∈Kδrs′k′,a′Frs′k′]=∑rs∈R∑k∈K∑rs′∈R∑k′∈Kδrsk,aδrs′k′,a′cov[Frsk,Frs′k′]=∑rs∈R∑k∈K∑rs′∈R∑k′∈Kδrsk,aδrs′k′,a′σrs,rs′f,k,k′=∑rs∈R∑k∈K∑rs′∈R∑k′∈Kδrsk,aδrs′k′,a′prskprs′k′σrs,rs′q,∀a,a′∈A,
where σa,a′v is the covariance between link flows Va and Va′, a,a′∈A. It can be seen from (15) that the covariance of link flows is a function with respect to the path choice proportions, which is expressed as:
(16)σa,a′v=σa,a′v(p),∀a,a′∈A.


## 2.2. Reliability-Based Traffic Assignment Problem

Under demand uncertainty, the link and path travel times stochastically fluctuate from day to day, indicated asTa(Va(p),ua) and Trsk, respectively. Let A¯⊆A be a subset of links which are implemented the congestion pricing scheme and u=(…,ua,…)Ta∈A¯ denote the vector of link tolls, where ua is the toll on link a∈A¯. Then, the link travel time function for link a∈A¯ can be defined as the following modified Bureau of Public Roads (BPR) function:
(17)Ta(Va(p),ua)=ta0(1+α(Va(p)ca)n)+1βua,∀a∈A¯,
where α is a parameter of link performance function and β>0 is a constant which represents the value of time (VOT). To facilitate the presentation of the essential idea, it is assumed that the VOTs of all travelers are same. For other links, the original BPR function is used as the link time function:
(18)Ta(Va(p),ua)=ta0(1+α(Va(p)ca)n),∀a∈A¯∖A,
where A¯∖A represents the link set, for which toll is not charged on the link. According to the method in Clark and Watling [24], (16) and (17), the mean and covariance of link travel times can be deduced, which are the functions with respect to p and u. The mean path travel time can be expressed as a function with respect to p and u as follows:
(19)trsk(p,u)=∑a∈Aδrsk,ata(p,u),∀k∈Krs,rs∈R,
where ta(p,u) is the travel cost on a∈A; trsk(p,u) is the travel cost on path k∈Krs. Similarly, the variance of path travel times can be expressed as
(20)σrst,k(p,u)=cov[Trsk,Trsk]=cov[∑a∈Aδrsk,aTa(p,u),∑a′∈Aδrsk,a′Ta′(p,u)]=∑a∈A∑a′∈Aδrsk,aδrsk,a′cov[Ta(p,u),Ta′(p,u)]=∑a∈A∑a′∈Aδrsk,aδrsk,a′σa,a′t(p,u),∀k∈K,rs∈R,
where Trsk is the path travel time on path k∈Krs, E[Trsk]=trsk; Ta and Ta′ are link travel times on links a∈A and a′∈A, respectively; σa,a′t is the covariance of link travel times on a∈A and a′∈A.Since travelers’ path choice decisions will be influenced by the uncertain OD demand variations, the decision of road pricing is also dependent on such stochasticity. To consider this effect, a reliability-based stochastic user equilibrium (RSUE) model [27] is adopted to account for the travelers’ reliability-based path choice behaviors in the road pricing problem. In this RSUE model, the effective travel time, t^rsk, is used as the path choice criterion, which is defined as the summation of the mean travel time, trsk, and the safety margin srsk [32]:
(21)t^rsk(p,u)=trsk(p,u)+srsk(p,u),∀k∈K,rs∈R.
The value of srsk can be obtained by solving the following chance-constrained minimization problem:
(22)minsrskt^rsk=trsk+srsks.t.Pr[Trsk≤t^rsk]≥ρ∀k∈K,rs∈R,
where ρ is the confidence level of travel time reliability. A high value of ρ means that the travelers would prefer setting a large safety margin of path travel time in order to guarantee a high on-time arrival probability. On the other hand, a low value of ρ means the travelers would prefer tolerating a high risk of on-time arrival. The effective path travel time can be calculated that
(23)t^rsk(p,u)=trsk(p,u)+Φ-1(ρ)σrst,k(p,u),∀k∈K,rs∈R,
where Φ-1(·) is the inverse of cumulative function of standard normal distribution.The reliability-based stochastic user equilibrium could be reached, in which for each OD pair no traveler can decrease his/her perceived disutility by unilaterally changing their paths. In the Logit-based RSUE model, the path choice proportionprsk, which is defined in (7), can thus be specified by the following formula:
(24)prsk=exp(-θt^rsk(p,u))∑j∈Krsexp(-θt^rsj(p,u))=wrsk(p,u),∀k∈K,rs∈R,
where θ is the dispersion parameter on travelers’ perception errors of effective travel time. For the sake of convenience, we denote the path choice function prsk as wrsk(p,u) and the set notation can be denoted as:
(25)W(p,u)=(…,wrsk(p,u),…)T.
Meanwhile, it is well known that level of service on the network would exert an impact on the OD demand [33]. Therefore, the mean OD demand is viewed as a function with respect to the expected disutility of travel for each OD pair:
(26)qrs(π)=qrs¯exp(-ηπ),
where qrs¯ indicates the potential demand for OD pair rs, and η denotes the elastic coefficient. The expected disutility can be attained by
(27)πrs=-1θIn∑iexp(-θ·t^rsk(p,u)).
Then, the vector form of (24) considering elastic demand yields the following fixed point problem:
(28)(pq)=(W(p,u)q(t^rsk(p,u))).


## 2.3. Optimization of Congestion Charges in a Single Region

Recently, an increasing number of transportation researchers have recognized that demand uncertainty plays an important role in the decision making of transportation management. Under demand uncertainty, the expected value of total system travel time, as an important measure, is always adopted to evaluate the system performance. Meanwhile, the variation of total network travel time could bring troubles for transportation planning as well as the mean total travel time. Theoretically, the uncertainty of demand will directly lead to variation of the travel time, which influences decision making for administrators and travelers. For decision maker, it is difficult to evaluate the level of service of the road as travel time stochastically fluctuates from day to day. On the other hand, for the travelers, the variation of the travel time may result in late arrival to the destination, which influences their path and departure time choices. In this regard, the variation of total travel time should be considered in the optimization objective for the pricing problem. To facilitate the model formulation, we only take into account the minimization of mean total travel time as the objective of the pricing problem. This is not to deny the importance of the higher moment of the total travel time.The congestion models in previous studies are assumed to alleviate the traffic congestion over the whole network, which is managed by a central authority. Therefore, the central authority will be concerned with the mean total travel time cost on the network. The corresponding road pricing is objectived comprises of the total user benefit and the mean total travel time cost:(29)maxuSW=∑rs∈R∫0qrs(u)qrs-1(ω)dω-E[TTT(p,u)],
where at RSUE the mean of total travel time (E[TTT(p,u)]) can be calculated as
(30)E[TTT(p,u)]=E[∑a∈A(Ta(p)-1αua)·Va(p(u))].
Equation (30) can be calculated using the method proposed by Clark and Watling [24]. It is noticeable that the following mathematical inequality generally holds:
(31)E[∑a∈A(Ta(p)-1αua)·Va(p(u))]≠∑a∈AE[Ta(p)-1αua]·E[Va(p(u))].
In practice, the regional road systems may be freely managed by the separate transportation authorities on the optimizations of toll level and toll location. Here, we introduce the stochastic pricing problem where only one local region performs pricing scheme. As stated by Zhang et al. [9], the optimization objective function for single region pricing scheme is different from that of the centric pricing scheme with a central authority. The former aims to maximize the social welfare just for its own residents, who live in its local administrative region whereas the later concerns the social benefit of all users on the whole network. In this study, we extend the objective function to the stochastic traffic network and consider the stochastic flows resulted from the demand uncertainty. The regional authority only takes into account the trips with origins that locate at its own regime. The pricing problem considering reliability-based user equilibrium can be formulated as follows (Model A):
(32)maxuSW=∑rs∈Ri∫0qrs(u)qrs-1(ω)dω+E[∑a∈A¯iua·Va(p(ui))∑a∈A¯iua·Va(p(ui))-∑rs∈Ri∑k∈KFrsk(p(u))·Trsk(p(u))]
subject to
(33)(pq)=(W(p,u)q(t^rsk(p,u))),(34)u_a≤ua≤u¯a,∀a∈A-i,
where Ri denotes the OD pairs with the origins in region; A¯i denotes the links in region i. In the optimization problem, u is the decision variable, and the path choice proportion (p) is the constant probability, which can be determined by the fixed point problem in (33). The constraint (34) sets the upper and lower bounds for the toll charges.It should be stressed that the social benefit expressed in (32) concerns only the local region i that implements congestion pricing, while the stochastic equilibrium flow pattern is characterized by the choice decisions of all users in all regions in the network.


## 2.4. Competitive Behavior of Pricing Problem among Multiple Regions

In this section, we study the competitive behavior of the scenario that several local authorities implement congestion pricing independently. LetI={1,2,…,|I|} indicate the set of regions in which congestion pricing schemes are implemented, and i∈I. Let Ri denote the set of O-D pairs for all residents living in this region, which is a subset of R, and R=∪i∈IRi. The set of candidate toll links A¯i is a subset of A-. Let ui be the set of tolls ua on the links a∈A-i, and u=∪i∈Iui. Based on the current decisions of other regions, each region designs its own pricing scheme with the objective of maximizing its own social benefit. Once an authority makes change of it’s toll levels, other authorities will make their best responses of adjusting their toll levels. The competition with theses mutual responses can be characterized as a Nash game.The optimal toll levels for a specific regional authorityi can be obtained by solving a similar optimization model as proposed in Section 2.3. For region i, its authority aims to maximize its own social welfare by setting toll charges in its regime, in which the network users follow the reliability-based stochastic user equilibrium principle. Taking the viewpoint of region i, the Nash equilibrium model is formulated as follows (Model B):
(35)maxuiSW(ui∣ui∖u)=∑rs∈Ri∫0qrs(ui)qrs-1(ω)dω+E[∑a∈A¯iua·Va(p(ui))∑a∈A¯iua·Va(p(ui))-∑rs∈Ri∑k∈KFrsk(p(ui))·Trsk(p(ui))]
subject to constraints (33) and (34).In this pricing scheme, eventually, all the regions are self-best responding to each other, named a Nash equilibrium, that no player can change his pricing strategy unilaterally to obtain a better result. The outcome of the Nash game can be obtained by iteratively solving the above pricing problem for all the players.


## 2.5. Cooperative Congestion Pricing among Multiple Regions

In Section2.4, we propose a Nash equilibrium model to capture the competitive behavior among the authorities in different regions. Each authority sets its own pricing objective to improve the social welfare independently. But such competition may actually be detrimental to the travelers from other regions of the increasing travel burden. In this regard, the competitive pricing scheme may do harms to traffic efficiency of the whole network. Therefore, the cooperative manner is recommended. We propose a pricing model in which the local authorities cooperate to maximize the total social welfare of travelers in the regions that implement the pricing schemes. All elements used in this subsection are the same as those in Section 2.4, except that the regional authorities behave in a cooperative manner. The congestion pricing model is formulated as follows (Model C):
(36)maxuiSW=∑i∈I{∑rs∈Ri∫0qrs(ui)qrs-1(ω)dω}+∑i∈I{E[∑a∈A¯iua·Va(p(ui))∑a∈A¯iua·Va(p(ui))-∑rs∈Ri∑k∈KFrsk(p(ui))·Trsk(p(ui))]},
where the constraints are also the traffic flow equilibrium constraint and the boundary constraint for the design variable, which is formulated by (33) and (34).It should be stressed that, as pointed out by Zhang et al. [9], whether such cooperation can be achieved depends on the benefit gain of each player under the cooperative manner. If all regional authorities can benefit from the cooperation, the agreement of the cooperation would be achieved easily. In contrast, when some regions suffer a loss in the cooperative scheme, they prefer competing with other regions. However, if the regions that gain more benefit are willing to compensate the regions that suffer loss, the alliance may still hold.In this section, we propose the competitive and cooperative congestion pricing models under demand uncertainty. To the best of our knowledge, Zhang et al. [9] have made comprehensive analyses of noncooperative behaviors of the road pricing problem among multiple regions. The proposed models differ from the most related studies, such as Zhang et al. [9], of the traffic conditions. Our models are based on the stochastic traffic flows and the corresponding RSUE principle, while the model in Zhang et al. [9] is based on the deterministic traffic flows following the user equilibrium principle. This study makes twofold contribution to the literature. First, travelers’ reliability-based path choice behaviors can be reflected by the RSUE constraint (33). It makes an obvious difference from the user equilibrium principle in previous studies by considering travelers’ risk-taking behavior. Generally, the risk-taking preference is important for a stochastic transport system because it exerts an important impact on both individual travel activity and system-level decision making. Furthermore, the competitive and cooperative behaviors of the pricing problem on a stochastic network have been discussed by incorporating the mean total travel time into the optimization objectives.


## 3. Solution Algorithm

The proposed pricing optimization models are inherently bilevel programs, in which the upper level is to optimize the pricing objective and the lower level is the RSUE traffic assignment. As the proposed bilevel program is by nature nonlinear and non-convex, the global optimal solution is difficult to be obtained by using the conventional optimization algorithms. Existing effective algorithms for solving the nonconvex bilevel programming problems are meta-heuristic, including the genetic algorithm, simulated annealing method, and sequential quadratic programming, to name but a few. These methods search the local optimal solution in an evolutionary manner based on the traffic flow patterns in the lower-level program. The lower-level traffic assignment problem formulated as the fixed-point problem can be solved by the Method of Successive Averages [25, 26].Since the transportation assignment problem is integrated as a nonlinear constraint, we develop a heuristic solution algorithm, which combines the penalty function method, to solve the proposed models. The penalty function method is used to cope with the equilibrium constraint and the boundary constraint. The constrained optimization problem can be further transformed into an unconstrained one as follows:(37)minuμ1(j)∥min{u_,u}∥2+μ2(j)∥min{u,u¯}∥2+μ3(j)∥p-W(p,u)∥2-SW(p,u),
where μ1,  μ2, and μ3 are three positive penalty coefficients, ∥·∥ is the Euclidean norm of a vector. For convenience, denote the penalty term as follows:
(38)y=μ1(j)∥min{u_,u}∥2+μ2(j)∥min{u,u¯}∥2+μ3(j)∥p-W(p,u)∥2.
Obviously, it is difficult to obtain the gradient of the objective function (37) due to the complexity of g1(p,u), g2(p,u), and W(p,u). Therefore, some derivative-free optimization methods could be employed for solving the minimization problem (37), such as the simplex search method [34] and generalized pattern search methods [35, 36]. In this paper, the simplex search method [34] is used to solve the unconstrained optimization problem (37), which is available in the Matlab optimization toolbox by the subroutine “fminsearch”. The flowchart of this method is shown in Figure 1.Figure 1
The flowchart of the proposed solution algorithm.


## 4. Numerical Examples

### 4.1. Preliminary

The numerical examples are used to illustrate: (a) the difference between two pricing strategies (b) effects of travelers’ reliability-based path choice behavior on pricing schemes. In the numerical study, a small network shown in Figure2 is employed to demonstrate the property of the proposed model. There are 6 nodes, 10 links, and 4 O-D pairs on the network. The network is partitioned into two regions, A and B, by dash line X-X. The candidate links to be charged are depicted with block dash-dot lines. The potential traffic demand for each OD pair and the coefficient of standard deviation (S.D.) of the actual demand are given in Table 1. Table 2 provides the link performance parameters, ta0 and ca.Table 1
Potential OD demands in the network.
OD pair
2→1
2→5
6→5
6→1
q
¯
r
s
800
500
500
600
Coefficient  of S.D.
0.5
0.5
1.0
1.0Table 2
Parameters used in link performance functions.
Number
1
2
3
4
5
6
7
8
9
10
t
a
0
8.0
4.0
4.0
10.0
10.0
14.0
14.0
4.0
4.0
8.0
c
a
300
300
300
400
400
400
400
300
300
200Figure 2
A small network for numerical examples.The elastic coefficient of demand function,η, is set as 0.05 and the dispersion parameter, θ, is set as 0.1. For the sake of simplicity, it is assumed that the traffic demands between two OD pairs are independent with each other (i.e. σrs,r′s′q=0). α=0.15, n=1, β=1, and η=0.05  in  (17), (18), and (26). Meanwhile, the path flows, and link and path travel times are all assumed mutually independent and follow normal distributions. The convergence stopping tolerance τ is set as 10-3. The solution code is run on Windows 7 system with the following attributes: Intel Core i5-2520 2.5 GHz×2 and 4 GB RAM.


### 4.2. Pricing Outcomes of Cooperative and Competitive Schemes

The pricing outcomes of cooperative and competitive schemes can be obtained by solving Models B and C, respectively. LetSWA, SWB, SWT denote the social welfare for Region A, B, and the whole network respectively. The network is comprised of two regions that both are considered in the cooperative pricing scheme. So the pricing objective in Model C is equivalent to that in (29), which is proposed for the conventional stochastic pricing model with a central authority. As mentioned by Shao et al. [25], the mean values of stochastic flows will be equal to those in the deterministic traffic scenario if the following conditions are satisfied: a linear link travel time function is adopted and the travel time reliability is set as risk neutral (ρ=50%). It should be stressed that, in spite of this, the optimization objective for stochastic pricing scheme is still different from deterministic pricing scheme due to the fact that the deviations of both flow and travel time are taken into account in the objective function. Two scenarios of different travelers’ risk-taking behaviors, namely ρ=50% and ρ=90%, are constructed to test the pricing effects of two pricing schemes. The pricing results for cooperative and competitive schemes are provided in Table 3. Before comparing the results of two pricing schemes, we first introduce the equilibrium of competitive pricing.Table 3
Pricing results for cooperative and competitive schemes.
Confidence level (ρ)
Pricing scheme
Optimal solutions
Social welfare of region A
Social welfare of region B
Total Social welfare
u
1
u
2
u
8
u
10
(SWA)
(SWB)
(SWT)
50%
cooperation
16.36
7.81
7.55
17.78
12997.12
9374.28
22371.40
competition
13.83
12.32
13.37
14.36
12754.40
9259.83
22014.23
90%
cooperation
15.79
7.03
6.81
17.20
12965.86
9416.70
22382.56
competition
13.40
12.13
13.19
13.99
12708.41
9268.52
21976.93In the competitive scheme, both regions compete with each other to maximize their own social benefit. The authority in Region A sets pricing scheme on links 1 and 2, and the authority in Region B implements a pricing scheme on links 8 and 10. Each region makes a response to the actions in other regions by updating its tolls. If the toll levels in one region change, another region would respond by adjusting its own pricing scheme. This iterative process continues until reaching a Nash equilibrium. As the competition initiator, Region A makes the toll scheme in the first instance. At first competition round, tolls in Region B are zero.In this example, we illustrate the iterative competition process under the scenario that the confidence level of the travel time reliability is set as 90%. The competition reaches an equilibrium state after seven iterations. The reaction process and the optimal solution of the Nash game are given in Table4. At equilibrium, social welfares for Region A and B are 12708.41 and 9268.52, respectively, and the total social welfare for the whole network is 21976.93.Table 4
The process of the competitive congestion pricing (ρ=90%).
Iteration
Reactor
Optimal solutions
Social welfare of region A
Social welfare of region A
Total Social welfare
u
1
u
2
u
8
u
10
(SWA)
(SWB)
(SWT)
1
A
13.31
12.17
0.00
0.00
13900.31
6912.76
20813.06
2
B
13.31
12.17
13.19
13.98
12707.82
9265.94
21973.76
3
A
13.41
12.12
13.19
13.98
12708.11
9269.08
21977.19
4
B
13.41
12.12
13.18
13.97
12708.50
9269.28
21977.78
5
A
13.40
12.13
13.18
13.98
12708.80
9268.41
21977.21
6
B
13.40
12.13
13.19
13.99
12708.41
9268.52
21976.93
7
A
13.40
12.13
13.19
13.99
12708.41
9268.52
21976.93As shown in Table3, the pricing results in terms of optimal solution and social welfares are different between cooperative and competitive schemes since different objectives are considered in the two pricing optimizations. When the confidence level is fixed at 50%, under cooperation, the social welfare for Region A is 12997.12, the social welfare for Region B is 9374.28, and the total social welfare is 22371.40. However, under competition, the social welfare for Region A is 12754.40, the social welfare for Region B is 9259.83, and the total social welfare is 22014.23. Compared with cooperation, the competition makes Region, A and B suffer benefit losses about 242.7 and 114.5, respectively, and leads a degradation of the network system performance and so do the pricing results of the risk-aversion case with high travelers’ travel time reliability (ρ=90%). Therefore, it clearly reveals that the pricing effect in terms of system performance of the cooperative scheme is better than that of competitive scheme. Moreover, by comparing the results between two scenarios represented different travel time reliabilities, it can be seen that the pricing outcomes are different since the stochastic patterns depend on the travel time reliability. In the next subsection, we will discuss the impact of travel time reliability on the pricing effects of two pricing schemes.


### 4.3. Effects on Travelers’ Reliability-Based Path Choice Behaviors

The proposed model was carried out under different values ofρ that represent different risk-taking path choice behaviors. In this impact analysis, the travel time reliability increases from 10% to 90% that each step is 10%. Three travelers’ risk-taking behaviors are considered, namely risk-prone behavior (ρ<50%), risk-neutral behavior (ρ=50%), and risk-averse behavior (ρ>50%). A higher confidence level for travel time reliability means travelers will pay more attention to guaranteeing the on-time arrival by setting larger safety margins. For the case of ρ=50%, the proposed pricing model can be regarded to be carried out under conventional path choice behavior assumptions; that is, travelers take the mean path travel time as the path choice criteria. Figure 3 depicts the variation of the social welfare for each region with different travel time reliability. The variation of whole network performance with travel time reliability is shown in Figure 4. Benefit gain/loss of the cooperative scheme changing with travel time reliability is given in Figure 5.Figure 3
Social welfare for each region with different travel time reliability.Figure 4
Total social welfare with different travel time reliability.Figure 5
Benefit losses/gains in cooperation with different travel time reliability.From Figure3, it can be found that the social welfare of Region B increases gradually with the travel time reliability no matter what the pricing scheme is the Meanwhile, the increase of social welfare in the cooperative scheme is more apparent and dramatical than that in the competitive scheme. The  contrast, the social welfare of Region A decreases monotonically as the increase of the travel time reliability under both pricing schemes. Moreover, the reduction of social welfare under competition is more quick and obvious than that under cooperation. To evaluate the impact of travel time reliability on the network performance properly, we can pay attention to Figure 4, namely the variation of total welfare. For cooperation, the total social welfare increases from 22352.15 to 22382.56 as the travelers put more emphasis on the travel time reliability. However, for competition, the total social welfare decreases from 22039.82 to 21976.91 as the increase of the travel time reliability. On the whole, the total social welfare under the cooperative scheme is more than that of the competitive scheme no matter what travelers’ risk-taking behavior is. Although these impact analysis tests are network-specific, they cannot deny the fact that cooperation is more beneficial to improving the network system performance for all users.The difference of social welfare between two pricing schemes is plotted in Figure5 to illustrate the impact of travel time reliability. The difference of the social welfare is defined as the value of social welfare in cooperation minus social welfare in competition. A positive value means a benefit gain in cooperation, and vice visa. As shown in Figure 5, both regions and the whole network benefit from the cooperative manner under all different travel time reliability scenarios. Obviously, the higher travel time reliability, the higher benefit gain. In this regard, both regions would prefer a cooperative manner so as to obtain more benefit for themselves. Here, it should be pointed out that the result in this example does not mean that the regions will always benefit from the cooperative schemes, which have been demonstrated by the analyses in Zhang et al. [9]. From the above discussion, it is clear that the resultant competitive and cooperative pricing schemes are different for different risk-taking path choice behaviors. This finding indicates that different risk-taking path choice behaviors lead to different optimal toll levels and clearly proves that the reliability-based path choice behaviors should be considered in congestion pricing problems, particular for transportation network with demand uncertainty.


## 4.1. Preliminary

The numerical examples are used to illustrate: (a) the difference between two pricing strategies (b) effects of travelers’ reliability-based path choice behavior on pricing schemes. In the numerical study, a small network shown in Figure2 is employed to demonstrate the property of the proposed model. There are 6 nodes, 10 links, and 4 O-D pairs on the network. The network is partitioned into two regions, A and B, by dash line X-X. The candidate links to be charged are depicted with block dash-dot lines. The potential traffic demand for each OD pair and the coefficient of standard deviation (S.D.) of the actual demand are given in Table 1. Table 2 provides the link performance parameters, ta0 and ca.Table 1
Potential OD demands in the network.
OD pair
2→1
2→5
6→5
6→1
q
¯
r
s
800
500
500
600
Coefficient  of S.D.
0.5
0.5
1.0
1.0Table 2
Parameters used in link performance functions.
Number
1
2
3
4
5
6
7
8
9
10
t
a
0
8.0
4.0
4.0
10.0
10.0
14.0
14.0
4.0
4.0
8.0
c
a
300
300
300
400
400
400
400
300
300
200Figure 2
A small network for numerical examples.The elastic coefficient of demand function,η, is set as 0.05 and the dispersion parameter, θ, is set as 0.1. For the sake of simplicity, it is assumed that the traffic demands between two OD pairs are independent with each other (i.e. σrs,r′s′q=0). α=0.15, n=1, β=1, and η=0.05  in  (17), (18), and (26). Meanwhile, the path flows, and link and path travel times are all assumed mutually independent and follow normal distributions. The convergence stopping tolerance τ is set as 10-3. The solution code is run on Windows 7 system with the following attributes: Intel Core i5-2520 2.5 GHz×2 and 4 GB RAM.


## 4.2. Pricing Outcomes of Cooperative and Competitive Schemes

The pricing outcomes of cooperative and competitive schemes can be obtained by solving Models B and C, respectively. LetSWA, SWB, SWT denote the social welfare for Region A, B, and the whole network respectively. The network is comprised of two regions that both are considered in the cooperative pricing scheme. So the pricing objective in Model C is equivalent to that in (29), which is proposed for the conventional stochastic pricing model with a central authority. As mentioned by Shao et al. [25], the mean values of stochastic flows will be equal to those in the deterministic traffic scenario if the following conditions are satisfied: a linear link travel time function is adopted and the travel time reliability is set as risk neutral (ρ=50%). It should be stressed that, in spite of this, the optimization objective for stochastic pricing scheme is still different from deterministic pricing scheme due to the fact that the deviations of both flow and travel time are taken into account in the objective function. Two scenarios of different travelers’ risk-taking behaviors, namely ρ=50% and ρ=90%, are constructed to test the pricing effects of two pricing schemes. The pricing results for cooperative and competitive schemes are provided in Table 3. Before comparing the results of two pricing schemes, we first introduce the equilibrium of competitive pricing.Table 3
Pricing results for cooperative and competitive schemes.
Confidence level (ρ)
Pricing scheme
Optimal solutions
Social welfare of region A
Social welfare of region B
Total Social welfare
u
1
u
2
u
8
u
10
(SWA)
(SWB)
(SWT)
50%
cooperation
16.36
7.81
7.55
17.78
12997.12
9374.28
22371.40
competition
13.83
12.32
13.37
14.36
12754.40
9259.83
22014.23
90%
cooperation
15.79
7.03
6.81
17.20
12965.86
9416.70
22382.56
competition
13.40
12.13
13.19
13.99
12708.41
9268.52
21976.93In the competitive scheme, both regions compete with each other to maximize their own social benefit. The authority in Region A sets pricing scheme on links 1 and 2, and the authority in Region B implements a pricing scheme on links 8 and 10. Each region makes a response to the actions in other regions by updating its tolls. If the toll levels in one region change, another region would respond by adjusting its own pricing scheme. This iterative process continues until reaching a Nash equilibrium. As the competition initiator, Region A makes the toll scheme in the first instance. At first competition round, tolls in Region B are zero.In this example, we illustrate the iterative competition process under the scenario that the confidence level of the travel time reliability is set as 90%. The competition reaches an equilibrium state after seven iterations. The reaction process and the optimal solution of the Nash game are given in Table4. At equilibrium, social welfares for Region A and B are 12708.41 and 9268.52, respectively, and the total social welfare for the whole network is 21976.93.Table 4
The process of the competitive congestion pricing (ρ=90%).
Iteration
Reactor
Optimal solutions
Social welfare of region A
Social welfare of region A
Total Social welfare
u
1
u
2
u
8
u
10
(SWA)
(SWB)
(SWT)
1
A
13.31
12.17
0.00
0.00
13900.31
6912.76
20813.06
2
B
13.31
12.17
13.19
13.98
12707.82
9265.94
21973.76
3
A
13.41
12.12
13.19
13.98
12708.11
9269.08
21977.19
4
B
13.41
12.12
13.18
13.97
12708.50
9269.28
21977.78
5
A
13.40
12.13
13.18
13.98
12708.80
9268.41
21977.21
6
B
13.40
12.13
13.19
13.99
12708.41
9268.52
21976.93
7
A
13.40
12.13
13.19
13.99
12708.41
9268.52
21976.93As shown in Table3, the pricing results in terms of optimal solution and social welfares are different between cooperative and competitive schemes since different objectives are considered in the two pricing optimizations. When the confidence level is fixed at 50%, under cooperation, the social welfare for Region A is 12997.12, the social welfare for Region B is 9374.28, and the total social welfare is 22371.40. However, under competition, the social welfare for Region A is 12754.40, the social welfare for Region B is 9259.83, and the total social welfare is 22014.23. Compared with cooperation, the competition makes Region, A and B suffer benefit losses about 242.7 and 114.5, respectively, and leads a degradation of the network system performance and so do the pricing results of the risk-aversion case with high travelers’ travel time reliability (ρ=90%). Therefore, it clearly reveals that the pricing effect in terms of system performance of the cooperative scheme is better than that of competitive scheme. Moreover, by comparing the results between two scenarios represented different travel time reliabilities, it can be seen that the pricing outcomes are different since the stochastic patterns depend on the travel time reliability. In the next subsection, we will discuss the impact of travel time reliability on the pricing effects of two pricing schemes.


## 4.3. Effects on Travelers’ Reliability-Based Path Choice Behaviors

The proposed model was carried out under different values ofρ that represent different risk-taking path choice behaviors. In this impact analysis, the travel time reliability increases from 10% to 90% that each step is 10%. Three travelers’ risk-taking behaviors are considered, namely risk-prone behavior (ρ<50%), risk-neutral behavior (ρ=50%), and risk-averse behavior (ρ>50%). A higher confidence level for travel time reliability means travelers will pay more attention to guaranteeing the on-time arrival by setting larger safety margins. For the case of ρ=50%, the proposed pricing model can be regarded to be carried out under conventional path choice behavior assumptions; that is, travelers take the mean path travel time as the path choice criteria. Figure 3 depicts the variation of the social welfare for each region with different travel time reliability. The variation of whole network performance with travel time reliability is shown in Figure 4. Benefit gain/loss of the cooperative scheme changing with travel time reliability is given in Figure 5.Figure 3
Social welfare for each region with different travel time reliability.Figure 4
Total social welfare with different travel time reliability.Figure 5
Benefit losses/gains in cooperation with different travel time reliability.From Figure3, it can be found that the social welfare of Region B increases gradually with the travel time reliability no matter what the pricing scheme is the Meanwhile, the increase of social welfare in the cooperative scheme is more apparent and dramatical than that in the competitive scheme. The  contrast, the social welfare of Region A decreases monotonically as the increase of the travel time reliability under both pricing schemes. Moreover, the reduction of social welfare under competition is more quick and obvious than that under cooperation. To evaluate the impact of travel time reliability on the network performance properly, we can pay attention to Figure 4, namely the variation of total welfare. For cooperation, the total social welfare increases from 22352.15 to 22382.56 as the travelers put more emphasis on the travel time reliability. However, for competition, the total social welfare decreases from 22039.82 to 21976.91 as the increase of the travel time reliability. On the whole, the total social welfare under the cooperative scheme is more than that of the competitive scheme no matter what travelers’ risk-taking behavior is. Although these impact analysis tests are network-specific, they cannot deny the fact that cooperation is more beneficial to improving the network system performance for all users.The difference of social welfare between two pricing schemes is plotted in Figure5 to illustrate the impact of travel time reliability. The difference of the social welfare is defined as the value of social welfare in cooperation minus social welfare in competition. A positive value means a benefit gain in cooperation, and vice visa. As shown in Figure 5, both regions and the whole network benefit from the cooperative manner under all different travel time reliability scenarios. Obviously, the higher travel time reliability, the higher benefit gain. In this regard, both regions would prefer a cooperative manner so as to obtain more benefit for themselves. Here, it should be pointed out that the result in this example does not mean that the regions will always benefit from the cooperative schemes, which have been demonstrated by the analyses in Zhang et al. [9]. From the above discussion, it is clear that the resultant competitive and cooperative pricing schemes are different for different risk-taking path choice behaviors. This finding indicates that different risk-taking path choice behaviors lead to different optimal toll levels and clearly proves that the reliability-based path choice behaviors should be considered in congestion pricing problems, particular for transportation network with demand uncertainty.


## 5. Conclusions and Further Studies

This paper proposed two new optimization models for congestion pricing problem on stochastic transportation networks with demand uncertainty.  We analyze the stochastic road pricing schemes on a network with multiple regions. In practice, there may be several independent regions in a transportation network; regional authorities either prefer to maximize the system performance for the whole network or to maximize their own benefits separately. The cooperative and competitive behaviors among multiple regional decision makers have been investigated. Two pricing strategies, cooperation and competition, can be formulated as bi-level programs, in which stochastic flow equilibrium is considered. Different from most conventional modelling approaches of congestion pricing, the traffic demand of the study period was assumed to fluctuate from day to day. As a result, the travel time also varies accordingly. Under such circumstance, the conventional second-best congestion pricing model was extended to capture the effects of uncertainty for both the decision makers and the travelers. On one hand, the authorities aim to maximize the social welfare through setting the toll charges on the candidate links. The social welfare here is comprised of the total user benefit and the mean total travel time cost, which are dependent on the stochastic flow pattern. On the other hand, the travelers were assumed to minimize their effective travel time for path choices, which explicitly accounts for the risk-taking path choice behaviors under uncertainty condition. Such path choice behavior is formulated as an equality constraint for the congestion pricing optimization problem by a fixed point formulation.A heuristic solution algorithm is proposed in this paper. The proposed algorithm employs the penalty function method for constrained optimization problem, namely equilibrium flow constraint. Numerical examples demonstrated that, on stochastic network, the cooperative pricing scheme is more beneficial to improve the system performance than the competitive scheme. Meanwhile, both two pricing schemes were quite sensitive to the travelers’ risk-taking path choice behaviors; that is, the travel time reliability plays an important role in determining the pricing effects.Further studies could be carried out to extend the proposed model in the following aspects. First, the proposed model is formulated under demand uncertainty. How to simultaneously consider demand and supply uncertainties in the congestion pricing problem reveals important investigations. Furthermore, in the proposed model, the toll charges schemes are determined on the fixed locations of links. How to optimize toll charge locations as well as toll levels could be an interesting extension. Finally, the proposed solution algorithm is heuristic by nature. It is necessary to propose a more efficient solution algorithm in further investigations.



---

*Source: 696481-2013-04-14.xml*