蚁群算法求解路径时间随机的应急资源调度问题研究

张岳峰，何建敏，孙 艳，刘向东

（东南大学 经济管理学院，南京 211189）

0 引言

随着现代经济的迅猛发展，高节奏的社会生活以及突发事件的日益增多使社会安全承受着前所未有的挑战[1]。针对一些突如其来的紧急事件，若能及时采取应急措施就能尽量避免不必要的人员伤亡和经济损失。然而在这些措施中，最为关键的就是要求制定适当、有效的调度方案使所需资源尽快到达应急地点，以辅助应急活动的尽早进行[2]。方磊等[3][4]在考虑应急系统时间紧迫性的前提下，提出基于系统的费用最小的选址模型和应急限制期下的应急选址模型。汪定伟等[5]提出一种基于灾害发生概率、灾害扩散函数和救援函数的救援中心选址优化的数学模型，并用嵌入启发式遗传算法求解。Ceyhun[6]等人提出一种多目标基于应急车辆—位置覆盖模型，以行程最短为优化目标，为提高后备服务水平尽可能让一辆车服务更多节点。林兴强等[7]把路网可靠性概念引入到车辆路径问题中，建立基于行程时间可靠性的车辆优化调度模型。孙燕、陈森发等[8]利用层次分析法和灰色系统理论提出一种可用于车载系统的根据驾驶员的偏好(要求)选择最优路径的方法。刘春林等[9][10]提出基于“时间最短”、“出救点数目最少”的多目标数学模型。针对应急系统的特点，何建敏等[11]研究了基于单目标、多目标、两阶段问题且有资源数量约束的组合优化模型及快速求解算法。可见，不少学者已经从应急资源地域分布、出救路线选择、应急时间最短或出救点最少等方面作为目标分别进行了研究。

然而，应急资源的调度问题常常需要考虑的因数和目标往往不止一个。尽管也有部分学者考虑到了多目标规划，但一般都没有考虑应急调度的成本问题。藉此，本文将以连续性消耗应急系统为背景探讨路径时间为随机数时应急资源调度的优化问题。首先，从交通工具通过道路的时间变化可能性进行阐述，采用正态分布随机变量刻画路段通行时间的不确定性，并建立道路时间随机条件下时间满意度最大和路径费用最小的多目标资源调度模型。其次，对蚁群算法进行改进，求解模型的非劣解集，并采用TOPSIS方法得到最优解；最后，通过算例验证模型和算法的可行性和有效性。

1 问题描述与模型建立

就一般的交通路网而言，可以采用图论中的赋权图G（或有向图，当存在单行道等情况时）进行简化，将路的端点或者路和路的交叉点用顶点集V(G)表示，相应的路用边集E(G)来表示，边e∈E(G)上的权重集W(G)|(w1,w2)表示通过这条路所需的时间w1和费用w2。那么，该问题就化解为从出救点到事发点的最优路径P*，使得

为了使模型更好地适应现实交通工具的运行情况，假设所有路段的通行时间都是服从正态分布的，并且路段与路段之间的通行时间相互独立。设μ为通过该路段所需时间的均值，σ为标准差，根据经典的正态分布3σ原则，将原来取值于[-∞,+∞]的正态分布随机变量限制在[μ-3σ,μ+3σ](μ-3σ＞0)中。由此可以求解置信度为99.7%的最大满意路径。根据相互独立的正态分布的可加性和区间数的加法法则，整个路径P的通行时间也是一个服从正态分布的区间数。

设网络G中任意一条边e的时间权重为[μ(e)-3σ(e),μ(e)+3σ(e)]，则对 于 任 意 一 条 路 径P，其 时间权重也是区间数

由于[μ-3σ,μ+3σ]是服从正态分布的区间数，其密度函数为：

在网络优化中，若只考虑两点之间的最短路径问题，便转化成最小费用流问题的特殊情形。一般的最小费用流可以写成线性规划的形式，即：

其中，cij表示边(i,j)上单位流量的费用，第一个约束表示从vs流出的净流量为f，第二个约束表示从vd流出的净流量为-f，第三个约束表示除了源点vs和汇点vd外其它点必须遵循流量守恒，第四个约束表示边(i,j)上的流量是非负的并且在容量uij限制内。只要在最小费用流模型下作如下假设：

