基于偏好序的多事故应急资源调配弈模型.pdf

ISSN 100020054 CN 1122223N 清华大学学报自然科学版 J Tsinghua U nivSci 资源调配;多事故;博弈理论; N ash 均衡 中图分类号 X 913. 1文献标识码 A 文章编号 10002005420071222172204 Preference-order-based game modeling of multiple emergency resource allocation ZHANG J ing,SHEN Shifei,YANG Rui Center for Public Safety Research, Department of Engineering Physics, Tsinghua University, Beijing 100084, China Abstract Resource allocation is an important issue in emergency decision makingand management.Autilityfunction w itha preference2order was used to describe the efficiency of emergency response and rescue to determ ine resource allocation when multiple emergencies occur si multaneously. The problem was ulated as a non2cooperative complete ination game w ith the solution given by calculating the Nash equilibrium using the open source software Gambit. M ultiple objects, such as accident severity, response time, and rescue reliability were considered.The results show that the model effectively optim izesresourceallocationduring multiple emergencies for emergency decision making support. Key words emergencyresponse;resourceallocation;multiple emergencies; game theory; Nash equilibrium 应急救援行动需要人力资源、 物资与设备、 个人 防护装备等人力、 物力、 财力资源的支持和保障,同 时需要公安、 消防、 交通、 医疗等部门在应急救援的 过程中的通力配合 [1]。 应急资源调配优化问题, 主要 是研究如何通过合理地分配有限的应急资源,及时 有效地进行应急救援行动,尽可能地减少事故所造 成的损失。 目前,国内外针对单一事故应急资源调配问题 的研究包括多资源组合、 多目标规划、 模糊优化、 实 时响应等方面 [2- 4]。考虑到多事故的发生, 特别是发 生时间间隔短、 地理位置相对靠近的多个事故的应 急响应,因涉及到共同的救援物资和力量,则更加凸 显资源调配问题的重要性和复杂程度。在应急救援 物资储备和力量部署一定的条件下,各事故之间必 然存在对稀缺资源的竞争。博弈论作为研究竞争与 冲突条件下决策分析的科学,运用于各领域的资源 调配或最优化问题中 [5], 也为解决该应急资源调配 问题提供了有效方法。Gupta [6]和Shetty[7]将博弈论 方法运用到多个危机事件管理的研究中,取得了初 步成果。 本文在Shetty [7]研究的基础上, 对多事故点、 多 救援点的应急救援资源调配问题的博弈模型和算法 进行了改进,设计了一种基于偏好序的效用函数。 1 应急资源调配的博弈模型 假设信息更新方式和速度满足要求如完备的 应急信息平台 , 使得各事故点都能及时了解发生事 故的数量、 严重程度及可用资源状况等。 该博弈的参 与人为各事故点,针对离散资源的情况,资源调配方 案是有限的。事故后果的灾难性使得各事故点都力 求在最短时间内获得应急资源,以便及时有效地开 展救援行动。 综合以上因素,刻画该应急资源调配问 题为完全信息非合作有限策略博弈。这里的 “非合 作” 是指各事故点着眼于自己的效用,即如何及时应 对各自职责范围内的突发事件,并非各事故点之间 采取不合作的态度或恶意占用资源。 记Ci为事故点,也称为博弈的参与人,i∈ {1, 2,⋯,n};Rj为救援点,j∈{1,⋯,m}。 事故点Ci 所需资源数为Qi,救援点Rj可用的资源数为Aj。这 里的 “资源” 可以是人力资源、 应急物资或救援设备 等,只考虑资源数量,不计具体单位。定义事故点Ci 对应的偏好向量为 Hih1i,h2i,⋯,hm i . 其中hki是该事故点对救援点Rk的偏好程度。定义Li ∈{1, 2,⋯}为事故点Ci的事故严重程度类似于应 急管理中的预警分级 , Li数值越大表示该事故越 严重。 对于不同情况下的应急救援行动,应急资源调 配优化问题的目标可能有所不同。 一般地,要求应急 响应时间最短。考虑到不同的救援点因人员经验或 设备的可靠程度不同而有所差别,在实际中,可能需 要从更有经验和可靠的救援点分派人和物资,到严 重程度更高的事故点进行救援,以保证应急救援的 有效性。这里偏好程度高代表该救援点应急响应时 间短、 人员经验丰富或设备的可靠程度高。 参与人的策略定义为事故点从各救援点获得的 资源组合,记Si为事故点Ci对应的策略集,即 Si {si1,si2,⋯,sigi}, i∈{1, 2,⋯,n}, 并且 sijri1j,ri2j,⋯,rim j , j≤gi . 其中gi为策略集Si中的策略个数,即事故点Ci 对应的资源分配方案的个数;sij表示事故点Ci的第 j策略,rikj是该事故点从救援点Rk分配到的资 源数。 当多个事故点都偏好于从同一救援点分配资 源,而该点的可用资源又无法满足所有事故点的需 求时,则形成多个事故对资源的竞争。 事故点从偏好 程度较低的救援点分配资源需要付出一定代价,如 应急响应时间延长,事故损失加大。 求解合理的资源 调配方案即寻求该博弈的N ash均衡解S 3 ,即策略 组合S 3 {s 3 1,s 3 2,⋯,s 3 n}使得 UiSi,S 3 -i≤UiS 3 , ΠSi≠S 3 i. 其中S 3 -i {s 3 1,⋯,s 3 i- 1,s 3 i 1,⋯,s 3 n}。UiS定义为 策略组合S下参与人Ci的期望效用函数。可以证明 该有限策略博弈的N ash均衡解存在 [8], 为直观表 述,记 Ei {Ei1,Ei2,⋯,Ein} 为该博弈的第i个纯策略N ash均衡解N ash Equilibrium。其中,Eij∈Sj是参与人Cj的策略, j∈{1, 2,⋯,n}。 2 算法与效用函数 步骤1 确定救援点 在多个事故发生后,需要确定各事故的应急救 援资源需求数,并比较资源需求总和与救援点的可 用资源总和。如资源短缺,则需扩大救援区域,增加 救援点直至可用资源总和不小于需求总和,即 ∑ n i 1 Qi≤∑ m j 1A j. 步骤2 生成策略集 采用递归方法生成参与人的策略集,一般地,策 略集包括满足该事故点需求的所有分配方案。为实 现资源的有效利用,策略sij ri1j,ri2j,⋯,rim j需满 足条件 ∑ m k 1 rikj≤Qi, i∈{1, 2,⋯,n}. 即事故点获得的资源总数不超过应急响应实际所需 资源数,避免造成资源的浪费。 当救援点数量或资源数量较多时,过多的策略 数会使得计算量过大而影响计算时间。考虑到最终 调配方案对于每个参与人应是较优策略,可以对策 略集进行简化,适当减少策略数gi。Shetty [7]在论 文中运用了以策略代价为依据对策略集排序的方 法。 然而作为判断策略优劣的变量,对于不同的影响 因素和优化目标,策略代价的计算方法有所不同。 在 本文中定义策略代价为 costsij m ax{h1iri1j,h2iri2j,⋯,hm irim j}, 即同时考虑救援点的偏好程度和从同一救援点获得 的资源数。 步骤3 确定支付矩阵 定义参与人Ci的支付矩阵为 Pi Ui11Ui12⋯Ui1[mi ] Ui21Ui22⋯Ui2[mi ] ω Uigi1Uigi2⋯Uigi[mi ] . 矩阵元素Uikj表示在其他参与人选择策略组合 S-ik时,参与人Ci选择策略sij所获得的效用。其中 S-ik {s1,⋯,si- 1,si 1,⋯,sn}表示除参与人Ci以外 所有参与人的第k策略组合,sj∈Sj,j∈{1,⋯,n}。 策略组合总数由下式求得 mi ∏ j≠i gj , j∈{1, 2,⋯,n}. 3712张 婧,等 基于偏好序的多事故应急资源调配博弈模型 某一特定资源分配方式下事故点获得的效用, 可以理解为由于及时获得资源而减缓的事故损失。 该效用函数是参与人竞争性决策互动的体现,各参 与人对策略的调整是为获得最大的效用。由于应急 资源是稀缺的,任何一个事故点获得救援物资和力 量,意味着其他事故点无法得到这一部分物资与力 量的救援与支持。这种资源竞争关系的存在使得事 故点的效用不仅仅取决于自身的严重程度和所需资 源,还与同时存在的事故数、 严重程度和所需资源数 量有关。 不失一般性,效用函数的设计满足以下原则 某一事故点获得的效用,与得到的资源数以及它对 该救援点的偏好程度成正比,即 Uikj ∑ m q 1 Κqhqiriqj. 其中 Κq为刻画资源需求冲突的变量,如果满足 ∑ n p 1,p≠qr pqkriqj≤Aq,则Κq 0,否则ΚqAq,此时该事故 点的分配方案组合会使得某救援点的资源供不应 求,因而事故点得到负的效用。 即必有事故点不能满 足资源需求以及时开展救援行动,事故超成的损失 加大。 考虑到现实中事故的严重程度可能不同,严重 程度高的事故点常常需要更加迅速有效的救援行动 支持,应具备一定的资源享有优先级。 优先级可以通 过效用函数的改进实现,即 Uikj ∑ m q 1 Λqhqiriqj. 其中Λq的取值体现了与其他事故点相比,事故点Ci 的优先级。如果满足 ∑ n p 1,p≠qr pqkriqjAq,且 ϖu∈ {1, 2,⋯,n}ł{i}使得Lu≥Li,ruqk≠0;那么Λq 0。其中Li是事故点Ci的事故严重程度。 步骤4 求解N ash均衡解 各事故点力求最大化其效用,则N ash均衡为该 非合作博弈的 “解” 的适合定义 [9]。 N ash均衡的多重 性使得针对某一调配问题同时得到多个可行优化方 案成为可能。 3 算例验证 下面讨论和对比不同偏好序和事故严重程度条 件下,非合作博弈资源调配的结果。 仿真计算通过面 向对象的编程方式实现,求解N ash均衡解时运用了 California Institute of Technology开发的计算程序 Gambit [10]。 3. 1 算例1 针对n 2、m 3的情况,即同时存在2个事故 点,共3个救援点同时提供应急救援资源。资源供求 关系见表1。其中Ci是事故点,i∈{1, 2};Rj是救 援点,j∈{1, 2, 3}。Q是事故点所需的资源数,A是 救援点可供的资源数,L是事故严重程度。 表1 算例1事故 资源供求关系 QAL C192 C261 R15 R24 R37 假设各事故点的偏好向量相同,即Hi 1, 2, 3,i∈{1, 2}。这种各事故点偏好序相同的情况可 对应某些与Ci无关的影响因素,如救援点设备的可 靠性和人员的经验等,偏好程度越高表示越可靠或 更具经验,救援行动更加及时有效。 即在获得相同资 源数的情况下,事故点能从偏好程度更高的救援点 获得更多的效用。 通过仿真计算得到该博弈的纯策略N ash均衡 解为 E110, 2, 7, E124, 2, 0. 考虑只存在事故点C1或事故点C2的情况,则每 一事故点的最优方案都是首先从偏好程度更高的R3 处调派应急资源,但两个事故点的同时存在导致出 现对资源的竞争。该调配方案中事故严重程度高的 事故点得到偏好程度更高的应急救援资源的支持, 从全局上便于更有效地开展多个事故的救援行动。 并且考虑到设备组装与人员配合的默契程度,前往 某一事故参与救援的资源尽可能地来自于同一救援 点。 3. 2 算例2 再考虑n 3、m 4,并且偏好序不同的情况。 资源供求关系见表2,相关参数的含义与表1相同。 4712清 华 大 学 学 报自 然 科 学 版2007, 4712 表2 算例2事故 资源供求关系 QAL C121 C231 C331 R11 R22 R32 R43 各事故点的偏好向量H1 1, 2, 3, 4,H2 4, 2, 3, 1,H3 3, 4, 1, 2。各事故点的偏好序不 一致可刻画某些与Ci有关的影响因素,如Ci与Rj之 间的路程,途经道路的交通状况,以及由此导致的不 同应急响应时间等。由于多个事故的存在与偏好序 的不一致使得该资源调配问题复杂程度增加,仅依 靠决策者的经验和直观判断难以有效解决。 该博弈存在两个纯策略N ash均衡解,通过仿真 计算得到。分别为 E110, 0, 0, 2, E120, 0, 2, 1, E131, 2, 0, 0; E210, 0, 0, 2, E221, 0, 2, 0, E230, 2, 0, 1. 由于多个事故的严重程度相当,不存在某一个 事故在资源的分配上享有优先级,则对应急资源形 成完全竞争的形式。 分配结果表明,各事故对资源的 竞争和冲突得到解决的同时,尽可能地满足了获得 各自偏好程度较高的资源的要求。 4 结 论 本文在Shetty [7]对多危机事件研究的基础上, 针对多事故的应急资源调配问题,建立了基于偏好 序的博弈模型,并设计了相应的效用函数和算法。 该 方法通过偏好向量来刻画影响应急救援行动及时性 和有效性的各种因素,并通过设计策略代价和效用 函数兼顾多个优化目标,如应急响应时间,救援可靠 程度,团队合作效率等。仿真计算的结果表明,该基 于偏好序的方法能解决多事故存在时资源需求的冲 突,合理地分配应急资源,同时得到多个事故点的资 源调配方案,为辅助应急决策提供有效支持。 对本文 提出的算法,在计算效率上仍可进行深入研究和优 化;针对更合理更实际的优化目标,设计和改进效 用函数,也是需要进一步研究的问题。 参考文献 References [1]刘茂,吴宗之.应急救援概论应急救援系统及计划[M ]. 北京化学工业出版社, 2004 . L I UM ao,WUZongzi .Generality ofEmergencyand RescueEmergency System s and Planning [M ].Beijing Chem ical Industry Press, 2004.in Chinese [2]Fiedrich F,Gehbauer F,Rickers U.Optim ized resource allocation for emergency response after earthquake disasters [J ].S af ety S cience, 2000, 351 -3 41 -57. [3]刘春林,沈厚才.一类离散应急供应系统的两目标优化模型 [J ].中国管理科学, 2003, 114 27 -31. L I UChunlin,SHEN Houcai .Two2objective optim ization model for discrete emergent supply system[J ].Chin J M anag S ci, 2003, 114 27 -31.in Chinese [4]高淑萍,刘三阳.应急系统调度问题的最优决策[J].系统工 程与电子技术, 2003, 2510 1222 -1224. GAOShuping,L I USanyang.Optimaldecisionfor scheduling problem in emergency system s [J ].S yst Eng and E lectronics, 2003, 2510 1222 -1224.in Chinese [5]席裕庚,王长军.控制、规划和调度问题中的博弈论应用 [J ].中国计量学院学报, 2005, 161 8 -16. XI Yugeng, WANG Changjun. The game theory applications in control, planning and scheduling problem s [J ].J Chin J iliang U niv, 2005, 161 8 -16.in Chinese [6]GuptaU.M ulti2EventCrisisM anagementusing non2cooperative repeated games [D ].Tampa U niv South Florida, 2004. [7]Shetty S R.An event drivensingle gamesolution for resourceallocationina multi2crisisenvironment[D ]. Tampa U niv South Florida, 2004. [8]Nash J.Equilibrium points in n2person games [J ].P roc N ational A cad S ci USA, 1950, 361 48 -49. [9]Nash J.Non2cooperative games [J ].A nnals M ath, 1951, 542 286 -295. [10] M cKelvey R D, M cL ennan A M ,Turocy T L.Gambit SoftwaretoolsforgametheoryVersion0[ZOL ]. 2006201220.http econweb. tamu. edugambit. 5712张 婧,等 基于偏好序的多事故应急资源调配博弈模型