留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

设施服务分区问题的求解算法框架设计

王玉璟 孔云峰

王玉璟, 孔云峰. 设施服务分区问题的求解算法框架设计[J]. 武汉大学学报 ● 信息科学版, 2021, 46(5): 726-735. doi: 10.13203/j.whugis20200393
引用本文: 王玉璟, 孔云峰. 设施服务分区问题的求解算法框架设计[J]. 武汉大学学报 ● 信息科学版, 2021, 46(5): 726-735. doi: 10.13203/j.whugis20200393
WANG Yujing, KONG Yunfeng. An Algorithm Framework for Facility Service Districting Problem[J]. Geomatics and Information Science of Wuhan University, 2021, 46(5): 726-735. doi: 10.13203/j.whugis20200393
Citation: WANG Yujing, KONG Yunfeng. An Algorithm Framework for Facility Service Districting Problem[J]. Geomatics and Information Science of Wuhan University, 2021, 46(5): 726-735. doi: 10.13203/j.whugis20200393

设施服务分区问题的求解算法框架设计

doi: 10.13203/j.whugis20200393
基金项目: 

国家自然科学基金 41871307

详细信息
    作者简介:

    王玉璟,博士生,讲师,研究方向为空间优化。yjwang@henu.edu.cn

    通讯作者: 孔云峰,博士,教授。yfkong@henu.edu.cn
  • 中图分类号: P208

An Algorithm Framework for Facility Service Districting Problem

Funds: 

The National Natural Science Foundation of China 41871307

