(ε) on routekbetween OD pairωis defined as the probability that a trip arrives within the shortest average travel time plus the predefined acceptable travel time differenceε, i.e.,Abstract：In order to ensure on-time arrival when travelers make their trips, the stochastic network assignment model under uncertainty of travel time is investigated. First, based on travelers’ route choice behavior, the reliable travel time confidence level (RTTCL), which is the probability that a trip arrives within the shortest average travel time plus the acceptable travel time difference, is defined. Then, a reliability-based user equilibrium (RUE) model, which hypothesizes that for each OD pair no traveler can improve his/her RTTCL by unilaterally changing routes, is built. Since the traditional traffic assignment algorithms are not feasible to solve the RUE model, a quasi method of successive average (QMSA) is developed. Using Nguyen-Dupuis and Sioux Falls networks, the model and the algorithm are tested. The results show that the QMSA algorithm can rapidly converge to a high accuracy for solving the proposed RUE model, and the RUE model can provide a good response to travelers’ behavior in the stochastic network.
Keywords：user equilibrium; reliable travel time; acceptable travel time difference; confidence level; quasi method of successive average
Uncertainties are unavoidable in the transportation systems. Due to the travel time reliability, travelers do not know the exact time that they will arrive at the destination[1-3]. However, in many cases (e.g., going to work, catching the train, having a meeting), travelers care more about arrive time than travel time, and they prefer departing earlier (i.e., using perceptive average travel time plus an acceptable travel time difference as their travel time) to address travel time reliability.
According to travelers’ different route choice criteria under travel time variability, the stochastic network equilibrium model with uncertainties can be summarized according to the classification of different theories. The game theory-based model[4-5]assumes that the travelers are highly pessimistic about the travel time variability and behave in a very risk-averse manner. The prospect theory-based model[6]considers an endogenous reference point formation and updating scheme, where travelers hold desired on-time arrival probability requirements and update them according to the network state. The travel time budget (TTB) model[7-8]is defined as the average travel time plus a safety margin as an acceptable travel time. The percentile travel time (PTT) model[9]addresses the fact that the PTT is the minimum travel time needed to complete the journey with any given on-time arrival probability. The mean-excess travel time (METT) model[10-11]considers both the reliability factor and the un-reliability factor of the route travel time, and the METT is defined as the conditional expectation of the travel time larger than the TTB. The disutility or utility-based model[12]uses the combination of attributes to construct the disutility function. The late arrival penalized user equilibrium (LAPUE) model[13]assumes that users minimize a composite path disutility whose value is the generalized cost plus a late arrival penalty. The bi-objective model[14-15]uses bi-objective programming to minimize both the travel time and travel time reliability. In addition, the non-expected route travel time (NERTT) model[16]defines the NERTT as the expectation of the random route travel time under an appropriate distortion function of the original distribution. All the above traffic assignment models under uncertainties use either the utility or probabilityαto describe the travel time reliability. However, in a real traffic trip process, travelers only consider how much extra travel time they would like to take compared to the general trip time; they do not know their utilities or probabilitiesα. In addition,αis more difficult to measure than travelers’ acceptable travel time difference.
Considering travel time reliability in the travelers’ route choice decision process, a reliability-based user equilibrium (RUE) model is proposed. This model integrates the travel time and acceptable travel time difference into the network equilibrium framework. The definition of reliable travel time confidence level (RTTCL) which is the probability that a trip arrives within the shortest average travel time plus the acceptable travel time difference is presented. Then, the equilibrium condition of the RUE model is that for each OD pair no traveler can improve his/her RTTCL by unilaterally switching routes. Finally, a quasi method of successive average (QMSA) is designed to solve the RUE model.
1.1 Definition of reliable travel time confidence level
In the real traffic network system, travelers prefer departing earlier (i.e., using perceptive average travel time plus an acceptable travel time difference as their travel time) to deal with travel time reliability. This tradeoff considering the travel time and travel time reliability can be illustrated by the reliable travel time confidence level (RTTCL) as follows.
Definition1 The reliable travel time confidence level(ε) on routekbetween OD pairωis defined as the probability that a trip arrives within the shortest average travel time plus the predefined acceptable travel time differenceε, i.e.,
∀k∈Kω,ω∈W
(1)
where
is the random travel time on routekbetween OD pairω;E( ·) is the expectation operator;Wis the set of OD pairs;Kωis the set of routes connecting OD pairωand allKωconstituteK;
E() is the shortest average travel time between OD pairω.
1.2 Equilibrium conditions
It is reasonable to assume that travelers are willing to maximize their RTTCL when traveling under uncertainty. Then, the traffic reaches a long-term habitual traffic equilibrium. The RUE conditions can be defined as follows:
Definition2 The RUE is a network state such that for each OD pair no traveler can improve his/her RTTCL by unilaterally changing routes. In other words, all used routes between each OD pair have equal RTTCL, and no unused route has a higher RTTCL, i.e.,
∀k∈Kω,ω∈W
(2)
whereWdenotes the set of OD pairs for which travel demandqωis generated between OD pairω∈W;
denotes the traffic flow on routek∈Kω; πωdenotes the maximal RTTCL between OD pairω.
1.3 Reliable travel time confidence level under stochastic network
In this study, we consider the travel time reliability from the supply aspect. First, we will derive the probability distribution and the numerical characteristics of the route travel time. To describe the link cost, the bureau of public roads (BPR) function is used.
(3)
whereTa,
,xa, andCaare the travel time, free-flow travel time, flow, and capacity on linka, respectively;βandnare the deterministic parameters.
Assume that road capacities follow a uniform distribution, the route flows are mutually independent, andCais independent ofxa. We derive the mean and variance ofTaas
(4)
var(Ta)=
(5)
where
is the design capacity; the lower bound capacity is a fractionθaof. Assuming that the link travel times are independent[8, 11], we can represent the mean and standard deviation of route flow travel timeas
(6)
(7)
where
is the route-link incidence parameter whose value is 1 if linkais on routek; 0 otherwise. Using the central limit theorem, the route flow travel time tends to be normally distributed[8, 11]:
(8)
Then, based on the probability distribution of route travel time and the acceptable travel time difference, we obtain the RTTCL on routekbetween OD pairω:
∀k∈Kω,ω∈W
(9)
whereΦ( ·) is the standard normal cumulative distribution function.
Inspired by the method of successive average, we design a QMSA to solve the proposed RUE model.
1) Set tolerance errore, the working route setK, initial traffic flowf(0)which is free flow travel time, and initial iteration numbern=0.
2) Use Eqs.(4) to (8) to calculate the linkTaand path
travel time distribution.
3) Use Eq.(9) to update RTTCL.
4) Use Eqs.(10) to (11) to calculate the search directiond(n)and step sizeα(n), update the traffic flowf(n+1)=f(n)+α(n)d(n).
5 If ‖f(n+1)-f(n)‖/‖f(n)‖≤e, then stop.f(n+1)is the optimal solution. Otherwise, setn:=n+1, go to Step 2.
The direction and step size are set as
d(n)=f(n)′-f(n)
(10)
α(n)=
(11)
3.1 Nguyen-Dupuis network
The Nguyen-Dupuis network[17]is presented to illustrate the essential ideas of the RUE model, and the topology and characteristics of the test network are depicted in Fig.1. The network consists of 13 nodes, 19 links, and 4 OD pairs. We adopt the commonly used BPR performance function (based on Ref.[18], we setβ=0.15,n=4) in Eq.(3). The values ofθaand ε are equal to 0.3 and 10, respectively. Link and traffic demand characteristics are provided in Fig.1. The algorithm is coded in Matlab R2015b and tested on a personal computer with Intel(R) Core(TM) i7-5600U CPU 2.60 GHz, 8 GB memory.
Fig.1 Network topology, ODs and link characteristics
First, we show the convergence curve of the QMSA algorithm in Fig.2. We can see that the proposed QMSA algorithm can converge to a high accuracy. After 1 s CPU time, the tolerance error can reach approximately 1.0×10-4. Thus, the designed algorithm is an effective method to solve the proposed model.
Fig.2 Convergence of QMSA
Secondly, we examine the validity of the equilibrium results of the RUE model in Tab.1. We only show the equilibrium results of OD pairs (1-3) and (4-2) here. As expected, the RTTCL on all used routes for each OD pair are greater than or equal to those of unused routes. This satisfies the RUE equilibrium conditions, and the sum of route flows is equal to the OD demand which satisfies the demand conservation constraint. From this table, we can also see that for the used route, although the mean of travel time is larger, the standard deviation is smaller. We should note that the threshold is not equal to the difference of the longest and shortest mean of travel time of used route. For example, in OD pair (1-3), the longest and shortest mean of travel time of the used route are 58.58 and 54.59 s, respectively. Moreover, 58.58 s-54.59 s≠10 s. In fact, the mean travel time does not mean the real travel time on a trip. People choose the route where the probability of on-time arrival is within 64.59 s (i.e., the shortest average travel time plus the threshold: 54.59 s+10 s) is maximal. Also, in reality, there must be some people’s travel time that is greater than, equal to or less than 64.59 s.
Tab.1 Equilibrium results of the RUE model
ODRouteNo．SequenceofnodesRTTCLRouteflow/(veh·h-1)Meanoftraveltime/minStandarddeviation/min1⁃311⁃5⁃6⁃7⁃11⁃30．67110255．5020．5321⁃5⁃6⁃10⁃11⁃30．67116558．5813．5831⁃5⁃9⁃10⁃11⁃30．660059．1413．2141⁃12⁃6⁃7⁃11⁃30．67123354．5922．5951⁃12⁃6⁃10⁃11⁃30．663057．6716．4561⁃5⁃9⁃13⁃30．67130056．5518．164⁃274⁃5⁃6⁃7⁃8⁃20．67828143．1821．6484⁃5⁃6⁃7⁃11⁃20．637045．5921．6694⁃5⁃6⁃10⁃11⁃20．637048．6612．90104⁃9⁃10⁃11⁃20．67831947．1613．03114⁃5⁃9⁃10⁃11⁃20．621049．2212．85
Finally, we illustrate the route choices of travelers with different sensitivities. We obtain the RUE equilibrium solutions of traffic flow, mean and standard deviation of travel time on route 7 and 10 with respect to the travelers’ acceptable travel time difference ε (from 2 to 20). Larger acceptable travel time difference indicates that travelers are more sensitive (risk-averse) to travel time reliability. From Fig.3, we can find that with the increase of travelers’ acceptable travel time differences, the traffic flows on route 10 gradually switch to route 7; the traffic flows, means and standard deviations of travel time on route 7 increase, while they decrease on route 10. This means that more risk-averse travelers will spend a larger mean of travel time but a smaller standard deviation of travel time to ensure more on-time arrivals.
Fig.3 Route choices of travelers with different acceptable travel time differences
3.2 Sioux Falls network
The well-known Sioux Falls network which consists of 24 nodes, 76 links, and 550 OD pairs is used to demonstrate the applicability of the proposed algorithm.
The evolution processes of route flow, RTTCL and mean of travel time of two routes connecting OD pair (7, 14) are shown in Figs. 4 and 5. The link sequences of route 1 and route 2 are 7-18-16-10-11-14 and 7-8-6-5-4-11-14, respectively. Fig.4 shows that the route flows can rapidly converge to the equilibrium results. As expected, from Figs. 4 and 5, we can find that the equilibrium results satisfy the RUE conditions and the conservation constraint.
The RUE model that explicitly considers travelers’ acceptable travel time difference in travelers’ route choice decision process is proposed. RTTCL is defined as the probability that a trip arrives within the shortest average travel time plus the acceptable travel time difference. The proposed model was tested in the Nguyen-Dupuis andSioux Falls networks. The analysis results indicate that more risk-averse travelers will spend a larger mean of travel time but a smaller standard deviation of travel time to ensure more on-time arrivals. The quasi MSA algorithm is an effective method for solving the proposed RUE model and the RUE model can provide a good response to travelers’ behavior in the stochastic network.
Fig.4 Evolution processes of traffic flow for OD pair (7-14)
(a)
(b)Fig.5 Evolution processes of RTTCL and mean of travel time for OD pair (7-14). (a) Convergence of RTTCL; (b) Convergence of the mean travel time
[1]Abdel-Aty M A, Kitamura R, Jovanis P P. Exploring route choice behavior using geographic information system-based alternative routes and hypothetical travel time information input [J].TransportationResearchRecord,1995,1493: 74-80.
[2]Lam T C, Small K A. The value of time and reliability: measurement from a value pricing experiment[J].TransportationResearchPartE:LogisticsandTransportationReview, 2001,37(2): 231-251. DOI:10.1016/s1366-5545(00)00016-8.
[3]Franklin J, Karlstrom A. Travel time reliability for Stockholm roadways: Modeling mean lateness factor [J].TransportationResearchRecord:JournaloftheTransportationResearchBoard, 2009,2134: 106-113. DOI:10.3141/2134-13.
[4]Bell M G H, Cassir C. Risk-averse user equilibrium traffic assignment: An application of game theory[J].TransportationResearchPartB:Methodological, 2002,36(8): 671-681. DOI:10.1016/s0191-2615(01)00022-4.
[5]Szeto W, O’Brien L, O’Mahony M. Generalisation of the risk-averse traffic assignment [J].TransportationandTrafficTheory, 2007,17: 127-153.
[6]Xu H, Zhou J, Xu W. A decision-making rule for modeling travelers’ route choice behavior based on cumulative prospect theory[J].TransportationResearchPartC:EmergingTechnologies, 2011,19(2): 218-228. DOI:10.1016/j.trc.2010.05.009.
[7]Lo H K, Luo X W, Siu B W Y. Degradable transport network: Travel time budget of travelers with heterogeneous risk aversion[J].TransportationResearchPartB:Methodological, 2006,40(9): 792-806. DOI:10.1016/j.trb.2005.10.003.
[8]Wu X. Study on mean-standard deviation shortest path problem in stochastic and time-dependent networks: A stochastic dominance based approach[J].TransportationResearchPartB:Methodological, 2015,80: 275-290. DOI:10.1016/j.trb.2015.07.009.
[9]Nie Y M. Multi-class percentile user equilibrium with flow-dependent stochasticity [J].TransportationResearchPartB:Methodological, 2011,45(10): 1641-1659. DOI:10.1016/j.trb.2011.06.001.
[10]Chen A, Zhou Z. Theα-reliable mean-excess traffic equilibrium model with stochastic travel times[J].TransportationResearchPartB:Methodological, 2010,44(4): 493-513. DOI:10.1016/j.trb.2009.11.003.
[11]Xu X, Chen A, Cheng L, et al. A link-based mean-excess traffic equilibrium model under uncertainty[J].TransportationResearchPartB:Methodological, 2017,95: 53-75. DOI:10.1016/j.trb.2016.10.018.
[12]Szeto W Y, O’Brien L, O’Mahony M. Risk-averse traffic assignment with elastic demands: NCP formulation and solution method for assessing performance reliability [J].NetworksandSpatialEconomics, 2006,6(3/4): 313-332. DOI:10.1007/s11067-006-9286-7.
[13]Watling D. User equilibrium traffic network assignment with stochastic travel times and late arrival penalty[J].EuropeanJournalofOperationalResearch, 2006,175(3): 1539-1556. DOI:10.1016/j.ejor.2005.02.039.
[14]Wang J Y T, Ehrgott M, Chen A. A bi-objective user equilibrium model of travel time reliability in a road network[J].TransportationResearchPartB:Methodological, 2014,66: 4-15. DOI:10.1016/j.trb.2013.10.007.
[15]Sun C, Cheng L, Zhu S, et al. Multi-criteria user equilibrium model considering travel time, travel time reliability and distance [J/OL].TransportationResearchPartD:TransportandEnvironment, 2017. http://www.sciencedirect.com/science/article/pii/S1361920916304928. DOI:10.1016/j.trd.2017.03.002.
[16]Ji X, Ban X J, Li M, et al. Non-expected route choice model under risk on stochastic traffic networks [J/OL].NetworksandSpatialEconomics, 2017. https://link.springer.com/journal/11067. DOI:10.1007/s11067-017-9344-3.
[17]Nguyen S, Dupuis C. An efficient method for computing traffic equilibria in networks with asymmetrictransportation costs [J].TransportationScience, 1984,18(2): 185-202. DOI:10.1287/trsc.18.2.185.
[18]National Research Council.Highwaycapacitymanual[M]. Washington, DC, USA: Transportation Research Board, 2000.
References
摘要：为了让交通出行者能够准时到达目的地,对出行时间不确定性下的随机网络分配模型进行了研究.首先根据出行者出行行为,定义了可靠旅行时间置信水平(RTTCL),即出行者在可靠旅行时间(最短旅行时间加上可接受的旅行时间偏差)范围内到达目的地的概率;然后建立了基于可靠性的用户均衡(RUE)模型,即没有出行者可以通过单方面改变自己的出行路径来提高自己的RTTCL.由于传统的交通分配算法无法求解建立的RUE模型,因此设计了一种拟相继平均算法(QMSA).将建立的模型和算法分别在Nguyen-Dupuis和Sioux Falls网络上进行了测试,结果表明,算法能够很快收敛到较高精度,随机交通网络中人们的出行行为与建立的RUE模型一致.
关键词：用户均衡;可靠旅行时间;可接受旅行时间偏差;置信水平;拟相继平均算法
中图分类号：U491
JournalofSoutheastUniversity(EnglishEdition) Vol．33，No．3，pp．335⁃340Sept．2017 ISSN1003—7985
DOI:10.3969/j.issn.1003-7985.2017.03.012
Foundationitems：The National Natural Science Foundation of China (No. 51608115, 51578150, 51378119), the Natural Science Foundation of Jiangsu Province (No. BK20150613), the Scientific Research Foundation of Graduate School of Southeast University (No. YBJJ1679), the Scientific Innovation Research of College Graduates in Jiangsu Province (No. KYLX15_0150), the China Scholarship Council (CSC) Program.
Citation：Sun Chao, Cheng Lin, Li Dawei, et al. Stochastic network equilibrium model with reliable travel time confidence level[J]．Journal of Southeast University (English Edition),2017,33(3):330-334．
DOI：10.3969/j.issn.1003-7985.2017.03.012.