基于双阶段的海上应急物资协同调度模型.pdf

1、基于双阶段的海上应急物资协同调度模型朱雪斌 吕靖【摘 要】为解决单一应急反应基地受物资储备量及运力条件限制无法在第一时间将所需物资一次性运抵事故现场以及后续物资供应不连续的问题，在反应基地物资可集结、多应急反应基地、单事故点的情境下，建立急速响应与连续供应双阶段海上应急物资协同调度模型，并结合双阶段应急物资协同调度特点开发精确解算法求解。结论表明，经应急物资调度任务的情景模擬，算法可即时输出调度策略并针对无解情况给出物资调度修改的策略。该研究可为海上应急物资调度策略的制定提供理论支持。【关键词】海上应急物资;急速响应;连续供应;协同调度;精确解算法0 引 言在应急物资调度问题中，学者大多以响应

2、时间最短或者成本最低作为整个调度周期的调度目标，前者未考虑物资调度各阶段紧迫性的差异，在物资需求紧迫性不强的情况下采用急速响应调度模式，容易造成资源的浪费;后者则会出现事故主体物资需求紧迫性得不到满足的情况。刘春林等1引入了物资连续消耗的概念，将物资消耗以需求/消耗速率的线性关系表示，为本文双阶段调度方法提出了理论基础。王军等2设计了多出救点、多物资储备基地两阶段多层级协同调度模型，并运用贪婪算法求解。宋晓宇等3从物资连续消耗的客观实际出发，将应急点的应急救援过程划分为多个阶段，建立了一个多应急点、多出救点的多目标应急物资动态调度模型，采取宽松策略解决非线性连续消耗应急物资调度问题，为本文涉及

3、的海上应急物资实际调度情况提供了借鉴依据。1 问题描述海上事故的发生具有突发性、事故后果持续时间长的特点。因海域面积广阔、生存环境恶劣，在突发海上事故后，事故主体必须得到及时救助，因此事故点在第一阶段对物资需求有紧迫性;同时，鉴于海洋环境保护及海洋事故处理的其他特性，即使在事态得到控制后，仍需连续供应应急物资以保障事故的后续处理。本文根据海上突发事故的阶段需求特点，对海上应急物资协同调度进行研究。考虑到事故点所属海域内的单一反应基地受到运力、物资储备量的限制，无法实现物资调度的急速响应和连续供应，因此在物资可集结、多应急反应基地、单一事故点的情景下，构建急速响应与连续供应双阶段海上应急物资协同

4、调度模型，并针对模型编译算法，求得双阶段调度方案的精确解。2 模型构建2.1 急速响应阶段调度模型为实现时间最短的调度目标，构建基于多应急反应基地、单一事故点的联合调度模型。该阶段将参与调度的每个应急反应基地的每一次调度标记为一个调度周期，以每一次调度周期内各反应基地执行调度的累计时间最短为目标构建模型，以多应急反应基地点同时调度的模式实现调度时间最短。模型中涉及的参数见表 1。应急物资救援第一阶段最短救援时间 T 对应的目标函数为Tm k=min（T1，T2，T3，Ti）（1）每个反应基地调运 1 次记为 1 个阶段，共有 m 个调度小周期，则第 m k 阶段调度所需时间取全局最优。令截至

5、m k 阶段应急反应基地 i 共参与 n 1 次调度，此时两种计算时间的情景如下：（2）情景（1）：在应急反应基地物资存量充足（xin 1 0）时，该阶段该点进行物资调度花费的累计时间，即上一阶段调运已花费的时间与船舶经由事故点返回应急反应基地并将货物运抵事故点的时间之和。情景（2）：在物资量不足（xin 1=0）的情况下该点集结物资所花费的累计时间，当调度前物资可集结完毕则取 Ti=Tin=Tin 1+ti+ti，否则取 Ti=Tin=tic+ti。利用数学模型对应急物资调度中的实际情形进行描述如下：qin=min（ci，xin 1，X m k+1）（3）xin=xin 1 qin（4）X1

6、m k=X1m k+1 qin（5）qinX1（6）0qinci（7）0qinxi（8）式（3）表示该点进行第 n 次应急物资调度运送的物资量;式（4）表示在每次调度后应急反应基地剩余的物资量;式（5）表示算法中每探索一个新的救援基地后，事故点的应急物资需求量更新一次;式（6）表示参与救援的应急反应基地总的调度量满足第一阶段物资需求量;式（7）、式（8）分别表示每个应急反应基地每次调度的物资量满足该点运力和物资储备量的限制。此时有急速响应阶段物资调度的总耗时 T=max（T1n，T2n，T3n，Tin）。2.2 连续供应阶段调度模型连续供应阶段的目的在于确定物资消耗速率、考虑物资消耗时间，找到

