基于真实路网特性及动态行程时间的最短路径诱导方法

摘要

本发明公开了一种基于真实路网特性及动态行程时间的最短路径诱导方法，首先，考虑真实路网特性，以交叉口转向限制信息和路段流量方向分布不均性为基础得到路网抽象图。其次，以实时行程时间和历史行程时间为因子，预测路段的动态行程时间，根据预测的动态行程时间计算路段交通阻抗，作为抽象路网的路段权值。最后，通过最短路径搜索算法，获得实时的最短路径。本发明克服了现有的路网抽象模型不能反映真实路网特性（交叉口转向限制信息和路段流量方向分布不均性），以及现有的基于静态交通信息的最短路径诱导方法无法对偶发的、随机的、动态交通事件（拥堵、临时管制、交通事故等）进行及时响应等缺陷，该方法获得的诱导路径更加实时、准确、有效。

权利要求

1.一种基于真实路网特性及动态行程时间的最短路径诱导方法，其特征在于，该方法包括如下步骤：

1)根据现实路网中交叉口的转向限制信息，得到基于交叉口各进口道的节点抽象方案；同时根据路段流量的方向分布不均性，按照路网中路段的可达性进行路段的有向图抽象，同一路段不同行驶方向给予不同编号，从而得到基于不同行驶方向的路段抽象方案；合并所述节点抽象方案和路段抽象方案得到路网抽象图；

2)根据路段不同行驶方向的实际检测行程时间和该路段在前一周同一天同一时段内的不同行驶方向的历史行程时间，按照下式计算该路段在下一时段内分行驶方向的行程时间预测值：Tk(t+1)＝θk·Tkt(n)+(1-θk)·Tk(t+1)(h)        (1)式中，Tk(t+1)为路段k在(t+1)时段内的行程时间预测值；Tkt(n)为路段k在t时段内的实际检测行程时间值；Tk(t+1)(h)为路段k在(t+1)时段内的历史行程时间值；θk为路段k的平滑系数，t为系统时段时序；

3)根据所述步骤2)得到的行程时间预测值，计算得到路段交通阻抗，并将其作为路网抽象图中各节点之间的路段权值；

计算路段交通阻抗的具体步骤为：

首先，根据下式计算车辆到达路段k起点时所属时段在系统工作时段序列中的序号Xk：其中int[]为取整函数，tk为车辆到达路段k起点的时刻，t0为系统接受诱导响应的起始时刻，ΔT为时段间隔；

其次，根据下式计算用户在通过路段k时穿越的各时段对应的行程时间预测值分别为Tk1'，Tk2'，Tk3'，…Tki'，…：其中，i为车辆通过路段k时跨越的时段总数， 为通过步骤2)得到的路段k在时段(Xk+i-1)内的行程时间预测值；

然后，计算车辆从进入第一时段即i＝1时到行驶完该时段所通过的长度与路段k总长度的比值S1：其中， 为通过步骤2)得到的路段k在时段Xk内的行程时间预测值；

最后，得到路段k的交通阻抗即路段权值Tk如下：

其中，Tk(n+1)'的值为穿越路段k时的第(n+1)时段对应的预测行程时间，n为中间量，由下式试算得到：

4)基于所述步骤1)得到的路网抽象图和所述步骤3)得到的路网抽象模型中各节点之间的路段权值，采用Dijkstra最短路径搜索算法，搜索路网中指定起讫点的最短路径，得到实时最短路径，并将其作为路径诱导方案。

2.根据权利要求1所述的一种基于真实路网特性及动态行程时间的最短路径诱导方法，其特征在于：所述步骤1)中得到基于交叉口各进口道的节点抽象方案的具体步骤为：首先，将路网中的交叉口按照进口道进行编号，然后，根据相邻交叉口的转向信息和相邻交叉口各进口道之间的可达性，确定各进口道之间的邻接关系，通过邻接表的指针指向实现相邻交叉口的各个进口道之间的邻接关系，最后建立基于各交叉口、各进口道的邻接表，作为基于交叉口各进口道的节点抽象方案。

说明书

基于真实路网特性及动态行程时间的最短路径诱导方法

技术领域

[0001] 本发明属于智能交通控制和交通诱导技术领域，涉及一种最短路径诱导方法。

背景技术

