吉林大学学报(工学版) ›› 2019, Vol. 49 ›› Issue (3): 720-726.doi: 10.13229/j.cnki.jdxbgxb20171143

• • 上一篇    下一篇

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

凃强1(),程琳1(),林芬2,孙超1   

  1. 1. 东南大学 交通学院,南京 210096
    2. 上海市政工程设计研究总院(集团)有限公司,上海 200092
  • 收稿日期:2017-11-22 出版日期:2019-05-01 发布日期:2019-07-12
  • 通讯作者: 程琳 E-mail:dqtu_1991@163.com;gist@seu.edu.cn
  • 作者简介:凃强(1991?),男,博士研究生.研究方向:交通运输规划与管理. E?mail:dqtu_1991@163.com
  • 基金资助:
    国家自然科学基金项目(51578150,51378119).

Finding shortest path considering traveler′s risk attitude

Qiang TU1(),Lin CHENG1(),Fen LIN2,Chao SUN1   

  1. 1. School of Transportation, Southeast University, Nanjing 210096, China
    2. Shanghai Municipal Engineering Design Institute Group Co. , Ltd. , Shanghai 200092, China
  • Received:2017-11-22 Online:2019-05-01 Published:2019-07-12
  • Contact: Lin CHENG E-mail:dqtu_1991@163.com;gist@seu.edu.cn

摘要:

由于交通系统存在不确定性,路径旅行时间会在一定范围内随机变化,面对随机交通网络,出行者表现出不同的风险态度,可以分为风险规避,风险中立和风险偏好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

图1

示例网络"

表1

模型参数取值"

模型λ(α)取值α取值
<0.5=0.5>0.5
TTBΦ-1(α)

风险

偏好

风险

中立

风险

规避

METT????exp-(Φ-1(α))222π(1-α)

风险

规避

风险

规避

风险

规避

MBTT-exp-(Φ-1(α))222πα

风险

偏好

风险

偏好

风险

偏好

图2

多兴趣点路径"

图3

Sioux Falls网络"

表2

不同模型的最优路径"

模型可靠度α最优路径均值方差出行时间
TTB0.751?3?4?5?6?8?13?14?241155.001020.001176.54
0.251?3?4?5?7?12?17?20?241145.002680.001110.08
METT0.751?3?4?5?6?8?13?14?241155.001020.001195.60
0.251?3?4?5?7?12?15?18?241145.002220.001164.96
MBTT0.751?3?10?21?22?23?241145.002680.001123.07
0.251?3?4?5?7?12?17?20?241155.003780.001076.85

表3

有效路径"

编号路径信息均值方差
11?3?4?5?6?8?13?14?241155.001020.00
21?3?4?5?7?12?17?20?241145.002680.00
31?3?4?5?7?12?15?18?241145.002220.00
41?3?4?5?7?12?17?20?241155.003780.00

图4

风险规避出行者出行时间与可靠度α的曲线"

图5

风险偏好行者出行时间与可靠度α的曲线"

图6

算法性能测试"

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.
[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.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
[1] 姚荣涵1,王铁成1,王建丽1,朱春钢2. 协调信号交叉口间路段上的车辆排队模型[J]. 吉林大学学报(工学版), 2011, 41(6): 1585 -1591 .
[2] 沈洁, 印桂生, 王向辉. P2P网络中基于非确定有限自动机的XML数据流过滤[J]. 吉林大学学报(工学版), 2012, 42(01): 134 -139 .
[3] 李志东, 杨武, 王巍, 苘大鹏. 基于扩散分析的网络安全威胁态势评估[J]. 吉林大学学报(工学版), 2012, 42(01): 145 -149 .
[4] 李静, 赵鼎, 朱琳, 刘俊杰. 节油驾驶控制策略速度门限匹配[J]. 吉林大学学报(工学版), 2010, 40(02): 320 -0323 .
[5] 周婧, 高印寒, 陈小林, 刘长英, 刘静. 基于单摄像机视觉测量系统的网络化数据融合[J]. 吉林大学学报(工学版), 2013, 43(01): 92 -97 .
[6] 赵玉, 李衍赫, 张培, 赵科, 刘伟超. 粘土的动力特性试验[J]. 吉林大学学报(工学版), 2015, 45(6): 1791 -1797 .
[7] 甄佳奇, 司锡才, 王桐, 那振宇. 基于虚拟阵列的相干信号快速测向算法[J]. 吉林大学学报(工学版), 2010, 40(03): 848 -0851 .
[8] 刘玉, 姚成, 那景新. 可提高客车侧翻安全性的变截面冲压立柱结构设计[J]. 吉林大学学报(工学版), 2014, 44(01): 17 -21 .
[9] 刘寒冰, 时成林, 谭国金. 考虑剪切滑移效应的叠合梁有限元解[J]. 吉林大学学报(工学版), 2016, 46(3): 792 -797 .
[10] 刘思培,刘大有,齐红,王佳强. 基于服务组链的Web服务组合方法[J]. 吉林大学学报(工学版), 2010, 40(01): 148 -0154 .