电子地图路径规划软件设计范文

摘要：设计了基于粒子群算法的电子地图路径规划软件，可以实现对西安市电子地图放大、缩小、定位、搜索、路径导航等功能，根据Dijsktra算法实现路径导航功能，根据粒子群算法解决真实路径的路径规划问题，可以在指定的节点范围内寻找一条较优路径，达到路径规划目的。

关键词：粒子群算法；Dijsktra算法；路径规划

0引言

电子地图不仅能够提供路线规划的多种功能，还能够提供道路的详细信息，规划出最佳的路线供用户选择。设计了西安市电子地图路径规划软件，该软件具有地图放大、缩小、定位、搜索等基本功能，可以根据Dijsktra算法实现路径导航功能，完成任意起始点和终点之间的最短路径计算，基于粒子群算法能够在选定的节点范围内寻找一条优化路径，达到路径规划目的，如公交线路规划、机器人路线规划、物流配送［1］等。

1路径规划软件设计模块与功能路径

规划软件主要模型主要分为地图操作和路径规划，其中地图操作主要有放大、缩小、定位搜索等，路径规划主要是路径导航与路径寻优。点击“地图操作”，会弹出“放大”、“缩小”、“定位”、“搜索”子菜单，各个功能如下：（1）放大：点击地图上任意位置，地图将以该地点为中心放大一倍比例尺显示。（2）缩小：点击地图上任意位置，地图将以该地点为中心缩小一倍比例尺显示。（3）定位：可以通过定位系统实时定位。（4）搜索：在地图上寻找目标位置。点击“路径寻优”，会弹出“路径导航”及“路径规划”子菜单，各个功能如下：（1）路径导航：输入起始点和终点，可以计算出一条最短路径。（2）路径规划：选择若干个结点，可以计算出经过这些结点的一条较优路径。

2路径规划软件实现技术

2．1MapInfo软件简介MapInfo由美国MapInfo公司开发，是一款地理信息系统二次开发软件，能够提供数据可视化、信息地图化的桌面解决方案。它集成多种数据库数据、结合计算机地图方法、采用数据库技术、融入地理信息系统分析功能，可以为各行各业所用的软件系统提供服务［2］。MapInfo全称为Mapping＋Information即地图对象＋属性数据。MapInfo采用“空间实体＋空间索引”的拓扑关系模型，其空间实体是地理实体的抽象，类型包括点、线、面，每个空间实体对象都具有自身所有属性，一个图层由多个空间实体构成。空间索引能够定位到给定的空间坐标，快速搜索到坐标范围中的空间对象。MapInfo利用双数据库存储模式（空间、属性数据），空间数据以MapInfo的自定义格式保存在文件中，属性数据存储在关系数据库的属性表中，他们之间通过一定的索引机制互相通信［3］。

2．2Mapx控件简介MapInfo公司在1996年推出了基于ActiveX技术的MapX控件，MapX控件随着MapInfo的功能升级而不断完善。MapX控件提供了二次开发的功能强大的地图化组件。可以嵌入到在可视化程序开发环境中如VisualBasic、VisualC＋＋等，只需将MapX控件放入到窗体中，进行设置属性、调用方法和事件，就可实现地理空间数据的常用操作及可视化，并可以实现空间查询、地理编码等复杂的地图信息系统功能［4］。MapX与MapInfo使用一致的地图数据格式，主要功能有显示MapInfo格式的地图数据，支持地图的放大、缩小、平移、选择等操作，图层的自由控制，支持动态图层和自定义图层，专题地图制作，简单的地理查询等。本软件基于MapX组件进行二次开发。2．3路径规划软件实现本软件把西安市路网电子地图数据显示在单文档上，安装MapX、MapInfo及VisualStudio2008开发平台，导入MapX．h和MapX．cpp到工程。其中MapX内置了常用的标准地图工具，例如放大、缩小、平移、选择等，在菜单的单击事件中编写相关的代码即可实现相应的功能。

3路径规划软件功能算法实现

3．1基于Dijkstra算法路径导航功能实现

3．1．1Dijkstra算法简介软件路径导航功能利用Dijkstra算法实现，Dijkstra算法思想［7］：迅速地扩展顶点集S中的每一个顶点v，S中s顶点和v顶点之间的最短路径已经计算出来。顶点集S初始化为｛s｝，在搜索s和v之间最短路径的过程中，S不断扩展，Dijkstra最短路径算法本身便可以寻找距离源点s最短路径的顶点v（v∈V－S），以此类推，顺着顶点v的边，寻找是否存在一条最短路径到达另外一个顶点v2。当处理完v2后，算法通过＜s，v2，v3＞这条路径计算得到s到v2的最短距离。当s扩展到等于v时，算法终止。

3．1．2基于Dijkstra算法路径导航功能实现步骤（a）初始时，S只包含源点，即S＝｛v｝，v的距离为0。U包含除v外的其他顶点，若v与u有边，U中顶点u距离为边上的权，若u不是v的出边邻接点，u距离无穷大。（b）从U中选取一个距离v最小的顶点k，把k加入S中（该选定的距离就是v到k的最短路径长度）。（c）以k为新考虑的中间点，修改U中各顶点的距离；若从源点v到顶点u的距离（经过顶点k）比原来距离（不经过顶点k）短，则修改顶点u的距离值，修改后的距离值的顶点k的距离加上边上的权。（d）重复步骤第（b）步和第（c）步直到所有顶点都包含在S中。