[0002] 随着城市化的快速发展，交通拥堵问题日趋严重。通过城市道路拓宽、路网改造等道路硬件升级，交通拥堵问题非但没有得到缓解，整个交通网络的服务水平反而降低。实际交通效率显著下降，严重地制约着城市的发展。城市智能交通诱导(Urban Intelligent Traffic Guidance，UITG)作为缓解城市交通拥堵的有效途径之一，通过诱导信息影响出行前、出行中的出行人，宏观上可以均衡网络上的交通流量，使网络的综合交通能力达到最大；微观上可以缩短出行费用和时间，实现路网交通设施运行效益的最大化。

[0003] 目前，城市智能交通诱导主要是基于静态的交通信息和以传统的无向图为路网抽象基础的最短路径诱导。但是，在现实世界中，因为路段上的交通状态是实时变化的，静态的交通状态不符合真实路网环境。并且传统的以无向图为基础的路网抽象方案不能准确的表示现实路网中交叉口的转向限制信息(如禁止左转、禁止右转、单行线)，不能体现路段流量的方向分布不均匀的特性(出城高峰和返城高峰等)。

[0004] 为了克服上述缺陷，得到更加具有实用意义的最短路径，本发明提出一种基于真实路网特性和动态行程时间预测的最短路径诱导方法。首先，结合区域内的现实路网特性，以交叉口转向限制和路段流量方向分布不均性为基础，优化路网抽象模型。其次，建立区域内各路段在不同时段内分行驶方向的行程时间预测表，根据预测行程时间计算路段交通阻抗，作为路网模型中的路段权值。最后，根据最短路径搜索算法找到指定起讫点的最短路径。

发明内容

[0005] 技术问题：本发明提供一种以真实路网特性和动态行程时间预测为基础搜索最短路径，进行诱导，使抽象的路网模型更加真实、诱导的路径更加精确，既满足了交通流特性在相同类别的时间段具有相似的趋势特性，又可以随时根据突发的交通状况进行及时响应的基于真实路网特性及动态行程时间的最短路径诱导方法，克服了传统的以无向图为基础的路网抽象模型和现有的以静态行程时间或是路程长度为权值的最短路径诱导的缺陷与不足。

[0006] 技术方案：本发明的基于真实路网特性及动态行程时间的最短路径诱导方法，包括以下步骤：

[0007] 1)根据现实路网中交叉口的转向限制信息，得到基于交叉口各进口道的节点抽象方案；同时根据路段流量的方向分布不均性，按照路网中路段的可达性进行路段的有向图抽象，同一路段不同行驶方向给予不同编号，从而得到基于不同行驶方向的路段抽象方案；合并所述节点抽象方案和路段抽象方案得到路网抽象图；

[0008] 2)根据路段不同行驶方向的实际检测行程时间和该路段在前一周同一天同一时段内的不同行驶方向的历史行程时间，按照下式计算该路段在下一时段内分行驶方向的行程时间预测值：

[0009] Tk(t+1)＝θk·Tkt(n)+(1-θk)·Tk(t+1)(h)  (1)

[0010] 式中，Tk(t+1)为路段k在(t+1)时段内的行程时间预测值；Tkt(n)为路段k在t时段内的实际检测行程时间值；Tk(t+1)(h)为路段k在(t+1)时段内的历史行程时间值；θk为路段k的平滑系数，t为系统时段时序；

[0011] 3)根据所述步骤2)得到的行程时间预测值，计算得到路段交通阻抗，并将其作为路网抽象图中各节点之间的路段权值；

[0012] 4)基于所述步骤1)得到的路网抽象图和所述步骤3)得到的路网抽象模型中各节点之间的路段权值，采用Dijkstra最短路径搜索算法，搜索路网中指定起讫点的最短路径，得到实时最短路径，并将其作为路径诱导方案。

[0013] 本发明方法的优选方案中，步骤1)中得到基于交叉口各进口道的节点抽象方案的具体步骤为：

[0014] 首先，将路网中的交叉口按照进口道进行编号，然后，根据相邻交叉口的转向信息和相邻交叉口各进口道之间的可达性，确定各进口道之间的邻接关系，通过邻接表的指针指向实现相邻交叉口的各个进口道之间的邻接关系，最后建立基于各交叉口、各进口道的邻接表，作为基于交叉口各进口道的节点抽象方案。

[0015] 本发明方法的优选方案中，步骤3)中计算路段交通阻抗的具体步骤为：

[0016] 首先，根据下式计算车辆到达路段k起点时所属时段在系统工作时段序列中的序号Xk：

