考虑等待时间的多层时变网络路径规划算法

doi:10.13229/j.cnki.jdxbgxb.20240841

Abstract

Abstract:

To address the limitations of classical path planning algorithms， which often overlook multi-modal transportation combinations and lack modeling of waiting times， a study was conducted on the transportation network in Xiamen City. The research involved constructing a multi-layer network topology that considers waiting times. Based on the characteristics of FINLO， a time-dependent modeling method for waiting times associated with different travel modes was proposed. Finally， the time-dependent waiting functions were incorporated into a multi-layer network path planning algorithm based on an adjacency dictionary and binary heap Dijkstra's algorithm. The results showed that this approach effectively considers waiting time dependencies related to multi-modal transit， vehicle schedules， and signal control. Compared to path planning algorithms that do not account for waiting time dependencies， the proposed method reduced total travel time by 8.4%.

Key words: engineering of communication and transportation system, time dependent network, waiting time, multi-model traffic, dijkstra algorithm, path planning

CLC Number:

U412

De-xin YU,Lu-chen WANG,Xin-cheng WU,Jian-yu MAO,Shi-long SHI. Multi-layer time dependent network path planning algorithm considering waiting time[J].Journal of Jilin University(Engineering and Technology Edition), 2026, 56(2): 443-454.

Figures/Tables 15

Fig.1

Fig.2

Fig.3

Fig.4

Fig.5

Fig.6

Fig.7

Fig.8

Fig.9

输入： $v s, v t, t s, G$
输出：在路网 $G$ 中， $t s$ 时刻从 $v s$ 出发到 $v t$ 的耗时最短路径和耗时
1	def FINLO-TDSP（ $v s, v t, t s, G$ ）：
2	$v o ← v s$
3	$t ← t s$
4	$O P E N ← O p e n ()$ #创建实例
5	$C L O S E ← C l o s e (v s)$ #创建实例
6	while $v o ≠ v t$ ：
7	for $k e y$ ， $f$ in $G [v o] . i t e m s ()$ ：
8	if $k e y$ not in $C L O S E . d i c t$ ：
9	$O P E N . a d d (k e y, ? (t ? + ? f (t), ? v o))$
10	if $O P E N . s i z e = 0$ ： #判断队列中元素数量
11	$t ← ∞$
12	break
13	$v o, t ← C L O S E . a d d (* O P E N . p o p ())$ #解包并传参，返回传递的参数
14	return $C L O S E . p a t h (v t)$ ， $t - t s$

$F ← l a m b d a ? x : x + f (x)$

$v a l u e ← m i n i m i z e_s c a l a r (F, b o u n d s = (t, F (t)), m e t h o d =' b o u n d s') . f u n$

#求解 $F$ 在区间内的最小函数值

$O P E N . a d d (k e y, (m i n (F (t), v a l u e, F (F (t))), v o))$

Fig.10

Fig.11

Table 1

Table 2

References 20

[1]	陈凤涛. 城市时变网络路径分析方法研究[D]. 南京:东南大学交通学院, 2018.
	Chen Feng-tao. Research on the method of routing analysis of urban in time-varying networks[D]. Nanjing: School of Transportation, Southeast University, 2018.
[2]	谭国真. 时变、随机网络最优路径算法及其应用研究[D].大连:大连理工大学信息与通信工程学院, 2002.
	Tan Guo-zhen. Studies on optimal path algorithms and its applications in time-varying and stochastic networks[D]. Dalian:School of Information and Communication Engineering, Dalian University of Technology, 2002.
[3]	王福. GIS中时变最短路径理论及算法研究[D]. 南京: 南京理工大学自动化学院, 2010.
	Wang Fu. Research on time varying shortest path theory and algorithm in GIS[D]. Nanjing: School of Automation, Nanjing University of Science and Technology, 2010.
[4]	张晓楠, 王陆宇, 谭昕妮, 等. 时变条件下道路网的车辆路径优化[J]. 机械科学与技术, 2023, 42(11): 1919-1928.
	Zhang Xiao-nan, Wang Lu-yu, Tan Xin-ni, et al. Time-dependent vehicle routing optimization problem under road network[J]. Mechanical Science and Technology for Aerospace Engineering, 2023, 42(11): 1919-1928.
[5]	Liu C, Kou G, Zhou X, et al. Time-dependent vehicle routing problem with time windows of city logistics with a congestion avoidance approach[J]. Knowledge-Based Systems, 2020, 188: 104813.
[6]	张煜璐. 考虑碳排放的时变路网多车型城市配送路径优化研究[D]. 杭州:浙江工商大学计算机与信息工程学院,2017.
	Zhang Yu-lu. The study of urban distrivution route optimization with heterogeneous fleet and time-varying networks for carbon emissions[D].Hangzhou:School of Computer and Information Engineering, Zhejiang Gongshang University,2017.
