一种基于交叉口信号延误的超路径规划方法

杜牧青; 鞠姿彦; 李大韦

doi:10.3969/j.issn.0258-2724.20220387

一种基于交叉口信号延误的超路径规划方法

doi: 10.3969/j.issn.0258-2724.20220387

1.
河海大学土木与交通学院，江苏南京 210098
2.
东南大学交通学院，江苏南京 210018

基金项目: 国家自然科学基金项目（72471083）

详细信息

作者简介:
杜牧青（1986—），男，副教授，博士，研究方向为交通运输规划与管理，E-mail：dumqhhu@hhu.edu.cn

中图分类号: U491.2
计量
- 文章访问数: 298
- HTML全文浏览量: 97
- PDF下载量: 32
- 被引次数: 0
出版历程
- 收稿日期: 2022-05-30
- 修回日期: 2022-09-20
- 网络出版日期: 2024-10-29
- 刊出日期: 2022-09-22

Hyperpath Searching Algorithm Method Based on Signal Delay at Intersections

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

摘要

摘要:
城市道路中交叉口信号周期性变化会导致车辆出行的不确定延误，为降低车辆在交叉口处产生的信号延误，以路段旅行时间和交叉口期望延误最小为优化目标，提出一种改进的超路径规划方法. 首先，根据车辆到达交叉口的概率分布函数，推导出车辆在信号交叉口的期望等待时间和转向比例计算公式；其次，引入标号设定算法构建高性能超路径规划方法；最后，将改进的超路径规划方法应用于南京新街口区域的路网，通过最优超路径集合分析证实其适用性. 研究表明：与最短路出行策略相比，车辆遵循基于超路径规划方法的出行策略，在行进过程时从最优超路径集合中选择变换的行驶路线可降低67.1%的交叉口信号延误和22.3%的总旅行时间；此外，超路径出行策略可优化路网中的出行结构，缓解交通拥堵，实现流量均衡.
- 交叉口信号配时 /
- 概率分布函数 /
- 转向延误 /
- 扩展的前向星结构 /
- 标号设定算法
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

HTML全文

静态全局路径规划中经典的最短路径算法所规划出的路径难以规避不确定延误产生的等待时间，并且只推荐一条最优路径容易导致大量车辆涌入同一路段，从而形成新的拥堵现象^[1]. 因此，车辆路径诱导系统应该向驾驶人提供可能最优的路径集合，以期提高网络对抗不确定性延误的性能. 目前，国内外学者对多条最优路径生成算法进行了广泛研究与改进，主要集中在以K短路径、完全不相交路径和遗传算法等经典多路径算法^[2].

Hoffman等^[3]最早提出K短路径搜索问题及其算法. 刘辉平^[4]将K短路径问题进行了分类分析. 基于差异性的前K条最短路径具有高度的相似性，不适用于复杂网络中^[5]. 前K条最优顺序的路径只是将不同最优目标的最短路径做简单叠加，实际应用效果不佳^[6]. 也有学者提出生成完全不相交路径算法（total disjoint path algorithm，TDPA）^[7]. TDPA可被分为路段不相交和节点不相交2种情况^[8]. 不相交的路段可以共享节点，反之亦然^[9-10]. 在多约束情况下TDPA可实现最优路径推荐^[11]，但目前该算法主要用于提高网络对不确定性延误的抵抗性能^[12]. 由于路径完全不相交，当其中一条路段发生严重拥堵时，可采用另一条不相交路段实现交通流的疏导，因此，该路径集在旅行时间上不一定最优. 遗传算法具有全局搜索能力，也有学者将其应用于多路径算法的计算中^[13]，使司机可以根据自身偏好自由选择路线，但其搜索效率低，应用性不高. 基于上述可知，目前已有的多路径生成算法无法同时实现路径集合的行驶时间最优和抵抗网络不确定性. 一方面，驾驶人需要在起点确定方案选择，不能在多种方案之间实现路径的转换（除非驾驶人在行驶过程中自行更改路线）；另一方面，上述多路径算法未考虑网络中延误的不确定性，尤其是信号交叉口的延误不确定性，无法有效规避延误问题. 因此，如何实现多路径诱导方案中路线的灵活转换是帮助驾驶人回避交通延误、实现最优的关键.

本文将已有的公交共线问题延伸至路径集合问题，引入适用于道路网络中的超路径概念. 该概念最早由Spiess和Florian^[14]提出，用以解决公交线路中客流分配的“共线”问题. 在公交模型中，超路径被解释为一种最优的乘车策略，包含起终点之间所有可以降低乘车者等车时间的公交线路集合，公交乘车者使用该策略可以有效降低其乘车时间（指乘客到达起始站台到离开终点站台所花费的时间）. Bell^[15]进一步考虑了道路网络中每条路段上行程时间的不确定性，将公交超路径应用于道路网络，并指出超路径搜索算法是一种特殊的多路径算法，以期望行程时间最小为目标，从实际路网中搜索出起终点之间所有可能的最短路径，纳入超路径子网中. 在此的基础上，Ma等^[16]提出加快超路径算法搜索速度的方法. 然而，交叉口延误是城市路网中不确定性因素的重要原因之一^[13]. 以延误最小为目标的路径规划可以大幅提高出行效率，路径规划需要交叉口延误数据的支持^[17]. Ju等^[18]研究了信号控制对超路径集合的影响，为简化延误计算式，假设交叉口进口道各转向对应的信号配时之间相互独立，提出一种车路协同环境下的超路径诱导方法. 但信号交叉口进口道各转向的信号配时之间存在时间顺序，对组合延误的计算有显著影响，其结果不能有效用于车辆路径诱导.

为此，本文通过建立交叉口延误期望的数学模型，提出准确性更高的交叉口转向延误计算式，并进一步构建结合标号设定算法的高性能超路径算法，最后在实例网络中验证所提出路径规划方法的可行性.

1. 原理与数学模型