[0017]

[0018] 其中int[]为取整函数，tk为车辆到达路段k起点的时刻，t0为系统接受诱导响应的起始时刻，ΔT为时段间隔；

[0019] 其次，根据下式计算用户在通过路段k时穿越的各时段对应的行程时间预测值分别为Tk1'，Tk2'，Tk3'，…Tki'，…：

[0020]

[0021] 其中，i为车辆通过路段k时跨越的时段总数， 为通过步骤2)得到的路段k在时段(Xk+i-1)内的行程时间预测值。

[0022] 然后，计算车辆从进入第一时段即i＝1时到行驶完该时段所通过的长度与路段k总长度的比值S1：

[0023]

[0024] 其中， 为通过步骤2)得到的路段k在时段Xk内的行程时间预测值；

[0025] 最后，得到路段k的交通阻抗即路段权值Tk如下：

[0026]

[0027] 其中，Tk(n+1)'的值为穿越路段k时的第(n+1)时段对应的预测行程时间，n为中间量，由下式试算得到：

[0028]

[0029] 有益效果：本发明与现有技术相比，具有以下优点：

[0030] 1)传统的路网抽象方案是以无向图为基础的，将交叉口抽象成单一节点，路段抽象为线段，这种抽象方式忽略了交叉口和路段的真实特性：在城市路网的交叉口中，往往存在转向限制信息(禁左、禁右等)；城市路段往往在同一时间段内，不同行驶方向的交通流量分布是不同的，在高峰时间段内，这种流量分布不均性将会更加明显。本发明与现有的以无向图为基础的路网抽象方案相比，采用进口道细化和邻接表的方式，增加了现实路网中交叉口的转向限制信息(如禁止左转、禁止右转、单行线)以及路段流量的方向分布不均性，使抽象的路网模型更加真实、诱导的路径更加精确。

[0031] 2)传统的交通诱导是以静态交通信息为基础的，如路段长度和路段行程时间，但城市道路的特性表明：路网的交通状况是实时变化的，以静态交通信息为依据的交通诱导，它忽略了城市路网的动态变化的真实特性，不能对时变的交通信息进行响应，因此，经过这种方式得到的诱导路径不是准确的。本发明与传统的以静态交通信息为权值的交通诱导相比，增加了动态的、实时的交通信息，以实时交通信息和历史数据为基础的行程时间预测，既满足了交通流特性在相同类别的时间段具有相似的趋势特性，又可以随时根据突发的交通状况进行及时响应。

附图说明

[0032] 图1为本发明实施例的流程图；

[0033] 图2本发明实施例的传统路网抽象方案图；

[0034] 图3为本发明实施例路网抽象优化方案图；

[0035] 图4为本发明实施例的路段上的OD点对抽象优化图；

[0036] 图5为本发明实施例的路段交通阻抗计算示意图；

[0037] 图6为本发明实施例的路段交通阻抗计算案例图；

[0038] 图7为本发明的实际应用案例图。

具体实施方式

[0039] 下面结合具体实施例和说明书附图进一步详细阐明本发明，应理解这些实施例仅用于说明本发明而不用于限制本发明的范围，在阅读了本发明之后，本领域技术人员对本发明的各种等同形式的修改和替换均落于本发明权利要求所限定的保护范围。

[0040] 本发明提出的基于真实路网特性及动态行程时间的最短路径诱导方法，其流程图见附图1，主要包括如下步骤：

[0041] 1)考虑现实路网的特性，提出以交叉口转向限制和路段流量方向分布不均性为基础的路网抽象优化方案：

[0042] 首先，将路网中的交叉口按照进口道进行编号，然后根据相邻交叉口的转向信息和各进口道之间的可达性，确定各进口道之间的邻接关系，通过邻接表的指针指向实现相邻交叉口的各进口道之间的邻接关系，最后建立各交叉口、各进口道的邻接表，实现交叉口的转向限制目的。其次，按照路网中路段的可达性进行路段的有向图抽象，其次考虑相同时段内同一路段不同行驶方向流量分布的不均性，将区域内的同一路段分起终点进行编号。路网抽象优化方案详细步骤如下：

