一种基于进化树拓扑路网构建的路径规划确定方法

摘要

一种基于进化树拓扑路网构建的路径规划确定方法，包括获取城市完全路网数据，应用邻接矩阵方法构造表示原始地理信息的路网全连通图G；将路网全连通图G归类划分为二叉路网拓扑进化树；获取包含所有目标结点的最小分支树；对于包含所有路径规划问题中目标结点的最小分支树采用分支定界搜索策略消除无效分支结点，减小关联矩阵维度，获得规划结果。本发明的有益效果主要表现在：本发明优化了路径规划过程的算法复杂度，提高了路径规划的效率。

主权项

1.一种基于进化树拓扑路网构建的路径规划确定方法，包括以下步骤：1）、获取城市完全路网数据，应用邻接矩阵方法构造表示原始地理信息的路网全连通图G，将路网结点抽象为路网全连通图G中的结点v_i，而路网结点间的路网可达性抽象为路网全连通图G中的边e_i的连通性，路网全连通图G={V,E}，其中V(G)={v₁,v₂,…v_n}为结点集,n表示结点个数；E(G)={e₁,e₂,…e_m}表示各路网结点之间边的集合，其中m表示边的条数，则有m=n×(n-1)/2；边权矩阵D表示路网全连通图G各结点之间的权值：其中w_ij表示结点v_i、v_j间路网可达距离；D_ij表示边权矩阵D的元素；2）、将路网全连通图G归类划分为二叉路网拓扑进化树；2.1）、将路网全连通图G抽象为一个以抽象连接点为连接点的星型树，路网全连通图中的结点形成星型树的实际结点，实际结点与抽象连接点连接；路网全连通图G中的任意两个结点v_i和v_j之间的权值d_ij表示为抽象星型树中两结点的抽象边权之和，d_ij=L_iX+L_jX，其中L_iX表示所述结点v_i到X之间的抽象边权，L_jX表示所述结点v_j到抽象连接点X之间的抽象边权；2.2）、获取表征星型树中的任意两个结点和之间邻接关系的邻接值S_ij，其中$v_i^{\prime },v_j^{\prime }\in V\left(G\right)$且i≠j；$S_{\mathrm{ij}}=\frac{{\Sigma }_{k\ne i,j}^n{D}_{\mathrm{ik}}+D_{\mathrm{jk}}}{2(n-2)}+\frac{D_{\mathrm{ij}}}{2}+\frac{{\Sigma }_{k,l\ne i,j}^n{D}_{\mathrm{kl}}}{n-2};$2.3）、在每一组邻接值计算结果集中，选择邻接值最小的结点对作为最佳邻接对保留，将每一对邻接结点对合并为虚拟结点插入结点集合中，进行拓扑重构获得二叉路网拓扑进化树；3）、依据路网结点间的邻接值，对路网全连通图进行分类划分、构建进化树拓扑路网，针对线路路径寻优问题，采用进行动态回溯方法对路径规划问题中线路路径寻优的目标结点进行分类，获取包含所有目标结点的最小分支树；4）、对于包含所有路径规划问题中目标结点的最小分支树采用分支定界搜索策略消除无效分支结点，减小关联矩阵维度，之后针对消除无效分支结点之后的包含目标结点的最小分支树进行路径规划分析，获得线路路径寻优结果；路径规划分析过程如下：4.1）.路网拓扑重构，将整个路网按照邻接关系进行拓扑重构，最终形成以邻接关系为表现特征的路网拓扑进化树Tree；4.2）.根据停靠站点集合V=(v₁,v₂，…v_n)，采用动态回溯分类策略，在Tree中寻找最小分支树B-Tree，满足条件：4.3）.对于包含(v₁,v₂,…v_n)的最小分支树B-Tree，遵循分支定界优化策略，获取依据邻接关系判定各停靠结点访问先后的巡游顺序(v_π1，v_π2，…v_πn)并输出；4.4）.同时对步骤4.3）所获取的序列应用动态规划策略进行局部调整，即将(v₁,v₂，…v_n)中位于B-Tree同一分支树的结点与其他结点分离开来，对限制范围内结点应用动态规划进行精确求解，之后与其他结点以相互邻接关系合并，得到最优解。