CS算法在应急救援中最佳路径的应用研究

郑洪清

摘 要：应急救援中时间是关键，而最佳路径的选择直接影响救援时间。本文在分析影响应急救援的基本因素上，利用随机生成邻接点的编码方式，将布谷鸟搜索算法应用于应急救援路径优化问题。仿真实验表明该方法大大提高了算法的收敛速度和解的质量，为应急指挥中心决策提供了可靠的方法。

关键词：应急救援；布谷鸟搜索算法；最佳路径

DOI：10.16640/j.cnki.37-1222/t.2018.15.213

1 引言

近几年来，自然灾害频发，在灾后，时间就是生命，如何在第一时间到达救灾点进行施救，最佳路路径的选择起着至关重要的作用，它可以最大限度的挽救人的生命和财产。突发事件发生以后，决策人员必须寻求源点到目标点的最佳救援路径，而现代交通的发达也给最佳路径的选择带来困难。因此对它的研究有着重要的理论和实践意义。目前国内外在这方面的研究文献不多，最短路径算法有Dijkstra算法[1]、蚁群算法[2]等算法。各算法有各自的优缺点，譬如Dijkstra算法针对大规模的问题它的运算时间呈指数级增长，而各种仿生智能算法可以快速得到最优解，由于其是一种随机算法，收敛速度慢，解的精確度不高。本文在前人的基础上对影响应急救援的因素进行分析，利用布谷鸟搜索算法（cuckoo search algorithm，CS）进行求解，设计随机生成邻接点的方法产生有效解，大大提高了算法的收敛速度。求得的最佳路径可以为应急救援指挥中心的决策提供有效支持。

2 应急救援最佳路径选择的问题描述

交通路网可以用一个有向图来表示，其中节点集。应急救援能否科学成功地进行实施涉及的因素很多，比如交通的拥挤状态、道路服务水平、车道数和天气状况等。应急救援的任务是迅速到达事故发生地进行施救，救援路径的选择主要考虑救援车辆的行驶时间，因此其目标函数[3]修改为：

（1）

3 改进的布谷鸟搜索算法

3.1 解的表示

布谷鸟搜索算法是一种连续的智能算法，标准的布谷鸟搜索算法所具有的连续编码不能直接用来求解突发事件下应急救援的路径选择问题，因此，构造从鸟巢位置矢量到车辆路线的合适映射是应用布谷鸟搜索算法求解该的问题首要工作。然而，随机生成鸟巢位置矢量并不是一个有效的初始解，救援路线有它固有的起点和终点，而且也无须经过每一个节点，所以，本文采用随机生成邻接点的方法来产生有效解。

4 仿真实验

某地区交通简化示意图如图1所示，其节点坐标如表2所示，交通道路信息如表1所示。设节点1为消防救援队伍的出发点，节点5为医疗队伍的出发点，节点9为事故发生点，此时天气晴朗。为了检测所提出算法的性能，实例运行在处理器为Celeron（R）双核CPU T3100， 1.90GHZ 、内存为2G的PC上，以Matlab R2010a编写代码。参数设置为：种群规模25，总迭代次数为50；（1）式计算公式中、a和b分别取值2、4和0.01；路面状况服务等级，由一级到四级分别赋值为（0.25、0.5、0.75、1）。编程实现改进后的布谷鸟搜索算法，得出如图2所示最佳路径选择的结果，其中的蓝色线表示消防队伍救援的路线图，红线表示医疗队伍救援的路线图。

由图2可以看出消防救援的最佳路径为：1→7→2→ 3→9；其距离为：22.9km，行程时间为：1.8619h，并未选择距离较短这条路线：1→2→3→9；医疗救援的最佳路径为：5→7→2→3→9。其距离为：24.4km，行程时间为：1.9759h；也未选择距离较短这条路线5→6→8→9。实验结果表明算法的有效性，最短路径不一定是最佳路径。

5 结论

本文研究了应急救援最佳路径选择问题，综合考虑了实际交通路网中影响救援车辆行驶的时间，并设计随机生成邻接点的方法来产生有效解，将改进后的布谷鸟搜索算法引入最佳路径搜索中。仿真实验表明所提出的算法大大提高了收敛速度和解的质量，为政府决策部门提供有效支持，为灾后救援争取更多的时间，提高救援效率，从而减小灾后对人们生命财产的损失。由于影响救援车辆行驶的因素很多，如何建立一个合理的模型，开发一款应用软件供决策人员使用，将是下一步研究的方向。

参考文献：

[1]Liang Dai.Fast Shortest Path Algorithm for Road Network and Implementation[R].COMP4905.Carlenton：Carletion University School of Computer Science，2005.

[2]高尚，杨静宇.群智能算法及应用[M].北京：中国水利出版社，

2006.

[3]吴正伟，吉文来，陈伟佳，卢扣.地理信息与物联网论坛暨江苏省测绘学会2010学术年会.

[4]YANG X S，DEB S.Cuckoo search via Levy flights[C]// proceedings of World Congress on nature & Biologically Inspired Computing，India：IEEE Publications，2009：210-214.

基金项目：广西高校科研项目（KY2015YB539）