EN中文

Journal of Geo-information Science >

2024 , Vol. 26 >Issue 11: 2452 - 2464

DOI: https://doi.org/10.12082/dqxxkx.2024.240044

An Intelligent Site Selection Approach for Public Service Facilities Coupled with Improved Graph Attention Network and Deep Reinforcement Learning

  • WANG Zhong , 1, 2 ,
  • CAO Kai , 1, 2, *
Expand
  • 1. School of Geographic Sciences, East China Normal University, Shanghai 200241, China
  • 2. Key Laboratory of Geographic Information Science (Ministry of Education), East China Normal University, Shanghai 200241, China
* CAO Kai, E-mail:

Received date: 2024-01-21

  Revised date: 2024-02-18

  Online published: 2024-11-07

Supported by

National Key Research and Development Program of China(2022YFB3903700)

National Key Research and Development Program of China(2022YFB3903704)

Fold

Abstract

In the context of the rapid development of urbanization, the reasonable selection of locations for public service facilities is critical for delivering efficient services and enhancing the quality of urban residents' lives. However, prevailing approaches for allocation of public service facilities often fall short of meeting the demands on their performance and efficiency in complex and large-scale real-world scenarios. To address these issues, this article proposed a novel Graph-Deep-Reinforcement-Learning Facility Location Allocation Model (GDRL-FLAM), coupling a Facility Location Allocation Graph Attention Network (FLA-GAT) with a Deep Reinforcement Learning (DRL) algorithm. This proposed model tackled the location allocation problem for public service facilities based on graph representation and the REINFORCE algorithm. To assess the performance and efficiency of the proposed model, this study conducted experiments based on randomly generated datasets with 20, 50, and 100 points. The experimental results indicated that: (1) For the tests with 20, 50, and 100 points, the GDRL-FLAM model exhibited a significant improvement ranging from 11.79% to 14.49% compared to the Genetic Algorithm (GA) which is one of the commonly used heuristic algorithms for addressing location allocation problems. For the tests with 150 and 200 points, the improvement ranged from 1.52% to 9.35%. Moreover, with the increase in the size of the training set, the model also demonstrated enhanced generalizability on large-scale datasets; (2) The GDRL-FLAM model showed strong transfer learning ability to obtain the location allocation strategies in simple scenarios and adapt them to more complex scenarios; (3) In the case study of Singapore, the GDRL-FLAM model outperformed GA significantly, achieving obvious improvements ranging from 1.01% to 10.75%; (4) In all these abovementioned tests and experiments, the GDRL-FLAM model showed substantial improvement in efficiency compared to GA. In short, this study demonstrated the potential of the proposed GDRL-FLAM model in addressing the location allocation issues for public service facilities, due to its generalization and transfer learning abilities. The proposed GDRL-FLAM could also be adapted to solve other spatial optimization problems. Finally, the article discussed the limitations of the model and outlined potential directions for future research.

Key words： deep reinforcement learning; graph attention network; public service facilities; site selection optimization; transfer learning; attention mechanism; healthcare facilities; accessibility

Cite this article

WANG Zhong , CAO Kai . An Intelligent Site Selection Approach for Public Service Facilities Coupled with Improved Graph Attention Network and Deep Reinforcement Learning[J]. Journal of Geo-information Science, 2024 , 26(11) : 2452 -2464 . DOI: 10.12082/dqxxkx.2024.240044

1 引言

