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

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

摘要

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

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

Graphical abstract

关键词

交通运输工程 / 时变网络 / 等待时间 / 多模式交通 / Dijkstra算法 / 路径规划

Key words

engineering of communication and transportation system / time dependent network / waiting time / multi-model traffic / dijkstra algorithm / path planning

0 引 言

伴随着交通网络的发展，以多方式换乘的多模式交通出行方式逐渐流行。这给传统路径搜索算法带来了新的挑战，即如何在车辆班次、信号控制等具有间断性质的不同等待时间的多层交通网络中动态寻找时间最短路径。

传统的交通网络通常假设网络中的出行时间等成本保持不变，但考虑到时间的动态性，并不能简单地将时间费用归为某条弧段的固定属性。已有学者对该问题（路段行程时间随时刻发生变化的网络）展开研究，通常表述为“时间依赖网络”或“时变网络”（Time dependent network，TDN）^［1］。时变网络的理论分析早期已有学者进行了研究^［2］，主要用于单一网络，并区分出先进先出（First in first out，FIFO）和非FIFO网络，其中非FIFO网络又被进一步细化为允许节点等待、禁止等待和源等待模型^［3］。在时变网络框架下，交通领域大致衍生出两方面研究，一个是时变网络下的旅行商问题（Traveling salesman problem，TSP）^［4］或车辆路径问题（Vehicle routing problem，VRP）^［5，6］，另一个是时变网络下的最短路径（Time dependent shortest path，TDSP）问题^{［1，7，8］}。前者多采用蚁群算法或遗传算法，后者主要围绕Dijkstra或A*等启发式算法。是否满足FIFO特性会显著影响TDSP算法，FIFO^［9］或允许节点等待的非FIFO网络^［10］使用经典最短路算法的理论可行性已经被证明，而禁止等待的非FIFO网络则被认为是无法使用Dijkstra等经典最短路算法的NP-hard问题^［11］。

有关多层交通网络的研究中，通常考虑多模式交通^［12］和最小化综合成本^{［13，14］}。目前将等待时间建模与网络拓扑结构相结合的研究较少，文献［14］考虑了时间成本但没有考虑等待时间；研究［13］考虑了等待时间的时变性，但没有给出时变等待网络的拓扑结构；文献［12］考虑了时变网络的拓扑结构但并未包含等待时间。另外，尽管多式联运本身考虑多种运输方式，但也有部分此类研究会考虑多交通方式的TDN建模^{［15，16］}，其网络建模较为简单。

对于TDSP研究下的时变道路网络方面，通常包含时变路段和时变交叉口建模。尽管有学者认为在一些特定情况下，TDN不满足FIFO特性^［17］，但目前通常将TDN视为满足FIFO特性^［1］的网络。对于时变路段，现有主流思路通常采用分时段平均车速表示路网时变特性，并通过积分解出路段行程时间^{［1，3，5，15］}，以此作为避免产生非FIFO特性的手段。然而，上述建模方法需要利用分段平均速度和路段长度求解行程时间，不能对等待时间直接进行建模。对时变交叉口的研究则主要采用交叉口期望延迟^{［1，18，19］}。但如果采用干线控制，车辆以绿波通行，则不能按照交叉口期望延误计算，可以看出，信号控制也需要考虑等待时间的建模^［20］。

鉴于等待是交通间断流的核心且广泛存在于交通网络中，需要考虑如何进行等待时间建模。本文开展的研究可以概括为以下4个方面：

（1）针对目前的研究没有很好地将多层网络和等待时间建模相结合的问题，从多层网络的拓扑结构出发，结合等待时间表达方法，构建动态的多层交通网络，将研究范围从单一网络扩大至多层网络。

（2）针对等待难以被现有的时间依赖方法建模的问题，在FIFO的基础上明确了先进不后出（First in not last out，FINLO），为等待时间依赖函数提供理论依据。

（3）针对现行研究不能表达信号控制、班次等待的等待时间，在等待时间依赖函数的基础上，实现信号控制和班次等待的等待时间依赖建模方法。

（4）将考虑等待时间的时间依赖函数引入基于二叉堆优化的Dijkstra算法中，提出考虑等待时间的多层时变网络路径规划算法。

结果表明：本文提出的等待时间依赖函数和考虑等待时间的多层时变网络路径规划算法，能有效对现实世界的等待现象（信号控制、车辆班次等待等）进行建模，弥补现有时间依赖建模的不足，找到多层时变网络下考虑等待时间的最短时间路径。

1 问题描述

在多层交通网络中，传统路径规划方法面临以下问题：①网络动态特性建模不足，特别是对等待时间的动态变化及其与网络拓扑关系的联合表达较为匮乏；②多层网络的复杂性在时变网络中未被充分考虑，难以满足多模式出行的需求；③传统方法通常基于FIFO假设，无法有效处理常见的信号控制、班次衔接等节点等待行为；④对信号控制和班次等待的建模多采用均值或期望值，难以反映实际动态特性。上述问题限制了路径规划算法在复杂多层交通网络中的应用，需要针对等待时间和动态特性提出新的建模与求解方法。

因此，针对这一背景，本文聚焦于如何在考虑等待时间动态特性的基础上建模多层交通网络，并提出路径规划方法。具体而言，已知任意路段行程时间和交通工具首站各发车班次，如何在考虑纳入等待时间的基础上，建模该网络（假定该网络为FINLO网络或允许节点等待的非FINLO网络），并求解任意时刻从某一点到另外一点的行程时间最短的路径及所花费的行程时间。

2 多层交通网络模型假设

2.1　静态网络

网络的动态性质在网络的拓扑结构上构成。拓扑结构如下：

G=\{G^{\mathrm{w}},G^{\mathrm{b}},G^{\mathrm{r}},G^{\mathrm{t}},G_{\mathrm{w}\mathrm{a}\mathrm{i}\mathrm{t}}^{\mathrm{w},\mathrm{b},\mathrm{b}\leftarrow \mathrm{w},\mathrm{r}}\}（1）

G^{\mathrm{w}}=(V^{\mathrm{w}},E^{\mathrm{w}},W^{\mathrm{w}})（2）

G^{\mathrm{b}}=(V^{\mathrm{b}},E^{\mathrm{b}},W^{\mathrm{b}})（3）

