考虑出行者风险态度的最优路径搜索

doi:10.13229/j.cnki.jdxbgxb20171143

Abstract

Abstract:

Due to the uncertainty in transportation system, the travel time of paths varies within a certain range. For stochastic transportation network, travelers have different risk attitudes which can be divided into three categories including risk?averse, risk?neutral and risk?seeking attitudes. The normal distribution was used to describe the randomness of travel time of links, and models of travel time budget, mean?extra travel time and mean?below travel time were considered to study travelers′ path selection behavior, in addition, travelers with multi?Point of Interests (POIs) were also considered. A label?correcting algorithm was proposed to solve this problem, setting α=0.75 and α=0.25 respectively. The results of shortest path selection of travelers with different risk attitudes were analyzed. The computational performance of the algorithm was tested in different scale of networks. The results show that the average operation time of the label?correcting algorithm is about 100 ms in the network with 10 000 nodes, which is about 42% slower than the classic algorithm of dijkstra in the deterministic network. Comparative analysis shows that the algorithm is fast and can meet the requirements of practical application.

Key words: engineering of communications and transportation system, path finding, risk attitude, travel time budget, multi?point of interests (POIs), label?correcting algorithm

CLC Number:

U491.1

Qiang TU,Lin CHENG,Fen LIN,Chao SUN. Finding shortest path considering traveler′s risk attitude[J].Journal of Jilin University(Engineering and Technology Edition), 2019, 49(3): 720-726.

Figures/Tables 9

Fig.1

Table 1

Values of parameters in model"

模型	$λ (α)$ 取值	$α$ 取值
模型	$λ (α)$ 取值	$< 0.5$	$= 0.5$	$> 0.5$
TTB	$Φ - 1 (α)$	风险偏好	风险中立	风险规避
METT	$? ? ? ? e x p - (Φ - 1 (α)) 2 2 2 π (1 - α)$	风险规避	风险规避	风险规避
MBTT	$- e x p - (Φ - 1 (α)) 2 2 2 π α$	风险偏好	风险偏好	风险偏好

Table 1

Fig.2

Fig.3

Table 2

Table 3

Fig.4

Fig.5

Fig.6

References 13

1	赵宏伟,刘宇琦,董立岩,等. 智能交通混合动态路径优化算法[J]. 吉林大学学报：工学版,2018,48(4):1214⁃1223.
	Zhao Hong⁃wei Liu Yu⁃qi Dong Li⁃yan,et al. Dynamic route optimization algorithm based on hybrid in ITS[J]. Journal of Jilin University(Engineering and Technology Edition), 2018,48(4):1214⁃1223.
2	周熙阳,杨兆升,张伟,等.考虑干线协调控制的城市最优路径搜索算法[J]. 吉林大学学报：工学版,2016,46(6):1799⁃1806.
	ZhouXi⁃yang, YangZhao⁃sheng, ZhangWei,et al. Urban shortest path searching algorithm considering coordinate control of arterial intersections[J]. Journal of Jilin University(Engineering and Technology Edition), 2016,46(6):1799⁃1806.
3	杜牧青，程琳. 最短路径Auction算法及其在路径诱导中的应用[J]. 武汉理工大学学报，2012,12(36):1161⁃1165.
	DuMu⁃qing, ChengLin. Auction algorithm for shortest paths and its application in route guidance[J]. Journal of Wuhan University of Technology, 2012, 12(36): 1161⁃1165.
4	ChenA, ZhouZ. The α⁃reliable mean⁃excess traffic equilibrium model with stochastic travel times[J]. Transportation Research Part B: Methodological, 2010, 44(4): 493⁃513.
5	ChenA,ZhaoJ.Path finding under uncertainty[J].Journal of Advanced Transportation,2005,39(1):19⁃37.
6	NieY, WuX. Shortest path problem considering on⁃time arrival probability[J]. Transportation Research Part B, 2009, 43(6): 597⁃613.
7	ShaoH,LamW H K,TamM L.A reliability⁃based stochastic traffic assignment model for network with multiple user classes under uncertainty indemand[J]. Network and Spatial Economics,2006,6(3/4):173⁃204.
8	ZhangW Y, GuanW, SongL Y, et al. Alpha⁃reliable combined mean traffic equilibrium model stochastic travel times[J]. Journal of Central South University of Technology, 2013, 20(12): 3770⁃3778.
9	Miller⁃HooksE, MahmassaniH. Path comparisons for a priori and time⁃adaptive decisions instochastic, time⁃varying networks[J]. Europe Journal of Operation Research, 2003, 146(1):67⁃82.
10	SenS, PillaiR, JoshiS, et al. A mean⁃variance model for route guidance in advanced travelerinformation systems[J]. Transportation Science, 2001, 35(1): 37⁃49.
11	ChenB Y, LamW H K, SumaleeA, et al. Finding reliable shortest paths in road networks under uncertainty[J]. Networks and Spatial Economics, 2013, 13(2): 123⁃148.
12	唐小勇，程琳. 考虑转向延误的交通网络存储结构[J]. 公路交通科技，2007,24(1):134⁃138.
	TangXiao⁃yong, ChengLin. A representation of traffic network inclusive of node costs[J]. Journal of Highway and Transportation Research and Development, 2007, 24(1): 134⁃138.
