（运筹学与控制论专业论文）广义最大覆盖模型在应急设施选址中的应用研究.pdf

山东大学硕士学位论文 广义最大覆盖模型在应急设施选址中的应用研究 殷代君 山东大学数学与系统科学学院 运筹学与控制论 山东济南2 5 0 1 0 0 中文摘要 应急管理中一项首要的职能就是选择应急服务点的位置，向事故地及时提供 充足的应急资源。例如在城市规划中，决策者往往要决定一些公共紧急服务设施 点的位置，如1 1 0 处警中心、消防大队、急救中心、交通控制点等等，以保证城 市中某些地点发生突发事件时，应急服务设施能在尽短的时间内到达进行服务。 服务点选址决策对于应急管理至关重要，这是因为将应急服务点置于合理的位置， 不仅可以降低成本，而且还能够保证提供应急物资的时效性，从而避免了可能导 致的更大损失。 目前，已有不少研究学者给出了应急设施选址问题的相关模型，包括绝对中 心点模型、中值模型、集合覆盖模型和最大覆盖模型及其各种扩展形式，还有将 排队理论、层次分析法( a x - n ) 和d e a 方法等综合应用到应急设施选址当中，取得 了不少突破性的成果。 本文在应急设施最大覆盖选址模型( m c l p ) 的基础上，将广义最大覆盖模型 应用到应急选址当中，改进了最大覆盖模型中覆盖度二元化的假设，使覆盖度变 为0 l 之间的递减分段函数；并且考虑应急服务中对时间紧迫性的要求，将广义 最大覆盖模型中用距离衡量覆盖水平改为用响应时间衡量，给出了应急设施广义 最大覆盖选址模型( g m c l p ) 。 由于传统的最大覆盖模型假设覆盖度是二元的，这可能导致某些应急点没有 被覆盖到，但实际中应急设施应为所有需求提供服务，不论应急设施到这些点的 时间是否超出了应急限制期。于是，本文将广义最大覆盖模型应用到应急服务设 山东大学硕士学位论文 施选址中，考虑每个应急点f 对应一个多重响应时问集合( 不同响应时间由不同应 急设施产生) ，该集合中的每个响应时间对应一个覆盖水平。因此，可咀将覆盖度 看成随应急点f 到离其最近设施的响应时间的递减分段函数，要求每个应急点，都 能被覆盖，只是覆盖的程度有所不同，在完全覆盖与不被覆盖之间提出了“部分 覆盖”的观点应急设施广义最大覆盖选址模型解决了传统最大覆盖选址模型中 可能导致个别应急地点不能被覆盖的问题，做到了以有限的资源覆盖所有的垭急 点。最后给出了求解该模型的分支定界算法和基于拉格朗日松弛的启发式算法， 井通过一个数值例子说明g m c l p 对m c l p 的改进。 在只考虑响应时间的基础上，本文又综合考虑了设施的处理能力，假设应急 系统由两种不同处理能力的服务设施组成每种设施对应不同的应急限制期，并 给出应急点j 是否被充分服务的标准，在此基础上建立了应急设施选址的双目标规 划模型，包括双目标m c l p 模型与双日标m c l p - g m c l p 模型，最后给出算例比 较两种模型的优劣。 关键词：应急设掩选址，响应时间，覆盖水平，处理能力，广义最大覆盖选址问 题 山东大学硕士学位论文 t h e a p p l i c a t i o n so f g e n e r a l i z e dm a x i m a l c o v e r i n gm o d e l i ne m e r g e n c y f a c i l i t yl o c a t i o np r o b l e m y md a i j u n s c h o o lo f m a t h s y s s c i s h a a d o n gu n i v e r s i t y s l l a l i d o n gj i n a n 2 5 0 1 0 0 t h em o s ti m p o r t a n tf u n c t i o ni ne m e r g e n c ym a n a g e m e n ti st h a tc h o o s i n gt h e p o s i t i o n so fe m e r g e n c ys e r v i c ef a c i l i t i e s s o 邪t op r o v i da b u n d a n te m e r g e n c yr e s o u r c e s i m m e d i a t e l y t ot h ep l a c e sw h e r et h ea c c i d e n t s h a p p e n e d f o re x a m p l e ，i nc i t y p r o g r a m m i n g ，t h ep o l i c y - m a k e ra l w a y sd e c i d ew h e r et oo p e nt h ee m e r g e n c ys e r v i c e f a c i l i t i e ss u c h 雒p o l i c es t a t i o n ，f i r eb r i g a d e ，e m e r g e n c yt r e a t m e n ts t a t i o n , t r a f f i c c o n t r o l i n gc e n t r ea n ds oo n ，t oe n s u r et h a tf o re a c he m e r g e n c yn o d ec o u l db es e r v e db y s o m ef a c i l i 锣鹊s o o n 嬲p o s s i b l ew h e ne m e r g e n c yo c c u r e do nt h i sn o d e s e r v i c ef a c i l i t y l o c a t i o nd e c i s i o ni se x t r e m e l yi m p o r t a n tt oe m e r g e n c ym a n a g e m e n t , f o ro p e n i n g f a c i l i t i e so na p p r o p r i a t es i t e sc o u l dn o to n l yd e c r e a s et h ec o s t , b u ta l s oe n s u r et h a tt h e g o o d s c a nb ep r o v i d e de f f i c i e n t l ys oa st oa v o i dm o r ep o s s i b l ei o s t s s of a r , m a n yr e l e v a n tm o d e l so fe m e r g e n c yf a c i l 酊l o c a t i o np r o b l e mh a v eb e e n p r o p o s e db yr e s e a r c h e r s ，i n c l u d i n ga b s o l u t ec e n t r e - p o i n tm o d e l ，m e d i a nm o d e l ，s e t c o v e r i n gm o d e la n dm a x i m a lc o v e r i n gm o d e la n daw i d ev a r i e t yo fe x t e n s i o n s t h e r e a l s oh a sb e e ns o m ea p p l i c a t i o n so fq u e u e i n gt h e o r y , a n a l y t i c a lh i e r a r c h yp r o c o s s ( a l i p ) a n dd e a ( d a t ae n v e l o p m e n ta n a l y s i s ) m e t h o r di ne m e r g e n c yf a c i l i t yl o c a t i o n , a n d h a v eo b t a i n e dm a n ya c c o m p l i s h m e n t s o nt h eb a s eo f e m e r g e n c y f a c i l i t ym a x i m a lc o v e r i n gl o c a t i o np r o b l e m ( m c l p ) , t h i s p a p e ra p p l i e sg e n e r a l i z e dm a x i m a lc o v e r i n gm o d e li n t oe m e r g e c yf a c i l i t y l o c a t i o n p r o b l e m ，i m p r o v e st h ea s s u m p t i o nt h a tt h ee n v 嗽g ei sb i n a r yi n m a x i m a lc o v e r i n g m o d e l ，a n dc o n s i d e r st h ec o v e r a g ea sad e c r e a s i n gs t e pf u n c t i o nb e u t v e e n0 1 ；i n 1 1 1 山东大学硕士学位论文 a d d i t i o n ，i nv i e wo ft h er e q u e s - t so fu r g e n c ya n de f f i c i e n c yi ne m e r g e n c ys e r v i c e ，t h i s p a p e rr e p l a c e sd i s t i a n c ew h i c hw a su s e dt om e a s u r ec o v e r a g el e v e l si ng e n e r a l i z e d m a x i m a lc o v e r i n gm o d e lw i t hr e s p o n s et i m e ，t h e np r e s e n t sa ne m e r g e n c yf a c i l i t y g e n e r a l i z e dm a x i m a lc o v e r i n gl o c a t i o np r o b l e m ( g m c l p ) a sar e s u l to ft h ea s s u m p t i o nt h a tt h ec o v e r a g ei sb i n a r yi nt r a d i t i o n a lm a x i m a l c o v e r i n gm o d e l ，af e wo fc e r t a i ne m e r g e n c yn o d e sm i g h tn o tb ec o v e r e d h o w e v e r , i n f a c t ，a l lo ft h ee m e r g e n c yn o d e ss h o u l db es e r v e dn om a t t e rw h e t h e rt h et i m e sf r o m f a c i l i t i e st ot h e s en o d e se x c e e dt h er e s t r i c t e dt i m e t h e r e f o r e ，t h i sp a p e ri n t r o d u c e st h e f o l l o w i n gg e n e r a l i z a t i o no f t h em c l pm o d e l ；w ea s s u m et h a tf o re a c he m e r g e n c yn o d e i c o r r e s p o n d sam u l t i p l es e to fr e s p o n s et i m e s ( d i f f e r e n tr e s p o n s et i m ei sg e n e r a t e db y d i f f e r e n te m e r g e n c yf a c i l i t y ) , w i t hc o r r e s p o n d i n gc o v e r a g el e v e l s ，撇s p e c i f i e d ，t h e nt h e d e g r e eo fc o v e r a g ei sa s s u m e dt ob ead e c r e a s i n gs t e pf u n c t i o no ft h er e s p o n s et i m et o t h ec l o s e s tf a c i l i t y , t h en o t i o no f p a g t i a l l yc o v e r e d i sp r o p o s e db e t w e e nf u l lc o v e r e da n d n o tc o v e r e d t h u s ，e s e ho ft h ee m e r g e n c yn o d e i c a nb ec o v e r e dj u s tw i t hd i f f e r e n t c o v e r a g el e v e l s t h eg m c l pm o d e lr e s o l v e dt h ep r o b l e mo f w h i c hc e r t a i nn o d e sm i g h t n o tb ec o v e r e di nt r a d i t i o n a lm c l pm o d e l ，a n dr e a l i z e dc o v e d n ga l ln o d e si nn e tw i t h f i n i t er e s o u r c e s i nt h ee n d ，t h eb r a n c h a n d - b o u n da l g o r i t h ma n dh e u r i s t i ca l g o r i t h m b a s e do nl a g r a n g i a nr e l a x a t i o na r ed e v e l o p e dt os o l v et h em o d e l ，a n dac o m p u t a t i o n a l i n s t a n c ei sp r e s e n t e dt oi l l u s t r a t eh o wg m c l pm o d e lh a si m p r o v e dm c l pm o d e l i na d d i t i o n ，o nt h eb a s eo fr e s p o n s et i m ew h i c hw a sc o n s i d e r e dm e r e l yb e f o r e ，t h i s p a p e ra l s oc o n s i d e r st h ep r o c e s s i n ga b i l i t yo fe m e r g e n c yf a c i l i t y w ea s s u m et h a tt h e e m e r g e n c ys y s t e mc o n s i s t so f t w ot y p e so fs e r v i c ef a c i l i t i e sw i t hd i f f e r e n tc a p a b i l i t i e s ， e a c ht y p eo ff a c i l i t y c o r r e s p o n d ss p e c i f i e dr e s t r i c t e dt i m e s ，a n da l s oc o n s i d e rt h e s t a n d a r dw h e t h e ran o d ei ss e r v e d a d e q u a t e l y a c c o r d i n gt ot h i s , w ee s t a b l i s h d o u b l e g o a lp r o g r a m m i n gf o r m u l a t i o n sf o re m e r g e n c yf a c i l i t yl o c a t i o np r o b l e m ，i n c l u d i n gd o u b l e g o a lm c l pf o r m u l a t i o na n dd o u b l e g o a lm c l p - g m c l pf o r m u l a t i o n c o m p u t a t i o n a lr e s u l t sa g ep r e s e n t e df o rc o m p a r i n gt w ot y p e so f f o r m u l a t i o n s k e yw o r d s ：e m e r g e n c yf a c i l i t yl o c a t i o n ，r e s p o n s et i m e ，c o v e r a g el e v e l ，p r o c e s s i n g a b i l i t y , g e n e r a l i z e dm a x i m a lc o v e t i n gl o c a t i o np r o b l e m 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究所取得的成果。除文中已经注明引用的内容外，本论文不 包含任何其他个人或集体已经发表或撰写过的科研成果。对本文的研 究作出重要贡献的个人和集体，均已在文中以明确方式标明。本声明 的法律责任由本人承担。 论文作者签名：e l 期：川 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同意学 校保留或向国家有关部门或机构送交论文的复印件和电子版，允许论 文被查阅和借阅；本人授权山东大学可以将本学位论文的全部或部分 内容编入有关数据库进行检索，可以采用影印、缩印或其他复制手段 保存论文和汇编本学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者签名：逸鱼盘导师签名： 山东大学硕士学位论文 第一章引言 1 1 问题的提出 长期以来，人类社会的进步常常以其赖以生存环境的不断恶化为代价，其结 果必然是自然或人为灾害的不断增多。当地震、水灾、核泄漏等恶性事件不断出 现在我们周围时，人类对灾害所表现的脆弱和无奈暴露无遗。如何应对突发事件， 是任何国家和社会组织都可能面对的强有力的挑战之一。 2 0 世纪7 0 年代以来，重大事故应急系统受到了国际社会的普遍重视，许多工 业化国家和国际组织都制定了一系列重大事故应急救援法规和政策，明确规定了 政府有关部门、企业、工人、社区在事故应急中的职责和作用，并成立了相应的 应急反应机构。在美国，无论是政府还是民间都建立了不同形式的应急管理机构 以及相应的应急反应体系，这其中最为典型的就是美国紧急事件反应体系和美国 应急管理协会，它们在美国国家安全中发挥了巨大作用。在我国，应急管理不容 忽视。近年来，我国生产安全事故频频发生，伤亡人数居高不下，给人民生命、财产 造成巨大损失，尤其是2 0 0 3 年“非典”的肆虐造成数百人伤亡的事实，暴露了我 国卫生应急防御体系的薄弱。与西方国家相比，我们的不足主要体现在三个方面： 首先在应急管理的投入上远低于其他发达国家；其次在应急系统的应用方面，我 们的技术水平还显得不够成熟；最后在应急管理的研究方面，我国学者这方面的 高水平研究还不多见。众多灾难事件留给我们的思考是，建立我国的应急管理机 制问题是一件刻不容缓的事情。 突发事件处置具有不可预知、突发性、灾难性、时效性要求高的特点。为有 效提高政府对各类灾害事故的应急能力和处置效率最大限度地减少各类灾害事 故带来的危害和损失各大城市及其行业管理部门都急需建立一个统一指挥、规范 有序、科学高效的灾害事故紧急处置体系。一个完整的突发事件处理系统称为应 急管理系统e m s ( e m e r g e n c ym a n a g e m e n ts y s t e m ) 即进行监测、预警、应急准备、 应急响应、恢复评估分析等五个过程的系统。 山东大学硕士学位论文 随着科学的进步，特别是信息化的发展使得我们战胜灾害成为可能，至少， 通过这些信息化手段对其进行应急管理可以在相当程度上降低灾害给人类带来的 巨大损失。近年来，国际学术界非常注重对应急问题的研究，从第一个应急管理 国际组织国际应急管理工程协会( t i 肛m s ) 诞生之日( 1 9 9 4 年) 起，高水平 的研究成果层出不穷。这些成果几乎囊括了从信息获取到应急策略制定的方方面 面，并且广泛运用于森林火灾、地震、矿井坍塌、辐射型废料泄漏事故等具体灾 害领域。这些方面的理论研究和应用实践取得了相当丰硕的成果。但是由于对该 领域的研究尚处在起步阶段，还有许多基础性工作迫切需要进行深入研究，其中 一个主要的方面就是应急服务点的选址问题。 1 2 应急选址的研究内容及发展状况 应急管理最重要的一项职能就是向事故地及时提供充足的应急资源，决策者 首先就面临应急服务点的选址安排问题。服务点选址决策对于应急管理至关重要， 这是因为将应急服务点置于合理的位置，不仅可以降低成本，而且还能够保证提 供应急物资的时效性，从而避免了可能导致的更大损失。如果从服务点的多少来 划分，应急服务点选址决策至少涉及两方面问题：单服务点选址决策问题和多服 务点选址决策问题。 例如在城市规划中，决策者往往要决定一些公共紧急服务设施点的优化选址 问题，如“o 处警中心、消防大队，急救中心、交通控制点等等，以保证城市中 某些地点发生突发事件时，应急服务设施能在尽短的时间内到达进行服务。 s h i e rdr 和d e a r i n gpm 2 1 在1 9 8 3 年讨论了单一设施的优化选址问题，给出 了单设施选址的绝对中心点模型。该模型实质上是寻找网络中到达各个节点距离 均最短的点，即绝对中心点。 w l o d z i m i e r z 3 2 0 0 1 年考虑了应急服务设施选址的双目标模型综合考虑 中心点和中位点目标函数，并将它转化为参数为a 的c e n t - d i a n 单目标模型，并指 出了a 参数的单目标模型应用到一般网络中的缺点。为了避免这些缺点，将它转化 为c h e b y s e h e v 2 参数的单目标模型。这种c h e h y s e h e v a 参数的单目标模型可以产 山东大学硕士学位论文 生所有的p a r e t o 优化解。 方磊，何建敏 4 1 2 e e 3 年在传统的绝对中心点模型的基础上，考虑了应急系统 中的实际情况，即“在满足时间紧迫性的前提下，应急服务设施点到各个应急地 点( 附权重) 的距离”最小。并将单个应急服务设施点模型推广到多个应急服务 设施点的模型。 a d e i a a l y 和j o l l i i a w h i t e 5 考虑从应急设施点到达应急地点之间的最短时间 为随机变量的情况。在此基础上给出了集合覆盖模型【6 】，即对于任何需求地点一 旦发生事故时，距离其最近的服务设施到达应急地点的时间小于或等于一个规定 的值，如何确定服务设施的地址使需要建立的服务设施数目最小。 在传统的确定性集合覆盖模型的基础上，v l a d i m i rm a r i s l l o v ，c h a r l e sr e v e l l e 【7 1 9 9 4 年考虑到服务设施经常处于服务状态的情况，提出了随机性集合覆盖模型。 m a s e o da b a d r i ，a m rk m o r m g y 和c o l o n e la l ia l s a y e d 8 1 9 9 8 年利用目标规 划方法建立了消防站选址的多目标数学模型，该模型不但考虑了传统选址模型的 时间、距离目标，而且还考虑到了与费用相关的目标。 b a d e n s o - d i a z 9 1 9 9 7 年考虑到传统的应急服务设施模型集合覆盖模型规 定所有的应急地点都必须覆盖到，造成城市管理部门没有充足的资源来建立应急 服务设施，提出了m c l p ( m a x i m a lc o v e r i n gl o c a t i o np r o b l e m ) 模型。该模型考虑 在建立应急服务设施现有资源的约束下，如何使最大数量的人口能被覆盖到，并 将该模型应用到西班牙l e o n 省的救护车基地选址中。 l u i s 1 0 1 2 0 0 3 年在m c l p 模型的基础上，提出了h c l p ( h i e r a r c h i c a lc o v e d n g l o c a t i o np r o b l e m ) ，该模型事实上是m c l p 模型的两层推广。 目前，已有不少研究涉及应急系统选址问题，但是应急服务设施地址的选择 涉及的因素极为复杂，如经济因素、技术因素、社会因素、安全因素等。这些影 响因素又可以分成定性因素和定量因素，所以应急服务设施的选址应综合运用定 性和定量分析相结合的方法。方磊，何建敏 2 9 1 将层次分析法( a h p ) 与目标规划 结合，既考虑了选址决策中的各种因素，又解决了具有不同度量单位和相互冲突目标 的多目标决策问题。还有将基于偏好d e a 的方法引入选址模型 3 0 ，采用多个数量指 标进行测量、分析和评估，并综合a i p 方法，使客观分析与主观评价相结合。 山东大学硕士学位论文 1 3 本文的主要内容 o d e db e r m 趼和d m i t r yk r a s s 1 4 于2 0 0 2 年提出了广义最大覆盖选址模型 ( g m c l p ) ，该模型将传统最大覆盖模型中覆盖度二元化的假设变为多元化假设， 在完全覆盖与不被覆盖之间提出了“部分覆盖”的观点。他们将覆盖水平考虑成 随需求点i 到离其最近设施的距离的递减分段函数，要求每个节点，都能被覆盖， 只是覆盖的程度有所不同，而目标依然是使被覆盖节点的总权重达到最大。 但是该模型较多地出现在供应链连锁零售店的选址问题中【1 9 】，而在应急服务 领域用于应急设施选址决策的研究还不多见。因此，本文将广义最大覆盖模型应 用到应急服务设施选址问题中，解决了传统最大覆盖模型中可能导致个别应急地 点不能被覆盖的问题，做到了以有限的资源覆盖所有的应急点。 本文第二章首先介绍了有关应急设施选址的若干模型，如绝对中心点模型、 中值模型、覆盖模型等，并介绍了广义最大覆盖模型：在第三章中给出了应急设 施选址的g m c l p 形式，包括g m c l p 的弱整数规划形式和强整数规划形式，其强 整数规划形式与经典u f l p ( u n c a p a c i t a t e df a e i l i t yl o c a t i o np r o b l e m ) 的形式十分相似， 由于u f l p 模型具有整数友好性，所以对于小规模的问题可以采用整数规划的分 支定界法求解，而对于大规模问题，给出了基于拉格朗日松弛的启发式算法，并 给出算例验证了g m c l p 模型对m c l p 模型的改进；在只考虑应急设施响应时间 的基础上，本文第四章综合考虑了设施的处理能力，假设应急系统由两种不同处 理能力的服务设施组成，每种设施对应不同的应急限制期，并给出应急点f 是否被 充分服务的标准，在此基础上建立了应急设施选址的双目标规划模型，包括双目 标m c l p 模型与双目标m c l p g m c l p 模型，最后给出算例比较两种模型的优劣。 4 山东大学硕士学位论文 第二章应急设施选址中的若干模型介绍 2 1 绝对中心点模型 给定需建立的应急设施数c - 7 以是一个也可以是多个) ，如何选择应急设施 的地点，使任何应急点一旦发生事故，应急服务设施能在最短的时间内到达应急 地点进行服务，即对应典型的p - c e n t e r 问题，可以求解网络图中绝对中心点。 城市是由众多的居民小区和一些特殊部门组成的，如果将它们看成网络中的 顶点，连接它们的道路看成网络中的弧，那么整个应急系统可以抽象为一个无向 图。 给定一无向连续网络g = 矿，毋，其中矿= v ，1 ，2 ， 为g 的点集， e = e 1e 2 ，巳) 为连接g 中各点间的弧集，6 0 。) 为弧p ，的长度。如果弧p ，连接 顶点v ，和，那么弧q 可以表示成口，= ( v ps v 。) ，6 0 ，) f l l 删b ( e ，) = b ( v ，一) 。 g 中的任何两个点聋、y ，d ( x ，j ，) 代表连接x l 篡f f i j y 点的最短路径。因此，d 化，功， j ( v pv q ) 具有以下性质 d ( v f ，功= m i n d ( v ，v ，) + 6 ( v ，n d ( v j ，v q ) + b ( v q ，石) 那么，绝对中心点模型 2 、1 7 可以描述为 m i n m l i l kd ( r ，x ) j j x g 令乙( x ) = 巴登d “，曲，使z 。( x ) 最小的点t 叫作g 的绝对中心点，上述模型 - s ls j ， 实质上就是求网络图的绝对中心点。如果所需建立的应急设施数为p 个，则多个 应急服务设施点的选址模型如下 1 8 翌玺r 彤d p ，k ) 其中d o ，x ，) = m 。；i n 。 d ( v ，) 即求解网络中的p 个绝对中心点。 山东大学硕士学位论文 上述绝对中心点模型仅仅考虑如何确定p 个应急服务设施的位置，以使 m 。a ，xd ( v ，x ，) t d 、化。但是，考虑这样一种情形：某个城市的一个区域根据其地 理位置将该区域划分成”个应急小区，其中某个应急小区坎e 于该区域的边缘地带， 同时该应急小区发生事故的频率很小，按照上述r a i nm a x 的原则来进行设施点选 取，那么至少得有一个服务设施一定接近该小区f ，因而离其他小区就会远，而其 他小区发生事故的频率比较高，这些小区每次发生事故时，该应急服务设施都会 进行应急，从而导致运行费用太大。由于服务设施一旦建立就将长期运营，因此 从从系统的运行费用来考虑，许多学者考虑结合应急点的权重而采用中值模型。 2 2 中值模型 h a k i m i ( 1 9 6 4 ) 最早提出中值问题，中值问题的目标是使所有需求点到设施的 平均权重距离最短( 距离也可用交通、运输时间表示) 。应急问题中最显著的特点 表现为时间的紧迫性。那么，在满足时间紧迫性的前提下，考虑应急服务设施点 到各个应急地点带权重的距离最小更具有实际意义。中值模型可以描述为【4 】 m i n 啊d ，力 f 4 l s t m 嚣d ( v ，x ) z x g h 岛为点i 的权重，代表，发生事故的频率。如果记乙( 善) = 啊d ( v ，曲，则使 z 。( j ) 最小的点工。叫作g 的绝对中位点。若五【o ，z 。o 。) 】，根据绝对中心点的定义， 上述模型就没有可行解；若z 【( x ，) ，+ 叫，根据绝对中位点的定义，那么靠就 是个最优可行解。其实际意义就是将服务设施选址在该网络的绝对中位点。 6 山东大学硕士学位论文 2 3 集合覆盖模型 中值问题的应用非常广泛，但是在某些情况下以降低总运输成本( 总距离) 作 为目标不太适宜。例如在应急设施选址中，城市的消防车、医疗急救车辆要求必 须在特定时间内到达事故现场，此类设施点必须布置在与需求点特定距离之内才 能满足特别的需要。下面考虑另一类问题；对于任何应急地点一旦发生事故时， 距离其最近的应急服务设施到达应急点的时间小于或等于一个规定的值，如何确 定应急服务设施点的地址，使需要建立的设施点的数目最小? 因此，提出了集合 覆盖模型 6 。 集合覆盖模型中考虑了建立服务设施的成本，因此不限定要建立的设施数， 在给定的应急限制期下，其且标方程求在给定时间( 距离) 内满足所有需求的最小 设施建设成本。如果每个设施建设费用相同，那么目标方程即求修建设施的最小数 量。模型描述为 m i n c ， ( 1 ) s j 口口x j2 l v i ( 2 ) x ， o ，l 夥 ( 3 ) 目标方程求设施最小建设费用，c ，为设施建设成本。限制条件( 2 ) 要求所有需 求都必须被特定距寰内的设施满足，其中嘞= ：p p r 嘶( t o - y 一。，勺表示从应急 服务设施点，到达应急点f 之间的最短时间，以表示应急点f 所需要的服务水平。 由于受交通条件等因素的影响，假设白是随机变量 5 。条件( 3 ) 说明如果在j 点 修建设施，x j 为i ，否则为0 。 同时，考虑到如果应急点发生大的灾难或事故时，单个应急设施一般不能满 足应急需求的情况，可以规定当某一应急点，发生事故时，必须到达的应急设施数 h 为以，即约束条件( 2 ) 变形为嘞6 f 。 j ；l 7 山东大学硕士学位论文 应该注意的是此模型没有考虑需求的规模，不论需求多大都可以被设施点满 足。另外，如果边缘的节点有非常小的需求量，那么建造此类设施的投入产出比非 常低，可能会导致系统资源耗费太大。鉴于上述情况，有些学者研究最大覆盖问题。 2 4 最大覆盖模型 当决策者没有足够的资源去满足所有的需求时，他们不得不寻求变通的方法， 即在给定建设投入( 设施数量) 、特定距离条件下，最大化所能满足的需求。在这 种情况下，c h u r c h 和r e v e l l e 等j i l l 提出了m c l p ( m a x i m a lc o v e r i n g l o c a t i o n p r o b l e m ) 模型，该模型不规定所有的应急地点都覆盖到，而是新建立p 个应急服务设施， 以便在规定的时间内，最大可能的人口被覆盖。以下给出m c l p 模型的形式 m a x z = w l y j ( 1 ) 豇 x = p ( 2 ) 弘石，v i j ( 3 ) x ，e o ，1 ) ，v j ， ( 4 ) 弘 o ，l ， v i ， ( 5 ) 式中，- - l ，2 ，m 表示应急地点集，j = l ，2 ，玎) 表示可能建立的应急服务设施 点集；，= ，i “f ，) ，其中表示点f 的应急限制期；w 表示应急地点i 的人 口数。目标方程( 1 ) 求有限资源条件下所能覆盖的最大需求量；约束( 2 ) 表示需 要建立的应急设施数目；约束( 3 ) 表明只有先在，点建立应急设施才能为应急点i 提供服务；( 4 ) 、( 5 ) 是变量的0 一l 约束。 为了解决上述问题，可将集合用变量来表示，即定义下列一个矩阵 _ = ( ) 。，式中吩= l , t f t i ，则上述模型中的约束( 3 ) 可转化为如下形式 山东大学硕士学位论文 y - z a 口_ 。v i e i j - l 其它约束条件均不变。 在忽视各节点需求规模情况下，最大覆盖问题目标方程就被简化为最大化需 求点数量。最早对最大覆盖目题进行深入研究的是r e v e l l e 、1 h i t o 与c a s e 1 2 。 一些研究假设设施提供服务的能力是无限的，即不管需求规模有多大，设施均能 满足。后来c u r r e n t 与s t o r b e c k 1 3 探讨与实际情况更为相符有能力限制问题， 但是他们的文章均没有说明哪些需求点应该被覆盖，哪些点不被覆盖。 2 5 广义最大覆盖模型 最大覆盖选址问题( m c l p ) 无论在理论上还是实践中都已被证明是设施选址 问题最有用的模型之- - 1 1 4 。然而在m c l p 模型中，一个关键的假设是覆盖度是二 元韵即任一节点f 要么被完全覆盖( 如果存在某一设施到f 的距离小于覆盖半径 ，) ，要么完全不被覆盖。这一假设可能会导致某些应急地点没有被覆盖到。但实 际中一些公共部门，如消防队、紧急救护中心，应为所有需求提供服务，不论这些点 是否超出了特定距离r ，否则将会造成更大的损失。例如在火灾应急当中，通过对 我国大量的火灾案例的分析，得出消防队必须在1 5 分钟内到达火场出水，才能有 效地扑救防止火势蔓延f 1 5 】。也就是说，火灾事故的应急限制期为1 5 分钟，只有 到其时间在1 5 分钟内的事故点才能被消防站覆盖，如果用最大覆盖模型来分析， 那么在1 5 分钟以外的点包括1 6 、1 7 分钟的点都将被放弃，显然这是不合常理的。 所以，传统的最太覆盖选址模型在覆盖水平上存在一定的缺陷。 有许多研究学者将覆盖度扩展为多元形式，在完全覆盖与不被覆盖之间提出 了“部分覆盖”的观点。b e n n a n 和k r a s s 1 4 1 将覆盖度设为一个【0 ，1 】之间的非增分 段函数，他们考虑每个节点i 附近有若干设施，而每个设施都会对i 产生一个覆盖 度，这依赖于f 到该设施的距离。所以，每个节点i 对应一个多重覆盖水平集合( 节 点j 被不同程度地覆盖) 。并假设覆盖水平随i 到离其最近设施的距离呈阶段函数递 山东大学硕士学位论文 减。由此给出了广义晟大覆盖选址模型g m c l p ( g c n e r a l i z e dm a x i m a lc o v e t i n g l o c a t i o n p r o b l e m ) 。在g m c l p 模型中t 每个节点，都能被覆盖，只是覆盖的程度有 所不同，而目标依然是使被覆盖节点的总权重达到最大。 假设一个网络g = ( e ) n 是节点集合d 州= 呻，e 是边集合a 每个节点f e 都对应一十救重m 。g 中的任何两个点j 、y ，d ( x ，力代表连接x 点和y 点的最短 距离，则对任意的集台s c g ，点f 到s 的最短距离可以表示成d ( s ，0 = m 姆d ( 0 。 每个节点i 可以被不同水平地覆盖，这依赖于i 到各设施的距离。所以对任 节点i n ，定义七个覆盖半径妒= 0 r , i 2 a 2 0 。对于任一给定的设施选址点集合s 和覆盖水平f s 七，令 n ( s ，) = 口e n i 一4s d ( s ，0 l 是常数，以随机变量 形表示与节点f 有关的现场处理时间和回到中心后的休整时间。则服务时间为 s ：r e , + p d ( x , i ) 在城市应急服务系统中，服务质量用响应时