专利名称：一种基于进化树拓扑路网构建的路径规划确定方法
技术领域：
本发明涉及一种地理信息数据处理、计算机应用领域，尤其涉及的是，一种基于进化树拓扑路网构建的路径规划方法。
背景技术：
针对具有连通性质停靠站点的实际城市路网，如何在多项式时间内求解多停靠站点网络路径优化问题，是智能交通系统的一个关键研究问题。目前多数网络路径规划问题普遍采用以最小K值法、动态规划等精确算法或者遗传算法、蚁群算法等启发式算法为主的优化算法求解。其中，^ian等首次实现了实际交通路网条件下的路径寻优算法，但是其采用的传统D算法进行线路搜索，对于小规模结点的计算结果非常准确，而对于大规模网络结点所需要的计算时耗是无法接受的。Jagadees等提出一种结点提升分层优化算法，能够保证算法在较短时间内获得最短路径，但其属于一种基于路网结点规模限制的算法，仅适合结点数固定的网络，对于现实结点个数的不确定性使得该算法无法普遍应用。Yanns等提出一种求解路径优化问题的混合启发性算法，有机结合了粒子群优化算法、多阶段领域搜索、随机自适应贪婪、扩展的领域搜索算法以及路径重新连接技术。刘菲等提出了一种基于加强基因突变解决网路路径优化问题，由于其初始种群仅有一个，无法避免遗传算法中普遍存在的早期收敛现象，也不能保证子代种群的多样性。景玲等提出了基于特定有序、选择、交叉、遗传算子路径诱导算法，而该算法对于初始种群的质量依赖性过高，如果初始化种群质量较差，则很容易陷入局部最优解。因此，现有的技术在针对实际路网中的路径规划方面存在着缺陷，需要改进。

