考虑空间随机需求的急救站点选址规划

苏 强，杨 微，王秋根

(1.同济大学经济与管理学院，上海 201804；2.深圳大学管理学院，广东 深圳 518060；3.上海市第一人民医院创伤中心，上海 201620)

1 引言

急救医学上，紧急事件发生后的十分钟称为急救白金十分钟，十分钟内患者如果能够得到有效的医疗处理，将大大提高患者的生存率。这就要求救护车应尽快到达患者处，及时展开救治。为达到这一目的，有效地规划急救站点布局是较为关键的[1]。在急救站选址问题研究上，学者们主要借鉴商业生产、军事等领域的方法，如p—中心模型，p—中位模型、覆盖模型等，然而急救站选址问题与其他选址问题相比，侧重点略有不同，就是在注重效率、成本的同时，需要更加关注选址方案在实际应用中的有效性、可靠性[2]。

近20年来，研究者们开始逐渐关注随机因素影响下的急救站选址问题。Beraldi 和 Bruni[3]在其研究中阐述了建立稳定、可靠的急救网络的重要性，指出EMS系统运行于一个充满随机性的环境中，包括需求数量的随机性、需求发生地址的随机性、车辆行驶时间的随机性等。这些随机性的存在会显著影响急救站点规划的有效性。

现有研究主要探讨需求数量随机性和车辆行驶时间随机性的影响，而针对急救需求发生的具体空间位置，相关的研究却还不够深入。主要原因之一是救护车配置方面的研究往往是在图论(Graph Theory)方法基础上进行的。研究者们通常将空间散布、随时随地可能发生的需求抽象为图上的若干代表性的点，认为急救站覆盖了该点即为覆盖了整个区域，实际上，这样处理存在较大的误差，往往有较大一部分需求并未被真正覆盖，尤其是在需求区域面积较大的情况下。虽然近期有研究将整个空间尽量细化成密集的矩形网格系统，仍然不能有效降低需求空间随机分布的影响。一方面这种方法大大增加了计算量，使得原本复杂的问题更加复杂；同时每一个网格中的需求较为稀疏，受误差影响很大，较难统计其数量和位置的分布规律，有的网格甚至几个月都没有需求产生，而且位于边角处的网格也需要满足覆盖水平的约束，往往需要配置更多的资源；另一方面，对于争分夺秒的救护车而言，每一个小矩形仍然是一个较大的区域，即便是边长2km的小网格，以城市车速40km/h计算，行驶整个网格也要约3分钟的时间，而3分钟对于急救响应时间而言，是难以忽视的。而如果选取面积稍大的网格，每个网格中需求的空间分布也是难以刻画的，因为网格是人为划分的，在一个特定的矩形区域内，虽然可以应用人工神经网络等方法来拟合其内部复杂的需求分布情况，但很难保证拟合出来的分布能够在长时间内仍然保持稳定。

本研究创新性地将高斯混合模型 (GMM，Gaussian Mixed Model)聚类方法应用于急救需求空间随机性的刻画上，将大量空间随机分布的急救需求分解为多组高斯分布的混合，从而解决了急救需求分布复杂、难以描述的问题。提出了从现实数据出发，重新聚类并划分需求区域的理念，首先应用上海市松江区2013年全年急救数据进行聚类分析，将聚类结果作为选址规划模型的输入，建立了考虑空间随机需求的机会约束规划模型，最后应用松江区2014年全年急救数据对选址方法的实用性进行了验证。

2 模型分析与假设

