论文推送 | 耦合动态时空图模型和深度强化学习的城市物流配送规划问题求解框架

Li, Y., Guan, Q.*, Gu, J. & Jiang. X. (2024) A deep reinforcement learning with dynamic spatio-temporal graph model for solving urban logistics delivery planning problems, International Journal of Digital Earth, 17(1): 2376273. DOI: 10.1080/17538947.2024.2376273.

作者简介：

李远远，博士研究生，中国地质大学（武汉）地理与信息工程学院。研究方向为深度强化学习与城市路径规划。

关庆锋（通讯作者），博士，教授，博导，中国地质大学（武汉）地理与信息工程学院。研究方向包括时空大数据、空间计算智能和高性能空间计算。

顾峻峰，博士研究生，中国地质大学（武汉）地理与信息工程学院。研究方向为GeoAI和空间数据挖掘。

姜昕彤，博士研究生，中国地质大学（武汉）地理与信息工程学院。研究方向为地理时空动态模拟和城市规划技术。

01、摘要

城市物流配送规划问题是城市空间决策分析的重要组成部分。然而，目前的研究面临以下问题：（1）现有的城市物流配送问题以行驶距离为目标，忽视了城市的实时交通信息；（2）常用的启发式方法难以基于根据实时交通信息对物流车辆行驶路线进行优化，也难以保证优化质量；（3）现存的深度强化学习方法忽视了城市实时的交通环境和城市物流任务的动态时空特征。为了解决以上问题，本研究提出了一种新的深度强化学习方法解决城市物流配送规划问题。在该方法中，使用时空动态图模型以捕捉城市物流配送规划任务中动态特征，利用时序模型提取物流车辆的时序特征，并结合多头注意力模型选择候选客户、优化物流车辆的行驶路线。最后，采用最大熵的行动者-批评者算法训练模型以获得最优策略函数。实验结果表明：与商业软件和启发式方法相比，本研究提出的方法能够以更快的计算效率、更高的优质质量获得解决方案。与其它深度强化学习方法相比，该方法能够有效的学习城市物流任务中的动态时空特征，提高了优化质量。

02、引言

城市物流配送规划问题是城市空间决策分析中的重要研究内容，它极大地促进了城市经济的发展。然而，由于城市基础设施陈旧、交通规划不足以及私家车数量的不断增加，城市交通拥堵成为城市发展的重大挑战。优化城市物流配送能够缓解城市交通拥堵，成为提高城市竞争力的重要战略举措。但是，传统的城市物流配送规划问题通常以行驶距离为目标，并假设交通情况是静态的，物流车辆按照预先规划的行驶路线为客户提高服务。在现实世界中，常态化的交通拥堵严重影响物流车辆为客户准时提高服务的能力。因此，基于实时交通信息的城市物流配送优化已成为空间决策分析的重大挑战。

在城市空间决策分析中，城市物流配送规划问题是一个著名的空间路径规划问题，利用优化方法规划物流车辆的行驶路线，从而降低城市物流配送成本。现有解决城市物流配送规划问题的方法主要可以分为两类：精确方法和启发式方法。精确方法通过穷举解空间确定最优解，该方法耗时较长。随着客户数量的增加，其计算时间会呈现指数级增长，只能用于小规模的城市物流配送规划问题。启发式方法能够在有限的时间提高可行的解决方案，但是需要专业的知识和经验，才能设计性能优异的算法，而且也难以保证优化质量。

目前，深度强化学习方法在解决城市空间决策问题中展现了具体巨大的潜力，已被用于优化典型的城市路径规划问题，如VRP和TSP等，获得了工业界和学术界越来越多的关注。现有的研究表明：相比于启发式方法，深度强化学习方法能够挖掘数据规律，取代人工经验和规则，具有更快的计算效率和更强的泛化能力，能够在极短的时间内获得高质量的优化方案。然而，现有的深度强化学习方法通常以传统的城市物流配送规划问题为主，忽视了动态的城市环境。此外，它们未充分考虑城市物流配送任务的动态特征，如已完成和未完成客户间的空间关系、物流信息和交通环境等动态特征，限制了深度强化学习的探索能力和优化性能。