More Information
    Author Bio:

    WANG Yujing, PhD candidate, lecturer, specializes in spatial optimization. E-mail: yjwang@henu.edu.cn

    Corresponding author: KONG Yunfeng, PhD, professor. E-mail: yfkong@henu.edu.cn
  • 摘要: 设施服务分区问题(facility service districting problem,FSDP)是指在一个地理区域内,根据服务设施位置和服务能力为其划分服务区,满足供需平衡、形状紧凑和空间连续等要求。空间连续约束使FSDP能更好地满足学区划分、医疗区划分等问题的政策需求,但同时增加了它的求解难度。构造了一个FSDP混合整型线性规划模型,并设计了一个算法框架。框架包括问题定义、初始解、搜索算子和策略等基本模块,支持精确算法、元启发算法和混合算法设计。基于算法框架,实现了数学模型、模拟退火算法、迭代局部搜索算法和数学启发混合算法,并使用4个中大规模案例进行算法测试。实验结果表明,算法框架能够很好地处理空间连续约束的FSDP,支持多种算法快速实现,且求解质量接近案例目标值下界。
  • 图  1  FSDP算法框架

    Figure  1.  Algorithm Framework of FSDP

    图  2  FSDP分区方案示例

    Figure  2.  An Instance of FSDP Solution

    图  3  案例区ZY和GY2示意图

    Figure  3.  Study Areas ZY and GY2

    图  4  案例ZYA和ZYB 15个设施服务区划分示意图

    Figure  4.  15 Facility Service Areas of ZYA and ZYB

    图  5  案例GY2A和GY2B 22个设施服务区划分示意图

    Figure  5.  22 Facility Service Areas of GY2A and GY2B

    表  1  4个测试案例的主要属性

    Table  1.   Attributes of Four Cases

    案例 区域特征 地理单元数 邻接关系 设施数 设施容量 服务需求量 供需比
    ZYA 城区 324 1 618 15 4 470 3 873 1.154
    ZYB 城区 324 1 618 15 3 979 3 873 1.027
    GY2A 县域 1 276 7 820 22 975 947 819 812 1.190
    GY2B 县域 1 276 7 820 22 843 424 819 812 1.029
    下载: 导出CSV

    表  2  5种算法求解服务分区结果统计

    Table  2.   Solution Results of Five Algorithms

    算法 统计指标 ZYA ZYB GY2A GY2B
    CPLEX 总距离/km 1 656.53* 1 874.58* 1 875 355.92* 2 003 951.77
    GAP/% 0 0 0 0.01
    运行时间/s 83.00 112.70 401.82 7 204.54
    SA 平均总距离/km 1 668.27 1 900.16 1 875 788.04 2 007 153.45
    最好总距离/km 1 661.37 1 892.22 1 875 563.99 2 006 397.20
    平均GAP/% 0.71 1.36 0.02 0.17
    平均运行时间/s 53.81 54.03 252.06 224.45
    SA-SPP 平均总距离/km 1 662.98 1 898.53 1 875 396.63 2 005 921.36
    最好总距离/km 1 661.37 1 891.16 1 875 355.92* 2 004 889.09
    平均GAP/% 0.39 1.28 0.00 0.11
    平均运行时间/s 57.58 59.32 259.65 258.65
    SPP改进/% 0.32 0.09 0.02 0.00
    SPP平均运行时间/s 3.77 5.29 7.60 34.20
    ILS 平均总距离/km 1 663.92 1 910.10 1 876 169.80 2 009 310.83
    最好总距离/km 1 660.19 1 904.51 1 875 633.19 2 007 623.64
    平均GAP/% 0.45 1.90 0.04 0.28
    平均运行时间/s 53.13 60.62 140.63 224.80
    ILS-SPP 平均总距离/km 1 657.08 1 905.24 1 875 476.09 2 006 901.47
    最好总距离/km 1 656.53* 1 895.06 1 875 367.74 2 005 088.75
    平均GAP/% 0.03 1.64 0.01 0.16
    平均运行时间/s 58.56 153.64 145.04 267.03
    SPP改进/% 0.41 0.23 0.04 0.12
    SPP平均运行时间/s 5.43 93.02 4.41 42.23
    注:*表示算法获得的最优解
    下载: 导出CSV
  • [1] Gilbert L, Stefan N, Francisco S. Location Science[M]. Cham: Springer, 2015
    [2] Tong D, Murray A T. Spatial Optimization in Geography[J]. Annals of the Association of American Geographers, 2012, 102(6): 1 290-1 309 doi:  10.1080/00045608.2012.685044
    [3] 王铮, 吴静. 计算地理学[M]. 北京: 科学出版社, 2016

    Wang Zheng, Wu Jing. Computation Geography[M]. Beijing: Science Press, 2016
    [4] 黎夏, 刘小平, 李少英. 智能式GIS与空间优化[M]. 北京: 科学出版社, 2010

    Li Xia, Liu Xiaoping, Li Shaoying. Intelligent GIS and Spatial Optimization[M]. Beijing: Science Press, 2010
    [5] Hess S W, Weaver J B, Siegfeldt H J, et al. Nonpartisan Political Redistricting by Computer[J]. Operations Research, 1965, 13(6): 998-1 008 doi:  10.1287/opre.13.6.998
    [6] Kalcsics J, Nickel S, Schröder M. Towards a Unified Territorial Design Approach: Applications, Algorithms and GIS Integration[J]. TOP, 2005, 13(1): 1-56 doi:  10.1007/BF02578982
    [7] Xiao N. A Unified Conceptual Framework for Geographical Optimization Using Evolutionary Algorithms[J]. Annals of the Association of American Geographers, 2008, 98(4): 795-817 doi:  10.1080/00045600802232458
    [8] Ricca F, Scozzari A, Simeone B. Political Districting: From Classical Models to Recent Approaches[J]. 4OR: A Quarterly Journal of Operations Research, 2011, 9(3): 223-254 doi:  10.1007/s10288-011-0177-5
    [9] 孔云峰, 朱艳芳, 王玉璟. 学校分区问题混合元启发算法研究[J]. 地理学报, 2017(2): 256-268 https://www.cnki.com.cn/Article/CJFDTOTAL-DLXB201702007.htm

    Kong Yunfeng, Zhu Yanfang, Wang Yujing. A Hybrid Metaheuristic Algorithm for the School Districting Problem[J]. Acta Geographica Sinica, 2017(2): 256-268 https://www.cnki.com.cn/Article/CJFDTOTAL-DLXB201702007.htm
    [10] Keane M. The Size of the Region-Building Problem[J]. Environment and Planning A, 1975, 7(5): 575-577 doi:  10.1068/a070575
    [11] Bucarey V, Ordóñez F, Bassaletti E. Shape and Balance in Police Districting[M] // Eiselt H A, Marianov V. Applications of Location Analysis. Cham: Springer, 2015
    [12] Duque J C, Ramos R. Design of Homogenous Territorial Units: A Methodological Proposal and Applications[J]. Working Papers in Economics, 2004, 70(3): 314-331 http://dialnet.unirioja.es/servlet/tesis?codigo=88133
    [13] Ricca F, Simeone B. Local Search Algorithms for Political Districting[J]. European Journal of Operational Research, 2008, 189(3): 1 409-1 426 doi:  10.1016/j.ejor.2006.08.065
    [14] Duque J C, Church R L, Middleton R S. The p-Regions Problem[J]. Geographical Analysis, 2011, 43(1): 104-126 doi:  10.1111/j.1538-4632.2010.00810.x
    [15] Kong Y F, Zhu Y, Wang Y. A Center-Based Modeling Approach to Solve the Districting Problem[J]. International Journal of Geographical Information Science, 2018, 33(1/2): 368-384
    [16] Minciardi R, Puliafito P P, Zoppoli R. A Districting Procedure for Social Organizations[J]. European Journal of Operational Research, 1981, 8(1): 47-57 doi:  10.1016/0377-2217(81)90028-X
    [17] Ferland J A, Guénette G. Decision Support System for the School Districting Problem[J]. Operations Research, 1990, 38(1): 15-21 doi:  10.1287/opre.38.1.15
    [18] Ko J, Nazarian E, Nam Y, et al. Integrated Redistricting, Location-allocation and Service Sharing with Intra-district Service Transfer to Reduce Demand Overload and Its Disparity[J]. Computers, Environment and Urban Systems, 2015, 54: 132-143 doi:  10.1016/j.compenvurbsys.2015.07.002
    [19] 何雪, 韦波, 张晓宇, 等. 一种求解学区划分问题的混合启发式算法[J]. 测绘科学, 2020, 45(1): 163-170 https://www.cnki.com.cn/Article/CJFDTOTAL-CHKD202001023.htm

    He Xue, Wei Bo, Zhang Xiaoyu, et al. A Hybrid Heuristic Algorithm for Solving School District Division Problem[J]. Science of Surveying and Mapping, 2020, 45(1): 163-170 https://www.cnki.com.cn/Article/CJFDTOTAL-CHKD202001023.htm
    [20] Kim K. A Spatial Optimization Approach for Simultaneously Districting Precincts and Locating Polling Places[J]. ISPRS International Journal of Geo-Information, 2020, 9(5): 301-317 doi:  10.3390/ijgi9050301
    [21] 孔云峰. 利用GIS与线性规划学校最优学区划分[J]. 武汉大学学报∙信息科学版, 2012, 37(5): 513-515 https://www.cnki.com.cn/Article/CJFDTOTAL-WHCH201205003.htm

    Kong Yunfeng. Optimal School Allocation Using GIS and Linear Programming[J]. Geomatics and Information Science of Wuhan University, 2012, 37(5): 513-515 https://www.cnki.com.cn/Article/CJFDTOTAL-WHCH201205003.htm
    [22] 孔云峰, 朱艳芳, 王玉璟. 整型规划求解空间连续约束学校分区问题[J]. 河南大学学报(自然版), 2017, 47(5): 13-20 https://www.cnki.com.cn/Article/CJFDTOTAL-HDZR201705002.htm

    Kong Yunfeng, Zhu Yanfang, Wang Yujing. Integer Programming for the Spatially-Contiguity Constrained School Districting Problem[J]. Journal of Henan University(Natural Science), 2017, 47(5): 13-20 https://www.cnki.com.cn/Article/CJFDTOTAL-HDZR201705002.htm
    [23] Shirabe T. A Model of Contiguity for Spatial Unit Allocation[J]. Geographical Analysis, 2005, 37(1): 2-16 doi:  10.1111/j.1538-4632.2005.00605.x
    [24] Maniezzo V, Stützle T, Voß S. Matheuristics: Hybridizing Metaheuristics and Mathematical Programming[M]. New York: Springer, 2010
    [25] Lagos C, Guerrero G, Cabrera E, et al. A Matheuristic Approach Combining Local Search and Mathematical Programming[J]. Scientific Programming, 2016, 2016(Pt. 1): 1-7 doi:  10.1155/2016/1506084
  • [1] 郭宇达, 朱欣焰, 呙维, 佘冰.  基于Spark计算框架的路网核密度估计并行算法 . 武汉大学学报 ● 信息科学版, 2020, 45(2): 289-295. doi: 10.13203/j.whugis20180473
    [2] 钟何平, 唐劲松, 张森, 黄攀.  集群环境下的复合最小不连续相位解缠算法 . 武汉大学学报 ● 信息科学版, 2019, 44(9): 1363-1368. doi: 10.13203/j.whugis20170323
    [3] 钟何平, 唐劲松, 张森, 田振.  共享内存环境下的分块最小不连续相位解缠算法 . 武汉大学学报 ● 信息科学版, 2018, 43(9): 1385-1390. doi: 10.13203/j.whugis20160373
    [4] 刘子维, 张晓彤, 张锐, 江颖, 韦进, 张坤.  连续重力观测异常模式的多分辨率识别算法 . 武汉大学学报 ● 信息科学版, 2018, 43(6): 840-846, 942. doi: 10.13203/j.whugis20160173
    [5] 钟何平, 田振, 吴浩然, 徐魁, 唐劲松.  非递归最小不连续相位解缠算法及其优化方法 . 武汉大学学报 ● 信息科学版, 2017, 42(10): 1411-1416. doi: 10.13203/j.whugis20150785
    [6] 魏海涛, 杜云艳, 周成虎, 易嘉伟.  利用ANNS的空间信息处理服务智能集成算法 . 武汉大学学报 ● 信息科学版, 2015, 40(1): 14-19.
    [7] 蒋东方, 童余德, 边少锋, 向才炳.  ICCP重力匹配算法在局部连续背景场中的实现 . 武汉大学学报 ● 信息科学版, 2012, 37(10): 1203-1206.
    [8] 刘耀林, 夏寅, 刘殿锋, 洪晓峰.  基于目标规划与模拟退火算法的土地利用分区优化方法 . 武汉大学学报 ● 信息科学版, 2012, 37(7): 762-765.
    [9] 王汉东, 乐阳, 李宇光, 黄玲.  城市商业服务设施吸引力的空间相关性分析 . 武汉大学学报 ● 信息科学版, 2011, 36(9): 1102-1106.
    [10] 李德仁, 黄俊华, 邵振峰.  面向服务的数字城市共享平台框架的设计与实现 . 武汉大学学报 ● 信息科学版, 2008, 33(9): 881-885.
    [11] 郭锦娣, 周雁舟.  基于混合混沌序列的对称图像加密算法设计 . 武汉大学学报 ● 信息科学版, 2008, 33(10): 1084-1087.
    [12] 李睿, 李明, 张贵仓.  基于随机分块的脆弱性水印算法设计 . 武汉大学学报 ● 信息科学版, 2006, 31(9): 832-834.
    [13] 吴小芳, 杜清运, 徐智勇, 蔡忠亮.  复杂线状符号的设计及优化算法研究 . 武汉大学学报 ● 信息科学版, 2006, 31(7): 632-635.
    [14] 孔令罔, 朱元泓, 李琼.  以混合算法建立宽带多光谱色彩表示空间 . 武汉大学学报 ● 信息科学版, 2006, 31(9): 788-791.
    [15] 王方雄1, 边馥苓1.  基于网格的空间信息原子服务互操作与集成框架 . 武汉大学学报 ● 信息科学版, 2005, 30(2): 182-186.
    [16] 朱家松, 龚健雅, 郑皓.  遗传算法在管网优化设计中的应用 . 武汉大学学报 ● 信息科学版, 2003, 28(3): 363-367.
    [17] 刘经南, 刘晖.  连续运行卫星定位服务系统——城市空间数据的基础设施 . 武汉大学学报 ● 信息科学版, 2003, 28(3): 259-264.
    [18] 胡鹏, 胡毓钜, 杨传勇, 吴艳兰.  我国地球空间数据框架的设计思想、技术路线及若干理论问题讨论 . 武汉大学学报 ● 信息科学版, 2002, 27(3): 283-288.
    [19] 李德仁, 龚健雅, 朱欣焰, 梁宜希.  我国地球空间数据框架的设计思想与技术路线 . 武汉大学学报 ● 信息科学版, 1998, 23(4): 297-303.
    [20] 王新生.  线性规划原理在城市道路控制点标高优化设计中的应用 . 武汉大学学报 ● 信息科学版, 1995, 20(3): 269-272.
  • 加载中
