学习型离散排超联赛算法求解带时间窗的绿色多车型两级车辆路径问题

A learning discrete volleyball premier league algorithm for solving green two-echelon heterogeneous-fleet vehicle routing problem with time windows

针对现实中广泛存在的带时间窗的绿色多车型两级车辆路径问题(G2E-HVRP-TW),本文提出一种结合加权K-means算法(WKA)的学习型离散排超联赛算法(LDVPLA)进行求解.首先,根据该问题规模大、约束多的特点,采用WKA将原问题G2E-HVRP-TW分解为一个绿色多车型车辆路径子问题(GHVRP)和一组带时间窗的GHVRP(GHVRP-TW),从而实现两级问题间的部分解耦,以合理缩小搜索空间.然后,利用LDVPLA求解分解后的一系列子问题,并将各子问题的解合并后得到原问题的解. LDVPLA在竞赛阶段将标准排超联赛算法(VPLA)中实数个体更新操作替换为一系列排序操作,使其能够直接在问题离散解空间内执行基于VPLA机制的搜索,可提高搜索效率;在学习阶段构建三维概率矩阵模型合理学习并积累优质解信息,有利于驱动算法较快到达解空间中的优质解区域执行搜索;在淘汰阶段设计一种重启策略,可避免算法过早陷入局部最优.最后,通过在不同规模算例上的仿真实验和算法对比,验证了所提算法的有效性.

This paper proposes a learning discrete volleyball premier league algorithm(LDVPLA)combined with the weighted K-means algorithm(WKA)for the widely existing green two-echelon heterogeneous-fleet vehicle routing problem with time windows(G2E-HVRP-TW).Firstly,according to the characters of the problem with a large scale and strong constraints,the WKA is used to split the G2E-HVRP-TW into a green heterogeneous-fleet vehicle routing problem(GHVRP)and a series of GHVRP with time windows(GHVRP-TW),so as to realize the partial decoupling between the two-level problems and reasonably reduce the search space.Then,the LDVPLA is designed to solve those subproblems,the solutions of each subproblem are combined to obtain the solution of the original problem.The LDVPLA replaces the real number individual updating operations of the volleyball premier league algorithm(VPLA)with a series of proposed arrangement operations in the competition phase,so that it can perform the search directly in the discrete solution space based on the mechanism of VPLA,which can improve the search efficiency.In the learning phase,a three-dimensional-based probabilistic model is designed to learn and accumulate the information of high-quality solutions,which is conducive to driving the algorithm to reach the high-quality solution area in the solution space to perform the search.In the elimination phase,a restart mechanism is designed to avoid falling into local optimal algorithm too early.Finally,the effectiveness of the proposed algorithm is verified by simulation experiments and algorithm comparisons on different scale examples.