3．2基于粒子群算法路径规划功能实现

3．2．1粒子群算法简介［8－9］设有n个粒子组成的一个粒子群算法，其搜索区域空间为D维，Xid＝（X1，X2，…XD）指粒子i在D维空间中的位置，Vid＝（V1，V2，…VD）指粒子i在D维空间中的飞行速度。Pid为粒子的个体极值，即粒子i在自己的寻优历史中找到的最优解，Pgd是目前为止整个群体中所有粒子发现的最好位置。

3．2．2粒子群算法进行电子地图路径寻优步骤［8－9］（a）在西安市地图4525个节点中选取n个必经节点，初始化粒子个数m（m＜n）、迭代次数Nc、惯性因子c1、学习因子c2等参数。（b）初始化粒子群，每个粒子的位置表示一条路径，粒子的速度表示一个随机交换序。（c）据粒子当前位置计算其下一个位置Xid。计算A＝Pid－Xid，A是一个基本交换序，表示A作用于Xid得到Pid，计算B＝Pgd－Xid，B是基本交换序，根据式（1）计算速度Vid，并将交换序Vid转换为一个基本交换序，根据式（2）计算搜索到的新解。（d）根据路径规划问题的适应度函数M，如式（4），计算每个粒子的适应度值，例如，有10个节点，某个粒子个体适应度值为这10个必经节点的最短距离，将每个粒子的个体适应度值与历史记录中其个体最优值比较，若优于个体最优值，则用此个体适应度值替代个体最优适应度值，同样，把每个粒子的个体最优值与粒子群算法的全局最优值进行比较，若优于全局最优值，则利用个体最优值进行更新。（e）判断当前迭代是否达到最大迭代次数，满足则终止，输出最优解，否则转至步骤（c）。

3．2．3与基于蚁群算法的路径寻优比较路径寻优问题是在给定节点的条件下，找到一条遍历所有节点且每个节点只能访问一次的距离最短的路线。蚁群算法在路径寻优问题应用中取得了良好的效果，但是也存在一些问题：如参数α，β值设置不当，求解速度会很慢且所得解的结果不理想；蚁群算法计算量大，求解时间较长，最优线路是所有的蚂蚁选择同一路线，但实际在给定一定循环数的条件下很难达收敛，如本软件用蚁群算法进行路径规划时在给定1000次迭代下，每次执行出现的结果会不同；蚁群算法收敛速度慢、易陷入局部最优，规划路径不一定是最优路线。为缓解以上问题，采用粒子群算法进行路径规划。粒子群优化算法的基本思想是通过粒子之间的协作和信息共享来寻找最优解，优点在于不用调节过多参数。粒子群算法利用当前位置、全局极值和个体极值，指导粒子下一步位置，每个粒子利用自身经验和群体经验调整自身的状态。粒子群算法可以优化参数，具有相当快的求解速度。实验表明，粒子群算法在给定迭代条件下，得到的规划路径比较稳定，运行时间也较蚁群算法快。

4总结

设计了电子地图路径规划算法软件，对路径规划软件功能及模型进行了介绍，软件实现了电子地图放大、缩小、定位、搜索等功能，基于Dijstrka算法实现了任意两点求解最短距离，基于粒子群算法实现了多节点路径规划。后面对软件功能将进一步完善，为提升软件运行速度，将设计基于云平台的路径规划算法软件。

参考文献

［1］王华东，李巍．粒子群算法的物流配送路径优化研究［J］．计算机仿真，2012，29（5）：243－246．

［2］阮曹华，徐绪忠，李华贵，等．在MapInfo电子地图中搜寻最短路径的实现［J］．微计算机信息，2017（28）：189－180．

［3］彭刚，王艳琴，王涛，等．基于MapInfo与MapX的电子地图［J］．计算机系统应用，2011，20（9）：153－156．

［4］杨斌，叶云霞，刘小勇．基于MapX的组件式GIS集成系统的开发与应用［J］．测绘与空间地理信息，2005（3）：29－32．

［5］刘德利，张亚双．基于MapX的水资源信息查询系统的设计与开发［J］．吉林水利，2006（3）：5－7．

［6］陈先龙，翁勇．基于MapX的GIS－T应用开发实例［J］．交通与计算机，2003（4）：72－74．

［7］潘开灵，董晶晶．基于Dijkstra算法的物流运输最短路径的研究［J］，中国集体经济，2011（28）：121－122．

［8］黄岚，王康平，周春光，等．粒子群优化算法求解旅行商问题［J］．吉林大学学报（理学版），2003，10（41）：77－480．

［9］吴高超．基于粒子群算法的路径规划问题研究［D］．秦皇岛：燕山大学，2016（5）

作者；王磊；杨思燕 单位：陕西广播电视大学信息与智能技术学院