基于备用覆盖的多目标公共设施选址问题研究

基于备用覆盖的多目标公共设施选址问题研究?

万 波1,2，杨 超1，黄 松1，董 鹏1

(1. 华中科技大学 管理学院, 武汉 430074；2. 江汉大学, 武汉 430056)

摘要： 关键词：

中图分类号：O22 文献标识码：A

WAN Bo, YANG Chao, HUANG Song, Dong Peng

(1.School of Management, Huazhong University of Science & Technology, Wuhan 430074, China;

2. Jianghan University, Wuhan 430056, China)

Abstract: Key words:

1 问题背景

有一类公共服务设施称为应急型公共服务设施，该类设施的作用在于对自然灾害、人为灾害等紧急事件(非常态)做出反应并进行处置。该类设施主要有医疗急救中心(120报警)、消防(119报警)、公安(110报警和122报警)、电力、通信、道路交通等专业工程抢险救援等设施。该类设施的一个显著的特征为“急”，即对时效性要求很高，当突发事件发生时，需要调动一系列公共服务设施来消除和减轻灾害或事故的影响，这要求更多地分散设置应急服务设施，以便在应急救援期间，可动用更多的紧急救援资源。

应急服务设施通常处在三种状态中：（1）在基站中待命；（2）服务中；（3）完成任务后回返中。服务设施可达性是指服务设施不仅处在服务需求的覆盖范围内，还须处在随时可用状态。在上述三种状态中，第二种状态显然是不可用的状态，也就是说服务设施处在被“占用”状态，这时，服务设施需要启用额外的备用(Backup )覆盖，以保证服务设施的可达性。在设计规划应急服务设施容量时，决策者必须充分考虑系统的复杂性，避免出现由于系统“拥挤”，需求区域看似全被覆盖、实际上可能“失防”的现象。

服务设施的可达性要求在需求触发时，系统能够提供数量充足的应急型公共服务设施，并在规定时间内到达现场，以满足应急服务需求。然而，由于受到资金约束，设施数目不可能无限制增加。挖掘系统内部潜能，实行科学管理，尽可能地使设置的应急服务设施具有备用覆盖，是提高系统的调度效率，解决应急型公共服务设施时效性问题的有效途径。

2 相关理论

2.1 备用覆盖

当城市应急服务系统出现拥挤现象时，由于单一覆盖不能保证服务设施提供及时的应急响应，通常需要附近的其他服务设施提供备用覆盖(backup coverage)，保证在单一覆盖设施不可达的情况下，备用覆盖设施可及时予以顶替。备用覆盖的概念见图

收稿日期：2010-05-10

基金项目：国家自然科学基金项目(70871044)

作者简介：万波(1972-)，男，湖北武汉人，博士研究生，主要研究方向：现代管理理论与方法，信息理论与信息系统。

j1 i j2

需求点i在单一覆盖情况下，由服务设施j1提供专属的应急服务。当i点产生服务需求时，如果j1处在空闲状态时，j1可及时地提供响应；如果j1正处在忙碌状态时，不能及时提供响应。在备用覆盖情况下，服务设施j1和j2都覆盖需求点i，在正常情况时，i的服务需求由服务设施j1提供响应，当j1不能及时响应时，由服务设施j2做出应急响应(j1为i的首选设施，j2为i的备用设施)。显然，需求点i的备用覆盖的应急服务设施越多，其服务需求被及时响应的可能性越大。（参考：陈志宗，城市防灾减灾设施选址模型与战略决策方法研究）

2.2 模糊目标规划

选址问题需要综合考虑公平与效益等多种因素，是一项系统工程，因而也是一个多目标决策问题。目标规划GP（Goal Programming）是一种非常有用的多目标决策方法，已经被广泛地应用于求解多个相互矛盾的目标问题。GP 方法最早是由Charnes[3]提出的，其思路为：首先确定各目标的期望值，然后使得目标值与目标期望值之间的偏差最小化，从而求得最优解。但是，GP方法有一个局限性，那就是必须确定目标的期望值。然而，在实际的多目标规划问题中，目标的期望值往往难以精确的确定。鉴于这种情况，模糊集理论[4]被引入到多目标规划问题中来，产生了模糊目标规划FGP（Fuzzy Goal Programming）方法[5]。FGP只需要给出“模糊”的目标期望值，也就是利用模糊集理论中的隶属度的概念，构造各目标的隶属度函数，用隶属度函数来描述各目标与目标期望值之间的接近程度。

一个典型的模糊目标规划问题描述如下：

Zm(xi)?Zm,Zk(xi)?Zk,gj(xi)?bj,m?1,2,...,M, k?M?1,M?2,...,K, j?1,2,...,J,

（1） （2） （3）

xi?0（4）

公式（1）、（2）中的“?”、与“?”分别表示“约小于或等于”和“约大于或等于”，体现了“模糊”

i?1,2...,n.

的含义，（1）式表示第m个目标的目标值允许在Zm的右边一定范围rm内波动，即Zm(xi)??lm,um?，这里um与lm分别代表第m个目标的上下界，即lm?Zm，um?Zm?rm，（2）式表示第k个目标的目标值允许在Zk的左边一定范围pk内波动，（3）式表示第j个不等式约束，（4）式对决策变量进行定义。

对于“约小于或等于”和“约大于或等于”的目标而言，线性隶属度函数定义分别见（5）式与（6）式。

?1ifzm(x)?lm?z(x)?l?muzm(x)??1?miflm?zm(x)?um