[0043] 现实路网中，诱导系统要求从起点到终点的总的行程时间最短，转化到图论中的最短路径问题上，就是将路段的行程时间抽象成网络图中的路段弧值，将交叉口抽象成网络节点。本发明所提的交叉口节点优化模型采用邻接表的存储方式。在邻接表中，对每一个顶点u，用一个链表将所有与u相邻的顶点串起来，与u相邻的顶点的集合记为Adj(u)。如果这个图是有向图，那么Adj(u)中的每个元素就是从u开始的一条有向边的另一端的顶点，如图2所示。

[0044] 传统的路网模型抽象虽然直观地反映出了各交叉口的邻接关系，但存在缺陷：无法表示交叉口的转向限制信息。在图2中，假设车辆从D经过A时禁止左转，此时A点无法邻接到B点，因此上述邻接表具有局限性，无法表示客观实际的节点限制信息。鉴于上述缺陷，本发明综合考虑现实路网的有向性和交叉口的转向限制问题，对过去简单的把交叉口抽象成单一节点的处理方式进行了优化，增加了路网节点的转向信息，将交叉口按进口道进行细化，再利用邻接表的指针，分别指向相邻交叉口的各个进口道，达到实现交叉口的转向限制目的。如图3所示。可以发现，同一交叉口由于各进口道的转向限制，邻接表内的元素是不一样的。

[0045] 由于现实生活中路径规划的起讫点(OD点对)往往是在路段上的，如图4所示。根据诱导算法停止的依据：如果发现最短路径的终点为目标路径的终点时，算法停止。因此必须要对原有的路网交叉口进口道邻接表进行临时修改，步骤如下：

[0046] (1)在目标路段上找出起点O沿行驶方向的最近节点A1，将原有邻接表中的邻接点A1全部替换为O，即将所有指向A1的指针改为指向O；增加O点的邻接信息：O→A1。

[0047] (2)在目标路段上找出终点D沿行驶方向的最近节点A2，将原有邻接表中的邻接点A2全部替换为D，即将所有指向A2的指针改为指向D；增加D点的邻接信息：D→A2。

[0048] 2)基于指数平滑法对得到的实时行程时间数据和历史行程时间数据进行处理，得到区域内各路段在各时段内不同行驶方向的行程时间预测表：

[0049] 获取前一周每一天的以固定时段为间隔的同一路段不同行驶方向的历史行程时间数据，建立路段历史行程时间数据库；利用路段检测器得到该路段在各时段内不同行驶方向的实时路段行程时间；通过计算得到该路段在下一时段内分行驶方向的预测行程时间值。具体采用指数平滑法：：

[0050] Tk(t+1)＝θk·Tkt(n)+(1-θk)·Tk(t+1)(h)  (1)

[0051] 式中，Tk(t+1)为路段k在(t+1)时段内的行程时间预测值；Tkt(n)为路段k在t时段内的实际检测行程时间值；Tk(t+1)(h)为路段k在(t+1)时段内的历史行程时间值；θk为路段k的平滑系数；t系统时段时序。

[0052] 以ΔT为一个时段的长度，将时间轴划分为1，2，3…t，此为时段编号。同时考虑相同时段内路段流量的分布不均匀性，将区域内的路段分起终点进行编号1，2，3…k，建立路段行程时间预测表如表1所示。以t0表示系统开始接受服务响应的时刻，所属时段为x。

[0053] 表1路段行程时间预测表/min

[0054]

[0055]

[0056] 3)根据各路段在各时段内不同行驶方向的行程时间预测值，计算得到路段交通阻抗，作为各路段权值：

[0057] 用户车辆可能在任意时刻呼叫诱导服务，t0为系统接受诱导响应的起始时刻，并且用户可能要经过多个路段才能到达目的地，假设车辆依次通过路段1，2，3…(k-1)，k…，车辆经过路段k的时间范围定义为[tk～tk']，车辆经过整个路段的时间(行程时间权值)为Tk，易得，tk'＝tk+Tk，由于路段k-1是路段k的上游路段，考虑路段的连续性，可得tk-1'＝tk。由于用户在通过路段k时可能会穿越好几个时段，各时段对应的行程时间预测值为Tk1'，Tk2'，Tk3'，…Tki'，为了便于理解该计算模型，将路段k的行程时间预测表转化为图5的模式，由积分的相关知识可知：纵坐标为速度，横坐标为时间，则由横、纵坐标包围的区域面积表示为行驶长度。分析可知，图5满足唯一约束条件：阴影部分的面积为1。根据图5的相关性质及约束条件，计算路段k的交通阻抗即路段权值Tk的具体步骤如下：

[0058] 首先，计算车辆到达路段k起点时所属时段在系统工作时段序列中的序号Xk：

[0059]

[0060]

[0061] int[]为取整函数。其中，i为车辆通过路段k时跨越的时段总数， 的值通过查询路段k在时段(Xk+i-1)内的行程时间预测值得到。

[0062] 然后，计算车辆从进入第一时段(i＝1)开始到行驶完该时段所通过的长度与路段k总长度的比值S1：

[0063]

[0064] 其中， 为通过步骤2)得到的路段k时在时段Xk内的行程时间预测值。