选址问题研究中，覆盖模型是最重要的模型之一。第一个急救资源选址覆盖模型是由Toregas等[4]提出的选址集合覆盖问题(Location Set Covering Problem)，其目标是用最少的站点覆盖规划空间内所有的需求。然而由于资源稀缺性的限制，全覆盖在现实中往往是很难实现的。鉴于此，Church和ReVelle[5]提出了一个最大覆盖选址问题(Maximal Covering Location Problem)，模型的目标是在给定有限数量的站点的情况下，最大化需求的覆盖水平。上述两种模型中，如某个站点只有一辆救护车，且处于执行急救服务任务过程中，则之前认为被该站点覆盖的需求将不再被覆盖，即出现“伪覆盖”的情况。为减小“伪覆盖”现象对急救系统的影响，Gendreau等[6]提出了双覆盖模型(Double Standard Model)，假设每个站点有大、小两个覆盖半径标准，该模型保证选取的站点在较大的覆盖半径情况下覆盖所有需求点，同时最大化被较小半径覆盖至少两次的需求数量，从而实现站点之间的联动，减少“伪覆盖”现象的产生。本文提出的选址模型假设站点有大小两个覆盖半径，其理念思想与双覆盖模型较为类似。近年来研究者们不断对双覆盖模型进行拓展，来解决更复杂的选址问题。例如Liu Yi等[7]改进了传统的双覆盖模型，探讨了具有一般生命支持系统和高级生命支持系统两类救护车的选址问题。Dibene等[8]考虑了不同的时间段急救需求的数量变化情况，开发了一个考虑不同时段需求情况的双覆盖选址模型。Liu Ming等[9]提出了一个新的双覆盖模型选址模型，其模型认为，急救站选址不仅要考虑救护车从急救站到现场的过程，同时还应考虑救护车从现场到医院的转运过程。

在上述经典的覆盖模型基础上，近年来研究者们开始关注随机环境下的救护车配置问题，Beraldi等[3]阐述了建立稳定急救网络的重要性，在其研究中考虑了需求数量的随机性，建立了相应随机规划模型。张玲等[10]建立了鲁棒优化模型，研究了需求数量不确定情况下救灾网络构建问题。Torres等[11]将粗糙集相关方法应用于双覆盖选址模型中，考虑了救护车行驶速度的随机性，探讨了急救站的最大覆盖问题。更多引入随机性的救护车运营问题的研究可以参考Aringhieri等[12]和Li Xueping等[13]的综述文章。

除了上述随机因素，急救需求的空间随机性影响也是近年来一个热点的研究问题。Wei Ran[14]指出现有的覆盖模型由于使用了“覆盖—未覆盖”的假设，可能不适用于存在空间随机需求的问题上。即便近年来提出的部分覆盖模型也只是考虑了覆盖水平随距离的增加而降低，而并没有考虑在某一区域内需求的具体空间分布形式。Altnel等[15]考虑了一个多工厂的韦伯选址问题，假设在一个需求区域内需求在空间上服从简单的二项分布形式，然而在一个给定的区域内需求的空间分布往往较为复杂，简单认为服从二项分布会造成较大的误差。Beraldi和Bruni[16]提出了一个概率模型来优化急救站点选址，然而在研究中只是通过一个随机参数来简单描述需求可能被覆盖的情况，没有详细探讨空间随机性的具体分布影响。Degel等[17]采用网格系统的方法将空间分散的急救需求划分为若干网格，分别对网格中的需求数量进行探讨，进而解决考虑空间随机性影响的救护车配置问题。Chen等[18]将网格系统和GIS系统结合，从而较为精确的分析网格内的空间分布情况。然而网格系统也存在明显的缺陷，一个网格没有任何具体的物理意义，不是医院、社区或事故高发区，因此需求分布的规律较难获得，即便找到网格内的分布情况，也难以保证分布的稳定性。樊博[19]应用k-means聚类算法来解决应急设施选址问题，认为应将应急设施建于聚类质心点处，但k-means聚类得到的并不是能够揭示空间随机性规律的概率分布，而只是对现有数据的一种关系描述，因此获得的选址方案并不能确保在长期内仍然有效。而且对于急救站点选址问题，聚类质心点处往往不一定存在医院或急救中心，而新建急救中心的成本往往是很高的。

