考虑出行者风险态度的最优路径搜索
|
摘要
由于交通系统存在不确定性,路径旅行时间会在一定范围内随机变化,面对随机交通网络,出行者表现出不同的风险态度,可以分为风险规避,风险中立和风险偏好3类。采用正态分布描述路段出行时间的随机性,分别考虑出行时间预算、超额出行时间、低额出行时间3类模型,研究出行者最优路径选择行为,此外还考虑了出行者多兴趣点出行的情况。提出一种标号修改算法,分别设置可靠度α=0. 75和α=0. 25,对不同风险态度出行者最优路径选择结果进行了分析,并在不同规模网络中对算法性能进行了测试。结果表明:在10 000节点大网络中,该算法平均运算时间约为100 ms,相比确定网络下的经典dijkstra算法约慢了42%,通过对比分析可知,该算法运行速度较快,能够满足实际应用需求。
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.
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.
引文
[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.Zhou Xi-yang,Yang Zhao-sheng,Zhang Wei,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.Du Mu-qing,Cheng Lin.Auction algorithm for shortest paths and its application in route guidance[J].Journal of Wuhan University of Technology,2012,12(36):1161-1165.
[4]Chen A,Zhou Z.Theα-reliable mean-excess traffic equilibrium model with stochastic travel times[J].Transportation Research Part B:Methodological,2010,44(4):493-513.
[5]Chen A,Zhao J.Path finding under uncertainty[J].Journal of Advanced Transportation,2005,39(1):19-37.
[6]Nie Y,Wu X.Shortest path problem considering ontime arrival probability[J].Transportation Research Part B,2009,43(6):597-613.
[7]Shao H,Lam W H K,Tam M 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]Zhang W Y,Guan W,Song L 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-Hooks E,Mahmassani H.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]Sen S,Pillai R,Joshi S,et al.A mean-variance model for route guidance in advanced travelerinformation systems[J].Transportation Science,2001,35(1):37-49.
[11]Chen B Y,Lam W H K,Sumalee A,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.Tang Xiao-yong,Cheng Lin.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.Li Xiong-fei,Zhang Hai-long,Liu Zhao-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.
[2]周熙阳,杨兆升,张伟,等.考虑干线协调控制的城市最优路径搜索算法[J].吉林大学学报:工学版,2016,46(6):1799-1806.Zhou Xi-yang,Yang Zhao-sheng,Zhang Wei,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.Du Mu-qing,Cheng Lin.Auction algorithm for shortest paths and its application in route guidance[J].Journal of Wuhan University of Technology,2012,12(36):1161-1165.
[4]Chen A,Zhou Z.Theα-reliable mean-excess traffic equilibrium model with stochastic travel times[J].Transportation Research Part B:Methodological,2010,44(4):493-513.
[5]Chen A,Zhao J.Path finding under uncertainty[J].Journal of Advanced Transportation,2005,39(1):19-37.
[6]Nie Y,Wu X.Shortest path problem considering ontime arrival probability[J].Transportation Research Part B,2009,43(6):597-613.
[7]Shao H,Lam W H K,Tam M 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]Zhang W Y,Guan W,Song L 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-Hooks E,Mahmassani H.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]Sen S,Pillai R,Joshi S,et al.A mean-variance model for route guidance in advanced travelerinformation systems[J].Transportation Science,2001,35(1):37-49.
[11]Chen B Y,Lam W H K,Sumalee A,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.Tang Xiao-yong,Cheng Lin.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.Li Xiong-fei,Zhang Hai-long,Liu Zhao-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.