多目标双重覆盖下的急救中心选址及其狼群算法求解

孙 冉， 张惠珍

(上海理工大学 管理学院， 上海 200093)

1 研究背景

优化急救中心选址可以降低由于急救不及时所导致的死亡率升高，提高院前急救的工作质量，保证患者生命安全，降低病死率和病残率[1]。通过优化急救中心选址和合理安排急救车数量，提高急救系统的运营效率。在实际选址问题中，并非仅要求达到一个最小成本或最短出行距离的目标，同时需要考虑多个目标，并且这些目标可能是互相冲突的，也就是说，一个目标的优化可能会导致其他目标的恶化。在多目标优化中，每组目标值都对应一个解，需要针对每个解得到的一组目标函数进行甄别，选择其中一组表示目标之间最佳权衡的解决方案[2]。根据急救服务的特点以及急救中心的基本条件，急救中心选址既要考虑所能提供服务的最大居民数量，又要考虑建设成本以及运营成本，此外，针对急救车提供的急救服务的特点，还需考虑未能在规定时间内服务到的居民，虽然这类地区较为偏远，但仍需考虑到这些部分的服务需求。因此在模型中加入代表惩罚的一个目标，要求到偏远地区的救护服务也应满足病人的急救需求。因此，本文在这一部分将提出一个考虑双重覆盖的多目标急救中心选址模型，并构造求解该问题的多目标狼群算法，得到多目标较优解。

急救中心选址问题包括确定哪个候选设施开放作为急救站以及在这个救护站应安排多少辆救护车。由于在实际急救车进行急救服务的过程中，急救车的出行时间在急救服务中至关重要，因此需要通过高效的车辆分配和急救站中心布局来确保救援行动的快速响应，考虑出生率的增长和环境增长加快等全球普遍的趋势，在满足当前需求的基础上，对未来人口数量和就医需求进行预测，将其加入模型中，对当前急救医疗系统进行补充和完善。

2 急救中心选址问题的多目标双重覆盖模型

2.1 问题描述

急救中心选址问题包括确定救护中心位置以及该救护中心安排的救护车数量，从候选设施中选择符合要求的设施并安排一定数量的救护车为周边居民提供急救服务。考虑到救护车的服务场景，救护车在提供救助服务时应通过规划救护车路径以及保证响应时间，因此针对急救中心选址问题，不仅要考虑建设成本，还要将救护中心为周边居民点提供服务的响应时间纳入考虑，结合实际就医状况合理优化急救中心选址布局能够有效降低死亡率，完善院前急救，提高急救医疗系统的效率。

对于应急服务而言，其目标通常被表述为对公众的损失最小化，也就是说居民所享受的急救医疗服务的利益最大化，称为最大覆盖问题[3]。早期的救护车选址模型并未考虑到在某个时间段内救护车处于繁忙状态，仅仅要求在给定响应时间内用最少的救护车(最小成本)覆盖所有的需求点。这类模型忽略了现实问题的几个方面，即一旦救护车被派遣出去，一些需求点就不再被覆盖，无法得到急救服务。人口密集的地区通常比人口较少的地区有更高的紧急服务的呼叫频率，一辆急救车一次只能响应一个紧急呼叫，并且只有在完成该任务后才可用。因此人口越密集的地区，急救车忙碌的可能性就越大，平均响应时间就越长，它提供的服务就越差。为了确保一个电话的平均响应时间是可接受的，可以设定每个急救中心都应双重覆盖该居民的，即每个居民可以在响应时间范围内有2个急救中心可以为其提供服务。

救护中心的选址应确保覆盖到周边居民，确保院前急救系统能够提供救护服务的时间缩短，提供及时的服务[4]。综合上述因素，最大覆盖模型可以应用于求解急救中心选址问题[5]，但是由于急救服务不仅仅需要最大化覆盖居民数量，现实生活中影响急救服务水平的因素较多，例如紧急救护情况下不同疾病的发病时间和危重情况，急救过程中环境因素(路况，交通状况)等附加情况。因此仅仅将最大化覆盖作为优化目标并不能得到合理的优化方案，应结合实际情况进行改进。

2.2 多目标双重覆盖模型