图(5) / 表(2)
计量
  • 文章访问数:  499
  • HTML全文浏览量:  184
  • PDF下载量:  40
  • 被引次数: 0
出版历程
  • 收稿日期:  2020-08-02
  • 刊出日期:  2021-05-05

设施服务分区问题的求解算法框架设计

doi: 10.13203/j.whugis20200393
    基金项目:

    国家自然科学基金 41871307

    作者简介:

    王玉璟,博士生,讲师,研究方向为空间优化。yjwang@henu.edu.cn

    通讯作者: 孔云峰,博士,教授。yfkong@henu.edu.cn
  • 中图分类号: P208

摘要: 设施服务分区问题(facility service districting problem,FSDP)是指在一个地理区域内,根据服务设施位置和服务能力为其划分服务区,满足供需平衡、形状紧凑和空间连续等要求。空间连续约束使FSDP能更好地满足学区划分、医疗区划分等问题的政策需求,但同时增加了它的求解难度。构造了一个FSDP混合整型线性规划模型,并设计了一个算法框架。框架包括问题定义、初始解、搜索算子和策略等基本模块,支持精确算法、元启发算法和混合算法设计。基于算法框架,实现了数学模型、模拟退火算法、迭代局部搜索算法和数学启发混合算法,并使用4个中大规模案例进行算法测试。实验结果表明,算法框架能够很好地处理空间连续约束的FSDP,支持多种算法快速实现,且求解质量接近案例目标值下界。

