Hyperpath Searching Algorithm Method Based on Signal Delay at Intersections

DU Muqing; JU Ziyan; LI Dawei

doi:10.3969/j.issn.0258-2724.20220387

Volume 59 Issue 6

Dec. 2024

Turn off MathJax

Article Contents

Abstract

References

Journal of Southwest Jiaotong University > 2024 > 59(6): 1378-1388.

XU Kai, LI Fu, AN Qi, MAO Wenhui. Wheel Tread Wear Characteristics of High-Speed Electric Multi-Units[J]. Journal of Southwest Jiaotong University, 2021, 56(1): 92-100. doi: 10.3969/j.issn.0258-2724.20190266

Citation:

DU Muqing, JU Ziyan, LI Dawei. Hyperpath Searching Algorithm Method Based on Signal Delay at Intersections[J]. Journal of Southwest Jiaotong University, 2024, 59(6): 1378-1388. doi: 10.3969/j.issn.0258-2724.20220387

Citation:

PDF( 2217 KB)

Hyperpath Searching Algorithm Method Based on Signal Delay at Intersections

doi: 10.3969/j.issn.0258-2724.20220387

1.
College of Civil and Transportation Engineering, Hohai University, Nanjing 210098, China
2.
School of Transportation, Southeast University, Nanjing 210018, China

Received Date: 30 May 2022
Rev Recd Date: 20 Sep 2022

Available Online: 29 Oct 2024

Publish Date: 22 Sep 2022

Abstract

Abstract

The periodic change of intersection signals in urban road systems leads to the uncertain delay of vehicle travel. In order to reduce the delays of vehicles at signal-controlled intersections, an improved hyperpath searching algorithm was proposed with the minimization of travel time on the road segments and the expected delay at the intersections as the optimization goal. First, according to the probability distribution function of vehicles arriving at the intersection, the expected waiting time and the turning movement proportion were derived. Then, the high-performance hyperpath searching algorithm was developed with the introduction of the label setting algorithm. Finally, the improved hyperpath searching algorithm was applied to the road network at Xinjiekou area, Nanjing, and the optimal hyperpath set was used to evaluate the applicability of the algorithm. The results show that compared with the shortest path strategy, hyperpath searching algorithm reduces the intersection delay and the total travel time by 67.1% and 22.3%, respectively as drivers shift to a driving route in the optimal hyperpath set. Furthermore, the hyperpath-based strategy can optimize the trip distribution in the road network, alleviating traffic congestion and contributing to flow equilibrium.
- intersection signal timing,
- probability distribution function,
- turning delay,
- extended forward star structure,
- label setting algorithm

FullText(HTML)

References(23)

References

