鉴于MapX电子地图软件设计及制作

1引言

本软件可作为交通道路电子导航使用，提供高效全面的最短路径规划算法，为智能交通、地理信息系统相关专业的教师、研究人员和高校学生提供可视化路径规划算法教学软件。作为一个全面的电子导航与路径规划路径算法软件，本软件可以实现任意起始点和目的地之间的最短路径计算，可以在指定的节点范围内寻找一条较优路径，实现路径规划目的。该软件操作简单、方便，用户很容易就可以掌握该软件的使用，实现旅游信息的快速查询，给用户带来了方便快捷的信息服务。

2系统设计方案与使用说明

2．1电子地图路径规划软件的设计方案［1～2］

图1基于mapx的电子地图路径规划软件设计方案

2．2电子地图路径规划软件使用说明

点击“地图操作”下拉菜单，弹出“放大”、“缩小”、“平移”、“测距”、“图层管理”几个选项。其中各选项功能如下：

1）放大：在地图上任一位置点击时，地图将以该点为中心放大一倍比例尺显示。

2）缩小：在地图上任一位置点击时，地图将以该点为中心缩小一倍比例尺显示。

3）平移：将光标移至某一位置并在屏幕上拖动，地图将向拖动方向移动。

4）测距：用于计算用户在电子地图上输入一条折线的长度。

5）图层管理：是对图层进行添加、删除、移动和图层属性的控制等。

点击“路径寻优”下拉菜单，单击Dijkstra算法可以求出两点之间最短路径，并以红色轨迹显示。单击“蚁群算法”，可以求出一条有结点约束的最优路径，以红色轨迹显示。

3电子地图路径规划软件的实现［3～4］

本系统实现了基本的电子地图操作功能，软件设计基于MapInfo的组件开发工具MapX平台，使用MapX开发地理信息系统具有简单快捷等优点，它和面向对象语言的结合，使其既能充分发挥管理地图数据的优势，又能使开发者快速生成友好的用户界面。在VisualStudio环境下，把MapX．h和MapX．cpp导入工程，用C＋＋语言实现界面设计及相应算法功能，数据库采用Access2003。

3．1地图操作功能实现

首先在单文档下加载并显示西安市地图，在地图操作中实现放大、缩小、漫游、测距、图层控制等功能，其实现函数分别如下：m＿ctrlMapX．SetFocus（）；m＿ctrlMapX．SetCurrentTool（miZoomInTool）；m＿ctrlMapX．SetCurrentTool（miPanTool）；m＿ctrlMapX．SetCurrentTool（miZoomOutTool）；m＿ctrlMapX．ZoomTo（2，centerX，centerY）；

3．2Dijkstra算法求解最短路径

3．2．1Dijkstra算法［5～6］

运用Dijkstra算法求解最短路径，就是扩展顶点集S中的每一个顶点v，顶点s和v之间的最短路径已经求解出来。顶点集S初始值为｛s｝，在求解s和v之间最短路径的过程中，S始终一直扩展，Dijkstra最短路径算法可以寻找距离起始点s最短路径的顶点v（v∈V－S），同理，沿着顶点v的边继续搜索是否存在一条最短路径到达另一个顶点v2。当v2结点搜索结束后，算法通过＜s，v2，v3＞这条路径计算求出s～v2的最短距离。当s扩展到v点时，算法终止结束。

用Dijkstra算法及蚁群算法求解最短路径后，要用MapX实现路径轨迹显示功能及节点高亮功能。其中Dijk－stra算法主要代码如下：voidCMapShowView：：OnDijkstra（）｛DijDialogm＿dijParameter；m＿dijParameter．DoModal（）；｝轨迹显示主要代码如下：COleVariantvtPoints；vtPoints．vt＝VT＿DISPATCH；vtPoints．pdispVal＝Pnts．m＿lpDispatch；vtPoints．pdispVal－＞AddRef（）；Feature＝FeaFac．CreateLine（vtPoints）；Style＝Feature．GetStyle（）；Style．SetLineColor（miColorBlue）；Style．SetLineWidth（5）；Style．SetLineStyle（65）；Feature．SetStyle（Style．m＿lpDispatch）；feat＝Layer．AddFeature（Feature）；feat．Update（）；