考虑到救护车利用率较高，对急救服务的需求较多，如果某个区域中急救中心的车辆均被派出进行救护，此时该区域有急救需求，此需求无法被满足，可能造成一定情况的延迟，对患者的病情有较大影响。因此改进的模型要求居民点应在服务范围内被至少两个急救中心覆盖以提高急救服务的可靠性[6]，缩短响应时间，降低因急救不及时造成的死亡率。与最大覆盖模型仅仅要求覆盖最大数量的居民不同，改进后的模型考虑到当救护车被派出后可能会有个别居民在需要急救服务时，急救中心已经没有救护车，因此无法及时提供急救服务。因此设立备用覆盖，并且考虑建设成本得到多目标优化问题。

本文中在最大覆盖模型的基础上进行改进，目标函数包括最小化建设成本，最大化二次覆盖居民数量以及最小化为被覆盖的居民至当前设施的距离。要求每个居民点均被一个小半径r1覆盖一次，同时一个大半径r2覆盖2次，同时，以保证每个居民点都有备用的救护车提供急救服务，即可以在救护车处于服务状态时为需求点提供备份覆盖[7]。现阶段大部分居民均可在大半径r2=12 min内接受急救服务，但是急救车忙碌的情况下，通常会造成等待时间，因此应对每个救护站的救护车数量进行分配，适当增加需求密集附近救护车的数量，以保证有病人需求时有对应的车辆到达。小半径r1对应更高的服务需求，为居民提供更加可靠的医疗救助服务。因此设置r1=8 min，表示在8分钟内可以到达需求点。与此同时，二次覆盖可以作为对当前救护站点的补充，以应对繁忙时的情况。此外对于较为偏远的居民点而言，当期需要急救服务时，仍需派出救护车进行救助。虽然救护车可能无法在15分钟内到达，但在选址时仍然要考虑这些居民点，因此应将该类服务点的服务质量考虑在内，若该点未被二次覆盖，则应保证该点至当前设施点的距离最小，进而在派出车辆时，可以尽快到达该点，确保该地区居民能够获得有效的急救医疗服务。多目标双重覆盖模型如下：

(1)

(2)

(3)

(4)

(5)

(6)

zi≤yi

(7)

xj

(8)

(9)

yi,zi∈(0,1)

(10)

qj=1，ifxj>0

(11)

qj=0，ifxj=0

(12)

xjis inter，{0,1,2,3,4,5}

(13)

r2>r1

(14)

其中目标函数(1)表示最大化在r1范围内至少被覆盖2次的居民数量；目标函数(2)表示最小化未被覆盖的居民点到当前的急救中心的距离；目标函数(3)表示最小化建设成本和运营成本；约束(4)要求每个需求点均在小半径r1范围内被覆盖一次，即确保每个需求点均可在15分钟内接到急救车的服务；约束(5)要求一定比例α的居民可以在r1范围内被覆盖2次；约束(6)保证居民点可以在大半径r2内被覆盖两次；约束(7)限制只有在被一次覆盖的情况下，才能被覆盖两次；约束(8)表示安排救护车数量不超过p辆，约束(9)和约束(10)表示，只有在候急救中心安排救护车的情况下，该候选点才开放；否则该候选点不开放。

(15)

2.3 参数说明

给定某个距离r，若tij

算法中相关参数含义如表1所示。

表1 参数意义

3 狼群算法

3.1 算法介绍

选址问题是典型的组合优化问题，可以采用启发式算法进行求解，对于双重覆盖下的最大覆盖问题，提出了改进的多目标狼群算法进行求解。其中算法相关参数及操作介绍如下：

1)编码方式。将每头人工狼wolfi作为该问题的初始解进行编码，其中wolfi=(xi1,xi2,xi3,…xiD) ，其中xik表示第i头人工狼在第k个候选设施安排xik辆救护车为周边居民提供服务。考虑到每个设施的容量限制，根据当前候选设施的具体情况，设置每个候选设施安排的救护车数量不超过5辆。