7、满足物资消耗时间的调度方法。令第二阶段物资需求总量为 X2，物资消耗速度为 v，第一阶段争取到的物资消耗时间为 T0=。模型中涉及的参数见表 2。在第二阶段调度中，优先遍历已参与物资调度的点，取满足调运时间限制要求、运力最大的点进行连续调度，则第二阶段经过j 个小周期的调度完成物资连续供应任务。有调度时间限制的目标函数为tj k Tj k+1，k=0，1，2，j 1（9）式（9）表示第 j k 次物资调度需在上一阶段物资调度后允许的最大消耗时间内完成，确保物资连续供应。经过急速响应阶段的物资调度，应急反应基地 i 每个阶段调度物资所需的时间为 tij k。执行应急物资调度的点存在应急物资为 0

8、 和应急物资不为 0 两种情况。（1）当 k=j 1 时，反应基地第二阶段第一次执行调度所需时间为ti1=tij k=（Ti+ti T）+ti（10）在物资量不为 0 的情况下，各应急反应基地第二阶段第一次调度所需时间分两种情况看：当=0 时，表示第二阶段调度开始时所选应急反应基地可立即调运物资，此时该应急反应基地第二阶段初始调度时间为 ti;当=1 时，表示进行第二阶段第一次调度时应急反应基地不满足立即调度的要求，此时该点调运所花费的时间为该点自上一阶段调运开始到返回应急反应基地与第一阶段总耗时的差值，加上应急反应基地前往事故点的时间。ti1=tij k=max（tic，T）T+（Ti+ti

9、 T）+ti（11）式（11）表示物資量为 0 的情况，考虑该点进行物资集结，调运前利用第一阶段调度间隙进行第二阶段的物资集结，存在第一阶段调运期间物资集结完毕和物资无法集结完毕的情况，同时考虑应急反应基地是否可以立即调度的情况。经第一次调度后，第二阶段该点累计调度时间为 Ti=Tij k=ti1，k=j 1。（2）当 kj 1，在物资量不为 0（即物资量充足）的情况下反应基地进行第 j k 次调度的时间为tij k=ti+ti（12）在物资量不足的情况下，应急反应基地进行调度所要花费的时间为tij k=max（T+T+ti），tic（T+T+ti）+ti（13）经第 j k 次调度后，该应急

10、反应基地第二阶段累计调度时间为 Ti=Tij k=Tij k+1+tij k。当应急反应基地物资量不为 0，反应基地第 j k 次调度的物资量为qij k=min（Xij k+1，ci，X2j k+1）（14）Xij k=（Xij k+1 qij k）+（1）X2j k（15）式（15）中：=0 表示应急反应基地物资量为 0，该点集结物资，使该点物资量达到满足物资需求的水平;当=1 表示现阶段物资存量等于上阶段物资存量经本次调度后剩余的应急物资量。Q j k=qij k+Q j k+1（16）Tj k=Tj k+1 tij k+Q i k/v（17）tTj k+T（18）qij kX2（19）

11、qij k 0（20）式（16）表示第二阶段第 j k 次运送到事故点的实际应急物资量等于参与第一阶段调运的应急反应基地运往事故点的运量总和（=0 时参与调度的应急反应基地此次调运满足消耗时间要求，由该点单独调运即可;=1 时应急反应基地第 j k 阶段单独调运将导致物资供应脱节，由其他应急反应基地进行补充调运）。式（17）表示经过 j k 次调度后，事故点物资消耗殆尽的时间更新为应急物资运抵后的消耗时间。式（18）表示参与补充调度的点的调度时间 t 需小于第二阶段物资调度已消耗时间与第一阶段调度所花的时间之和，即确保物资及时运抵事故点，避免物资链断裂。式（19）表示第二阶段物资调度总量需满足

