许向阳，吴泽华

（河北科技大学，河北 石家庄 050000）

0 引 言

随着社会经济的飞速发展，城市规模不断扩大，车流量越来越大，带来的交通问题越来越严重，给一些用于紧急工作的车辆带来了极大不便，如急救车、警车和消防车等。在这些车辆执行任务时，时间就是生命。因此，在这些车辆执行任务时，为任务车规划一条最优路径，必将提高其工作效率，减少财产损失，保障人们的安全[1]。将科技融入到实际生活是科技发展的必经之路。随着地理信息系统（GIS）的不断发展，越来越多与地理相关的行业开始结合GIS来提升自己在本行业的影响力。地理信息系统是专门为地理数据和空间数据诞生的，在处理地理模拟、空间网络分析等方面具有很大优势。网络分析是GIS的一个重要功能，而路径规划是网络分析的一个重要应用[2]。将GIS的路径规划功能与消防行业相结合，可以提高消防作业的效率。

目前，对于消防与GIS结合的研究中，路线规划仍是研究重点[3]。路线规划研究的本质是研究最优路径算法[4]，常用的经典最优路径算法有Dijkstra算法、A*算法、蚁群算法和Floyd算法等。这些经典的最优路径算法都有不足，如Dijkstra算法不能解决带负权值的图，如果处理的数据量较大，可能需要邻接表；A*算法不能保证找到最优解；蚁群算法在数据量非常大时，容易陷入局部最优解，且算法执行时间长、复杂度高等。基于这些算法的局限性，本文提出在蚁群算法的基础上优化，使其能够更好地应用于现实生活。

1 系统设计

1.1 系统需求分析设计

为了加强对消防工作的管理，提高消防工作效率，实现智能消防模型，为了达到智能消防的目的，系统需要进行消防设施信息的存储；为了提高消防出警效率，提高消防资源利用率，系统需要提供消防决策的功能；同时，系统应该提供可视化工具，来对智能消防的规划结果进行展示。

1.2 系统整体架构

根据系统的需求分析，可设计系统包含以下模块：用户登录模块、数据管理模块、出警决策辅助模块、网络分析模块和结果展示模块。系统总体架构如图1所示。

图1 系统总体架构

1.3 道路因素分析

结合实际生活中的道路影响因素，提出以下几种关键影响道路通行概率的影响因素，包括路段总通行概率P、遇到交通管制的概率P1，发生交通事故的概率P2，由于人为因素产生的交通拥堵概率P3，由于天气原因导致的交通拥堵概率P4。综上所述，影响道路通行的总概率P为：

其中，在遇到交通管制情况下，P1为0＜P1＜1；发生交通事故时，P2为0＜P2＜1；由于人为原因产生的交通拥堵概率0＜P3＜1；由于天气原因导致的交通拥堵概率为0＜P4＜1。如果没有上述原因的干扰，则路段的总通行概率P=1。道路因素对路段通行概率情况如图2所示。

图2 道路因素对道路通行影响

1.4 系统关键技术

网络数据集是进行交通网络分析的数据基础，由网络元素组成。网络元素的本质是要素集，要素集的几何信息是用于建立网络的连通性，且网络元素的属性可以约束网络中被运输网络对象的运输路径。基本的网络元素可以划分为三种，分别是边要素、节点要素和转弯要素。边要素与节点要素相连，是资源流动的纽带；节点要素连接边要素，引导目标从一条边到另一条边移动；转弯要素用来记录在两条边或多条边之间运动的信息。其中，边要素和节点要素是网络的基本结构。网络数据集的创建有两种方式：一种是基于ShapeFile文件，利用该文件创建的网络数据集仅支持单模式的网络分析；另一种是基于地理数据库GeoDatabase，利用地理数据库创建的网络数据集可以支持多模式网络分析。单模式与多模式的区别在于出行方式的不同。多模式包括不同类型和级别的道路，可提供更多的出行手段。

2 蚁群算法

2.1 经典蚁群算法模型

蚁群算法是由蚂蚁搜索食物的过程演变而来的。算法的基本思想如下：蚂蚁在搜索食物的过程中，会在路过的道路上留下一种叫信息素的物质；因为蚂蚁在找到食物的周围和在家的周围释放的信息素浓度最多，所以蚂蚁会根据信息素浓度的大小来确定自己的行进方向，因此蚂蚁群体会表现出正反馈的特征。道路上信息素浓度越多，蚂蚁选择该道路的概率越大。随着某条道路上信息素浓度的不断增加，这条道路上通过的蚂蚁也越来越多，最优路径随之产生[6]。

该算法的基本流程如图3所示。

图3 蚁群算法流程