2)“胜者为王”的头狼产生规则。初始化狼群，计算每个解得到其适应度函数，将适应度值最优的解作为头狼，后续迭代过程中根据头狼产生规则进行更新[10]。当前解中有多个目标函数值最优时，随机选择一个作为头狼。头狼不进行游走、召唤和围攻，仅在种群迭代过程中进行更新。每一匹人工狼都对应一个猎物气味浓度值，即每个解对应一个目标函数的适应度值。因此将人工狼i的适应度定义为：

Y=f(Xi)

(16)

其中，f(Xi)目标函数。在种群迭代更替的过程中，当某个人工狼的目标函数值满足Yi>Ylead，Xi替换当前头狼作为新一轮迭代过程中的Xlead，同时更新Ylead=Yi。

3)“强者生存”的狼群更新机制。自然界中“物竞天择，适者生存”的原则使种群不断更新，保留精英个体。在狼群算法中，根据人工狼的适应度值将其按照“由弱到强”的顺序进行分配，强壮的狼将得到充足的食物，但弱小的狼将会因缺乏食物而被饿死。在算法中体现为，将当前种群中的适应度值进行排序，去掉较差的解，并且根据初始化方法随机产生同样数量的人工狼，从而使种群保持多样性。算法能够拓展搜索范围，开辟新的搜索空间，跳出局部最优解。

4)游走行为。根据探狼比例因子α，确定探狼数量，选择除了头狼以外的前Snum头人工狼作为探狼，进行随机搜索以增加种群的多样性，拓展全局搜索的范围[11]。探狼Xsearch，i根当前的位置所感知到的猎物气味浓度Ysearch，ii，即这头狼的适应度值，确定猎物的位置及搜索方向。若当前猎物浓度Ysearch，i大于头狼所感知的猎物浓度Ylead，说明其距离猎物较近，更容易捕获猎物，因此用该探狼Xsearch，i代替头狼并更新头狼位置及其目标函数值Ylead=Ysearch，i，并发起召唤行为；若Ysearch，i

(17)

即：每个候选点安排的救护车数量以固定值O为基准，O=3。当候选点的救护车数量超过3辆，则可以减少1辆进行调整，若候选点救护车数量仅1辆则保持不变，若候选点没有安排救护车，则在该位置增加一辆救护车。具体操作步骤如图1。

图1 游走行为示意图

其中wolfi代表进行游走的探狼，wolf(i，k)表示探狼在第k个候选设施的位置上进行游走，即在第k个方向上进行游走。游走后探狼Xsearch，i的当前适应度值为Ysearch，i=Ysearch,ik，选择比当前适应度值更优位置所在的方向进行游走，并更新探狼Xsearch，i的状态。重复以上游走行为直至某人工狼Xsearch，i的适应度值比头狼适应度值更佳或游走次数T到最大游走次数Tmax。根据算法的搜索效率和k的不同取值，可以确定探狼的搜索方式，开辟新的搜索范围。

5)召唤行为。头狼在靠近最优解(猎物)时，通过嚎叫召唤其他人工狼聚集到猎物附近进行围攻。除头狼和探狼以外，将其他人工狼作为猛狼，它们在听到召唤后迅速向头狼所在的位置聚集靠拢，猛狼以较大的奔袭步长，朝着头狼方向靠拢。为了体现狼群内部的信息交流，将头狼和探狼的解进行比较，根据不同情况进行召唤行为。因此，设计召唤行为如下：对于头狼和猛狼对应位置安排相同数量救护车的候选点，保持该位置救护车数量不变，对于不同救护车数量的候选设施处的数量进行调整，将当前解猛狼wolfferocious,i)=(xi1,xi2,xi3,…xiD)和当前最优解头狼wolflead=(xlead1,xlead2,xlead3,…,xleadD)的不同候选位置的救护车数量进行比较，相同数量的不作改变，以体现保留头狼传递的有效信息。继续改变数量不同的位置，改变方法则考虑此处所有解安排救护车的数量，计算一个频率，选择频率较高的数量作为调整后的解。具体改变方式如图2。

图2 召唤行为示意图

图3 猛狼听到召唤后的位置图

6)围攻行为。围攻行为可以看作是狼群算法中的局部搜索，在最优解附近进行更加细致的搜索以发现最优解的过程。猛狼奔袭至猎物附近后联合探狼，将头狼的位置看作猎物的位置对其进行围攻，此时已经较为靠近最优解，因此，只需在当前解的基础上进行局部搜索，因此设定以下行为进行围攻。