3．2．2Dijkstra功能实现

在对话框中选择起点和终点，如图2所示。图2Dijkstra参数设置地图中选择的起点是“三桥车站”，终点是“田家湾”，路径显示结果图3中黑色路径轨迹所示。图3Dijkstra路径轨迹

3．3蚁群算法求解路径规划

3．3．1基本蚁群算法求解TSP［7～8］

假设存在m个蚂蚁，n个城市节点（mn），把这m个蚂蚁撒在n个城市节点上，使这些蚂蚁按式（1）向前搜索路径，并在路径上撒上定量的信息激素，直到回到起始点，所有的蚂蚁都完成一次循环后本次迭代结束。pkij（t）＝ταij（t）ηβij（t）∑μTabukταiμ（t）ηβiμ（t），jTabuk0，烅烄烆otherwise（1）其中pkij（t）是在t时刻蚂蚁k～i城市转移到j城市的转移概率，Tabuk为蚂蚁k的禁忌表，τij（t）为在t时刻两城市ij之间边上的信息素量，ηij（t）为t时刻由城市i转移到城市j的期望值，TSP问题一般取ηij（t）＝1／dij（dij是ij两城市之间距离），启发因子α是边上积累的信息素的重要程度，启发因子β是蚂蚁选择此条路径的重要程度。每只蚂蚁周游一次后，根据式（2）进行局部更新。τij（t＋n）＝τij（t）＋τ0?ρ（2）式（2）中τ0＝C（C为常数），ρ是信息素激量保留系数。一次循环结束后，进行一次全局更新，把本次迭代后的最优路径上信息素值按式（3）进行更新，经过数次迭代后，最终形成一条较优路径。τij（t＋n）＝ρ?τij（t）＋Δτij（t，t＋n）Δτij（t，t＋n）＝∑mk＝1τkij（t，t＋n）（3）式（3）中ρ是信息素保留系数，Δτkij（t，t＋n）是第k只蚂蚁在时刻（t，t＋n）撒在路径ij上的信息素激量，值按式（4）计算：Δτkij（t，t＋n）＝QLk，蚂蚁k经过ij0，烅烄烆otherwise（4）式（4）中Q为定义好的信息素定值，Lk为第k只蚂蚁周游的路径长度。

3．3．2蚁群算法求解路径寻优流程［9］

1）在西安市地图中随机抽取n个节点，预定义边上的最大信息素值τmax，设Q0初始值为0．1，生成随机数Q∈（0，1），把m个蚂蚁放在n个节点上（mn）。若QQ0，算法保证优先访问必经节点，即如果从当前必经节点i到下一个必经节点j道路联通且转移概率相比其它节点高，蚂蚁按式（1）选择下一节点j；如果从当前必经节点i没有一条道路联通下一个必经节点j，则选择转移概率相比其它节点最高的。若Q＜Q0，每只蚂蚁按式（5）选择下一个节点。s＝argmaxs∈Allowedk｛ταis（t）ηβis（t）｝（5）2）本次迭代结束后算法求出最优路径，置各边上的信息素范围为［τmin，τmax］［12］，按式（2）进行局部更新。3）算法迭代若干次后，判断最优路径在某一个时间段是否有所变化，若有改变，继续迭代执行，按式（3）全局更新；否则迭代结束，保存最优解。蚁群算法算法代码如下：voidCMapShowView：：OnAnt（）｛AntParaDialogantPDlg；antPDlg．DoModal（）；AntParaDialog＊pDlg＝newAntParaDialog（）；pDlg－＞Create（IDD＿DIALOG2）；｝显示代码和Dijkstra算法模块中一样。

3．3．3蚁群算法路径规划功能实现

蚁群算法参数设置如图4所示。图中必经城市为16个，路径显示结果为图5中黑色路径轨迹所示。

4结语

本文对电子地图路径规划软件功能特点以及设计方案进行了介绍，对软件的实现及使用方法也进行了说明。本软件基于MapX平台，实现了西安市电子地图放大、缩小、平移、图层管理、测距等功能。用Dijkstra算法实现了求解地图上任意两点之间最短距离，用蚁群算法实现了交通路网路径规划功能，在必经节点的约束下，求解一条较优路径。