13	李雄飞,张海龙,刘兆军,等. 用启发式算法求解最短路径问题[J]. 吉林大学学报：工学版,2011,41(1):182⁃187.
	LiXiong⁃fei,ZhangHai⁃long,LiuZhao⁃jun,et al. Problem for shortest path problem based on heuristic algorithm[J]. Journal of Jilin University(Engineering and Technology Edition), 2011,41(1):182⁃187.

Related Articles 15

[1]	Qiao⁃wen BAI,Zhao⁃wei QU,Yong⁃heng CHEN,Shuai XIONG,Chu⁃qing TAO. Modeling on trajectories of through vehicles with an unprotected left⁃turn phase under non⁃strict priority [J]. Journal of Jilin University(Engineering and Technology Edition), 2019, 49(3): 673-679.
[2]	Ning⁃bo CAO,Li⁃ying ZHAO,Zhao⁃wei QU,Yong⁃heng CHEN,Qiao⁃wen BAI,Xiao⁃lei DENG. Social force model considering bi⁃direction pedestrian slipstreaming behavior [J]. Journal of Jilin University(Engineering and Technology Edition), 2019, 49(3): 688-694.
[3]	Lei CHEN,Jiang⁃feng WANG,Yuan⁃li GU,Xue⁃dong YAN. Multi⁃source traffic data fusion algorithm based onmind evolutionary algorithm optimization [J]. Journal of Jilin University(Engineering and Technology Edition), 2019, 49(3): 705-713.
[4]	Chao⁃ying YIN,Chun⁃fu SHAO,Xiao⁃quan WANG. Influence of urban built environment on car commuting considering parking availability [J]. Journal of Jilin University(Engineering and Technology Edition), 2019, 49(3): 714-719.
[5]	CHEN Yong-heng,LIU Fang-hong,CAO Ning-bo. Analysis of conflict factors between pedestrians and channelized right turn vehicles at signalized intersections [J]. Journal of Jilin University(Engineering and Technology Edition), 2018, 48(6): 1669-1676.
[6]	LIU Zhao-hui, WANG Chao, LYU Wen-hong, GUAN Xin. Identification of data characteristics of vehicle running status parameters by nonlinear dynamic analysis [J]. Journal of Jilin University(Engineering and Technology Edition), 2018, 48(5): 1405-1410.
[7]	LIU Xiang-yu, YANG Qing-fang, KUI Hai-lin. Traffic guidance cell division based on random walk algorithm [J]. Journal of Jilin University(Engineering and Technology Edition), 2018, 48(5): 1380-1386.
[8]	LUAN Xin, DENG Wei, CHENG Lin, CHEN Xin-yuan. Mixed Logit model for understanding travel mode choice behavior of megalopolitan residents [J]. 吉林大学学报(工学版), 2018, 48(4): 1029-1036.
[9]	CHEN Yong-heng, LIU Xin-shan, XIONG Shuai, WANG Kun-wei, SHEN Yao, YANG Shao-hui. Variable speed limit control under snow and ice conditions for urban expressway in junction bottleneck area [J]. 吉林大学学报(工学版), 2018, 48(3): 677-687.
[10]	WANG Zhan-zhong, LU Yue, LIU Xiao-feng, ZHAO Li-ying. Improved harmony search algorithm on truck scheduling for cross docking system [J]. 吉林大学学报(工学版), 2018, 48(3): 688-693.
[11]	CHEN Song, LI Xian-sheng, REN Yuan-yuan. Adaptive signal control method for intersection with hook-turn buses [J]. 吉林大学学报(工学版), 2018, 48(2): 423-429.
[12]	SU Shu-jie, HE Lu. Transient dynamic congestion evacuation model of pedestrian at walk traffic planning crossroads [J]. 吉林大学学报(工学版), 2018, 48(2): 440-447.
[13]	HOU Xian-yao, CHEN Xue-wu. Use of public transit information market segmentation based onattitudinal factors [J]. 吉林大学学报(工学版), 2018, 48(1): 98-104.
[14]	WANG Zhan-zhong, ZHAO Li-ying, JIAO Yu-Ling, CAO Ning-bo. Social force model of pedestrian-bike mixed flow at signalized crosswalk [J]. 吉林大学学报(工学版), 2018, 48(1): 89-97.
[15]	GAO Kun, TU Hui-zhao, SHI Heng, LI Zhen-fei. Effect of low visibility in haze weather condition on longitudinal driving behavior in different car-following stages [J]. 吉林大学学报(工学版), 2017, 47(6): 1716-1727.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed

Comments

Recommended 10

[1]	YAO Rong-han,WANG Tie-cheng,WANG Jian-li,ZHU Chun-gang. Vehicle queue model for link between coordinated signalized intersections[J]. 吉林大学学报(工学版), 2011, 41(6): 1585 -1591 .
[2]	SHEN Jie, YIN Gui-sheng, WANG Xiang-hui. XML data filtering in P2P network based on non-determinate finite automata[J]. 吉林大学学报(工学版), 2012, 42(01): 134 -139 .
[3]	LI Zhi-dong, YANG Wu, WANG Wei, MAN Da-peng. Network security threat situation evaluation based on spread analysis[J]. 吉林大学学报(工学版), 2012, 42(01): 145 -149 .
[4]	LI Jing, ZHAO Ding, ZHU Lin, LIU Jun-Jie. Matching of velocity threshold for vehicle fuel saving driving control strategy[J]. 吉林大学学报(工学版), 2010, 40(02): 320 -0323 .
[5]	ZHOU Jing, GAO Yin-han, CHEN Xiao-lin, LIU Chang-ying, LIU Jing. Networked data fusion based on visual measure system with single camera[J]. 吉林大学学报(工学版), 2013, 43(01): 92 -97 .
[6]	ZHAO Yu, LI Yan-he, ZHANG Pei, ZHAO Ke, LIU Wei-chao. Experimental study of the dynamic characteristics of clay[J]. 吉林大学学报(工学版), 2015, 45(6): 1791 -1797 .
[7]	JUAN Jia-Ai, CI Ti-Cai, Wang-Dong, NA Zhen-Yu. Fast approach for direction estimation coherent signals based on virtual array[J]. 吉林大学学报(工学版), 2010, 40(03): 848 -0851 .
[8]	LIU Yu, YAO Cheng, NA Jing-xin. Structural design of variable cross-section stamping column to improve bus rollover safety[J]. 吉林大学学报(工学版), 2014, 44(01): 17 -21 .
[9]	LIU Han-bing, SHI Cheng-lin, TAN Guo-jin. Finite element solution of composite beam with effect of shear slip[J]. 吉林大学学报(工学版), 2016, 46(3): 792 -797 .
[10]	LIU Si-pei,LIU Da-you,QI Hong,WANG Jia-qiang. Service community chain based approach for web service composition[J]. 吉林大学学报(工学版), 2010, 40(01): 148 -0154 .

模型	可靠度α	最优路径	均值	方差	出行时间
TTB	0.75	1?3?4?5?6?8?13?14?24	1155.00	1020.00	1176.54
TTB	0.25	1?3?4?5?7?12?17?20?24	1145.00	2680.00	1110.08
METT	0.75	1?3?4?5?6?8?13?14?24	1155.00	1020.00	1195.60
METT	0.25	1?3?4?5?7?12?15?18?24	1145.00	2220.00	1164.96
MBTT	0.75	1?3?10?21?22?23?24	1145.00	2680.00	1123.07
MBTT	0.25	1?3?4?5?7?12?17?20?24	1155.00	3780.00	1076.85

编号	路径信息	均值	方差
1	1?3?4?5?6?8?13?14?24	1155.00	1020.00
2	1?3?4?5?7?12?17?20?24	1145.00	2680.00
3	1?3?4?5?7?12?15?18?24	1145.00	2220.00
4	1?3?4?5?7?12?17?20?24	1155.00	3780.00

Finding shortest path considering traveler′s risk attitude

RICH HTML

PDF (PC)