1.1 超路径原理

可供乘车者选择的公交线路越多，即超路径集合越大，乘车者在站台的平均等车时间就越低. 图1展示了公交超路径概念的原理.

图 1 公交超路径概念示意

Figure 1. Concept of hyperpath in public transport

下载: 全尺寸图片幻灯片

1）从站点A_s到站点D_s，只有发车间隔为6 min的线路1. 此时，乘客的等车期望值 $T\mathrm{_q}=6\ \mathrm{min}$ .

2）从站点A_s到站点D_s，有发车间隔为6 min的线路1、发车间隔为3 min的线路2以及发车间隔为3 min的线路3. 此时，乘客的等车期望值 $T_{\mathrm{q}}= 1/\left(1/6+1/3\right)=2\; \min$ .

由此可见，多条可供选择的公交线路的存在降低了乘客在站台等车的期望时间. 此后，有学者将这一概念引入到道路网络中^[15].

在道路网络中，当延误时间为固定值时，起终点之间存在一条确定的最优路径. 然而，当考虑路网中延误的不确定性时，会存在多条可降低旅行时间的替代路径. 因此，路网中的最优超路径，是起终点之间所有可能成为最优路径构成的集合. 如图2所示，当路段存在不确定延误时，驾驶人在路网中存在多条可替代路径的选择^[15]. 文献[15]假定每条路段都存在一个最大延误.

图 2 道路网络考虑路段延误的最优超路径^[15]

Figure 2. Optimal hyperpath in the road network with the consideration of delays on road segments^[15]

下载: 全尺寸图片幻灯片

超路径策略在现实路网的实际运用中，需要在车辆进入特定的转向车道前给予相应的提示信息，有2种实现方法：

第1种可行方法依赖于车路协同（cooperative vehicle infrastructure system，CVIS）技术的支持. 在有车路协同的环境下，通过及时的路网信息反馈，诱导系统在车辆接近交叉口时，基于最优超路径策略实时推荐合适的转向车道，帮助车辆以最小的等待延误通过前方交叉口. 目前，已有研究证实车路协同环境下超路径诱导方法的可行性^[18].

另一种可行方法，在没有CVIS技术下，可为驾驶人提供多样化的路径选择，结合驾驶人的自主判断，在进入特定车道前选择合适的转向行为. 在驾驶人出发前，超路径诱导系统就提供了完整的路径选择集合. 即使没有CVIS支持，驾驶人也可以提前得知其在每个交叉口可行的选择，根据到达前交叉口的实际情况做出判断，选择出优先绿灯的转向.

但是，与公交网络不同（令最大等车延误等于发车频率的导数），道路的最大延误较难预测，且明显取决于车辆在交叉口的转向行为.

由于交叉口信号变化与公交车到站频率同样具有周期性，车辆在路口等待绿灯的延误可类比于乘客在公交站台的候车延误. 此外，有经验的驾驶人往往会同时考虑多条行车路径，在某些交叉口会根据到达时的信号周期情况，选择优先绿灯放行的可行转向作为前进路线. 这一点与公交“共线”问题中“乘客选择乘坐首先到站的公交线路”情况类似.

因此，本文在公交超路径概念和道路网络中考虑路段延误的超路径基础上，提出考虑交叉口转向延误的超路径规划方法. 由图3可知，由于信号配时的存在，车辆可在该交叉口进行多种转向选择，将产生不同的转向延误. 本文将所有可能降低旅行时间的转向行为纳入超路径集合中. 车辆可根据信号周期情况，在交叉口选择等待时间少的可用转向，进一步实现对出行路线的转换，达到降低不确定性延误的目的.

图 3 交叉口的转向行为

Figure 3. Turning movements at intersection

下载: 全尺寸图片幻灯片

超路径算法以终点作为初始搜索节点，以路段的旅行时间与交叉口期望延误之和最小为目标函数，对路网中的路段逐一搜索，筛选出能降低期望行程延误的路段，形成最优超路径.

在转向延误和转向选择概率的影响下，超路径搜索结果还包括每个路段在超路径集合中被选择的概率，该概率也可以看作是超路径策略下的网络流量分配依据. 因此，超路径规划方法的实现对降低驾驶人个体行程延误以及网络流总体延误有重要意义.

1.2 数学模型的导出

1.2.1 信号交叉口延误的基本原理

考虑信号交叉口延误的超路径规划方法，与公交网络中的超路径问题类似，假设车辆均匀地到达交叉口. 但与公交候车等待时间的计算原理不同，由于最优超路径在进口道存在单个或多个相位选择情况，两者的计算思路不同. 具体原理为：

1）车辆在交叉口单个转向的期望延误时间，是车辆到达交叉口时等待时间的分布函数的积分.

2）车辆在交叉口多个转向的期望延误时间，是组合相位下车辆到达交叉口时等待时间的分布函数的积分.

以下给出了基于信号配时的交叉口单个转向和多个转向的期望延误时间以及最优超路径中可行转向选择概率的数学模型推导过程.

1.2.2 单个转向延误的数学模型

为描述问题，引入以下参数： ${W_X}$ 为车辆沿进口道X通过交叉口时的期望延误时间； $r_{X,m}$ 为进口道 $X$ 的第m个可用转向； $R(X)$ 为超路径在进口道 $X$ 处包含的所有可用转向， $R(X) = \{ {r_{X,1}},{r_{X,2}}, \cdots ,{r_{X,m}}, \cdots,r_{X,n} \}$ ； $y_{r_{X,m}}$ 为车辆沿进口道X到达交叉口时等待转向 $r_{X,m}$ 的时间； $P(y_{r_{X,m}})$ 为 $y_{r_{X,m}}$ 的分布函数，如所示； $y_{r_{X,m}}$ 的期望延误时间的分布函数为1− $P(y_{r_{X,m}})$ ； $G\mathrm{_K}$ 为可通行时间（绿灯时间和黄灯时间之和）；T为周期时长；t₀为不可通行时间，t₀=T – G_K； $E(y_{r_{X,m}})$ 为车辆在进口道 $X$ 处单个转向 ${r_{X,m}}$ 的期望延误时间，如式（1）所示.