English Abstract

王玉璟, 孔云峰. 设施服务分区问题的求解算法框架设计[J]. 武汉大学学报 ● 信息科学版, 2021, 46(5): 726-735. doi: 10.13203/j.whugis20200393
引用本文: 王玉璟, 孔云峰. 设施服务分区问题的求解算法框架设计[J]. 武汉大学学报 ● 信息科学版, 2021, 46(5): 726-735. doi: 10.13203/j.whugis20200393
WANG Yujing, KONG Yunfeng. An Algorithm Framework for Facility Service Districting Problem[J]. Geomatics and Information Science of Wuhan University, 2021, 46(5): 726-735. doi: 10.13203/j.whugis20200393
Citation: WANG Yujing, KONG Yunfeng. An Algorithm Framework for Facility Service Districting Problem[J]. Geomatics and Information Science of Wuhan University, 2021, 46(5): 726-735. doi: 10.13203/j.whugis20200393
  • 设施服务分区问题(facility service districting problem,FSDP)是为设施划分服务范围。在一个特定地理区域内存在若干服务设施,按照设施的位置和服务能力对设施的服务范围进行划分。例如为义务教育学校划分学区,为基层医疗服务中心划分服务区等。一般来说,服务区应当满足供需平衡、形状紧凑和空间连续等要求。供需平衡要求设施的服务供应与服务区内的服务需求相匹配,服务区紧凑能够提升使用服务的可达性,而服务区空间连续可能是某些法规要求,也方便于公共或商业服务管理。

    设施服务分区问题是地理学中的一种重要应用,也是区位科学中的一个分支[1]。服务设施的位置、服务能力、服务范围经常会引起公众的密切关注,也会在一定程度上决定人们的生活质量。尤其是幼儿园、中小学、社区健康服务中心、老年日照中心等保障民生基本需求的公共设施,现实生活中有必要对这些设施进行合理的服务区划分。而警察巡逻区、商品销售区、选举区等均等分区问题也与FSDP密切相关。

    空间优化是地理学的重要研究领域之一[2]。设施空间优化主要采用离散的区位数据,使用设施选址模型和求解方法,分析设施布局,提供决策和评价[3-4]。FSDP基于设施区位理论、模型和方法,兼有设施容量限制、空间连续性等约束[5-9],可以看作是一个受空间连续性约束的设施区位(location-allocation,LA)问题,或者一个带有容量约束的区划问题。FSDP是对经典区位、区划问题的扩展和延伸。区位问题本身计算复杂度极高,空间连续性约束更增加了问题求解难度,文献[10]证明了空间连续性约束分区问题是一类NP(nondeterministic polynominal)难问题。

    历史文献中,学者们经常借助经典LA问题模型来求解分区问题。文献[5]最早借用带容量限制的k-median区位模型求解均等分区问题;文献[6]基于LA模型建立了一个通用均等分区问题解决框架;文献[11]通过改变k-median模型建立分区均衡、形状紧凑的警察巡逻区。但是,LA模型本身没有空间连续性约束。这类文献的数学模型大多数不考虑分区的空间连续性问题,获得的分区方案往往不能保证空间连续,有的分区甚至会被分割。少数文献考虑了分区的空间连续性问题,但是在数学模型中没有使用严格意义的空间连续约束,而实际应用中往往要求分区连续,如学校、医疗等。分区不连续不能满足实际管理和生活需求,容易引起各种争议。

    在区划问题研究领域中,学者们考虑了分区的空间连续性约束。文献[12]借助图论处理空间连续性约束,构建分区问题混合整型模型;文献[13]采用经典的图论描述选区划分问题,实现了多种局部搜索算法求解;文献[7]在定义研究区域地理空间关系的基础上,基于演化算法建立一个通用概念框架,主要求解选址和均等分区问题;文献[14]将p-区域分区问题表达为3种混合整形规划模型,分别是树模型、次序模型和流模型;文献[15]建立了混合整型线性数学模型求解中大规模均等分区问题。但是,这些研究主要集中在选区、警察巡逻区、商品销售区等均等分区问题上。均等分区问题更关注各分区间的均衡,FSDP则强调分区内的供需平衡。两者问题定义有差异,均等分区问题的求解方法不能直接解决FSDP。

    已有学者对学校、医疗等设施服务区划分进行研究。文献[16]以医疗卫生服务分区问题为例,要求将地理区域划分为指定数量的非重叠的分区;文献[17]分析学校分区问题,要求每个学区中只包含一个学校,兼顾学校的容量限制、使用公平性、可达性等要求;文献[18]将设施区位和分区问题整合讨论,使用模拟退火算法成功求解了一个法庭审判服务分区问题;文献[9]采用多启动和迭代局部搜索混合元启发算法对中国义务教育的单校划片和多校划片问题进行了研究;文献[19]设计了迭代禁忌搜索与模拟退火混合算法求解柳州市柳南区学校划片问题;文献[20]提出设施选址和服务区划分同时进行,建立混合整型数学模型完成了选举区的划分和选举区内投票站的选址。这些文献讨论了连续性约束的设施服务区划分问题,但是,在优化算法方面体现不够,模型计算效率偏低,优化质量不高,算法之间存在差异,既缺乏比较,又缺乏基准测试案例,相关算法的计算效率与优化性能尚不清晰,整体不够成熟。

    本文综合考虑各类设施服务规划中的供需均衡、分区连续、便捷利用等普适性准则,对FSDP进行了定义,提出了一个带有容量限制和空间连续性约束的混合整型线性规划(mixed integer linear programming,MILP)数学模型。在分析各种求解算法的基础上,本文设计了一个FSDP算法框架,基于这个算法框架,多种算法机制可以组合使用。本文还设计了不同规模和设施容量的案例,通过多种算法的实现和案例测试来评估算法性能。

    • FSDP是在设施位置和容量已经确定的情况下,遵循设施就近原则,将一个区域内的地理单元指派到各个设施服务区。设施所在地理单元称为设施单元,需求所在地理单元称为需求单元。FSDP要求服务区供需平衡、空间连续、空间可达,以及地理单元完整且唯一指派。供需平衡要求服务区内各地理单元的服务需求总和不能大于设施服务容量。空间可达性可以通过服务区内各需求单元到设施单元的总距离来评估,一般优先选择最短距离。空间连续性是服务分区满足政策和管理要求的必要条件。单元完整性是指分区时不允许将基本单元分割。唯一性要求每个单元只能指派到一个服务区。

      一个地理区域U包含n个地理单元和m个设施,集合U={1,2… n}。每一个地理单元i具有属性AiBi,其中,Ai表示空间单元i的服务需求量;Bi表示地理单元i内设施容量,Bi=0则表示地理单元i内无设施。变量Dik表示地理单元i与设施单元k之间的距离;变量Cij代表地理单元ij是否邻接,地理单元i的邻接单元集合表示为Ni={ j | Cij =1};变量K表示要划分的设施服务区数量。设施服务区集合S={s1 s2 … sK }(sKU)表示K个设施服务区。分区目标是需求单元到设施单元的总距离函数值最小。

      FSDP就是在一定约束条件下,将集合U划分为K个空间连续的子集sK。参考文献[21-22],建立一个MILP模型将FSDP描述为一个带空间连续性约束的指派问题。参考文献[14, 23],使用网络流模型来表示设施服务区的空间连续性约束。FSDP的数学模型为:

      $$ \min \mathop \sum \limits_{i \in U} \mathop \sum \limits_{k \in S} {A_i}{D_{ik}}{y_{ik}} $$ (1)
      $$ {\rm{s}}.{\rm{t}}.\mathop \sum \limits_{k \in S} {y_{ik}} = 1, \forall i \in U $$ (2)
      $$\mathop \sum \limits_{i \in U} {A_i}{y_{ik}} \le {B_k}, \forall k \in S$$ (3)
      $$ {f_{ijk}} \le {y_{ik}}\left( {n - K} \right), \forall i \in U, j \in {N_i}, \forall k \in S $$ (4)
      $${f_{ijk}} \le {y_{jk}}\left( {n - K} \right), \forall i \in U, j \in {N_i}, \forall k \in S$$ (5)
      $$\mathop \sum \limits_{j \in {N_i}} {f_{ijk}} - \mathop \sum \limits_{j \in {N_i}} {f_{jik}} \ge {y_{ik}}, \forall i \in U\backslash S, \forall k \in S$$ (6)
      $$\mathop \sum \limits_{j \in {N_i}} {f_{ijk}} - \mathop \sum \limits_{j \in {N_i}} {f_{jik}} \ge K - n, \forall i \in S, \forall k \in S$$ (7)
      $${y_{ik}} = \left\{ {0, 1} \right\}, \forall i \in U, k \in S$$ (8)
      $$ {f_{ijk}} \ge 0, \forall i \in U, j \in {N_i}, k \in S $$ (9)

      函数(1)为优化目标,求解每个分区中需求单元到设施单元的总距离的最小值。约束条件(2)要求每个地理单元i必须且唯一指派到一个设施服务区。约束条件(3)是设施容量限制,要求保证每个设施服务区的需求量不能超过设施容量。约束条件(4)~(7)是基于网络流概念构造的,保证设施服务区k的空间连续性。条件(4)、(5)保证属于同一个设施服务区k的两个相邻单元ij才可能产生流。设施服务区k中,如果单元i不是设施单元,约束条件(6)确保该单元产生1个单位流量;约束条件(7)保证设施单元最多汇入(nK)个单位流量。模型中定义2个决策变量,约束条件(8)、(9)是对决策变量取值的限定,yik表示地理单元i是否分配到设施单元k,取值只能是0或者1;fijk是非负整数,表示设施服务区k内从地理单元i到单元j的流量。

    • 设施服务分区问题FSDP算法框架如图 1所示。这个算法框架面向设施服务分区问题,支持使用精确算法、元启发算法及混合算法求解,遵循算法实现的有效性、简单性和灵活性原则,同时具有可重用性和扩展性等特点。在底层问题定义和数据结构模块的基础上建立基本操作和数学模型,根据顶层应用问题的需要选择初始方案、邻域搜索算子和启发策略,调用数学模型、元启发算法或混合算法,对实际FSDP进行求解。

      图  1  FSDP算法框架

      Figure 1.  Algorithm Framework of FSDP

    • 在算法框架中,问题定义和数据结构模块主要将FSDP的描述转换成数据表达,定义区域、服务区、需求单元、设施单元、单元邻接关系、分区方案等数据结构。每一个分区方案用一个整型数组来表示。数组的长度就是地理单元的个数,值是服务区的编号。如图 2所示的案例将100个地理单元划分为6个服务区,其中,方格代表需求单元,阴影代表设施单元,数字表示单元所属服务区编号,粗线是各服务区的分界线,分界线两边的单元是边界单元,边界单元①、③、⑥分别与一个分区相邻,边界单元②、④分别有两个相邻分区,边界单元⑤有3个相邻分区。

      图  2  FSDP分区方案示例

      Figure 2.  An Instance of FSDP Solution

      基本操作模块在数据结构的基础上,提供算法中常用的公共操作方法,例如文件读入、数据输出、分区空间连续性判断、各种约束检测、优化目标评价、更新分区方案等。这些操作方法主要供初始方案、邻域搜索算子、启发策略、数学模型等选择和调用。

    • 基本算法包含初始方案、邻域搜索算子、启发策略、元启发算法等模块。

      初始方案模块提供了运输问题(transportation problem,TP)模型和区域生长算法来获得初始方案。调用时可以指定初始方案生成算法,也可以随机选择。用于获取初始方案的TP模型为:

      $$\min \mathop \sum \limits_{i \in U} \mathop \sum \limits_{k \in S} \left( {1 + {\varepsilon _{ik}}} \right){D_{ik}}{y_{ik}}$$ (10)
      $${\rm{s}}.{\rm{t}}.\mathop \sum \limits_{k \in S} {y_{ik}} = 1, \forall i \in U$$ (11)
      $$\mathop \sum \limits_{i \in U} {y_{ik}} \le {B_k}, \forall k \in S$$ (12)
      $${y_{ik}} \ge 0, \forall i \in U, k \in S$$ (13)

      为了获得不同的初始方案,在TP模型的目标函数中引入随机系数εik(|εik| < 0.02)。TP模型生成的解有可能将一个需求单元分割为若干块。为了保持地理单元完整性,按照较大块所在分区进行指派。TP模型产生的解也有可能不满足空间连续性约束,需要进行检测、判定和修复。

      区域生长算法是一种典型的构造启发式算法。这种算法用于FSDP问题时,将设施单元作为分区的种子单元,但向邻近地理单元逐步“生长”,直至满足终止条件,形成各设施服务区。区域生长算法思路简单且应用广泛,获得的解空间连续,但是该算法仅顾及局部相邻单元,求解质量不高,部分分区可能违背约束条件,需要后续算法改进。

    • FSDP要求分区空间连续,邻域搜索时只有尝试移动边界单元才有意义。而且并不是所有边界单元都可以移动,有些单元移动可能会破坏原分区的连通性,如图 2中的边界单元④。

      FSDP邻域搜索算子将分区的一个或多个边界单元移入相邻分区。这种单元的移动必须保持分区连通性,能够提升优化目标值,从而更新分区方案。算法框架提供了3个邻域搜索算子:One Unit Move、Two Unit Move和Three Unit Move。

      One Unit Move算子是将一个分区的某个边界单元从原分区移入到它的某个相邻分区,一般涉及2个分区。Two Unit Move算子将第1分区的某个边界单元移入到相邻分区(第2分区),又从第2分区中移出一个边界单元到它的相邻分区(第3分区),一般涉及3个分区。特殊地,第3分区恰好是第1分区,即交换了两个相邻分区中的单元。Three Unit Move算子是在不超过4个分区中移动3个单元:从第1分区中选择一个边界单元移到相邻第2分区;从第2分区移出一个边界单元到相邻第3分区;再从第3分区移出一个边界单元到相邻第4分区。很明显,Three Unit Move算子探索了一个更大的邻域空间,时间复杂度也会更高。

      One Unit Move算子实现时,首先构建当前分区方案中的所有边界单元集合(至多n个),遍历集合中的每个边界单元;针对每个边界单元,再遍历其所有相邻分区(至多K-1个),判断是否可以将它移动到该分区:移动后,涉及的所有分区保持空间连续,优化目标值得到提升则可以移动;如果满足移动条件,则改进分区方案。算子的计算复杂度是OnK)。

      3个算子的实现原理相同。在搜索过程中,Two Unit Move算子尝试移动2个边界单元,Three Unit Move算子尝试移动3个边界单元,因此,这两个算子的计算复杂度更高,分别是On2K)和On3K)。但是,实际操作中可以被移动的单元个数是非常少的。首先,边界单元的个数有限,只有边界单元才可以被移动到它的相邻分区;其次,边界单元的相邻分区个数有限,一个边界单元只有一个或几个相邻分区可用。3个算子的计算时间相比,Three Unit Move算子相对耗时,但在某些情况下,用来探索邻域解可能非常有效。

    • 启发策略模块主要包含多启动、搜索策略、扰动策略、接受准则。

      元启发算法可以采用多启动方法,在多次启动过程中构造不同的初始解,以避免算法对初始解过于依赖。搜索策略包括随机和顺序,如邻域搜索时随机地选择边界单元移动。扰动策略有单元移动、交换,也有破坏重建,都是用来扩大算法的搜索空间,避免陷入局部最优。接受准则可以是首次接受、最优接受、阈值接受,主要是根据分区方案的优化目标评价决定是否接受邻域解。

    • 算法框架主要有3个数学模型:FSDP模型、TP模型和集合划分问题(set-partitioning problem,SPP)模型。

      FSDP精确算法求解是通过本文§2提出的MILP数学模型来完成的。算法框架中的元启发算法可以采用TP模型来获取服务区划分的初始方案,也可以和SPP模型进行算法混合,获取质量更高的分区方案。

      SPP模型求解时需要先构造大量分区,再通过模型选择最优的分区组合。求解结果取决于构造分区的数量和质量。在元启发算法的邻域搜索过程中会产生大量的服务分区,记录所有出现的服务分区构成集合Ω。每一个服务分区i具有目标属性Oi和单元集合Ui。构建SPP模型,从服务区集合Ω中选择子集,实现最小目标函数,并全覆盖地理单元集合U。定义ΩjΩ的子集,是一个包含空间单元j的分区的集合,定义决策变量xi表明候选服务分区i是否被选中。SPP模型描述为:

      $$\min \mathop \sum \limits_{i \in \Omega } {O_i}{x_i}$$ (14)
      $${\rm{s}}.{\rm{t}}.\mathop \sum \limits_{i \in {\Omega _j}} {x_i} = 1, \forall j \in U$$ (15)
      $${x_i} = \left\{ {0, 1} \right\}, \forall i \in {\mathit{\Omega}} $$ (16)
    • FSDP算法框架支持精确算法、元启发算法和混合算法等多种求解方式。算法框架已经实现了常见的模拟退火(simulated annealing,SA)、迭代局部搜索(iterated local search,ILS)、记录更新(record-to-record travel,RRT)、禁忌(tabu,TA)、变邻域搜索(variable neighborhood search,VNS)等元启发算法,同时支持多种元启发算法混合、Matheuristic混合算法求解,目的在于发挥每种算法机制的优点,提升优化目标值。在解决具体FSDP应用问题时,可以选择适宜求解方法,获得满足实际需求的设施服务分区规划方案。

      将元启发算法和数学模型混合构成的算法称为Matheuristics算法[24],已经被用来解决复杂的设施选址问题[25]。本文基于FSDP算法框架设计两个Matheuristics算法:SA-SPP和ILS-SPP。分别选择SA算法、ILS算法作为混合算法的基本结构,采用多启动(M)方式,使用TP模型生成初始分区方案,元启发算法搜索过程中更新分区方案,同时记入服务分区集合,再调用SPP模型求解,以期进一步改进分区方案。

    • 基于FSDP算法框架构造SA-SPP混合算法,设置SA算法参数初始温度InitT和循环次数Loop。

      1)采用多启动方法,M次启动SA算法,执行步骤2)~6)。

      2)调用TP模型获得初始分区方案S

      3)计算降温系数Cooling = eln0.005/Loop;循环Loop次执行步骤4~6)。

      4)计算第i次循环(i < Loop)的当前温度T = InitT × Coolingi;通过Metropolis方法调用邻域搜索算子集合Operators,获取当前最好分区方案S'

      5)比较优化目标值fS/)、fS*)的大小,判断是否更新全局最好分区方案S*

      6)记录循环过程中出现的分区方案,构成服务分区集合sPool。

      7)基于服务分区集合构建SPP模型,调用模型求解得分区方案S''

      8)比较优化目标值fS'')、fS*)的大小,最终返回全局最好的分区方案S*

    • 基于FSDP算法框架,改变启发策略/扰动策略、接受准则,可以快速构成ILS-SPP混合算法。设置ILS算法参数迭代循环次数Loop和扰动策略pm。

      1)采用多启动方法,M次启动ILS算法,执行步骤2)~6)。

      2)调用TP模型获得初始分区方案S

      3)通过LocalSearch方法调用Operators获取当前最好分区方案S',并循环Loop次执行步骤4~6)。

      4)调用Perturbation方法对S按策略pm扰动;再次调用LocalSearch方法获取当前最好分区方案S'

      5)比较优化目标值fS')、fS*)的大小,判断是否更新全局最好分区方案S*

      6)记录循环过程中出现的分区方案,构成服务分区集合sPool。

      7)基于服务分区集合构建SPP模型,调用模型求解得分区方案S''

      8)比较优化目标值fS'')、fS*)的大小,最终返回全局最好的分区方案S*

    • 本文针对两个实际区域构建FSDP案例。区位问题基准测试案例研究表明,案例求解难度与案例规模、设施供需比值、供需空间分布等因素相关。一般来说,案例规模(设施数量、需求单元数量)越大,其求解难度越高;设施供应与服务需求比值越低,案例求解难度越高。因此,本文考虑设施数量、需求单元数量,设施供需比值这3个因素构造4个实验案例。

      案例区ZY的地理数据主要来源于河南省某市城区的一部分,包含324个地理单元,服务需求总量为3 873,15个设施单元;案例区GY2的地理数据来源于河南省某县级市,包含1 276个地理单元,服务需求总量819 812,22个服务设施。案例区ZY和GY2的供需空间分布特征、地理单元规模具有一定的代表性。针对每个地理区域构造两个供需比值差异较大的案例,最终获得4个测试案例:ZYA、ZYB、GY2A和GY2B,主要属性如表 1所示。

      表 1  4个测试案例的主要属性

      Table 1.  Attributes of Four Cases

      案例 区域特征 地理单元数 邻接关系 设施数 设施容量 服务需求量 供需比
      ZYA 城区 324 1 618 15 4 470 3 873 1.154
      ZYB 城区 324 1 618 15 3 979 3 873 1.027
      GY2A 县域 1 276 7 820 22 975 947 819 812 1.190
      GY2B 县域 1 276 7 820 22 843 424 819 812 1.029

      两个案例区ZY和GY2的基本地理特征如图 3所示,图 3中的地理单元随着颜色变深服务需求量增大,黑色圆点代表设施的位置。案例ZYA和ZYB的地理单元、服务需求数量、设施位置完全相同,不同之处仅在于设施提供的服务容量有差异。案例GY2A和GY2B亦如此。

      图  3  案例区ZY和GY2示意图

      Figure 3.  Study Areas ZY and GY2

    • 使用Python语言实现本文的FSDP算法框架。实验计算环境为惠普(HP)台式计算机,配置Intel Core i7-6700 CPU和8 GB内存,Windows 10(64位)操作系统,IBM CPLEX12.6优化器。为加快计算速度,算法在PyPy(https://www.pypy.org)环境中执行。

      首先,对4个案例分别采用FSDP模型求解。在算法框架的基础上,对案例数据进行数学建模,调用CPLEX优化器进行计算。设置CPLEX的参数如下:可容忍的目标差距MIPGap值为1×10-10,计算时间限制为7 200 s,选择非确定性的机会优化模式,Parallel设为-1,其他参数缺省。GAP表示CPLEX所发现的可行解与下界的差异百分比。

      然后,调用多启动SA、ILS、SA-SPP、ILS-SPP混合算法完成4个案例实验。设置算法参数如下:多启动次数M为10次,SA算法的初始温度InitT为1,迭代循环次数Loop为100次,扰动策略为随机选择扰动方法。每个算法执行10遍,统计需求单元到设施单元平均总距离、最好总距离、平均GAP(与最优解或已知最好解的差距)、平均运行时间,以及增加SPP模型后解的平均改进程度。所有算法计算结果的统计如表 2所示。

      表 2  5种算法求解服务分区结果统计

      Table 2.  Solution Results of Five Algorithms

      算法 统计指标 ZYA ZYB GY2A GY2B
      CPLEX 总距离/km 1 656.53* 1 874.58* 1 875 355.92* 2 003 951.77
      GAP/% 0 0 0 0.01
      运行时间/s 83.00 112.70 401.82 7 204.54
      SA 平均总距离/km 1 668.27 1 900.16 1 875 788.04 2 007 153.45
      最好总距离/km 1 661.37 1 892.22 1 875 563.99 2 006 397.20
      平均GAP/% 0.71 1.36 0.02 0.17
      平均运行时间/s 53.81 54.03 252.06 224.45
      SA-SPP 平均总距离/km 1 662.98 1 898.53 1 875 396.63 2 005 921.36
      最好总距离/km 1 661.37 1 891.16 1 875 355.92* 2 004 889.09
      平均GAP/% 0.39 1.28 0.00 0.11
      平均运行时间/s 57.58 59.32 259.65 258.65
      SPP改进/% 0.32 0.09 0.02 0.00
      SPP平均运行时间/s 3.77 5.29 7.60 34.20
      ILS 平均总距离/km 1 663.92 1 910.10 1 876 169.80 2 009 310.83
      最好总距离/km 1 660.19 1 904.51 1 875 633.19 2 007 623.64
      平均GAP/% 0.45 1.90 0.04 0.28
      平均运行时间/s 53.13 60.62 140.63 224.80
      ILS-SPP 平均总距离/km 1 657.08 1 905.24 1 875 476.09 2 006 901.47
      最好总距离/km 1 656.53* 1 895.06 1 875 367.74 2 005 088.75
      平均GAP/% 0.03 1.64 0.01 0.16
      平均运行时间/s 58.56 153.64 145.04 267.03
      SPP改进/% 0.41 0.23 0.04 0.12
      SPP平均运行时间/s 5.43 93.02 4.41 42.23
      注:*表示算法获得的最优解

      对比4个案例运行5种算法的计算结果发现:(1)本文算法框架支持模型调用、多种元启发算法、混合算法对FSDP进行求解。(2)所有算法所得设施服务分区方案均是空间连续的。(3)调用数学模型求解结果表现出一定的优势,获得了最优解或者近似最优解(与最优解差异小于0.01%),但不同类型的案例求解时间差异较大。(4)4种混合优化算法运行稳定,执行时间相对较短,案例目标值与最优解或已知最好解的差距处于0.00%~1.90%之间,整体上表现出良好的收敛性;即使没有找到最优划分方案,也获得了较好的可行分区方案,表明算法性能优越。(5)混合算法中增加SPP模型后,运行时间有所增加,但是优化目标值改进了0.00%~0.41%,整体上有所提高,与最优解或已知最好解的差距处于0.00%~1.64%之间,并且在ZYA和GY2A案例中找到了最优解。

      综合来看,FSDP优化算法的求解质量和计算时间与案例区的地理单元数量、设施布局、设施供需比值有着密切的关系。(1)案例区ZY的地理单元数量少,需求单元和设施分布较均衡,优化算法执行速度比案例区GY2快。(2)同一个案例区,供需比小的案例ZYB和GY2B求解难度更大,寻找最优解或近似最优解的时间相对较长。(3)案例GY2B是典型的大规模、小供需比案例,精确算法在2 h(7 200 s)内没有获得最优解,而此时混合算法表现出时间上的优势,在较短的运行时间内发现了可行分区方案。也就是说,研究区的地理单元规模和供需比对FSDP求解方法的选择、设施服务分区方案的获取有着显著的影响。案例ZYA、ZYB和GY2A、GY2B的调用数学模型求解服务分区方案如图 45所示。

      图  4  案例ZYA和ZYB 15个设施服务区划分示意图

      Figure 4.  15 Facility Service Areas of ZYA and ZYB

      图  5  案例GY2A和GY2B 22个设施服务区划分示意图

      Figure 5.  22 Facility Service Areas of GY2A and GY2B

    • 本文在给出FSDP问题定义的基础上构造线性规划数学模型,并设计了一个算法框架。所定义FSDP问题兼顾了设施服务供需平衡、服务区紧凑及空间连续要求,适用于学校划片、基层医疗首诊服务范围划分、避难所服务范围划分等问题,便于公共服务规划与管理。经典的一般指派问题或区位问题不要求服务区空间连续,原因在于空间连续的模型表达较为困难,且增加了计算复杂度。针对空间连续分区需求,传统的解决方法是忽略这一需求,在获得需求指派结果后进一步处理,这一方法有可能损失目标函数值。本文提出的数学模型及算法框架较好地解决了分区空间连续这一需求,能够高质量求解一大类空间连续约束的服务分区问题,也可以将其扩展到空间连续约束的LA问题中。

      本文针对FSDP问题设计的算法框架具有良好的计算性能和可扩展性。首先,算法框架支持多种优化算法的实现;其次,算法优化性能优越,在服务供需比较高时,可以搜索到最优解,或目标值非常接近最优解;最后,本文算法框架兼顾到了设施服务区均衡、连续、紧凑原则的处理,具有进一步扩展的潜力。例如,针对多校划片问题,可以使用本文方法进行单校服务区划分,再进行分区合并,获得满足要求的多校划片方案。针对经典的LA问题增加区位搜索算子,从而求解具有分区连续约束的LA问题。

      本文的案例研究也表明FSDP案例的求解难度与服务供需比关系密切。针对同一区域,保持其他条件不变,仅降低设施服务容量,案例求解难度增加,导致求解计算时间增加或者求解质量下降。另外,在案例区需求规模不变的前提下,设施的位置也会影响服务分区。如果对部分设施进行位置变动,或者扩充设施容量,或者增加新的设施,通常会带来更好的分区结果。后续研究中可以引入设施区位搜索机制,求解服务区空间连续的LA问题,为实际应用中的设施布局规划及分区管理提供决策支持。

参考文献 (25)

目录

    /

    返回文章
    返回