基于整数规划的疫情援助分配问题

The Distribution of Epidemic Aid Based on Integer Programming

摘要: 2019年底，新冠肺炎疫情肆虐，武汉市及整个湖北省全境范围疫情异常严峻。国家卫生健康委提出建立“一省包一市”的一一对口支援关系，全力支持湖北省的防疫工作。基于此，本文首先利用主成分聚类衡量全国31个省市的援助水平，得出各省份援助实力强弱。为保证当地留有足够的医疗资源，综合考虑距离及援助水平因素，运用整数规划筛选出十六个进行支援的省市。最后，基于支援省市和被支援城市的聚类结果设定支援效果分数，采用整数规划分配援助关系。本文对疫情下筛选支援省市和分配援助力量具有重大借鉴意义。

Abstract: At the end of 2019, the new crown pneumonia epidemic was raging, and the epidemic situation in Wuhan City and the entire Hubei Province was extremely severe. The National Health and Health Commission proposed to establish a one-to-one support relationship of “one province covers one city” to fully support the epidemic prevention work in Hubei Province. Based on this, this paper first uses principal component clustering to measure the aid level of 31 provinces and cities across the country, and obtains the strength of each province’s aid strength. In order to ensure that there are enough medical resources in the local area, taking into account factors such as distance and assistance level, 16 provinces and cities for assistance were selected by integer programming. Finally, based on the clustering results of the supporting provinces and cities and the supported cities, the supporting effect scores are set, and the supporting relationship is allocated by integer programming. This paper has great reference significance for screening and supporting provinces and cities and allocating aid forces under the epidemic situation.

1. 问题背景

1.1. 研究背景与文献综述

2019年底新冠疫情在武汉市爆发，武汉市及整个湖北省全境范围受到新冠病毒的严重威胁，为人民群众的生命财产安全带来了沉重打击。疫情爆发之初，面对传播速度快、变异率高的新冠病毒与日益增长的感染人数，疫情防控与治疗工作异常严峻。为解决包括武汉在内的一些城市存在医疗资源短缺的痛点、难点，国家卫生健康委提出“一省包一市”的援助模式。

针对疫情援助问题，目前多数文献侧重应急物资的运输与配送。沈兵(2020) [1] 与朱晔(2020) [2] 分析疫情下应急物资运输的难点与痛点，并提出相应的建议与对策；张立(2022) [3] 运用改进的蚁群算法解决不确定条件下多周期应急物资配送；冯春(2017) [4] 在综合考虑公平与效率的基础上，建立应急物资分类、分批的配送模型。

在已有文献中，少有学者探究疫情中地区间援助分配问题。刘畅、龚思强、党亚峥(2021) [5] 根据“一省包一市”的政策背景，依据运筹学中线性规划以及整数规划的思想，运用分配问题的模型及算法，得到了该问题的优化后的可行解。但以上研究在对援助省份与被援助地区进行评价时考虑的指标较少，并且在筛选援助省份时仅考虑总体医疗水平达到最大化。本文在此基础上，丰富指标选取的种类与范围，采用主成分与系统聚类结合的方法构建各地医疗援助实力评价模型。其次，本文基于援助省份与被援助地区聚类结果得援助效果分数，增强结果的可信度与准确性。此外，由于疫情下救援物资及时送达至关重要，本文在援助省份选择时综合考虑距离与医疗水平两个因素，进一步完善该模型。

1.2. 研究假设

为忽略细碎条件影响，本文做出如下假设：

1) 假设各地区各指标数据真实可信，不存在隐瞒、漏报等情况。

2) 假设各地到湖北省的距离为各省省会到武汉的距离。

3) 假设不同区域被分为医疗水平较高和医疗水平较低两类。其中医疗水平较高的地区派出60%的力量进行支援，留40%的力量进行防守，医疗水平较低的地区派出40%的力量进行支援，留60%的力量进行防守。

4) 假设位于同一聚类组的省份援助能力相同，位于同一聚类组的被支援城市疫情严重程度相同。

2. 数据说明

2.1. 数据选取