图 4

${y_{{r_{X,m}}}}$ 的分布函数

Figure 4. Distribution function of

${y_{{r_{X,m}}}}$

下载: 全尺寸图片幻灯片

$\begin{split} & E(y_{r_{X,m}})=\int_0^{\infty}[1-P(y_{r_{X,m}})]\text{d}\text{z}= \\ &\quad\int_0^{t_0}\left[1-\left(\frac{G_{\mathrm{K}}}{T}+\frac{1-G_{\mathrm{K}}/T}{t_0}\right)\right]\text{d}\text{z}= \\ &\quad(1-G_{\mathrm{K}}/T)t_0/2=(T-G_{\mathrm{K}})^2/(2T). \end{split}$

(1)

由式（1）可知，单个转向对应的期望延误时间由信号配时的G_K和T决定.

1.2.3 多个转向延误的数学模型

当最优超路径在进口道处存在多个可用转向时，进口道处的期望延误时间由组合的新相位决定. 本文以2个相位组合为例，即 $R(X) = \left\{ {{r_1},{r_2}} \right\}$ . 由于组合相位中可通行时间段（绿灯时间和黄灯时间的总和）数量影响了车辆在交叉口的最大等待时间，因此本文将其分为相邻和不相邻2种情况进行讨论. 其中， $g_{1,{\mathrm{o}}}$ 和 $g_{1,{\mathrm{t}}}$ 分别表示第1个相位的可通行时间的开始时刻和结束时刻， $g_{2,{\mathrm{o}}}$ 和 $g_{2,{\mathrm{t}}}$ 分别表示第2个相位的可通行时间的开始时刻和结束时刻.

1）若多个可用相位不相邻（ $g_{1,{\mathrm{t}}} < g_{2,{\mathrm{o}}}$ ）

为可用相位不相邻的情况，图中： ${G_1}$ 和 ${G_2}$ 分别为左转和直行的可通行时间（绿灯和黄灯时间之和）， ${t_1}$ 和 ${t_2}$ 分别为左转和直行转向对应绿灯时间的间隔时间，即红灯时间. 假设 ${t_1} > {t_2}$ ，通过组合相位得到可通行时间 ${G_X} = {G_1} + {G_2}$ .

图 5 不相邻转向的组合（单位：s）

Figure 5. Combination of non-adjacent turns （unit:s）

下载: 全尺寸图片幻灯片

令 ${y_X}$ 为车辆在组合相位下在进口道 $X$ 的等待时间，其在一个周期内最大等待时间为最长的红灯时间，即 ${t_1}$ ，据此概率分布 $P(y_X)$ 如图6所示.

图 6 相位不相邻

${y_X}$ 的分布函数

Figure 6. Distribution function of

${y_X}$

下载: 全尺寸图片幻灯片

中以 $t_1$ （ $t_1>t_2$ ）作为等待时间的上限，即车辆在到达交叉口后，经过时间 ${t_1}$ 必定能遇到绿灯. 同理，车辆在进口道 $X$ 存在多个可用不相邻转向 $R(X)$ 时，等待时间的期望 $W_X$ 为

$\begin{split} & W_X=\int_0^{\infty}[1-P(y_X)]\text{d}{\textit{z}}= \\ & \quad\displaystyle\int_0^{t_{\text{1}}}\left[1-\left(\frac{G_{\text{1}}\text{ + }G_2}{T}+\frac{1-(G_{\text{1}}\text{ + }G_2)/T}{t_{\text{1}}}\right)\right]\text{d}{\textit{z}}= \\ & \quad[1-(G_{\text{1}}\text{ + }G_2)/T]t_{\text{1}}/2=(t_1+t_2)t_1/(2T).\end{split}$

(2)

以图7的信号配时为例，根据式（1）、（2）计算该交叉口多个转向组成的期望延误时间. 仅考虑左转的期望延误时间为20.0 s；同时考虑左转和直行的期望延误时间为7.8 s.

图 7 交叉口信号配时图（单位：s）

Figure 7. Intersection signal timing diagram (unit: s)

下载: 全尺寸图片幻灯片

2）若多个可用相位相邻（ $g_{1,{\mathrm{t}}} \geqslant g_{2,{\mathrm{o}}}$ ）

图8为可用相位相邻交叉口的信号配时图. 由图8可知，此时组合相位的情况与单个转向延误的数学模型相似，分布函数如图9所示.

图 8 相邻转向绿灯时间的组合

Figure 8. Combination of the green time for adjacent turns

下载: 全尺寸图片幻灯片

图 9 相位相邻

${y_X}$ 的分布函数

Figure 9. Distribution function of

${y_X}$

下载: 全尺寸图片幻灯片

同理，车辆在进口道 $X$ 存在多个可用相邻转向 $R(X)$ 时，期望延误时间 $W_{X}$ 为

$\begin{split} & W_X=\int_0^{\infty}[1-P(y_X)]\text{d}\text{z}= \\ & \quad\int_0^{t_1}\left(1-\left(\frac{G_X}{T}+\frac{1-G_X/T}{t_1}\right)\right)\text{d}\text{z}= \\ & \quad(1-G_X/T)t_1/2=t_1^2/(2T). \end{split}$

(3)

1.2.4 转向延误选择概率数学模型

超路径的存在，使得驾驶人在交叉口处有多种选择. 然而，同一配时中各相位的绿灯时间存在差异，所以被选择的各转向的概率也不同. 驾驶人选择不同转向，使得车辆进入不同的下游路段，从而实现路网中交通流量的分配. 各转向被选择的概率就是车流量分配到各路段的比重，具有一定的研究意义. 因此，以图7的配时图为例，求解转向概率.

