中心控制式车载导航系统两阶段多路径优化方法

摘要

本发明属载导航系统路线优化领域。目前动态多路径优选存在高精度实时信息的获取、路径计算实时性、有约束多路径计算问题。本发明包括以下步骤：建立双参数的道路单元准动态属性文件；考虑路径合理性约束及共同失效约束，利用启发式加权的方法离线建立备选路径集合；改善A＊的启发式函数提高备选路集建立的效率，该路集满足用户喜好约束及共同失效约束；离线备选路集编码式存储及在线回溯；在线动态路径筛选、补充搜索及多路径发布。该发明提高了基于历史信息的备选路径的合理性及在线有效性，减少了在线路径搜索的工作量，有利于实现系统最优与用户最优的协调。

主权项

1、一种中心控制式车载导航系统两阶段多路径优化方法，其特征在于，包括以下步骤：第一阶段：离线阶段(1)标定双参数的道路单元属性文件将一天划分为t个典型时段，t＞＝3；下面的操作是针对其中任何一个典型时段进行的，其它时段的操作方法相同；历史信息被处理与提炼成两种参数形式服务于导航算法：一是各典型时段的道路单元平均通行时间，一是各典型时段道路单元的畅通可靠度；道路单元一般包括路段和交叉口；利用现有技术将路网转化为弧权网络，即将路口各转向用虚拟路段表示，各转向延误时间即虚拟路段的通行时间；在交叉口拥挤不严重的路网，也可不考虑交叉口的延误，仅考虑路段通行时间；从而路网道路单元可仅指路段单元；对每个道路单元进行各典型时段平均通行时间及畅通可靠度双参数的标定，其中建立道路单元平均通行时间，采用以下方法：对于具有一个月以上交通流历史数据的道路单元，用统计方法计算道路单元i在畅通条件下某一时段内的平均通行时间，这个平均通行时间就是道路单元i的权重w_i；对于没有一个月以上的交通流历史数据的路段，可以路段长度除以路段设计速度作为道路单元i的权重w_i；其中确定道路单元畅通可靠度要经过两个过程：a.对道路单元做二元状态假设：即将道路单元的状态分为两种：畅通和阻塞；区分路段畅通和阻塞的界限是提前设定的路段单元行驶速度阈值，大于这个值则视为畅通，小于这个值则视为阻塞；而区分交叉口各转向畅通和阻塞的界限则是提前设定的交叉口延误阈值；小于这个值则视为畅通，大于这个值则视为阻塞；以上阈值可根据交通部畅通工程标准制定；b.确定道路单元的畅通可靠度，道路单元的畅通可靠度可以定义为在规定的时间段内道路单元畅通或不发生阻塞的概率；其确定方法如下：对道路单元采集3个月以上的交通流数据，采用下式计算道路单元i畅通可靠度r_i的近似值：(2)建立备选路径集1)令Q为整个路网的总起讫点对数，对所有起讫点对，初始化其备选路集S_n＝φ，n表示Q中的第n个起讫点对，n＝1，2，3……Q；以各道路单元正常条件下的通行时间为路权，对所有点对用传统Dijkstra算法计算最短路P_n，1，进而计算其权重和为L_n，1，即为路径P_n，1的通行时间；将P_n，1存入第n个起讫点对的备选路集S_n，作为第一条备选路径；初始化所有起讫点对的备选路径条数K_n＝1；令n＝1，即对第一个起讫点对进行计算；2)对第n个起讫对，初始化迭代数m＝0；3)对路网上可靠度较低的道路单元，建议取r_i＜0.5-0.9，和S_n中已有路径上的每个道路单元增加权重Δw_i，令新一轮道路单元权重w_i’为：              w_i’＝w_i+Δw_i＝w_i+α^m(1-r_i)^qW₀              (2)式中，w_i为单元平均通行时间路权，当m＝0时，q＝0，否则q＝1；α为松弛因子，0＜α＜1，α越大该道路单元被包括在新路径里的可能性越小，相反α越小该单元被包括在新路径里的可能性越大；W₀为一较大正数，建议取W₀＝1.5L_n，1～3L_n，1；4)令新一轮备选路径数K_n′＝K_n+1，新一轮迭代次数m′＝m+1，m＝m′，以w_i’为路权，用现有A^*算法计算最短路P_n，Kn，K_n＝K’_n，将路权恢复为w_i，重新计算L_n，Kn，L_n，Kn为P_n，Kn上的路权w_i之和；5)如果P_n，Kn违反了合理路径约束条件L_n，Kn＜βL_n，1则K_n′＝K_n-1，转到3)；β为允许系数，一般与用户自身的意愿有关，β越大新路径用户绕行越长，相反β越小用户绕行越短，建议取1.0-1.5；否则将P_n，Kn存入S_n；6)如果N’＜K_n＜N，N为最大的备选路径数，N’为最小的备选路径条数，则返回3)；7)如果整个路网的起讫点对全部计算完则结束，否则返回步骤2)计算第n+1个起讫点对，直到所有Q个起讫点对都计算完结束；(3)离线编码存储备选路集其中对于备选路集中的最短路，本发明对每个起讫点对间的最短路，假设起点为s，终点为t，中间节点为m₁，m₂，…m_n，采用如下编码记录该条路：<终点编号t，紧邻起点的下一节点编号m₁，最短路长>对于非最短路的其他备选路径，则不能用此编码形式，可采用现有技术进行路径全信息存储；第二阶段：在线阶段(2.1)备选路径在线回溯利用现有路径回溯方法对路径进行在线回溯，对于备选路径中的最短路，根据用户的需求，先找到起终点对，即先找到起点s，然后在所有该起点的编码表中找到终点t，随后由该编码找到紧邻起点的下一节点m₁，进而将m₁作为新的起点，在m₁的编码表中找到终点t的编码，然后找到紧邻新起点m₁的第二个下一个节点m₂，再以m₂为新的起点，依次类推，直到下一个节点为终点停止，将这些节点依次记录便得到了最短路；对于备选路径中的非最短路，则按储存的所有节点编号按从起点到终点的顺序回溯；(2.2)在线动态路径筛选、补充搜索及多路径发布在线时可根据动态交通信息进行路径筛选，即删去备选路径中发生阻塞延误的路径，进而将剩余备选路径对各导航车辆进行随机路径发布，当在线没有可用的备选路径或没有足够数量的可用备选路径用于避免群聚现象时，可根据实时交通信息重新利用建立备选路径集算法重新搜寻路径在线发布，算法结束。