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

doi:10.13229/j.cnki.jdxbgxb20171143

摘要/Abstract

摘要：

由于交通系统存在不确定性，路径旅行时间会在一定范围内随机变化，面对随机交通网络，出行者表现出不同的风险态度，可以分为风险规避，风险中立和风险偏好3类。采用正态分布描述路段出行时间的随机性，分别考虑出行时间预算、超额出行时间、低额出行时间3类模型，研究出行者最优路径选择行为，此外还考虑了出行者多兴趣点出行的情况。提出一种标号修改算法，分别设置可靠度α=0.75和α=0.25，对不同风险态度出行者最优路径选择结果进行了分析，并在不同规模网络中对算法性能进行了测试。结果表明：在10 000节点大网络中，该算法平均运算时间约为100 ms，相比确定网络下的经典dijkstra算法约慢了42%，通过对比分析可知，该算法运行速度较快，能够满足实际应用需求。

关键词: 交通运输系统工程, 路径搜索, 风险态度, 出行时间预算, 多兴趣点, 标号修改法

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

中图分类号:

U491.1

凃强,程琳,林芬,孙超. 考虑出行者风险态度的最优路径搜索[J]. 吉林大学学报(工学版), 2019, 49(3): 720-726.

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.

图/表 9

图1

表1

模型参数取值"

模型	$λ (α)$ 取值	$α$ 取值
模型	$λ (α)$ 取值	$< 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 π α$	风险偏好	风险偏好	风险偏好

表1

图2

图3

表2

表3

图4

图5

图6

参考文献 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.

相关文章 15

[1]	白乔文,曲昭伟,陈永恒,熊帅,陶楚青. 非严格优先权下无左转专用相位直行车辆轨迹模型建立[J]. 吉林大学学报(工学版), 2019, 49(3): 673-679.
[2]	李志慧,钟涛,赵永华,胡永利,李海涛,赵景伟. 面向车辆自主驾驶的行人跟踪算法[J]. 吉林大学学报(工学版), 2019, 49(3): 680-687.
[3]	曹宁博,赵利英,曲昭伟,陈永恒,白乔文,邓晓磊. 考虑双向行人跟随行为的社会力模型[J]. 吉林大学学报(工学版), 2019, 49(3): 688-694.
[4]	罗小芹,王殿海,金盛. 面向混合交通的感应式交通信号控制方法[J]. 吉林大学学报(工学版), 2019, 49(3): 695-704.
[5]	陈磊,王江锋,谷远利,闫学东. 基于思维进化优化的多源交通数据融合算法[J]. 吉林大学学报(工学版), 2019, 49(3): 705-713.
[6]	尹超英,邵春福,王晓全. 考虑停车可用性的建成环境对小汽车通勤出行的影响[J]. 吉林大学学报(工学版), 2019, 49(3): 714-719.
[7]	陈永恒,刘芳宏,曹宁博. 信控交叉口行人与提前右转机动车冲突影响因素[J]. 吉林大学学报(工学版), 2018, 48(6): 1669-1676.
[8]	常山,宋瑞,何世伟,黎浩东,殷玮川. 共享单车故障车辆回收模型[J]. 吉林大学学报(工学版), 2018, 48(6): 1677-1684.
[9]	曲大义,杨晶茹,邴其春,王五林,周警春. 基于干线车流排队特性的相位差优化模型[J]. 吉林大学学报(工学版), 2018, 48(6): 1685-1693.
[10]	刘兆惠, 王超, 吕文红, 管欣. 基于非线性动力学分析的车辆运行状态参数数据特征辨识[J]. 吉林大学学报(工学版), 2018, 48(5): 1405-1410.
[11]	宗芳, 齐厚成, 唐明, 吕建宇, 于萍. 基于GPS数据的日出行模式-出行目的识别[J]. 吉林大学学报(工学版), 2018, 48(5): 1374-1379.
[12]	刘翔宇, 杨庆芳, 隗海林. 基于随机游走算法的交通诱导小区划分方法[J]. 吉林大学学报(工学版), 2018, 48(5): 1380-1386.
[13]	钟伟, 隽志才, 孙宝凤. 不完全网络的城乡公交一体化枢纽层级选址模型[J]. 吉林大学学报(工学版), 2018, 48(5): 1387-1397.
[14]	宗芳, 路峰瑞, 唐明, 吕建宇, 吴挺. 习惯和路况对小汽车出行路径选择的影响[J]. 吉林大学学报(工学版), 2018, 48(4): 1023-1028.
[15]	栾鑫, 邓卫, 程琳, 陈新元. 特大城市居民出行方式选择行为的混合Logit模型[J]. 吉林大学学报(工学版), 2018, 48(4): 1029-1036.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed

模型	可靠度α	最优路径	均值	方差	出行时间
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