较为准确地描述急救需求的空间分布，是解决空间随机需求影响下的选址问题的基础，在相关研究中，主要是从统计学的角度对每个区域的需求进行描述和估算。半参数贝叶斯混合模型经常被用于解释急救需求空间密度的不均匀性。如Kottas和Sanso[20]应用二元Beta混合分布来对空间中散布点的分布形式进行描述。与其类似，Ji Chunlin等[21]应用高斯混合模型进行了空间点过程的定量描述。Zhou Zhengyi等[22]将其拓展到多时段急救需求的空间分布描述中。由于上述研究主要关注急救需求空间分布的统计意义，大多是用混合模型的方法来描述急救需求的空间分布规律。但混合模型的各个组分在空间上存在重叠和交叉的情况，且每一组分空间跨越度可能较大，空间距离非常远的两个需求也可能来自于同一个组分，从而导致获得的结果难以应用到救护车配置或指派相关的问题上。

综上所述，在急救站点选址问题研究中，对需求空间分布随机性的影响探讨尚不够深入，现有的空间随机性描述方法难以为救护车配置研究提供有力的帮助。需要一种空间分布描述方法，既能够实现对需求分布的准确描述，又能将其描述结果方便地应用于配置优化模型。

3 基于高斯混合模型的需求空间分布描述

本文从现实数据出发，通过对上海市松江区急救需求数据进行分析，来获取急救需求的空间分布规律。急救需求在城市、街道、村镇内随机地发生，其地理位置体现出较强的随机性，图1中显示了上海市松江区2013和2014年急救需求的地理分布情况，黑色的点代表发生的急救需求，H表示急救站点的布局。通过对数据进行初步分析可以发现，急救需求的分布呈现出一定的规律，在城镇或街道的中心、一些特定的路段、事故的高发区，急救需求较为密集。另外，一些社区、医院、养老院等人口老龄化比较严重，急救需求也较为集中。而在周边一些地区，急救需求较为分散，发生频率较低。

图1 上海市松江区2013、2014年急救需求空间分布图

以往研究常用行政区域来划分急救需求，如一个村镇、街道代表一个需求点，但这种划分方法存在明显的弊端。首先每一个行政区域的面积一般较大，受需求空间分布随机性的影响更加显著；其次，行政区域是人为划分的，很难在其中找出需求空间分布的规律。通过上述分析得出，用行政区域来划分需求给问题的解决造成了不必要的麻烦。急救系统在一定程度上并不依赖行政区域，因此本研究突破行政区域思想的束缚，采用高斯混合模型聚类方法来刻画需求的分布情况，将整个规划区域重新聚类为若干服从高斯分布的需求区域。

3.1 应用高斯混合模型聚类的合理性

本研究用高斯混合模型聚类方法来分析急救需求空间分布的主要依据是：

(1)任何复杂的分布形式都可以用多个高斯分布的混合来近似[23]。急救需求在一个村镇的中心可能较为集中，但同时在村镇的某些街道上，急救需求的分布又看似独立于其他地区，高斯混合模型可以将这些复杂的分布形式分解为多个简单高斯分布的混合，从而解决需求分布随机性的定量描述问题[24]。当预测一个需求发生时，可以根据混合高斯分布函数，获取其出现在不同地理位置的概率情况。

(2)观察上海市松江区2014年急救需求的空间分布情况，可以发现，不同年份间急救需求的空间分布较为相似，2013年需求比较密集的区域在2014年仍有类似的体现，证明急救需求的空间分布具有一定的稳定性，应用高斯混合模型聚类方法得到的结果不仅反映了当下急救需求的分布情况，也能够揭示未来急救需求的发生规律。

3.2 GMM聚类在急救需求分布刻画上应用

根据信号处理理论，任何复杂的随机信号都可以通过傅里叶转换，分解为若干个正弦波的组合。同理，在二维地理空间随机分布的急救需求也可以分解为若干标准分布的组合。本文应用高斯混合模型来描述急救需求的空间随机分布。假设某一混合模型由K个高斯分布组成，则混合模型的概率密度函数为：

(1)

式(1)中，x是经纬度坐标组成的二维随机变量；πk为混合系数，表示每一个需求区域出现需求的概率；N(x|μk,Σk)为每一个高斯分布的密度，μk表示第k个需求区域的经纬度坐标均值；Σk为协方差矩阵。其中二维高斯分布的密度函数：

(2)

