摘要
城市空间决策分析是空间优化的重要研究内容，在城市规划、物流配送、应急管理等多个领域都有十分重要的意义。城市设施选址问题是一类重要的空间优化问题。已有的研究多是采用启发式方法，基于深度学习方法的研究还很少。在本研究中，提出了一个统一的框架-SpoNet。将动态覆盖信息和注意力机制相结合，设计了一个动态覆盖注意力模型，求解了p-中值、p-中心和最大覆盖选址问题。通过将每个问题建模为马尔可夫决策过程，使用深度强化学习算法来训练模型。实验表明，SpoNet在求解设施选址问题上展现出显著优势。相比于传统的启发式方法求解速度更快，和最优解的差距更小。该方法在城市空间决策分析中具有广阔的应用前景，对可持续城市和社区的建设带来积极影响。
背景
城市空间决策分析在可持续城市和社区的发展中起着至关重要的作用。随着城市化进程的加快，城市面临着交通拥堵、基础设施陈旧、灾害风险等诸多挑战。这些挑战是由于城市空间利用不足和不均衡、公共设施配置不足、交通规划不切实际、应急预警机制不成熟等造成。 空间优化作为城市可持续发展的重要内容，通过合理的规划、设计和管理，最大限度地利用和优化现有空间资源。城市设施选址问题是一个重要的空间优化问题，在物流、通信和应急管理中起着至关重要的作用。面向城市的设施选址问题是城市空间分析的关键组成部分，通过分析城市现有设施的布局和空间分布，为城市规划、城市管理和设计提供可行的决策依据。在此过程中，应考虑设施建设因素的影响，可以极大地满足城市居民的需求，促进可持续发展，包括交通、环境、社会经济因素、政策和法规。
P-中值问题（p-Median）、最大覆盖选址问题（Maximum Coverage Location Problem, MCLP） 和p-中心问题（p-Center） 是经典的离散设施选址问题，为城市空间决策提供了科学合理的数学模型, 指导城市设施配置优化。求解选址问题的传统方法分为三类：精确算法、近似算法和启发式算法。上述算法已广泛应用于城市空间决策分析。近年来，一些深度学习方法被用于解决城市可持续发展的挑战和优化问题。尽管深度学习方法已被广泛用于解决路线问题，但很少有研究将这些技术应用于设施选址问题。
技术路线
1.将问题建模为马尔可夫决策过程
p-中值、p-中心和MCLP的核心是如何从N个候选设施中选择p个设施以满足目标函数。在决策过程中，每一步都选择一个设施点，直到选择p个设施点。下面将这个决策过程建模为马尔科夫决策过程（Markov Decision Process, MDP）。
MDP 通常由五元组表示，包括状态、操作、状态转换矩阵、奖励和折扣因子。
状态：状态sT=(Mt)表示第t步的当前解集，其中Mt包括时间T步的所有选择的设施点，M0为空集；
动作：在构造解决方案的过程中，每个步骤都必须选择一个节点作为设施点。设aT表示为zj,即在T时刻,选址节点j作为设施点；
状态转移：状态转换表示在状态st中，模型采用动作at进入下一个状态st+1=Mt+1=(Mt;zj)，即下一个状态st+1的解由当前状态st和动作对应的点zj拼接在一起。
折扣因子：折扣系数设置为 1。在计算奖励函数时，我们以目标函数作为最终奖励，不计算累积奖励。
奖励函数：策略网络的优化方向由奖励函数决定。
2.SpoNet
用pθ表示我们的策略，策略网络在每个时间步选择一个节点，直到获得p点作为设施。然后将其他需求点分配给最近的设施点，并计算最终目标函数。它为问题提供了一个可行的解决方案，用Π={Π1,...,Πp,p≤Π}表示，并且每一步只选择一个节点。因此,SpoNet的策略网络p(Π|s)可以表示为
SpoNet的主体为Encoder-Decoder框架，编码器对原始特征进行编码，为每个节点生成隐藏嵌入，而解码器则将隐藏嵌入作为输入。最后，每个节点的选择概率是输出。在设施选址问题中，节点之间存在覆盖关系。如果某个节点已被覆盖，则将不再选择该节点，或者选择的机会将减少。因此，我们提出了一种动态覆盖模型，对城市的静态坐标和城市之间的覆盖状态进行编码，以提高模型性能。
图 1：SpoNet的流程框架
结果
本研究将SpoNet 与三种类型的方法进行了比较：1） 数学规划求解器，包括 Gurobi、Cplex 和 COPT；2）深度模型基线，注意力模型（AM），一种基于DRL的求解TSP和CVRP的构造性方法，我们将其迁移到求解p-Median、p-Center和MCLP；3）启发式和元启发式算法，包括GA、VNS、SA、TS和Teitz-Bart。针对 p-Median 问题实现了 SA、VNS 和 Teitz- Bart;SA、TS 和 GA 用于 p-Center 问题;以及 MCLP 的 SA、VNS 和 GA。在测试过程中，为每组实验生成了 10000 个与训练数据分布相同的实例，使用目标函数值（Obj）、和最优解的差距（Gap）和运行时间进行评估。
可视化结果
图 2：由 Gurobi、SpoNet 和 SA 算法生成的 p-Median 在 n=100、p=15 时的可视化解
图 3：由 Gurobi、SpoNet 和 SA 算法生成的 p-Center 在 n=100、p=15 上的可视化解决方案
图 4：由 Gurobi、SpoNet 和 SA 算法生成的 MCLP 在 n=100、p=15、r=0.15 上的可视化解决方案
创新点
将p-中值、p-中心和最大覆盖选址问题建模为马尔可夫决策过程，并采用深度强化学习算法来训练模型；
设计了一种统一的深度学习模型——SpoNet，基于节点间的分配关系，结合设施选址问题的特性，将局部特征、分布关系以及动态覆盖信息融入模型中；
与成熟求解器、四种启发式方法以及注意力模型进行对比实验，证明了SpoNet的有效性。通过消融实验进一步验证了动态覆盖信息和门控循环单元的有效性。
结论
本研究提出了一个统一的深度学习模型-SpoNet，用于求解p-中值、p-中心和最大覆盖选址问题。通过将三个设施选址问题建模为马尔科夫决策过程，并使用强化学习算法训练模型，来处理序列中的长期依赖关系。通过和数学规划求解器、多种启发式方法、深度学习基线模型进行对比实验，验证了SpoNet在求解空间优化问题上的有效性。消融实验表明，动态覆盖信息和门控循环单元能够有效提高模型的性能。本研究所提出的方法为空间优化问题的求解提供了新的思路，为大规模空间优化问题的求解提供了一种新的方法。