设施服务分区问题的求解算法框架设计.docx资源-CSDN文库

版权申诉

168 浏览量 2022-11-30 09:28:38 上传评论收藏 328KB DOCX 举报

资源详情

资源评论

设施服务分区问题（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 算法框架，基于这个算法框架，多种算法机制可以组合使用。本文

还设计了不同规模和设施容量的案例，通过多种算法的实现和案例测试来评估算法性能。

1. 问题定义

FSDP 是在设施位置和容量已经确定的情况下，遵循设施就近原则，将一个区域内的

地理单元指派到各个设施服务区。设施所在地理单元称为设施单元，需求所在地理单元称

为需求单元。FSDP 要求服务区供需平衡、空间连续、空间可达，以及地理单元完整且唯

一指派。供需平衡要求服务区内各地理单元的服务需求总和不能大于设施服务容量。空间

可达性可以通过服务区内各需求单元到设施单元的总距离来评估，一般优先选择最短距

离。空间连续性是服务分区满足政策和管理要求的必要条件。单元完整性是指分区时不允

许将基本单元分割。唯一性要求每个单元只能指派到一个服务区。

一个地理区域 U 包含 n 个地理单元和 m 个设施，集合 U={1，2… n}。每一个地理单

元 i 具有属性 A

和 B

，其中，A

表示空间单元 i 的服务需求量；B

表示地理单元 i 内设施容

量，B

=0 则表示地理单元 i 内无设施。变量 D

表示地理单元 i 与设施单元 k 之间的距离；

变量 C

代表地理单元 i 与 j 是否邻接，地理单元 i 的邻接单元集合表示为 N

={ j | C

=1}；

变量 K 表示要划分的设施服务区数量。设施服务区集合 S={s

，

… s

}（s

⊂U）表示 K

个设施服务区。分区目标是需求单元到设施单元的总距离函数值最小。

FSDP 就是在一定约束条件下，将集合 U 划分为 K 个空间连续的子集 s

。参考文献

[21-22]，建立一个 MILP 模型将 FSDP 描述为一个带空间连续性约束的指派问题。参考文

献[14, 23]，使用网络流模型来表示设施服务区的空间连续性约束。FSDP 的数学模型为：

min∑i∈U∑k∈SAiDikyikmin∑i∈U⁡∑k∈S⁡AiDikyik

(1)

s.t.∑k∈Syik=1,∀i∈Us.t.∑k∈S⁡yik=1,∀i∈U

(2)

∑i∈UAiyik≤Bk,∀k∈S∑i∈U⁡Aiyik≤Bk,∀k∈S

(3)

fijk≤yik(n−K),∀i∈U,j∈Ni,∀k∈Sfijk≤yik(n−K),∀i∈U,j∈Ni,∀k∈S

(4)

fijk≤yjk(n−K),∀i∈U,j∈Ni,∀k∈Sfijk≤yjk(n−K),∀i∈U,j∈Ni,∀k∈S

(5)

∑j∈Nifijk−∑j∈Nifjik≥yik,∀i∈U∖S,∀k∈S∑j∈Ni⁡fijk−∑j∈Ni⁡fjik≥yik,∀i∈U∖S,∀k∈S

(6)

∑j∈Nifijk−∑j∈Nifjik≥K−n,∀i∈S,∀k∈S∑j∈Ni⁡fijk−∑j∈Ni⁡fjik≥K−n,∀i∈S,∀k∈S

(7)

yik={0,1},∀i∈U,k∈Syik={0,1},∀i∈U,k∈S

(8)

fijk≥0,∀i∈U,j∈Ni,k∈Sfijk≥0,∀i∈U,j∈Ni,k∈S

(9)

函数（1）为优化目标，求解每个分区中需求单元到设施单元的总距离的最小值。约

束条件（2）要求每个地理单元 i 必须且唯一指派到一个设施服务区。约束条件（3）是设

施容量限制，要求保证每个设施服务区的需求量不能超过设施容量。约束条件（4）~

（7）是基于网络流概念构造的，保证设施服务区 k 的空间连续性。条件（4）、（5）保

证属于同一个设施服务区 k 的两个相邻单元 i 和 j 才可能产生流。设施服务区 k 中，如果单

元 i 不是设施单元，约束条件（6）确保该单元产生 1 个单位流量；约束条件（7）保证设

施单元最多汇入（n－K）个单位流量。模型中定义 2 个决策变量，约束条件（8）、（9）

是对决策变量取值的限定，y

表示地理单元 i 是否分配到设施单元 k，取值只能是 0 或者

1；f

ijk

是非负整数，表示设施服务区 k 内从地理单元 i 到单元 j 的流量。

2. FSDP 算法框架

2.1 设计思路

设施服务分区问题 FSDP 算法框架如图 1 所示。这个算法框架面向设施服务分区问

题，支持使用精确算法、元启发算法及混合算法求解，遵循算法实现的有效性、简单性和

灵活性原则，同时具有可重用性和扩展性等特点。在底层问题定义和数据结构模块的基础

上建立基本操作和数学模型，根据顶层应用问题的需要选择初始方案、邻域搜索算子和启

发策略，调用数学模型、元启发算法或混合算法，对实际 FSDP 进行求解。

剩余13页未读，继续阅读

评论收藏

内容反馈

版权申诉

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

评论0

最新资源

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

评论0

最新资源

相关推荐

基于OpenCV图像处理的智能小车户外寻迹算法的设计.docx

各种优化算法求解函数优化问题.docx

新闻流实时话题挖掘框架与算法研究 .docx

交通AI算法平台框架设计.docx

(完整版)MATLAB典型去雾算法代码...docx

关系模式候选键求解算法及其应用.docx

页面置换算法课程设计.docx

轻松看懂机器学习十大常用算法知识分享.docx

离散型遗传算法求解组合优化代码.docx

百度校园招聘笔试试题-深度学习算法研发工程师.docx

对常用的机器学习和深度学习算法进行总结.docx

逻辑回归分类实验——【机器学习与算法分析】.docx

Apriori算法实现实验报告.docx

求职招聘_2014去哪儿网校园招聘笔试算法题汇总.docx

百度 2014校园招聘笔试试题--深度学习算法研发工程师.docx

机器学习--决策树(ID3)算法及案例.docx

课程设计-磁盘调度算法.docx

《程序设计与问题求解》实验指导书.doc.docx

相关实用应用程序（Windows可用）

免费可用的ChatGPT网页版.zip

ChatGPT使用总结：150个ChatGPT提示词模板（完整版）

chromedriver-win64.zip

李飞飞自传 我看见的世界 The World I see

全国计算机二级WPSoffice精选350道选择题题库（含答案）.pdf

哈尔滨工业大学-ChatGPT调研报告-2023.3.6-94页.pdf

农村公交与异构无人机协同配送优化

4个亲测好用的ChatGPT4渠道

学术海报模板+论文科研+研究生

北森能力测评题库.zip

李飞飞自传我看见的世界 The World I see