延误风险规避的车载导航系统准动态路线优化方法

摘要

本发明涉及车载导航系统路线优化领域。现有问题：实时信息的获取及低成本传输；导航实时性；用户多目标要求，用户最优与系统最优。本发明步骤：确定道路单元平均通行时间、畅通可靠度、失效相关性数据，应用上述数据采用有约束的A*路径搜索算法，或者改进了A*算法中启发式函数的路径搜索算法；然后当事故等发生在已规划路径上时，执行存在有限的实时交通信息的A*路径搜索算法：否则结束。本发明在没有实时信息或仅有有限的实时信息条件下，考虑通行时间及阻塞风险双目标。本发明实时反应速度快，可不必依赖完全的动态信息，减少出行延误风险，并可对紧急事件做出实时反应；同时通过多路径规划及信息发布，有利于实现系统最优与用户最优的协调。

主权项

1、一种延误风险规避的车载导航系统准动态路线优化方法，其特征在于，包括以下步骤：1.标定双参数的道路单元属性文件将一天划分为n，n≥3个典型时段；下面的操作是针对其中任何一个典型时段进行的，其它时段的操作方法相同；确定三种服务于导航算法的数据：一是各典型时段的道路单元平均通行时间；一是各典型时段道路单元发生阻塞的可能性，即道路单元的畅通可靠度；一是各典型时段的道路单元间的失效相关性；其中确定道路单元畅通可靠度要经过两个过程：a.对道路单元做二元状态假设：即将道路单元的状态分为两种：正常和异常；道路单元包括路段和交叉口两部分，区分路段正常和异常的界限是提前设定的路段单元行驶速度阈值，大于这个值则视为表现正常，小于这个值则视为表现异常；而区分交叉口正常和异常的界限则是提前设定的平均交叉口延误阈值；小于这个值则视为表现正常，大于这个值则视为异常；b.确定道路单元的畅通可靠度，道路单元的畅通可靠度可以定义为在规定的时间段内路段不发生异常延误，或行驶速度低于一定的界限的概率；当具有3个月以上的交通流数据时，采用下式计算单元畅通可靠度的近似值；道路单元i畅通可靠度r_i表示为：在判断道路单元畅通与否时，路段采用车速为衡量标准，交叉口采用停车延误为衡量标准，至于衡量标准可参见相关方面的文献；当不具有3个月以上的交通流数据时，可以通过函数f(v_i/c_i)近似的估算，函数的具体形式由回归可以确定，方法是：首先，以v_i/c_i为自变量，可靠度为因变量做散点图，然后根据散点图的形状进行曲线拟合，最后在拟合出的曲线中，选择最合理的为具体的函数表达式；v_i/c_i——定义为道路单元i的饱和度，其中v_i为通过道路单元i的流量，可通过短期内交通流数据得到，c_i为单元i的通行能力，根据道路类型和等级不同而不同，是一个定值，可通过相关文献查得；其中建立道路单元平均通行时间，采用以下方法：对于具有一个月以上交通流数据的道路单元，用统计方法在计算道路单元i正常条件下在某一时段内的平均行驶时间，这个平均行驶时间就是道路单元i的权重w_i；对于那些没有一个月以上的交通流数据时，对于路段根据历史起讫点信息，也就是O-D信息，利用交通规划理论中传统交通分配方法对一天内不同时段的O-D矩阵进行分配，根据分配所得到的路段i上的交通量，从而根据交通流理论中交通量与速度的关系计算其行驶速度，然后用路段i的长度除以该路段的行驶速度，进而求出各路段的通行时间，这个平均行驶时间就是路段单元i的权重w_i；对于交叉口，根据交叉口类型，假定其平均行驶时间近似的同有一个月以上交通流数据的同类交叉口相同；其中确定道路单元间的失效相关性方法如下：当有交通事故发生在某道路单元上时，与其相邻的其他道路单元也会因受到影响而发生异常变化，将此现象称为道路单元间的失效相关性；确定道路单元间的失效相关性通过两种手段：一是根据历史交通信息分析出各道路单元间的失效相关性，一是利用现有的交通仿真技术，令某一路段产生阻塞，从而分析其他路段的运行速度与阻塞路段之间的关系；然后将道路单元间的失效相关性数据存储在车载光盘上；2.改进的A*路径搜索算法改进的A*路径搜索算法分为两种：一种是有约束的A*路径搜索算法，一种是改进了A*算法中启发式函数的路径搜索算法；其中有约束的现有A*路径搜索算法如下：1)在某一个典型时段内，令迭代次数k＝0，以w_i为道路单元i的权重，通过现有A*算法找到具有最小权重的路径P_s，0，进行计算P_s，0行程时间为L_s，0；2)通过对道路单元i的可靠度r_i进行分析，对路网上可靠度比较低的道路单元i，建议取r_i＜0.5的道路单元，增加一个权重增量Δw_i；增加后权重w_i’＝w_i+Δw_i＝w_i+α^k(1-r_i)^qW₀    (2)α为权重增加系数0＜α＜1.r_i为道路单元i的可靠度，建议取W₀＝1.5L_s，0~3L_s，0；当k＝0时，判别指数q＝0，k＞＝1时，判别指数q＝1；3)计算可靠路径：令新一轮迭代次数k’＝k+1，以w_i’为道路单元i的新权重，用现有A*算法计算权重最小的路径P_s，k’，将其上面的道路单元i的权重恢复为w_i，计算L_s，k’，也就是路径P_s，k’上的各道路单元路权w_i总和；4)检查路径约束条件：如果所得路径满足时间限制L_s，k’＜βL_s，0，则转到5)，否则回到2)；β为允许系数，建议取1.0-1.5；5)有约束的现有A*路径搜索算法结束；其中改进了A*算法中启发式函数的路径搜索算法如下：在运用A*算法时，路网中每个节点n，其权重f(n)＝g(n)+h(n)，这里g(n)指从起点到节点n的最短路长，h(n)指节点n到目的地最短路长的估计函数；从而g(n)指从起点到目的地最短路长估计函数。在现有A*算法中，还要用到两个表，也就是关闭表(close list)和开放表(open list)；已经计算和检查过的节点被放在关闭表里，计算过而没有被检查过的节点放在开放表里；(1)在某一个典型时段内，令迭代次数k＝0，以w_i为道路单元i的权重，在运用现有的A*算法计算最短路时，按从终点到起点的搜索顺序计算起终点间的通行时间最短路径，对搜索过程中的各道路单元i路权用其反向路权w_j；对于搜索过程中已经放在关闭表中的节点n，储存其节点n到终点的最短通行时间值为g(n)’，最终搜索所得最短路实际上为从起点到终点具有最小权重的路径P_s，0，进而计算P_s，0行程时间为L_s，0，即组成P_s，0的各道路单元的权重和；(2)通过对道路单元i的可靠度r_i进行分析，对于可靠度较低道路单元i，建议取r_i＜0.5，增加一个权重增量Δw_i；增加后权重w_i’＝w_i+Δw_i＝w_i+α^k(1-r_i)^qW₀     (3)α为权重增加系数0＜α＜1.r_i为道路i的可靠度，建议取W₀＝1.5L_s，0~3L_s，0；当k＝0时，判别指数q＝0；k＞＝1时，判别指数q＝1；(3)令新一轮迭代次数k’＝k+1，以w_i’为道路i的新权重，用现有A*算法按从起点到终点的搜索顺序，进行路权改变后的路径重新计算；对于计算过程中已放到关闭表中的节点，利用(1)中现有A*反向搜索的g(n)’，令其代替h(n)值；对于那些没在关闭表里的节点，用从起点到终点的欧几里德距离除以道路单元的设计速度作为h(n)，道路单元的设计速度可参见交通工程书籍，从而计算出权重最小的路径P_s，k’，将其上面的道路i的权重恢复为w_i，计算L_s，k’，也就是路径P_s，k’，上的各道路单元路权w_i总和；(4)检查路径约束条件：如果所得路径满足时间限制L_s，k’＜βL_s，0，，则转到(5)，否则回到(2)；β允许系数，建议取1.0-1.5；(5)改进了A*算法中启发式函数的路径搜索算法结束；3、当有交通信息如事故、阻塞、施工占路等发生在已规划路径上时，执行存在有限的实时交通信息的A*路径搜索算法：否则结束；存在有限的实时交通信息的A*路径搜索算法如下：[1]初始化：令迭代次数k＝0，当动态交通信息显示在规划出的路线上有异常阻塞，需要重新规划路线时，令道路单元i的估算行驶时间为道路单元的权重w_i[2]道路单元权重改变对于可靠度较低的道路单元，建议取r_i＜0.5，及事故道路单元和其相关道路单元，将它们的权重增加权重增量Δw，对于道路单元i，增加后权重w_i’＝w_i+Δw_i＝w_i+α^k(1-r_i)^qw₀     (4)α为权得增加系数0＜α＜1.r_i为道路单元i的可靠度，建议取W₀＝1.5L_s，0~3L_s，0；当迭代次数k＝0时，q＝0；k＞＝1时，q＝1；对于事故道路单元i，令道路单元i的可靠度r_i＝0，所以w_i’＝w_i+α^kW₀，0＜α＜1；此时搜索存储在车载光盘上的道路单元间失效相关性数据，找到与阻塞道路单元i相关的道路单元；如果道路单元j由于道路单元i发生异常阻塞，也随之发生阻塞时，称为正相关，令道路单元j的可靠度r_i＝0，所以w_i’＝w_i+α^kW₀，0＜α＜1；如果道路单元j由于道路单元i发生异常阻塞，运行状态反而改善时，称为负相关，令道路单元j的可靠度r_j＝1，所以w_j’＝w_j；如果道路单元j的运行状态不受道路单元i发生异常阻塞的影响时，称为不相关，其权重不变；[3]新一轮迭代次数k’＝k+1，以改变后的权重用现有A*算法重新计算权重最小路径P_s，k’，然后还原道路单元到之前事故道路单元行驶时间的估计值w_i，并计算L_s，k’；[4]路径检查如果P_s，k’满足限制条件，也就是L_s，k’＜βL_s，0，转向[5]，否则，返回[2]；[5]算法结束。