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

1.一种基于进化树拓扑路网构建的路径规划确定方法，包括以下步骤：
1）、获取城市完全路网数据，应用邻接矩阵方法构造表示原始地理信息的路网全连通图G，将路网结点抽象为路网全连通图G中的结点vi，而路网结点间的路网可达性抽象为路网全连通图G中的边ei的连通性，路网全连通图G={V,E}，其中V(G)={v1,v2,…vn}为结点集,n表示结点个数；E(G)={e1,e2,…em}表示各路网结点之间边的集合，其中m表示边的条数，则有m=n×(n-1)/2；
边权矩阵D表示路网全连通图G各结点之间的权值：
其中wij表示结点vi、vj间路网可达距离；Dij表示边权矩阵D的元素；
2）、将路网全连通图G归类划分为二叉路网拓扑进化树；
2.1）、将路网全连通图G抽象为一个以抽象连接点为连接点的星型树，路网全连通图中的结点形成星型树的实际结点，实际结点与抽象连接点连接；路网全连通图G中的任意两个结点vi和vj之间的权值dij表示为抽象星型树中两结点的抽象边权之和，dij=LiX+LjX，其中LiX表示所述结点vi到X之间的抽象边权，LjX表示所述结点vj到抽象连接点X之间的抽象边权；
2.2）、获取表征星型树中的任意两个结点 和 之间邻接关系的邻接值Sij，其中且i≠j；
2.3）、在每一组邻接值计算结果集中，选择邻接值最小的结点对作为最佳邻接对保留，将每一对邻接结点对合并为虚拟结点插入结点集合中，进行拓扑重构获得二叉路网拓扑进化树；
3）、依据路网结点间的邻接值，对路网全连通图进行分类划分、构建进化树拓扑路网，针对线路路径寻优问题，采用进行动态回溯方法对路径规划问题中线路路径寻优的目标结点进行分类，获取包含所有目标结点的最小分支树；
4）、对于包含所有路径规划问题中目标结点的最小分支树采用分支定界搜索策略消除无效分支结点，减小关联矩阵维度，之后针对消除无效分支结点之后的包含目标结点的最小分支树进行路径规划分析，获得线路路径寻优结果；
路径规划分析过程如下：
4.1）.路网拓扑重构，将整个路网按照邻接关系进行拓扑重构，最终形成以邻接关系为表现特征的路网拓扑进化树Tree；
4.2）.根据停靠站点集合V=(v1,v2，…vn)，采用动态回溯分类策略，在Tree中寻找最小分支树B-Tree，满足条件：
4.3）.对于包含(v1,v2,…vn)的最小分支树B-Tree，遵循分支定界优化策略，获取依据邻接关系判定各停靠结点访问先后的巡游顺序(vπ1，vπ2，…vπn)并输出；
4.4）.同时对步骤4.3）所获取的序列应用动态规划策略进行局部调整，即将(v1,v2，…vn)中位于B-Tree同一分支树的结点与其他结点分离开来，对限制范围内结点应用动态规划进行精确求解，之后与其他结点以相互邻接关系合并，得到最优解。
2.如权利要求1所述的基于进化树拓扑路网构建的路径规划确定方法，其特征在于：
所述步骤3）中，构建进化树拓扑路网采用上文结点间邻接值计算方法，按照邻接值最小策略，构建拓扑进化树Tree，包括以下步骤：
3.1.1）、令G={V,E}， Tree；
3.1.2）、对 vj∈V(G），计算vi，vj的邻接值Sij；
3.1.3）、寻找vm、vn，使得vm、vn的邻接值Smn=min（Sij），vm、vn∈V(G）；其中，vm、vn表示路网全连通图G中的任意两个结点；
3.1.4）、vm-n=vm∪vn，V＝V-{vm，vn}+{vm-n}，按照邻接关系，将父结点vm-n、子结点vm、子结点vn插入Tree中；
3.1.5）、若V中元素个数为1，算法结束，否则转步骤3.1.2）。
3.如权利要求2所述的基于进化树拓扑路网构建的路径规划确定方法，其特征在于：
所述步骤3）中，采用动态回溯策略对目标结点进行分类包括以下步骤：
3.2.1）、获取目标结点vs、vo，分别获取结点vs所在层m，和结点vo所在层n；
3.2.2）、判断vs和vo是否拥有同一父结点，若是，则获取共同父结点和该父结点的所有子结点；若否，则获取所在层大的目标结点作为回溯结点，获取回溯结点的直系父结点，将该直系父结点作为新的目标结点，重复步骤3.2.1）；
3.2.3）、以两个目标结点的共同父结点及其所有子结点形成的树作为最小分类树。
4.如权利要求1所述的基于进化树拓扑路网构建的路径规划确定方法，其特征在于：
所述步骤4）中，对目标结点的最小分支数采用分支定界搜索策略包括以下规则：
规则1、获取所在层大的目标结点，以该所在层大的目标结点的直系父结点或直系子结点作为途径结点，所有的目标结点和该途径结点形成关联结点集合；将该途径结点取代与其有直系关系的目标结点作为新的目标结点；
规则2、判断新的目标结点是否由邻接结点对合并而成的虚拟结点，若是则以与目标结点的邻接值最小的非虚拟结点替换；
判断新的目标结点的父结点或子结点是否为虚拟结点，若是，则以其非虚拟结点的兄弟结点替代；
规则3、判断两目标结点在路网拓扑进化树中是否位于同一层且具有兄弟邻接关系，若是，则以与最近邻接结点的邻接值判断先后顺序；所述的最近邻接点是指距离目标结点邻接值最小的为结点；
规则4、每一层只选择一个途径结点，忽略同层其他分支。

一种基于进化树拓扑路网构建的路径规划确定方法\n技术领域\n[0001] 本发明涉及一种地理信息数据处理、计算机应用领域，尤其涉及的是，一种基于进化树拓扑路网构建的路径规划方法。\n背景技术\n[0002] 针对具有连通性质停靠站点的实际城市路网，如何在多项式时间内求解多停靠站点网络路径优化问题，是智能交通系统的一个关键研究问题。\n[0003] 目前多数网络路径规划问题普遍采用以最小K值法、动态规划等精确算法或者遗传算法、蚁群算法等启发式算法为主的优化算法求解。其中，Zhan等首次实现了实际交通路网条件下的路径寻优算法，但是其采用的传统D算法进行线路搜索，对于小规模结点的计算结果非常准确，而对于大规模网络结点所需要的计算时耗是无法接受的。Jagadees等提出一种结点提升分层优化算法，能够保证算法在较短时间内获得最短路径，但其属于一种基于路网结点规模限制的算法，仅适合结点数固定的网络，对于现实结点个数的不确定性使得该算法无法普遍应用。Yanns等提出一种求解路径优化问题的混合启发性算法，有机结合了粒子群优化算法、多阶段领域搜索、随机自适应贪婪、扩展的领域搜索算法以及路径重新连接技术。刘菲等提出了一种基于加强基因突变解决网路路径优化问题，由于其初始种群仅有一个，无法避免遗传算法中普遍存在的早期收敛现象，也不能保证子代种群的多样性。景玲等提出了基于特定有序、选择、交叉、遗传算子路径诱导算法，而该算法对于初始种群的质量依赖性过高，如果初始化种群质量较差，则很容易陷入局部最优解。\n[0004] 因此，现有的技术在针对实际路网中的路径规划方面存在着缺陷，需要改进。\n发明内容\n[0005] 为了克服已有的实际路网路径规划方法的模型求解规模限制、计算速度慢的不足，本发明提供一种路径规划模型合理、快速性良好的基于进化树拓扑路网构建的路径规划确定方法。\n[0006] 本发明解决其技术问题所采用的技术方案是： \n[0007] 一种基于进化树拓扑路网构建的路径规划确定方法，包括以下步骤：\n[0008] 1）、获 取 城 市 完 全 路 网 数 据，应 用 邻 接 矩 阵 方 法 构 造 表示 原 始 地 理 信 息 的 路 网 全 连 通 图G，将 路 网 结 点 抽 象 为 全 连 通 图 中的结点 ，而路网结点间的路网可达性抽象为全连通图 中的边 的连通性，全连通图 ，其中 为结点集, 表示结点个数； 表示各路\n网结点之间边的集合， 表示边的条数，则有 边权矩阵 表示全联通图\n各结点之间边权值：\n[0009] \n[0010] 其中 、 表示图 中结点标号， 表示结点 、 间路网可达距离； 为边权矩阵 的元素，表示连接结点 、 的边权值；\n[0011] 2）、将路网全连通图G 归类划分为二叉路网拓扑进化树；\n[0012] 2.1）、将路网全连通图 抽象为一个以抽象连接点为连接点的星型树，全连通图中的结点形成星型树的实际结点，实际结点之间通过抽象连接点连接；全连通图G 中的任意两个结点 和 之间的权值 表示为抽象星型树中两结点的抽象边权之和， \n，其中 表示星型树中结点 到X之间的抽象边权， 表示星型树中结点\n到抽象连接点X之间的抽象边权；\n[0013] 2.2）、获取表征星型树中的任意两个结点 和 之间邻接关系的邻接值 ，其中、 且 ； ；\n[0014] 2.3）、在每一组邻接值计算结果集中，选择邻接值最小的结点对作为最佳邻接对保留，将每一对邻接结点对合并为虚拟结点插入结点集合中，进行拓扑重构获得二叉路网拓扑进化树；\n[0015] 3）、依据路网结点间的邻接值，对路网全连通图进行分类划分、构建进化树拓扑路网，针对线路路径寻优问题，采用进行动态回溯方法对路径规划问题中线路路径寻优的目标结点进行分类，获取包含所有目标结点的最小分支树；\n[0016] 4）、对于包含所有路径规划问题中目标结点的最小分支树采用分支定界搜索策略消除无效分支结点，减小关联矩阵维度，在此基础之上进行路径规划分析，获得规划结果。\n[0017] 进一步，所述步骤3）中，构建进化树拓扑路网采用上文结点间邻接值计算方法，按照邻接值最小策略，构建拓扑进化树 ，包括以下步骤：\n[0018] 3.1.1）、令G={V,E}， ， ；\n[0019] 3.1.2）、对 vi、vj V，计算vi，vj的邻接值Sij；\n[0020] 3.1.3）、寻找vm、vn，使得vm、vn的邻接值Smn=min（Sij），vm、vn V；其中，vm、vn表示路网全连通图G 中的任意两个结点；\n[0021] 3.1.4）、vm-n= vm vn，V=V-{ vm，vn }+{ vm-n }，按照邻接关系，将父结点vm-n、子结点vm、子结点vn插入 中；\n[0022] 3.1.5）、若V 中元素个数为1，算法结束，否则转步骤3.1.2）。\n[0023] 进一步，所述步骤A3中，采用动态回溯策略对目标结点进行分类包括以下步骤：\n[0024] 3.2.1）、获取目标结点 、 ，分别获取结点 所在层m，和结点 所在层n；\n[0025] 3.2.2）、判断 和 是否拥有同一父结点，若是，则获取共同父结点和该父结点的所有子结点；若否，则获取所在层大的目标结点作为回溯结点，获取回溯结点的直系父结点，将该直系父结点作为新的目标结点，重复步骤3.2.1）；\n[0026] 3.2.3）、以两个目标结点的共同父结点及其所有子结点形成的树作为最小分类树。\n[0027] 进一步，所述步骤4）中，对目标结点的最小分支数采用分支丁姐搜索策略包括以下规则：\n[0028] 规则1、获取所在层大的目标结点，以该所在层大的目标结点的直系父结点或直系子结点作为途径结点，所有的目标结点和该途径结点形成关联结点集合；将该途径结点取代与其有直系关系的目标结点作为新的目标结点；\n[0029] 规则2、判断新的目标结点是否由邻接结点对合并而成的虚拟结点，若是则以与目标结点的邻接值最小的非虚拟结点替换；\n[0030] 判断新的目标结点的父结点或子结点是否虚拟结点，若是，则以其非虚拟结点的兄弟结点替代；\n[0031] 规则3、判断两目标结点在路网拓扑进化树中是否位于同一层且具有兄弟邻接关系，若是，则以与最近邻接结点的邻接值判断先后顺序；所述的最近邻接点是指距离目标结点邻接值最小的为结点；\n[0032] 规则4、每一层只选择一个途径结点，忽略同层其他分支。\n[0033] 本发明的技术构思为：首先获取城市完全路网数据，然后借鉴系统生物学中进化树分类的思想，引入路网结点间邻接关系评价标准邻接值的概念，将路网按照其结点邻接关系归类划分为以路网结点间邻接值为表征的路网拓扑进化树，同时对线路路径寻优问题中目标结点进行动态回溯分类，在限定路网搜索区域同时采用分支定界搜索策略进行搜索优化，降低了搜索算法时间复杂度。\n[0034] 本发明的有益效果主要表现在：本发明优化了路径规划过程的算法复杂度，提高了路径规划的效率。\n附图说明\n[0035] 图1是基于进化树拓扑路网构建的路径规划确定方法的流程图。\n[0036] 图2是路网结点结构图。\n[0037] 图3是抽象路网星形树。\n[0038] 图4是结点 、 邻接关系判定模型树。\n[0039] 图5是选择 、 为邻接对后的拓扑重构模型树。\n[0040] 图6是动态回溯分类算法示意图。\n[0041] 图7是拓扑进化树筛选示意图。\n[0042] 图8是中国30个大陆省会城市拓扑进化树示意图。\n[0043] 图9是搜索区域局部动态规划示意图。\n[0044] 图10是进化树路径优化结果示意图(32停靠点)。\n具体实施方式\n[0045] 实施例一\n[0046] 参照图1～图10：\n[0047] 一种基于进化树拓扑路网构建的路径规划方法，包括以下步骤：\n[0048] 1）、获取城市完全路网数据，应用邻接矩阵方法构造表示原始地理信息的路网全连通图G，将路网结点抽象为全连通图 中的结点 ，而路网结点间的路网可达性抽象为全连通图 中的边 的连通性，全连通图 ，其中 为结点集, 表\n示结点个数； 表示各路网结点之间边的集合，其中 表示边的条数，则有\n；\n[0049] 边权矩阵 表示全联通图 各结点之间的权值：\n[0050] \n[0051] 其中 表示结点 、 间路网可达距离； 表示边权矩阵 的元素；\n[0052] 2）、将路网全连通图G 归类划分为二叉路网拓扑进化树；\n[0053] 2.1）、将路网全连通图 抽象为一个以抽象连接点为连接点的星型树，全连通图中的结点形成星型树的实际结点，实际结点之间通过抽象连接点连接；全连通图G 中的任意两个结点 和 之间的权值 表示为抽象星型树中两结点的抽象边权之和， \n，其中 表示星型树中结点 到X之间的抽象边权， 表示星型树中结点\n到抽象连接点X之间的抽象边权；\n[0054] 定义：给定一个抽象路网星形树，定义路网抽象边权总和 为： \n[0055] (1)\n[0056] 其中 表示结点 到连接点 的权值， 表示结点 到 之间的权值，\n为路网结点个数，且有： ， 。 \n[0057] 由式(1)变式为：\n[0058] (2)\n[0059] 也即：\n[0060] (3)\n[0061] 由此可得：\n[0062] (4)\n[0063] 2.2）、获取表征星型树中的任意两个结点 和 之间邻接关系的邻接值 ，其中、 且 ； ；\n[0064] 基于式(1)，引入邻接值的概念用于判断结点 、 的邻接关系，其中 、 且，定义 表示结点 、 之间邻接值，将网络中任意两点 、 结点通过两个抽象连\n接点X、Y与其他结点连接，如图4所示，之后计算结点 、 的 值。\n[0065] 为了计算路网中任意两点间的邻接关系权值，引入以下定义：\n[0066] 由图4定义图 中任意两点 、 之间的邻接值 为：\n[0067] (5)\n[0068] 定义两结点 和 合并后，组成新结点 ， 与其他结点边权为：\n[0069] (6)\n[0070] 其中 且 ，由式(1)和式(5)可计算得到推论如下：\n[0071] (7)\n[0072] 证明. 将邻 接值 计算 转化 为邻 接矩 阵方 法 表示，令Ax=d，其 中， 为任意两结点之间的边权值矩阵，其长度为n(n-1)/2，则有\n， 为图G的邻接矩阵表示，其中：\n[0073] \n[0074] 将 转化为 ，得到：\n[0075] (8)\n[0076] 其中 ，由图4可知， 、 为任意结点与 连线中所有经过 的道路，\n除 外都经过 ，则：\n[0077] \n[0078] 其他类推得到矩阵 和 为：\n[0079] \n[0080] \n[0081] 其 中 ， ，\n， ， ，\n， 。将 代入式(8)中，从而求得：\n[0082] (9)\n[0083] (10)\n[0084] (11)\n[0085] (12)\n[0086] 其中 ， ， ， ，上式与\n式(5)联立，可消除未知变量 、 、 、 ，求得 的最终计算式如\n下：\n[0087] \n[0088] 证毕.\n[0089] 2.3）、在每一组邻接值计算结果集中，选择邻接值最小的结点对作为最佳邻接对保留，将每一对邻接结点对合并为虚拟结点插入结点集合中，并在结点集中删除该邻接结点对，进行拓扑重构获得二叉路网拓扑进化树；\n[0090] 如图5所示，以下为拓扑重构规则及其合法性证明：\n[0091] 拓扑重构规则：假定 和 为邻接结点对，则将结点 和 组成一个新的结点，定义为虚拟结点 ，表现为在 中删除结点 、 ，插入新结点 ，之后依照抽象图\n构建原则构建新的路网 。\n[0092] 合法性证明 ：以结点 、 为例，假定 、 为邻接结点对，如图5所示，拓扑重构后的连通图 应满足式(1)，即需证明：\n[0093] (13)\n[0094] 证明：\n[0095] (1) 对于式(13)中右式，由式(9)可知：\n[0096] \n[0097] 联立 ， .化简上式得：\n[0098] 则可得到：\n[0099] (2)对于式（13）中左式，由式(6)，可知：\n[0100] \n[0101] 其中D13=D1A+LAX+L3X，D23=D2A+LAX+L3X，则上式可变式为：\n[0102] \n[0103] 也即：\n[0104] 综上，左式=右式，则 。\n[0105] 证毕.\n[0106] 上述证明重新拓扑构建满足式(1)要求，由此在寻求每一对邻接结点后，将其合并为虚拟结点并插入结点集合中，进行拓扑重构；\n[0107] 3）、依据路网结点间的邻接值，对路网全连通图进行分类划分、构建进化树拓扑路网，针对线路路径寻优问题，采用进行动态回溯方法对路径规划问题中线路路径寻优的目标结点进行分类，获取包含所有目标结点的最小分支树；\n[0108] 4）、对于包含所有路径规划问题中目标结点的最小分支树采用分支定界搜索策略消除无效分支结点，减小关联矩阵维度，在此基础之上进行路径规划分析，获得规划结果。\n[0109] 所述步骤3）中，构建进化树拓扑路网采用上文结点间邻接值计算方法，按照邻接值最小策略，构建拓扑进化树 ，包括以下步骤：\n[0110] 3.1.1）、令G={V,E}， ， ；\n[0111] 3.1.2）、对 vi、vj V（G），计算vi，vj的邻接值Sij；\n[0112] 3.1.3）、寻找vm、vn，使得vm、vn的邻接值Smn=min（Sij），vm、vn V（G）；其中，vm、vn表示路网全连通图G中的任意两个结点；\n[0113] 3.1.4）、vm-n= vm vn，V=V-{ vm，vn }+{ vm-n }，按照邻接关系，将父结点vm-n、子结点vm、子结点vn插入 中；所述的邻接关系就是根据邻接值判断的，邻接值越小邻接关系越紧密，按照邻接关系是指两结点为子结点，其构成的虚拟结点为父结点这样的一个父子关系；\n[0114] 3.1.5）、若V 中元素个数为1，算法结束，否则转步骤3.2）。\n[0115] 所述步骤A3中，采用动态回溯策略对目标结点进行分类包括以下步骤：\n[0116] 3.2.1）、获取目标结点 、 ，分别获取结点 所在层m，和结点 所在层n；\n[0117] 3.2.2）、判断 和 是否拥有同一父结点，若是，则获取共同父结点和该父结点的所有子结点；若否，则获取所在层大的目标结点作为回溯结点，获取回溯结点的直系父结点，将该直系父结点作为新的目标结点，重复步骤3.2.1）；\n[0118] 3.2.3）、以两个目标结点的共同父结点及其所有子结点形成的树作为最小分类树。\n[0119] 所述步骤4）中，对目标结点的最小分支数采用分支丁姐搜索策略包括以下规则：\n[0120] 规则1、获取所在层大的目标结点，以该所在层大的目标结点的直系父结点或直系子结点作为途径结点，所有的目标结点和该途径结点形成关联结点集合；将该途径结点取代与其有直系关系的目标结点作为新的目标结点；\n[0121] 规则2、判断新的目标结点是否由邻接结点对合并而成的虚拟结点，若是则以与目标结点的邻接值最小的非虚拟结点替换；\n[0122] 判断新的目标结点的父结点或子结点是否虚拟结点，若是，则以其非虚拟结点的兄弟结点替代；\n[0123] 规则3、判断两目标结点在路网拓扑进化树中是否位于同一层且具有兄弟邻接关系，若是，则以与最近邻接结点的邻接值判断先后顺序；所述的最近邻接点是指距离目标结点邻接值最小的为结点；\n[0124] 规则4、每一层只选择一个途径结点，忽略同层其他分支。\n[0125] 本发明的技术构思为：首先获取城市完全路网数据，然后借鉴系统生物学中进化树分类的思想，引入路网结点间邻接关系评价标准邻接值的概念，将路网按照其结点邻接关系归类划分为以路网结点间邻接值为表征的路网拓扑进化树，同时对线路路径寻优问题中目标结点进行动态回溯分类，在限定路网搜索区域同时采用分支定界搜索策略进行搜索优化，降低了搜索算法时间复杂度。\n[0126] 实施例二\n[0127] 结合实际城市完全路网，进一步说明本发明：\n[0128] 一种基于进化树拓扑路网构建的路径规划确定方法，如图1所示，其中包含以下步骤：\n[0129] A1、获取城市完全路网数据，构建路网全连通图 ，其中\n为路网结点集, 表示结点个数。 表示各路网结点之间边的集合，其中\n表示边的条数，边权矩阵 表示全联通图 各结点之间的权值 ，\n表示为路网中结点 、 间路网可达距离；A2、将路网全连通图 按照其结点邻接关系归类划分为以路网结点间邻接值为表征的二叉路网拓扑进化树；A3、依据进化树拓扑路网，构建线路路径寻优问题，对于问题中目标结点进行动态回溯分类，获取包含所有目标结点的最小分支树；A4、对于包含所有路径规划目标结点的最小分支树采用分支定界搜索策略消除无效分支结点，进一步减小关联矩阵维度，在此基础之上进行路径规划分析，更快的得到规划结果。\n[0130] 所述的方法，其中，在步骤A1中，获取城市完全路网数据，路网数据中应包括路网结点的经纬度、结点间路网可达距离等地理信息，如采用国家基础地理信息系统（NFGIS）\n1:400万比例的中国行政中心数据文件res1_4m，该文件（.shp，GIS的图形格式）包含30个大陆省会城市信息，可以从http://nfgis.nsd-i.gove.cn下载。\n[0131] 所述的方法，其中，在步骤A1中，针对城市完全路网数据，构建路网全连通图，其中 为路网结点集, 表示结点个数。 表示各\n路网结点之间边的集合，其中 表示边的条数，边权矩阵 表示全联通图 各结点之间的权值 ， 表示为路网中结点 、 间路网可达距离。 \n[0132] 所述的方法，其中，在步骤A2中，针对路网全连通图 ，计算路网全连通图 中任意两结点之间的邻接值。首先根据路网全连通图 ，计算其中任意两结点的邻接值，组成当前路网全连通图 的结点邻接值集，在每一组邻接值计算结果集中，选择邻接值最小的结点对作为最佳邻接对保留，之后应用拓扑重构规则对路网进行重构，\n[0133] 所述的方法，其中，在步骤A2中，针对路网拓扑重构，采用以下规则：假定 和为邻接结点对，则将结点 和 组成一个新的结点，定义为虚拟结点 ，表现为在\n中删除结点 、 ，插入新结点 ，之后依照抽象图构建原则构建新的路网 。\n[0134] 所述的方法，其中，在步骤A3中，根据步骤A2中计算结果，构建路网拓扑进化树，如针对国家基础地理信息系统（NFGIS）1:400万比例的中国行政中心数据文件res1_4m，该文件（.shp，GIS的图形格式）包含30个大陆省会城市地理信息，采用以下算法实现路网拓扑进化树构建(构建结果如图8)：\n[0135] 1. 令G={V,E}， ，初始化进化树 ；\n[0136] 2. 对 vi、vj V（G），计算vi，vj的邻接值Sij；\n[0137] 3. 寻找vm、vn，使得Smn=min（Sij），vm、vn V（G）；\n[0138] 4. vm-n= vm vn，V=V-{ vm，vn }+{ vm-n }，按照邻接关系，将vm-（n 父结点）、vm（子结点）、vn（子结点）插入 中\n[0139] 5. 若V 中元素个数为1，算法结束，否则转步骤2。\n[0140] 所述的方法，其中，在步骤A3中，针对路网拓扑进化树，采用动态回溯方法获取包含所有路径规划目标结点的最小分支树包含以下步骤，获取起始结点 以及目标结点 ，遍历路网拓扑进化树 ，判断 、 在 中的位置，假定 、 分别处于 的第m、n\n层，分别回溯 、 的父结点，当二者回溯到同一父结点时终止，保留该结点及其以下分支树，作为包含目标结点最小分类树，算法流程如图6所示。\n[0141] 所述的方法，其中，在步骤A4中，还包含以下步骤，包含所有路径规划目标结点的最小分支树，采用分支定界算法对规划过程进行优化，以图7为例，定义规则如下：\n[0142] 1．根据目标结点的邻接性，首选直系父结点或直系子结点，图7中从 出发，则首先选择 作为途径结点，此时关联结点集合为 。\n[0143] 2．若目标结点的父结点或子结点为虚拟结点，则以其兄弟结点替代，图7中从出发，其父结点为 ，则以结点 替代 。\n[0144] 3．若两目标结点位于同一层次且具有兄弟邻接关系，则以与最近邻接结点的邻接值判断先后顺序，如图7中 、 、 均为停靠站点，此时存在两种停靠顺序，即S-2-3或者S-3-2，根据点2、3到点S的邻接值大小，判断点2和点3那个距离S更近，近的先停靠，远的后停靠，如2点距离S更近，则停靠顺序为S-2-3，反之则为S-3-2；因此， 、 位于同一层，则判断 、 大小来决定停靠顺序。\n[0145] 4．每一层只选择一个途径结点，忽略同层其他分支，如选择 作为途径结点，则忽略 及其分支树。\n[0146] 所述的方法，其中，在步骤A4中，还包含以下步骤，将包含所有停靠站点的路网重构为具有邻接关系表现特征的路网拓扑进化树，应用动态回溯方法获取包含所需停靠站点的最小分支树，采用分支定界优化策略对停靠站点集合 进行拓扑排序，在此基础之上设计路径规划算法步骤如下：\n[0147] 1．路网拓扑重构，将整个路网按照邻接关系进行拓扑重构，最终形成以邻接关系为表现特征的路网拓扑进化树Tree。\n[0148] 2．根据停靠站点集合V=(v1,v2,…vn)，采用动态回溯分类策略，在Tree 中寻找最小分支树B-Tree，满足条件： 。\n[0149] 3．对于包含(v1,v2,…vn)的最小分支树B-Tree，遵循分支定界优化策略，获取依据邻接关系判定各停靠结点访问先后的巡游顺序 并输出。\n[0150] 4．同时对步骤3所获取的序列应用动态规划策略进行局部调整，即将(v1,v2,…vn)中位于B-Tree同一分支树的结点与其他结点分离开来，对限制范围内结点应用动态规划进行精确求解，之后与其他结点以相互邻接关系合并，得到最优解，如图9所示。\n[0151] 图9给出了搜索区域局部动态规划的情况，其中B-Tree’ B-Tree，v2、v3、v4为B-Tree’所包含的停靠结点，将B-Tree’在B-Tree中分离出来，对(v2，v3, ,v4)进行动态规划求解局部最优路线 ，之后依据邻接关系将其插入到 中，得到\n经过局部优化后的巡游路线，其中其中 是 的一个规则置换。\n[0152] 本发明中基于路网拓扑进化树构建的路径规划算法平均时间复杂度为\n，其中n表示路径规划问题中停靠站点的个数。\n[0153] 依据路网拓扑进化树的路径优化算法，考虑实际路网可达性，对中国大陆32个省会城市随机选取停靠站点进行路径寻优算法仿真，以停靠站点组合北京、石家庄、太原、沈阳、长春、西安、成都为实施例，基于路网拓扑进化树构建的路径规划算法过程如下：\n[0154] Step1：获取中国大陆省会城市完全路网数据，根据各城市之间相互邻接关系，构建路网拓扑进化树，如图8所示。\n[0155] Step2：应用动态回溯策略判断路网拓扑进化树中北京、石家庄、太原、沈阳、长春、西安、成都所在最小分支树。\n[0156] Step3：采用分支定界策略消除包含北京、石家庄、太原、沈阳、长春、西安、成都的最小分支树中无效结点，用于减小路径规划问题关联矩阵维度。\n[0157] Step4：设计路径规划算法，并获取包含北京、石家庄、太原、沈阳、长春、西安、成都目标结点的路径规划方案，采用拓扑分类算法求解结果为序列：长春→沈阳→北京→太原→石家庄→西安→成都，目标值为35.0420(1:400万比例尺)，如图10所示。\n[0158] 以上阐述的是本发明给出的一个实施例表现出来的优良优化效果，显然本发明不仅适合上述实施例，在不偏离本发明基本精神及不超出本发明实质内容所涉及内容的前提下可对其做种种变化加以实施。