Determining Effective Paths Set Based on Reverse Depth-First Search Algorithm

doi:10.3969/j.issn.1674-0696.2015.03.20

Abstract

Abstract: Based on the definition of alternative path, the range of effective path impedance values was identified. Adopting the depth-first algorithm and the idea of getting closer to the end from the effective path Dail algorithm, an effective paths search algorithm which starts from the end node to the front node was proposed. Numerical results show that, the effective path search algorithm not only identifies the impedance values range associated with the network structure automatically, but also finds the effective path sets quickly.

Key words: traffic engineering, graph theory, effective path, depth-first search algorithm, Floyd algorithm

摘要： 基于最短路径中任意路段因发生交通事件而失效时的替代路径搜索，合理界定了有效路径的阻抗值范围。参考深度优先算法和有效路径Dail算法离终点越来越近的思想，提出了一种从终点出发，反向搜索前置节点的多条有效路径搜索算法。算例结果表明：该算法能自动识别与路网结构相关的有效路径阻抗值范围，且能快速找到阻抗范围内的有效路径集合。

关键词: 交通工程, 图论, 有效路径, 深度优先算法, Floyd算法

CLC Number:

U491.1+3

Zhang Jianxu, Jiang Yan, Liu Xingguo. Determining Effective Paths Set Based on Reverse Depth-First Search Algorithm[J]. Journal of Chongqing Jiaotong University(Natural Science), 2015, 34(3): 93-98.

张建旭,蒋燕, 刘兴国. 基于深度优先反向搜索算法确定有效路径集合[J]. 重庆交通大学学报（自然科学版）, 2015, 34(3): 93-98.

References

[1] Soo-young J,Chae Y L.Multipath selection and channel assignment in wirelessmesh networks[J].Wireless Netw,2011,17(4):1001-1014.
[2] 王英杰,程琳,王炜.基于有效路径集合的节点间连通度估计方法研究[J].武汉理工大学学报:交通工程与科学版,2009,33(5):960-963.
Wang Yingjie,Cheng Lin,Wang Wei.Researches on estimations of connectivity reliability of an OD pair based on the effective path sets[J].Journal of Wuhan University of Technology:Transportation Science & Engineering,2009,33(5):960-963.
[3] 杨信丰,刘兰芬.基于影响度的有效路径集合的确定[J].交通运输系统工程与信息,2011,11(6):104-110.
Yang Xinfeng,Liu Lanfen.Determining the efficient paths based on effect degree[J].Journal of Transportation Systems Engineering and Information Technology,2011,11(6):104-110.
[4] Lokshtanov D,Mnich M,Saurabh S.Planar k-path in subexponential time and polynomial space[C]//Proceedings of the 37th International Workshop on Graph-Theoretic Concepts in Computer Science.Teplá-Kláter:Czech Republic,2011:262-270.
[5] 何胜学,范炳全.随机交通分配中有效路径的定向树搜索算法[J].交通与计算机,2005(5):38-41.
He Shengxue,Fan Bingquan.Orientated tree algorithm of searching efficient paths in stochastic traffic assignment[J].Computer and Communications,2005(5):38-41.
[6] Leurent F.Curbing the computational difficulty of logit equilibrium assignment model[J].Transportation Research B:Methodological,1997,31(4):315-326.
[7] 李景,彭国雄,臧亦文.改进型多路径分配模型及算法设计[J].系统工程理论与实践,2001(9):130-134.
Li Jing,Peng Guoxiong,Zang Yiwen.An improved multi-path assignment model and algorithms design [J].Systems Engineering-Theory & Practice,2001(9):130-134.
[8] 李洪波,王茂波.Floyd最短路径算法的动态优化[J].计算机工程与应用,2006(34):60-63.
Li Hongbo,Wang Maobo.Dynamic optimum of shortest path’s algorithm devised by Floyd[J].Computer Engineering and Applications,2006(34):60-63.
[9] 严晓凤,陆济湘,唐双平.基于Floyd算法的校园最短路径问题分析与实现[J].武汉理工大学学报:信息与管理工程版,2012,34(6):695-703.
Yan Xiaofeng,Lu Jixiang,Tang Shuangping.Analysis and implementation of campus shortest path based on Floyd algorithm[J].Journal of Wuhan University of Technology:Information & Management Engineering ,2012,34(6):695-703.
[10]黄远春,胥耀方,潘海泽.城际公共交通系统最短路算法[J].重庆交通大学学报:自然科学版,2010,29(2):265-268.
Huang Yuanchun,Xu Yaofang,Pan Haize.Algorithm for shortest path of intercity public transportation system[J].Journal of Chongqing Jiaotong University:Natural Science,2010,29(2):265-268.
[11]黄美灵, 陆百川.考虑交叉口延误的城市道路最短路径[J].重庆交通大学学报:自然科学版,2009,28(6):1060-1063.
Huang Meiling,Lu Baichuan.Determination of the shortest path considering delays at intersections[J].Journal of Chongqing Jiaotong University:Natural Science,2009,28(6):1060-1063.
[12]赖树坤,姚宪辉,彭愚.交通网络中有效路径确定方法的探讨[J].交通标准化,2008(1):137-139.
Lai Shukun,Yao Xianhui,Peng Yu.Determination of efficient path in traffic network[J].Communications Standardization,2008(1):137-139.
[13]Evangelista S,Laarman A,Petrucci L,et al.Improved multi-core nested depth-first search[C]∥Automated Technology for Verification and Analysis,Thiruvananthapuram.India:Springer Berlin Heidelberg,2012:269-283.
[14]Kozen D C.Depth-first and breadth-first search[M]//The Design and Analysis of Algorithms.New York:Springer Berlin Heidelberg,1992:19-24.