为了能够设计出具有较强实践意义的疫情援助分配方案，选取各省2021年度的各项指标(部分数据由于公布信息的延迟性以2020年的数据作为替代)作为研究数据。数据来源于各省份统计年鉴。

2.2. 变量说明

变量说明表如下表1。

Table 1. Variable definition table

表1. 变量定义表

3. 各省医疗援助实力评价建模分析

3.1. 医疗援助实力指标选取

实施援助的地区主要向被援助地区派遣医护人员以及输送医疗与生活物资。在疫情发生时，将相关物资及时送达被援助地区至关重要，各地运输能力决定了运输的效率。在进行援助时，应为自身留下足够的医疗资源。因此，医疗与生活物资的援助数量应考虑当地的经济发展水平；医护队的派遣与当地新冠疫情的防控与治疗都应考虑当地的医疗水平。此外，对援助实力的衡量应结合自身的潜在风险与社会力量，以保障自身疫情防控工作的顺利进行。

在综合参考李程跃(2011) [6] 以及张慧(2006) [7] 对突发公共卫生事件防控指标选取的基础上，本文共设立医疗水平、基础建设水平、经济发展水平、潜在风险与社会力量五个二级指标以及十八个三级指标衡量一个地区的援助水平，具体指标如图1所示：

Figure 1. Indicators for assessing aid strength

图1. 评价援助实力的各项指标

3.2. 主成分聚类

本文首先采用一种综合的降维统计方法——主成分分析，将原始数据中冗余数据进行剔除，将援助实力中多个指标转换为少数几个主成分，即将高维数据转化为低维数据，进而用少数几个主成分反映原始数据绝大多数的信息。

在主成分分析中，需对数据进行预处理，以将数据方向进行统一并消除数据量纲的影响。本文采用Excel软件对数据进行Z-Score标准化处理，其公式为：

$\frac{x_{ij}-\frac{1}{n}{\displaystyle \underset{i=1}{\overset{n}{\sum }}{x}_{ij}}}{s_{ij}}$ (1)

参考孙义豪(2017) [8] 的做法，对于正向化的指标只做标准化处理，对于负向指标进行标准化处理后取负数。求得协方差矩阵R的特征值与特征向量后，计算每个主成分的贡献率 $w_i$ 与累计贡献率 $\rho$ ，其中 $i=1,2,3,\cdots ,p$ 。选择保留前m个主成分使其累计贡献率超过80%，并计算第i个主成分的得分 $F_i$ ( $i=1,2,3,\cdots ,m$ )。

对主成分特征值与方差进行分析，前四个主成分特征值大于1，且前四个主成分累计贡献率达到82.47%，即可较为全面地反映原始数据的信息，因此选择这四个主成分表征原始数据中18个指标(具体结果见附录(一))。提取的主成分的贡献率分别为42.22%、22.30%、10.66%与7.29%。

使用matlab软件，可得各省份主成分的值如表2所示。

Table 2. Principal component score table

表2. 主成分得分表

使用spss软件对各省份的4个主成分得分数据进行系统聚类，使用瓦尔德法以及平方欧式距离，所得的谱系图如附录(二)所示。根据实际研究需要，将各省份援助实力分为四类，所得聚类结果利用颜色在地图上做出区分(如图2)，具体省份援助实力强弱见附录(三)。

Figure 2. Aid strength cluster plot

图2. 援助实力聚类图

3.3. 参与援助的省份的选择

3.3.1. 问题分析

在选择哪些省份参与对湖北省的援助时，我们考虑两方面的重要因素：一是各省医疗水平，二是各省与湖北省之间的距离，这两方面因素体现在目标函数却终的确定中。采用0-1规划模型根据各变量之间的约束条件最终求解出哪些省份适合参与援助。

3.3.2. 0-1规划模型求解

1) 变量设定：

设北京，天津，河北，山西，内蒙古，辽宁，吉林，黑龙江，上海，江苏，浙江，安徽，福建，江西，山东，河南，湖南，广东，广西，海南，重庆，四川，贵州，云南，西藏，陕西，甘肃，青海，宁夏，新疆分别为 $X_i\left(i=1,2,3,\cdots ,30\right)$ 。