给定一组数据，直接获得混合高斯分布密度p(x)是较为困难的。因此，这里引入一个K维0-1向量z，向量中的元素zk满足zk∈{0,1}，且∑kzk=1。对于某一个数据点xn有一个zk与之对应，表明了xn所在的高斯需求区域。从而可以定义一个联合分布p(x, z)，则边缘分布p(z)和条件概率p=(x|z)与式(1)中πk和N(x|μk,Σk)相对应，有：

(3)

(4)

从而根据加法乘法法则可以得到混合高斯分布密度：

(5)

在聚类过程中，我们关心某一个急救需求属于某一区域的概率，据此才能将急救需求归入不同的区域中，并通过迭代估计每个高斯区域的坐标均值和协方差。这一概率可以根据贝叶斯理论计算：

(6)

在评价数据拟合程度时，采用最大化对数似然函数：

E=lnp(x|π,μ,Σ)

(7)

其中N表示样本数量。

经典的高斯混合聚类方法是EM算法(Expectation Maximization Algorithm)，可以参考文献[24]。而传统聚类方法并不完全适用于急救需求刻画的特殊问题上。考虑到急救需求特点，本文将EM方法进行如下改进：

(1)在经典的EM算法中，聚类数目K的值需要提前给定，如果K值定的过大，划分的需求区域较多，区域内的需求量较少，会造成过拟合。而如果划分的数量过少，拟合效果会较差，每个区域的面积较大，空间分布的随机性影响会增大。需要注意的是，GMM聚类的目的不仅仅是提供一个较为准确的拟合曲面，同时这个分布应当能够在一段时间内都能保持良好的拟合效果，符合需求发生的规律。因此，本研究提出一个评价K值的指标函数，假设有T期可用数据，可以用第T期数据进行参数估计，而剩余T-1期数据可以用来帮助确定K值。计算多期对数似然函数：

(8)

其中，0<γ<1为折扣因子，该式表示近期数据的拟合效果对K值选择的影响大于远期数据的拟合效果。除以当期数据数量NT-t是为了消除每期数据数量不同的影响。由于数据限制，在本文中应用2013年的数据来进行均值和方差的参数估计，然后再计算聚类结果对2014年数据的拟合效果，从而确定一个合适的K值。

(2)将事故高发区、养老院、人口密集社区等地段选择为初始聚类质心点，这样既可以反映问题本身特点又可以提高聚类算法的效率。

(3)考虑救护车的响应时间限制(根据国际惯例，站点和需求点之间的距离应小于15分钟的车程)，按照城市行驶平均速度为40km/h，那么每个站点的覆盖半径应该小于10km。因此，聚类得到的每一个需求区域应小于这个覆盖面积。在算法中我们通过调整某一个点xn属于某一个高斯分布的概率p(zk=1|xn)的值来实现对聚类面积的控制。

改进的EM算法具体步骤如下：

步骤0 初始化过程

各类参数初始值的选取会影响聚类的效果和效率。为提高算法效率，本研究首先应用K-means聚类的方法获得每一类的初始μk、Σk、πk，并计算初始E值，给定一个K值。

步骤1 E过程(Expectation)

根据现有的μk、Σk、πk，计算每个数据属于每类的概率，每个数据暂时归于概率最大的类。

步骤2 M1过程(Modification)

如果样本xn和质心k的距离大于10km，则修正概率p(zk=1|xn) = 10-10从而保证该样本不会被归于第k个高斯。

步骤3 M2过程(Maximization)

根据聚类结果，更新相关参数：

(9)

(10)

(11)

其中N为样本量，Nk为第k类高斯组成中的样本数。

步骤4 计算并评估对数似然函数值

计算对数似然函数值，评估其改进情况，确定是否停止。本研究设置的标准为聚类算法连续300次迭代对数似然函数改进幅度小于0.01‰时，认为算法收敛，若不满足，返回步骤1。

步骤5 计算2014年数据的拟合优度

计算得到的分布与2014年数据的符合程度，然后令K=K+1。循环结束后，挑选出最优的K值。