（1）vs作为源点净流出量为1，vd作为汇点净流出量为-1，其它点的净流出量为0；

（2）当网络中任意两节点存在连接边时，边上的单位流量费用等于边权的值；当任意两节点不存在连接边时，边上的单位流量费用等于一个很大的常数；

（3）各边的容量无限制。

这样，对于上述最小费用流问题实质上可以转化为一个整数线性规划的形式，即：

定义 1 设M=[μ-3σ,μ+3σ]是服从正态分布的区间数，c为给定的实数，M小于等于c的可能度定义为：

定义2如果边e上的通行时间取左端点μ(e)-3σ(e)，在最小费用流模型中即边e上的费用取左端点，以此求得的最小费用流称为乐观最小费用流。

定义3如果边e上的通行时间取右端点μ(e)+3σ(e)，在最小费用流模型中即边e上的费用取右端点，以此求得的最小费用流称为保守最小费用流。

定义4对于给定的费用c，最小费用流值F小于等于c的满意度H(F≤c)定义为T({M≤c})。

显然，满意度函数具有以下性质：

（1）0≤H(F,c)≤1

（2）如果保守最小费用流值小于给定费用c，即：

则H(F0,c)=1，F0即最大满意最小费用流。

（3）如果乐观最小费用流值大于给定费用c，即：

则H(F0,c)=0，无最大满意最小费用流。

最后整个问题的模型可以简化为：

2 基于蚁群算法的模型求解方法

标准的蚁群算法主要是解决TSP（旅行商问题）的，在此基础上许多学者将其进行改进，使其适用于VRP（车辆路径问题）。这两类问题的相同之处在于旅行商或车辆在网络中的某一点出发，最后又回到该点；不同之处在于，旅行商需要经过网络的所有节点，而车辆只需要到达固定的几个客户点。而资源调度问题只考虑运载工具从出救点到事发点的调度问题，如何从事发点回到出救点不在该问题的讨论范围之内。因此本文从以下几个方面对蚁群算法进行改进，使该算法适合多目标的资源调度问题。

在给出多目标资源调度模型的蚁群算法之前，首先对以下符号进行定义：

o为目标，取值为1或2，表示时间或费用；

m为蚂蚁个数；

s为出救点；

d为事件爆发点；

Nk为蚂蚁k当前的可行集；

NCmax为蚁群算法循环最大次数；

为以目标为o的蚁群中蚂蚁k的行走路径；为目标o的边弧(i,j)权重；

为对于目标o而言，边弧(i,j)的能见度(visibility)，即

τij为边弧(i,j)的轨迹强度（intensity）；

式中Q表示蚂蚁所留的信息素大小，为一个常数。

由此可以得到轨迹强度更新的方法：

式中ρ表示轨迹的持久度；

式中，α是轨迹强度的相对重要性；β是能见度的相对重要性。

为了适应该模型的求解，还需要对蚁群算法的过程进行调整。

（1）蚂蚁可行集的设置

蚂蚁可行集是指蚂蚁下一步所有可以行径的节点。若蚂蚁k在节点i处时，则定义该蚂蚁的可行集为Nk(i)，它是节点i的所有后继节点集合。设集合(i)为蚂蚁k关于目标o（时间或费用）到达i点时的行走路径，那么：

（2）目标函数的调整

在确定情况下，问题求解的一个目标是时间最短。而当前该目标变为满意度最大。因此算法的的需要改成满意度。

（3）信息素增加值的调整

（4）蚂蚁进行下一节点选择时，能见度的相对重要性应当适当减少。因为问题的目标不是一次运行的时间最短问题，而是要求所有可行解中时间满意度最大。

根据以上的改进，考虑到应急调度中时间因数的重要性，设计算法时让以时间为目标的蚂蚁群先走。因此设计算法如下。

输入参数：α，β，ρ，m，Q，s，d，NCmax

步骤1：初始化参数nc←1；

步骤2：若nc＞NCmax，转步骤8；否则，令nc←nc+1，={s}，o←1，k←1，转步骤3；