G^{\mathrm{r}}=(V^{\mathrm{r}},E^{\mathrm{r}},W^{\mathrm{r}})（4）

G^t=(E^{\mathrm{t}},W^{\mathrm{t}})（5）

G_{\mathrm{w}\mathrm{a}\mathrm{i}\mathrm{t}}^{\mathrm{w},\mathrm{b},\mathrm{b}\leftarrow \mathrm{w},\mathrm{r}}=(E_{\mathrm{w}\mathrm{a}\mathrm{i}\mathrm{t}}^{\mathrm{w},\mathrm{b},\mathrm{b}\leftarrow \mathrm{w},\mathrm{r}},W_{\mathrm{w}\mathrm{a}\mathrm{i}\mathrm{t}}^{\mathrm{w},\mathrm{b},\mathrm{b}\leftarrow \mathrm{w},\mathrm{r}})（6）

式（1）表示网络集，均为有向图，由下述构成：

道路层（式（2））：不包含小汽车（小汽车的路段行程时间通常最短，会导致最短时间路径永远位于道路层），因此，本文在道路层中假设出行者为步行状态。

公交层（式（3））：由具有多条公交线路的拓扑结构构成，依附于道路层，因此，G^{\mathrm{b}}的边和节点的线形结构来源于G^{\mathrm{w}}及G_{\mathrm{w}\mathrm{a}\mathrm{i}\mathrm{t}}^{\mathrm{w}}。不同公交线路的共线段依然具有独立拓扑结构防止路径规划过程中串线。

轨道层（式（4））：由具有多条轨道线的拓扑结构构成。每条线路同样具有独立拓扑结构。

换乘层（式（5））：用于不同网络间过渡或换乘的网络，和道路层类似，用于连接两个不同网络或同一网络的不同路线，换乘层均假设出行者为步行状态。需要注意的是，由于G^{\mathrm{b}}依附于G^{\mathrm{w}}，G^{\mathrm{b}}和G^{\mathrm{w}}间不需要经过换乘层（即公交站台与公交网络之间步行长度视为0）。

等待层（式（6））：由G^{\mathrm{w},\mathrm{b},\mathrm{r}}的等待构成，可分别视为：由信号控制造成的等待G_{\mathrm{w}\mathrm{a}\mathrm{i}\mathrm{t}}^{\mathrm{w}}、由出行者等待公交造成的等待G_{\mathrm{w}\mathrm{a}\mathrm{i}\mathrm{t}}^{\mathrm{b}}、由公交等待信号控制造成的公交等待G_{\mathrm{w}\mathrm{a}\mathrm{i}\mathrm{t}}^{\mathrm{b}\leftarrow \mathrm{w}}、由出行者等待轨道造成的等待G_{\mathrm{w}\mathrm{a}\mathrm{i}\mathrm{t}}^{\mathrm{r}}。

多层网络如图1所示。

另外，用V\mathrm{、}E\mathrm{、}W（式（7）（9））分别表示所节点集、弧段集、边权集（边权由路段行程时间表示）。

V=\{V^{\mathrm{w}},V^{\mathrm{b}},V^{\mathrm{r}}\}（7）

E=\{E^{\mathrm{w}},E^{\mathrm{b}},E^{\mathrm{r}},E^{\mathrm{t}},E_{\mathrm{w}\mathrm{a}\mathrm{i}\mathrm{t}}^{\mathrm{w},\mathrm{b},\mathrm{r}}\}（8）

W=\{W^{\mathrm{w}},W^{\mathrm{b}},W^{\mathrm{r}},W^{\mathrm{t}},W_{\mathrm{w}\mathrm{a}\mathrm{i}\mathrm{t}}^{\mathrm{w},\mathrm{b},\mathrm{b}\leftarrow \mathrm{w},\mathrm{r}}\}（9）

2.2　动态路阻

在网络静态拓扑结构的基础上，对各弧段的路阻进行构建。本文将所有时变网络下的路段行程时间（包括等待时间）进行统一：w(w\in W)由进入该路段的时刻t决定，称为时间依赖函数：

w=f(t)（10）

式中：f(t)在定义域内处处有定义，另外，在本文中，对任意v(v\in V)，不设置点权。

2.2.1　由路段行程时间（不含等待）构成的路阻

由于本文主要考虑的是等待时间如何建模，因此，对于不含等待的边权W^{\mathrm{w},\mathrm{b},\mathrm{r},\mathrm{t}}，假定以匀速行驶或步行通过该路段：

W^{\mathrm{w},\mathrm{b},\mathrm{r},\mathrm{t}}=L^{\mathrm{w},\mathrm{b},\mathrm{r},\mathrm{t}}/S^{\mathrm{w},\mathrm{b},\mathrm{r},\mathrm{t}}（11）

式中：L^{\mathrm{w},\mathrm{b},\mathrm{r},\mathrm{t}}为E^{\mathrm{w},\mathrm{b},\mathrm{r},\mathrm{t}}各路段的长度；S^{\mathrm{w},\mathrm{b},\mathrm{r},\mathrm{t}}为所在路段类型的行驶或步行平均速度。

在实际交通网络中，可考虑通过历史行程时间对未来一段时间的行程时间进行进一步预测，并将预测得到的路段行程时间转换为时间依赖函数（式（10））。

2.2.2　由等待构成的路阻

信号控制等待：W_{\mathrm{w}\mathrm{a}\mathrm{i}\mathrm{t}}^{\mathrm{w}}受交通信号S_{\mathrm{T}}影响（记作W_{\mathrm{w}\mathrm{a}\mathrm{i}\mathrm{t}}^{\mathrm{w}}\leftarrow S_{\mathrm{T}}），不考虑排队长度和交通流量。

