发布时间：2022-04-02 08:42:05
浏览数：
摘 要:
非常规突发事件爆发后, 如何使用不同的运输方式联合调度应急资源就成为急需解决的关键问题。鉴于应急资源在应急资源中心、资源中转站和需求中心之间的调运, 设计了应急资源流转过程模型。 在此基础上, 考虑到多种运输方式的联合调度问题而设计了面向非常规突发事件的应急资源联合调度博弈模型和算法。 针对经典核心法对该模型求解可能出现无解或多解的情况，提出了改进的核心法。 通过应急资源调度的算例分析与比较, 验证了所建模型与算法的有效性和求解结果作为调度策略的优越性。
关键词:非常规突发事件；应急资源；联合调度；博弈模型；优化
中图分类号: TP393.07
文献标志码:A
英文标题
Joint scheduling game model and optimization of emergency resources
英文作者名
YANG Jijun1,2*, XU Chenhua3,4
英文地址(
1.Department of Public Administration, Guangxi Institute of Administration, Nanning Guangxi 530021,China;
2.National Institute of Emergency Management, Chinese Academy of Governance, Beijing 100089,China;
3.School of Economics and Management, Tongji University, Shanghai 201804,China;
4.College of Electrical Engineering, Guangxi University, Nanning Guangxi 530004,China
英文摘要)
Abstract:
After unconventional emergency breaks out, how to use different modes of transportation to coordinately convey emergency resources becomes the main problem. Emergency resources are delivered among emergency resource centers, resource transfer stations and demanding spots (crisis locations). In order to depict the moving of emergency resources, a flow model of emergency resources was designed. Then the cooperative game model and algorithm for emergency resources scheduling were presented in unconventional emergency. In view of the shortcomings of the classic core method to solve the model, the improved core method were put forward. By analyzing and comparing the results of a numerical example of the emergency resources scheduling, the scheduling model and algorithm are availiable and the scheduling strategies based on improved core method are better.
英文关键词Key words:
unconventional emergency; emergency resource; joint scheduling; game model; optimization
0 引言
近些年来，我国各种自然灾害、事故灾难、公共卫生和社会安全等领域的非常规突发事件频频发生，且危害程度越来越大，比如2008年南方大雪灾和“5•12”汶川大地震、2010年玉树“4•14”大地震和舟曲“8•8”特大泥石流灾害、2012年云南彝良“9•7”大地震和甘肃岷县“5•10”特大冰雹山洪泥石流灾害等。这类非常规突发事件的共同特征［1-2］是：其爆发具有不可预测性和突发性；危机的发展具有高度的动态性和不确定性；所造成的结果对社会具有深度的破坏性和危害性。在应对这类非常规突发事件(下文简称突发事件)的过程中，应急资源的快速调度是提高防灾减灾和灾害救助的关键环节，也是衡量政府应急管理能力的重要指标。
目前针对应急资源调度的研究主要集中在以下几个方面：1)应急资源调度在路径或运输时间上的最短问题 ［3-5］；2)在应急时间约束条件下考虑最小费用或最大运量问题［6-7］；3)灾区资源调度路况可靠性问题［8-10］等，这些都是考虑在单一运输方式下对某一特定目标问题进行研究，却忽略了这样一个事实：突发事件发生后，往往需要同时使用诸如航空运输、公路运输、铁路运输或水路运输等多种运输方式把应急资源快速调度到灾区并展开应急救援。因此，构建反映多种运输方式的联合调度模型则更具有实际意义。鉴于博弈论［11］对分析多种运输方式联合调度应急资源的适应性，由此构建基于多种运输方式的应急资源联合调度博弈模型及其算法，为应急资源的快速调度提供决策支持。
1 应急资源流转过程模型
应急资源运输通常会涉及时间、路程、容量和成本等因素，需要精心组织和合理安排，确保应急资源快速、安全地到达指定位置。在应急资源调度过程中，应当遵循快速、安全、可靠和准确的原则，注重应急资源应急价值的实现。一般情况下，应急资源流转网络由应急资源中心、资源中转站和灾区需求中心组成。
应急资源中心的每种资源从起点运送到灾民手中都可能包括多个应急资源中心、资源中转站和需求中心，往往需要同时使用多种运输方式如航空运输、公路运输、铁路运输或水路运输等，由此设计了如图1所示的应急资源流转过程模型。
在图1中，使用了3种运输方式即公路运输、铁路运输和航空运输分别依据不同情况从2个应急资源中心向2个灾点同时调度应急资源，其中2个资源中转站用于资源中转。
图片
图1 应急资源流转过程模型
2 基于多模式分层网络的合作博弈调度模型
2.1 模型假设
在应急资源调度过程中，依据灾区的实际情况，往往需要多种运输方式的相互配合，因而具有合作的性质，用博弈论的语言，各运输方式的相互配合就可认为是合作博弈的，它们博弈的目的是在满足灾区对资源需求的前提下尽量以最小的损失调度资源。为了便于说明问题，在建立应急资源联合调度模型之前作如下假设：
1)为了满足灾区的需求，需要多种运输方式协调来完成。比如在“5•12”汶川大地震中，在救灾“黄金72小时”内，其天气状况是非常恶劣的，当时连降暴雨，同时余震不断，导致大面积山体滑坡，大部分桥梁中断，道路被毁。面对当时严峻的灾害情况，为了及时挽救灾区人民的生命和财产，将其损失尽量降到最低限度，在应急资源调度方面，应急决策者果断采用飞机、轮船和汽车等多种运输方式联合协调调度应急资源，达到了比较好的救灾效果。
2)应急资源中心到资源中转站之间的运输不存在运输损失；中转站到灾区需求中心因受交通路况等因素的影响而存在运输损失；应急资源由资源应急中心直接运到灾区需求中心同样存在运输损失。
3)资源中转站之间进行资源转运不存在损失，若到达资源中转站的应急资源无法运到灾区，则这部分资源全记为损失。
4)根据灾害的类型和严重程度，采用不同的运输方式所导致的资源损失率不一样。就航空运输、水路运输、公路运输等三种运输方式而言，在地震灾害中，使用航空运输直接把救援资源空投到灾区，其速度虽然最快，但受灾区天气状况、地理环境的影响比较大。当地震灾害发生后，灾区往往天气比较恶劣，再加上地形复杂，因此，在这种情况下，与其他运输方式相比较，航空运输最为快捷，但空投应急资源时所导致的损失却是最大的。
2.2 合作博弈调度模型描述
1)运输方式(局中人)。
假设有n种运输方式，应急资源调度中的运输方式构成博弈的局中人集合，可以表示为：N={1,2,…,n}。
2)博弈策略。
在由各种运输方式组建的调度联盟中(联盟用A表示)，其中任意一个调度联盟就构成博弈策略。
3)博弈收益。
对某种特定的运输方式来讲，与其他运输方式的不同组合可以形成不同的调度联盟，这些不同的调度联盟将会产生一定的收益(该支付代表其调度到灾区的资源量)。调度联盟的支付情况可以使用一个收益函数进行描述，记为：P(A)。
4)调度联盟博弈的收益函数
定义1 设N={1,2,…,n}，P(A)是定义在N的一切子集A(调度联盟)上的实值函数，且满足条件：
P(Φ)=0,若A=
P(N)≥∑ni=1P({i}) (1)
则P(A)为该调度联盟的收益函数。
设A,M∈N且A∩M=，调度联盟A能保证得到的最大收益为P(A)，调度联盟M能保证得到的最大收益为P(M)。即使A和M互相不合作的情况下也能取得P(A)+P(M)的收益，如果A∪M满足下式：
P(A∪M)>P(A)+P(M)(2)
则表示收益函数具有超可加性，这在经济学上称为协同效应，即所谓一加一大于二。如果一个由不同运输方式组成的调度联盟不满足超可加性，那么这个调度联盟是低效的。
另外， P(A∪M)=P(A)+P(M)表示了收益函数的可加性。
定理1 n种运输方式合作博弈G={N,(Si)i∈N,(Ui)i∈N,P(A)}的收益函数P(N)具有可加性的充要条件为
P(N)=∑ni=1P(i)(3)
证明
充分性
P(N)=∑ni=1P(i)=∑i∈AP(i)+∑i∈MP(i)+
∑i∈N/(A∪M)P(i)≤P(A)+P(M)+
P(N/(A∪M))≤
P(A∪M)+P(N/(A∪M))≤P(N)
因此，可以得出：P(A∪M)=P(A)+P(M)。
必要性 因为n种运输方式合作博弈G={N,(Si)i∈N,(Ui)i∈N,P(A)}的收益函数P(A)具有可加性，所以可以得到P(N)=∑ni=1P(i)。
定义2 任意的非空的运输方式集合N={1,2,…,n}的子集AN，定义为博弈联盟(Coalitions)。
所有运输方式集合N的全部子集所组成的集合为2N，则2N中的任意一运输方式组合构成一个联盟。
实际上，联盟是指部分或全体局中人组成的集合，需要说明的是，可以把空集作为一个特殊的联盟，所有2N个联盟的全体记为H(N)。联盟一旦形成，该联盟就作为一个整体共同行动，其目的是使该联盟获得的收益最大，所有联盟的最大收益都确定后，整个博弈就完全清楚了。这样，合作博弈就可以用收益函数来描述。
定义3 给定N={1,2,…,n}，n种运输方式的收益函数是定义在2N上的一个实值函数P，其中P(A)表示联盟A通过内部协调不同运输方式的策略所能够得到的最大收益(Payoff)，并满足P()=0。
定义4 给定N={1,2,…,n}和相应的收益函数P，称(N,P)为N上的一个n种运输方式的合作博弈。
采用收益函数来研究n种运输方式合作博弈(N,P)时，实际上是假定了各种运输方式都用相同的效用尺度来衡量他们的收益，同时还假定合作博弈中各联盟的收益P(A)可以按任一方式调配给不同的运输方式即每种运输方式的收益是可以转移的。
定义5 对任意的两个调度子联盟AN和MN，如果满足如下条件，则该博弈称为凸博弈：
P(A)+P(M)≤P(A∪M)+P(A∩M)(4)
对合作博弈中每种运输方式从联盟的收益中所分得的份额，用n维向量组x=(x1,x2,…,xn)来表示，称为支付向量，其中xi(i=1,2,…,n)表示第i种运输方式所得的份额。
定义6 满足
xi≥P({i}); i∈N(5)
∑i∈Nxi=P(N)(6)
的支付向量称为合作博弈G的一个分配，分配的全体记为E(G)。其中，P({i})表示运输方式i单干时的收益；满足式(5)的分配称为个体理性条件，它表明每种运输方式所获得的收益至少与其单干时所得一样多；满足式(6)的分配称为集体理性条件，它表明满足式(6)的分配使联盟中合作成员最大限度地获得了合作带来的好处。
定义7 对任意的两个分配向量x,y，x=(x1,x2,…,xn)，y=(y1,y2,…,yn)，若存在N的任意非空子集A，使得下式成立：
xi>yi; i∈A(7)
∑i∈Axi≤P(A)(8)
则称x关于A优超y，记为xAy。
式(7)表示联盟A中的局中人(运输方式)一致同意选取x而不是y作为调度方案。从优超的概念可知：联盟A中的调度方案不仅要满足个体理性条件，而且还要满足“小联盟”的理性条件。如果“大联盟”提出的调度方案，局中人可以通过形成“小联盟”与之抗争，且具备抗争的实力，则这个“大联盟”的调度方案是无法实现的，从而大联盟就不可能真正形成。
定义8 对于n个人合作博弈(N,P)，分配集P(N)中不被任何分配优超的分配全体，称为核心(Core)［12］。
合作博弈的核心是由下面满足方程(9)和(10)的全体支付向量组成的集合，记为C={N,(Si)i∈N,(Ui)i∈N,P(A)}。
∑i∈Axi≥P(A)(9)
∑i∈Nxi=P(N)(10)
式(9)表明x=(x1,x2,…,xn)提供给A的分配不少于A自身所得的总收益P(A),成为联盟合理性条件。
从核心的定义可知博弈的核心是闭凸集，如果博弈的核心非空，就可以将合作总收益P(N)按照一种合理的方式分配给局中人(运输方式)，使之不仅满足个体理性条件和集体理性条件，同时还满足联盟合理性条件。如果博弈的核心为空，说明没有形成稳定的合作联盟。
5)调度联盟的博弈目标。
应急资源调度的目标是在满足灾区对应急资源需求的情况下，使整体应急资源调度损失最小化，其目标函数定义如下：
f(Ui)=min∑ni=1Ui(11)
3 模型求解算法
对合作博弈模型求解的目的是使多种运输方式相互协调配合，在满足灾区需要的情况下尽量使资源损失最小化。此处采用核心法对所建立的博弈调度模型进行求解。
核心法是在博弈论中出现最早的解的概念，往往把核心中的解作为分配方案时是可行的。按照式(9)和式(10)对合作博弈模型求解的方法就称为核心法。然而采用核心法对合作博弈模型进行求解可能出现无解的情况即博弈的核心为空，则造成调度任务无法分配。针对这种情况，在参考相关文献［13-14］的基础上，采用线性规划中引入松弛变量的思想，在式(9)中引入一个松弛变量Z(此处Z称为补偿变量)构成如下线性规划问题来对模型求解。
minZ (12)
s.t.xi≥P({i}); i∈N
∑i∈Axi≥P(A); AN
∑i∈Nxi+Z=P(N)
补偿变量Z的作用是确保使用改进核心法求解的支付向量唯一，这就可以作为联盟成员即各运输方式之间进行资源调度任务公平合理分配的依据。补偿变量Z在线性规划模型(12)中可能出现下列三种情况：
① 当Z=0时，式(12)有唯一解，这时核心存在且唯一，可作为公平、合理的任务调度分配方案，记为x1=(x11,x12,…,x1i,…,x1n)；
② 当Z>0时，式(12)有无穷多个解。从当前联盟总任务P(N)中减去Z单位的调度任务，就能保证式(12)的解的唯一性，此时的解记为x2=(x21,x22,…,x2i,…,x2n)；
③ 当Z<0时，式(12)无解，说明博弈的核心为空，此时的调度任务不能进行公平合理分配，这就需要从联盟调度总任务中加上Z单位的虚拟调度任务，以便保证式(12)有唯一解，把此时的解记为x3=(x31,x32,…,x3i,…,x3n)。
第②和③种情况中的Z统称为联盟中不可分摊任务，对这种不可分摊任务可采取的解决办法是联盟中不可分摊任务Z以局中人已分配的调度任务与局中人单干时的调度任务差值的比例进行分配，下面对上述两种情况分别进行处理：
针对第②种情况，局中人i在联盟中不可分摊任务Z应担当的份额为：
x2#i=x2i－P({i})∑ni=1(x2i－P({i}))Z(13)
此时局中人i总的调度任务为：
xi=x2i+x2#i(14)
针对第③种情况，局中人i在联盟中不可分摊任务Z应担当的份额为：
x3#i=x3i－P({i})∑ni=1(x3i－P({i}))Z (15)
此时局中人i总的调度任务为：
xi=x3i－x3#i(16)
在核心唯一存在的前提下，该分配方案是最公平的，这就是核心分摊法最为显著的优点。核心分摊法具有明确的物理意义即在核的范围内公平地向各局中人分配合作任务，使得所有子联盟的净收益(子联盟成员分得的合作收益之和减去该联盟的自身合作收益)尽可能保持平衡。
4 算例分析
以某地区发生地震灾害为例。由三种运输方式T1(公路运输)、T2(水路运输)、T3(航空运输)把应急资源从应急资源中心c运到灾区需求中心d,全体局中人集合记为N={T1,T2,T3}；e, f,g为资源中转站，它们之间进行资源转运不存在资源损失。假设 T1、T2、T3的调度损失率分别为10%，5%，15%，应急资源中心需要调度的资源量为100个单位，各运输方式的调运量如图2所示。
图片
图2 多模式应急资源调度网络图
设三种调运方式承担的任务分配向量为x=(x1,x2,x3)。先按照模型(12)求解，即求解下面的线性规划：
minZ
x1≥19x2≥37x3≥26x1+x2≥64x1+x3≥45x2+x3≥73x1+x2+x3+Z=100 (17)
求解线性规划式(17)得：
x*1=22.643，x*2=47.030，x*3=30.327
即x*=(22.643,47.030,30.327)，Z*=0。
再考虑资源调度损失，调度到灾区的资源量为：
P=22.643×(1-10%) + 47.030×(1-5%)+30.327×(1-15%)=90.84
其资源调度损失总量为：
fCore=100-90.84=9.16
从求解结果显示，线性规划式(17)存在唯一解即x*=(22.643,47.030,30.327)，此时资源调度损失最小即为fCore=9.16。而作者在文献［15］中采用Shapley 值法求得资源调度损失为fShapley=9.25，其误差如下。
绝对误差：σ=fShapley-fCore=9.25-9.16=0.09
相对误差：σ′=0.099.25×100%≈1%
5 结语
通过上述比较分析可知：1)两种算法求解结果的相对误差不足1%，说明改进核心法对该模型求解是有效的；2)采用改进核心法求得的结果作为应急资源调度方案时所造成的资源损失更小(fShapley=9.25>fCore=9.16)，说明改进核心法对该模型求解具有更佳的优越性，因此可将该方案作为最优调度方案,而把按Shapley 值法求得的结果作为次优调度方案(备选方案)；3)改进核心法一方面克服了经典核心法的不足(采用经典核心法求解可能出现无解或多解的情况)，另一方面也突破了Shapley 值法苛刻的限制条件(采用Shapley 值法［16］的前提条件是一个博弈问题必须同时满足三个公理即有效性公理、对称性公理和可加性公理)，因此改进核心法具有更广的适用性。另外，算例分析也说明了所建模型与算法的有效性和求解结果作为调度策略的优越性。
参考文献:
［1］ XU X, ZHOU S, CHEN X. Conflict eliminating coordination method for emergency decision of unconventional outburst incidents［J］. Control and Decision, 2013, 28(8):1138-1144. (徐选华, 周声海, 陈晓红. 非常规突发事件应急决策冲突消解协调方法［J］. 控制与决策, 2013,28(8): 1138-1144.)
［2］ YANG J, WU Q, XU W, et al. Contingency plans of unconventional emergency based on sequential decisionmaking［J］. Journal of Tongji University: Natural Science, 2010, 38(4): 619-623.(杨继君, 吴启迪，许维胜, 等. 面向非常规突发事件的应对方案序贯决策［J］. 同济大学学报:自然科学版, 2010, 38(4): 619-623.)
［3］ SIGAL C E, PRISKER A, SOLBERG J J. The stochastic shortest path problem［J］. Operations Research, 1980, 28: 1122-1129.
［4］ LINET O, EDIZ E, BESTE K. Emergency logistics planning in natural disasters［J］. Annals of Operations Research, 2004, 129(1/2/3/4): 217-245.
［5］ LONG K, HAN L D, WANG S. Shortest path search in road network with incomplete information［J］. Journal of Computer Applications, 2011, 31(3): 651-654.(龙科军, HAN L D, 王赛政. 路网信息不完备条件下的动态最短路搜索［J］. 计算机应用, 2011, 31(3): 651-654.)
［6］ BARBAROSOGLU G, ARDA Y. A twostage stochastic programming framework for transportation planning in disaster response ［J］. Journal of the Operational Research Society, 2004, 55(1): 43-53.
［7］ YANG J, ZHU C. The optimization on emergency supply transportation based on twostage scheduling model［J］. Journal of Lanzhou Jiaotong University, 2013, 32(1): 133-137.(杨菊花, 朱昌峰. 基于Ⅱ阶段法的应急物资运输路径选择［J］. 兰州交通大学学报, 2013, 32(1):133-137.)
［8］ CHEN A, JI Z. Path finding under uncertainty［J］. Journal of Advanced Transportation, 2005, 39(1): 19-37.
［9］ YANG J, XU W, MIAO C. Relief resources scheduling model based on multimode layer network［J］. Computer Engineering, 2009, 35(10): 21-24.(杨继君, 许维胜, 缪成. 基于多模式分层网络的应急资源调度模型［J］. 计算机工程, 2009, 35(10): 21-24.)
［10］ CHEN S. Emergency resources scheduling problem with variable road network structure ［D］. Changsha: National University of Defense Technology, 2011.(陈森. 基于可变路网结构的应急资源调度问题研究［D］. 长沙: 国防科学技术大学, 2011.)
［11］ OWEN G. Game theory［M］. 2nd ed. New York：Academic Press, 1982.
［12］ DONALD B G. Solutions to general nonzerosum games［M］. Princeton: Princeton University Press, 1959.
［13］ DIAO Z J, LIU G Z, MA J H. Operations research［M］. 3rd ed. Beijing: Higher Education Press, 2007.(刁在筠, 刘桂真, 马建华. 运筹学 ［M］. 3版.北京：高等教育出版社, 2007.)
［14］ YANG J, XU W, WU Q. Application of accumulative fund system based on cooperative games in supply chain［J］. Systems Engineering - Theory and Practice, 2009, 29(3): 63-68.(杨继君, 许维胜，吴启迪. 基于合作博弈的联盟公积金制度在供应链中的应用［J］. 系统工程理论与实践，2009, 29(3): 63-68.)
［15］ YANG J, WU Q, XU W. Cooperative game scheduling of relief resources for unconventional emergency［J］. Systems Engineering, 2008, 26(9): 21-25.(杨继君, 吴启迪，许维胜. 面向非常规突发事件的应急资源合作博弈调度［J］. 系统工程, 2008, 26(9): 21-25.)
［16］ SHAPLEY L S. A value for Nperson games ［M］. Princeton： Princeton University Press, 1953.
上一篇：物流优化策略探析
上一篇：河北省海运业现状及发展建议
如有意见、反馈或投诉等情况，请随时联系我们，我们将会在48小时内给文章处理！
当前位置：