公共服务设施作为城市社会性服务的基础设施，涵盖了教育、医疗、文体等多个领域，其分布与服务大众的性质使其在城市社会结构和可持续发展中发挥着至关重要的作用[1]。它们的分布不仅影响着居民的日常生活，更关系到整个城市社会结构的合理性和可持续发展的方向。我国“十四五规划”中指出，要进一步优化公共服务设施布局，既要考虑设施的可及性，又要合理控制公共服务设施规模[2]。这体现了对城市发展的全面要求，不仅需要确保服务设施能够覆盖更多居民，还要在可持续的基础上进行规模控制，以实现资源的有效利用和社会服务的高效提供。在这一背景下，合理规划和选择公共服务设施的位置至关重要，通过科学的选址决策，可以更好地满足居民的需求，进而推动城市社会结构的协调发展。
选址问题的复杂性在于其涉及多个空间维度和复杂的相互关系，解决这类问题需要建立高效的选址模型，其中经典的选址模型包括P中值(P-median)模型[3]、P中心(P-center)模型[4]、集合覆盖模型[5]等，这些选址模型通常属于NP-hard问题。对于这类复杂问题，目前主流的求解方法主要包括精确算法、近似算法和启发式算法。精确算法是解决选址问题的经典方法之一，主要代表有分支定界算法[6-7]和动态规划算法[8-9]。这类算法通常能够获得全局最优解，但其局限性在于当问题规模扩大时，求解时间呈线性增长，使得精确算法在处理大规模选址问题时面临计算复杂度的挑战。近似算法的目的是找到一个次优解，为所找到的解的质量提供近似保证[10]，主要包括贪心算法[11]、局部搜索算法和线性规划等。启发式算法利用设定的启发式规则对解空间进行搜索[12-13]。这类算法在可行时间内能够找到一个相对较好的解，常见的有模拟退火算法[14]、禁忌搜索算法[15]、进化算法[16]、蚁群算法[17]等。然而，当问题规模较大时，这类迭代型优化算法需要进行大量的迭代搜索，此外，一旦问题发生变化，这类方法通常需要重新进行搜索求解或者需要重新设计问题求解策略，具有二次运行时间[18]。
随着人工智能领域的兴起，深度强化学习(Deep Reinforcement Learning, DRL)作为其中一个重要的分支，主要用来做序列决策。事实上，选址问题具有明显的时序性和决策过程，需要一个能够在不同时间步骤中作出决策并从中学习的模型。DRL能够使模型根据不同的环境状态和行动获得奖励或惩罚，从而逐步优化决策策略，帮助模型更好地适应城市的动态变化和不确定性。近年来DRL在AlphaGO[19]、Atari[20]等问题上的出色表现展示了其强大的学习能力和优化决策能力。目前基于DRL的组合优化模型主要包括指针网络模型（Pointer Network, Ptr-Net）和图神经网络模型（Graph Neural Network, GNN）。这类方法统称为端到端的方法。具体而言，给定问题实例作为输入，利用训练好的深度神经网络（Depp Neural Network, DNN）直接输出问题的解，其中神经网络的参数一般利用DRL训练得到。相对于传统的迭代型优化算法，端到端方法无需搜索即可直接输出问题解，具有求解速度快的优势[21]；并且，模型一旦训练完成，可以对具有相同分布特性的所有问题实例进行求解，而不需要重新进行训练，具有很强的泛化能力[22-23]，而传统算法一旦遇到一个新的问题实例，则需要从头开始重新进行搜索求解。
Ptr-Net通过逐步生成输出序列，将问题转变为一个动作序列的生成过程。在每个时间步，模型选择一个动作，逐渐构建出最终的结果。目前Ptr-Net在组合优化领域的应用主要集中在路径优化问题上，例如Vinyals等[24]最早提出用Ptr-Net来解决组合优化问题，它通过引入一个序列到序列的Ptr-Net的监督学习框架来解决TSP问题。但是由于其采用的是监督学习的方法，事先需要构建大量的标签数据集，从而限制了其应用到更大规模的组合优化问题。因此Bello等[25]引入一种actor-critic强化学习算法来训练Ptr-Net以无监督的方式解决TSP问题，并表明他们的算法在大规模TSP问题上的性能优于传统算法和Vinyals等监督式的训练方法。相较于传统的序列决策模型，近年来Transformer模型在自然语言处理领域取得了巨大成功。Kool等[21]借鉴Transformer模型，提出了一种注意力模型(Attention Model, AM)来解决多种组合优化问题，并且其结果超越了以往所有的Ptr-Net模型，而且已经接近Gurobi等求解器取得的最优解。然而这类模型在选址优化方面的应用相对较少，因为其在处理图结构和全局信息方面存在一定的局限性，特别是对于选址问题，需要考虑更复杂的空间结构[26-27]。GNN采用更为全局的视角，将组合优化问题抽象成一个图的表示，通过学习节点之间的关系，自动提取并利用城市空间中的特征。例如，Li等[28]利用图卷积神经网络(Graph Convolutional Network, GCN)来解决诸如最小顶点覆盖等基于图的组合优化问题，他们是直接输出所有选择节点的概率，而不是逐步输出节点来构造解。Drodi等[29]使用图注意力网络(Graph Attention Network, GAT)来解决多种图组合优化问题，并且声明他们的模型具有从随机点训练泛化到真实城市中的能力。城市空间通常被视为一个复杂的图结构，其中节点代表地理位置，边代表节点之间的连接关系[30-31]。这样的空间关系往往无法被传统的规划方法和线性模型充分捕捉。而GNN通过层层传递和聚合，能够更好地捕捉节点之间的复杂依赖关系。然而，当前对于GNN在组合优化问题上的研究主要问题之一在于缺乏对序列决策的充分考虑，组合优化问题通常涉及到在离散领域中做出一系列决策，尤其是对于选址问题来说，而传统的GNN方法往往未能有效地处理这种序列性质[32]。这种不足限制了GNN在组合优化问题中的应用范围。此外，当前研究中较多采用监督学习的方式来训练GNN，这在一定程度上限制了模型的泛化能力和适应性。监督学习通常需要大量标记数据，而在组合优化问题中，获取大规模标记数据通常会导致时间成本较高[33]。
因此，为了更有效地解决公共服务设施选址问题并充分探索DRL在这一领域的应用潜力，本研究基于改进的GAT提出了一种创新的端到端DRL选址模型——图强化选址模型(Graph-Deep-Reinforcement-Learning Facility Location Allocation Model, GDRL-FLAM)。该模型综合运用了GAT的全局建模和Transformer的序列决策能力。通过DRL训练策略，无需大规模标记数据，为公共服务设施选址问题提供一种先进而实用的解决方案。通过多尺度的测试和案例研究，GDRL-FLAM在公共服务设施选址问题上相比较于遗传算法(Genetic Algorithm, GA)取得了显著效果。GDRL-FLAM能够有效处理城市规模的图结构，同时考虑到选址过程的序列性质，为相关部门制定决策和公共服务设施布局优化提供依据。

2 研究方法

2.1 技术路线

本研究提出了一种耦合设施选址图注意力网络(Facility Location Allocation Graph Attention Network, FLA-GAT)与DRL算法的图强化选址模型(GDRL-FLAM)，旨在更有效地解决公共服务设施的选址问题，框架见图1，主要包括FLA-GAT模型以及使用DRL算法进行训练和测试的2个部分。
图1 GDRL-FLAM框架

Fig. 1 The framework of GDRL-FLAM

2.2 FLA-GAT模型

对于设施选址问题，在一个无向图G=(V, E, W)上定义问题实例，其中每个节点i属于V={1,…, n}，表示一个潜在的设施位置，其特征由坐标ni表示。边aij∈E表示设施位置之间的连接，其中i, j∈W，而eij∈E表示与aij相关的距离信息。
引入一个解p=(p1, …, pm)来表示所有设施位置的序列，其中pt∈{1, …, n}表示选择的设施，且 ∀ t ≠ t ' ,   p t ≠ p t '。目标是找到一个给定问题实例s的解p​，使得每个设施只选择一次，从而最小化到最近设施的总距离[34]。设施选址问题的目标函数定义如下：
L ( p | s ) = ∑ i = 1 n m i n j ∈ p | | n i - n j | | 2
式中：i, j∈V，在设施选址问题的目标函数中，使用L2范数计算了点之间的距离的平方和； | | n i - n j | | 2表示第i个点和第j个点之间的欧几里得距离。
FLA-GAT包括编码器和解码器两部分，编码器通过嵌入生成对所有输入节点的表示，任务是将问题信息转化为解码器理解的嵌入表示。解码器按照不同的解码策略逐个节点生成被选择的点。通过设计掩码防止重复选择已选取的点，可以有效地搜索潜在解空间并缩小动作空间。FLA-GAT的设计目标是通过最小化到最近设施的总距离来解决设施选址问题，距离计算基于欧氏距离。通过调整输入表示、掩码和解码器上下文向量，FLA-GAT可以适用于各种选址场景。FLA-GAT的流程图见图2。
图2 FLA-GAT模型示意图