本研究基于动态时空图模型提出了一种新的深度强化学习方法（DRLDSTG），用于解决具有实时交通环境下的城市物流配送规划问题。在该方法中，本研究在编码器中使用动态时空图模型对客户和物流车辆的行驶信息进行动态编码，并在解码器中利用时序模型和多头注意力模型确定候选客户、优化物流车辆的行驶路线，通过编码器和解码器的不断交互，完成城市物流配送规划问题。为了展现DRLDSTG方法的性能，本研究采用真实的城市交通和物流场景，采用商业软件Gurobi、启发式方法和现有经典的深度强化学习进行对比分析，以探索不同方法的性能差异，并通过可视化分析检验模型的有效性。

03、研究方法

本研究基于动态时空图模型提出了一种深度强化学习方法（DRLDSTG），优化实时条件下的城市物流配送规划问题。图1展示DRLDSTG方法，该方法分为四个部分：（1）数据处理模块，该模块被用来提取城市物流配送规划任务下的静态要素（位置数据）和动态要素（物流和交通数据等）；（2）动态特征处理模块，该模块被用来构造城市物流配送任务的动态时空间结构；（3）基于编码器-解码器结构的动态时空图模型（DSTG），该模型表示策略函数被用来选择候选客户和车辆行驶路线；（4）训练方法模块，该模型以马尔可夫为基础被用来训练动态时空图模型。

图1 DRLDSTG方法结构

图2 DSTG模型结构

（1）动态时空图模型

图2展示了基于编码器-解码器结构的动态时空图模型（DSTG）。该编码器对城市物流配送任务中的客户位置等静态元素和物流信息等动态元素进行编码，从而生成城市物流配送任务的动态图嵌入；解码器则将动态图嵌入作为输入，并利用物流车辆容量等信息，以最大概率输出候选客户和车辆行驶路线；最后，该模型根据相关的输出信息，对动态元素进行更新。

在本研究中，动态时空图模型的编码器与Wen等人（2022）的研究类似。Wen等人（2022）根据客户的空间距离构建时空图关系，但是忽略了物流和交通信息等动态变化特征。因此，本研究中的编码器以客户的动态时空关系为基础，利用城市物流配送任务的动态时空图特征，构建动态时空图编码。其中，动态时空特征可以分为两类：静态元素和动态元素。静态元素表示物流客户的二维空间坐标信息，其不会随着时间的变化而变化。动态元素中表示物流信息、交通信息和客户间的空间关系，它们会随着物流车辆的行驶和客户服务不断发生变化。因此，本研究利用图卷积网络（Graph Convolutional Network, GCN）和门控递归单元（Gate Recurrent Unit, GRU）根据静态和动态元素，对城市物流配送任务进行动态时空图编码。

具体来说，本研究使用一维卷积核将客户的空间位置

映射到

维度的节点编码

。客户的物流信息

和交通信息

也使用一维卷积将其映射到dh维度特征编码

和

。在交通信息中，

表示已完成客户服务序列的物流车辆行驶时间，

表示在时间t下物流车辆从客户i出发到其它未服务客户的物流车辆行驶时间。随后，将客户位置信息、客户物流信息和交通信息拼接到形成特征集合，即

。为了获得已服务和未服务客户间的空间关系，本研究采用以下方式构建动态邻接矩阵：

在公式（5.7）中，

是邻接矩阵

的元素，表示客户在时间t下的空间关系。

根据城市物流配送任务特征和客户的空间关系，本研究采用GCN对其进行编码，详细过程如下：

在公式（5.8）中，

是自连接矩阵；

是度矩阵；

是第l层的图卷积网络；

是参数矩阵；

是sigmoid函数；在本文中，本研究采用两层的GCN模型用来提取城市物流配送任务的空间图编码，其表示如下：

在公式（5.9）中，W0和W1表示相关参数；Ft是在时间步t下的城市物流配送任务特征矩阵。

为了利用历史图编码信息，本研究使用GRU时序模型记录城市物流任务的空间结构变化信息，对当前的图编码信息进行更新，其公示表示如下：

在公式（5.10）中，Ht-1表示在t-1时间步下的城市物流任务的时空图编码。