[1]	TANG Jiqiang1,2, ZHONG Xinwei2, LIU Jian1, LI Tianrui3. Short Term Forecast of Rail Transit Passenger Flow Based on Time Series Seasonal Classification Model [J]. Journal of Chongqing Jiaotong University(Natural Science), 2021, 40(07): 31-38.
[2]	QI Chunhua, WANG Xiaonan, ZHU Shoulin, LI Hangtian. Traffic Engineering Facility Information Threshold Based on Drivers Visual Area of Interest [J]. Journal of Chongqing Jiaotong University(Natural Science), 2021, 40(07): 53-60.
[3]	DENG Tianmin1, ZHU Jie2, ZHU Kaijia1, QU Zhihua3. Driving Style Recognition Method Based on iForest and Bisecting K-means Combined Algorithm [J]. Journal of Chongqing Jiaotong University(Natural Science), 2021, 40(06): 1-6.
[4]	XU Maozeng, ZHANG Li. Identification of Road Section Congestion Influence Based on Bijective Soft Decision Theory [J]. Journal of Chongqing Jiaotong University(Natural Science), 2021, 40(06): 7-11.
[5]	WANG Tao1, XIE Sihong1, LI Wenhao1,2, LI Wenyong1. Short-Term Traffic Flow Adaptive Prediction Model Based on FFOS-ELM and PF [J]. Journal of Chongqing Jiaotong University(Natural Science), 2021, 40(06): 21-27.
[6]	ZHANG Cheng1, WANG Chengyin1, CHEN Zhiwei2, ZHANG Zhengxiang3, ZHANG Zilei3. Mining Method of Key Nodes of Urban Road Network Based on Spatial-Flow Degree [J]. Journal of Chongqing Jiaotong University(Natural Science), 2021, 40(06): 28-35.
[7]	WANG Yonggang, ZHANG Heng, PENG Zhipeng, ZHOU Wanqi. Analysis of Influencing Factors of Taxi Accidents Based on Structural Equation Model [J]. Journal of Chongqing Jiaotong University(Natural Science), 2021, 40(06): 36-42.
[8]	ZHU Shunyin, LI Weiji, LIN Xiaoyuan, XIAO Wenbin, WANG Hong. Setting No Re-inspection Control Point for Tourist Vehicles in Characteristic Towns [J]. Journal of Chongqing Jiaotong University(Natural Science), 2021, 40(06): 52-58.
[9]	PAN Binghong1,2, HU Wei1, REN Hui1, SHAN Huimin1. Truck Side-Slip Velocity Model in Curve Road Section Based on TruckSim Simulation [J]. Journal of Chongqing Jiaotong University(Natural Science), 2021, 40(05): 38-45.
[10]	WU Wenjing, SUN Renchao, ZONG Fang, JIA Hongfei. Subjective Attitude Identification and Impact Analysis of Residents Low-Carbon Commuting Travel [J]. Journal of Chongqing Jiaotong University(Natural Science), 2021, 40(05): 53-58.
[11]	LI Jun, DENG Yuxin. Cluster Analysis of Taxi Spatiotemporal Behavior Based on Non-negative Matrix Factorization [J]. Journal of Chongqing Jiaotong University(Natural Science), 2021, 40(05): 59-65.
[12]	CHENG Wei1, LIU Xiang1, LEI Jianming2. Optimization of Cycle Length of Intersection Signal Based on RBF Neural Network Prediction [J]. Journal of Chongqing Jiaotong University(Natural Science), 2021, 40(04): 13-18.
[13]	SHI Tianliang, WANG Wenguang. Information View and Particle Swarm Optimization Algorithm in Urban Traffic Congestion [J]. Journal of Chongqing Jiaotong University(Natural Science), 2021, 40(04): 19-25.
[14]	HE Yulong1, 2, LIU Lei1,2, CHI Jiaxin1,2. Risk of Vehicle Lane Change Behavior on Highway [J]. Journal of Chongqing Jiaotong University(Natural Science), 2021, 40(04): 26-33.
[15]	WANG Lu1, CHEN Xiaoxin2, LI Huaen1. Critical Speed of Vehicles Running Stably on Expressway in the Weather of Rain and Snow under Strong Wind [J]. Journal of Chongqing Jiaotong University(Natural Science), 2021, 40(04): 34-40.