微搜索算法“花”式求解双层车辆路径规划问题

来源: 黄翰/

华南理工大学

1734

2022-01-29 14:32:36

2022-01-29

随着城市中的货运车辆越来越多，城市交通管理和环境保护的压力与日俱增。为了提高物流效率，减轻货物运输所带来的负面影响，多层城市物流系统应运而生。其中，双层物流系统是多层城市物流系统最简单的形式。在双层物流系统中，大型货车把货物从仓库运送到中转站（卫星），再由小型货车完成最后一段的货物运输。

不论是战略层面的城市物流系统规划，还是日常运作层面的车辆路径管理，双层车辆路径问题（Two-Echelon Vehicle Routing Problem, 2E-VRP）[1]都是必须要解决的关键一环。现有的2E-VRP求解方法多利用变邻域搜索等局部优化算子对卫星进行随机打开、移除、交换等操作，得到2E-VRP的局部最优解。然而，这些方法过分依赖局部信息和局部优化算子，忽略了2E-VRP最优路径具有无交叉点哈密尔顿路的特点。

微搜索是一种在微小范围内的有效的定向搜索方法，它能集中算力，在某个确定的方向或者范围内获得高质量的解。由于相对于2E-VRP完整的解集而言，具有嵌入式哈密尔顿子图结构的解集是一个微小的搜索范围，因此智能算法研究中心的研究人员基于微搜索假设，结合2E-VRP最优路径具有哈密尔顿图的特性，在全局范围内将2E-VRP的最优路径规划考虑为基于一个嵌入式哈密尔顿图的搜索过程，提出一个基于嵌入式哈密尔顿图的启发式算法（Embedded Hamiltonian Graph-guided Heuristic Algorithm, EHG-HA）[2]。该算法可以在不违反任何一个约束条件的情况下搜索出交叉点尽可能少的哈密尔顿路径，从而获得2E-VRP的高质量求解。目前，此项成果已经发表在智能优化领域的国际学术期刊IEEE Transactions on Cybernetics（JCR一区，影响因子11.448）上。下面我们将对该研究工作展开介绍。

基于嵌入式哈密尔顿图的启发式算法（EHG-HA）主要包括三个阶段：初始化、卫星调整和路线重建。其中，我们主要在初始化机制和卫星调整机制上进行了创新。

图1 EHG-HA算法的流程示例

初始化机制：种“花”得“花”

嵌入式哈密尔顿图由嵌入式车辆路径组成，这些路径都是没有交叉点的哈密尔顿路径。如果将仓库和卫星视为两组不同的顶点，并且车载容量是无限的，那么具有最优路径规划的2E-VRP图是一个嵌入式哈密尔顿图。基于以上理论，我们提出一个基于哈密尔顿图的初始化机制（Initialization Scheme based on an Embedded Hamiltonian Graph, ISEHG）。

图2 ISEHG的说明示例。(a)为客户分配卫星，(b)根据所属卫星对客户分组，(c)根据角度对客户分组，(d)为每条路线选择每个最远的客户，(e)根据卫星和最远的客户重新分配剩余客户，(f)完成第二层路径的初始化，(g)完成第一层路径的初始化。

图2展现了整个初始化2E-VRP解的过程。因为最优解包含了嵌入式哈密尔顿图结构，所以采用微搜索方法所获得的解的质量显著较高。

由于2E-VRP有两层路径需要优化，因此，初始化机制主要分为两个阶段对2E-VRP的解进行初始化，图3和图4分别给出了ISEHG包含的两种策略的伪代码。

图3 算法1初始化第二层路径(ISR)