得到聚类结果如图2所示。其中同一颜色的点代表属于同一需求区域的急救需求，黑色三角形为需求区域的聚类质心点。

图2 高斯混合模型聚类结果

4 考虑空间随机需求的站点选址模型

4.1 模型的建立

在GMM聚类获取急救需求的空间分布基础上，本节建立整数规划模型来解决空间随机需求影响下的急救站点选址问题。

在以往研究中，大多数模型没有指明被多重覆盖的需求优先被哪一个站点服务，而是仅以覆盖或未覆盖作为评判标准，使得服务响应时间难以达到最优。因此，本研究提出考虑服务优先级的选址规划模型，该模型假设：

(a)一个需求区域有且仅有一个主站点为其优先提供服务；(b)一个需求区域有且仅有一个备用站点提供后备服务；(c)一个需求区域的主站点和备用站点不是同一个站点；(d)一个需求区域的主站点可以是另一个需求区域的备用站点，反之亦然；(e)每个需求区域到其主站点的距离均值小于到其它已启用站点的距离均值。(f)各个需求区域内的需求相互独立；(g)假设站点的救护车数量能够满足相应的急救需求。

定义如下符号：

αij：0-1决策变量，站点j是需求区域i的主站点则αij=1，否则αij=0；

βij：0-1决策变量，站点j是需求区域i的备用站点则βij=1，否则βij=0；

yj：0-1变量，备选站点j被启用则yj=1，否则yj= 0；

K：需求区域的总数量；

M：备选站点的总数量；

W：启用的站点的集合；

λi：需求区域i中产生的需求的数量；

tsr：主站点到其服务的需求区域的理想行驶时间；

ts1：主站点到其服务的需求区域需要满足的最大行驶时间；

ts2：备用站点到其服务的需求区域需要满足的最大行驶时间

目标函数为最小化启用站点的数量：

(12)

模型需满足如下约束条件：

(13)

(14)

(15)

(16)

(17)

αij+βij≤yj，∀i

(18)

(19)

(20)

约束(13)为救护站点选址问题中的一个经典约束，即期望φ比例的需求能够在tsr时间内得到主站点服务，其中Pr(tij≤tsr)表示j站点到i需求点的行驶时间小于某标准tsr的概率，可以通过GMM聚类获得的参数计算其具体值，这一约束往往被政府部门用来评估医疗急救中心的运营绩效；约束(14)(15)分别要求主站点和备用站点到其服务的需求区域的行驶时间不高于标准时间ts1和ts2；约束条件(16)(17)要求每一个需求区域有且仅有一个主站点和一个备用站点，需要注意的是，我们在现实应用情况中发现，即便某一处急救需求无法得到其主站的及时服务，大部分需求的首个备用站点即能够及时满足该需求，当然如果放松约束，也可以实现为某一需求区域配备多个备用站点；约束条件(18)(19)保证j站点作为主站或备站启用时，yj=1；约束条件(20)对应假设(e)。

4.2 随机变量的计算处理方法设计

在随机环境中，政府和公众期望急救服务系统可以在较大的概率下仍然保持稳定、有效，因此本研究采用机会约束规划方法对模型进行求解。首先将含有随机变量的约束条件(14)、(15)写为机会约束形式：

(21)

(22)

θ1、θ2为风险参数，式(21)表示需求区域i中的需求能够在ts1时间内得到主站点服务这一约束条件被满足的概率为1-θ1，式(22)类似。

·αij≥1-θ1

(23)

·βij≥1-θ2

(24)

其中，

(25)

其中，μiu和μiv分别为第i个需求区域中需求横纵坐标的均值，σiu和σiv为标准差，ρi为相关系数，其取值在高斯混合模型聚类中获得。

将约束(14)、(15)写为式(23)、(24)的形式，问题即转化为二次约束规划问题，可以应用成熟数学规划软件，如Cplex、Lingo等进行规划求解。

5 上海松江区急救算例分析与讨论