um?lm?ifzm(x)?um?0?（5）

?1ifzk(x)?uk?u?z(x)?uzk(x)??1?kkiflk?zk(x)?uk

uk?lk?ifzk(x)?lk?0?（6）

利用Belman和Zadeh的求解方法，可行的模糊解集可通过模糊目标的隶属度函数的交集获得，即：

uF(x)?uZ1(x)?uZ2(x)?...?uZk(x)?min??uZ1(x),uZ2(x),...,uZk(x)??. 对于模糊决策而言，最优决策由隶属度最大的值确定，即

maxuF(x)?maxmin??uZ1(x),uZ2(x),...,uZk(x)??.

x?Fx?FZimmermann将辅助变量λ引入模糊目标规划，建立了经典的FGP（FGP-C）模型：

maxZ??s..tuZ1(x)??,uZ2(x)??,??uZk(x)??,gj(xi)?bj,xi?00???1.该方法虽然将多目标问题转化为单目标问题，便于求解。但该模型无法反映各目标之间的重要程度，Tiwari等给出了加权的FGP（FGP-W），wk表示第k个目标的权重，模型如下：

j?1,2,...,J,i?1,2...,n,maxZ??wk?kk?1ms..tuZk(x)??k,k?1,...,m,gj(xi)?bj,xi?0j?1,2,...,J,i?1,2,...,n,

0??k?1,k?1,...,m.Chen和Tsai给出了带优先级的FGP模型。设有4个目标，其优先级分别为：?1??3,?4??3,?3??2，则带优先级的FGP（FGP-P）模型如下：

4maxZ???kk?1s..tuZk(x)??k,k?1,?,4,gj(xi)?bj,xi?0j?1,2,...,J,

?1??3,?4??3,?3??2,i?1,2...,n,0??k?1,k?1,?,4.3 模型建立与求解算法

3.1 符号含义

本文需要用到的有关符号定义如下： I： 需求点的集合，I?{i|1,?,n}；

J： 设施候选点的集合，J?{j|1,?,k}； R： 覆盖半径；

C： 设施的台套数目约束； wi： 需求点i的需求量；

kj： 定位于j点的单个设施的服务容量； dij： 需求点i到设施点j的距离；

aij： 如果dij?R,则aij?1；否则aij?0； eij： 如果dij?R,则eij?1；否则eij?0； Fi： 如果需求点i被覆盖一次，则Fi =1；否则Fi =0； Si： 需求点i被至少覆盖两次的人口份额；

M： 一个足够大的正数。 同时定义如下的决策变量：

zij： 源于需求点i的需求分配给j点的份额；

yj： 服务设施定位于j点，则yj =1；否则yj =0； xj： 服务设施定位于j点的台套数。 3.2 基于备用覆盖的多目标公共设施选址模型(MPFLMBC)

本文提出了一个基于备用覆盖的多目标公共服务设施选址模型。该模型考虑以下三个目标：一是从传统的最大覆盖角度出发，寻求一次覆盖的人口最大化；二是从备用覆盖的角度出发，要求最大化至少两次覆盖的人口数；三是从非覆盖范围内的设施调试效率角度出发，要求在选址点与需求点超过覆盖距离的情况下，实现系统总的旅行距离之和最小化。模型考虑了设施点的服务能力，系统成本约束等条件。模型如下：

max?wiFi (1)

imax?wiSi

i(2) (3)

ijmin??eijwidijzij

ij Subject to：

?aj?Fi?Si?0,?i?I,

(4) (5) (6) (7) (8) (9) (10) (11) (12) (13) (14) (15)

Si?Fi,?i?I,

?zij?1,?i?I,

jxj?Myj,?j?J, yj?xj,?j?J,

?wz?kx,?j?J, ?y?B,

iijjjijj?xjj?C,

Fi??0,1?,?i?I,

Si?[0,1],?i?I,

zij?[0,1],?i?I,?j?J,

xj?0,xj?Z,?j?J.

其中，(1)式表示最大化至少覆盖一次的人口数；(2)式表示最大化备用覆盖的人口数，即至少覆盖两次的人口数；(3)式表示当选址点与需求点超过覆盖距离的情况下，最小化非覆盖范围内的旅行距离；(4)式确定需求点覆盖距离之内的设施数目；(5)式表示当且仅当首次覆盖存在的情况下才可能有备用覆盖；(6)式表示每一个需求点的需求均得以分配；(7)式表示当服务设施未选址于j点时，其设施台数为零；(8)式表示设施台数为零时，服务设施不会选址于j点；(9)式表示分配给一个设施点的总人口数不超过该点所有设施的服务容量；(10)式表示设施点的数目约束；(11)式表示设施的台套数目约束；(12)式定义了中间变量Yi；（13）式定义了中间变量Ui，表示需求点i被至少覆盖两次的人口份额不一定要求为整数，说明模型允许第二次覆盖为部分覆盖；(14)式、（15）式定义了决策变量。 3.3求解算法

本文利用模糊目标规划（FGP）的方法对基于备用覆盖的多目标公共设施选址模型(MPFLMBC)进行求解。以加权的FGP（FGP-W）为例，将求解算法分成两个部分。第一步求隶属度函数，方法为对每个目标分别利用Lingo软件求出其上下界，即可得每个目标的隶属度函数。第二步将多目标问题利用FGP–W方法转化为单目标模型，然后利用Lingo软件求解。

Step1 求隶属度函数。

（1）求第一个目标的上限u1与下限l1。