在每个时间步上，解码器根据城市物流配送任务的动态时空图嵌入和物流车辆特征，输出候选客户和物流车辆的行驶路线。首先，解码器使用一维卷积对物流车辆信息

进行处理

，其中车辆信息中

、

和

分别表示物流车辆的位置、容量和出发时间。接着，GRU根据历史物流车辆信息和当前物流车辆信息计算物流车辆的时空特征，其计算公式为：

在公式（5.11）中，Rt-1表示t-1时刻下物流车辆的时空特征。

随后，多头注意力（Multi-Head Attention, MHA）计算客户和旅行路线的概率，并以最大概率输出下一个客户和物流车辆的行驶路线。具体过程如下：

在公式（5.12）中，RtWq，HtWk和HtWv分别表示注意力中的查询、健和值；Wq，Wk和Wv分别是相关参数；m表示注意力的个数；MHA的核心是多个缩放点积注意力模型，其表示为：

公式（5.13）是缩放点积注意力模型；dk是

和

的矢量长度；W3是其参数。

最后，本研究使用softmax函数计算候选客户和物流车辆行驶路线的概率，公式表示为：

公式（5.15）中pt表示相关概率。

（2）训练方法

由于优化问题缺乏标注数据（最优解），本研究利用带有最大熵的行动者-批评者算法来训练动态时空图模型，以确定最优策略。在这种方法中，行动者模型是策略函数负责做出决策。批评者是另一个神经网络模型，用于评估行动者模型的决策。最大熵被用作正则化，以提高行动者模型的探索能力。在深度强化学习中其损失函数定义如下：

在公式（5.16）中，R(π)是累积奖励值；

是行动者模型，即动态时空图模型，被用来指导物流车辆行为；B(S)是批评者模型是一个全连接深度学习模型，被用来对物流车辆行为进行评价；

是一带有权重的熵函数，被用来增加行动者模型的探索能力。因此，在深度强化学习中实时交通条件下的城市物流配送优化模型训练过程如算法1所示：

算法1 带有最大熵的行动者-批评者算法的工作流程

04、研究数据

