1484
0
0
2019-11-03 11:52:10
2021-09-02
随着物流领域的不断发展，越来越多的货运车辆投入到城市物流运输之中，尽管这样的趋势在一定程度上给城市物流带来了极大的便利，但同时也给城市交通管理和环境保护带来了巨大的挑战。因此，研究人员提出了一种双层次物流配送系统，该系统首先由大型货车将货物从仓库运送到中转站，再由中转站的小型货车进行配送来完成最后一段货物运输。这种双层次物流配送系统可以有效地把大型货车限制在城外，一定条件下减少了大型货车在城市内的行驶里程。然而构建双层次物流配送系统往往需要求解双层次车辆路径规划问题（2E-VRP），该问题是一种比经典路径规划问题更复杂的NP难问题。
图一 2E-VRP可行解示意图
如图一所示，2E-VRP可以用一个加权的无向图G(V, E)来表示，其中V和E分别代表顶点集和边集。顶点集V由仓库节点V0、m个中转站的子集VS和n个客户的子集Vc组成; 边集E = {E1，E2}，其中，E1为第一层路径组成的边子集，E2为第二层路径组成的边子集。2E-VRP问题可以简单理解为在给定约束条件下设计第一层和第二层路线的整体规划。然而考虑到不同运输层的车辆数以及车辆的载重量有所差异，第二层路径上的VRP子问题个数往往是不确定的，因而仅仅通过距离信息或其他简单的信息是很难将第一层与第二层的VRP子问题完全分离的，这就给构建双层次物流配送系统的研究带来了巨大的挑战。不仅如此，随着2E-VRP问题规模的增加，中转站-顾客之间的分配关系也会变得更加复杂。
针对上述问题，智能算法实验室提出一种基于图的模糊进化算法(GFEA)[1]，该算法借鉴一些求解2E-VRP问题算法的优点，如ACOS[2]，BSOA[3]，BCA[4]等，从用户之间的模糊相关性出发，探索大规模物流配送路径问题的高质量可行解，为智慧城市的物流配送提供了技术支撑。目前该研究成果已成功发表在进化计算领域顶级国际学术期刊IEEE Transactions on Evolutionary Computation（JCR中科院一区，影响因子8.124）上。下面我们对本研究工作的相关成果展开介绍。
图二 基于图的模糊进化算法流程
基于图的模糊进化算法流程如图二，该算法首先构造初始种群，采用统计模糊估计方法来构造当代种群的模糊分配图，在此基础上迭代学习双层次路径的分配关系，并设计不同的模糊启发式算子生成下一代新解，最终构造出能够解决大规模用户需求的双层次路径分配问题的新方法。图三展示了采用统计模糊估计所构造的种群模糊分配图，其中，为了提高第一层路径构造的搜索效率，基于概率图我们采用模糊邻域搜索策略来寻找更有效的搜索路径。
图三 种群模糊分配图
在模糊分配图的基础上，我们通过分解当前种群用户之间的模糊关系矩阵，获取一系列具有特定关系的模糊用户子集，如图四所示。该算法将模糊子集作为启发式信息，并设计相应的模糊操作算子，最终获取到2E-VRP问题的第2层优化路径。
图四 具有特定关系的模糊用户子集
为了验证所提算法GFEA的有效性，本文首先与 LNS-2E、ALNS[5]、GRASP 等求解 2E-VRP问题的算法进行对比分析，实验对比结果如图五所示。结果表明，基于图的模糊进化算法相较于其它算法，在大规模测试用例（Set5）上取得了较好的可行解。另外，在相同实验环境的条件下，对大规模测试集（SET 5）上的每一个测试用例独立进行 30 次实验，最终实验结果如图六所示。从实验结果不难看出，GFEA算法在大规模测试用例上可以获取更加稳定的解。并且，通过观测多个测试用例的四分位图，我们发现该算法在获取最优解的上分位数与下分位数之间的差异较小，主要原因是算法基于图结构的模糊分配策略，利用种群的整体优势，减少了卫星-用户之间大量重复匹配可能带来的搜索无效性的出现次数。
图五 算法对比实验结果
图六 GFEA算法在大规模测试集（SET 5）上
重复实验结果
目前，大规模双层次车辆路径问题[6]作为城市物流领域前沿核心的复杂规划难题，具有极高的研究意义和学术价值。本文针对大规模路径优化问题中双层次分配的复杂性，提出了一种求解2E-VRP问题的基于图的模糊进化算法（GFEA），该算法既提高了双层次车辆路径问题的效率和性能，也为城市物流多层次运输调度提供高效可行的实施方案。下面我们给出一些基于该算法的应用案例。
图七 物流多层调度方案演示软件示意图
案例一为物流多层调度方案演示软件，如图七所示，该案例结合相关的智能算法来解决实际问题，如搅拌站选择问题、单层车辆路径问题、双层车辆路径问题等。目前，该成果已经成功应用在广州、南宁等多个重要城市的规划设计方案中，大大提高了规划的质量与工作效率，取得明显成效。不仅如此，该项成果还成功应用在国内知名物流企业的冷链物流系统中。
案例二为大型港口优化项目，该项目综合应用各类信息技术、控制技术、运营管理、港口资源以及电子商务等，通过GFEA求解2E-VRP问题的思想，来实现港口人力、资金、物资、设备以及其他资源的互联共享，从而对港口实行横向贯通、纵向可控的全方位管理。
从上述案例可以看出，GFEA在求解大规模路径优化问题上具有一定的优势，主要原因在于它能避免不合理的分配关系所引起的不同中转站变更问题的发生，这使得评价函数的估计次数减少。其次，每代种群的不同个体信息交换估计的模糊分配图，使GFEA在迭代分配学习过程中保持了种群的优势。但 GFEA 在一定程度上仍需进一步改进，例如，基于图的模糊算子对模糊子集的数目很敏感，且影响解决方案评估的模糊分配指标也需要进一步讨论。
参考文献
[1] Xueming Yan, Han Huang*, Zhifeng Hao and Jiahai Wang. A Graph-based Fuzzy Evolutionary Algorithm for Solving Two-Echelon Vehicle Routing Problems. IEEE Transactions on Evolutionary Computation, 2019.[DOI:10.1109/TEVC.2019.2911736].
[2] Xueming Yan, Zhifeng Hao, Han Huang* and Hongyue Wu. Ant colony optimization with human-computer cooperative strategy for two-echelon vehicle routing problem [C]//Proceedings of the Genetic and Evolutionary Computation Conference Companion. ACM, 2017: 1443-1446.
[3] Xueming Yan, Zhifeng Hao, Han Huang* and Gang Li. Human-computer cooperative brain storm optimization algorithm for the two-echelon vehicle routing problem [C]//2016 IEEE Congress on Evolutionary Computation (CEC). IEEE, 2016: 2676-2681.
[4] Tian Liu, Zhixing Luo*, Hu Qin and Andrew Lim. A Branch-and-cut Algorithm for the Two-echelon Capacitated Vehicle Routing Problem with Grouping Constraints. European Journal of Operational Research, Volume 266, Issue 2, 16 April 2018 : 487-497.
[5] V. C. Hemmelmayr, J. F. Cordeau, and T. G. Crainic. An adaptive large neighborhood searchheuristic for two-echelon vehicle routing problems arising in city logistics. Computers & operations research, 2012, 39(12): 3215-3228.
[6] U. Breunig, V. Schmid, R. F. Hartl and T. Vidal. A large neighbor-hood based heuristic for two-echelon routing problems. Computers & Operations Research, 2016, 76: 208-225.
-END-
文字：颜学明、刘子钊
校稿：冯夫健
图：颜学明