[7]	许祎娜, 王旭仁, 苏红莉. 时变公路网络的动态路径规划算法[J]. 小型微型计算机系统, 2018, 39(6): 1291-1298.
	Xu Yi-na, Wang Xu-ren, Su Hong-li. Dynamic path planning algorithm in time-dependent road networks[J]. Journal of Chinese Computer Systems, 2018, 39(6): 1291-1298.
[8]	Cheng P, Xu C, Lebreton P, et al. TERP: time-event-dependent route planning in stochastic multimodal transportation networks with bike sharing system[J]. IEEE Internet of Things Journal,2019, 6(3): 4991-5000.
[9]	何俊, 戴浩, 宋自林, 等. 时间依赖的交通网络模型及最短路径算法[J]. 解放军理工大学学报: 自然科学版, 2005(6): 541-544.
	He Jun, Dai Hao, Song Zi-lin, et al. Time-dependent traffic networks model and shortest path algorithm[J]. Journal of PLA University of Science and Technology, 2005(6): 541-544.
[10]	魏航. 时变条件下允许等待的最短路问题[J]. 系统管理学报, 2008, 2008(1): 99-103.
	Wei Hang. An approach for time-varying shortest path problem with waiting[J]. Journal of Systems ＆ Management, 2008, 2008(1): 99-103.
[11]	Foschini L, Hershberger J, Suri S. On the complexity of time-dependent shortest paths[C]∥Proceedings of the Twenty-second Annual ACM-SIAM Symposium on Discrete Algorithms, New Orleans, USA, 2011: 327-341.
[12]	Huang H, Bucher D, Kissling J, et al. Multimodal route planning with public transport and carpooling[J]. IEEE Transactions on Intelligent Transportation Systems, 2018, 20(9): 3513-3525.
[13]	赵凯旋. MaaS背景下网约车接驳轨道交通的路径优化研究[D]. 武汉: 华中科技大学土木工程与力学学院, 2019.
	Zhao Kai-xuan. Study on path optimazition of online car-hailing transfering to rail transit under MaaS background[D]. Wuhan: School of Civil Engineering and Mechanics, Huazhong University of Science and Technology, 2019.
[14]	Zhang Y, Ye M, Deng L, et al. Path optimization of green multimodal transportation considering dynamic random transit time[J]. International Journal of Applied Mathematics, 2024, 54(4): 623-633.
[15]	刘松. 面向随机时变网络的带班期限制的多式联运路径优化研究[D]. 重庆: 重庆交通大学交通运输学院, 2019.
	Liu Song. Research on route optimization of multi-modal transport with timetable limit for stochastic time-dependent networks[D]. Chongqing: School of Transportation, Chongqing Jiaotong University,2019.
[16]	Li L, Zhang Q, Zhang T, et al. Optimum route and transport mode selection of multimodal transport with time window under uncertain conditions[J]. Mathematics, 2023, 11(14): 11143244.
[17]	Kaufman D E, Smith R L. Fastest paths in time-dependent networks for intelligent vehicle-highway systems application[J]. Journal of Intelligent Transportation Systems, 1993, 1(1): 1-11.
[18]	杜牧青, 鞠姿彦, 李大韦. 一种基于交叉口信号延误的超路径规划方法[J]. 西南交通大学学报, 2024, 59(6): 1378-1388.
	Du Mu-qing, Ju Zi-yan, Li Da-wei. Hyperpath searching algorithm method based on signal delay at intersections[J]. Journal of Southwest JiaoTong University, 2024, 59(6): 1378-1388.
[19]	蒋睿. 考虑节点耗费的时变随机网络最短路径问题研究[D]. 天津: 天津理工大学计算机与通信工程学院, 2016.
	Jiang Rui. Least travel time paths in stochastic and time-varying transportation networks considering the time consumption of nodes[D]. Tianjin:School of Computer and Communication Engineering, Tianjin University of Technology, 2016.
[20]	Sun Y, Li J, Liu S X. Study on the shortest reliable path of stochastic time‐dependent transportation networks considering waiting time at signalized intersections[J]. Journal of Advanced Transportation, 2023, 2023(1): 8298068.

Related Articles 15

