改进的容量约束设施区划模型的算法及应用

吴建军 孔云峰

关键词：容量约束;改进区划模型;求解算法;公共服务设施优化

0 引言（Introduction）

公共服务设施空間布局的公平性是指服务的需求者对设施的使用机会是均等的，这也是公共服务设施空间布局的最终目的。公共服务设施空间布局涉及的是复杂空间的设施区位问题，简单来说就是对设施进行选址定位，具体是利用数学模型和算法寻找复杂问题中的最佳或近似最佳的解答，进而改善或优化现有系统的效率[1-3]。

现阶段，国内关于公共服务设施空间布局优化的研究比较丰富，邵晖等[4]、安芸睿[5]和许翔宇[6]采用各区人口与公共设施数量的比值等方法研究公共服务资源空间分布特征。李旭丽等[7]和罗萌[8]根据以研究区域内的公共服务设施数量与人口数量的供需情况采用对比分析的方法进行了研究。还有学者采用基于GIS的多准则决策分析的最优选址模型等方法进行了分析探讨[9-11]。这些研究都是较粗略的定量分析研究。空间布局优化研究所涉及的数据量非常大，目前关于公共服务设施优化布局的研究，已有理论研究者提出了一些数学模型和算法，但由于这些模型和算法属于NP难问题（NP-Hard），尤其对于中大规模问题，难以获得精确解，因此，这也是目前国内鲜少研究的领域。

1 经典的CFLP模型算法（Classic CFLP modelalgorithm）

得益于近几年计算机技术的进步和发展，空间布局规划问题模型解算效率快速提升，已逐步满足很多实际应用。基于此，本项目以基本医疗卫生服务设施为具体研究对象，借用经典的CFLP模型，并对模型进行进一步优化，设计、开发出解算工具，为实现公民公平享有公共卫生服务资源、节约政府公共投资提供技术支持。

优化设施布局就要进行精确的定量分析，本研究的算法原理是基于CFLP模型（经典的容量约束设施区位问题），首先令集合I={1，2，…，n}表示n 个候选医疗服务设施的空间位置，设施i（i∈I）有最大接诊量Si。令集合J={1，2，…，m}表示m 个需求点，需求点j（j∈J）的就医服务需求量为dj。空间单元i 与单元j 之间的距离成本为cij。定义布尔型决策变量xij 为是否指派医疗服务设施i 到需求空间j 进行服务，布尔型决策变量yi 表示是否在区位i 上建设医疗卫生服务设施，经典的单源CFLP模型如下：

其中：目标函数（1）最小化设施固定成本和使用服务的旅行成本;约束条件（2）保证每一个空间单元的需求获得公共服务;约束条件（3）保证每一个服务设施分配的服务量不超过其供给量;条件（4）定义决策变量xij 和yi。

2CFLP模型算法改进原理（Principle of improvingCFLP model algorithm）

经典的CFLP模型没有考虑设施服务半径，这会使得部分需求区位距离服务设施过远，缺少公平性方面的考虑。为克服这一局限，本文提出改进方法，即在模型中引入覆盖半径。令覆盖半径为ϕ，在约束条件（2）中加入服务半径限制，见约束条件（5）：

但是，约束条件（5）会导致所需设施数量大幅增加。为平衡服务成本、服务质量和空间公平性三者之间的关系，本文引入最低覆盖率μ继续对模型进行改进。在经典模型中增加新的约束条件（6），即设施在服务半径内覆盖需求总量满足最低覆盖率指标。

考虑到设施建设成本在规划阶段难以精确地估算，可将建设成本设置为一个较大的固定数值CAP，从而将目标函数（1）修改为（7）：

基于上述改进的CFLP模型，本研究进行算法求解的设计。借鉴单源CFLP数学启发算法进行求解。算法原理概括如下：（1）通过构造启发式算法获得问题初始解;（2）从当前解中随机选择一个超大邻域，获取邻域内的需求点、当前设施和候选设施集合;（3）构造邻域内子问题模型，求解模型获得局部解，并使用局部解更新当前全局解;（4）重复执行“步骤（2）”和“步骤（3）”，直到不能更新当前解。“步骤（2）”能构造一个大邻域，“步骤（3）”能发现邻域内的最优解。

模型经以上改进后，所有需求区位都能够满足服务半径的要求。

3 算法应用（Algorithm application）

3.1 软件安装

本研究所提算法的求解实质是求解线性规划问题的最优解。线性规划是研究线性约束条件下线性目标函数的极值问题的数学理论和方法。Python中有许多第三方的工具可以解决这类问题，本研究采用的是常用的pulp工具包。软件运行环境为Windows 10。此外，需要安装Gurobi（全球综合能力排名第一的数学规划求解器），获取Gurobi商业版或学术版软件，并安装在运行算法的计算机中。

3.2 数据准备