其中 $X_i=\{\begin{array}{l}1,当选中i时\\ 0,当不选i时\end{array}$

2) 目标函数设立：

要从30个省份中挑选16个省进行援助，需综合考虑各省医疗水平和各省与湖北省之间的距离两个因素，选择总和分数最高的16个省份进行援助。由于援助省份的选择上有两个目标函数，即距离最短与医疗水平最高(分别记为 $F_1$ 与 $F_2$ )，为统一量纲，参考刘可(2018) [9] 的做法，对目标函数进行如下处理：

$F_i^{\ast }=\frac{F_i-\min F_i}{\max F_i-\min F_i}\left(i=1,2\right)$ (2)

将目标函数统一为最小化函数并进行加权，得

$\min F={\epsilon }_1{\displaystyle {\sum }_{i=1}^{30}{a}_{ij}{x}_{ij}}+{\epsilon }_2{\displaystyle {\sum }_{i=1}^{30}{b}_{ij}{x}_{ij}}\left(i,j=1,2,3,\cdots ,30\right)$ (3)

其中 ${\epsilon }_1$ 和 ${\epsilon }_2$ 分别为目标函数的权重。在进行援助的过程中，医疗水平相较距离更为重要，因此对 ${\epsilon }_1$ 和 ${\epsilon }_2$ 分别赋值为0.3与0.7。

3) 约束条件设定：

在选择进行援助的省份时，要为各个地理区域疫情防控留下充分的医疗资源。根据医疗水平综合评分得出结论：华东和中南地区医疗水平较高，华北、西南和西北地区医疗实力较弱。根据假设三确定资源系数( $b_j$ )。参考医疗水平综合评分，对于具体的约束条件如下：

$\text{s}\text{.t}\{\begin{array}{l}{x}_1+x_2+x_3+x_4+x_5\le 3\hfill \\ x_6+x_7+x_8\le 1\hfill \\ x_9+x_{10}+x_{11}+x_{12}+x_{13}+x_{14}+x_{15}\le 5\hfill \\ x_{16}+x_{17}+x_{18}+x_{19}+x_{20}\le 3\hfill \\ x_{21}+x_{22}+x_{23}+x_{24}+x_{25}\le 3\hfill \\ x_{26}+x_{27}+x_{28}+x_{29}+x_{30}\le 2\hfill \\ {\displaystyle {\sum }_{i=1}^{30}{x}_i}=16\hfill \\ x_i\in \left\{0,1\right\}\left(i=1,2,3,\cdots ,30\right)\hfill \end{array}$

利用matlab求解，结果整理如表3所示：

Table 3. Aid by province

表3. 各省援助情况

最终结果为1，表示为参与援助的省份；最终结果为0，表示为不参与援助的省份。由表可得，参与援助的省份包括：北京市、天津市、河北省、辽宁省、上海市、江苏省、浙江省、安徽省、山东省、河南省、湖南省、广东省、重庆市、四川省、贵州省、陕西省共16个省市。

4. 援助分配建模分析

4.1. 问题分析

在对参与援助的省份进行具体援助城市的选择时，首先根据被援助的城市的疫情影响状况进行K-Means聚类分析。根据聚类结果，对各省份与各城市之间对应的援助效果进行评分。在选取不同省份的援助目标时，使用0-1变量表示采取的方式，目标函数取不同援助方案下援助分数总和最大值。

4.2. 建立对援助省份和被援助城市的聚类分析

对湖北省被援助的各个城市的患病人数N，死亡人数DN，治愈人数CN，致死率RD与治愈率RC进行综合的K-Means聚类分析，根据聚类结果将其分为严重、较严重、较不严重，不严重四个等级。结果如表4所示：

Table 4. Classification of epidemic severity levels of cities in Hubei Province

表4. 湖北省各市疫情严重等级分类

4.3. 变量说明与模型假设

设孝感市，黄冈市，荆州市，鄂州市，随州市，襄阳市，黄石市，宜昌市，荆门市，咸宁市，十堰市，仙桃市，天门市，恩施州，潜江市，神农架市分别为 $c_j\left(j=1,2,3,\cdots ,15,16\right)$ 。设北京市，天津市，内蒙古自治区，上海市，江苏省，浙江省，福建省，山东省，湖南省，广东省，重庆市，贵州省，西藏自治区，宁夏回族自治区，新疆维吾尔自治区分别为 $d_i\left(i=1,2,3,\cdots ,15,16\right)$ 。

根据聚类结果，将参与救援省份的医疗水平和被救援市的疫情影响状况分别分为四个等级。假设医疗水平等级最好的省份对所有被援助地区的援助效果分数为100；医疗水平较好的省份对疫情严重的地区援助效果为90，其余为100；医疗水平较差的省份对疫情严重的地区援助效果为80，较严重的地区援助效果为90，其余为100；医疗水平最差的省份对疫情严重的地区援助效果为70，较严重的地区援助效果为80，较不严重的地区为90，其余为100。整理援助效果分数对应如表5所示：

Table 5. Aid effectiveness score

表5. 援助效果评分

4.4. 0-1规划模型的建立

1) 变量设定