在超路径网络中，为降低延误时间车辆到达交叉口时会选择优先绿灯的转向. 因此，在不同时间段到达的车辆会有不同的转向选择，从而决定了各转向被选中的概率.

假设该交叉口有直行和左转2个相位包含在超路径中，将左转和直行2个相位进行时间段分割.

由于转向的概率选择与相位是否相邻有关，因此区分以下2种情况进行讨论，如、所示. 图中： $G_{\mathrm{O}}$ 为相邻相位绿灯重叠时间（不相邻相位不存在 $G_{\mathrm{O}}$ ）； $G_{X\mathrm{a}}$ 为相邻组合相位的可通行时间.

图 10 相邻两相位时间段分割

Figure 10. Segmentation of two adjacent phases

下载: 全尺寸图片幻灯片

图 11 不相邻两相位时间段分割

Figure 11. Segmentation of two non-adjacent phases

下载: 全尺寸图片幻灯片

1）多个可用相位相邻（ $g_{1,{\mathrm{t}}} \geqslant g_{2,{\mathrm{o}}}$ ）

车辆在进口道X选择左转的概率为

${\gamma _{X{\mathrm{l}}}} = \frac{1}{2} {G_{\mathrm{O}}}\Bigg/\mathop \sum \limits_{{r_{X,m}} \in R\left( X \right)} {G_{X\mathrm{a}}} +({G_1} - {G_{\mathrm{O}}})\Bigg/\mathop \sum \limits_{{r_{X,m}} \in R\left( X \right)} {G_1} ,$

(4)

车辆在进口道X选择直行的概率为

${\gamma _{X{\mathrm{s}}}} = \frac{1}{2} {G_{\mathrm{O}}}\Bigg/\mathop \sum \limits_{{r_{X,m}} \in R\left( X \right)} {G_{X\mathrm{a}}} +({G_2} - {G_{\mathrm{O}}})\Bigg/\mathop \sum \limits_{{r_{X,m}} \in R\left( X \right)} {G_2} .$

(5)

2）多个可用相位不相邻（ $g_{1,{\mathrm{t}}} < g_{2,{\mathrm{o}}}$ ）

此时G_X = G₁+G₂，车辆在进口道X选择转向左转的概率为

$\gamma_{X{\mathrm{l}}}=G_1/G_X,$

(6)

车辆在进口道X选择转向直行的概率为

$\gamma_{X{\mathrm{s}}}=G_{\text{2}}/G_X.$

(7)

基于上述推导可知，上述模型同样适用于可行相位数量大于2个的情况，因此模型具有普遍适用性.

对于网络流问题，各路段的被选择概率，可看作沿超路径将车流量分配到各路段的比例，即通过转向比例实现交通流量的合理分配.

1.3 信号配时对超路径构成的影响

根据式（1）～（3）可知交叉口信号配时决定了转向延误的期望值，进而影响超路径的构成，如图12所示. 图中：箭头表示车辆行驶方向，数值表示路段旅行时间，变量下标A、B、C、D表示交叉口，变量下标r、l、s、sl分别表示右转、左转、直行和左转与直行的组合，W_C,s表示在交叉口C选择直行的延误时间，其余变量释义类同. 通过图12所示的局部方格网络，说明信号配时变化对超路径集合的影响.

图 12 局部方格网络示意（单位：s）

Figure 12. Local grid-type network （unit: s）

下载: 全尺寸图片幻灯片

根据配时，设定的最优超路径集合包含路径1（A—B—C）和路径2 （A—D—C），超路径期望旅行时间为121.6 s，低于任何一条单一路径（131.4 s和149.3 s）. 进一步，改变交叉口A和C的信号配时，超路径集合的构成会发生变化，结果如表1所示.

表 1 信号配时变化对超路径集合元素的影响

Table 1. Influence of signal timing on hyperpath set

序号	交叉口	周期/s	相位 1/s	相位 2/s	相位 3/s	路径 1 时间/s	路径 2 时间/s	组合期望/s	最优超路径
1	A	110	40	50	20	131.4	149.3	121.6	A—B—C, A—D—C
1	C	80	60	20	0	131.4	149.3	121.6	A—B—C, A—D—C
2	A	150	80	20	50	202.6	127.1	130.1	A—D—C
2	C	120	30	90	0	202.6	127.1	130.1	A—D—C
3	A	47	12	15	20	124.4	138.8	125.1	A—B—C
3	C	110	95	15	0	124.4	138.8	125.1	A—B—C

下载: 导出CSV

| 显示表格

表1中超路径集合的构成随着交叉口信号配时的变化而不同，可以看出交叉口延误值是影响超路径集合的重要因素之一.

2. 超路径算法流程

由于新的网络结构增加了对车辆在交叉口转向行为的考虑，即对于同一进口道的车辆如果转向行为不同，其在交叉口产生的等待时间也不相同^[19]. 因此，原有超路径算法不能直接用于解决当前问题. 为此本文采用扩展的前向星结构（EFSS）^[20]表示交叉口转向行为，并对超路径算法做出相应的改进.

值得说明的是，算法的遍历方式影响着标号的含义和位置. 现有的EFSS结构大多应用于传统最短路径算法的交叉口转向表达中^[21-22]. 不同的是，超路径算法从终点开始遍历节点，因此其对应的EFSS结构需要进行修改. 参数定义如表2所示.

表 2 参数定义

Table 2. Parameters definition

