多资源消耗应急系统调度模型及算法

郑 昊， 高 岩

（上海理工大学管理学院，上海 200093）

多资源消耗应急系统调度模型及算法

郑 昊， 高 岩

（上海理工大学管理学院，上海 200093）

结合应急系统多点出救的特征，研究了在资源消耗速率为非负可积函数的情况下，构建基于应急时间最早的连续型应急资源调度模型，并给出相应算法.对模型及所提出的求解算法进行实证研究，结果表明：模型与算法有效，并能对突发事件应急资源调度起到积极的作用.

连续性消耗；多资源；应急资源调度；调度模型

近年来无论是自然灾害、事故灾害还是公共安全灾害，爆发的频率、规模都明显增加，因此，应急系统的设计和管理便显得尤为重要［1］.步入21世纪以来，应急管理得到长足的发展，各种介绍应急系统及其在各行业中应用的文献不断涌现［2-4］.突发的地震、水灾、核泄露等恶性事件发生时，临场快速地给出相关救灾物资调度能极大减少人员伤亡［5］.我国地域辽阔，灾害时有发生，如南方雪灾和四川汶川地震均给国家带来了巨大灾害［6］.这些灾害的特点是受灾点集中、物资需求量大、物资调配复杂，因此需要多个物资储备点同时出救.面对突如其来的灾害，如何快速合理的调度救援物资是一个亟待解决的问题.

当突发性重大自然灾害发生时，往往存在灾害点同时需要调集多种救援设备和物资的现象.目前国内关于应急资源调度的研究大都针对资源消耗速率一定，主要包括多资源组合、多目标规划、模糊优化、连续消耗等方面［7-11］.刘春林等［9］在考虑连续消耗应急系统的一般调运方法的基础上，提出了以最早应急开始时间为目标的固定消耗速率应急资源调度模型及相应的求解算法.赵林度等［10］建立了具有脉冲需求的应急资源调度模型，研究了单目标和二阶段资源调度问题.李梅霞等［11］研究了消耗速率为函数的单资源连续型应急资源调度模型，特别给出了应急时间最早的单资源应急调度模型及算法，并从理论上进行了分析和证明.

国外方面，应急系统的研究起步比较早，相关的研究及应用大量涌现，例如Zografor等［12］研究了基于响应时间最短的适时决策支持系统的公路网事故响应模型；Jae［13］研究了灾害发生时如何分配有限的车辆资源将伤员运送到医院，确保伤员存活率最高；Gulay等［14］提出了一种分层多标准方法解决直升机在救灾中的调度问题，使派遣的直升机和飞行员数目在满足需求的情况下成本最低.

上述研究大都是在考虑资源消耗速率为恒定值时，构建的资源调度模型和算法，但是由于灾害现场伤亡人数往往具有不可预测性，因此应急资源消耗数量也不会简单的为一个恒定值.笔者在以上研究的基础上，构建消耗速率为非负可积函数的连续型多资源应急系统调度模型.该模型以最早应急时间为目标，给出资源调度总方案和最早应急开始时间的求取算法，并通过实证分析验证算法的有效性和实用性.

1 问题描述

设A1，A2，…，An为n个应急资源供应点（出救点）；A为应急地点；x1，x2，…，xm分别为m种应急物资需求量，（xj表示对第j种资源的需求量）；Ai中第j种资源可用量表示为xji（i=1，2，…，n）；vj（y）为第j种资源消耗速率（vj（y）为可积函数，且vj（y）≥0）；sj为第j种资源参与应急的开始时间；fj为其完成时间；（Ai，x）为出救点Ai的资源j的调度方案，即从出救点Ai调度出的第j种资源为；应急物资从Ai到应急地点A的时间为ti（ti＞0），不妨设t1≤t2≤…≤tn.由于救灾工作一般要经历混乱、平稳有序到救灾结束，资源消耗数量应是先增加，然后趋于平衡，最后会逐渐递减，不失一般性，本文以线性连续可积非负函数为资源消耗函数.

对于第j种资源而言，其消耗速率vj（y）为可积函数且vj（y）≥0，则第j种资源的需求量xj满足

因此，本模型研究的应急资源调度问题可以描述为：当A地发生突发事件后，应快速给出一个应急资源调度方案

定义1如果对于总调度方案φ中任意单一资源单资源方案）关于起始时间s是连续可行的，则称总调度方案式（2）关于起始时间s是连续可行的.

设对于第j种资源，起始时间s是连续可行的所有方案的集合为χjs，模型最优解为确定参与应急的出救点及各自的应急物资量，在保证应急物资连续供应的条件下，使得应急开始时间最早，即求解下述问题

2 多资源应急系统调度模型的求解

结合相关问题的描述与假设，给出多资源连续消耗应急资源调度模型的总调度方案和最早应急开始时间的求解，并给出相应的证明.

2.1 调度方案

由定义1知，对于式（2）中任一应急资源jk的方案，文献［7］中给出的性质仍然成立.

2.2 最早开始时间

2.3 求解算法

根据定理1和定理3及相关证明过程，给出多资源应急系统调度模型的总调度方案和对应的最早应急开始时间的求解算法.算法步骤如下：

步骤1比较各应急点应急时间的大小，按照lk的大小从小到大顺序将Ai重新排列；

步骤2对于每种资源的应急需求量

步骤3当j≤m时，重复步骤2，即可求出每种资源对应的单资源方案，进而求出总调度方案φ*；

步骤4具体计算依照文献［11］.计算单一资源应急最早开始时间，即第j种资源应急最早开始时间；

步骤5根据定理2，求得总调度方案φ*对应的最早应急开始时间

3 实证分析

