论文作者信息：Changhao Miao, Yuntian Zhang, Tongyu Wu, Fang Deng, and Chen Chen. 2024. Deep Reinforcement Learning for Multi-Period Facility Location: ��-median Dynamic Location Problem. In The 32nd ACM International Conference on Advances in Geographic Information Systems (SIGSPATIAL ’24), October 29-November 1, 2024, Atlanta, GA, USA. ACM, New York, NY, USA, 11 pages.
推文作者：缪昌昊
编者按本论文于2024年被第32届ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM SIGSPATIAL 2024) 录用为长文并应邀做口头报告，首次将深度强化学习方法应用于求解多周期设施选址问题。本论文针对多周期设施选址的复杂时空特性，提出了一种基于动态注意力网络的深度强化学习方法，可以同时捕捉问题的空间特征与时间特征。该方法采用了编码器-解码器的架构，并引入了门控循环单元对动态信息进行编码。实验表明，所提出的方法能够快速求解大规模多周期设施选址问题，在求解速度上比精确求解器Gurobi快2个数量级且拥有良好的泛化性能。
1. 背景近十年来，随着城市化的快速发展，城市中的基础设施规模急剧扩张。如图1所示，从2005年到2022年，北京市海淀区的应急服务设施规模呈现出快速扩张的趋势。随着设施数量的增加，城市将面临着各种各样的挑战，例如交通堵塞、设施老化以及设施开设等问题。出现这些问题的原因在于城市空间利用不合理、资源配置不均衡、交通规划不完善，上述问题均对城市的规划带来了重大挑战。为了保证城市的可持续发展，空间优化(Spatial Optimization)侧重于利用数学计算方法更好地解决地理决策问题，以实现更高效的城市规划和管理。
图1: 2005年、2012年和2022年（从左至右）北京市海淀区的应急服务设施分布密度图
设施选址问题(Facility Location Problem, FLP)是空间优化中一个经典且关键的问题，在供应链网络、物流配送、应急管理、泛在传感器网络等诸多实际场景中有着广泛的应用。设施选址问题主要被分为单周期问题和多周期问题。单周期问题通常假设某些问题参数保持不变，即使它们在实际应用中可能是动态变化的。在参数可预测的前提下，考虑未来参数的潜在变化通常对决策是有帮助的，因此多周期设施选址问题(Multi-period FLP)往往更加符合实际应用的需求。
与此同时，由于多周期设施选址问题的参数会随着周期动态变化，该问题的求解是一项艰巨的任务。在相关研究中，多周期设施选址问题的求解方法主要分为两大类：精确方法和启发式方法。精确方法往往通过建模技巧和分支定界框架来寻找问题的最优解，而在处理大规模问题时，该方法的计算代价会十分昂贵。因此，人们提出了启发式方法，其能够在可接受的时间内提供满意的解决方案。然而，启发式方法严重依赖于复杂的手工设计，忽略了周期之间的时间相关性，从而导致算法性能不理想。与此同时，对于大规模的多周期设施选址问题，其决策变量数目和搜索空间均十分庞大，这一特点给精确方法和启发式方法都带来了巨大的挑战。
2. 问题建模在多周期的设施选址问题中，运输成本和开设成本会随着周期的不同而变化，因此多周期设施选址问题的决策变量数目非常庞大。与此同时，决策过程中不仅需要考虑备选点的静态信息，还需要考虑它们在时间尺度上的相互关系。图2给出了一个具有10个备选点和3个周期的问题示例，其中每个周期运营的设施数量分别为1、3和5个。由图中可以发现，每个周期中设施的运营数量以及设施与客户之间的分配关系均会随着周期的变化而变化。
图2: 拥有10个备选点和3个周期，且pk = 1, 3, 5的pk-中值动态选址问题示例
3. 算法流程
图3: 所提出算法的流程图
为了将深度强化学习方法应用于问题的求解，本节中首先将数学模型重新表示为马尔可夫决策过程的形式，并对ADNet的具体网络结构和训练流程进行介绍。作者所提出算法的流程图如图3所示。
3.1 马尔可夫决策过程
REINFORCE算法采用梯度下降法对参数迭代更新，并直接以最小化代价函数为优化目标。
3.2 ADNet网络结构ADNet采用了编码器-解码器架构来更好地处理问题特征。编码器负责将所有输入节点的原始特征转换为隐藏编码，而解码器负责一次一个节点地生成节点序列。因此，解码器将编码后的隐藏编码作为输入，并输出下一个节点被选中的概率分布。ADNet模型的网络结构如图4所示。
图4: ADNet模型网络结构
3.2.1 编码器
图5: 基于REINFORCE的训练算法伪代码
图6: 不同规模的实验想定（小、中、大三个规模）
图7: 模型训练与模型网络的超参数设置
（3）对比算法作者将ADNet与一系列有代表性的基线算法进行了比较，以此验证所提出算法的有效性。为了使实验结果更加全面，作者与不同类型的方法进行了对比，其中包括精确求解器、深度学习算法、传统启发式方法和元启发式方法。具体而言，用于对比的基线算法如下所示：
精确求解器Gurobi深度学习基线算法，注意力模型(Attention Model, AM)置换类启发式算法(Teitz and Bart, Teitz-Bart)传统元启发式算法，模拟退火算法(Simulated Annealing, SA)此外，作者将算法的运行时间(Execution Time)与最优间隔(Optimal Gap)作为性能指标，且在所有场景中均将所有算例下的平均值作为最终结果。
（4）硬件设备所有实验均在2个GTX 3090 GPU和Intel(R) Xeon(R) Silver 4210R CPU @ 2.40GHz的设备上完成，所有代码均由Python实现。
4.2 对比分析ADNet在三个不同规模的问题下与上述基线算法进行了对比，并记录对比算法给出的目标函数值、最优间隔和运行时间。其中，最优间隔以精确求解器Gurobi给出的目标函数值作为基准进行计算。对于每个问题规模，记录的结果均为1000个随机生成算例下的平均值。此外，作者也对比分析了不同解码策略对模型性能的影响，包括贪婪策略和采样策略。对于采样策略，作者进一步比较了采样128次和采样1280次采样的性能差异。
图8: 不同问题规模下ADNet网络与其他基线算法的对比结果
如图8所示，ADNet在20、50和100个节点规模下与最优值的间隔分别达到了0.1016%、0.0994%和0.2728%，超过了其他所有启发式方法和学习类方法。
（1）与精确求解器的对比
（2）与（元）启发式算法的对比对于Teitz-Bart算法和SA，二者的性能很大程度上取决于算法参数，求解的时间越长对应的最优间隔也会越小。为了保证对比的公平性，作者对算法的参数进行了调整，使得其运行时间与ADNet贪婪解码策略的运行时间基本一致。由于多周期设施选址问题需要考虑时间维度的决策，导致问题的搜索空间非常庞大，因此（元）启发式算法无法快速给出令人满意的解决方案。
（3）与学习类算法的对比作者对比了ADNet与AM在不同问题规模下的结果，并测试了不同解码策略对模型性能影响。由于采样策略会多次采样概率分布以获得最佳值，因此采样策略应当优于贪婪策略。实验结果表明，即使是贪婪策略解码的ADNet仍然在最优间隔上大幅超过了1280次采样下的AM模型。与此同时，尽管AM模型的运行时间比ADNet更短，但二者所相差的运行时间以0.01s为单位，这种时间和性能之间的置换是可以接受的。
（4）解的可视化展示为了更好地说明问题的特点，作者对ADNet提供的解进行了可视化展示。如图9所示，用于可视化的算例共包含50个节点和5个周期，在每个周期中分别需要运营2、3、4、6和8个设施。图中的蓝色点代表客户位置，红色点代表开设的设施位置，而线段代表设施与客户之间的分配关系。
图9: 一个包含50个节点和5个周期的算例，以及对ADNet求解方案的可视化展示
4.3 泛化性能分析
图12: Gurobi和ADNet所提供求解方案的可视化，二者均将算例求解至了最优
图13: SA所提供求解方案的可视化
如图12和图13所示，Gurobi和ADNet均能将算例求解至最优，而SA只能给出近优解。很明显在第一个周期中，Gurobi和ADNet所提供的解决方案在客户的分配关系上更加合理。相反，SA提供的解可能会导致某些设施和客户之间的运输成本更高，从而导致分配关系的不平衡。在实际数据下的可视化结果强调了多周期设施选址在战略层面的重要性，选址阶段的决策会直接影响后续物流决策的效率。这一简单的例子直观地展示了ADNet模型在求解实际问题时的出色效果，表明了它在未来研究和实际应用中的巨大潜力。
5. 总结
参考文献：Changhao Miao, Yuntian Zhang, Tongyu Wu, Fang Deng, and Chen Chen. 2024. Deep Reinforcement Learning for Multi-Period Facility Location: -median Dynamic Location Problem. In The 32nd ACM International Conference on Advances in Geographic Information Systems (SIGSPATIAL ’24), October 29-November 1, 2024, Atlanta, GA, USA. ACM, New York, NY, USA, 11 pages.