图4 算法2初始化第一层路径(IFR

动态卫星调整机制：“花”开不败

卫星在连接2E-VRP的两层路径中起着非常重要的作用。一旦一个卫星的状态发生变化，与该卫星相连的客户和仓库必须被重新安排到其他卫星上。因此，原来的路径基本上被破坏了。当随机对卫星的状态进行改变（移除、打开、交换）时，路径中的交叉点数量可能会增加。由此，我们提出一个动态卫星调整机制（Dynamic Adjustment for Satellites, DAS），旨在通过微搜索获得含有尽可能少交叉点的路径。DAS与之前最大的不同就是保持嵌入式哈密尔顿图不变，即维持路径“花”的形态。

DAS主要由两个策略组成：卫星重排策略（Satellite Rearrangement, SRa）和卫星约简策略（Satellite Reduction, SRd）。

SRa策略先移除所有二层路径，再根据贪婪操作符选择卫星，将其重新插入路径中，图5展示了其实现过程。

图5 SRa策略卫星调整的说明示例

SRd策略将容量最小的卫星的运输任务分配给插入成本偏差最小的卫星，根据第二层卫星的使用情况重新调整所有第一层路径，同时确保成本降低，图6展示了其实现过程。

图6 SRd策略卫星调整的说明示例

为了验证EHG-HA算法对2E-VRP求解的有效性，智能算法研究中心搜集整理出了一个全面的2E-VRP测试集。该测试集的详细信息如表1所示。（下载地址：http://www2.scut.edu.cn/huanghan/kycg/list.htm）

表1 测试集的详细信息表

该测试集数据数量庞大，包含了测试集2-6中的207个测试用例，性能优秀，能有效检验2E-VRP相关算法的优劣。与此同时，这也是从2E-VRP问题被提出以来，包含问题数量最多的测试集。

为了考察ISEHG初始化对2E-VRP求解的贡献，研究人员分别将它与五个初始化方法（NNM[3]、CW[4]、IM[5]、SA[6]、SM[7]）进行了比较。表2给出了所有初始化算法性能比较的统计数据结果。ISEHG在所有实例上都明显优于NNM、SA和SM，在194个实例上的表现明显优于CW。

表2 初始化算法的性能比较结果

为调查本文提出的DAS机制是否有效，研究人员开发了不使用DAS的EHG-HA变体EHG-HA-DAS和添加了局部搜索算子的EHG-HA变体EHG-HA+LS。表3总结了六种算法（EHG-HA、ALNS[8]、LNS-2E[9]、GFEA[10]、EHG-HA-DAS、EHG-HA+LS）在207个测试用例上的性能比较结果。EHG-HA的表现明显优于ALNS、LNS-2E和GFEA。此外，EHG-HA在60个实例上的表现显著优于EHG-HA-DAS。实证结果表明，DAS机制对于EHG-HA是不可或缺的。

表3 六个算法的性能比较结果

图7显示了使用六种算法求解2E-VRP构造的嵌入式哈密尔顿图路径交叉点个数的统计结果。与其他五种算法相比，EHG-HA算法在大多数情况下都能获得交叉点最少的路径。

图7 六种算法求解207个实例的路径交叉点个数统计，x轴中的1到207表示实例的序列号，其中1-30、31-54、55-162、163-180和181-207分别表示测试集2、3、4、5和6的实例，y轴表示交叉点的数量。

此外，图8给出了EHG-HA求解测试集5的6个测试用例的路径结构图，进一步证明了EHG-HA在大部分实例中可以比其它比较算法取得更少的路径交叉点个数，基于嵌入式哈密尔顿图的微搜索“花”式求解是十分有效的。

图8 EHG-HA求解测试集5的6个测试用例的路径结构图

总体而言，通过在嵌入式哈密尔顿图中进行微搜索，EHG-HA在求解大规模2E-VRP实例方面取得了显著的进步，在性能上明显优于ALNS、LNS-2E、GFEA等现有的高水平算法。微搜索方法的优势在EHG-HA上展露无遗！

未来，我们将研究如何有效划分搜索空间的有效决策子集，进一步挖掘子图结构，缩小搜索空间，使算法能够在有限的评估次数内快速得到问题的可行解。

参考文献

[1] A. Schrijver, Combinatorial optimization: polyhedra and efficiency, Springer Science and Business Media, vol. 24, 2003.

[2] H. Huang, S. Yang, X. Li*, and Z. Hao, “An embedded hamiltonian graph guided heuristic algorithm for two-echelon vehicle routing problem,” IEEE Transactions on Cybernetics, doi: 10.1109/TCYB.2021.3108597.

[3] D. J. Rosenkrantz, R. E. Stearns, and P. M. Lewis, “An analysis of several heuristics for the traveling salesman problem,” SIAM Journal on Computing, vol. 6, no. 3, pp. 563-581, 1977.

[4] G. Clarke and J. W. Wright, “Scheduling of vehicles from a central depot to a number of delivery points,” Operations Research, vol. 12, no. 4, pp. 568–581, 1964.

[5] R. H. Mole and S. R. Jameson, “A sequential route-building algorithm employing a generalised savings criterion,” Journal of the Operational Research Society, vol. 27, no. 2, pp. 503–511, 1976.

[6] B. E. Gillett and L. R. Miller, “A heuristic algorithm for the vehicle dispatch problem,” Operations Research, vol. 22, no. 2, pp. 340–349, 1974.

[7] J. E. Beasley, “Route first-cluster second methods for vehicle routing,” Omega, vol. 11, no. 4, pp. 403–408, 1983.

[8] V. C. Hemmelmayr, J. F. Cordeau, and T. G. Crainic, “An adaptive large neighborhood search heuristic for two-echelon vehicle routing problems arising in city logistics,” Computers & Operations Research, vol. 39, no. 12, pp. 3215–3228, 2012.

[9] U. Breunig, V. Schmid, R. F. Hartl, and T. Vidal, “A large neighbourhood based heuristic for two-echelon routing problems,” Computers & Operations Research, vol. 76, pp. 208–225, 2016.

[10] X. Yan, H. Huang, Z. Hao, and J. Wang, “A graph-based fuzzy evolutionary algorithm for solving two-echelon vehicle routing problems,” IEEE Transactions on Evolutionary Computation, vol. 24, no. 1, pp. 129–141, 2020.

研究团队介绍