基本蚁群算法模型如下：每只蚂蚁经过一条路径后，会对该路径上的信息素进行更新，假设整个蚁群的蚂蚁总量为m，当前蚂蚁的编号为k，t时刻边(i, j)上的信息素浓度为Δτij(t)，蚂蚁k每经过一次迭代信息素更新量为Δτkij(t)，其中信息素更新量按照式（2）进行更新：

Q为信息素总量，为一个常数；Lk为当前蚂蚁本次迭代过程中经过的总距离。经过多次迭代后，t时刻道路(i, j)上的信息素总量为：

蚂蚁更新信息素后，道路上信息素会以不同的速度挥发。信息素的挥发公式为：

τij( t + n )为经过n时刻后道路(i, j)上的信息素浓度，ρ为信息素衰减因子，范围为(0,1)。

算法运行过程中，每只蚂蚁选择下一个城市不是随机选择的，而是按照式（5）的转移概率公式进行下一个城市点的转移：

为蚂蚁的转移概率，为在运行t个时间周期后道路上的信息素浓度，为启发函数因子。启发函数因子需要设定合适的值，若启发函数因子过大，算法的收敛速度快，容易陷入局部最优解；若启发函数因子过小，算法将找不到最优解[7]。

2.2 改进蚁群算法模型

经典的蚁群算法运行时间长、算法效率较低，算法运行到一定程度后易陷入局部最优的停滞状态。为了避免算法陷入局部最优的停滞，提高算法的运行效率，本文提出修改算法中的几个关键参数，保证在算法可运行状态下提高算法运行效率，解决陷入局部最优解的状态。

算法核心是信息素的更新策略。信息素更新分为局部信息素更新和全局信息素更新，本文将分别对其作出改进。

局部信息素更新改进为：

θ为信息素增加因子，取值范围为(0,1)。当蚂蚁k沿着某条道路(i, j)找到食物时，蚂蚁k会按照式（6）的方式释放信息素。采用该方式可以提高信息素的播撒效率，为第k+1只蚂蚁提供更快的路径选择。

蚂蚁在寻路过程中，道路上的信息素浓度会按照一定速率挥发。若某条道路上的信息素持续挥发至0，蚂蚁将停止向此条路径转移。为了避免蚂蚁陷入局部最优解，将每条道路上的信息素浓度设置在[min，max]之间，并且对信息素挥发引入辅助挥发因子，对全局信息素更新策略作出如下改进：

式（7）中添加参数ω∈(0,1)和γ∈(1,2)。其中，ω为信息素负挥发因子，在一定范围内可以减缓信息素的挥发，为蚂蚁的随机转移概率提供参考；γ为信息素正挥发因子，当蚂蚁预测到自己走过的路程大于起点与目的点的欧几里得距离时，便加快当前道路上的信息素浓度。同时，为了避免算法陷入局部最优，每条道路上的信息素浓度都会维持在一定范围。如果当前道路信息素浓度小于道路信息素浓度下限时，系统会将当前道路信息素浓度置为道路信息素浓度最小值。

在信息素挥发策略中，为蚂蚁提供智能功能。蚂蚁在开始搜索路径之间，先对起点到目的点的欧几里得距离做一个估值D0。蚂蚁寻路开始后，当蚂蚁发现经过的距离D大于D0时，说明当前路径并非最短路径。为了减少算法迭代次数，智能蚂蚁将适当提高当前道路的信息素挥发因子，加快算法运行速度。当蚂蚁发现经过的距离D小于D0时，则降低当前道路信息素挥发因子，以保证算法能够找到最短路径。

改进后蚁群算法的流程，如图4所示。

3 系统实现

3.1 系统开发环境

由于ArcGIS平台对地理数据有很强大的处理能力，且ArcEngine针对C#语言提供了用于实现地理功能的各种接口，故本系统采用VS2010平台结合ArcEngine提供的地理功能接口。地理数据的处理采用的是ArcCatalog，能够实现网络数据集的创建。可以设置网络数据集中的属性如道路连通性、转弯特性等。系统基于C#的可视化应用程序，提供了友好的系统用户界面，功能界面如图5所示。系统主界面主要包括五个模块：文件管理、构建网络数据集、添加网络元素、寻找最优路径和结果分析。如图5所示，左侧导航栏中包括网络节点信息和地理信息；左下角为鹰眼功能展示，可以通过拖动鹰眼的小地图，实现对主地图的查询。

图4 改进蚁群算法流程

图5 系统主界面

利用ArcEngine开发解决最优路径问题的基本步骤如下：

（1）读取shp文件和网络数据集数据；

（2）创建网络分析上下文对象INAContext和网络分析对象；

（3）加载位置停靠点图层，创建网络位置；

（4）设置Solver参数（输出、容差值等）；

