专利名称：基于遥感电子地图的旅行商路径规划方法
技术领域：
本发明涉及导航技术领域，尤其是涉及一种基于遥感电子地像处理的旅行商路径规划问题的解决方法。
背景技术：
旅行商问题(Traveling Salesman Problem)是路径规划的经典问题,最早的数学规划是由Dantzig等人在1959年提出，其核心问题是寻求遍历所有路径规划需求点的最小路径成本。旅行商问题属于NP-Complete的范畴，目前大多数解法为启发式算法。遥感技术是20世纪60年代兴起的一种探测技术，它以航空摄影技术为基础，目前广泛应用于水文、气象、环境资源、地质勘探等领域，是一门实用的空间探测技术。遥感技术有以下特点 I.可用于获取大范围的地理数据资料。遥感技术使用的航拍飞行器的飞行高度可超过10km，而卫星轨道高度可达910km左右。2.获取信息速度快且周期短。遥感拍摄卫星围绕着地球运转，可以及时传送经过地区的自然地理情况的最新资料，更新原有资料。3.受限制少。作为空间技术的典型代表，遥感技术完全不受地表复杂的地理环境制约，能快速提供相关地理位置的全局信息。公开号为101832779A的发明专利公开了一种复杂环境下的导航方法，从航空遥感或卫星遥感影像图获取某区域复杂环境下的道路灾情信息；初始化处理；信息融合，生成某区域复杂环境下的实时导航电子地图；监控中心根据新生成的实时导航电子地图，对监控目标进行路径规划，把规划后的路径发给所有监控目标；监控目标利用自身携带的导航系统和实时导航电子地图，实时获取自身真实位置信息；当真实位置信息和估计位置信息间误差大于某个阈值时，监控目标通过复杂环境下特殊的通信手段向监控中心上报监控目标当前真实位置信息及当前期望速度；监控中心利用监控目标上报的目标真实位置信息和目标当前期望速度在实时导航电子地图上对监控目标进行实时显示和监控。目前，遥感技术和路径规划领域都处于快速发展阶段，逐渐成熟的GPS全球定位系统已经广泛的应用于导航领域，而基于图像处理的旅行商路径规划问题尚属一个新的技术领域。

发明内容
本发明提供了一种基于遥感电子地图的旅行商路径规划方法，将旅行商路径规划问题的地理节点坐标和节点间相对距离建立地理位置数据库，根据遥感电子地图能反映描述区域全局特征的特点，采用图像处理的方法将特定地理特征提取出来，形成地理特征数据库，用于修正地理位置数据库的节点相对距离；采用一种启发式算法——模拟退火算法对经过修正的地理位置数据库进行路径优化，从而获得能反映实际地理情况的基于遥感电子地图的旅行商路径规划问题的解法。
一种基于遥感电子地图的旅行商路径规划方法，包括第一步从卫星遥感电子地图或航空遥感电子地图中获取进行旅行商问题路径规划的某区域；第二步确定路径规划所要遍历的地理节点坐标值并计算节点之间的相对距离，作为全理想状况下的数据模型存入地理位置数据库中，数据模型的结构为[节点，节点坐标]+[组合节点对之间的距离]，为后续的修正及移位做准备；第三步，对第一步所述区域的遥感电子地图进行地理特征提取和图像分割处理，以获得反映该区域关键地理特征的地理特征数据库，为后续步骤的路径规划提供可靠数据；第四步，对所有地理节点进行如下处理从地理位置数据库中获取任意一对节点的坐标以及他们之间的距离；判断第三步中得到的地理特征数据库中是否有至少一个点处在该节点对的连线上，根据是否存在这样的点，对该节点对的距离乘以不同的修正系数，从 而修正了地理位置数据库中各节点对的距离；第五步采用模拟退火解法，使数据模型得到组合优化下的最优解，输出优化路径。所述的采用模拟退火解法得到最优解，步骤如下(5. I)随机生成一条遍历路径，作为初始解，计算全部遍历路程，统计步长计数器清零。(5. 2)在第四步所得修正后的地理位置数据库中随机生成一条邻域内解，计算新路径的遍历长度，根据新路径的长度比较进入两种选择如果新路径长度较短，则接受较新的解，根据降温速率将系统能量降低，统计步长计数器递增；如果新路径长度较之前解没有减短，则将一个大小合适的随机数与降温速率的指数做比较，如果前者较小，同样根据降温速率将系统能量降低，统计步长计数器递增。(5. 3)如果统计步长计数器没有达到临界连链长，循环进行第5. 2步骤。(5. 4)每十次第5. 2步骤中的比较之后，进行一次路径结果的输出，以图形的方式显示，可视化地呈现路径改善的过程。如果遥感地图没有更新的话，不断进行第二步至第五步的操作，系统的稳定速率将会逐渐平缓，模拟退火算法第5. 2步骤对系统能量降低的贡献度减弱，在给定链长内对所产生新解的接受度下降，经过一定的时间后，认为概率意义下能够接受即可。如果遥感电子地图被更新，那么输入较新的地理信息，进行第三，第四步骤，获得更新后的地理特征数据库，跳回第一步进行运算。本发明中的所述的地理特征提取和图像分割处理方法，能准确获取当前区域内的关键地理特征，并反馈给路径组合优化过程，排除不符合实际路径规划情况的方案，具体地理特征的选择取决于旅行商路径规划问题的实际情况。本发明的方法能及时获取规划区域的地理信息数据，更新图像即可更新数据库，而组合优化的搜索算法同时让其在图像更新的间隔时间内不停止地进行更优路线的搜索；组合优化的搜索方法为启发式的模拟退火算法，通过强收敛条件进行迭代，接受最优解。本发明方法主要针对基于遥感电子地图的旅行商路径规划问题，通过建立地理特征数据库和使用启发式算法，在有限时间内给出当前遥感电子地图中符合地理特征情况的旅行商问题优化解。