符号	含义
$G(N,A)$	有向网络图，其中N、A分别为网络中的节点集合、路段集合
${\varGamma ^ - }(i)$	流入节点 $i$ 的路段集合
${\varGamma ^ + }(i)$	流出节点 $i$ 的路段集合
j	节点 i 的下游节点标号
k	节点 j 的下游节点标号
s	终点
r	起点
${m_k}$	转向节点 k 的转向行为
H	超路径的路段集合
${M_{i,j}}$	进口道 $(i,j)$ 处，属于超路径的转向行为集合
$u_{i,j}$	进口道 $(i,j)$ 到终点的期望旅行时间
$p\{ (j,k)\|i\}$	由节点 i 转向路段 $j—k$ 时，节点 $j$ 被选择的概率
$p\{ k\|j\}$	由节点 j 转向节点 k 时，节点 k 被选择的概率
${P_{ {i,j} }}$	在节点i处，路段 $i—j$ 被选择的概率
$c_{i,j}$	路段 $i—j$ 的旅行时间
$\xi_{i,j,m_k}$	从节点 i 经过节点 j 转向节点 k 的期望延误时间
$w_{i,j}$	进口道为 $\left(i,j\right)$ 时，在节点 j 处的组合延误期望值
注： $\displaystyle \sum\nolimits_{(i,j) \in {\varGamma ^ + }(i)} {P_{{i,j} }} = 1$ .

下载: 导出CSV

| 显示表格

2.1 超路径的最优化模型

根据表1所给出的参数，建立超路径的最优化模型，如式（8）～（11）所示. 式（8）为最小化超路径的期望旅行时间，式（9）为流量守恒约束，式（10）～式（11）表示节点概率为各出度路段概率的总和.

${\min _p}\mathop \sum \limits_{\left( {j,k} \right) \in A} c(j,k) p\{ (j,k)|i\} + \mathop \sum \limits_{i,j \in N} w_{i,j} p\{ j|i\},$

(8)