公交等待：W_{\mathrm{w}\mathrm{a}\mathrm{i}\mathrm{t}}^{\mathrm{b}\leftarrow \mathrm{w}}受S_{\mathrm{T}}影响，W_{\mathrm{w}\mathrm{a}\mathrm{i}\mathrm{t}}^{\mathrm{b}}受W_{\mathrm{b}}、W_{\mathrm{w}\mathrm{a}\mathrm{i}\mathrm{t}}^{\mathrm{b}\leftarrow \mathrm{w}}和公交发车班次S_{\mathrm{I}}^{\mathrm{b}}影响（记作W_{\mathrm{w}\mathrm{a}\mathrm{i}\mathrm{t}}^{\mathrm{b}\leftarrow \mathrm{w}}\leftarrow S_{\mathrm{T}}和W_{\mathrm{w}\mathrm{a}\mathrm{i}\mathrm{t}}^{\mathrm{b}}\leftarrow W_{\mathrm{b}},W_{\mathrm{w}\mathrm{a}\mathrm{i}\mathrm{t}}^{\mathrm{b}\leftarrow \mathrm{w}},S_{\mathrm{I}}^{\mathrm{b}}，发车仅为首站发车，后续各站台通过推导得到）。

轨道等待：W_{\mathrm{w}\mathrm{a}\mathrm{i}\mathrm{t}}^{\mathrm{r}}受轨道发车班次S_{\mathrm{I}}^{\mathrm{r}}影响（记作W_{\mathrm{w}\mathrm{a}\mathrm{i}\mathrm{t}}^{\mathrm{r}}\leftarrow W_{\mathrm{r}},S_{\mathrm{I}}^{\mathrm{r}}，发车仅为首站发车，后续各站台通过推导得到，无信号控制）。

2.3　FINLO特性

FINLO是在FIFO的基础上针对多层网络的等待时间做的进一步补充和概括，是为了论证满足在考虑等待时间的网络中使用Dijkstra算法求得最优解的理论可行性。

FIFO不能涵盖以下情况：某一班车即将到达出行者上车点，在到达前，搭乘该班车的出行者不论稍早还是稍晚到达上车点，其上车时间点均一致（即等待）。不同学者关于FIFO的描述略有差异，但共识是“车辆以一定顺序进入某路段，则离开该路段时则为什么顺序”，其数学含义为：对于，有。

大部分研究局限在道路车辆行驶上，FIFO满足现有研究，但现有研究少有讨论将该特性扩展至多层网络的等待时间上，本文对其进行界定，以此建立等待时间依赖模型。有以下定理：

定理1：如果一弧段权重w=f(t)，对，满足以下其一条件：

\frac{f(t_{\mathrm{2}})-f(t_{\mathrm{1}})}{t_{\mathrm{2}}-t_{\mathrm{1}}}>-\mathrm{1}（12）

\frac{f(t_{\mathrm{2}})-f(t_{\mathrm{1}})}{t_{\mathrm{2}}-t_{\mathrm{1}}}=-\mathrm{1}（13）

则该弧为FINLO弧或具有FINLO特性，否则该弧为非FINLO弧或具有非FINLO特性。

FINLO即先进不后出，由定理1可知，FIFO是FINLO的子集，FINLO包含先进先出（式（12））和先进同时出两个概念（式（13））。其中式（13）用于描述等待：某一车辆到达前，搭乘该车辆的出行者不论何时到达该上车点搭乘该车辆，其上车时刻和下车时刻不变，该示例可推广至其他交通方式。也可描述以下情况；某一车辆在红灯周期内任意时刻到达交叉口并停车等待，其离开交叉口的时刻不变（不考虑排队长度）。在定理1的基础上有以下规定：

如果网络中所有弧段均为FINLO弧，则称该网络为FINLO网络，否则称该网络为非FINLO网络。

定理2：假设一条路径依次经过e_{\mathrm{0}},e_{\mathrm{1}},\dots ,e_n(i=\mathrm{0,1},\cdots ,n,e_i\in E)，弧段均满足FINLO特性，如果不在节点处停留，则经过e_j到达其终点的时刻为：

t_{i+\mathrm{1}}=t_i+f_i(t_i)（14）

式中：t_i为进入e_i时的时刻；f_i为e_i的时间依赖函数。

可证明该行程整体满足FINLO特性。

证明：

当进入e_{\mathrm{0}}时刻为t_{\mathrm{0}}，则有t_{\mathrm{1}}=t_{\mathrm{0}}+f_{\mathrm{0}}(t_{\mathrm{0}})；

现假设进入e_{\mathrm{0}}时刻为t_{\mathrm{0}\mathrm{\text{'}}}=t_{\mathrm{0}}+\mathrm{\Delta }t(\mathrm{\Delta }t>\mathrm{0})得t_{\mathrm{1}\mathrm{\text{'}}}=t_{\mathrm{0}\mathrm{\text{'}}}+f_{\mathrm{0}}(t_{\mathrm{0}\mathrm{\text{'}}})；

由于t_{\mathrm{0}\mathrm{\text{'}}}>t_{\mathrm{0}}，由式（12）（13）可得t_{\mathrm{1}\mathrm{\text{'}}}\ge t_{\mathrm{1}}；

当进入e_{\mathrm{1}}时刻为t_{\mathrm{1}}，则到达t_{\mathrm{2}}=t_{\mathrm{1}}+f_{\mathrm{1}}(t_{\mathrm{1}})；

当进入e_{\mathrm{1}}时刻为t_{\mathrm{1}\mathrm{\text{'}}}，则到达t_{\mathrm{2}\mathrm{\text{'}}}=t_{\mathrm{1}\mathrm{\text{'}}}+f_{\mathrm{1}}(t_{\mathrm{1}\mathrm{\text{'}}})；

由于t_{\mathrm{1}\mathrm{\text{'}}}\ge t_{\mathrm{1}}，根据e_{\mathrm{1}}的FINLO特性，可得t_{\mathrm{2}\mathrm{\text{'}}}\ge t_{\mathrm{2}}；