引入0-1变量：

$x_{ij}=\{\begin{array}{l}1,当c_i援助d_j时\left(i,j=1,2,3,\cdots ,15,16\right)\\ 0,当c_i不援助d_j时\left(i,j=1,2,3,\cdots ,15,16\right)\end{array}$

2) 目标函数的设定：

援助的原则为综合医疗水平和受疫情影响状况，充分利用医疗资源，达到援助效果最大化。

$\max z_2={\displaystyle {\sum }_{i=1}^{30}{a}_{ij}{x}_{ij}}\left(i,j=1,2,3,\cdots ,15,16\right)$ (4)

3) 约束条件设定：

根据一省援助一市，一市仅由一省援助的原则，对该决策问题进行约束。

$\text{s}\text{.t}\text{.}\{\begin{array}{l}{\displaystyle {\sum }_{i=1}^{16}{x}_{ij}}=1\left(j=1,2,3,\cdots ,15,16\right)\\ {\displaystyle {\sum }_{j=1}^{16}{x}_{ij}}=1\left(i=1,2,3,\cdots ,15,16\right)\\ x_{ij}\in \left\{0,1\right\}\left(i,j=1,2,3,\cdots ,15,16\right)\end{array}$

4.5. 0-1规划模型求解：

利用matlab对模型进行求解，所得结果整理后如表6所示。

Table 6. The allocation table of the “one province, one city” aid program

表6. “一省包一市”援助方案分配表

表中横轴与纵轴相交数字为1，则表示进行援助的省份与被援助的地区进行匹配。由表中结果可得，北京省援助黄石市，天津市援助鄂州市，河北省援助荆州市……以此类推。

5. 总结与展望

本文依据国家卫生健康委提出建立“一省包一市”的一一对口支援关系，分析各地的医疗资源和疫情发生地的严重程度，建立了基于主成分分析与系统聚类的各省份医疗水平评价模型。并选取目标最短与总体医疗水平最强两个目标进行多目标整数规划，筛选出进行援助的省份。最后根据一省援助一市，一市仅由一省援助的原则，进行援助省份与被援助地区间匹配。所得模型不仅解决救助省的医疗资源与被救助地区疫情严重程度不匹配的问题，还有助于保障救助省尽可能快的到达被救助区展开救助活动。

本文所提的各省医疗水平的评价模型和救助匹配模型不仅适用于全国的疫情救助活动，还适用于地震等大规模灾后医疗救助以及各地医疗资源分配上提供参考与借鉴。在后续的研究中，笔者将把该模型进行改进和推广，进一步考虑多地援助一地，资源的分阶段分配等更接近实际情况的应用场景。

附录

(一) 特征根及其方差百分比

(二) 系统聚类谱系图

(三) 各省份援助实力强弱

NOTES

^*共一作者。

^#通讯作者。