图4 围攻操作示意图

如图4所示，猛狼局部搜素，保持与头狼相同的救护车数量，对其他不同位置的救护车数量根据下式进行调整。即：当候选点的救护车数量超过2辆，则可以减少1辆进行调整，若候选点救护车数量仅1辆则保持不变，若候选点没有安排救护车，则在该位置增加一辆救护车。猛狼wolf(ferocious)围攻后当前的位置如Step3中所示。

(18)

围攻后人工狼当前的适应度值大于原位置的适应度值时，即人工狼距离猎物更近即围攻后的解得到的适应度函数更优，则更新该人工狼i的位置，否则保持原位置不变。

3.2 算法步骤

因此改进后的狼群算法求解双重覆盖问题的求解流程如下所示：

Step1： 初始化算法参数。包括狼群规模Num，候选设施数量、需求量、种群更新因子β，最大迭代次数iters等；并对种群进行初始化，得到人工狼群；

Step2： 选取头狼。选择适应度值最小的人工狼为头狼；若同时存在多匹人工狼适应度值相等且最小，则在其中随机选取一匹人工狼充当头狼；

Step3：游走。探狼k根据游走策略进行游走，比较探狼和头狼的目标函数值，若Ysearch，i

Step4：召唤。其他人工狼接收头狼信息，再在头狼的号召下，猛狼向头狼进行奔袭。在奔袭的过程中，若Yfriosiouc，i

Step5：围攻。把头狼位置视为猎物的移动位置,，即最优解所在的位置。参与围攻的猛狼按照前述围攻方法对猎物进行围攻，若Yfriosiouc，i

Step6：更新狼群。参照“强者生存”的规则，对狼群进行更行。保留最优解，剔除种群中的其他部分弱者，同时产生等量新的个体，保持狼群数量；

Step7：终止。若t

4 数值计算

4.1 模型数据

为了提高急救中心服务效率，缩短救护车进行救护工作的平均时间，以保证该区域居民能够在规定时间内接收到急救服务并提高医疗急救系统的效率[12]，选址某市特定区域进行急救中心选址优化。该地区候选设施点由社区卫生服务中心、二级医院、三级医院和卫生防疫站等医疗机构选择，根据急救车安排的要求，初步剔除不能改建成为急救中心的候选设施，并加入一些有硬件条件的候选设施，最终得到50个地点作为后续选址问题的候选点。

以某地区为例，为该地区80个需求点提供医疗急救服务，在当前73个候选设施筛选出硬件条件满足急救中心要求的设施作为候选点，并且另外增加一些候选设施，从中选择50候选点作为急救中心，并安排救护车在该急救中心为该区域居民提供急救服务，考虑到急救中心救护车数量的限制，救护车数量应不得超过150辆。以该地区的最小行政划分区域(街道)作为居民点的划分依据，并将街道办事处所在地作为该需求点的具体位置。

4.2 模型参数

模型中涉及到的候选点和需求点位置、需求点规模、需求点与设施点最短通达时间、二次覆盖比例因子、多目标权重、各地区需求人数以及候选设施建立费用等的设定如下：

1)候选点位置。选择某市的医疗卫生服务机构以及大型公共设施作为候选点，包括三甲医院、社区卫生服务中心、卫生防疫站等[13]。考虑到急救中心需配备急救车以及医护人员，因此应选择具有一定规模并且医护人员具备急救技能的医疗设施作为候选点。共计35个候选点，分布位置如图6所示。

2)救护车的行驶时间。考虑到救护车进行救助时的行驶速度和交通情况，设定救护车在市区行驶速度为60 km/h,不考虑通过交通信号等的时间。将需求点和候选设施点的出行距离转化为出行时间进行计算。

3)需求点位置及人口规模。以行政区域划分该区域居民，将该区域的各个街道作为需求点集合，街道的几何中心视为人口中心，及需求点位置。该街道的常住人口数量作为需求量。