图3展示了成都市研究区。交通网络来自于OSM (http://www.openstreetmap.org)。OSM是一个免费、高精度的开源地图网站。交通网络包含道路的定位信息和属性信息。道路的交通速度来自于DiDi（https://outreach.didichuxing.com）的出租车轨迹数据。针对出租车轨迹数据，剔除离群数据后，对每天的时间进行离散化，每隔十分钟计算一次道路的交通深度情况。

为了评价优化方法，本研究在成都市区域内生成不同客户规模的城市物品配送案例开展系列实验。具体而言，本研究随机生成10、20、50和100个客户的城市物流配送案例，并将相应的物流车辆容量分别设置为20、30、40和50，其客户和仓储的位置是在POI数据中随机选择。为了训练和测试模型，该研究在2018年3月1日至30日从成都市随机生成10万个城市物流配送案例作为训练数据集，并在该时间段内随机生成3千条城市物流配送案例作为测试数据集（H(S)）。为了进一步验证模型，该研究也在2018年3月31日随机生成3千条城市物流配配送案例作为新的测试据集（H(G)），用于评估方法在未来城市交通和物流方面的鲁棒性和可靠性。最后，该研究在工作日（星期一、星期二、星期三和星期五）和周末（星期六和星期日）等不同的交通场景下对方法进行评估。

图3 成都市主城区行政区划图

05、研究结果

由表1和表2可知，DRLDSTG方法可以在毫秒内得到优化结果，它在不同客户规模下的城市物流配送案例均实现了最佳性能。在H(S)和H(G)中，与商业优化软件和启发式方法相比，深度强化学习方法所需要的计算时间最少。DRLDSTG方法相比于其它深度强化学习方法需要消耗更多的时间，这是因为DRLDSTG方法根据实时交通条件和物流信息构建城市物流任务的动态图需要消耗较多的时间，但是仍然能够在极短的时间内得到优化结果。在城市物流配送优化结果方面，DRLDSTG方法具有最好的优化质量、更高的稳定性和更强的鲁棒性。在只包含10个客户规模下的城市物流配送任务中，各个方法均表现出较好的结果，它们相互间的差距也比较小。随着客户规模的增加，商业优化软件Gurobi无法在有限的时间内得到优化结果，启发式方法也难以快速获得高质量的优化方案。与其它深度强化学习方法相比，DRLDSTG只增加了极少的时间，却获得了更高的优化质量。

为了验证DRLDSTG方法在鲁棒性和可靠性方面的优势，表3统计城市物流配送优化结果的标准差、偏差和平均预测区间宽度。标准差和偏差值表示方法的波动程度，其值越小说明相应的方法具有更高的鲁棒性。平均预测区间宽度表明了模型的在不确定性条件下的可靠性，其值越小相关方法就越可靠。由表3的统计结果可知，DRLDSTG方法的标准差和偏差值最小，在本研究中表现出最强的鲁棒性。在95%的显著性水平计算条件下，DRLDSTG方法的平均预测区间宽度最小，具有最强的可靠性。因此，在鲁棒性和可靠性方面，DRLDSTG方法的性能优于其它方法。

此外，为了进一步展示DRLDSTG方法在不同交通条件下的优越性，本研究统计了商业优化软件、启发式方法和深度强化学习方法的在工作日和周末条件下不同客户规模下的优化结果。图4展示了各个方法在在不同场景下的箱型图，箱型图越小、越短，说明方法的优化结果越好，越稳定。在所有方法中，DRLDSTG的始终显示出最小和最短的箱型图，表明该方法具有最好的优化性能。实验结果也表明启发式方法的稳定性最低，波动性程度最高。随着客户数量的增加，与DRLDSTG方法相比，其它深度强化学习方法也表现出更差的稳定性。例如，在客户数据为10和20的城市物流配送任务中，DRL方法表现出较高的稳定性，但是当客户数量增加到50和100时，其方法的优化性能就会急剧下降。

综上所述，本研究提出的DRLDSTG方法在优化效率方面优于商业优化软件Gurobi和启发式方法，能够在实时交通条件下与城市环境进行实时交互，并根据交通和物流信息的变化，优化物流车辆的行驶路线。与此同时，本研究也与其它经典的深度强化学习方法进行对比，尽管计算时间略多余其它的深度强化学习方法，但是DRLDSTG方法能够在优化质量、模型的稳定和模型的可靠性均优于其它的方法。因此，DRLDSTG方法能够完全适应于实时交通条件下的城市物流配送任务。

表1 各个方法的平均计算时间

表2 各个方法的平均优化目标

表3 各个方法的鲁棒性和可靠性分析

图4 各个方法在不同场景下的行驶时间箱型图

06、总结

作为空间决策分析的重要组成部分，城市物流配送问题已受到广泛关注。随着城市交通网络的的日益复杂和拥堵，实时交通条件增加了空间决策分析的动态性和不确定性。城市物流配送系统需要捕捉交通拥堵和事故等动态信息，快速确定或修改物流车辆的行驶路线。然而，基于实时交通条件下的城市物流配送规划问题是一个NP-hard问题。与其它空间决策分析问题相比，它涉及更加复杂的整形规划模型。以精确方法为代表的Gurobi商业求解器，通过穷举解空间获得最优解，但是计算时间呈现出指数级的上升趋势，只能解决小规模的城市物流配送问题（少于20个客户），并且无法在实时交通条件下快速修改行驶路线。启发式方法可以在有效的时间内获得城市物流配送的行驶路线，但是设计高质量的启发式方法很大程度上依赖于专家的知识和经验，并且难以充分利用实时交通条件等信息，容易陷入局部最优状态。

深度强化学习方法是解决实时交通条件下城市物流配送规划问题的最有效工具，该类型方法是一种数据驱动的方法，利用历史物流订单和交通信息进行训练。深度强化学习方法可以使智能体与城市环境实时交互，提供更快的计算速度和更好的泛化性能。但是，现有的深度强化学习方法忽略了城市物流任务和环境的动态特征，如已完成和未完成客户的动态时空结构以及动态交通信息等。为解决该问题，本研究在深度强化学习方法中引入了动态时空图模型（DRLDSTG）。实验结果表明，动态时空图模型可以提高模型的优化性能、鲁棒性和可靠性，优于商业软件、启发式算法和其它的深度强化学习方法。

欢迎关注

HPSCIL@CUG