由此递推可得式（14），并得到t_{n\mathrm{\text{'}}}\ge t_n；即当t_{\mathrm{0}\mathrm{\text{'}}}>t_{\mathrm{0}}，有t_{n\mathrm{\text{'}}}\ge t_n，得证。

由定理2可知，当网络中均为FINLO弧时，任意一条路径均满足FINLO特性，因此，FINLO网络满足FINLO特性。

同时易知，如果需要确定FINLO网络中某一路径某一时刻出发的最短行程时间，对于行程的中途而言，离开上一路段的时刻即进入下一路段的时刻。与之相对的，允许节点等待的非FINLO网络需要确定在节点处停留时间以确保最短行程时间。

3 等待时间依赖建模

不论信号控制还是搭乘交通工具，出行者都需等待最近绿灯周期或搭乘最近到站车辆。同时，在信号变为新的绿灯或车辆到站之前，出行者越晚到达，其所需等待时间越少。基于上述理念，本节设计了工厂函数（即生成函数的函数）以构建等待时间依赖函数，随后细化不同交通方式的等待时间。

3.1　道路网络等待时间依赖建模

由式（10）可知，对于路段行程时间和等待时间，依赖于函数f的构建，令：

f=F_{\mathrm{f}\mathrm{a}\mathrm{c}\mathrm{t}\mathrm{o}\mathrm{r}\mathrm{y}}(\Delta ,R,G,T)（15）

使得：

（16）

其中：

M=(t-\Delta )\mathrm{\%}(R+G)（17）

式中：F_{\mathrm{f}\mathrm{a}\mathrm{c}\mathrm{t}\mathrm{o}\mathrm{r}\mathrm{y}}为工厂函数；\Delta为周期偏置；R为最大等待时间；G为无等待的通行时间段；T为初始需要固定消耗的时间（由式（11）决定）；\mathrm{\%}为模运算符。

道路网络路段行程时间为定值，如式（18）所示：

f^{\mathrm{w}}=F_{\mathrm{f}\mathrm{a}\mathrm{c}\mathrm{t}\mathrm{o}\mathrm{r}\mathrm{y}}(\mathrm{0,0},\mathrm{0},T)（18）

式中：f^{\mathrm{b},\mathrm{r},\mathrm{t}}同式（18），w^{\mathrm{w},\mathrm{b},\mathrm{r},\mathrm{t}}=f^{\mathrm{w},\mathrm{b},\mathrm{r},\mathrm{t}}(t)，w^{\mathrm{w},\mathrm{b},\mathrm{r},\mathrm{t}}\in W^{\mathrm{w},\mathrm{b},\mathrm{r},\mathrm{t}}，后续不再阐述。

对于S_{\mathrm{T}}而言，在交叉口处以“虚拟边”的形式将等待时间转变为f(t)。在转向延误方面，有学者将网络转化为对偶图的形式，但本质是将原始的网络边权视为点权，并不影响时间复杂度。本文采用“先合并，后拆分”的策略对部分交叉口增加虚拟边，随后新增的虚拟边用于表征信号控制的等待时间。合并和拆分策略见图2。

考虑到达交叉口的时间不同和受到的信号控制不同（转向不同）会导致不同的延误值，对图2右图圈内的每条边权独立构建式（19）：

f_{\mathrm{w}\mathrm{a}\mathrm{i}\mathrm{t}}^{\mathrm{w}}=F_{\mathrm{f}\mathrm{a}\mathrm{c}\mathrm{t}\mathrm{o}\mathrm{r}\mathrm{y}}(\Delta ,R,G,\mathrm{0})（19）

使得w_{\mathrm{w}\mathrm{a}\mathrm{i}\mathrm{t}}^{\mathrm{w}}=f_{\mathrm{w}\mathrm{a}\mathrm{i}\mathrm{t}}^{\mathrm{w}}(t)，w_{\mathrm{w}\mathrm{a}\mathrm{i}\mathrm{t}}^{\mathrm{w}}\in W_{\mathrm{w}\mathrm{a}\mathrm{i}\mathrm{t}}^{\mathrm{w}}。（只考虑定周期，忽视黄灯信号，不考虑排队），如图3所示。

3.2　轨道网络等待时间依赖建模

对于W_{\mathrm{w}\mathrm{a}\mathrm{i}\mathrm{t}}^{\mathrm{r}}而言，以起点为例，设某线路起点站班车j从该站的每日发车时刻为{\Delta }_j，对于该线路该起点，有依次排序的起点发车时刻表{\mathit{\Delta }}_{\mathrm{0}}：

{\mathit{\Delta }}_{\mathrm{0}}=[{\Delta }_{\mathrm{0}},{\Delta }_{\mathrm{1}},\cdots ,{\Delta }_n]（20）

对于非起点站点的发车时刻表{\Delta }_i(i=\mathrm{1,2},\cdots ,n)而言，参考式（14）（18），可得任意班车在该站的发车时刻表：

{\mathit{\Delta }}_{i+\mathrm{1}}={\Delta }_i+f_i^r({\Delta }_i)（21）

假设用户只搭乘最近一班车，可知任意时刻站台i(i=\mathrm{0,1},\cdots ,n)的等待时间（小时为单位，不考虑交通工具的容量限制）：

f_{\mathrm{w}\mathrm{a}\mathrm{i}\mathrm{t}}^{\mathrm{r}}=F_{\mathrm{m}\mathrm{i}\mathrm{n}}({\Delta }_i)（22）

使得：

w_{\mathrm{w}\mathrm{a}\mathrm{i}\mathrm{t}}^{\mathrm{r}}=f_{\mathrm{w}\mathrm{a}\mathrm{i}\mathrm{t}}^{\mathrm{r}}(t)=\mathrm{m}\mathrm{i}\mathrm{n}\{x\in (\Delta -t\mathrm{\%}\mathrm{24})|x\ge \mathrm{0}\}（23）

式中，w_{\mathrm{w}\mathrm{a}\mathrm{i}\mathrm{t}}^{\mathrm{r}}\in W_{\mathrm{w}\mathrm{a}\mathrm{i}\mathrm{t}}^{\mathrm{r}}。

此时各站台的发车时刻则由该车辆在上一站推导得到，如图4所示。式（23）通过二分查找实现。

3.3　公交网络等待时间依赖建模

对于W_{\mathrm{w}\mathrm{a}\mathrm{i}\mathrm{t}}^{\mathrm{b}}而言，各站点的等待时间推导与W_{wait}^r类似，但由于W_{\mathrm{w}\mathrm{a}\mathrm{i}\mathrm{t}}^{\mathrm{b}}\leftarrow W_{\mathrm{b}},W_{\mathrm{w}\mathrm{a}\mathrm{i}\mathrm{t}}^{\mathrm{b}\leftarrow \mathrm{w}},S_{\mathrm{I}}^{\mathrm{b}}和W_{\mathrm{w}\mathrm{a}\mathrm{i}\mathrm{t}}^{\mathrm{b}\leftarrow \mathrm{w}}\leftarrow S_{\mathrm{T}}，因此，还需要考虑S_{\mathrm{T}}的影响。

以下述情况为例（路段行程时间恒为6，中途穿过一信号控制点，包含起终点共计4个站点），各站点发车时刻表推导如图5所示。

其后续等待时间的推导与3.2节一致。

3.4　考虑等待时间依赖的单向绿波

由3.1节可知，等待时间建模可以实现信号控制。与3.2节和3.3节类似，可以进一步结合式（14），验证绿波及其可行性。下面以一个简单模型进行测试：

\begin{array}{l}[F_{\mathrm{f}\mathrm{a}\mathrm{c}\mathrm{t}\mathrm{o}\mathrm{r}\mathrm{y}}(\mathrm{0,0},\mathrm{0,100}),F_{\mathrm{f}\mathrm{a}\mathrm{c}\mathrm{t}\mathrm{o}\mathrm{r}\mathrm{y}}(\mathrm{0,300,100,0}),\\ F_{\mathrm{f}\mathrm{a}\mathrm{c}\mathrm{t}\mathrm{o}\mathrm{r}\mathrm{y}}(\mathrm{0,0},\mathrm{0,100}),F_{\mathrm{f}\mathrm{a}\mathrm{c}\mathrm{t}\mathrm{o}\mathrm{r}\mathrm{y}}(t,\mathrm{300,100,0}),\\ F_{\mathrm{f}\mathrm{a}\mathrm{c}\mathrm{t}\mathrm{o}\mathrm{r}\mathrm{y}}(\mathrm{0,0},\mathrm{0,100})]\end{array}（24）

式（24）表示利用5个工厂函数分别表示3条行程时间为100 s的路段和两个信号周期为400s，进口道绿灯时间为100 s的假想信号控制。

同时第二个信号交叉口与第一个交叉口存在相位差t。检测两个周期内（800 s）任意时刻通过该完整路段的行程时间（见图6），当相位差位于100 s和500 s时，此时具有最宽绿波带，其具有最短平均路段行程时间，且分别在200~300 s和600~700 s内从起点出发具有最短路段行程时间，此时车辆从起点出发位于绿波带上。由于中段路段行程时间为f_{\mathrm{f}\mathrm{a}\mathrm{c}\mathrm{t}\mathrm{o}\mathrm{r}\mathrm{y}}(\mathrm{0,0},\mathrm{0,100})，印证等待时间依赖函数可以通过调节相位差实现绿波控制。上述绿波控制可以进一步引入最短路计算中，解决平均延误无法运用于考虑绿波控制的最短路的问题。

4 时变网络路径规划算法设计

在结合时间依赖建模的基础上，对基于二叉堆构建的Dijkstra算法进行改造，使之能在FINLO网络或允许节点等待的非FINLO网络中寻找时间最短路径。时变网络示例见图7。使用Python 3.9作为本文的编程环境。

4.1　网络结构设计

与传统路网存储的固定权重不同，本文权重均由时间依赖函数进行统一表达。

由于邻接矩阵并不适合存储稀疏路网，使用由时间依赖函数表示边的带权邻接字典存储路网G，格式如式（25）（以图7为例）所示。

\begin{array}{l}\{\mathrm{0}:\{\mathrm{1}:F_{\mathrm{f}\mathrm{a}\mathrm{c}\mathrm{t}\mathrm{o}\mathrm{r}\mathrm{y}}(\mathrm{0,0},\mathrm{0,2}),\mathrm{2}:F_{\mathrm{f}\mathrm{a}\mathrm{c}\mathrm{t}\mathrm{o}\mathrm{r}\mathrm{y}}(\mathrm{1.5,2},\mathrm{2,0})\},\\ \mathrm{1}:\{\mathrm{3}:F_{\mathrm{f}\mathrm{a}\mathrm{c}\mathrm{t}\mathrm{o}\mathrm{r}\mathrm{y}}(\mathrm{0,2},\mathrm{2,0})\},\mathrm{2}:\{\mathrm{3}:F_{\mathrm{f}\mathrm{a}\mathrm{c}\mathrm{t}\mathrm{o}\mathrm{r}\mathrm{y}}(\mathrm{0,0},\mathrm{0,2})\},\\ \mathrm{3}:\{\}\}\end{array}（25）

4.2　OPEN表和CLOSE表

OPEN表是Dijkstra用于临时存储已被探索但尚未纳入CLOSE表的路段的数据结构，核心由一个优先队列构成，本文的优先队列选用二叉堆。OPEN表结构如下：定义一个OPEN类（类指对象类型，下同），初始化一个列表和字典；列表中存储到达节点号v，用于二叉堆元素的排序；字典键值对中的键同样用v表示，值用元组存储到达该节点的当前最优紧前节点号u_{\mathrm{l}\mathrm{o}\mathrm{c}\mathrm{a}\mathrm{l}}和路段(u_{\mathrm{l}\mathrm{o}\mathrm{c}\mathrm{a}\mathrm{l}},v)行程时间w，形如\{v:(w,u_{\mathrm{l}\mathrm{o}\mathrm{c}\mathrm{a}\mathrm{l}})\}；类里同时包含二叉堆的基本函数，用于实现二叉堆的基本操作，包括find-min、delete-min、insert、decrease-key。

CLOSE表是用于存储到达某节点v的最优紧前节点u_{\mathrm{b}\mathrm{e}\mathrm{s}\mathrm{t}}及经过路段(u_{\mathrm{b}\mathrm{e}\mathrm{s}\mathrm{t}},v)到达v的时刻t。同时用于最终回溯路径得到最优结果。CLOSE表结构如下：定义一个CLOSE类，初始化一个字典，字典键值对分别表示v和u_{\mathrm{b}\mathrm{e}\mathrm{s}\mathrm{t}}，形如\{v:(t,u_{\mathrm{b}\mathrm{e}\mathrm{s}\mathrm{t}})\}用于存储已经确定到达v的最优紧前节点u_{\mathrm{b}\mathrm{e}\mathrm{s}\mathrm{t}}；类里同时包含添加和回溯的函数，回溯过程参考图8（以图7的CLOSE表为例，1.7时刻出发，从0到3节点）。

4.3　函数式编程

在求解路径前，由于出行者的出发时刻无法确定，因此，时间依赖建模无法被提前计算，可借助函数式编程特点中的惰性计算进行函数封装，从而实现等待时间依赖建模。以图5为例，流程如图9所示。

通过构建等待时间的工厂函数，可以分别实现恒定延迟（固定权重）、信号控制和班次等待的时间依赖建模。其次，通过递推式（14），可以求得不同站点的出发时间表并进一步转换为各站点上车等待时间依赖函数。通过这种方法，可以将交通工具的行程时间和等待时间建模分离，从而对多层时变交通网络进行有效衔接。

4.4　FINLO网络下时变最短路算法

本小节求解在满足FINLO特性的前提下，任意时刻出发耗时的最短路径。该算法伪代码如算法1所示。

由于等待时满足FINLO特性，因此，考虑等待时间的路径规划可以使用上述算法进行求解。

4.5　允许节点等待的非FINLO网络时变最短路算法

在允许节点等待的非FINLO网络情况下，核心是找到节点等待时间t_{\mathrm{w}\mathrm{a}\mathrm{i}\mathrm{t}}与路段行程时间f(t_{\mathrm{a}\mathrm{r}\mathrm{r}\mathrm{i}\mathrm{v}\mathrm{e}}+t_{\mathrm{w}\mathrm{a}\mathrm{i}\mathrm{t}})最小之和时的t_{\mathrm{w}\mathrm{a}\mathrm{i}\mathrm{t}}。对于最短计算中的单次求解而言，求解节点等待时间t_{\mathrm{w}\mathrm{a}\mathrm{i}\mathrm{t}}的目标函数为：

\underset{t_{\mathrm{w}\mathrm{a}\mathrm{i}\mathrm{t}}}{\mathrm{a}\mathrm{r}\mathrm{g}\mathrm{m}\mathrm{i}\mathrm{n}}\{t_{\mathrm{w}\mathrm{a}\mathrm{i}\mathrm{t}}+f(t_{\mathrm{a}\mathrm{r}\mathrm{r}\mathrm{i}\mathrm{v}\mathrm{e}}+t_{\mathrm{w}\mathrm{a}\mathrm{i}\mathrm{t}})\}（26）

式中：t_{\mathrm{a}\mathrm{r}\mathrm{r}\mathrm{i}\mathrm{v}\mathrm{e}}为到达该节点的时刻，在该时刻可以视为固定值，其可以等价于求：

\underset{t_{wait}}{\mathrm{a}\mathrm{r}\mathrm{g}\mathrm{m}\mathrm{i}\mathrm{n}}\{t_{\mathrm{a}\mathrm{r}\mathrm{r}\mathrm{i}\mathrm{v}\mathrm{e}}+t_{\mathrm{w}\mathrm{a}\mathrm{i}\mathrm{t}}+f(t_{\mathrm{a}\mathrm{r}\mathrm{r}\mathrm{i}\mathrm{v}\mathrm{e}}+t_{\mathrm{w}\mathrm{a}\mathrm{i}\mathrm{t}})\}（27）

令t_{\mathrm{d}\mathrm{e}\mathrm{p}\mathrm{a}\mathrm{r}\mathrm{t}}=t_{\mathrm{a}\mathrm{r}\mathrm{r}\mathrm{i}\mathrm{v}\mathrm{e}}+t_{\mathrm{w}\mathrm{a}\mathrm{i}\mathrm{t}}，可以转变为：

\underset{t_{\mathrm{d}\mathrm{e}\mathrm{p}\mathrm{a}\mathrm{r}\mathrm{t}}}{\mathrm{a}\mathrm{r}\mathrm{g}\mathrm{m}\mathrm{i}\mathrm{n}}\{t_{\mathrm{d}\mathrm{e}\mathrm{p}\mathrm{a}\mathrm{r}\mathrm{t}}+f(t_{\mathrm{d}\mathrm{e}\mathrm{p}\mathrm{a}\mathrm{r}\mathrm{t}})\}（28）

式中：t_{\mathrm{d}\mathrm{e}\mathrm{p}\mathrm{a}\mathrm{r}\mathrm{t}}为进入在完成节点停留进入下一路段的时刻。

由于t_{\mathrm{d}\mathrm{e}\mathrm{p}\mathrm{a}\mathrm{r}\mathrm{t}}不早于从上一路段到达节点的时刻t_{\mathrm{a}\mathrm{r}\mathrm{r}\mathrm{i}\mathrm{v}\mathrm{e}}，即：

t_{\mathrm{a}\mathrm{r}\mathrm{r}\mathrm{i}\mathrm{v}\mathrm{e}}\le t_{\mathrm{d}\mathrm{e}\mathrm{p}\mathrm{a}\mathrm{r}\mathrm{t}}（29）

同时，t_{\mathrm{w}\mathrm{a}\mathrm{i}\mathrm{t}}应等于或小于f(t_{\mathrm{a}\mathrm{r}\mathrm{r}\mathrm{i}\mathrm{v}\mathrm{e}})，否则不需要在节点处等待即应进入下一路段，即：

\left\{\begin{array}{l}{t}_{\mathrm{w}\mathrm{a}\mathrm{i}\mathrm{t}}\le f(t_{\mathrm{a}\mathrm{r}\mathrm{r}\mathrm{i}\mathrm{v}\mathrm{e}})\\ t_{\mathrm{w}\mathrm{a}\mathrm{i}\mathrm{t}}+t_{\mathrm{a}\mathrm{r}\mathrm{r}\mathrm{i}\mathrm{v}\mathrm{e}}\le f(t_{\mathrm{a}\mathrm{r}\mathrm{r}\mathrm{i}\mathrm{v}\mathrm{e}})+t_{\mathrm{a}\mathrm{r}\mathrm{r}\mathrm{i}\mathrm{v}\mathrm{e}}\\ t_{\mathrm{d}\mathrm{e}\mathrm{p}\mathrm{a}\mathrm{r}\mathrm{t}}\le f(t_{\mathrm{a}\mathrm{r}\mathrm{r}\mathrm{i}\mathrm{v}\mathrm{e}})+t_{\mathrm{a}\mathrm{r}\mathrm{r}\mathrm{i}\mathrm{v}\mathrm{e}}\end{array}\right.（30）

综上，进入下一路段的时刻的约束条件为：

t_{\mathrm{a}\mathrm{r}\mathrm{r}\mathrm{i}\mathrm{v}\mathrm{e}}\le t_{\mathrm{d}\mathrm{e}\mathrm{p}\mathrm{a}\mathrm{r}\mathrm{t}}\le t_{\mathrm{a}\mathrm{r}\mathrm{r}\mathrm{i}\mathrm{v}\mathrm{e}}+f(t_{\mathrm{a}\mathrm{r}\mathrm{r}\mathrm{i}\mathrm{v}\mathrm{e}})（31）

结合式（28）（31），实际编程过程采用scipy.optimize的minimize_scalar模块表达区间内最小函数值，通过替换FINLO网络下时变最短路算法中（算法1）的第9行为算法2中的第3行，可以实现允许节点等待的非FINLO网络下时变最短路算法：

5 测试验证

5.1　主要步骤

采用厦门市岛内OSM地图（Open street map）进行测试。按以下步骤进行：

步骤1 加载道路网络拓扑结构V^{\mathrm{w}},E^{\mathrm{w}}，计算路段行程时间F_{\mathrm{f}\mathrm{a}\mathrm{c}\mathrm{t}\mathrm{o}\mathrm{r}\mathrm{y}}(\mathrm{0,0},\mathrm{0},T)，赋值给W^{\mathrm{w}}。

步骤2 通过扩展边的形式（3.1节）扩展道路交叉口，实现新增节点和边，分进口设置信号控制等待时间F_{\mathrm{f}\mathrm{a}\mathrm{c}\mathrm{t}\mathrm{o}\mathrm{r}\mathrm{y}}(\Delta ,R,G,\mathrm{0})，赋值给W_{\mathrm{w}\mathrm{a}\mathrm{i}\mathrm{t}}^{\mathrm{w}}。

步骤3 加载轨道网络拓扑结构V^{\mathrm{r}},E^{\mathrm{r}}，计算站间路段行程时间F_{\mathrm{f}\mathrm{a}\mathrm{c}\mathrm{t}\mathrm{o}\mathrm{r}\mathrm{y}}(\mathrm{0,0},\mathrm{0},T)，赋值给W^{\mathrm{r}}。

步骤4 连接G^{\mathrm{r}}和G^{\mathrm{w}}。形成G^{\mathrm{w}}\to G^{\mathrm{t}}\to G_{\mathrm{w}\mathrm{a}\mathrm{i}\mathrm{t}}^{\mathrm{r}}\to G^{\mathrm{r}}和G^{\mathrm{r}}\to G^{\mathrm{t}}\to G^{\mathrm{w}}，计算G^{\mathrm{t}}路段行程时间F_{\mathrm{f}\mathrm{a}\mathrm{c}\mathrm{t}\mathrm{o}\mathrm{r}\mathrm{y}}(\mathrm{0,0},\mathrm{0},T)，赋值给W^{\mathrm{t}}。

步骤5 根据轨道起点发车班次，结合W^r得到各站点发车时刻表{\Delta }_i(i=\mathrm{0,1},\dots ,n)，计算出各站点等待时间F_{\mathrm{m}\mathrm{i}\mathrm{n}}({\Delta }_i)，赋值给W_{\mathrm{w}\mathrm{a}\mathrm{i}\mathrm{t}}^{\mathrm{r}}。

步骤6 从V^{\mathrm{w}}\mathrm{、}{E}^{\mathrm{w}}复制出公交线网V^{\mathrm{b}},E^{\mathrm{b}}（采用地图匹配，限于篇幅，不展开叙述），计算路段行程时间F_{\mathrm{f}\mathrm{a}\mathrm{c}\mathrm{t}\mathrm{o}\mathrm{r}\mathrm{y}}(\mathrm{0,0},\mathrm{0},T)，将其和途经的信号控制等待时间F_{\mathrm{f}\mathrm{a}\mathrm{c}\mathrm{t}\mathrm{o}\mathrm{r}\mathrm{y}}(\Delta ,R,G,\mathrm{0})分别赋值给W^{\mathrm{b}}和W^{\mathrm{b}\leftarrow \mathrm{w}}。

步骤7 设定公交起点发车班次，根据W^{\mathrm{b}}和W^{\mathrm{b}\leftarrow \mathrm{w}}迭代计算出各站点发车时间，计算出各站点等待时间F_{\mathrm{m}\mathrm{i}\mathrm{n}}({\Delta }_i)，将其赋值给W_{\mathrm{w}\mathrm{a}\mathrm{i}\mathrm{t}}^{\mathrm{b}}。

步骤8 连接G^{\mathrm{b}}和G^{\mathrm{w}}。形成G^{\mathrm{w}}\to G_{\mathrm{w}\mathrm{a}\mathrm{i}\mathrm{t}}^{\mathrm{b}}\to G^{\mathrm{b}}和G^{\mathrm{b}}\to G^{\mathrm{w}}。

步骤9 在网络弧段均通过F_{\mathrm{f}\mathrm{a}\mathrm{c}\mathrm{t}\mathrm{o}\mathrm{r}\mathrm{y}}或F_{\mathrm{m}\mathrm{i}\mathrm{n}}得到时间依赖函数f基础上，根据网络是否满足FINLO特性，采用4.4或4.5节提到的算法进行求解。

换乘细节如图10所示。网络结构和求解结果如图11所示。由于涉及多个交叉口及数百条公交线路，核心参数依据现实情况进行假设，如表1所示。实际运用中，应根据观测或预测得到的各交叉口信号周期、不同网络类型各路段不同时间下的实际行程时间、车辆发车的实际班次及到站情况、出行者个体特征等，对网络的各参数进行标定，从而得到与现实较为符合的路径规划结果。

5.2　模型求解与对比

本文通过调整网络结构和路阻表征，对比不同情况下算法的计算时间和计算结果（见表2）。最短路计算过程均通过由二叉堆构建的Dijkstra算法执行。其中算法1~通过时间依赖函数对时变网络进行路阻表征；算法5~8则只考虑通过固定权重进行路阻表征，可视为经典的基于二叉堆的Dijkstra算法，只是权重不同。表2中，是否考虑信号控制是指是否通过本文3.1节部分对交叉口扩展虚拟边。

测试网络采用厦门市网络（见图11（e）），扩展交叉口前，节点数为36 861，边数为86 925，扩展交叉口后节点数为75 689，边数为162 882，其中筛选有效公交线路为585条（单个方向），有效公交站点数为13058个节点（不同公交线路单独计算站点），轨道线路6条（单个方向），轨道站点数150个（不同方向单独计算站点）。其中算法1和3为本文提到的考虑等待时间的多层交通网络路径规划算法，其余对比算法均考虑多层网络及各层拓扑连接。

从路径耗时看，与非时变的固定路段行程时间的算法5相比，本文算法1、能充分考虑动态网络的时变等待特性，从而找到时变网络下的时间最短路径，路段行程时间减少8.4%。与同为时变网络但不考虑交叉口动态等待时间的算法2、相比，本文对交叉口进行了扩展，从而使算法能考虑信号交叉口的等待时间（算法1、）以选择最优路径，使路段行程时间减少14.9%。

从路径长度看，尽管算法7和8为最短路径，但由于仅考虑长度，其大部分路径位于步行段，使得搜索结果的整体行程时间超过10 h（见图11（d））。同时，由于是否扩展交叉口的区别在于是否存在0长度路段，因此，算法7和8的区别在于网络规模大小，但计算结果的行驶路径长度仍会保持一致，这在表2中得到了验证。

从计算时间看，与非时变网络的路径规划算法相比，由于需要在计算路径的时候计算时间依赖函数，时变网络下的路径规划算会增加计算时间；另外，由于扩展交叉口必然扩展网络规模，考虑交叉口等待时间的算法1、也会相对不考虑交叉口等待时间的算法2、更耗时；在算法3、4中，由于允许节点等待的非FINLO网络下时变最短路算法在每次将路段纳入OPEN表时，需要耗费大量时间以寻找函数的最小值，导致整体运行时间较长，对于FINLO网络，尽管算法3、4能得到同样的计算结果，但考虑到计算时间，算法1会更为适用。

从换乘过程看，本文算法1、，通过考虑交通工具的等待时间和网络拓扑结构，能实现有效换乘（轨道-轨道、轨道-公交、公交-道路）的同时，找到当前的最短时间路径。以图11（a）为例，出行者从早上5：00出发，根据表3设定，此时未有公交发车，出行者经步行后，在公交发车后搭乘公交经轨道换乘后继续前往目的地。以图11（c）为例，出行者在20：36出发，出发时轨道交通并未停运，但由于经过部分行程后当天轨道交通已经停运（即出行者再次等待搭乘轨道的等待时间需要等到第二天早上），出行者继续采用公交前往目的地。

6 结 论

（1）通过调整多层网络的拓扑结构，能有效嵌入等待时间，从而实现在考虑等待时间变化（源于发车班次、信号控制等因素的影响下）的网络中寻找时间最短路径。

（2）本文所提的等待时间依赖函数建模方法能适用于班次等待和信号控制等具有间断性质的等待路阻建模当中。后续可以考虑进一步引入信号控制绿波，发车时刻表协调的研究当中。

（3）等待时间建模与常规的基于分时段的时间依赖建模方法并不冲突，可以进一步考虑两者的结合，对于常规路段的时间依赖采用分时段建模，或者引入历史、预测数据（任意时间节点下进入该路段的路段行程时间）以设定时间依赖函数。

（4）对于信号控制而言，本文只讨论了无排队情况下的等待时间，实际过程中可以进一步引入流量以估计排队长度，从而进一步估计任意时刻因信号控制导致的延误。

参考文献

[1] 陈凤涛. 城市时变网络路径分析方法研究[D]. 南京:东南大学交通学院, 2018.

[2] Chen Feng-tao. Research on the method of routing analysis of urban in time-varying networks[D]. Nanjing: School of Transportation, Southeast University, 2018.

[3] 谭国真. 时变、随机网络最优路径算法及其应用研究[D].大连:大连理工大学信息与通信工程学院, 2002.

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

[5] 王福. GIS中时变最短路径理论及算法研究[D]. 南京: 南京理工大学自动化学院, 2010.

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

[7] 张晓楠, 王陆宇, 谭昕妮, 等. 时变条件下道路网的车辆路径优化[J]. 机械科学与技术, 2023, 42(11): 1919-1928.

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

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

[10] 张煜璐. 考虑碳排放的时变路网多车型城市配送路径优化研究[D]. 杭州:浙江工商大学计算机与信息工程学院,2017.

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

[12] 许祎娜, 王旭仁, 苏红莉. 时变公路网络的动态路径规划算法[J]. 小型微型计算机系统, 2018, 39(6): 1291-1298.

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

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

[15] 何俊, 戴浩, 宋自林, 等. 时间依赖的交通网络模型及最短路径算法[J]. 解放军理工大学学报: 自然科学版, 2005(6): 541-544.

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

[17] 魏航. 时变条件下允许等待的最短路问题[J]. 系统管理学报, 2008, 2008(1): 99-103.

[18] Wei Hang. An approach for time-varying shortest path problem with waiting[J]. Journal of Systems ＆ Management, 2008, 2008(1): 99-103.

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

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

[21] 赵凯旋. MaaS背景下网约车接驳轨道交通的路径优化研究[D]. 武汉: 华中科技大学土木工程与力学学院, 2019.

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

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

[24] 刘松. 面向随机时变网络的带班期限制的多式联运路径优化研究[D]. 重庆: 重庆交通大学交通运输学院, 2019.

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

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

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

[28] 杜牧青, 鞠姿彦, 李大韦. 一种基于交叉口信号延误的超路径规划方法[J]. 西南交通大学学报, 2024, 59(6): 1378-1388.

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

[30] 蒋睿. 考虑节点耗费的时变随机网络最短路径问题研究[D]. 天津: 天津理工大学计算机与通信工程学院, 2016.

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

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

基金资助

国家社科基金重大项目(23&ZD138)