本研究应用上海市松江区2013-2014年的急救网络数据对上文提出的选址方法进行验证，在第二章首先利用2013年的数据进行高斯混合模型聚类，来获取需求空间分布的概率描述，再应用2014年的数据对随机模型的选址效果进行验证，应用2014年数据进行验证是为了说明基于GMM的方法可以较好地揭示需求空间分布规律，在一定时期内都能够保证选址方案的有效性。

为了增加可行解空间，本研究在松江区原有8个急救站点的基础上，依照上海市120医疗急救中心对建立救护车站点的规定，另外增加7家三级医院和较大的二级医院作为备选站点。15个备选站点的分布情况如图3所示，其中空心十字为后添加的备选站点，三角形表示30个需求区域的聚类质心点。

图3 备选站点和需求区域质心点分布图

选址模型的参数取值如表1所示，其中tsr和ts1的取值依据以往类似研究[6]，ts2的取值出于上海市基础设施条件的考虑。

表1 模型参数的取值

本文关注于探讨急救需求空间随机性对急救站选址方案有效性的影响，因此将本文建立的空间随机模型与不考虑空间随机性的选址模型进行对比。在不考虑空间随机性的模型中，用均值取代随机的距离和行驶时间，因此称之为均值模型，原模型中约束(13)～(15)用以下约束代替：

(26)

(27)

(28)

此外，本研究还与松江区现有站点布局的绩效进行了对比，松江区现有站点是按照行政区域进行铺设的，基本上每一个行政区域都设有一个急救站点。本文通过模型获得考虑和不考虑空间随机需求的最优选址方案，然后应用2014年松江区急救数据进行数值验证，实验结果如表2所示，模型中限定了主站到需求区域的时间不超过10分钟，因此表2中的延误是指救护车的行驶时间超过10分钟，超出10分钟的时间即为延误时间。每次响应时间超过10分钟的救护记为一次救护延误。因为每天急救需求量较少，较难看出延误的影响，因此本文观察每周的延误情况。

表2 实验结果对比

从表2中可以看出，为了保证急救网络的有效性，空间随机模型启用了更多的站点，但同时平均服务响应时间也相应缩短。均值模型没有考虑急救需求的空间随机性影响，因此产生了较多的救护延误情况。空间随机模型和现实布局虽然都启用了8个站点，但8个站点的地理分布是不同的。显然，从延迟时间、延误时间和延误次数上看，空间随机模型得到的结果都明显优于现实布局，说明空间随机模型的选址方案更加科学、有效。图4、图5对比了各种模型的每周延误总时间和延误次数。从图4和图5中可以看出，考虑需求空间分布的随机性，应用机会约束规划模型进行求解，效果明显优于均值模型和现实的布局情况，延误时间和延误次数的差距显著。

图4 每周延误总时间对比

图5 每周延误次数对比

约束条件(13)要求60%的需求在5分钟内得到服务，从图10中可以看出，不考虑需求随机性，应用均值模型进行选址规划，其效果远差于模型的预期，5分钟内得到服务的需求几乎全年都低于60%。而考虑了需求空间分布的随机性后，服务水平得到了明显的提升，全年均高于60%。

图6 5分钟内得到服务的需求百分比对比

6 结语

本研究重点考虑了急救需求的空间随机性影响，分别介绍了空间随机需求的处理方法和急救站点选址规划的随机模型。提出对空间随机需求的处理应从实际数据出发，应用高斯混合模型聚类的方法对急救需求的分布特征进行定量描述。在此基础上，本研究建立了考虑需求空间随机性的机会约束规划模型，以期提高急救站点规划的有效性。在算例分析中，以上海市松江区2013年的数据为例，本研究将急救需求拆解为30个高斯分布的混合，进而通过求解机会约束规划模型得到站点布局方案，之后应用2014年的真实数据对选址的效果进行了验证。实验结果表明，急救需求的空间随机性对站点规划有效性的影响是十分显著的，应用考虑空间随机需求的规划模型进行选址，周平均延误时间从不考虑空间随机性时的36.92分钟降低到3.95分钟，周平均延误次数从24次减少至3.4次，且能够保证60%的急救需求在5分钟内得到服务，实验结果证明了方法的实用性和优越性。