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

doi:10.13229/j.cnki.jdxbgxb.20240841

摘要/Abstract

摘要：

为解决经典路径规划算法的两个局限性，即较少考虑多交通方式组合换乘和缺少等待时间的建模方法，以厦门市交通网络为研究对象开展研究。构建了考虑等待时间的多层网络拓扑结构；基于FINLO的特性研究，提出了不同出行方式等待时间的时间依赖建模方法；最后，将等待时间依赖函数引入基于邻接字典的二叉堆Dijkstra算法，提出了一种考虑信号控制、车辆发车间隔的等待时间的多层网络路径规划算法。研究结果表明：本文方法能综合考虑多模式交通换乘、车辆班次和信号控制的等待时间依赖特性，弥补了现有时间依赖建模的不足，与不考虑等待时间依赖特性的路径规划算法相比，总行程时间缩短了8.4%。

关键词: 交通运输工程, 时变网络, 等待时间, 多模式交通, Dijkstra算法, 路径规划

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

中图分类号:

U412

于德新,王胪陈,吴新程,毛建宇,石世龙. 考虑等待时间的多层时变网络路径规划算法[J]. 吉林大学学报(工学版), 2026, 56(2): 443-454.

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.

图/表 15

图1

图2

图3

图4

图5

图6

图7

图8

图9

算法1

FINLO网络下时变最短路算法伪代码"

输入： $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$

算法1

算法2

允许节点等待的非FINLO网络时变最短路算法伪代码（片段）"

$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))$

算法2

图10

图11

表1

表2

参考文献 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.

相关文章 15

[1]	张伏,韩伟东,鲍若飞,张亚坤,王亚飞,付三玲. 融合改进A^*与DWA算法的车间移动机器人路径规划[J]. 吉林大学学报(工学版), 2025, 55(9): 3020-3031.
[2]	张文会,付博,周舸,乔晓田. 城市公共汽车全生命周期碳排放测算[J]. 吉林大学学报(工学版), 2025, 55(4): 1232-1240.
[3]	李振江,万利,周世睿,陶楚青,魏巍. 基于时空Transformer网络的隧道交通运行风险动态辨识方法[J]. 吉林大学学报(工学版), 2025, 55(4): 1336-1345.
[4]	孙帅帅,冯春晓,张良. 基于离散采样的多模态四足机器人路径规划[J]. 吉林大学学报(工学版), 2025, 55(11): 3736-3744.
[5]	李健,孙晓海,廖昌义,杨建平. 基于双起点蚁群算法的机器人路径规划方法[J]. 吉林大学学报(工学版), 2025, 55(1): 325-332.
[6]	朱瑾,黄琦. 路网资源分配下自动化码头水平运输调度与路径规划[J]. 吉林大学学报(工学版), 2024, 54(8): 2245-2255.
[7]	涂辉招,鹿畅,陆淼嘉,李浩. 基于避险脱离的自动驾驶路测安全影响因素[J]. 吉林大学学报(工学版), 2024, 54(7): 1935-1943.
[8]	胡钊政,孙勋培,张佳楠,黄戈,柳雨婷. 基于时空图模型的车-路-图协同定位方法[J]. 吉林大学学报(工学版), 2024, 54(5): 1246-1257.
[9]	孙宝凤,刘娇娇,姚天姿,任欣欣. 考虑能量消耗的纯电动物流车柔性时间窗路径规划问题[J]. 吉林大学学报(工学版), 2023, 53(4): 1047-1059.
[10]	吴振宇,刘小飞,王义普. 基于DKRRT^*-APF算法的无人系统轨迹规划[J]. 吉林大学学报(工学版), 2023, 53(3): 781-791.
[11]	张惠臻,高正凯,李建强,王晨曦,潘玉彪,王成,王靖. 基于循环神经网络的城市轨道交通短时客流预测[J]. 吉林大学学报(工学版), 2023, 53(2): 430-438.
[12]	孙宝凤,姚天姿,陈雨琦. 考虑时变交通拥堵的纯电动物流车路径规划模型[J]. 吉林大学学报(工学版), 2023, 53(2): 468-479.
[13]	李津,孙雨彤,魏小忠,焦玉玲. 考虑柔性车道设置的公交优先信号设计[J]. 吉林大学学报(工学版), 2023, 53(2): 448-456.
[14]	李文勇,马从若,胡清玮,刘承堃,廉冠,顾国斌,周旦. 基于站台容量限制和路段绿波控制的公交速度引导模型[J]. 吉林大学学报(工学版), 2023, 53(11): 3088-3103.
[15]	杨帆,翟志强,汪圆圆,朱忠祥,杜岳峰,毛恩荣. 基于虚拟现实的拖拉机变速箱装配系统设计[J]. 吉林大学学报(工学版), 2023, 53(10): 3038-3044.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed

类型		来源/设定
网络	道路网络	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