基于蚁群算法的突发事件应急调度概述

杨祎

【摘 要】 针对突发事件而引起的应急调度目的是为了保证所需资源尽早到达和突发事件损失最小化，本文提出用蚁群算法作为一种智能优化算法来计算出最佳路线。文章概述了蚁群算法，介绍了蚁群优化算法基本流程，评价了它的效果和意义。

【关键词】 突发事件;应急调度;蚁群算法

近年来，突发事件常常发生，当突发事件发生之后，常常因为无法充分地，及时地供应各类资源，比如关于应急资源的库存短缺、车辆在资源调运过程中安排以及调运方式选择不合理等，进而又导致其他各种问题的出现。由于突发事件的紧急性、难预知性以及发生后信息匮乏等特点，使得实现突发事件应急调度的空间效应和时间效应有更多的难度，即应急调度的过程较难实现。蚁群算法作为一种智能优化算发已经在诸多领域取得良好的研究成果。

一、应急资源调度的概述

1、应急资源调度的介绍

应急资源调度是指从资源供应点向资源需求点进行资源调运、资源供给的一个过程。应急资源是突发事件中急需的各类资源，它可以包括人力资源、资金资源、物资资源等等。这些资源在整个突发事件中，又有应急需求点多、需求量大、种类繁多、领域广等特点，故在进行这些资源调度的过程中，我们必须预知资源的布局、优化配置和调度特点，这也是主要的决策问题。

（1）通常情况下，应急调度的弱经济性和时间约束的紧迫性与普通物流调度是以效益为核心的目标是不同的，应急调度问题的场景通常是在有限且紧迫的时间约束条件下将应急救灾物资以最短的时间送达受灾点。也就是在时间最短的条件下寻求最小化运输成本。属于同时追求运输时间最小化与运输成本最小化的多目标规划问题，而其中运输时间最小化是核心目标。

（2）在应急调度的一些场景中，我们无法进行事先精确地预测所需要的救灾物资的种类、数量等，导致了应急调度的不确定性和突发性。

（3）在实际应用中应急调度配送车辆调度是一种非常规性活动。

2、应急资源调度模型的研究

根据问题涉及的范围不同应急调度问题属于复杂的TSP问题（旅行商寻找最佳路线问题），可以在两种基本类型的基础上进行描述。第一类是宏观的应急调度问题，宏观的应急调度问题应用多种运输方式协同合作实现应急物资的调度并且在地理空间上设计广泛。例如“5·12”汶川大地震发生以后，救灾物资需要通过水路、公路等方式援助，甚至有时候需要多种运输方式的协同合作从全国各地甚至全世界调度运输到灾区。另一类是微观应急调度问题，微观应急调度问题调度途径相对单纯，涉及地理空间比较小，例如更小区域的应急物资调度。在宏观调度的调度安排前提下，进行的后续微观应急调度，主要是完成具体的调度物资向各个分散点的转移调度。

在我国，对于全国性的突发事件中的应急调度活动，所有的车辆调度都是由政府临时征用并合理安排调度的。这种情况下，这些车辆都必须在规定时间内完成调度任务，在最短时间内，以最优路径将应急物资送达受灾点，所以在我国研究应急调度问题是十分必要并有现实意义的。

在应急资源调度问题中将车辆路径问题的求解方法进一步简化，充分考虑各个因素，将问题分解成若干个基本问题，对于这些若干个基本问题，再利用成熟的研究方法，进而得到最优解或满意解。目前求解确定性车辆路径问题的主要方法是启发式算法，现代启发式算法在目前的研究成果来看，确实可以找到最优解。这些算法也被统称为智能优化算法，由此可见，将智能优化算法中的一种——蚁群算法引入到求解应急调度模型中是一个可行的方案。

二、蚁群算法的概述

1、蚁群行为的描述

蚁群算法是对真实蚁群行为研究而提出的。1990年Goss S A等做了著名的“非对称双桥”实验对蚁群的觅食行为进行了研究。实验结果证明，蚁群通过某种特殊的引导元素进行路径的选择，最终会选择一条最短路径来完成觅食过程。