4)急救中心个数以及急救车数量。根据《上海市医疗机构设置“十三五”规划》中关于急救医疗卫生机构设置的规定，根据该区域内居民的数量以及当前可供选择的设施的具体情况等相关因素，选择50个作为急救中心安排救护车。根据急救电话的呼出频率确定急救车数量，正常情况下，急救中心的救护车一般为3辆，因此在本文中设定每个候选点做安排的急救车不得超过5辆，由此来设定每个候选设施的救护车数量上限。

5)覆盖半径。考虑到病人发病的黄金救助时间，救护车进行救护的时间以及出行时间应规定在15分钟内到达病人处，从而使病人得到有效的救治[14]。因此，在基础的救助时间15分钟的基础上，对全部的居民点的病人提供服务。考虑到建立的救护站应在以后较长时间内满足急救需求，在该模型中考虑未来的人口变化以及急救服务水平的提高，在基础的15分钟应急服务的情况下，确保一定比例的居民的能够在12分钟内接到急救服务，这是对当前急救服务的改善，通过缩小覆盖半径进行提高救护时间。如图5所示，急救中心为周围候选点提供服务时，有一定的有效服务半径，在这一半径内，需求点1，2可以得到急救中心为其提供的服务。其他的需求点2则无法得到急救中心的相关服务。

图5 急救中心覆盖半径示意图

7)覆盖次数。考虑到救护车的救助服务类型，对任何一个需要救护车到达的地方都应考虑在内，因此当某急救中心的救护车全部派出执行救护任务后，若仍有救护需求，该救护站则无法派出车辆。在这种情况下，居民的病情无法得到及时的救治，考虑到这种情况，建立二次覆盖模型，可以在该居民点对口急救站无法提供急救服务时，可由其他急救中心提供服务。因此该居民可以被急救中心覆盖2次，即可以接受2个急救中心提供的服务，当一个急救中心忙时，另一个急救中心可以作为备用服务设施为其提供服务。因此当某居民可以在规定时间内被1个急救中心服务时，该居民可以被覆盖1次；当某居民点可以在规定时间内被2个急救中心服务时，该居民可以被覆盖2次，即可以得到备用服务。

图6 多次覆盖示意图

如图6示，对于需求点1来说，在规定时间内，急救中心A可以为其提供服务；对于需求点4而言，该需求点可以由急救中心A 和急救中心B提供服务，当某个急救中心的救护车派出后，则另一个急救中心可以为其提供服务，为该需求点提供双重保障，以避免救护车派出的情况下，部分地区无法得到及时的急救服务，错过黄金抢救时间。

8)固定设施费和救护车数量的成本。对于所设立的急救站应有固定设施费，考虑到救护车停车位置以及急救人员休息区的建设费用，若该候选点以及具备条件，则固定设施费为0，一般情况下候选点中医院已经具有急救车需要的固定配套设施，因此该费用为0；对于一些社区卫生服务中心或者公共设施应增设急救中心的固定配套设施，因此应根据统一设定候选点的固定设施费为30万到100万之间，因此文章中随机确定该地区候选设施的建设成本。假设该设施的使用年限为15年，则每个月的费用根据该候选设施的具体情况确定。考虑到具体采集数据的难度和不确定性，在本文中随机确定每个候选设施点的每个月的建设成本在急救站安排急救车除了车辆本身费用外，还应考虑救护车配备的司机及医生的费用，因此每辆救护车的成本参考医生的工资，分摊到每个月为8 000元，根据相关文件指出，人员薪资每个月为24 000。因此根据以上假设确定每个候选点的固定设施费和救护车数量的费用。

4.3 求解结果

利用Matlab2016b对狼群算法进行编程实现，实验所用硬件环境为Intel©Processor 5Y10 CPU@0.80 GHz，8.0 GB内存，64位Windows 10操作系统。在现有50个急救中心候选点中，选择若干个作为急救中心，为80个街道提供紧急医疗服务，以满足居民突发情况的就医需求。其中算法相关参数通过调整某一参数值，固定其他参数保持不变的调整方式，得到狼群算法中相关参数的最佳值，逐一调整得到算法参数: 种群数量pop:100; 最大迭代次数gmax:0.4; 探狼游走方向β:0.2; 探狼比例因子ρ:0.6。