某地A发生严重事故，急需3种应急物资x1，x2，x3.现有A1，A2，A3，A4，A5，A6，A7，A88个物资供应点可以提供物资.采用文献［7］中数据，设事故发生地A对3种物资的需求量分别为x1=20，x2=30，x3=92.各出救点Ai能提供第j种资源的量xji如表1所示，到达A所需要的时间ti如表2所示.

表1 各出救点的物资量及到达时间Tab.1 Arrival time and nu m ber of each relief point

表2 各出救点到达灾害现场场地所需要的时间Tab.2 Arrival time of each relief point to disaster

b.根据算法步骤2，分别算得资源j的单一方案

其中，第一种资源需要6个出救点，分别为A1，A2，A3，A4，A5，A6.第二种资源需要5个出救点，分别为A1，A2，A3，A4，A5.第三种资源需要7个出救点，分别为A1，A2，A3，A4，A5，A6，A7.

当v1（y）=1，v2（y）=2，v3（y）=4时，文献［7］中算例即为本文的一个特例.

4 小 结

在假设应急物资的消耗速率为非负可积函数的情况下，提出了以最早应急时间为目标的多资源应急系统调度模型及相应方案、应急开始时间的求解算法，并利用实证分析验证了算法的有效性和实用性.但是该多资源应急系统调度模型仍存在着不足，首先面对应急环境的紧迫性和不可预测性，各种应急资源的消耗速率函数难以获得.其次，本文所给模型只是建立在以“应急开始最早”的基础上，但是以“应急开始最早”作为目标的方案可能很多，无论从费用或系统稳定性角度，考虑“应急时间最早的前提下出救点数目最少”的二阶段问题更有实际意义.因由于出行车辆的多少直接关系到系统的稳定性和可靠性.因此可以在文中模型的基础上建立“应急开始最早、出救点数目最少”的二阶段应急资源调度模型

φχs此外，在实际应用中，由于应急系统所处环境的多变性，各出救点的应急时间不是一个确定的时间，而是一个区间数，因此如何在应急时间不确定的情况下选择“应急时间最早”的多资源连续型消耗系统方案将是一个有意义的研究课题.

［1］ 陶泽琼，高岩.基于改进目标规划方法的应急系统优化选址模型［J］.技术与创新管理，2012，33（2）：179 -182.

［2］ Liu S.E mploying system of systems engineering in China’s emergency management［J］.IEEE systems journal，2011，5（2）：289-308.

［3］ Tassetto D，Fazl i E H，Werner MA.Novel hybrid algorithmforpassivelocal izationofvictims in emergency situations［J］.International Journal of Satel l ite Com munications and Networking，2011，29（5）：461-478.

［4］ Yang J F，Gao Y.E mergency evacuation model and algorithm in the bui lding with faci l ities［J］.Intel l igent Information Management Systems and Technologies，2012，8（3）：283-292.

［5］ 何建敏，刘春林，曹杰，等.应急管理与应急系统——选址、调度与算法［M］.北京：科学出版社，2005.

［6］ 耿泽飞，胡飞虎，陈慧敏，等.多灾害点应急资源调度模型研究与实现［J］.计算机应用与软件，2010，22（2）：63-66.

［7］ 刘春林，盛昭瀚，何建敏.基于连续消耗应急系统的多出救点选择问题［J］.管理工程学报，1999，13（3）：3 -6

［8］ 戴更新，达庆利.多物资组合应急调度问题的研究［J］.系统工程理论与实践，2000，12（9）：52-55.

［9］ 刘春林，沈厚才.一类离散应急供应系统的两目标优化模型［J］.中国管理科学，2003，11（4）：27-31.

［10］ 赵林度，刘明，戴东甫.面向脉冲需求的应急资源调度问题研究［J］.东南大学学报，2008，38（6）：1116 -1120.

［11］ 李梅霞，车海涛.应急资源调度模型与算法［J］.运筹与管理，2011，20（3）：72-76.

［12］ Zografos K G，Konstantinos N A，George M V.A realtime decision support system for roadway network response logistics［J］.Transportation Research Part C，2002，10（1）：1-18.

［13］ Choi J Y.Stochasticschedul ingproblemsfor minimizing tardy jobs with appl ication to emergency vehicle dispatching on unrel iable road networks［D］. New Yonk：University of New York.2003.

［14］ Gulay B，Linet O，Ahmet C.An interactive approach for hierarchical analysis of hel icopter logisitics in disaster rel ief operations［J］.European Journal of Operational Research，2002，140（1）：118-133.

（编辑：金 虹）

Dispatching M odel and Algorith m for M ulti-resource E m ergency Syste m s

ZHENG Hao， GAO Yan
（Business School，University of Shanghai for Science and Technology，Shanghai 200093，China）

Considering themulti-objective，dynamic，uncertain and time-sensitive features of emergency resource scheduling，the fast reaction time was focused as an important research subject.According to the characteristic of emergency system，themulti-resource emergency systems model with comsumption rates of nonnegative and integrable functions was introduced.A new model was built based on the object of earliest emergency-start-time，and the corresponding algorithm was provided.The results of empirical research illustrate that the model and the algorithm are both effective and play an active role in emergency resource scheduling.They also provide a theoretical support to emergency scheduling decision.

continuous consu m ption；m ulti-resource；emergency source dispatching；dispatching model

N 945.12

A

1007-6735（2013）05-0415-05

2012-12-26

上海市科委资助项目（10550500800）

郑 昊（1987-），男，硕士研究生.研究方向：应急管理.E-mai l：zhenghao.87＠163.com

高 岩（1962-），男，教授.研究方向：复杂系统分析与优化.E-mai l：gaoyan＠usst.edu.cn