12、第二阶段物资消耗的总需求量。式（20）确保每一个周期均有调度的物资，保证物资调度的一般意义。3 算法实现3.1 应急物资急速响应协同调度算法该阶段算法结合应急反应基地物资量情况初始化（初始化时考虑应急反应基地物资量为 0，物资集结相关参数更新）应急反应基地调度所需时间;取输出时间最短的基地执行调度，结合该反应基地下一次调度是否涉及物资集结、物资集结与调度同时发生的情况，将调度所需时间更新为执行下一次调度花费的累计调度时间，其余参数根据调度、集结情况更新，第一阶段物资需求量更新;将参与调度并更新参数的基地重新放回到资源列表中进行迭代，直至物资需求量为 0、输出时间最短。3.2 应急物资连续供应调

13、度算法该阶段算法按照物资消耗速率计算第一阶段物资调度争取到的最大物资消耗时间，考虑参与第一阶段调度的船舶未返回基地的情况，初始化第二阶段第一次物资调度所需时间;取满足物资消耗时间且运力最大的点进行调度;考虑下一次调度中该基地实际情况（如物资集结，集结与第一阶段、第二阶段整个调运环节同时发生的情况），调度所需时间更新为下一次调度所需时间（并非累计值）;更新物资消耗时间和第二阶段物资需求量;判定该点调度所需时间是否满足下一次物资消耗的时间要求，如是则继续迭代，否则激活补充调度代码，取剩余资源列表中满足时间需求且运力最大的点进行本阶段补充调运，延长下一次调度允许的最大时间;初始点继续迭代，直至需求量

14、为 0，输出调度结果，遇到无解情况提示增加第一阶段物资需求量。4 算例分析本文模拟了某海域发生意外事故，经救援专家测算，第一阶段必须第一时间运抵 X1个单位的应急物资量，初步估计第二阶段需要 X2 个单位的应急物资量。由事故发生后应急反应基地与事故点相关数据（前往时间、返回时间等）可知，算例中应急反应基地相关参数见表 3，模拟见表 4。表 4 中 1 号数据的计算结果见表 5、表 6。由表 5、表 6 可以看出：第一阶段由应急反应基地 与应急反应基地 共同调运，各调运 1 次物资，分别调运 17 个单位和 5 个单位的物资，应急反应基地 用时最长（而不同装备的调度是同时发生的，取其中调度时间最

15、长的基地用时为急速响应阶段最短用时），累计为 4 个单位时间;第二阶段从应急反应基地 开始调运物资，起初调运 11 个单位物资，因时间限制不满足调运需求，同时由应急反应基地 进行补充调运（即在第一阶段调运时安排调运），调运 10 个单位物资;由于此时消耗时间延长，由应急反应基地 进行第 3 次调运，调运 11 个单位物资量;后因应急反应基地 物资量不足且集结后调运不满足时间要求，由应急反应基地 进行第 4、第 5 次补充调运，期间应急反应基地 集结物资。由表 7、表 8 可以看出：第一阶段调运由应急反应基地 调运 6 个单位物资，物资调运所需最短时间为 3 个单位时间;第二阶段无解，算法提示增

16、加第一阶段物资需求量。调整后结果为第一阶段由应急反应基地 调运 14 个单位物资量，第二阶段可由应急反应基地调运 12 个单位物资。运输断裂，此时将第一阶段物资需求调整为 24 个单位，第二阶段物资需求下降为 60 个单位物资。经算法计算，其结果见表 9、表 10。5 结 语本文考虑阶段特点的海上应急物资调度模式提出了双阶段的精确解算法。经验证，算法可根据应急物资需求阶段性特点，输出急速响应与后续连续供应的精确解，为后续研究提供借鉴依据。但算法中将物资量为 0 作为是否调运的阈值，有失实际意义。阈值的选取可确保应急物资调度有效、高效运作，因此海上应急物资急速响应与连续供应双阶段协同调度研究仍可

17、进一步优化。参考文献：1 刘春林，盛昭瀚，何建敏.基于连续消耗应急系统的多出救点选择问题J.管理工程学报，1999（3）：19-22.2 王军，王美蓉，王怡洋，等.基于贪婪算法的水上漂移目标救助物资协同调度方法J.运筹与管理，2014（2）：116-123.3 宋晓宇，王建国，常春光.非线性连续消耗应急物资调度问题研究J.系统工程学报，2017（2）：163-176.收稿日期：2019-12-26基金项目：国家社科基金重大项目（19VHQ012）作者简介：朱雪斌（1995），男，硕士研究生，研究方向为海上应急物流、基于AIS 数据的船舶异常行为分析;吕靖（1959），男，博士、教授，研究方向为交通运输规划与管理