[1]	Wen-hui ZHANG,Mei-ru YE,Cong XI,Zi-wen SONG. Vehicle formation and carbon emission characteristics in mixed traffic flow environment [J]. Journal of Jilin University(Engineering and Technology Edition), 2026, 56(2): 416-430.
[2]	Yu-sheng CI,Yi-kang HUANG. Overview of intersection vehicle-infrastructure integration based on bibliometrics [J]. Journal of Jilin University(Engineering and Technology Edition), 2026, 56(2): 313-332.
[3]	Zhao-wei QU,Ming-yang WANG,Zhe WANG,Xian-min SONG,Yun-xiang ZHANG,Jing-cheng HUANG. Adaptive scheduling method for bus based on autonomous modular vehicles main⁃auxiliary function allocation [J]. Journal of Jilin University(Engineering and Technology Edition), 2025, 55(9): 2946-2957.
[4]	Fu ZHANG,Wei-dong HAN,Ruo-fei BAO,Ya-kun ZHANG,Ya-fei WANG,San-ling FU. Path planning of workshop mobile robots integrated with improved A^* and DWA algorithms [J]. Journal of Jilin University(Engineering and Technology Edition), 2025, 55(9): 3020-3031.
[5]	Chang-ru MU,Liang XU,Guo-zhu CHENG. Collision prevention performance of outsourced U-shaped steel concrete composite guardrail based on reasonable energy allocation [J]. Journal of Jilin University(Engineering and Technology Edition), 2025, 55(8): 2669-2680.
[6]	Yan-bo LI,Jing-yuan WANG,Yuan-yuan Chen,Shao-feng CHENG,Hao-nan LYU,Jun-shuo CHEN. RAMS assessment approach of self-consistent energy system in highway service areas [J]. Journal of Jilin University(Engineering and Technology Edition), 2025, 55(7): 2243-2250.
[7]	Xiao-feng JI,Ruo-fan DENG,Xin QIAO,Hao-tian GUAN. Nonlinear influence of built environment on temporal aggregation modes of shared bicycles [J]. Journal of Jilin University(Engineering and Technology Edition), 2025, 55(7): 2233-2242.
[8]	Yuan-wen LAI,Yan-sheng CHEN,Shu-yi WANG,Yu-long ZHANG,Xin-yun ZHU. Bus schedule optimization considering bus and metro interchange needs [J]. Journal of Jilin University(Engineering and Technology Edition), 2025, 55(6): 2030-2037.
[9]	Sheng-yu YAN,Ming-jie CHENG,Hong-ce TIAN,Hong-yu WANG,Yong-heng ZHOU,Bo-hao MA. Scheduling algorithm for battery electric vehicle in closed scenic area [J]. Journal of Jilin University(Engineering and Technology Edition), 2025, 55(6): 1984-1993.
[10]	Yan-yan QIN,Teng-fei XIAO,Qin-zhong LUO,Bao-jie WANG. Car-following safety analysis and control strategy for foggy freeway [J]. Journal of Jilin University(Engineering and Technology Edition), 2025, 55(4): 1241-1249.
[11]	Yi-yong PAN,Xiang-yu XU. Model for predicting severity of accidents based on MobileViT network considering imbalanced data [J]. Journal of Jilin University(Engineering and Technology Edition), 2025, 55(3): 947-953.
[12]	Yong-zheng YANG,Zhi-gang DU,Jia-lin MEI. Setting method and effect evaluation of linear guiding system in highway tunnels [J]. Journal of Jilin University(Engineering and Technology Edition), 2025, 55(12): 3885-3897.
[13]	Guang-yong CHEN,Shi-rui ZHOU,Chu-qing TAO,Li WAN,Wei WEI. Collaborative control of tunnel speed and lighting based on driver’s visual characteristics [J]. Journal of Jilin University(Engineering and Technology Edition), 2025, 55(12): 3898-3906.
[14]	Shuai-shuai SUN,Chun-xiao FENG,Liang ZHANG. Path planning for multimodal quadruped robots based on discrete sampling [J]. Journal of Jilin University(Engineering and Technology Edition), 2025, 55(11): 3736-3744.
[15]	Jian LI,Xiao-hai SUN,Chang-yi LIAO,Jian-ping YANG. Robot path planning method based on double-origin ant colony algorithm [J]. Journal of Jilin University(Engineering and Technology Edition), 2025, 55(1): 325-332.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed

Comments

Recommended 0

No Suggested Reading articles found!

类型		来源/设定
网络	道路网络	OSM
	轨道网络	高德地图API/OSM
	公交网络	8684公交查询+高德地图API+地图匹配
网络衔接	道路-轨道	经近邻节点搜索后连接
网络衔接	道路-公交	经地图匹配后同一站点连接
信号控制	位置	经3.1节交叉口节点合并后出度、入度同时为3或4的节点
	类型	单口放
	绿灯时间	36 s/单个相位
平均速度	步行/换乘	4 km/h
	轨道	60 km/h
	公交	25 km/h
发车	轨道	6：00~22：00，6 min/趟
发车	公交	6：30~21：12，18 min/趟

算法	OPEN表数据结构	权重	时变网络	考虑信号控制	路径耗时/h	路径长度/km	计算时间/s
算法1	二叉堆	时间依赖函数（4.4节）	是	是	2.62	44.58	1.07
算法2		时间依赖函数（4.4节）	是	否	3.08	48.60	0.46
算法3		时间依赖函数（4.5节）	是	是	2.62	44.58	12.02
算法4		时间依赖函数（4.5节）	是	否	3.08	48.60	9.37
算法5		出发时刻路段行程时间	否	是	2.86	43.49	0.50
算法6		出发时刻路段行程时间	否	否	2.96	43.45	0.29
算法7		路段实际长度	否	是	10.04	41.45	0.37
算法8		路段实际长度	否	否	10.04	41.45	0.22

Multi-layer time dependent network path planning algorithm considering waiting time

RICH HTML

PDF (PC)