$\begin{split} & {\mathrm{s.t.}} \displaystyle \sum _{\left(j,k\right)\in {\Gamma }_{j}^{ + }}{P}_{j,k}-\displaystyle \sum _{\left(i,j\right)\in {\Gamma }_{j}^-}{P}_{i,j}= \left\{\begin{array}{l} 1,\quad k=s,\\ -1, \quad i=r,\\ 0, \quad 其他, \end{array}\right.\\ &\quad \forall i,j,k\in N, \end{split}$

(9)

$\begin{split} & p\{ (j,k)|i\} = {P_{ {j,k} }} p\{ j|i\},\quad \forall i,j,k \in N,\quad \left({j,k} \right) \in A, \end{split}$

(10)

$p\{ j|i\} = 1,\quad j = s \;或\; i = r.$

(11)

2.2 基于标号算法的超路径结构

对于超路径算法下的交叉口转向行为进行以下描述. 有向图 $G (N,A)$ 中， $\xi (i,j,{m_k}) = \infty$ 表示转向行为被禁止. 对于任意节点j， $|\mathit{\Gamma}^+(j)|$ 表示节点j的出度，共有 $|\mathit{\Gamma}^+(j)|$ 对标号 $\{ u_{i,j},{m_k}\}$ 用以记录节点j处特定转向行为产生的旅行时间费用. 由于超路径从终点开始搜索，标号方向应与搜索方向保持一致. 为表示出当前节点到终点的期望旅行时间，在入度集合 ${\varGamma ^ - }(i)$ 中增加节点本身，即 $u_{i,i}$ 表示虚拟进口道 $\left(i,i\right)$ 到终点的期望旅行时间. 弧段和节点标号的表示如图13所示.

图 13 超路径网络中的标号定义

Figure 13. Definitions of labels in the hyperpath network

下载: 全尺寸图片幻灯片

2.3 算法步骤

步骤1　对于有向图 $G (N,A)$ 指定起点r和终点s；创建存储所有弧段的集合L，创建代表搜索方向的弧段集合S，创建存储最优超路径弧段的集合H，以及创建存储所有转向延误的集合S_T. 初始化各变量如式（12）所示.

$\left\{\begin{array}{l} L = A\text{，}H = \varnothing ,\\ u_{i,j}=\infty \text{，}\;\;\forall (i,j) \in L\text{，}\forall j \ne s,\\ u_{i,s}=0\text{，}\;\;\forall \xi _{i,j,{m_k}} \in {S_{\mathrm{T}}} ,\\ w_{i,j}=0\text{，}\;\;\forall i \ne r,\\ p\{ i|(j,k)\} =0\text{，}\;\; p\{ j|k\} =0,\forall j \in N\text{，}\\ p\{ m|s\} =1,\;\;\forall m \in N\text{.} \end{array}\right.$

(12)

步骤2　初始化集合S. 找到集合L中 $u_{j,k} + c_{j,k}$ 最小的路段j—k，将其加入集合S中.

步骤3　如果集合S为空，转步骤6；否则，找到集合S中 $u_{j,k} + c_{j,k}$ 最小的路段j—k，并从集合S中删除.

步骤4　当 $u_{i,j} \geqslant u_{j,k} + c_{j,k}$ 时，其中 $i \in {\varGamma ^ - }(j)$ ，在集合S_T中找到对应的 $\xi _{i,j,{m_k}}$ .

当 $u_{i,j} = \infty$ 时， $p\{ (j,k)|i\} = p\{ k|j\}$ ， $p\{ j|i\} =$ $p\{ (j,k)|i\}$ ， $u_{i,j} = u_{j,k} + \xi _{i,j,{m_k}} + c_{j,k} p\{ (j,k)|i\}$ ，将转向 ${m_k}$ 纳入集合 ${M_{i,j}}$ 中并记录路段j—k被选中的概率 $p\{ (j,k)|i\}$ . 集合H中增加路段j—k，集合S中增加路段i—j；否则， ${u}_{i,j}=\left({w}_{i,j}+{\displaystyle \sum _{{m}_{l}\in {M}_{i,j}}({u}_{j,l} + c_{j,l}) p\{(j,l)|i\}}\right) p\left\{j\right|i\}$ ，其中， $w_{i,j}$ 由式（2）或式（3）计算， $p\{ j|i\}$ 、 $p\{ (j,l)|i\}$ 由式（4）～式（7）计算. 集合 ${M_{i,j}}$ 中增加转向行为 ${m_l}$ 并记录概率 $p\{ (j,l)|i\}$ . 集合H中增加路段j—k，集合S中增加路段i—j.

步骤5　若满足条件S ${\text{ = }}\varnothing$ 或 $\text{ }{u}_{r,n} + c_{r,n} > {u}_{r,r}$ ，则进入步骤6；否则，返回步骤3.

步骤6　从起点r开始，根据记录，用深度优先搜索追溯到达终点s的超路径集（包含各路段的选择概率）.

超路径算法属于LS （lable search）算法的一种. LS算法的思路是通过迭代过程对标号进行修正，每次迭代选择集合S中标号最小的路段，并将其从集合S中删除，标志着该节点标号从临时标号转变为永久标号. 在初始迭代后，算法从终点开始搜索，在贪心策略下，每次搜索到的都是当前离终点最近的路段. 在局部最优导致全局最优的策略下，搜索出最优超路径. 由于超路径的性质，同一进口道可以有多种转向. 由式（4）～（7）可知，信号配时的存在使得每条路段被选中的概率不同，因此该概率也决定了各路段在 $u_{j,k}$ 中的占比. 值得注意的是，当前进口道存在多个可用转向后，该进口道的期望旅行时间不再是简单的相加，需要用式（2）～（3）完成.

在步骤3中，超路径的筛选标准是新的路段可以降低 $u_{i,j}$ 的值，也就是降低路段i—j到终点的最小期望旅行时间. 通过不断迭代，直到集合S为空或 $\text{ }{u}_{r,n} + c_{r,n} > {u}_{r,r}$ ，算法终止.

3. 算例分析

为进一步检验所提出的超路径规划方法，调查了南京市中心新街口区域的路网，并作为研究对象. 该区域共有49个交叉口，其中有37个信号控制交叉口. 同时，区域内有29条路段，包含多条主干道、次干道和支路. 具体情况如图14所示，图中线路旁数字表示路段被选择的概率.

图 14 起点38到终点37的最短路径和最优超路径

Figure 14. Shortest path and optimal hyperpath from origin 38 to destination 37

下载: 全尺寸图片幻灯片

图14中，以节点38为起点、节点37为终点，分别由考虑转向延误的Dijkstra算法计算出的最短路径和由改进的超路径算法计算出的最优超路径.

3.1 最优超路径集合分析

3.1.1 路径选择概率

采用C# 编程代码实现第1、2节提出的超路径算法. 由图14可知，最优超路径集合中共有2条可行路径，如表3所示.

表 3 路径选择概率

Table 3. Path choice probability

路径	路径走行路段	路径被选择概率
路径 1	38—7—9—10—14—17—18— 19—20—44—22—26—32—37	0.45
路径 2	38—7—9—13—16—17—18— 19—20—44—22—26—32—37	0.55

下载: 导出CSV

| 显示表格

3.1.2 与Dijkstra算法结果对比

交通效益或效果的评价指标通常有：通行能力（饱和度）、总延误、排队长度、行程时间和停车次数等^[23]. 本文选取总延误时间、总旅行时间和流量分配占比3个指标对比最短路和超路径出行策略的影响. 表4列出相应的计算结果.

表 4 两种路径出行策略对比

Table 4. Comparison between two routing strategies

出行策略	路径	总旅行时间/s	总旅行时间降低率/%	总延误时间/s	总延误时间降低率/%
最短路	路径 1	1 010.0	317.0
超路径	路径 1 或路径 2	784.8	22.3	104.2	67.1

下载: 导出CSV

| 显示表格

1）总旅行时间

由表4可知，基于超路径出行策略，起讫点之间，可以降低22.3%的总旅行时间. 在路网中，各驾驶人沿最优超路径出行，通过交叉口处的多转向组合，降低交叉口等待时间，从而实现总旅行时间的缩短.

2）总延误时间

表4的结果表明，超路径的总延误降低率高达67.1%，即多条可行路径的存在，降低了交叉口的等待延误，降低了总延误时间.

3）流量分配占比

基于表3的路径选择比例，考虑交通量为500 辆/h的情况，将其分配到以节点38为起点节点37为终点的路网中，结果如图15所示. 路网流量均衡地分配在2条路径上，避免了流量集中造成的路段拥堵.

图 15 网络流量分配

Figure 15. Traffic distribution in the network

下载: 全尺寸图片幻灯片

基于以上3个指标，采用超路径诱导策略，可以实现流量在网络中的合理分配，达到网络整体车辆交叉口延误时间和总旅行时间最短的目的.

3.1.3 超路径集合最优性检验

超路径搜索算法的原理是将所有可能降低交叉口延误的路段纳入最优超路径集合中. 车辆在当前交叉口距终点的最短旅行时间，通过式（13）计算得到.

$T = {\mathrm{min}}\mathop \sum \limits_{\left( {i,j} \right) \in L} u_{i,j} p\{ j|i\} + \mathop \sum \limits_{i,j \in N} w_{i,j}.$

(13)

根据式（13），超路径集合在每个交叉口的目标函数值最小，任意减少或增加每个交叉口超路径集合元素，目标函数值都会增加.

为检验所得超路径的最优性，选取交叉口9、20进行验证. 令 $\hat{X}$ 表示转向被选择的情况， $\hat{X}=(0,0,1)$ 中的元素从左到右依次表示为直行、左转和右转，其中0表示未选择，1表示选择.

1）进口道(7,9)

表5列出了进口道(7,9)对应下游路段9—10和9—13的各项参数指标.

表 5 进口道(7,9)的相关参数

Table 5. Related parameters of entrance (7,9)

下游路段	转向行为	距终点的总旅行时间/s	路段旅行时间/s	延误时间/s	选择概率/%	组合延误时间/s	组合总旅行时间/s
9—10	左转	555.3	79.0	22.1	45	8.5	655.2
9—13	直行	582.3	52.0	19.2	55	8.5	655.2

下载: 导出CSV

| 显示表格

基于式（9），仅有路段9—10在最优超路径中时，令 $\hat{X}=(1,0,0)$ ；仅有路段9—13在最优超路径时，令 $\hat{X}=(0,1,0)$ ；2个路段都在最优超路径中时，令 $\hat{X}=(1,1,0)$ . 计算以上3种情况下进口道(7,9)到终点的总旅行时间. 数据对比呈现于图16中.

图 16 进口道(7,9)处转向选择对总旅行时间的影响

Figure 16. Total travel time versus the set of turns on entrance (7,9)

下载: 全尺寸图片幻灯片

由可知，只有当2个路段都在超路径集合中时，即 $\hat{X}=(1,1,0)$ 时，总旅行时间才最小，对应于最优超路径. 与图14的超路径搜索结果一致.

2）进口道(19,20)

表6列出进口道(19,20)对应下游路段20—21和20—44的各项参指标.

表 6 进口道(19,20)的相关参数

Table 6. Related parameters of entrance (19,20)

下游路段	转向行为	距终点的总旅行时间/s	路段旅行时间/s	延误时间/s	选择概率/%	组合延误时间/s	组合总旅行时间/s
20—21	直转	283.6	13.0	31.1	13.8	0	307.6
20—44	右转	255.3	40.0	0	86.2	0	307.6

下载: 导出CSV

| 显示表格

为进行数据对比，找到路段20—21到终点的最短路径，即20—21—22—26—32—37，将其补充于超路径集合中.

同理，也有3组对比数据列在图17中.

图 17 进口道(19,20)转向选择对总旅行时间的影响

Figure 17. Total travel time versus the set of turns on entrance (19,20)

下载: 全尺寸图片幻灯片

由图17可知，并非所有的组合延误都是最优，在进口道(19,20)处，只有右转的转向为最优. 所以只有路段20—44在最优超路径集合中.

基于上述2个进口道总旅行时间分析可知，最优超路径集合均符合式（9），具有降低交叉口等待延误的特点.

4. 结　论

本文考虑交叉口信号配时造成的不确定延误影响，根据车辆到达交叉口的概率分布函数，提出基于交叉口信号配时的交叉口延误和转向选择概率的计算公式. 通过标号设定算法实现超路径对转向延误的考虑，改进了超路径算法. 通过数值实验，选取交叉口延误、行程时间和流量分配占比3个指标，从整体网络角度分析超路径策略相对于最短路的优点. 最后选取南京市中心路网进行超路径算法试验，验证改进超路径算法的应用前景. 得出以下结论:

1）利用EFSS结构存储交叉口延误，进一步结合LS算法实现超路径算法对转向延误的计算. 通过分析搜索结果，验证了本文考虑交叉口延误的超路径算法的有效性.

2）根据车辆在当前交叉口距终点的最短旅行时间函数T，验证了超路径集合在每个交叉口的目标函数值最小，任意减少或增加每个交叉口超路径集合元素，目标函数值都会增加，验证了最优超路径的合理性.

3）从个体出行角度分析，相比于最短路径策略，超路径策略在延误时间和旅行时间方面均有大幅降低，分别为67.1%和22.3%.

4）从流量分配角度，超路径策略可根据交叉口的转向延误概率实现对网络交通流量的合理分配，为优化道路交通量的均匀分布提供有效工具.

图 1 公交超路径概念示意

Figure 1. Concept of hyperpath in public transport

下载: 全尺寸图片幻灯片

图 2 道路网络考虑路段延误的最优超路径^[15]

Figure 2. Optimal hyperpath in the road network with the consideration of delays on road segments^[15]

下载: 全尺寸图片幻灯片

图 3 交叉口的转向行为

Figure 3. Turning movements at intersection

下载: 全尺寸图片幻灯片

${y_{{r_{X,m}}}}$ 的分布函数

Distribution function of ${y_{{r_{X,m}}}}$

下载: 全尺寸图片幻灯片

图 5 不相邻转向的组合（单位：s）

Figure 5. Combination of non-adjacent turns （unit:s）

下载: 全尺寸图片幻灯片

相位不相邻 ${y_X}$ 的分布函数

Distribution function of ${y_X}$

下载: 全尺寸图片幻灯片

图 7 交叉口信号配时图（单位：s）

Figure 7. Intersection signal timing diagram (unit: s)

下载: 全尺寸图片幻灯片

图 8 相邻转向绿灯时间的组合

Figure 8. Combination of the green time for adjacent turns

下载: 全尺寸图片幻灯片

相位相邻 ${y_X}$ 的分布函数

Distribution function of ${y_X}$

下载: 全尺寸图片幻灯片

图 10 相邻两相位时间段分割

Figure 10. Segmentation of two adjacent phases

下载: 全尺寸图片幻灯片

图 11 不相邻两相位时间段分割

Figure 11. Segmentation of two non-adjacent phases

下载: 全尺寸图片幻灯片

图 12 局部方格网络示意（单位：s）

Figure 12. Local grid-type network （unit: s）

下载: 全尺寸图片幻灯片

图 13 超路径网络中的标号定义

Figure 13. Definitions of labels in the hyperpath network

下载: 全尺寸图片幻灯片

图 14 起点38到终点37的最短路径和最优超路径

Figure 14. Shortest path and optimal hyperpath from origin 38 to destination 37

下载: 全尺寸图片幻灯片

图 15 网络流量分配

Figure 15. Traffic distribution in the network

下载: 全尺寸图片幻灯片

图 16 进口道(7,9)处转向选择对总旅行时间的影响

Figure 16. Total travel time versus the set of turns on entrance (7,9)

下载: 全尺寸图片幻灯片

图 17 进口道(19,20)转向选择对总旅行时间的影响

Figure 17. Total travel time versus the set of turns on entrance (19,20)

下载: 全尺寸图片幻灯片

表 1 信号配时变化对超路径集合元素的影响

Table 1. Influence of signal timing on hyperpath set

序号	交叉口	周期/s	相位 1/s	相位 2/s	相位 3/s	路径 1 时间/s	路径 2 时间/s	组合期望/s	最优超路径
1	A	110	40	50	20	131.4	149.3	121.6	A—B—C, A—D—C
1	C	80	60	20	0	131.4	149.3	121.6	A—B—C, A—D—C
2	A	150	80	20	50	202.6	127.1	130.1	A—D—C
2	C	120	30	90	0	202.6	127.1	130.1	A—D—C
3	A	47	12	15	20	124.4	138.8	125.1	A—B—C
3	C	110	95	15	0	124.4	138.8	125.1	A—B—C

下载: 导出CSV

表 2 参数定义

Table 2. Parameters definition

符号	含义
$G(N,A)$	有向网络图，其中N、A分别为网络中的节点集合、路段集合
${\varGamma ^ - }(i)$	流入节点 $i$ 的路段集合
${\varGamma ^ + }(i)$	流出节点 $i$ 的路段集合
j	节点 i 的下游节点标号
k	节点 j 的下游节点标号
s	终点
r	起点
${m_k}$	转向节点 k 的转向行为
H	超路径的路段集合
${M_{i,j}}$	进口道 $(i,j)$ 处，属于超路径的转向行为集合
$u_{i,j}$	进口道 $(i,j)$ 到终点的期望旅行时间
$p\{ (j,k)\|i\}$	由节点 i 转向路段 $j—k$ 时，节点 $j$ 被选择的概率
$p\{ k\|j\}$	由节点 j 转向节点 k 时，节点 k 被选择的概率
${P_{ {i,j} }}$	在节点i处，路段 $i—j$ 被选择的概率
$c_{i,j}$	路段 $i—j$ 的旅行时间
$\xi_{i,j,m_k}$	从节点 i 经过节点 j 转向节点 k 的期望延误时间
$w_{i,j}$	进口道为 $\left(i,j\right)$ 时，在节点 j 处的组合延误期望值
注： $\displaystyle \sum\nolimits_{(i,j) \in {\varGamma ^ + }(i)} {P_{{i,j} }} = 1$ .

下载: 导出CSV

表 3 路径选择概率

Table 3. Path choice probability

路径	路径走行路段	路径被选择概率
路径 1	38—7—9—10—14—17—18— 19—20—44—22—26—32—37	0.45
路径 2	38—7—9—13—16—17—18— 19—20—44—22—26—32—37	0.55

下载: 导出CSV

表 4 两种路径出行策略对比

Table 4. Comparison between two routing strategies

出行策略	路径	总旅行时间/s	总旅行时间降低率/%	总延误时间/s	总延误时间降低率/%
最短路	路径 1	1 010.0	317.0
超路径	路径 1 或路径 2	784.8	22.3	104.2	67.1

下载: 导出CSV

表 5 进口道(7,9)的相关参数

Table 5. Related parameters of entrance (7,9)

下游路段	转向行为	距终点的总旅行时间/s	路段旅行时间/s	延误时间/s	选择概率/%	组合延误时间/s	组合总旅行时间/s
9—10	左转	555.3	79.0	22.1	45	8.5	655.2
9—13	直行	582.3	52.0	19.2	55	8.5	655.2

下载: 导出CSV

表 6 进口道(19,20)的相关参数

Table 6. Related parameters of entrance (19,20)

下游路段	转向行为	距终点的总旅行时间/s	路段旅行时间/s	延误时间/s	选择概率/%	组合延误时间/s	组合总旅行时间/s
20—21	直转	283.6	13.0	31.1	13.8	0	307.6
20—44	右转	255.3	40.0	0	86.2	0	307.6

下载: 导出CSV

参考文献(23)

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

施引文献

附加材料(0)

访问统计

点击查看大图

图(17) / 表(6)

计量

文章访问数: 298
HTML全文浏览量: 97
PDF下载量: 32
被引次数: 0

1. 原理与数学模型
1.1 超路径原理
1.2 数学模型的导出
1.3 信号配时对超路径构成的影响
2. 超路径算法流程
2.1 超路径的最优化模型
2.2 基于标号算法的超路径结构
2.3 算法步骤
3. 算例分析
3.1 最优超路径集合分析
4. 结　论

一种基于交叉口信号延误的超路径规划方法

doi: 10.3969/j.issn.0258-2724.20220387

作者简介: 杜牧青（1986—），男，副教授，博士，研究方向为交通运输规划与管理，E-mail：dumqhhu@hhu.edu.cn

计量

出版历程

Hyperpath Searching Algorithm Method Based on Signal Delay at Intersections

1. 原理与数学模型

1.1 超路径原理

1.2 数学模型的导出

1.2.1 信号交叉口延误的基本原理

1.2.2 单个转向延误的数学模型

1.2.3 多个转向延误的数学模型

1.2.4 转向延误选择概率数学模型

1.3 信号配时对超路径构成的影响

2. 超路径算法流程

2.1 超路径的最优化模型

2.2 基于标号算法的超路径结构

2.3 算法步骤

3. 算例分析

3.1 最优超路径集合分析

3.1.1 路径选择概率

3.1.2 与Dijkstra算法结果对比

3.1.3 超路径集合最优性检验

4. 结 论

计量

出版历程

目录

1. 原理与数学模型

1.1 超路径原理

1.2 数学模型的导出

1.3 信号配时对超路径构成的影响

2. 超路径算法流程

2.1 超路径的最优化模型

2.2 基于标号算法的超路径结构

2.3 算法步骤

3. 算例分析

3.1 最优超路径集合分析

4. 结 论

作者简介:
杜牧青（1986—），男，副教授，博士，研究方向为交通运输规划与管理，E-mail：dumqhhu@hhu.edu.cn

4. 结　论

4. 结　论