[0065] 最后，得到路段k的交通阻抗即路段权值Tk如下：

[0066]

[0067] 其中，Tk(n+1)'的值为穿越路段k的第(n+1)时段对应的预测行程时间，n为中间量，由下式试算得到：

[0068]

[0069] 下面以一个路段为例，如图6所示，说明计算路段交通阻抗即路段权值的具体过程：

[0070] 如图所示，路段行驶方向为A→B，系统接受响应的时刻t0为0，若车辆在第4分钟到达A，即tk为4，以ΔT为5min为例建立该行驶方向上的路段行程时间预测表，如下：

[0071] 表2A→B路段行程时间预测表/min

[0072]

[0073] 求解A→B的路段权值Tk的过程如下：

[0074] (1)首先确定车辆到达A点时属于第一时段(0-5min)，即Xk＝1，查询路段行程时间预测表得到：

[0075] (2)计算该车行驶完第一时段所走的长度与路段长度的比值S1：

[0076]

[0077] (3)计算 则

[0078] (4)试算n，得： 因此n＝2；

[0079] (5)计算Tk：

[0080]

[0081] 4)基于Dijkstra最短路径搜索算法，根据优化的模型需要，提出改进方案：

[0082] 首先，根据步骤1)中建立的交叉口各进口道的邻接信息表，查找经过步骤2)和步骤3)得到的路网抽象模型中各节点之间的路段权值，带入到Dijkstra最短路径搜索算法中，搜索出路网中指定起讫点的最短路径。

[0083] Dijkstra算法又叫双标号算法，是由荷兰数学家E.W.Dijkstra提出，是一个基于非负权值网络的最短路径算法，通过权值和排序可以计算出从任意指定节点到图中所有其他节点之间的最短路径。Djikstra算法采用贪心策略来计算最短路径，它是按照路径长度逐点增长的方法构造路径树，生成一个从树的根节点(即起点)到其他所有节点的最短路径。

[0084] 为验证本发明的实用性和有效性，以南京市江宁区核心区域路网为例，如图7所示，选取路网北至鼓山路(万达商业广场)，南至金山路，东至竹山路(主干路)，西至小龙湾路(新建道路)。本次验证进行单车诱导，车辆从A1出发，终点为J2(万达广场停车场)，如图中标记所示。

[0085] 根据上述路网抽象方案，建立路网节点邻接表：

[0086] 表3实际路网节点邻接表

[0087]

[0088]

[0089] 考虑研究路网高峰时段内的道路拥挤变化的精度以及路段长度小，行程时间短的特点，本次仿真以分析周期为15min，时段间隔ΔT为3min(180s)分别建立工作日平峰、高峰时段路段行程时间预测表。关键路段行程时间如表4、表5所示。为简化计算量，假设系统接受响应的时刻为第一时段的起始时刻。

[0090] 表4路网行程时间预测表(平峰)/s(13:45-14:00)

[0091]

[0092] 执行结果如下：

[0093] Planned Shortest Path:A1→N2→M2→L2→K2→J2

[0094] Predicted Total Travel Time:274.4s

[0095] 表5路网行程时间预测表(高峰)/s(17:30-17:45)

[0096]

[0097]

[0098] 执行结果如下：

[0099] Planned Shortest Path:A1→B3→C1→D1→E3→F1→G1→H1→I1→J1→J2[0100] Predicted Total Travel Time:300.7s

[0101] 比较两次仿真结果可知：在平峰和高峰时段内，最短路径是不同的；平峰时段内生成的最短路径为竹山路(主干路)，道路比较畅通，行程距离较短；高峰时段内最短路径为小龙湾路和兴宁路(新建道路)，道路等级较高，通行能力较强，车流量相对较少，避开了竹山路因下班、放学接送车辆造成的严重道路拥挤，因此生成的最短路径符合真实环境，具有实际意义。