• ISSN 0258-2724
  • CN 51-1277/U
  • EI Compendex
  • Scopus 收录
  • 全国中文核心期刊
  • 中国科技论文统计源期刊
  • 中国科学引文数据库来源期刊

一种基于交叉口信号延误的超路径规划方法

杜牧青 鞠姿彦 李大韦

杜牧青, 鞠姿彦, 李大韦. 一种基于交叉口信号延误的超路径规划方法[J]. 西南交通大学学报. doi: 10.3969/j.issn.0258-2724.20220387
引用本文: 杜牧青, 鞠姿彦, 李大韦. 一种基于交叉口信号延误的超路径规划方法[J]. 西南交通大学学报. doi: 10.3969/j.issn.0258-2724.20220387
DU Muqing, JU Ziyan, LI Dawei. Hyperpath Searching Algorithm Method Based on Signal Delay at Intersections[J]. Journal of Southwest Jiaotong University. doi: 10.3969/j.issn.0258-2724.20220387
Citation: DU Muqing, JU Ziyan, LI Dawei. Hyperpath Searching Algorithm Method Based on Signal Delay at Intersections[J]. Journal of Southwest Jiaotong University. doi: 10.3969/j.issn.0258-2724.20220387

一种基于交叉口信号延误的超路径规划方法

doi: 10.3969/j.issn.0258-2724.20220387
基金项目: 国家自然科学基金项目(72471083);江苏省科技厅项目(BZ2020016)
详细信息
    作者简介:

    杜牧青(1986—),男,副教授,博士,研究方向为交通运输规划与管理,E-mail:dumqhhu@hhu.edu.cn

  • 中图分类号: U491.2

