1.本发明涉及智能驾驶汽车的行车路径规划技术领域，具体涉及考虑城市路网行程时间动态变化的全局最优路径规划方法。
背景技术：2.智能化作为汽车新四化的代表之一，如今的技术发展势头愈发快速，其中汽车的自动驾驶技术是智能化开发的主阵地。自动驾驶技术从技术流向可以划分为感知、定位、预测、决策、规划及控制六大部分，其中规划层起着承上启下的关键作用。按照空间尺度大小可以将规划层进一步分为全局规划与局部规划。全局规划一般指全局路径规划，主要从行程时间最短或行驶里程最短等方面展开研究，输出一条从起点到终点的路径，生成的路径时空跨度较大。全局路径规划从宏观层面决定了车辆在未来时空的运动路线，为后端的局部路径规划起到了关键作用，两者技术的相互支撑可极大提高车辆的智能化水平，加快商业落地进程。
3.目前全局路径规划可分为静态路径规划(static path planning，spp)和滚动路径规划(rolling path planning，rpp)：(1)spp将路网权值视为定值，常见的便是路程最短路径规划，主要研究各类路径寻优算法，包括dijkstra算法、a* 算法、蚁群算法等，但spp忽略了交通信息的更新，使得规划的路径无法适应动态交通的改变。(2)rpp将路网权值视为动态变化的，当路网的权值发生改变时不断滚动规划路径，常见的便是行程时间最短路径规划。动路径规划主要研究未来交通信息的预测以及信息的融合处理，不断调用spp的路径规划算法获得实际行驶路径；一般来说，rpp的结果是多阶段的局部最优路径拼接而成，这种拼接得到的路径无法保证全局最优。
4.现有技术中，如cn111982142a公开的一种基于改进a星算法的智能车全局路径规划方法、申请号202010763228.1，其规划方法包括如下步骤：本发明将室外特定区域停车场划分为网格，每个网格中心视为一个控制点，将所有控制点放入l集并编号，根据空间状态初始化各控制点初始权重矩阵om，自动确定起点、手动选择目标终点，动态识别障碍物；然后根据改进a星算法的智能车全局路径规划方法，规划出全局最优的路径；在用户界面显示可行驶路径，进行路口信息、减速、转向等安全性提示。本发明解决了智能车辆路径规划不能高效规划最短路径问题，完成室外停车场最短路径规划和全局路径避障的综合行驶的目标，且路口信息、减速、转向等安全性提醒，本发明直观明了，功能完善，可适用于大多数场景路径规划；该申请公开的技术方案，重点对算法做了改进，但忽略了环境信息的改变。
5.如cn112562309a公开的基于改进dijkstra算法的网约车调度方法、申请号 202110222684.x；其反潜股份首先获取指定区域内路网数据、poi数据、出租车行程gps数据和实时路况数据；其次，选取了经典的dijkstra算法，并在其基础上调整权重，把路网距离影响因子和基于实时路况的时间影响因子综合考虑，形成新的乘客需求与司机匹配策略；最后，依据poi数据与出租车行程gps的综合数据产生随机乘客与司机分布，为每一个随机产生的乘客设定一个调度范围，通过改进dijkstra算法在调度范围中进行司机和路径搜
索，得到兼顾乘客、司机和网约平台三者利益的最优化路径。本发明有效地提高了司机的利用率，平台的接单率，以及减少了乘客的等待时间。
技术实现要素：6.针对现有技术存在城市路网动态行程时间的环境中，无法有效规划全局最优路径，造成智能汽车行驶路径不佳、时间长的问题，本发明的目的是提供一种考虑城市路网行程时间动态变化的全局最优路径规划方法，旨在解决智能汽车从始发地到目的地全程行驶过程的路径不佳、时间长的问题。
7.本发明的技术方案是这样实现的：
8.考虑城市路网行程时间动态变化的全局最优路径规划方法，其特征在于包括如下步骤：
9.1)获取城市路网的各个路段在不同日期、不同时段的车流量数据；
10.2)某个具体路段在某天的任意时间段的行程时间，通过该路段的车流量数据映射为行程时间，获得该路段任意时间段的动态的行程时间；
11.3)车辆从始发地到目的地的全局最优路径规划，在前述步骤2)获得城市路网每一条具体路段在本次行程预计通过的时间段的具体行程时间的前提下，从车辆始发地开始利用改进的dijkstra算法计算到目的地的所有路径中，将每一条路径的每个路段的行程时间相加，得到累计行程时间最短的路径。
12.这样，本发明通过获取城市路网的各个路段的车流量数据，再根据该路段的车流量数据映射为行程时间，获得该路段任意时间段的动态的行程时间；从车辆始发地开始，利用改进的dijkstra算法计算到目的地的所有路径中，将每一条路径的每个路段的行程时间相加，得到累计行驶时间最短的路径。
13.进一步的：步骤1)所述的获取城市路网的各个路段车流量数据，是通过城市路网的路面车辆信息采集设备，实时采集各个路段的车流量数据，将其传回数据中心，数据中心通过统计便可获得该路段在不同日期、不同时段的车流量数据。
14.进一步的：所述某一个具体路段的车流量数据基于下式映射为行程时间，
[0015][0016]
其中，q代表某一路段的车流量，下标i代表周期w的编号，fq代表周期、
[0017]
日期、时刻与车流量的函数映射关系，t代表每日的任意时刻，n代表一定范围的整数；r
t
为路段行程时间，f
t
为路段行程时间映射函数，t0为路段自由流行程时间，α,β为模型常量参数，c为路段实际通行能力。
[0018]
进一步的：实时采集各个路段的车流量数据后，在不考虑节假日、临时突发重大交通事故的前提下，城市路网车流量具有显著的周期性，简称周期相似性，如式(1)所示：
[0019]
qi＝fq(wi,d,t)≈fq(wi+nw,d,t)
ꢀꢀꢀ
(1)
[0020]
式中，q代表某一路段的车流量，下标i代表周期w的编号，fq代表周期、
[0021]
日期、时刻与车流量的函数映射关系，t代表每日的任意时刻，n代表一定范围的整数；
[0022]
根据通行时间路阻函数模型，如式(2)所示：
[0023][0024]
式中，r
t
为路段行程时间，f
t
为路段行程时间映射函数，t0为路段自由流行程时间，α,β为模型常量参数，c为路段实际通行能力；
[0025]
城市路网某一路段行程时间仅与该路段的实际车流量相关，故式(2)可以改写为：
[0026][0027]
城市路网某个具体路段在某天的任意时间段的行程时间，就可以通过前期的路面车辆信息采集设备统计车流量，并基于式(3)映射为该路段的行程时间。
[0028]
进一步的：若设车流量的时变周期为t，则城市路网某个路段行程时间也将按照周期t进行更新，建立城市路网路段行程时间的动态变化数据库，所述数据库反映了城市路网的行程时间的动态变化情况。
[0029]
进一步的：车辆从始发地开始，在起点就根据城市路网各个路段行程时间随着本次驾驶的行驶时间进程的动态变化，并基于动态变化的行程时间利用改进的 dijkstra算法进行全局最优路径规划。
[0030]
进一步的：将每条路段的行程时间按照时段进行区分，相邻时段的行程时间一般不同，车辆在经过该路段时若跨过两个及其以上的时段，则实际行程时间由各个不同时段的行程时间按照比例进行加权。
[0031]
进一步的：所述的全局最优路径规划，以dijkstra作为算法载体，新增跨时段路段的实际权值计算环节，计算车辆在每一个时段到达的最远位置所处的路段的实际权值。
[0032]
进一步的：所述的dijkstra算法，包括如下步骤：
[0033]
1)初始化
[0034]
设始发地的源节点为s，目的地的目标节点为t，di表示源节点s到节点i的最小累积权值，pi是到节点i所经过的路径节点集合，s表示最小累积权值已知的节点的集合，u为最小累积权值未知的点的集合；初始时刻，节点s的邻近子节点的权值di和路径pi可以读取路网数据直接得到，不相邻的节点最小累积权值设为∞；
[0035]
2)遍历未知节点集
[0036]
进入循环，在u中搜索距源节点s权值最小的节点k，将该点从u移到s 中，同时将该点k的权值和对应的路径分别存放到dk和pk中；
[0037]
3)比较更新邻近节点权值
[0038]
设节点k至邻近子节点j的路段权值与转向权值之和为w(k,j)，判断dk+w(k,j) 与dj的大小，更新s至j的最小权值dj和对应路径pj；
[0039]
判断路网权值是否更新；
[0040]
4)若至节点k的最小权值dk》t
·
t
num
，表明在到达节点k的路段将经历路网权值更新；
[0041]
5)计算临界节点对的实际累积权值
[0042]
将集合s中的所有临界父节点构成集合sc，将集合u中的所有临界子节点构成集合uc，进而组成临界节点对集c，计算临界节点对集的所有跨时段路段实际权值；之后更新时段编号t
num
，然后循环第2)步到第5)步，直到
[0043]
进一步的：设时段1和时段2相邻，时段1和时段2的行程时间分别为t1和 t2，车辆在该路段的时段1和时段2的行驶路程分别为s1和s2，则车辆经过该路段的总时间为：
[0044][0045]
总之，本发明考虑城市路网行程时间动态变化的全局最优路径规划方法，具有如下有益效果：
[0046]
1.本发明的基于动态行程时间的全局最优路径规划方法，首先提出了城市交通流的周期相似性规律，然后分析spp和rpp的缺陷，结合周期相似性规律提出了城市路网动态行程时间的全局最优路径规划方法，从始发地到目的地的行驶时间最短，进一步提高了汽车全局路径规划的智能性。
[0047]
2.本发明通过仿真验证模块，基于建立的重庆xx区域局部路网，分别利用 spp、rpp和gopp进行路径规划，验证了gopp在缩短行程时间方面的优越性。
[0048]
3、本发明通过获取城市路网的各个路段的车流量数据，再根据该路段的车流量数据映射为行程时间，获得该路段任意时间段的动态的行程时间；从车辆始发地开始，从车辆始发地开始，利用改进的dijkstra算法计算到目的地的所有路径中，将每一条路径的每个路段的行程时间相加，得到累计行驶时间最短的路径。
附图说明
[0049]
图1为本发明动态路网全局最优路径规划流程示意图；
[0050]
图2为某路段的车流量获取示意图；
[0051]
图3为实施例路网及三种路径规划思想示意图；
[0052]
图4为不同路径规划思想与起点的直线距离变化示意图；
[0053]
图5-1为原始dijkstra算法框图，图5-2为本发明改进dijkstra算法框图；
[0054]
图6为三种路径规划思想的仿真结果比较；
[0055]
图7为三种路径规划思想的d-t图。
具体实施方式
[0056]
为使本发明实施例的目的、技术方案和优点更加清楚，下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、完整地描述。显然，所描述的实施例是本发明一部分实施例，而不是全部的实施例。通常在此处附图中描述和示出的本发明实施例的组件可以以各种不同的配置来布置和设计。因此，以下对在附图中提供的本发明的实施例的详细描述并非旨在限制要求保护的本发明的范围，而是仅仅表示本发明的选定实施例。基于本发明中的实施例，本领域普通技术人员在没有作出创造性劳动前提下所获得的所有其他实施例，都属于本发明保护的范围。
[0057]
应注意到：相似的标号和字母在下面的附图中表示类似项，因此，一旦某一项在一个附图中被定义，则在随后的附图中不需要对其进行进一步定义和解释。在本发明的描述
中，需要说明的是，术语“中心”、“上”、“下”、“左”、“右”、“竖直”、“水平”、“内”、“外”等指示的方位或位置关系为基于附图所示的方位或位置关系，或者是该发明产品使用时惯常摆放的方位或位置关系，仅是为了便于描述本发明和简化描述，而不是指示或暗示所指的装置或元件必须具有特定的方位、以特定的方位构造和操作，因此不能理解为对本发明的限制。此外，术语“第一”、“第二”、“第三”等仅用于区分描述，而不能理解为指示或暗示相对重要性。此外，术语“水平”、“竖直”等术语并不表示要求部件绝对水平或悬垂，而是可以稍微倾斜。如“水平”仅仅是指其方向相对“竖直”而言更加水平，并不是表示该结构一定要完全水平，而是可以稍微倾斜。在本发明的描述中，还需要说明的是，除非另有明确的规定和限定，术语“设置”、“安装”、“相连”、“连接”应做广义理解，例如，可以是固定连接，也可以是可拆卸连接，或一体地连接；可以是机械连接，也可以是电连接；可以是直接相连，也可以通过中间媒介间接相连，可以是两个元件内部的连通。对于本领域的普通技术人员而言，可以具体情况理解上述术语在本发明中的具体含义。
[0058]
如图1至图7所示，本发明的考虑城市路网行程时间动态变化的全局最优路径规划方法，包括如下步骤：
[0059]
1、获取城市路网的各个路段在不同日期、不同时段的车流量数据；通过城市路网的路面车辆信息采集设备，如高清摄像头、雷达等，实时采集各个路段的车流量数据，将其传回数据中心，数据中心通过统计便可获得该路段在不同日期、不同时段的车流量数据；
[0060]
2、某个具体路段在某天的任意时间段的行程时间，通过该路段的车流量数据映射为行程时间，获得该路段任意时间段的动态的行程时间；本发明的车流量数据与行程时间的映射关系，具体采用下式：
[0061][0062]
其中，q代表某一路段的车流量，下标i代表周期w的编号，fq代表周期、日期、时刻与车流量的函数映射关系，t代表每日的任意时刻，n代表一定范围的整数；r
t
为路段行程时间，f
t
为路段行程时间映射函数，t0为路段自由流行程时间，α,β为模型常量参数，c为路段实际通行能力；
[0063]
3、车辆从始发地到目的地的全局最优路径规划，是在前述步骤2)获得城市路网每一个具体路段在本次行程预计通过的时间段的具体行程时间的前提下，从车辆始发地开始利用改进的dijkstra算法计算到目的地的所有路径中，将每一条路径的每个路段的行程时间相加，得到累计行程时间最短的路径。
[0064]
本发明在通过城市路网的路侧设备，如高清摄像头、雷达等，如图2所示，实时采集各个路段的车流量数据后，在不考虑节假日、临时突发重大交通事故的前提下，城市路网交通流(车流量)具有显著的周期性，简称周期相似性，如式 (1)所示：
[0065]
qi＝fq(wi,d,t)≈fq(wi+nw,d,t)
ꢀꢀꢀ
(1)
[0066]
式中，q代表某一路段的车流量，下标i代表周期w的编号，fq代表周期、
[0067]
日期、时刻与车流量的函数映射关系，t代表每日的任意时刻，n代表一定范围的整数。
[0068]
对式(1)简单举例理解，即为：本周二早上8时至9时某一路段的车流量，与上一周
二或者下一周二、早上8时至9时同一路段的车流量大致相等。这是通过大量数据统计、研究得出的城市交通自有规律。
[0069]
其次，美国联邦局曾于1964年提出了具有代表性的通行时间路阻函数模型，如式(2)所示：
[0070][0071]
式中，r
t
为路段行程时间，f
t
为路段行程时间映射函数，t0为路段自由流行程时间，α,β为模型常量参数，c为路段实际通行能力。
[0072]
式(2)表明当路段一定时，路段的实际通行能力和自由流行程时间即为常数，故城市路网某一路段行程时间仅与该路段的实际车流量相关。因此式(2)可以改写为：
[0073][0074]
其中，q代表某一路段的车流量，下标i代表周期w的编号，fq代表周期、
[0075]
日期、时刻与车流量的函数映射关系，t代表每日的任意时刻，n代表一定范围的整数；r
t
为路段行程时间，f
t
为路段行程时间映射函数，t0为路段自由流行程时间，α,β为模型常量参数，c为路段实际通行能力。综上，从统计学角度出发，可以认为城市路网的某个具体路段在某天的任意时间段的行程时间，是可以通过前期的城市路网的路面车辆信息采集设备，统计车流量并基于式(3)映射为该路段行程时间从而提前获知的。那么若设车流量的时变周期为t，则城市路网某个路段行程时间也将按照周期t进行更新，由此可以建立城市路网路段行程时间的动态变化数据库，这对车辆的全局路径规划具有重要意义。
[0076]
若设车流量的时变周期为t，则城市路网某一个具体路段行程时间也将按照周期t进行更新，建立城市路网路段行程时间的动态变化数据库，所述数据库反映了城市路网的行程时间的动态变化情况。
[0077]
车辆从始发地开始，在起点就根据城市路网各个路段行程时间随着本次驾驶的行驶时间进程的动态变化，并基于动态变化的行程时间利用改进的dijkstra算法进行全局最优路径规划。
[0078]
本发明建立城市路网路段行程时间的动态变化数据库，在城市路网的一定范
[0079]
围内，路网的路段行程时间的未来动态变化规律已知，车辆充分处理动态路段行程时间信息并规划一条到达目标点理论上满足全局最优的路径。
[0080]
本发明全局最优的路径并非一条基于车辆在起始点时刻的路网路段行程时间分布而计算的最短路径，也非一条车辆在行驶途中进行动态规划得到的拼接路径，而是在起点就充分考虑路网路段行程时间在未来的动态变化，并基于动态变化的行程时间利用改进的dijkstra算法进行全局最优路径规划。
[0081]
将每个路段的行程时间按照时段进行区分，相邻时段的行程时间一般不同，车辆在经过该路段时若跨过两个及其以上的时段，则实际行程时间应当由各个不同时段的行程时间按照比例进行加权。本发明所述的全局最优路径规划，以 dijkstra作为算法载体，新增跨时段路段的实际权值计算环节，计算车辆在每一个时段到达的最远位置所处的路段的
实际权值。
[0082]
设时段1和时段2相邻，时段1和时段2的行程时间分别为t1和t2，车辆在该路段的时段1和时段2的行驶路程分别为s1和s2，则车辆经过该路段的总时间为：
[0083][0084]
图1中，本发明涉及的模块，包括城市路网动态行程时间数据库模块、传统全局路径规划缺陷介绍模块、动态行程时间全局最优路径规划模块和仿真验证模块，其中的城市路网动态行程时间数据库模块，根据步骤1获取城市路网的各个路段在不同日期、不同时段的车流量数据；步骤2的某个具体路段在某天的任意时间段的行程时间，通过该路段的车流量数据并基于式(3)映射为行程时间，获得该路段动态的行程时间；就能够获得城市路网动态行程时间数据库模块。
[0085]
其中的传统全局路径规划缺陷介绍模块，如图3所示，该路网的路段行程时间以周期t动态更新，将每一个更新周期命名为一个时段，表1展示了两个相邻时段1和2的路段行程时间。假设当前车辆位于交叉口2，当前时刻t0处于时段1，目标交叉口为11，现探讨起讫点为(2,11)的传统路径规划规划思想。
[0086]
spp只考虑路网当前时刻的权值，根据时段1的权值分布计算得到的最优路径为2
→6→7→
11，如附图1实线路径所示。现假设车辆到达交叉口6的时刻恰好是时段1和时段2的临界时刻，路网权值随即更新为时段2的权值。则车辆在经过6
→7→
11时所耗费的行程时间应当参考时段2的权值分布，那么在时段1 规划的所谓“最优路径”也就无法证明在时段2是否继续保持最优。因此，spp 的路径是特定时域(时段1)的最优路径，无法实现在全时域保持最优。
[0087]
参考spp在交叉口2规划的实线路径，当车辆到达交叉口6时，路网权值发生更新。此时rpp根据时段2的权值立即重新规划剩余的道路网络的路径，计算发现虚线路线的累积权值小于实线路径的累积权值，因此将行驶路线更改为虚线路线。rpp的两次路径规划起点分别为交叉口1和交叉口6，对应的路径分别为2
→
6和6
→
10
→
11，路径规划的空域显然不同。因此，rpp的实际行驶路径是由特定空域中的局部最优路径拼接而成的，局部最优的叠加并非全局最优，故rpp无法实现在全空域保持最优。实际上，根据表1的权值变化通过计算可以证明图3点画线路径才是最优路径。三种路径规划思想的实际行程时间如表2 所示。
[0088]
表1 实施例路网的时变路段行程时间(单位：s)
[0089][0090]
表2 实施例路网的三条路径的实际行程时间(单位：s)
[0091][0092]
为更加直观的展示三种路径规划思想的区别，绘制三种路径规划思想的途径交叉口与起点的直线距离随时间变化的示意图，简称为d-t图，利用d-t图可以较直观的观察每一条路径所经过的交叉口与起点的直线距离随时间的变化关系，可以反映出不同路径的行程时间变化趋势，如图4所示。图4车辆从交叉口 2出发，随时间推移到达交叉口11。其中，spp_1表示车辆在交叉口2利用spp 思想规划路径计算得到的理想直线距离变化曲线，但由于车辆在交叉口6时路网权值更新，车辆继续按照spp路径行驶的实际直线距离变化曲线如spp_2所示。值得注意的是，点画线最优路径在时段1并未体现其优势，进入时段2却率先到达了目标点。
[0093]
其中的动态行程时间全局最优路径规划模块，如图4所示，分析图4可以发现，spp路径规划思想错过了点画线路径的原因是当车辆位于起始节点2时，认为路径2
→3→7→
11在时段1的行程时间较长，却忽略了路段3
→
7在时段2 的行程时间将变化到较小值；rpp路径规划思想错过了点画线路径的原因是当车辆位于节点6重新进行路径规划时，尽管车辆获知了路段3
→
7在本时段2的行程时间较短，但此时车辆已经位于节点6，路段3
→
7已经不再位于考察路段范围。
[0094]
为此欲在节点2就能计算出点画线路径的累积行程时间最短，需要将整个路网的时段1和时段2的行程时间权值进行综合分析，设想有三辆车同时从节点2 分别沿着实线、虚线及点画线路径行驶，那么在权值更新时刻，三辆车在路网的位置是确定的。这三处位置就代表了车辆在时段1的t0时刻从节点2向路网外围扩散的过程中，到达权值更新时刻时车辆在三条不同路径上能够到达的最远位置，这个最远位置通常位于路段上，而非恰好位于交叉口上。因此，对于任一动态路网，若车辆在起始点位于时段1，那么首先利用dijkstra算法基于时段1的权值可以计算车辆从起始点向外行驶能够到达的最远位置，在时段1已经遍历到的节点的路径是确定的、最优的；然后路网权值发生更新，进而在这些最远位置基于时段2的权值继续遍历余下未访问的节点，若时段2内还未遍历完整个路网，则基于时段3的权值继续遍历剩余节点，直到遍历完整个路网。
[0095]
综上所述，在路网的拓扑结构一定及权值更新周期规律已知的前提下，可以规划路网的全局最优路径，其关键是计算车辆在每一个时段到达的最远位置所处的路段的实际权值(行驶时间)。因此，本发明以dijkstra作为算法载体，融合上述全局最优路径规划思想，新增跨时段路段的实际权值(行驶时间)计算环节，对dijkstra算法进行适当改进，提出了基于dijkstra算法的全局最优路径规划思想，如图5所示。
[0096]
以图3的示例路网为例，介绍本发明全局最优路径规划思想，dijkstra算法包括5个步骤：
[0097]
①
初始化
[0098]
设源节点为s(始发地)，目标节点为t(目的地)，di表示源节点s到节点i 的最小累积权值，pi是到节点i所经过的路径节点集合。s表示最小累积权值已知的节点的集合，u为
最小累积权值未知的点的集合。初始时刻，节点s的邻近子节点的权值di和路径pi可以读取路网数据直接得到，不相邻的节点最小累积权值设为∞。在图3中，设源节点为1，目标节点为11，路网权值时变周期为t，时段编号为t
num
＝1，车辆在源节点1的时刻为t0，则t0+t
num
·
t为权值更新时刻。初始时刻s＝{1}，u＝{2,3,4,5,6,7,8,9,10,11,12}。节点2与节点1相邻，故d2可以获知，其余节点累积权值均为∞。
[0099]
②
遍历未知节点集
[0100]
进入循环，在u中搜索距源节点s权值最小的节点k，将该点从u移到s 中，同时将该点k的权值和对应的路径分别存放到dk和pk中。在第
①
步基础上，设集合u中节点2具有最小累积权值d2，故s＝{1,2}， u＝{3,4,5,6,7,8,9,10,11,12}。
[0101]
③
比较更新邻近节点权值。
[0102]
设节点k至邻近子节点j的路段权值与转向权值之和为w(k,j)，判断dk+w(k,j) 与dj的大小，更新s至j的最小权值dj和对应路径pj。在第
①
步基础上，节点2 的邻近节点包括3和6，由于节点3和6的累积权值为无穷大，故此时应当更新 d3和d6。传统dijkstra算法从第
①
步至第
③
步不断循环，直至便结束算法。本文所提出的全局最优路径规划算法新增跨时段路段的实际权值计算环节，该环节将判断路网权值是否更新并计算跨时段路段的实际权值，如图5虚线框所示，具体步骤如下第
④
、
⑤
步。
[0103]
④
判断路网权值是否更新。
[0104]
若至节点k的最小权值dk》t
·
t
num
，表明在到达节点k的路段将经历路网权值更新。在前三步基础上，设当前s＝{1,2,3,6}，u＝{4,5,7,8,9,10,11,12}，集合u 中节点10具有最小累积权值d
10
，且d
10
》t
·
t
num
，表明按照路径1
→2→6→
10经历了权值更新，且发生在路段6
→
10。我们定义节点6为临界父节点，节点10 为临界子节点，节点6与10共同构成临界节点对。
[0105]
⑤
计算临界节点对的实际累积权值。
[0106]
在第
④
步基础上，设临界路段6
→
10在时段1和时段2的权值分别为ω
6_10_1
和ω
6_10_2
，车辆在路段6
→
10于时段1的行驶路程比例r为：
[0107][0108]
则路径1
→2→6→
10的实际累积权值为：
[0109]d10
＝d6+r
·
ω
6_10_1
+(1-r)
·
ω
6_10_2
ꢀꢀꢀ
(5)
[0110]
据此将集合s中的所有临界父节点构成集合sc，将集合u中的所有临界子节点构成集合uc，进而组成临界节点对集c。参照式(4)与式(5)，可以计算临界节点对集的所有跨时段路段实际权值。之后更新时段编号t
num
，然后循环第(2)步到第
⑤
步，直到
[0111]
本发明的仿真验证模块，用于验证本发明的方法：
[0112]
利用vissim交通仿真软件预先建立重庆xx区域局部路网，并在路网输入不同车流量模拟不同时段的交通拥堵情况，并记录仿真得到的每条路段的平均行程时间等数据。以该路网的(12,209)作为仿真试验的起讫点，设车辆位于源节点12的时刻为早上8:17(即时段1起始时刻)，路网的权值将在8:30更新，利用dijkstra算法分别采用spp、rpp和全局最优路径规划三种思想进行路径规划，三种路径规划结果见图6和表3。上述仿真实验以(12,
209)作为起讫点，验证了gopp相比spp和rpp在实现全局最优路径规划方面的优越性。实际上，任意选择一组起讫点，spp、rpp及gopp的规划路径的累积行程时间的大小关系可以表达为：
[0113]
t
gopp
≤t
rpp
≤t
spp
ꢀꢀꢀ
(6)
[0114]
对式(6)的大小关系做进一步说明：
[0115]
①
当在动态路网中，选择的目标点位于本时段车辆能遍历的最远节点范围内(如图6的节点49在时段1便被遍历)，则有t
gopp
＝t
rpp
＝t
spp
；
[0116]
②
若在动态路网中，选择的目标点位于本时段车辆能遍历的最远节点范围外，即跨过 了时变周期(如图6的节点209在时段2才会被遍历)，rpp与全局最优路径规划的关系 需要进一步分析，但两者的累积时间必然小于spp，即t
gopp
＝t
rpp
＜t
spp
；
[0117]
③
若在动态路网中，选择的目标点位于本时段车辆能遍历的最远节点范围外，且剩余未遍历节点的若干路段在下一时段的权值存在变小的情况，可能存在到目标点权值最小的路径(如图6中，节点184向左的点画线路径在时段2权值变小，从184到达209的点画线路径累积行程时间，要小于从107到209的行程时间)，则有t
gopp
＜t
rpp
＜t
spp
。
[0118]
表3 重庆xx局部路网三条规划路径的累积行程时间
[0119][0120]
综上，基于dijkstra算法的gopp路径规划思想在行程时间动态变化的路网中能够规划全局最优路径，可以为驾驶员缩短交通出行时间，具有一定的实用价值。同时，这一性质可以推广到任意权值发生动态变化的路网中，如路段平均速度、能耗等。
[0121]
最后需要说明的是，本发明的上述实例仅仅是为说明本发明所作的举例，而并非是对本发明的实施方式的限定。尽管申请人参照较佳实施例对本发明进行了详细说明，对于所属领域的普通技术人员来说，在上述说明的基础上还可以做出其他不同形式的变化和变动。这里无法对所有的实施方式予以穷举。凡是属于本发明的技术方案所引申出的显而易见的变化或变动仍处于本发明的保护范围之列。
技术特征：1.考虑城市路网行程时间动态变化的全局最优路径规划方法，其特征在于包括如下步骤：1)获取城市路网的各个路段在不同日期、不同时段的车流量数据；2)城市路网中某一个具体路段在某天的任意时间段的行程时间，通过该路段的车流量数据映射为车辆在该时间段的行程时间，获得该路段任意时间段的动态的行程时间；3)车辆从始发地到目的地的全局最优路径规划，是在前述步骤2)获得城市路网每一个具体路段在本次行程预计通过的时间段的具体行程时间的前提下，从车辆始发地开始利用改进的dijkstra算法计算到目的地的所有路径中，将每一条路径的每个路段的行程时间相加，得到累计行程时间最短的路径。2.根据权利要求1所述的考虑城市路网行程时间动态变化的全局最优路径规划方法，其特征在于：步骤1)所述的获取城市路网的各个路段车流量数据，是通过城市路网的路面车辆信息采集设备，实时采集各个路段的车流量数据，将其传回数据中心，数据中心通过统计便可获得该路段在不同日期、不同时段的车流量数据。3.根据权利要求1所述的考虑城市路网行程时间动态变化的全局最优路径规划方法，其特征在于：所述某一个具体路段的车流量数据基于下式映射为行程时间，其中，q代表某一路段的车流量，下标i代表周期w的编号，f
q
代表周期、日期、时刻与车流量的函数映射关系，t代表每日的任意时刻，n代表一定范围的整数；r
t
为路段行程时间，f
t
为路段行程时间映射函数，t0为路段自由流行程时间，α,β为模型常量参数，c为路段实际通行能力。4.根据权利要求3所述的考虑城市路网行程时间动态变化的全局最优路径规划方法，其特征在于：实时采集各个路段的车流量数据后，在不考虑节假日、临时突发重大交通事故的前提下，城市路网车流量具有显著的周期性，简称周期相似性，如式(1)所示：q
i
＝f
q
(w
i
,d,t)≈f
q
(w
i
+nw,d,t)
ꢀꢀꢀ
(1)式中，q代表某一路段的车流量，下标i代表周期w的编号，f
q
代表周期、日期、时刻与车流量的函数映射关系，t代表每日的任意时刻，n代表一定范围的整数；根据通行时间路阻函数模型，如式(2)所示：式中，r
t
为路段行程时间，f
t
为路段行程时间映射函数，t0为路段自由流行程时间，α,β为模型常量参数，c为路段实际通行能力；城市路网某一个具体路段行程时间仅与该路段的实际车流量相关，故式(2)可以改写为：
城市路网某一个具体路段在某天的任意时间段的行程时间，就可以通过前期的路面车辆信息采集设备统计车流量，并基于式(3)映射为该路段的行程时间。5.根据权利要求4所述的考虑城市路网行程时间动态变化的全局最优路径规划方法，其特征在于：若设车流量的时变周期为t，则城市路网某一个具体路段行程时间也将按照周期t进行更新，建立城市路网路段行程时间的动态变化数据库，所述数据库反映了城市路网的行程时间的动态变化情况。6.根据权利要求1—5任一所述的考虑城市路网行程时间动态变化的全局最优路径规划方法，其特征在于：车辆从始发地开始，在起点就根据城市路网各个路段行程时间随着本次驾驶的行驶时间进程的动态变化，并基于动态变化的行程时间利用改进的dijkstra算法进行全局最优路径规划。7.根据权利要求1—5任一所述的考虑城市路网行程时间动态变化的全局最优路径规划方法，其特征在于：将每条路段的行程时间按照时段进行区分，相邻时段的行程时间一般不同，车辆在经过该路段时若跨过两个及其以上的时段，则实际行程时间由各个不同时段的行程时间按照比例进行加权。8.根据权利要求1—5任一所述的考虑城市路网行程时间动态变化的全局最优路径规划方法，其特征在于：所述的全局最优路径规划，以dijkstra作为算法载体，新增跨时段路段的实际权值计算环节，计算车辆在每一个时段到达的最远位置所处的路段的实际权值。9.根据权利要求1—4任一所述的考虑城市路网行程时间动态变化的全局最优路径规划方法，其特征在于：所述的dijkstra算法，包括如下步骤：1)初始化设始发地的源节点为s，目的地的目标节点为t，di表示源节点s到节点i的最小累积权值，pi是到节点i所经过的路径节点集合，s表示最小累积权值已知的节点的集合，u为最小累积权值未知的点的集合；初始时刻，节点s的邻近子节点的权值d
i
和路径p
i
可以读取路网数据直接得到，不相邻的节点最小累积权值设为∞；2)遍历未知节点集进入循环，在u中搜索距源节点s权值最小的节点k，将该点从u移到s中，同时将该点k的权值和对应的路径分别存放到d
k
和p
k
中；3)比较更新邻近节点权值设节点k至邻近子节点j的路段权值与转向权值之和为w(k,j)，判断d
k
+w(k,j)与d
j
的大小，更新s至j的最小权值d
j
和对应路径p
j
；4)判断路网权值是否更新；若至节点k的最小权值d
k
>t
·
t
num
，表明在到达节点k的路段将经历路网权值更新；5)计算临界节点对的实际累积权值将集合s中的所有临界父节点构成集合s
c
，将集合u中的所有临界子节点构成集合u
c
，进而组成临界节点对集c，计算临界节点对集的所有跨时段路段实际权值；之后更新时段编号t
num
，然后循环第2)步到第5)步，直到10.根据权利要求7所述的考虑城市路网行程时间动态变化的全局最优路径规划方法，其特征在于：设时段1和时段2相邻，时段1和时段2的行程时间分别为t1和t2，车辆在该路段的时段1和时段2的行驶路程分别为s1和s2，则车辆经过该路段的总时间为：
。
技术总结本发明公开了考虑城市路网行程时间动态变化的全局最优路径规划方法，1）获取城市路网的各个路段的车流量数据；2）通过该路段的车流量数据并基于映射关系式，得到该路段任意时间段的动态的行程时间，并构建变化数据库；3）在提前获知路网未来路段行程时间动态变化规律的前提下，改进传统Dijkstra算法，动态计算到目的地途中可能行驶的每一条路径的每个路段的累积行程时间，进而规划全局行程时间最短路径。本发明通过获取车流量数据，再根据该路段的车流量数据映射为行程时间；从车辆始发地开始，利用改进的Dijkstra算法动态计算到目的地途中可能行驶的每一条路径的每个路段的行程时间，得到动态的最短行驶时间，优化了从始发地到目的地的全程行驶路线。地到目的地的全程行驶路线。地到目的地的全程行驶路线。
技术研发人员：黎万洪 孙正海 邱利宏 周增碧
受保护的技术使用者：重庆长安汽车股份有限公司
技术研发日：2022.06.16
技术公布日：2022/11/1