[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.

Relative Articles

[1]	ZHANG Weilie, YAN Qixiang, ZHANG Chuan, YANG Kai, JIA Ding. Cracking Behavior of Segmental Lining in Subways Under Adverse Jacking Force During Shield Tunneling[J]. Journal of Southwest Jiaotong University, 2023, 58(5): 1073-1082. doi: 10.3969/j.issn.0258-2724.20220235
[2]	ZHONG Xiaochun, HUANG Siyuan, ZHU Weibin, CHEN Qiaosong, YOU Zhi. Analysis of Sealing Performance of Shield Tail Brush Based on Compression and Grease Escape Test[J]. Journal of Southwest Jiaotong University, 2023, 58(1): 125-132. doi: 10.3969/j.issn.0258-2724.20210814
[3]	YANG Cheng, LIAO Weilong, SONG Tongwei, GENG Ping, FANG Yong. Bond-Slip of Connecting Bolts Between Tunnel Segments and Metro Station Portal Ring Beam[J]. Journal of Southwest Jiaotong University, 2022, 57(4): 876-885. doi: 10.3969/j.issn.0258-2724.20200703
[4]	LI Bingtian, QIU Wenge, QI Xingxin, DENG Zhiheng, HU Hui. Shaking Table Tests on Seismic Response of Tunnel with Longitudinal Cracking Lining[J]. Journal of Southwest Jiaotong University, 2021, 56(1): 20-27, 55. doi: 10.3969/j.issn.0258-2724.20190657
[5]	SHEN Xiang, YUAN Dajun, CAO Yutao, GAO Zhenfeng. Experiments on Material Proportions for Simulating Sandy Layer in Deep Sea[J]. Journal of Southwest Jiaotong University, 2020, 55(3): 628-634. doi: 10.3969/j.issn.0258-2724.20180285
[6]	GENG Ping, WANG Qi, GUO Xiangyu, HE Chuan, LU Shujun, XIAO Mingqing. Force Characteristics of Longitudinal Joints of Shield Tunnel under Seismic Action[J]. Journal of Southwest Jiaotong University, 2020, 55(4): 704-712. doi: 10.3969/j.issn.0258-2724.20180634
[7]	GENG Ping, YANG Qi, HE Yue, HE Chuan, GUO Xiangyu. Shaking Table Test and Numerical Simulation of Shield Tunnel Connecting Cross Passage[J]. Journal of Southwest Jiaotong University, 2020, 55(6): 1215-1223. doi: 10.3969/j.issn.0258-2724.20180982
[8]	WANG Mingnian, HUANG Haibin, TANG Yuan, WANG Chuang, LIU Dagang. Influence of Shield Construction on Pressure Fluctuation of Segment Grout[J]. Journal of Southwest Jiaotong University, 2019, 54(3): 461-467, 586. doi: 10.3969/j.issn.0258-2724.20170199
[9]	YAN Qixiang, LI Binjia, CHEN Hang, ZHANG Weilie, DENG Zhixin. Failure and Parametric Analysis of Shield Tunnel Bolts under Impact Load[J]. Journal of Southwest Jiaotong University, 2019, 54(1): 23-31, 38. doi: 10.3969/j.issn.0258-2724.20160637
[10]	WANG Jun, LIN Guojin, TANG Xie, HE Chuan. Face Stability Analysis of Shield Tunnel in Sandy Ground Using 3D DEM[J]. Journal of Southwest Jiaotong University, 2018, 53(2): 312-321. doi: 10.3969/j.issn.0258-2724.2018.02.013
[11]	LU Daiyue, XU Guowen, WANG Shimin. Effects of Material Damage and Structural Characteristics on Tunnel Shield During Loading and Unloading[J]. Journal of Southwest Jiaotong University, 2017, 30(6): 1104-1112. doi: 10.3969/j.issn.0258-2724.2017.06.010
[12]	ZHENG Yuchao, SHI Bowen, SUN Keguo, YANG Tianchun, LI Hui. Impact of Partition Method in Pit Construction Adjacent to Existing Metro Shield Tunnel[J]. Journal of Southwest Jiaotong University, 2017, 30(5): 910-918. doi: 10.3969/j.issn.0258-2724.2017.05.010
[13]	LU Daiyue, HE Chuan, WANG Shimin. Crack Propagation Law of Segment Tendon under Jacking Forces[J]. Journal of Southwest Jiaotong University, 2017, 30(1): 75-82. doi: 10.3969/j.issn.0258-2724.2017.01.011
[14]	FANG Yong, HE Chuan, QI Chun, ZHANG Ming. Structural Internal Force of Shield Tunnel in Expansive Soil Underlying Sandy Pebble Layer[J]. Journal of Southwest Jiaotong University, 2014, 27(3): 386-392. doi: 10.3969/j.issn.0258-2724.2014.03.003
[15]	YE Fei, LIU Yanpeng, GOU Changfei, ZHANG Jinlong, ZHOU Zhuo. Capillary Penetration Diffusion Model for Backfill Grouting of Shield Tunnel[J]. Journal of Southwest Jiaotong University, 2013, 26(3): 428-434. doi: 10.3969/j.issn.0258-2724.2013.03.006
[16]	WEI Kai, ZHAI Wanming, XIAO Junhua. Influence of Track Regularity and Soil Dynamic Characteristics on Vibration of Subway Tunnel[J]. Journal of Southwest Jiaotong University, 2013, 26(6): 989-995. doi: 10.3969/j.issn.0258-2724.2013.06.004
[17]	YUAN Xiao-Hui, HAN Ru-Wang, ZHONG Xiao-Chun. Pressure Distribution Model of Simultaneous Backfill Grouting of Shield Tunnel[J]. Journal of Southwest Jiaotong University, 2011, 24(1): 18-23. doi: 10.3969/j.issn.0258-2724.2011.01.003
[18]	GENG Ping, HE Chuan, YAN Qixiang. Analysis of Longitudinal Seismic Response of Shield Tunnel[J]. Journal of Southwest Jiaotong University, 2007, 20(3): 283-287.
[19]	LIWei, HE Chuan, ZHANG Zhi-qiang. M odelTest ofConstructing Shield Tunnel under Large Underground Structure[J]. Journal of Southwest Jiaotong University, 2005, 18(4): 478-483.
[20]	ZENG Dong-yang, HE Chuan. Numerical Simulation of Segment Joint Bending Stiffness of Metro Shield Tunnel[J]. Journal of Southwest Jiaotong University, 2004, 17(6): 744-748.

Supplements(0)

Cited By

Cited by

Periodical cited type(4)

1.	龚书锦，陈志忠. 降低站内无轨道电路区段不平衡牵引电流干扰问题探讨. 铁路通信信号工程技术. 2023(S1): 18-22 .
2.	唐伟，史籍. 牵引回流对ZPW-2000A轨道电路的影响及解决措施. 铁路通信信号工程技术. 2022(S1): 122-126 .
3.	董昱，魏万鹏. 基于RBF神经网络PID控制的列车ATO系统优化. 电子测量与仪器学报. 2021(01): 103-109 .
4.	田粉霞，杨世武，崔勇，武沛. 基于改进卷积神经网络的无绝缘轨道电路调谐区故障诊断. 铁路计算机应用. 2020(06): 58-63+74 .

Other cited types(7)

Proportional views

Proportional views

通讯作者: 陈斌, bchen63@163.com

1.
沈阳化工大学材料科学与工程学院沈阳 110142

Figures(17) / Tables(6)

Get Citation

PDF

XML

Article views(279) PDF downloads(31)