首先给定城市基本空间单元（500 m×500 m 的网格）、单元内就医需求数量（居民人数）、候选设施空间位置（医疗服务设施的地点）和设施的最大服务容量（卫生服务中心或卫生院的接诊量），其次选择一定数量的区域内医疗服务设施，满足所有居民点的就医需求，并指定服务半径（ϕ）和需求覆盖率（μ）要求，研究的最终目标是让所需要的服务设施的数目（N ）最少，使居民看病就医的旅行成本最低。

使用ARCGIS 10.6地理信息系统软件创建医疗服务供应者图层，在该图层中保持原有的29个基本医疗卫生服务设施，并在此基础上于KF市区的基本空间单元中选择173个候选点，作为备选医疗服务设施的备选点。本算法的目的是快速从候选点中选出最合适的服务设施的空间位置，从而尽可能地使每个居民点距离所对应的卫生服务设施最短，并且不能超过该服务设施的最大服务能力，即获得最优解。同时，要保证医疗服务设施数量最少。

从ArcGIS 10.6相关图层导出相应的属性表，进行整理后最终形成以下文本文件：

应用以上文本文件描述需求点和候选设施点。第1列为点位ID（整数类型），要求ID唯一;第2列为该点位服务需求量（整数类型），在本研究中具体指城市空间单元格的人数;第3、4列为坐标，单位为m;第5列为候选设施点的类型，对于现有的卫生服务中心和卫生院设置为“1”，即必选项，对于其他设施点设置为0;第6列为候选设施投资建设成本，为了尽可能地减少设施数量，设置了一个较大的数值，即1.0e8;第7列为设施容量，备选点为KF市区2021年基本医疗卫生服务设施的平均接诊量，现有的卫生服务设施必选点则是该点2021年的实际接诊量。

3.3 设施选址计算

本研究的算法使用Python程序设计，调用Gurobi优化求解器求解子问题模型。实验计算环境为PC个人计算机，配置英特尔Core i5-9400 @ 2.90 GHz六核处理器、16 GB内存和Windows 10操作系统。安装软件包括Python 2.7、ArcGIS 10.0和Gurobi 9.5.2。在ArcGIS中准备案例数据，包括城市基本空间单元及其属性di 和si、单元间距离成本cij 采用两个单元中心点的直线距离。

研究设置不同的参数，通过程序运行结果分析、总结设施布局优化方案。程序是在Windows命令窗口运行相关命令的。表1至表3是在分别设置了不同的规划参数即服务半径（ϕ）和覆盖率（μ），并设置不同服务设施总数量的情况下，应用改进模型算法得出的服务设施规划结果的统计。

从表1中可以看出，虽然设置了规划参数服务半径为1.0 km和覆盖率为80%，但是从实际的程序计算结果来看，在新增5个、29个现有设施点必选、共有34个卫生服务设施的限制条件下，满足规划参数服务半径为1.0 km时，其实际的人口覆盖率μ只有54.14%。

从表2中可以看出，虽然设置了规划参数服务半径为1.5 km和覆盖率为70%，但是从实际的程序计算结果来看，在新增5个、29个现有设施点必选、共有34个服务设施的限制条件下，当满足规划参数服务半径为1.5 km时，实际的人口覆盖率有70.12%，完全达到了预先设置的70%的人口覆盖率的规划参数。

从表3中可以看出，设置了规划参数服务半径为1.5 km和覆盖率为80%，从实际的程序计算结果来看，在保证29个现有设施点必选、不限定设施总数量的情况下，满足规划参数服务半径为1.5 km时，其实际的人口覆盖率为80.04%，完全达到了预先设置的规划参数，但是需要新增加18个卫生服务设施点。

图1显示的是在现有的29个基础卫生设施的基础之上，根据程序运算优化的结果，增加5个卫生服务设施的空间位置，城市空间单元选择500 m×500 m的网格，并删除50人以下的低密度人口區域网格。

图2显示的是限定34个设施（新增5个），优化新增卫生服务设施后的泰森多边形，平均就医距离为1.74 km，平均每个设施点服务2.80万人，最远就医距离为10 km，占比为0.067 6%，约642人，医疗卫生设施利用率较高。

不限定卫生服务设施总数的规划方案如图3所示，该方案没有限定卫生服务设施数量，根据程序计算得出共计47个卫生服务设施（新增18个），平均就医距离为1.38 km，平均每个设施点服务2.02 万人，最远就医距离为9 km，占比为0.057 7%，约549人，医疗卫生设施利用率较低。

4 结论（Conclusion

文章分析了经典的CFLP模型存在的局限性，为克服这一局限，提出可引入覆盖半径ϕ、最低覆盖率μ、设施建设成本CAP 对模型进行改进，实验结果表明，与传统模型算法相比，该模型算法兼顾了服务成本、服务质量和空间公平性三者之间的关系，改进的CFLP模型算法更加科学、合理，实用性更强，也可以应用于公共服务体系中的其他领域，如义务教育、公共文化设施等公共服务空间可达性评估，以利于优化布局。

该模型未来可以考虑引入居民的性别、年龄、职业、需求偏好等参数，进一步提高其准确性，为构建高质量和人性化的公共服务体系提供更可靠的技术支持。