步骤3：若o＞2，更新信息素，转步骤2；否则令k←1，转步骤4；

步骤4：若k＞m，根据m次循环后得到的所有目标函数值更新解集，并令o←o+1，转步骤3；否则令k←k+1，转步骤5；

步骤5：根据和更新集合Nk。若Nk=Φ，宣布蚂蚁k死亡，转步骤4；否则转步骤6；

步骤6：根据和蒙特卡洛方法在集合Nk中选中节点i；

步骤8：删除解集中的劣势解，输出解集；算法结束。

在得到方案的非劣解集后，还需要对方案进行排序选择其中的最优方案。本文采用TOPSIS方法来确定最优方案：设由蚁群算法得到决策矩阵为[X,Y]，其中X=(xi)'；Y=(yi)'；i=1,2,...,m。X表示时间满意度，Y表示费用，即共有m对非劣方案。

（1）无量纲化

（2）确定最优值与最劣值

（3）计算欧氏距离

（4）计算接近度

（5）选取最优方案

选择Ci最大的作为非劣解集中的最优方案。

3 算例分析

图1 时间为正态分布随机数时的城市网络

时间为正态分布随机数时的网络见图1，由此可以得到路径上时间的上限、下限和费用矩阵。令t=180,m=60，NCmax=50,α=0.5,β=1,ρ=0.9,Q=1。采用蚁群算法非劣解见表1。

表1 非劣解集

由此可以得到决策矩阵：

采用TOPSIS方法，可以得到目标集合（0.9182，93）最优，即在该环境下选择路径1-＞4-＞9-＞11-＞14-＞13-＞15是最优的。

4 总结

本文讨论了在路径时间为正态分布的随机数条件下，应急资源的多目标调度问题。主要从以下几个方面进行了研究：（1）考虑到交通工具通过某条道路所消耗的时间是变化的，因此采用正态分布的随机数刻画调度时间的不确定性，并建立时间满意度最大和路径费用最低的多目标应急资源调度模型；（2）设计多目标的蚁群算法，求解路径时间随机的条件下，多目标的应急资源调度模型的非劣解集，并通过TOPSIS方法对蚁群算法得到的方案集进行选优。（3）通过算例验证了模型和算法的可行性和有效性。具有一定的实际运用意义，当还需要考虑其它目标，只要将该目标转换成网络上权重，整合进目标函数,并增加一组蚂蚁种群便可以进行求解。本文的研究和结论也多目标应急调度优化问题提供了进一步研究的思路。

[1]Choi S O.Relative Efficiency of Fire and Emergency Services in Florida:an Application and Test of Data Envel Opment Analysis[J].International Journal of Emergency Management，2005,2(3).

[2]潘郁,余佳,达庆利.基于粒子群算法的连续性消耗应急资源调度[J].系统工程学报，2007,22(005).

[3]方磊，何建敏.应急系统优化选址的模型及其算法[J].系统工程学报，2003,18(1).

[4]方磊，何建敏.城市应急系统优化选址决策模型和算法[J].管理科学学报，2005,8(1).

[5]汪定伟，张国祥.突发性灾害救援中心选址优化的模型与算法[J].东北大学学报（自然科学版），2005,26(10).

[6]Ceyhun A H S I.Fuzzy Mufti-objective Covering-based Vehicle Location Model for Emergency Services[J].Computer&Operational Research，2007,34(3).

[7]林兴强，陈驰，陈景新，任爱珠.基于行程时间可靠性的车辆优化调度[J].交通运输系统工程与信息，2005,5(5).

[8]孙燕，陈森发，亓霞，黄昆鸟.基于灰色系统理论的最优路径选择方法[J].土木工程学报，2003,36(1).

[9]刘春林，何建敏，盛昭瀚.应急系统调度问题的模糊规划方法[J].系统工程学报，1999,14(4).

[10]刘春林，沈厚才.一类离散应急供应系统的两目标优化模型[J].中国管理科学，2003,11(4).

[11]何建敏，刘春林，尤海燕.应急系统多出救点的选择问题[J].系统工程理论与实践，2001,(11).