Hyperpath Searching Algorithm Method Based on Signal Delay at Intersections

  • 摘要:

    城市道路中交叉口信号周期性变化会导致车辆出行的不确定延误,为降低车辆在交叉口处产生的信号延误,以路段旅行时间和交叉口期望延误最小为优化目标,提出一种改进的超路径规划方法. 首先,根据车辆到达交叉口的概率分布函数,推导出车辆在信号交叉口的期望等待时间和转向比例计算公式;其次,引入标号设定算法构建高性能超路径规划方法;最后,将改进的超路径规划方法应用于南京新街口区域的路网,通过最优超路径集合分析证实其适用性. 研究表明:与最短路出行策略相比,车辆遵循基于超路径规划方法的出行策略,在行进过程时从最优超路径集合中选择变换的行驶路线可降低67.1%的交叉口信号延误和22.3%的总旅行时间;此外,超路径出行策略可优化路网中的出行结构,缓解交通拥堵,实现流量均衡.

     

  • 图 1  公交超路径概念示意

    Figure 1.  Concept of hyperpath in public transport

    图 2  道路网络考虑路段延误的最优超路径[15]

    Figure 2.  A optimal hyperpath in the road network with the consideration of delays on road segments [15]

    图 3  车辆在交叉口6处的可行转向行为

    Figure 3.  Feasible turning movements at intersection 6

    图 4  ${y_{{r_{X,m}}}}$的分布函数

    Figure 4.  Distribution function of ${y_{{r_{X,m}}}}$

    图 5  不相邻转向的组合(单位:s)

    Figure 5.  Combination of non-adjacent turns (unit:s)

    图 6  相位不相邻${y_X}$的分布函数

    Figure 6.  Distribution function of ${y_X}$

    图 7  交叉口信号配时图(单位:s)

    Figure 7.  Intersection signal timing diagram (unit: s)

    图 8  相邻转向绿灯时间的组合

    Figure 8.  Combination of the green time for adjacent turns

    图 9  相位相邻${y_X}$的分布函数

    Figure 9.  Distribution function of ${y_X}$

    图 10  相邻两相位时间段分割

    Figure 10.  Segmentation of two adjacent phases

    图 11  不相邻两相位时间段分割

    Figure 11.  Segmentation of two non-adjacent phases

    图 12  局部方格网络示意图(单位:s)

    Figure 12.  Local grid-type network (unit:s)

    图 13  超路径网络中的标号定义

    Figure 13.  Definitions of labels in the hyperpath network

    图 14  起点38到终点37的最短路径和最优超路径

    Figure 14.  Shortest path and optimal hyperpath from origin 38 to destination 37

    图 15  网络流量分配

    Figure 15.  Traffic distribution in the network

    图 16  进口道(7,9)处转向选择对总旅行时间的影响

    Figure 16.  Total travel time versus the set of turns on entrance (7,9)

    图 17  进口道(7,9)转向选择对总旅行时间的影响

    Figure 17.  Total travel time versus the set of turns on entrance (7,9)

    表  1  信号配时变化对超路径集合元素的影响

    Table  1.   Influence of signal timing on hyperpath set

    序号 交叉口 周期
    /s
    相位
    1 /s
    相位
    2 /s
    相位
    3 /s
    路径 1
    时间 /s
    路径 2
    时间 /s
    组合
    期望 /s
    最优超
    路径
    1 A 110 40 50 20 131.4 149.3 121.6 A—B—C, A—D—C
    C 80 60 20 0
    2 A 150 80 20 50 202.6 127.1 130.1 A—D—C
    C 120 30 90 0
    3 A 47 12 15 20 124.4 138.8 125.1 A—B—C
    C 110 95 15 0
    下载: 导出CSV

    表  2  参数定义

    Table  2.   Notations

    符号 含义
    $ G(N,A) $  有向网络图,其中N表示网络中的节点集合,A表示网络中的路段集合
    ${\varGamma ^ - }(i)$ 流入节点$i$的路段集合
    ${\varGamma ^ + }(i)$ 流出节点$i$的路段集合
    i 节点标号
    j 节点 i 的下游节点标号
    k 节点j的下游节点标号
    S 终点
    r 起点
    ${m_k}$ 转向节点k的转向行为
    H 超路径的路段集合
    ${M_{i,j}}$ 进口道$(i,j)$处,属于超路径的转向行为集合
    $u_{i,j}$ 进口道$(i,j)$到终点的期望旅行时间
    $ p\{ (j,k)|i\} $  由节点 i 转向路段$ j—k $时,路段$ j—k $被选择的概率
    $ p\{ k|j\} $ 由节点 j 转向节点 k 时,节点 k 被选择的概率
    $ {P_{ {i,j} }} $  在节点i处,路段$ i—j $被选择的概率,满足$\displaystyle \sum\nolimits_{(i,j) \in {\varGamma ^ + }(i)} {P_{{i,j} }} = 1 $
    $c_{i,j}$ 路段$ i—j $的旅行时间
    $ \xi_{i,j,m_k} $ 从节点 i 经过节点 j 转向节点 k 的期望延误时间
    $ w_{i,j} $ 进口道为$ \left(i,j\right) $时,在节点 j 处的组合延误期望值
    下载: 导出CSV

    表  3  路径选择概率

    Table  3.   Path choice probability

    路径 路径走行路段 路径选择
    概率
    路径 1 38—7—9—10—14—17—18—
    19—20—44—22—26—32—37
    0.45
    路径 2 38—7—9—13—16—17—18—
    19—20—44—22—26—32—37
    0.55
    下载: 导出CSV

    表  4  两种路径出行策略对比

    Table  4.   Comparison between two routing strategies

    出行策略 路径 总旅行时间/s 总旅行时间降低率/% 总延误时间/s 总延误时间降低率/%
    最短路 路径 1 1 010.0 317.0
    超路径构成 路径 1或路径 2 784.8 22.3 104.2 67.1
    下载: 导出CSV

    表  5  进口道(7,9)的相关参数

    Table  5.   Related parameters of entrance (7,9)

    下游路段 对应转向行为 距终点的总旅行时间 路段旅行时间 延误时间 选择概率 组合延误时间 组合总旅行时间
    9—10 左转 555.3 s 79.0 s 22.1 s 45% 8.5 s 655.2 s
    9—13 直行 582.3 s 52.0 s 19.2 s 55%
    下载: 导出CSV

    表  6  进口道(19,20)的相关参数

    Table  6.   Related parameters of entrance (19,20)

    下游路段 对应转向行为 距终点的总旅行时间 路段旅行时间 延误时间 选择概率 组合延误时间 组合总旅行时间
    20—21 直转 283.6 s 13.0 s 31.1 s 13.8% 0 307.6 s
    20—44 右转 255.3 s 40.0 s 0 86.2%
    下载: 导出CSV
  • [1] 王芬芬. 合理的多路径算法研究[D]. 西安:长安大学,2017.
    [2] 段征宇,雷曾翔,孙硕,等. 随机时变车辆路径问题的多目标鲁棒优化方法[J]. 西南交通大学学报,2019,54(3): 565-572. doi: 10.3969/j.issn.0258-2724.20170617

    DUAN Zhengyu, LEI Zengxiang, SUN Shuo, et al. Multi-objective robust optimisation method for stochastic time-dependent vehicle routing problem[J]. Journal of Southwest Jiaotong University, 2019, 54(3): 565-572. doi: 10.3969/j.issn.0258-2724.20170617
    [3] HOFFMAN W, PAVLEY R. A method for the solution of the N th best path problem[J]. Journal of the ACM, 1959, 6(4): 506-514. doi: 10.1145/320998.321004
    [4] 刘辉平. 基于路网的路径规划问题研究[D]. 上海: 华东师范大学,2018.
    [5] DROSOU M, PITOURA E. Search result diversification[J]. ACM SIGMOD Record, 2010, 39(1): 41-47. doi: 10.1145/1860702.1860709
    [6] YEN J Y. Finding the K shortest loopless paths in a network[J]. Management Science, 1971, 17(11): 712-716. doi: 10.1287/mnsc.17.11.712
    [7] TORRIERI D. Algorithms for finding an optimal set of short disjoint paths in a communication network[J]. IEEE Transactions on Communications, 1992, 40(11): 1698-1702. doi: 10.1109/26.179933
    [8] YALLOUZ J, ROTTENSTREICH O, BABARCZI P, et al. Minimum-weight link-disjoint node-“somewhat disjoint” paths[J]. ACM Transactions on Networking, 2018, 26(3): 1110-1122. doi: 10.1109/TNET.2018.2823912
    [9] GOMES T, CRAVEIRINHA J. Efficient calculation of the most reliable pair of link disjoint paths in telecommunication networks[J]. European Journal of Operational Research, 2007, 181(3): 1055-1064. doi: 10.1016/j.ejor.2006.03.005
    [10] GOMES T, MARTINS L, FERREIRA S, et al. Algorithms for determining a node-disjoint path pair visiting specified nodes[J]. Optical Switching and Networking, 2017, 23: 189-204. doi: 10.1016/j.osn.2016.05.002
    [11] 倪明放,高石云,马峰,等. 多约束最短链路不相交路径的启发式算法[J]. 解放军理工大学学报(自然科学版),2013,14(1): 79-83.

    NI Mingfang, GAO Shiyun, MA Feng, et al. Heuristic algorithm for multi-constrained shortest link-disjoint paths[J]. Journal of PLA University of Science and Technology (Natural Science Edition), 2013, 14(1): 79-83.
    [12] LAI C N. Optimal node-disjoint paths in folded hypercubes[J]. Journal of Parallel and Distributed Computing, 2021, 147: 100-107. doi: 10.1016/j.jpdc.2020.09.005
    [13] 周加全. 基于改进遗传算法路径规划问题的研究[J]. 微型电脑应用,2021,37(11): 1-3,8. doi: 10.3969/j.issn.1007-757X.2021.11.002

    ZHOU Jiaquan. Research of path planning problem based on improved genetic algorithm[J]. Microcomputer Applications, 2021, 37(11): 1-3,8. doi: 10.3969/j.issn.1007-757X.2021.11.002
    [14] SPIESS H, FLORIAN M. Optimal strategies: a new assignment model for transit networks[J]. Transportation Research Part B: Methodological, 1989, 23(2): 83-102. doi: 10.1016/0191-2615(89)90034-9
    [15] BELL M G H. Hyperstar: a multi-path Astar algorithm for risk averse vehicle navigation[J]. Transportation Research Part B: Methodological, 2009, 43(1): 97-107. doi: 10.1016/j.trb.2008.05.010
    [16] MA J S, FUKUDA D, SCHMÖCKER J D. Faster hyperpath generating algorithms for vehicle navigation[J]. Transportmetrica A: Transport Science, 2013, 9(10): 925-948. doi: 10.1080/18128602.2012.719165
    [17] 高明霞,贺国光. 考虑交叉口延误和转向限制的弧标号最短路径算法[J]. 兰州交通大学学报,2011,30(6): 111-114. doi: 10.3969/j.issn.1001-4373.2011.06.026

    GAO Mingxia, HE Guoguang. An arc labeling algorithm for shortest path problem considering turn penalties and prohibitions at intersections[J]. Journal of Lanzhou Jiaotong University, 2011, 30(6): 111-114. doi: 10.3969/j.issn.1001-4373.2011.06.026
    [18] JU Z Y, DU M Q. Hyperpath searching algorithm considering delay at intersection and its application in CVIS for vehicle navigation[J]. Journal of Advanced Transportation, 2022, 2022: 2304097.1-2304097.15.
    [19] 杜牧青,程琳. 考虑交叉口转向延误的最短路径拍卖算法[J]. 西南交通大学学报,2010,45(2): 249-254. doi: 10.3969/j.issn.0258-2724.2010.02.015

    DU Muqing, CHENG Lin. Auction algorithm for shortest paths in road networks considering delays for intersection movements[J]. Journal of Southwest Jiaotong University, 2010, 45(2): 249-254. doi: 10.3969/j.issn.0258-2724.2010.02.015
    [20] ZILIASKOPOULOS A K, MAHMASSANI H S. A note on least time path computation considering delays and prohibitions for intersection movements[J]. Transportation Research Part B: Methodological, 1996, 30(5): 359-367. doi: 10.1016/0191-2615(96)00001-X
    [21] 任刚. 交通管制下的交通分配算法研究[D]. 南京: 东南大学,2003.
    [22] 卢顺达,程琳,邵娟. 转向延误和路段容量双约束下的用户均衡模型及算法研究[J]. 道路交通与安全,2017,17(6): 19-24.

    LU Shunda, CHENG Lin, SHAO Juan. Research on user equilibrium model and algorithm with turning delays and link capacity[J]. Journal of Transportation Engineering, 2017, 17(6): 19-24.
    [23] 李晓红. 城市干线交通信号协调优化控制及仿真[D]. 大连: 大连理工大学,2007.
  • 加载中
图(17) / 表(6)
计量
  • 文章访问数:  33
  • HTML全文浏览量:  11
  • PDF下载量:  4
  • 被引次数: 0
出版历程
  • 收稿日期:  2022-05-30
  • 修回日期:  2022-09-20
  • 网络出版日期:  2024-10-29

目录

    /

    返回文章
    返回