蚂蚁群体之所以能具有非常强的适应环境变化的能力，是因為蚂蚁在寻找食物时，它释放了一种其他蚂蚁也能够感觉到的特殊分泌物——信息素，这种信息素在它们经过的路径上释放，进而指导后继蚂蚁的前进方向。当某条路径上经过的蚂蚁数越多，就会留下更多的信息量，后来的蚂蚁也会优先选择信息量多的路径，最终整个蚁群会找出最优路径。

人们正是通过模拟蚁群搜索食物的生物过程，而总结出的一种求解复杂优化问题的启发式算法——蚁群优化算法。这种算法也正是采用的是一种分布式的协同优化机制，蚁群优化算法中的人工蚂蚁群搜索的智能行为——发现最短路径。表现在以下三个方面：

（1）人工蚂蚁在行走时，不会再选择已经走过的路径，如此行为可以理解成人工蚂蚁的行走有记忆性的。

（2）蚂蚁作为群体用信息素作为媒介来进行相互通信，这种方式正是一种协同机制。

（3）在从蚁巢到实物源的寻食过程中，蚂蚁是集群活动的，单只蚂蚁虽然能够找到的一条路径，但很难找到通向食物的较短的路径。随着时间流逝，某条路径的信息浓度会逐渐增高，而后继蚂蚁也会选择信息素浓度高的路径行走，如此就形成一条最短路径。因此蚁群优化算法模型也可以理解成增强学习系统的特例。

图1-1 蚁群优化算法流程图

2、蚁群优化算法基本流程

以TSP为例来说明基本蚁群优化算法的实现步骤，蚁群优化算法的执行过程主要体现在以下几个阶段：（1）初始化阶段，在这个阶段中需要设置运行参数，对于信息素的设置主要是信息素浓度的初始值设置以及它的挥发系数，并且在此阶段需要设置搜索一个循环的终止条件。最后也需要进行蚁群数目的设置;（2）搜索阶段，本阶段是建立在上一阶段基础上的，初始化设置后，蚁群开始搜索的过程都是按照概率转移公式进行的，根据这个公式，计算出移动过程中的城市转移概率;（3）信息更新阶段，此阶段的实现过程都是按照蚁周模型进行的，信息的更新是在每批蚂蚁完成可行性解构建之后进行。具体步骤如图1-1所示。

三、基于蚁群优化算法的应急调度

1、蚁群算法求解车辆路径问题的思考

分析应急调度问题是考虑了车辆的最大载质量限制和单边硬时间窗限制的VRP问题。它要求配送车辆必须在每个受灾点的时间限制之前将救灾物资送达救灾点且累计载质量不能超出最大载质量限制。

应用蚁群优化算法求解应急调度问题时，人工蚂蚁模拟配送车辆成所有受灾点的配送任务，在未完成配送任务的受灾点中，根据概率转移规则找出下一个配送任务且满足单边硬时间窗和车辆的最大载质量限制。在人工蚂蚁执行整个配送任务中，每一只人工蚂蚁都会完成本次所有配送任务后更新信息素，直到整个蚁群完成所有的配送任务，记为一次迭代完成。若没有找到满足条件的配送任务，人工蚂蚁返回配送中心重新完成未完成的配送任务，直到完成所有的配送任务为止。数次迭代后，直到迭代次数达到最大值或者出现了重复路径，则表示迭代可以结束了，由此确定最终搜索到全局最优路径或者近似于最优路径的次优路径。这里的由蚂蚁来完成配送任务只是利用蚂蚁模拟配送路线，在多轮迭代模拟之后可以找到最有路径或者次优路径。

【参考文献】

[1] 刘春林、何建敏、盛昭瀚.应急系统调度问题的模糊规划方法[J].系统工程学报，1999（4）.

[2] 何建敏、刘春林.限制期条件下应急车辆调度问题的模糊优化方法[J].控制与决策，2001.16（3）.

[3] 高淑萍，刘三阳.应急系统调度问题的最优决策[J].系统工程与电子技术，2003.25（10）.

[4] 蒋璐璐.蚁群算法在车辆路径问题中的应用研究[D].西安理工大学，2010.

[5] 詹士昌、徐婕、吴俊.蚁群算法中有关算法参数的最优选择[J].科技通报，2003（05）.

[6] 孙明雪.蚁群算法的改进及其在TSP问题中的应用[D].吉林大学，2006.

[7] 王颖、谢剑英等.一种基于蚁群系统的多点路由新算法[J].计算机工程，2001（01）.