Fig. 2 The schematic diagram of FLA-GAT model

在编码器中，输入是一个图，其中每个节点i由其二维坐标ni表示，边eij表示位置i和j之间的欧氏距离。X表示节点特征， X ∈ R N × D，N表示节点数，D表示原始节点特征维度，E表示边特征， E ∈ R N 2 × 1，通过全连接层对节点特征和边特征进行映射，引入一个可学习的权重矩阵W，进行线性变换，并进行批归一化[35]。
x i ( 0 ) = B N X ∙ W X + b X
e i j = B N ( E ∙ W E + b E )
式中：WX表示节点特征的权重矩阵， W X ∈ R D × h x；hx表示节点嵌入维度；WE是边特征的权重矩阵， W E ∈ R 1 × h e；he表示边嵌入维度；bX、bE为偏置；BN代表批归一化。这一步骤旨在将原始特征映射到更高维的表示空间，以便后续的GAT层能够更好地捕捉节点和边之间的复杂关系。
全连接层只是对输入进行线性映射，在图数据中，节点之间的关系通常是复杂的，因此引入注意力机制和多层结构，从而更好地捕捉这些复杂关系，提高模型的表达能力。将新的节点表示和新的边表示输入到L层GAT中，第一层的输入包括节点特征xi(0)和边特征eij，每一层的输出xi(l)表示第l层的节点嵌入[36]。在每个GAT层通过动态计算注意力系数来聚焦邻居节点的重要性[37]。具体来说，每一层GAT都会更新节点表示，通过注意力加权邻居节点的信息，对于节点i和j之间的边，注意力系数通过以下公式计算：
α i j = s o f t m a x ( L e a k y R e L U ( a T W x i | | W x j | | W e i j )
在注意力机制的输入中，xi||xj||eij表示将节点i和j的特征以及边的特征按列拼接在一起。这样得到的特征向量将同时包含节点信息和边信息，然后通过学习到的权重矩阵W对拼接后的特征向量进行线性映射，最后使用注意力参数向量a对映射后的特征向量进行注意力权重的计算[38]。其中，a是学习得到的注意力参数向量，W是学习得到的权重矩阵，eij是节点i和j之间的边特征。通过学习得到的参数a和W对输入特征进行线性映射，并通过LeakyReLU激活函数引入非线性[39]。注意力权重αij的计算使用了softmax函数，确保所有权重的和为1，得到每个节点与邻居节点的注意力权重。在计算出来注意力系数后，使用这些系数对邻居节点的特征进行加权求和，然后通过将加权求和得到的节点表示与原始节点表示相加，称为残差连接[40]，实现信息的整合和更新：
x i ( l ) = x i ( l ) + x i ( l - 1 )
式(5)中左边的 x i ( l )是更新后的最终节点表示，右边的 x i ( l )是使用注意力权重加权邻居节点的特征得到的， x i ( l - 1 )是原始的未加权注意力权重的节点表示。在L层GAT中，上述过程会循环进行，每一层都会以前一层的输出作为输入得到更新后的节点表示，然后输入到下一层进行进一步的信息传递，经过L层GAT后，得到最终的节点嵌入 x i ( L )。多层结构的引入有助于逐层提取和整合图中的特征，每一层都可以看作对前一层特征的进一步抽象和表示。最终，通过这些步骤，模型完成了对节点特征的更新，输出最终的节点嵌入，然后将所有节点嵌入取平均值得到最终的图嵌入。整个过程实现了对节点特征的更新，充分利用注意力机制关注节点邻居中更重要信息，同时通过残差连接保留原始节点表示。这样的设计提高了模型对图数据中关系的灵活建模能力，增强了对节点特征的表达。
解码器使用编码器输出的节点嵌入和图嵌入作为输入，通过多头注意力机制计算上下文向量，上下文向量是一种综合了编码器输出、先前选择的节点信息以及其他问题相关上下文的向量表示，通过融合这些信息，旨在提供更全面的语境信息，以改善模型对当前任务的表现[41]。在计算上下文向量之后，解码器使用上下文向量和编码器的输出来计算查询向量q，键向量k和值向量v用于计算注意力系数，将计算出来的注意力系数经过softmax函数，获得每个节点的概率分布。
在获得概率分布后，使用ε-greedy和Sample两种解码策略。ε-greedy策略根据随机生成的值决定是否贪婪地选择或进行随机采样，具体来说，当生成的值小于等于预设的ε阈值时，执行随机采样，否则采用贪婪策略。Sample策略直接根据概率分布进行随机采样，选择下一个节点。
在训练阶段，本文采用ε-greedy策略，在初始阶段充分进行探索，使模型更加随机地选择动作，从而有助于充分探索环境，发现潜在的有效策略。随着训练的进行逐步减小ε的值：
ε n e w = ε i n i t i a l ∙ β e p o c h
其中，β为衰减系数，这样会使模型逐渐偏向贪婪策略，更多地利用已学到的知识，稳定训练、提高收敛速度。在测试阶段，分别使用ε-greedy策略和Sample策略进行评估，增加了模型对多样性的适应能力，提高了模型的鲁棒性和泛化性能。

2.3 DRL算法

本研究采用REINFORCE算法来进行选址优化[42]。在这个算法框架下，该模型致力于解决公共服务设施选址问题，该问题的优化目标是最小化其他点到最近选择点的距离之和。使用GDRL-FLAM模型将选址问题建模为图输入，并通过策略优化来获得最优解。将公共服务设施的选址问题建模为马尔可夫决策过程，决策过程主要包括状态(state)、动作(action)和奖励(reward) 3部分，具体描述如下：
s ( t ) = s 1 , s 2 ,   ⋯ ,   s n  
A ( t ) = a 1 ,   a 2 ,   ⋯ ,   a n | a t ∈ 0 ,   n - 1
R ( t ) = L ( p | s )
图3描述了智能体-环境交互示意图。在这个过程中，状态代表当前已选设施位置和需求点的位置，状态空间s(t)描述了到目前为止已选设施的空间布局。动作对应于在何处放置下一个设施的决策，每个动作涉及选择新设施的具体位置，动作空间A(t)包含了可以将新设施添加到现有配置的所有潜在位置，动作空间初始为长度为N的集合，取值范围为0到N-1之间的自然数。在选址问题中，奖励R(t)反映了优化的目标。具体而言，目标是最小化需求点到最近设施点的距离之和，L(p|s)由式(1)计算得到。
图3 智能体-环境交互示意图

Fig.3 The agent - environment interaction diagram

REINFORCE算法的目标是调整策略参数，以最小化损失。在每个时间步，智能体根据当前策略选择一个动作，影响状态的转移。每个回合结束后，通过奖励函数计算整个回合的距离成本，该奖励反映了优化目标。最终，通过最小化损失来更新策略参数。
s t + 1 = f ( s t ,   a t )
a t ~ π ( ∙ | s t )
∇ θ J ( θ ) = E π θ L ( p | s ) - b ( s ) ∇ θ l o g π θ ( a | s )
式(10)描述了状态如何根据选择的动作at从st转移到st+1。式(11)表示动作at是从随机策略π中基于当前状态st采样得到的。式(12)表示算法的损失函数。与任何基于蒙特卡罗的方法一样，REINFORCE算法的梯度会受到高方差的影响，因此为了解决REINFORCE算法中的高方差问题，采用Rollout基线，在计算梯度时从获得的回报中减去基线[21]。Rollout基线是一个独立的神经网络，用于估计未来奖励的期望值。πθ(a|s)是在给定问题实例S的情况下，根据策略参数θ生成解决方案的概率分布。
在这种方法中，使用Rollout作为基线b(s)，通过比较采样解与Rollout的性能差异，利用梯度下降调整模型参数。当采样解表现更佳时，将增加这些动作的选择概率，使模型更趋向于采样解；反之，则减少对不佳解的偏好。同时在每一个epoch结束后比较训练策略和基线策略，仅当改进在5 120个验证实例上通过配对t检验α=5%显著时，才替换基线策略的参数θ。基线策略更新后，采样新的评估实例以防止过拟合。
为了使得REINFORCE算法在训练中表现更为出色，本研究经过多次调整和优化，采用了以下一系列技巧：
奖励归一化：通过将奖励归一化到一定范围，确保了梯度更新的合理性，防止奖励值的极端波动对训练造成负面影响。
R n o r m a l i z e d = R - R m e a n R s t d
学习率递减：初始阶段使用相对较大的学习率以便快速收敛，随着训练的进行，逐渐减小学习率以防止学习过程中的震荡和过拟合。
l n e w = l o l d ∙   ( α ) e p o c h

3 模型验证

为了展现GDRL-FLAM模型在公共服务设施选址问题上的优越性，以及DRL在该领域的潜在价值，本研究开展了一系列实验。这些实验旨在为未来公共服务设施规划提供更为智能、灵活的选址决策支持。具体而言，模型在规模分别为20、50和100个节点上进行训练，分别称为GDRL-FLAM20、GDRL-FLAM50和GDRL-FLAM100。这一过程中，生成了随机的训练数据、验证数据和测试数据，这些数据均取自0到1之间的随机数。基于改进的基线REINFORCE算法，分别为20、50和100个节点生成了12 800、51 200、76 800个训练实例，保证了训练集的充分性和多样性。对于验证数据，采用相同的数据分布，生成了5 120个实例，以确保对模型性能的全面评估。在测试阶段，分别进行了同规模下的泛化测试实验、大规模下的泛化测试实验以及迁移学习能力测试实验。该模型采用了Pytorch构建，整个实验的代码基于Python3.9实现，使用Nvidia GeForce RTX 4090 GPU完成训练，训练过程的相关超参数设置如表1所示。
表1 参数设置

Tab. 1 Parameter setting

参数 值 参数 值
Epoch 200 学习率衰减系数 α 0.98
编码层数L 4 ε 0.90
学习率 0.000 1 ε 衰减系数 β 0.99
节点嵌入维度hx 128 边嵌入维度he 64

3.1 同规模下的泛化测试实验

采用相同的数据分布模式分别生成5 000个 0到1之间包含20、50和100个节点的实例来进行测试，分别从中选择3、5和8个设施点，称为FLP20、FLP50、FLP100，通过计算这5 000个实例的平均距离来评估模型性能。在使用ε-greedy进行测试时，选择一个较小的固定ε值(通过多次测试，确定测试阶段的ε=0.18)，仍然保留一定的随机性，防止模型过于确定性，从而更好地适应环境变化和未知情况。GA通过模拟生物进化的过程，通过初始化一组候选解，使用交叉和变异来产生新的解，利用适应度函数对解进行评估和选择，并迭代进行优化，最终得到一个适用于公共服务设施选址的最优解。GA凭借其较强的搜索能力，在解决选址问题上取得了较好的研究成果[43-44]。通过计算GDRL-FLAM模型相比较于GA在目标上的改善，即距离改善(Distance Improvement)，从而能更好地评估模型的性能优势：
D I = 1 N ∑ i = 1 N L G A - L L G A
式中：L代表GDRL-FLAM模型得到的结果；LGA代表GA得到的结果；N代表测试的5 000个实例，结果如表2所示。
表2 不同节点数量下的GDRL-FLAM性能评估

Tab. 2 Performance evaluation of the GDRL-FLAM with different numbers of nodes

方法 FLP20 FLP50 FLP100
目标值 DI/% 时间 目标值 DI/% 时间 目标值 DI/% 时间
GA 4.411 0.00 3 h 8.700 0.00 5 h 14.081 0.00 12 h
GDRL-FLAM (ε-greedy) 3.773 14.33 11 min 7.593 12.56 27 min 12.400 11.79 58 min
GDRL-FLAM (Sample) 3.766 14.49 24 min 7.566 12.87 53 min 12.373 11.99 2 h
通过表2中的实验结果可明显看出，模型在不同规模的测试实例上相较于GA表现更优。具体而言，在20个点的测试实例上，该模型相比GA分别提升了14.33%和14.49%；在50个点的测试实例上，提升了12.56%和12.87%；在100个点的测试实例上，提升了11.79%和11.99%。这些结果证明了模型在解决选址问题上的有效性和性能优越性。关于求解时间的对比，模型在所有规模的测试实例上都表现出远远短于GA的求解时间。能够通过修改输入来快速得到泛化的结果，而不需要像GA一样从零开始迭代，具有更为高效的运行时间。在实际问题中，快速获得泛化结果可以为决策提供更迅速准确的支持，尤其是在需要频繁更新和调整的场景下，这一优势显得尤为重要。

3.2 大规模下的泛化测试实验

为了进一步测试模型的泛化性能，本研究进行了更大规模的随机点的测试实验。通过生成 3 000个包含150个节点的实例与2 000个包含200个节点的实例来测试模型在大规模数据集上的泛化效果，分别从中选择12个设施点和30个设施点，结果如表3、表4所示。
表3 FLP150泛化性能测试结果

Tab. 3 Generalization performance test results for FLP150

方法 GDRL-FLAM50 GDRL-FLAM100
目标值 DI/% 时间/h 目标值 DI/% 时间/h
GA 17.787 0.00 11 17.787 0.00 11
GDRL-FLAM (ε-greedy) 17.406 1.97 2 16.273 8.34 2
GDRL-FLAM (Sample) 16.922 4.69 5 16.094 9.35 5
表4 FLP200泛化性能测试结果

Tab. 4 Generalization performance test results for FLP200

方法 GDRL-FLAM50 GDRL-FLAM100
目标值 DI/% 时间/h 目标值 DI/% 时间/h
GA 15.282 0.00 10 15.282 0.00 10
GDRL-FLAM (ε-greedy) 15.026 1.52 1 14.613 4.23 1
GDRL-FLAM (Sample) 14.792 3.06 4 13.835 9.33 4
表3中的数据显示，在测试包含150个点的实例时，GDRL-FLAM50模型的测试结果相对于GA提升了1.97%和4.69%。同时，GDRL-FLAM100模型的测试结果相对于GA提升了8.34%和9.35%。在更大规模的包含200个点的实例中（表4），GDRL-FLAM50模型的测试结果相对于GA提升了1.52%和3.06%，GDRL-FLAM100模型的测试结果相对于GA提升了4.23%和9.33%。这些结果表明GDRL-FLAM模型在处理大规模实例时表现出良好的泛化能力。特别地，随着训练集规模的增大，模型在大规模实例上的泛化效果逐渐增强。因为更大的训练集提供了更丰富的信息，使得模型能够更好地学习问题的复杂性和特征，从而在未见过的大规模实例上表现更出色。此外，在所有的泛化实验中，GDRL-FLAM都在求解效率上相较于GA表现出了极大的提升。

3.3 迁移学习能力实验

本文研究了不同规模数据集之间的可迁移性，在20个点的数据集上获得一个预训练模型，并在50个点的数据集上对其进行微调，本研究将预训练的模型与从头开始训练的模型进行比较。根据生成的包含50个节点的5 000个测试数据，分别测试与GA的差距，结果如表5所示。
表5 迁移学习测试结果

Tab. 5 The test results of transfer learning

方法 预训练 从头开始
目标值 DI/% 时间 目标值 DI/% 时间
GA 8.700 0.00 5 h 8.700 0.00 5 h
GDRL-FLAM (ε-greedy) 7.588 12.63 26 min 7.593 12.56 27 min
GDRL-FLAM (Sample) 7.561 12.94 53 min 7.566 12.87 53 min
从表5可看到，预训练的结果相比较于GA分别提升了12.63%和12.94%，取得了不弱于模型直接在50个点上训练的效果，这说明在较小规模数据上学到的知识对解决较大规模问题仍然具有通用性和稳健性，并且通过在小规模数据上提前获取有用的特征和知识，模型在迁移到大规模问题时无需从头开始学习，从而在训练过程中节省了时间和计算资源，极大地提升了求解效率，这对实际的公共服务设施选址优化至关重要。

4 案例研究

4.1 背景介绍

为了更好地验证GDRL-FLAM模型的优越性以及为未来提供精准的医疗服务选址决策支持，本研究选择在实际案例中测试该模型。新加坡的医疗保健系统以其高效和优质的服务而著称。医疗服务在新加坡一直是政府关注的重点领域，以确保居民获得高效、优质的医疗服务。社区健康援助计划(Community Health Assist Scheme, CHAS)在新加坡的医疗服务中扮演着至关重要的角色。作为初级医疗保健的支持体系，CHAS致力于提供经济实惠的医疗服务，覆盖了广泛的人群。CHAS的诊所选址战略直接影响到居民的医疗可及性和效率，而选址决策的合理性对整个社会的健康和福祉都具有深远的影响。CHAS的成功在于提供经济实惠的医疗服务，覆盖广泛人群，并在新加坡的医疗服务中发挥着至关重要的作用。然而，对于CHAS诊所的空间布局和优化，以确保其在社区中的普及和高效分布，目前的研究尚显不足[45]。宏茂桥(Ang Mo Kio)位于新加坡中心区域，不仅有多样化的住宅网络，还包括众多社区设施。因此，本研究选择新加坡宏茂桥区域作为研究区，房屋发展局(Housing and Development Board，HDB)为案例研究对象，HDB是新加坡负责提供住房的主要机构，其庞大的住宅网络和社区构成了医疗服务设施选址的重要背景。宏茂桥区域共有380个HDB点，研究从中选择50个CHAS诊所，使得HDB到最近的CHAS诊所的距离之和最小，以确保医疗服务设施在整个区域的普及和均衡分布。案例研究旨在基于新加坡医疗保健数据测试GDRL-FLAM模型的泛化性能，证明其在应用中的可行性与高效性，为公共卫生决策者提供实用的工具，以优化医疗服务设施的选址，提高医疗资源的利用效率，同时促进社区的整体健康，实现更全面、高效的医疗资源利用。这对于新加坡及其他城市而言，都具有积极的社会和经济效应。

4.2 实验结果与分析

案例研究中所使用的经纬度数据、边界数据和道路数据均来源于新加坡市建局(Urban Redevelopment Authority, URA)。在考虑到新加坡点的经纬度特性时，本研究在模型训练中选择了使用0到1的随机点数据进行训练。为了使模型更好地适应实际的新加坡地理数据，本研究采取了经纬度数据的归一化处理。通过对新加坡的实际经纬度数据进行归一化，本研究确保了模型在训练和测试阶段都能够处理各种规模和范围的地理信息。实验结果见表6。
X n o r m a l i z e d = X - m i n ( X ) m a x ( X ) - m i n ( X )
表6 新加坡案例实验结果

Tab. 6 The results of case study in Singapore

方法 GDRL-FLAM50 GDRL-FLAM100
目标值 DI/% 目标值 DI/%
GA 16.715 0.00 16.715 0.00
GDRL-FLAM (ε-greedy) 16.546 1.01 15.590 6.73
GDRL-FLAM (Sample) 15.900 4.88 15.031 10.75
从表6中可以观察到，当使用GDRL-FLAM100模型进行测试时，在宏茂桥上，相比GA，使用 ε-greedy策略和Sample策略分别提升了6.73%和10.75%。这说明该模型在100个点的实例上训练后，能够泛化到更大规模的测试集上，并且在不同的测试策略下均表现出较好的性能。在使用GDRL-FLAM50模型进行测试时，ε-greedy策略和Sample策略相比GA提升了1.01%和4.88%。这是因为训练数据规模较小，模型未能充分学习到足够泛化的特征，因此在更大规模的测试集上表现不佳。从空间分布上来看(以GDRL-FLAM100并采用ε-greedy策略为例（图4），可以观察到在宏茂桥的西部地区，由于小区分布相对较为稀疏，GA的结果在这一区域呈现出过多的诊所分布，导致医疗资源的浪费现象凸显。相比之下，GDRL-FLAM模型表现出更为均衡的结果，能够有效避免在稀疏小区过度分配医疗资源的问题。此外，在宏茂桥的中部和东部地区，GA的结果主要集中在小区密度较高的区域，却忽略了边缘地区的小区。这种情况可能导致目标值较高，同时无法满足边缘地区居民的医疗需求。相反，GDRL-FLAM模型不仅充分关注到了小区密集的核心区域，而且在设计选址方案时，还考虑到了一些位于边缘地区的小区，为这些区域适当分配了诊所，实现了更为全面的医疗资源分配。值得强调的是，GDRL-FLAM的运行时间要比GA短得多，ε-greedy策略的运行时间又要比Sample策略的时间更短，但是效果没有Sample策略好。在实际应用中，决策者可以根据具体情况灵活选择解码策略，权衡运行时间与选址效果。本案例研究再次证明了本研究中提出的GDRL-FLAM模型的有效性，并展示了其应用于不同实际公共服务设置布局优化案例中的潜力。
图4 GDRL-FLAM100 ε-greedy优化结果

Fig. 4 The result of GDR-FLAM100 ε-greedy

5 结论与讨论

在当今城市社会性服务业的发展中，公共服务设施作为支持教育、医疗、文体等社会性基础设施的重要组成部分，对于居民的日常生活和城市社会结构的合理性起着关键作用。然而，现有常用的公共服务设施选址方法往往未能满足复杂及大规模的现实场景中对于其性能及效率上需求。鉴于此，本研究创新地提出了GDRL-FLAM模型，旨在通过耦合改进设施选址图注意力网络FLA-GAT与DRL的方式，更有效地解决公共服务设施选址问题。这一创新性的模型结合了GAT和DRL的优势，以适应不同规模和地理条件的城市环境，并且同时具备GAT的全局建模和Transformer的序列决策能力，提供更为智能、灵活的选址决策支持。为了验证该框架的有效性，本研究进行了在不同规模(20、50、100)的随机点上的训练。首先，在规模为20、50和100个点的测试实例中，相较于GA，GDRL-FLAM模型在距离优化方面实现了显著改善，距离改善幅度分别达到了11.79%到14.49%。在更大规模的150和200个点的测试实例上，模型仍然呈现1.52%到9.35%的距离改善，突显了GDRL-FLAM在不同规模数据集上的鲁棒性和出色表现。这表明随着训练集规模的增大，模型在处理大规模数据集时能够更好地保持优越的泛化性能。其次，本研究观察到GDRL-FLAM模型不仅能够在简单场景中准确掌握选址策略，而且成功将这些策略迁移到更为复杂的场景中。这证实了模型在不同场景和复杂度下的灵活性和适应性，为其在实际应用中提供了更广泛的适用性。最后，在实际案例研究中，GDRL-FLAM模型在距离改善方面相对于GA实现了1.01%到10.75%的显著提升。这一结果强化了该模型在实际应用中的实际效益，具有从随机实例训练到实际问题测试的泛化性能，显示了GDRL-FLAM模型在特定城市背景下的优越性。此外，在所有的测试及实验中，GDRL-FLAM模型在效率方面相较于GA都展示出了成倍的提升。总体而言，本研究揭示了GDRL-FLAM模型在公共服务设施选址问题上的潜在价值，为公共服务设施选址研究提供了理论指导和模型参考。
本研究旨在提出一种用于解决公共服务设施选址优化问题的通用DRL框架，为公共服务设施选址提供了一种有效及高效的辅助决策工具。通过引入GAT和DRL，本研究提出的端到端框架不仅令选址问题的求解更为准确和高效，而且为决策者提供了更有力的支持。通过融合先进的技术，该模型能够更全面、准确地考虑各种地理信息和实际需求。GAT能够有效地捕捉地理空间中的关联关系，使得模型能够更好地理解不同地点之间的相互影响。同时，DRL的引入使得模型能够根据实际需求和环境动态调整决策策略，从而更好地适应复杂多变的场景，提高选址问题解决的精度和效率。与传统算法相比，该方法为决策者提供了更有力的支持，使其能够基于更全面的信息做出决策。这有助于提高决策的科学性和可行性，使决策者能够更好地应对不同场景下的选址挑战。模型在不同规模和复杂度的场景中均表现出卓越的性能，该模型不仅在大规模问题上具备处理能力，而且能够在多样化、复杂的实际场景中发挥出色的性能。这一算法的提出填补了现有方法的不足之处，为未来设施选址问题的研究和应用提供了新的思路和方法。此外，我们所提出的GDRL-FLAM的潜力不仅限于解决公共服务设施选址问题，还可推广到更为复杂的选址优化问题或者其他空间优化问题如路径优化、土地利用优化等。
尽管本研究在公共服务设施选址问题上取得了显著的成果，但同时也存在一些局限性。首先，该模型仅考虑了单一目标，并且目标函数相对简单，未能涵盖多目标和多约束情境。未来的研究将致力于拓展模型复杂性，引入更多真实场景中常见的多目标和多约束条件，以更贴近实际的选址决策需求。其次，本研究中使用的训练数据仅基于随机生成的位置点集，尚未考虑其他类型的地理空间要素。下一步的研究将致力于基于真实的、多源的地理空间数据进行训练，以提高模型在实际场景中的泛化能力和适应性。

References

Publishing order | Descend order by publishing year | Descend order by cited within
[1]
高军波, 周春山. 西方国家城市公共服务设施供给理论及研究进展[J]. 世界地理研究, 2009, 18(4):81-90.

[Gao J B, Zhou C S. The progress of the theory and research on the supply of urban public service facilities in western countries[J]. World Regional Studies, 2009, 18(4):81-90.] DOI:10.3969/j.issn.1004-9479.2009.04.011

[2]
国家发展改革委. 关于印发《“十四五”公共服务规划》的通知[EB/OL].(2022-01-10)[2024-01-21]. https://www.gov.cn/zhengce/zhengceku/2022-01/10/content_5667482.html.

[National Development and Reform Commission. Notice on Issuing the "14th Five-Year Plan" Public Service Plan[EB/OL].(2022-01-10)[2024-01-21]. https://www.gov.cn/zhengce/zhengceku/2022-01/10/content_5667482.html.]

[3]
Hakimi S L. Optimum locations of switching centers and the absolute centers and medians of a graph[J]. Operations Research, 1964, 12(3):450-459. DOI:10.1287/opre.12.3.450

[4]
Owen S H, Daskin M S. Strategic facility location: A review[J]. European Journal of Operational Research, 1998,111(3):423-447. DOI:10.1016/S0377-2217(98)00186-6

[5]
Roth R. Computer solutions to minimum-cover problems[J]. Operations Research, 1969, 17(3):455-465. DOI:10.1287/opre.17.3.455

[6]
Lawler E L, Wood D E. Branch-and-bound methods: A survey[J]. Operations Research, 1966, 14(4):699-719. DOI:10.1287/opre.14.4.699

[7]
Holmberg K. Exact solution methods for uncapacitated location problems with convex transportation costs[J]. European Journal of Operational Research, 1999,114(1):127-140. DOI:10.1016/S0377-2217(98)00039-3

[8]
Sniedovich M. Dynamic Programming: Foundations and Principles(Second Edition)[M]. CRC Press, Boca Raton, 2010.

[9]
Hribar M, Daskin M S. A dynamic programming heuristic for the P-median problem[J]. European Journal of Operational Research, 1997,101(3):499-508. DOI:10.1016/S0377-2217(96)00218-4

[10]
Shmoys D B, Tardos É, Aardal K. Approximation algorithms for facility location problems (extended abstract)[C]// Proceedings of the twenty-ninth annual ACM symposium on Theory of computing. ACM, 1997:265-274. DOI:10.1145/258533.258600

[11]
Jain K, Mahdian M, Saberi A. A new greedy approach for facility location problems[C]// Proceedings of the thiry-fourth annual ACM symposium on Theory of computing. ACM, 2002:731-740. DOI:10.1145/509907.510012

[12]
关亚宾, 马瑞, 孔云峰. 城市社区便民服务中心选址模型研究[J]. 地球信息科学学报, 2023, 25:2164-2177.

DOI

[Ma R, Kong Y F. Research on site selection model of urban community convenience service centers[J]. Journal of Geo-information Science, 2023, 25:2164-2177.] DOI:10.12082/dqxxkx.2023.230349

[13]
翟石艳, 孔云峰, 宋根鑫, 等. 面向15 min生活圈的城市服务设施规划模型与实验[J]. 地理学报, 2023, 78(6):1484-1497.

DOI

[Kong Y F, Song G X, et al. A new facility location problem for urban public facility planning toward 15-minute life circle: Model and experiment[J]. Acta Geographica Sinica, 2023, 78(6):1484-1497.] DOI:10.11821/dlxb202306010

[14]
Kirkpatrick S. Optimization by simulated annealing: Quantitative studies[J]. Journal of Statistical Physics, 1984, 34(5):975-986. DOI:10.1007/BF01009452

[15]
Arostegui M A, Kadipasaoglu S N, Khumawala B M. An empirical comparison of Tabu Search, Simulated Annealing, and Genetic Algorithms for facilities location problems[J]. International Journal of Production Economics, 2006, 103(2):742-754. DOI:10.1016/j.ijpe.2005.08.010

[16]
席裕庚, 柴天佑, 恽为民. 遗传算法综述[J]. 控制理论与应用, 1996, 13(6):697-708.

[Xi Y G, Chai T Y, Yun W M. Overview of genetic algorithms[J]. Control Theory & Applications, 1996, 13(6):697-708.]

[17]
黎夏. 协同空间模拟与优化及其在快速城市化地区的应用[J]. 地球信息科学学报, 2013, 15(3):321-327.

DOI

[Li X. Collaborative spatio-simulation and optimization and its application in fast growing regions[J]. Journal of Geo-Information Science, 2013, 15(3):321-327.] DOI:10.3724/SP.J.1047.2013.00321

[18]
李凯文, 张涛, 王锐, 等. 基于深度强化学习的组合优化研究进展[J]. 自动化学报, 2021, 47(11):2521-2537.

[Li K W, Zhang T, Wang R, et al. Research reviews of combinatorial optimization methods based on deep reinforcement learning[J]. Acta Automatica Sinica, 2021, 47(11):2521-2537.] DOI:10.16383/j.aas.c200551

[19]
Silver D, Schrittwieser J, Simonyan K, et al. Mastering the game of Go without human knowledge[J]. Nature, 2017, 550(7676):354-359. DOI:10.1038/nature24270

[20]
Mnih V, Kavukcuoglu K, Silver D, et al. Human-level control through deep reinforcement learning[J]. Nature, 2015, 518(7540):529-533. DOI:10.1038/nature14236

[21]
Kool W, van Hoof H, Welling M. Attention, learn to solve routing problems![EB/OL]. 2018: arXiv: 1803.08475. https://arxiv.org/abs/1803.08475

[22]
Neyshabur B, Bhojanapalli S, McAllester D, et al. Exploring generalization in deep learning[C]// Proceedings of the 31st International Conference on Neural Information Processing Systems. ACM, 2017:5949-5958. DOI:10.5555/3295222.3295344

[23]
Keskar N S, Mudigere D, Nocedal J, et al. On large-batch training for deep learning: Generalization gap and sharp minima[EB/OL]. 2016: arXiv: 1609.04836. https://arxiv.org/abs/1609.04836.

[24]
Vinyals O, Fortunato M, Jaitly N. Pointer networks[J]. Computer Science, 2015, 28. DOI:10.48550/arXiv.1506.03134

[25]
Bello I, Pham H, Le Q V, et al. Neural combinatorial optimization with reinforcement learning[EB/OL]. 2016: arXiv: 1611.09940. https://arxiv.org/abs/1611.09940.

[26]
Nazari M, Oroojlooy A, Takáč M, et al. Reinforcement learning for solving the vehicle routing problem[C]// Proceedings of the 32nd International Conference on Neural Information Processing Systems. ACM, 2018:9861-9871. DOI:10.5555/3327546.3327651

[27]
Deudon M, Cournut P, Lacoste A, et al. Learning heuristics for the tsp by policy gradient[C]// Proceeding of the Integration of Constraint Programming, Artificial Intelligence, and Operations Research:15th International Conference, CPAIOR 2018, Delft, The Netherlands, June 26-29, 2018, Proceedings 15. Springer, 2018:170-181. DOI:10.1007/978-3-319-93031-2_12

[28]
Li Z W, Chen Q F, Koltun V. Combinatorial optimization with graph convolutional networks and guided tree search[C]// Proceedings of the 32 nd International Conference on Neural Information Processing Systems. ACM, 2018:537-546. DOI:10.5555/3326943.3326993

[29]
Drori I, Kharkar A, Sickinger W R, et al. Learning to solve combinatorial optimization problems on real-world graphs in linear time[C]// 2020 19th IEEE International Conference on Machine Learning and Applications (ICMLA). IEEE, 2020:19-24. DOI:10.1109/ICMLA51294.2020.00013

[30]
Zheng Y, Su H, Ding J, et al. Road planning for slums via deep reinforcement learning[EB/OL]. 2023:arXiv: 2305. 13060. https://arxiv.org/abs/2305.13060.

[31]
Wu L F, Cui P, Pei J, et al. Graph neural networks: Foundation, frontiers and applications[C]// Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining. ACM, 2022:4840-4841. DOI:10.1145/3534678.3542609

[32]
Manchanda S, Mittal A, Dhawan A, et al. Learning heuristics over large graphs via deep reinforcement learning[EB/OL]. 2019: arXiv: 1903.03332. https://arxiv.org/abs/1903.03332

[33]
Nowak A, Villar S, Bandeira A S, et al. A note on learning algorithms for quadratic assignment with graph neural networks[EB/OL]. 2017: arXiv: 1706.07450. https://arxiv.org/abs/1706.07450.

[34]
王玉璟, 孔云峰. 义务教育就近入学优化建模研究[J]. 地球信息科学学报, 2021, 23(9):1608-1616.

DOI

[Wang Y J, Kong Y F. Optimization modeling for nearby school enrollment of compulsory education[J]. Journal of Geo-information Science, 2021, 23(9):1608-1616.] DOI:10.12082/dqxxkx.2021.200728

[35]
Ioffe S, Szegedy C. Batch normalization: Accelerating deep network training by reducing internal covariate shift[C]// Proceedings of the International conference on machine learning. pmlr, 2015:448-456. DOI:10.48550/arXiv.1502.03167

[36]
He K M, Zhang X Y, Ren S Q, et al. Deep residual learning for image recognition[C]// 2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR). IEEE, 2016:770-778. DOI:10.1109/CVPR.2016.90

[37]
Sankar A, Wu Y, Gou L, et al. Dynamic graph representation learning via self-attention networks[EB/OL]. 2018: arXiv: 1812.09430. https://arxiv.org/abs/1812.09430

[38]
Veličković P, Cucurull G, Casanova A, et al. Graph attention networks[EB/OL]. 2017: arXiv: 1710.10903. https://arxiv.org/abs/1710.10903

[39]
Sharma S, Sharma S, Athaiya A. Activation functions in neural networks[J]. Towards Data Sci, 2017, 6(12):310-316.

[40]
Lei K, Guo P, Wang Y, et al. Solve routing problems with a residual edge-graph attention neural network[J]. Neurocomputing, 2022, 508:79-98. DOI:10.1016/j.neucom.2022.08.005

[41]
Vaswani A, Shazeer N, Parmar N, et al. Attention is all you need[C]// Proceedings of the 31st International Conference on Neural Information Processing Systems. ACM, 2017:6000-6010. DOI:10.5555/3295222.3295349

[42]
Williams R J. Simple statistical gradient-following algorithms for connectionist reinforcement learning[J]. Machine Learning, 1992, 8(3):229-256. DOI:10.1007/BF00 992696

[43]
刘萌伟, 黎夏. 基于Pareto多目标遗传算法的公共服务设施优化选址研究——以深圳市医院选址为例[J]. 热带地理, 2010, 30(6):650-655.

[Liu M W, Li X. A Pareto genetic algorithm for multi-objective site search problem: A case study on hospital location in Shenzhen city[J]. Tropical Geography, 2010, 30(6):650-655.] DOI:10.3969/j.issn.1001-5221.2010.06.014

[44]
Xiao N C, Bennett D A, Armstrong M P. Using evolutionary algorithms to generate alternatives for multiobjective site-search problems[J]. Environment and Planning A: Economy and Space, 2002, 34(4):639-656. DOI:10.1068/a34109

[45]
Deborah O M L, Chiu M Y L, Cao K. Geographical accessibility of community health assist system general practitioners for the elderly population in Singapore: a case study on the elderly living in housing development board flats[J]. International Journal of Environmental Research and Public Health, 2018, 15(9):1988. DOI:10.3390/ijerph15091988

Options
Outlines

/

〈 〉