（5）进行最优路径分析；

（6）绘制分析结果路线，输出结果信息。

3.2 系统功能介绍

系统整体界面风格，如图5所示，系统各部分功能如下。

文件管理。此模块用于打开工作空间，包括几何网络数据集和逻辑网络数据集。

添加网络元素。此模块用于对所选图层进行网络停靠点的添加，提供网络分析的基础。

最短路径分析。此模块用于解决最优路径问题。清除分析。此模块用于清除网络分析结果。

分析结果显示。此模块用于显示网络分析结果，可以选择采用图表显示和折线显示分析结果。

帮助。此模块提供该系统的帮助文档。

4 试验结果对比

添加信息素更新因子后，t时刻蚂蚁k的信息素更新情况如表1所示。

表1 信息素增加因子对信息素更新的影响

说明：Q为信息素总量，Lk为蚂蚁一次循环经过的路径，θ为信息素增加因子，τijk(t)为t时刻蚂蚁k的信息素更新量，τijk'(t)为增加θ后信息素的更新量。

折线图表示如图6所示。

图6 局部信息素因子对信息素更新影响

实验分析结果表明：添加信息素更新因子θ后，对于信息素更新速率有很大的提高，但是考虑到信息素更新太快，可能会导致算法早熟，以至于未能找到最优路径，因此选取适当的信息素更新因子才可以在保证最优路径的基础上，提高算法效率，通过多次试验发现，当信息素更新因子θ在0.3～0.5范围内时，算法可以在保证最优路径的基础上，提高信息素更新速度。

对于全局信息素更新策略，根据蚂蚁所经过路程不同，采用的不同的信息素更新策略，本实验取信息素挥发因子为0.5，信息素更新量为3.0，根据蚂蚁所经过路程与初始估测值的关系，不同的信息素更新策略如表2所示。

说明：D0为蚂蚁k估测起点与目的点的距离，D为蚂蚁k寻路过程中实际走过的路程，ω为信息素的正挥发因子，γ为信息素的负挥发因子，折线图分别如图7、图8所示。

表2 信息素挥发因子对信息素更新的影响

图7 ω对信息素影响

图8 γ对信息素影响

实验表明：当D＜D0时，信息素更新速度很快，呈指数形式增长，随着蚂蚁走过的路程增加，信息素的更新速度趋于平缓；当D=D0时，信息素的更新速度是原来的2倍；当D＞D0时，信息素开始出现负增长（信息素开始衰减）。为了保证蚂蚁的随机搜索能力，规定每条道路上的信息素浓度有下限。当该道路上的信息素浓度衰减越过该下限时，系统强制将本道路上的信息素浓度置为最小值。通过多次试验分析发现，在蚂蚁寻路过程中，信息素挥发正因子ω=0.5，信息素挥发负因子γ=1.5时，系统的稳定性最好。

5 结 语

本文通过提出智能蚂蚁信息素更新策略，使蚂蚁根据不同距离采用不同的信息素更新策略。仿真结果表明，改进蚁群算法具有优越性。下一步尝试将路径之间的角度参数加入蚁群算法。

[1] Wang Z.A Preliminary Report on the Great Wencluan Earthquake[J].Earthquake Engineering Vibration,2014,7(02):225-255.

[2] Toro-Diaz H,Mayorga M E,Chanta.Joint Location and Dispatching Decisions for Emergency Medical Services[J].Computers & Industrial Engineeri ng,2015,165(05):1917-1928.

[3] Ozdamar L,Demir O.A Hierachical Chistreing and Routing Procedure for Large Scale Disaster Relief Logistics Planning[J].Transportation Research Part E,2012,48(03):591-602.

[4] 高炳楠.基于GIS的应急预案管理系统研究[D].北京:北京交通大学,2011.GAO Bing-nan.Research on Emergency Plan Management System Based on GIS[D].Beijing:Beijing Jiaotong University,2011.

[5] 魏铼,李含伦,刘琦,等.基于GIS和AHP的消防站点规划[J].消防科学与技术,2010,29(09):827-833.WEI Lai,LI Han-lun,LIU Qi,et al.Fire Station Planning Based on GIS and AHP[J].Fire Science and Technology,2010,29(09):827-833.

[6] 陈艳.基于蚁群算法的最优路径选择研究[D].北京:北京交通大学,2007.CHEN Yan.Research on Optimal Path Selection Based on Ant Colony Algorithm[D].Beijing:Beijing Jiaotong University,2007.

[7] 陆锋.最短路径算法:分类体系与研究进展[J].测绘学报,2010,30(03):269-299.LU Feng.Shortest Path Algorithm: Classification System and Research Progress[J].Journal of Surveying and Mapping,2010,30(03):269-299.