采用所构造的狼群算法求解急救中心选址的多目标双重覆盖模型，根据某区域的实际情况，进行求解。所得结果为0.447，对于所得到的结果如表2所示。

表2 急救中心选址结果表

在表2中，根据算法得到结果可得，2号候选设施启用，作为急救中心建立，并安排3辆救护车，5号候选设施处不安排救护车，因此该候选设施不启用。同样可以得到其他候选设施处安排的救护车数量以及选址开放的急救中心，同理，其他候选设施点救护车数量安排可参照表1。

根据算法求解结果可得在候选急救中心中选择合适的急救中心安排救护车，并根据该地区的人口密度和急救医疗服务的需求安排救护车，以满足双重备用覆盖的要求。通过结果可以得出每个急救中心安排的救护车数量，得到对应急救中心分别覆盖的居民点以及相应的配备救护车数量。根据覆盖半径的覆盖范围可以得到，急救中心能够为周边居民提供可靠的服务，即使该急救中心的急救车被派出，居民点仍然可以被其他急救中心的急救车服务。同时，急救服务响应时间也能满足要求，保证病人的黄金救援时间。重新进行布局急救中心并合理安排急救车后，该地区的急救医疗服务效率得到提高，急救响应时间由原来的15分钟缩短到12分钟，缩短了院前急救的时间为病人的安全提供保障。对于突发疾病，能够更快的到达危重病人所在地点，展开急救服务，确保在黄金救护时间进行有效的救护，降低死亡率。每个急救站可以为周围居民提供响应时间在12分钟内的急救服务，而居民点也可以得到2个急救站所提供的服务。此外较为偏远的需求点也能接收到同样的服务，因为求解算例是某市的急救中心选址，城市人口密集，没有较为偏远的居民点，因此对偏远地区无法服务的惩罚较小。如果将该模型推广到大范围的急救中心选址，则偏远地区的服务水平将会在目标函数中体现出惩罚因素。同样，当前要求急救车的响应时间是15分钟，考虑到未来交通状况、人口老龄化问题以及各种突发疾病的发病率等因素，建设急救中心时应具有一定的前瞻性，因此应提出一部分人口密集的居民点的救护车到达时间应在12分钟以内，作为一个提高服务质量的要求加入模型中，因此当前选址布局下，居民在小半径的情况下仍能保证全部居民点都可接受急救服务。

5 小结

考虑到急救医疗服务的高效性和敏捷性的特点，通过设立分散的急救中心来进行有效的院前急救，在一些突发疾病的黄金时间进行救护，提高患者的存活率。通过安排急救中心以及救护车，来缩短急救车的响应时间，建立有序、有效的新型医疗服务体系。构造求解该问题的狼群算法，重新定义游走、召唤、围攻等操作以及种群更新策略，能够有效地求解此类问题，效率较高。当前优化后的急救中心选址布局克服了当前急救车出行时间较长的问题，重新合理安排急救车数量，避免了人口密集地区救护车数量的短缺。通过算例求解表明，该模型及求解算法在实际应用中是可行和有效的，并且能够在当前急救中心布局的情况下有所改进，能够更好地满足居民的就医需求，加强了急救中心等各类医疗资源有效配置，提升综合医疗服务能力。在实际问题基础上，结合未来医疗资源分配的要求以及当前医疗资源分配中的问题，对当前医疗设施重新进行改进，使其适应社会发展对医疗资源服务的需求。

根据急救中心所提供的急救服务的特点采用最大覆盖模型进行求解，并在此基础上进行改进，建立多目标双重覆盖模型，引入双重备用覆盖约束，并对未能提供及时的急救服务的居民的施加惩罚值，从而建立具有一定前瞻性的贴合实际情况的多目标双重覆盖模型。模型中引入3个目标，包括最小化成本，最大化覆盖人数和最小化不能服务的惩罚值，通过求解得到Paroto解来平衡不同目标，决策者可以根据权重选择对应的选址方案。所得到的结果与当前急救车分布相比，提供的急救服务更加高效及时，救护车平均响应时间大大缩短，居民得到的急救服务更加及时，急救医疗系统更加高效。此外多目标问题可以为决策者提供选址空间，可供决策者参考，通过调整权重进而得到符合实际情况的选址方案。