图I为本发明的基本思路概念图。图2为本发明方法的流程图。图3 图6，为具体实例实施本发明的方法的试验过程示意图。图7为本发明方法中对地理节点进行相对位置修正的示意图。图8 图10，为对具体实例进行本发明方法的结果验证示意图。
具体实施例方式
·
如图I所示，在遥感电子地图中进行旅行商路径规划问题的求解需要考虑两方面，首先是寻求一种应用于解决该问题的启发式算法，本发明中采用模拟退火算法；其次是寻求一种特征提取和图像处理的方法，将遥感电子地图中涉及到影响路径规划算法实际效果和合理性的关键地理特征抽象成数学模型，储存在地理特征数据库中，进而应用于改善基于所述的启发式算法，是算法结果符合实际地理情况。如图2为本方法的流程示意图，图3-图6所示描述了一个基于遥感电子地图的旅行商路径规划问题范例——印度洋爪哇海域群岛旅行商路径规划问题的求解，按照以下步骤实现第一步，从卫星遥感电子地图或航空遥感电子地图中获取进行旅行商问题路径规划的某区域；如图3所示，遥感电子地图的来源是美国谷歌公司的免费软件GoogleEarth。在选择该区域的遥感电子地图时，尽量将区域中的目标放置在视野中央，使得该区域的全部地理信息能显示在图中，方便进行区域的地理特征提取和图像处理操作。图3中的群岛构成了一个较为密集且复杂的地理特征系统，该范例将旅行商问题的背景设为海上航行，此处为了说明本发明的具体实施方案，在遥感电子地图中选取了 22个地理节点，所选节点具有随机性、偶然性和实际性，如图4所示，目的是通过路径优化获取遍历这些地理节点的最短路径，同时考虑到海洋航行中无法“穿岛而过”的实际情况，从而优化出一条最短、最合理的路径。第二步确定路径规划所要遍历的地理节点坐标值并计算节点之间的相对距离，作为全理想状况下的数据模型存入地理位置数据库中，为后续的修正及移位做准备；将图4中的地理节点的坐标值以及节点之间的相对距离保存到地理位置数据库G中，为后续进行旅行商路径规划问题做准备。第三步，对第一步所述区域的遥感电子地图进行地理特征提取和图像分割处理，以获得反映该区域关键地理特征的数学模型和数据库，为后续步骤的路径规划提供可靠数据；首先确定图3需要提取的地理特征，即全部岛屿或陆地。在遥感电子地图中手动选择符合这一地理特征的一块子区域，通过电脑编程实现了手动交互选择，得到了图5中多边形区域选中的子区域。计算这块子区域内所有像孝点的平均RGB值向量m..并乘以矫正系数α，得到所述子区域内像素点的矫正均值m，》l=m < α，矫正系数α衡量了该子区域的遥感电子地图在考虑过信号传输影响之后的清晰程度，通常取α约等于1，代表清晰程度最佳。m衡量了我们需要从遥感电子地图中提取的地理特征。同时计算该子区域对应的协方差矩阵C，公式如下
权利要求
1.一种基于遥感电子地图的旅行商路径规划方法，包括 第一步从卫星遥感电子地图或航空遥感电子地图中获取进行旅行商问题路径规划的某区域； 第二步确定路径规划所要遍历的地理节点坐标值并计算节点之间的相对距离，作为全理想状况下的数据模型存入地理位置数据库中，数据模型的结构为[节点，节点坐标]+[组合节点对之间的距离]; 第三步，对第一步所述区域的遥感电子地图进行地理特征提取和图像分割处理，以获得反映该区域关键地理特征的地理特征数据库； 第四步，对所有地理节点进行如下处理从地理位置数据库中获取任意一对节点的坐标以及他们之间的距离；判断第三步中得到的地理特征数据库中是否有至少一个点处在该节点对的连线上；根据是否存在这样的点，对该节点对的距离乘以不同的修正系数，从而修正了地理位置数据库中各节点对的距离； 第五步采用模拟退火解法，使数据模型得到组合优化下的最优解，输出优化路径。
2.根据权利要求I所述的基于遥感电子地图的旅行商路径规划方法，其特征在于所述的采用模拟退火解法处理数据模型过程，包括 (5. I)随机生成一条遍历路径，作为初始解，计算全部遍历路程，统计步长计数器清零； (5. 2)在第四步所得修正后的地理位置数据库中随机生成一条邻域内解，计算新路径的遍历长度，根据新路径的长度比较进入两种选择如果新路径长度较短，则接受较新的解，根据降温速率将系统能量降低，统计步长计数器递增；如果新路径长度较之前解没有减短，则将一个大小合适的随机数与降温速率的指数做比较，如果前者较小，同样根据降温速率将系统能量降低，统计步长计数器递增； (5. 3)如果统计步长计数器没有达到临界连链长，循环进行5. 2步骤； (5.4)每十次第5. 2步骤中的比较之后，进行一次路径结果的输出，以图形的方式显示，呈现路径改善的过程。
3.根据权利要求I所述的基于遥感电子地图的旅行商路径规划方法，其特征在于所述的第五步的最优解为 如果遥感地图的数据库没有更新的话，不断进行第二步至第五步的操作，系统的稳定速率将会逐渐平缓，模拟退火算法第5. 2步骤对系统能量降低的贡献度减弱，在给定链长内对所产生新解的接受度下降，经过一定的时间后，认为概率意义下能够接受即可；如果遥感电子地图被更新，那么输入较新的地理信息进入数据库，跳回第一步进行运算。
全文摘要
本发明公开了一种基于遥感电子地图的旅行商路径规划方法，包括第一步从遥感电子地图中获取进行旅行商问题路径规划的某区域；第二步确定路径规划所要遍历的地理节点坐标值并计算节点之间的相对距离，作为全理想状况下的数据模型存入地理位置数据库中；第三步，对第一步所述区域的遥感电子地图进行地理特征提取和图像分割处理，获得反映该区域关键地理特征的地理特征数据库；第四步量化地赋予修正系数，修正数据模型；第五步采用模拟退火解法，使数据模型得到组合优化下的最优解，输出优化路径。本发明方法通过建立地理特征数据库和使用启发式算法，在有限时间内给出当前遥感电子地图中符合地理特征情况的旅行商问题优化解。
文档编号G01C21/20GK102945511SQ20121040921
公开日2013年2月27日 申请日期2012年10月23日 优先权日2012年10月23日
发明者齐欢, 刘亮, 吴维敏 申请人:浙江大学