发明内容
为了克服已有的实际路网路径规划方法的模型求解规模限制、计算速度慢的不足，本发明提供一种路径规划模型合理、快速性良好的基于进化树拓扑路网构建的路径规划确定方法。本发明解决其技术问题所采用的技术方案是
一种基于进化树拓扑路网构建的路径规划确定方法，包括以下步骤 1)、获取城市完全路网数据，应用邻接矩阵方法构造表示原始地理信息的路网全连通图^，将路网结点抽象为全连通图
G中的结点巧，而路网结点间的路网可达性抽象为全连通图G 中的边A的连通性，全连通
图σ={Γ，5},其中r={Vl，V2,...Vs丨为结点集，《表示结点个数；s = ... }表示各路
网结点之间边的集合，m表示边的条数，则有《 = nx{n-\)j2边权矩阵D表示全联通图“ 各结点之间边权值
权利要求
1.一种基于进化树拓扑路网构建的路径规划确定方法，包括以下步骤1)、获取城市完全路网数据，应用邻接矩阵方法构造表示原始地理信息的路网全连通图^将路网结点抽象为全连通图3中的结点々，而路网结点间的路网可达性抽象为全连通图G中的边&的连通性，全连通图 0 =化对，其中「=丨^...%}为结点集，《表示结点个数；5 = — 表示各路网结点之间边的集合，m表示边的条数，则有《 = η An-1)/2边权矩阵D表示全联通四各结点之间边权值—J、CvjjVj-ED 「1Λ其他其中、J表亍四中结点标号，表示结点巧、々间路网可达距离；为边权矩阵D的元素，表示连接结点巧、力的边权值；2)、将路网全连通图G归类划分为二叉路网拓扑进化树；2.1)、将路网全连通图G抽象为一个以抽象连接点为连接点的星型树，全连通图中的结点形成星型树的实际结点，实际结点之间通过抽象连接点连接；全连通图G中的任意两个结点Vi和、之间的权值Dtf表示为抽象星型树中两结点的抽象边权之和， = Lix + Lix ,其中表示星型树中结点巧到X之间的抽象边权，Ljz表示星型树中结点 到抽象连接点X之间的抽象边权,i、J表示四中结点标号；2. 2)、获取表征星型树中的任意两个结点Vi和 之间邻接关系的邻接值& ,其中t v/ € F且# J , Aa表示结点巧与结点h间边权值，%表示结点&与结点&间边权值，表示结点与结点间边权值；在.= 2j^a ；DuVi2(μ 2)222. 3)、在每一组邻接值计算结果集中，选择邻接值最小的结点对作为最佳邻接对保留， 将每一对邻接结点对合并为虚拟结点插入结点集合中，进行拓扑重构获得二叉路网拓扑进化树；3)、依据路网结点间的邻接值，对路网全连通图进行分类划分、构建进化树拓扑路网， 针对线路路径寻优问题，采用进行动态回溯方法对路径规划问题中线路路径寻优的目标结点进行分类，获取包含所有目标结点的最小分支树；4)、对于包含所有路径规划问题中目标结点的最小分支树采用分支定界搜索策略消除无效分支结点，减小关联矩阵维度，在此基础之上进行路径规划分析，获得规划结果。
2.如权利要求1所述的基于进化树拓扑路网构建的路径规划确定方法，其特征在于 所述步骤3)中，构建进化树拓扑路网采用上文结点间邻接值计算方法，按照邻接值最小策略，构建拓扑进化树Γγμ，包括以下步骤·3.1. 1 )、令G= {V，EJ，边权矩阵D =[、],初始进化树；.3. 1. 2)、选择任意结点Vj、Vj e K,对V Ki, ^，计算Vj，Vj的邻接值5；7 ； 3. 1. 3)、寻找结点 vm、vn，使得 vm、vn 的邻接值 lMi/ CSjj), vm, vn e V (G)；其中，vm,vn 表示路网全连通图G中的任意两个结点；.3. 1.4)、将步骤3. 1.3)中得到的 …合并为新结点Lf即v,\J Vn'V=V-i VG} + { Vm_n }，按照邻接关系，将父结点K”、子结点&、子结点Vn插入Γ卿中； 3. 1.5)、若K中元素个数为1，算法结束，否则转步骤3. 1.2)。
3.如权利要求2所述的基于进化树拓扑路网构建的路径规划确定方法，其特征在于 所述步骤A3中，采用动态回溯策略对目标结点进行分类包括以下步骤.3. 2. 1)、获取目标结点力、Vij，分别获取结点r,位于拓扑进化树所在层次标号，和结点I位于拓扑进化树所在层次标号；.3. 2. 2)、判断义和 是否拥有同一父结点，若是，则获取共同父结点和该父结点的所有子结点；若否，则获取所在层大的目标结点作为回溯结点，获取回溯结点的直系父结点， 将该直系父结点作为新的目标结点，重复步骤3. 2. 1)；.3.2. 3)、以两个目标结点的共同父结点及其所有子结点形成的树作为最小分类树。
4.如权利要求3所述的基于进化树拓扑路网构建的路径规划确定方法，其特征在于 所述步骤4)中，对目标结点的最小分支数采用分支定界搜索策略包括以下规则规则1、获取所在层大的目标结点，以该所在层大的目标结点的直系父结点或直系子结点作为途径结点，所有的目标结点和该途径结点形成关联结点集合；将该途径结点取代与其有直系关系的目标结点作为新的目标结点；规则2、判断新的目标结点是否由邻接结点对合并而成的虚拟结点，若是则以与目标结点的邻接值最小的非虚拟结点替换；判断新的目标结点的父结点或子结点是否虚拟结点，若是，则以其非虚拟结点的兄弟结点替代；规则3、判断两目标结点在路网拓扑进化树中是否位于同一层且具有兄弟邻接关系，若是，则以与最近邻接结点的邻接值判断先后顺序；所述的最近邻接点是指距离目标结点邻接值最小的为结点；规则4、每一层只选择一个途径结点，忽略同层其他分支。
全文摘要
一种基于进化树拓扑路网构建的路径规划确定方法，包括获取城市完全路网数据，应用邻接矩阵方法构造表示原始地理信息的路网全连通图G；将路网全连通图G归类划分为二叉路网拓扑进化树；获取包含所有目标结点的最小分支树；对于包含所有路径规划问题中目标结点的最小分支树采用分支定界搜索策略消除无效分支结点，减小关联矩阵维度，获得规划结果。本发明的有益效果主要表现在本发明优化了路径规划过程的算法复杂度，提高了路径规划的效率。
文档编号G01C21/34GK102175256SQ20101060677
公开日2011年9月7日 申请日期2010年12月27日 优先权日2010年12月27日
发明者何洋军, 俞立, 吴海涛, 张贵军, 洪榛, 郭海峰, 金媚媚 申请人:浙江工业大学