Yao, Y., Lei, S., Guo, Z., Li, Y., Ren, S., Liu, Z., Guan, Q., Luo, P. (2023). Fast optimization for large scale logistics in complex urban systems using the hybrid sparrow search algorithm. International Journal of Geographical Information Science, 1-29.
01
摘要
物流对城市的发展和运营、以及经济增长至关重要。不断增长的客户需求和城市系统的复杂性是当前物流优化的两个挑战。然而，很少有研究考虑这两点，未能平衡效率和成本。在这项研究中，我们提出了一种混合麻雀搜索算法（SA-SSA），将具有快速计算速度的麻雀搜索算法和具有获得全局最优解能力的模拟退火算法相结合。选择武汉市进行物流优化实验。结果表明，SA-SSA可以在保证效率和方案质量的前提下优化大规模城市物流。与模拟退火、麻雀搜索和遗传算法相比，SA-SSA的成本分别降低了17.12、18.62和14.72%。虽然SS-SSA的成本比蚁群算法高11.50%，但其计算时间却减少了99.06%。此外，还进行了仿真实验，探讨了空间元素对算法性能的影响。考虑到众多客户和复杂路网的限制，SA-SSA可以提供高质量的解决方案，具有很高的效率。它可以支持实现物流企业对配送车辆的科学调度。
02
混合麻雀搜索算法
麻雀搜索算法（Sparrow search algorithm, SSA）是一种模拟麻雀觅食和预警行为的启发式算法。该算法求解速度快，但容易陷入局部最优，全局搜索能力较弱。模拟退火算法（SA）是一种基于蒙特卡罗思想设计的优化算法，具有跳出局部最优的能力。它通常应用于较大求解空间中搜索近似全局最优解。为了提高麻雀搜索算法的全局搜索能力，本研究将SSA和SA结合，提出了一种混合启发式算法（SA -SSA）。
2.1 优化问题的构建
物流优化问题可以理解为对客户服务顺序的合理排序。在本研究提出的基于麻雀搜索算法的物流优化算法中，K个麻雀对所有配送点的访问权重形成一个矩阵，配送车辆将按照权重顺序为各配送点服务。因此，物流优化的目的是获得一个合理的接入权重矩阵，以获得适当的配送效率和质量。访问权重矩阵如下：
其中d表示要优化的问题变量的维度，即物流分布点的个数。xi*表示第i个智能体的解决方案，即城市物流配送解决方案。xi,j表示第i个智能体在第j的客户点的权重，权重越高，访问的概率越高。
2.2 使用麻雀搜索算法得到每轮迭代最优解
总计K个智能体根据优化目标的不同分为三类：发现者、跟随者和侦察者。具体来说，将客户点数据和客户点间最短距离等物流数据输入SA-SSA，算法将麻雀种群分为发现者、跟随者以及侦查者，通过迭代更新麻雀种群寻找全局最优解。发现者为优化结果较好群体，它的位置更新公式如下：
为第i个个体在第t次迭代中的d维位置，α为(0,1]区间的随机数，Q为符合标准正态分布的随机数。R2为[0,1]区间的随机数，ST为[0.5,1.0]区间内的警告值。
对于跟随者，其位置更新公式如下：
xw为麻雀在当前种群中的最差位置，xbi为麻雀在当前种群中的最佳位置。
侦查者种群的位置更新公式如下：
β为符合标准正态分布的随机数，K为[-1,1]区间内的随机数，ε为较小数字， fW为最差位置麻雀的适应度值。
2.3 使用模拟退火算法对迭代最优解进行更新
为了避免麻雀搜索算法陷入局部最优，提高大规模城市物流配送的优化质量，本文引入了模拟退火算法。该算法的思路是受固体可燃物的模拟退火原理启发，其本质是一种基于概率的随机算法。因此，模拟退火算法可以使麻雀搜索算法以一定的概率跳出局部最优。
对于每轮迭代中使用麻雀搜索算法得到的结果，根据SA原理对其进行扰动，使得算法具备跳出局部最优解的能力。当算法满足迭代次数时，输出最终优化结果。
在模拟退火算法中，F(x)是优化目标，xbest是由麻雀搜索算法得到的当前最优解。在迭代求解过程中，算法随机扰动当前的解xold，产生新的解xnew。如果F1(xold)≥F1(xnew)，那么新解xnew将覆盖旧解xold。否则，差的解决方案xnew将被选择以一定的概率被接受，其概率p由Metropolis准则定义：
其中k表示迭代次数。T是当前的温度值，在本研究中用来控制模型收敛的速度。T在优化过程中会逐渐降低。它的温差代表新旧解决方案之间的差异。
03
实验与结果
为了验证SA-SSA算法在真实大规模城市物流中的有效性，我们获得了一家物流公司的在武汉市的客户位置和仓库数据。一千个客户点和四个仓库被随机抽取。除了位置信息外，客户点还包含了送货数量数据，该数据是1-100kg区间的随机值。此外，我们还从物流公司获得了车辆状况数据，包括车辆的最大载荷。
为了证明所提出的SA-SSA的有效性，我们进行了一系列的模型验证和比较，所选的四种算法是蚁群算法(ACO)、遗传算法(GA)、麻雀搜索算法 (SSA)和模拟退火算法(SA)。首先，我们利用SA-SSA在研究区进行了物流优化实验，计算了优化路径的总距离和时间，并将其与其他算法进行比较。其次，为了深入讨论复杂空间要素对物流优化算法的影响，我们进行了三套不同空间尺度下的模拟实验。
3.1 模型验证结果
为了验证所提出的混合算法的有效性，本研究依据武汉市客户点及路网数据构建城市物流配送场景，利用SA-SSA进行配送路径优化，并针对各类算法的优化结果进行对比分析。每类算法运行30次，记录平均路径总长度、标准差及计算时间。表格为每类算法配送路径优化的结果。
从表中可以看出，在最短配送路径优化结果方面，本文所提SSA-SA算法解的质量有了显著的提高。与模拟退火算法及遗传算法相比， SSA-SA算法的最小配送距离分别减少了17.77%和14.71%。值得注意的是，与原始麻雀搜索算法相比，本研究所提算法最短配送距离减少了18.61%。这说明本研究的改进方法提高了SSA-SA算法的全局搜索能力。此外，由于蚁群算法具有较强的全局搜索能力，其最短配送距离优于混合麻雀搜索算法，相比SSA-SA算法减少10.31%。
在计算效率方面，提出的混合麻雀搜索算法平均在804.61s完成1000个客户实例的路径配送优化，所需时间较少。可以发现混合麻雀搜索算法与麻雀搜索算法、模拟退火算法及遗传算法在计算时间上没有显著差异。但与蚁群算法相比，本研究所提算法的计算时间明显缩短。此外，本文提出的SSA-SA算法平均最小配送距离的标准差最小，且平均优化时间的标准差较小，相比其他算法具有更好的寻优精度和求解稳定性。综上所述，所提出的算法在城市物流配送场景下能够同时兼顾配送成本及计算时间，更好的满足当下城市物流配送需求。
3.2 物流优化算法的性能与不同尺度的空间影响
物流优化是一个在复杂空间约束下的优化问题。探讨空间特征如何影响算法性能以了解优化算法的机制是很重要的。这也有助于我们在进一步的研究中把GIS用于更复杂的空间约束下的物流优化。在这项研究中，我们计算了客户点的三种不同尺度的空间特征。通过根据空间特征对物流客户点进行分组，然后使用提议的SA-SSA分别进行优化，我们探讨了空间特征是如何影响算法的性能的。
1） 个体尺度
我们进行了单个规模的模拟实验，从单个客户点的空间特征角度分析了物流优化算法的性能。从仓库到客户点的网络效率对物流规划任务非常重要。它是节点之间最短路径距离的倒数，描述了一个仓库为客户点提供配送服务的便捷程度。在这项研究中，我们计算了每个客户点到四个仓库的平均网络效率，并分析了SA-SSA为不同网络效率水平的客户群提供服务的性能。
图1. 个体尺度(A)以及局部尺度(B)的模拟实验结果。对于每一套模拟实验，我们进行了低密度和高密度采样。对于个体尺度模拟实验，我们分析了低网络效率（low NE）与高网络效率（High NE）的结果差异。对于局部尺度模拟实验，我们分析了低紧密中心度（low closeness）和高紧密中心度（high closeness）的结果差异。
结果显示，当服务于任何网络效率水平的客户点时，SA-SSA都能保证最佳解决方案（图1(A)）。当客户点的网络效率较高，即离仓库较近时，SA的分布距离较长。特别是在高密度抽样的情况下，当服务于较高网络效率的客户时，SA的分布距离提高了2.66%，SSA的路径提高了0.09%，SA-SSA的路径提高了0.57%。在低密度抽样的情况下，当服务于网络效率较高的客户时，SA的分布路径提高了5.05%，SSA的路径减少了0.75%，SA-SSA的路径提高了2.29%。
在多仓库物流配送中，优化算法要实现合理的空间划分是有难度的。具体来说，存在这样的情况：靠近特定仓库的客户点被另一个仓库的车辆分配，导致分配成本增加。这个问题也会影响SA-SSA的性能，增加其配送路径的距离。然而，当网络效率增加时，SSA的配送路径会减少（0.75%，低密度抽样）或只稍微增加（0.09%，高密度抽样）。这表明，SSA可以考虑多仓库物流任务的空间划分问题。由于引入了SSA，SA-SSA在这个问题上有了部分改进。在为仓库周围的客户点提供服务时，SA-SSA的算法没有表现出与SA类似的配送效率下降的程度。
2） 局部尺度
局部尺度的模拟实验从客户点位置的局部空间结构来评估优化算法。物流优化的任务是确定访问每个客户点的顺序。客户点被服务的难易程度不仅取决于它离仓库的位置，也取决于它与其他客户点的联系是否方便。如果一个客户点离所有其他客户点都比较近，那么由物流车提供服务就比较方便。在本研究中，我们选择紧密中心度来表征城市道路网络中一个客户点的其他客户点之间的接近度。对于一个特定的节点，紧密中心度被计算为从这个节点到所有其他节点的最短路径的平均长度。与网络效率的模拟经验相似，我们计算了1000个客户点的接近度中心性，然后将它们平均分为两个子组。之后，对每个分组进行了两次低密度（100个点）和高密度（300个点）抽样，然后使用SA、SSA和SA-SSA进行物流优化。
结果显示，在高密度抽样的情况下（图1(B)），SA-SSA对服务于高亲密度中心的客户点（3511.02公里）的分布距离比服务于低亲密度中心的客户点（3582.43公里）减少了71.41公里。这表明，当一个客户点离其他客户点较近时，它更有可能被SA-SSA选中，从而导致高质量的配送路线。在同样的情况下，SA和SSA在为高接近度中心性客户点服务时，优化的配送距离分别缩小了39.63和35.40公里，几乎是SA-SSA的一半。综上所述，结果表明，当客户点具有高紧密性中心性时，它将被SA-SSA优先考虑，从而产生更好的解决方案和更低的成本。
3） 全局尺度
全局尺度的模拟实验从城市结构的角度评估了该算法。城市道路网络和客户具有空间上的异质模式。例如，一些地区的客户在空间上呈现出聚集性，而其他地区则是稀疏的。此外，城市道路网络的空间结构会影响不同地区的物流服务能力和效率。为了探索SA-SSA在服务不同空间特征的地区时的表现，我们对研究地区的1000个客户点进行了基于网络的频谱聚类，以获得不同空间模式的聚类。然后对每个聚类内的客户点分别进行物流优化实验，以评估算法的性能
在所有四个集群中，SA-SSA在分布距离方面的优化结果最好（图2(B)）。其中，在聚类簇1和3中，SA-SSA优化的距离分别比SSA短2.05和2.25%。此外，结果显示，在稀疏的城市路网中，物流优化算法更容易陷入局部最优，尤其是SA在武汉东北郊（聚类簇1，红点），路网稀疏，客户点的分布比较分散，物流配送算法的局部最优问题非常明显。此外，SA的物流配送距离比SSA高7.12%，比SA-SSA高9.31%。在武汉市南郊（聚类簇2），SA的物流分布距离比SSA和SA-SSA分别高5.58和5.74%。在如此稀疏的城市道路网络中，SA很难找到高质量的配送路径。同时，与SA相比，SSA可以有效地搜索到高质量的路径并大大减少配送距离。在城市中心区（聚类簇3和聚类簇4），城市道路网络更加紧密，与郊区相比，物流优化算法的局部最优问题相对较小。
图2. 全局尺度的模拟实验
04
结果与讨论
对于大规模的城市物流优化任务，传统的启发式算法无法快速提供高质量的车辆路径规划方案。本研究提出了一种基于SSA与SA的混合启发式算法，用于有效解决考虑复杂道路网络的多网点车辆调度问题。在武汉市进行的大型物流优化实验表明，所提出的SA-SSA算法可以有效地提供高质量的车辆路径解决方案，且性能稳定，适合于大规模城市物流优化。SA-SSA可以为相关物流企业提供车辆路径设计服务，从而提高物流效率，降低物流成本，实现物流智能化。此外，本研究探讨了城市的空间特征以及客户点对物流优化算法的影响。然而，这项研究仍有一些局限性，如没有考虑到实时交通状况。在未来，我们将在不同类型的城市中应用所提出的方法，并尝试引入深度强化学习来提高物流路线优化的效率。
来源：高性能空间计算智能实验室
转自：“测绘学术资讯”微信公众号
如有侵权，请联系本站删除！
