| 引用本文: | 李正雯,胡蓉,钱斌,金怀平,吕阳.学习型离散排超联赛算法求解带时间窗的绿色多车型两级车辆路径问题[J].控制理论与应用,2023,40(3):549~557.[点击复制] |
| LI Zheng-wen,HU Rong,QIAN Bin,JIN Huai-ping,LV Yang.A learning discrete volleyball premier league algorithm for solving green two-echelon heterogeneous-fleet vehicle routing problem with time windows[J].Control Theory and Technology,2023,40(3):549~557.[点击复制] |
|
| 学习型离散排超联赛算法求解带时间窗的绿色多车型两级车辆路径问题 |
| A learning discrete volleyball premier league algorithm for solving green two-echelon heterogeneous-fleet vehicle routing problem with time windows |
| 摘要点击 1116 全文点击 272 投稿时间：2021-08-31 修订日期：2023-03-22 |
| 查看全文 查看/发表评论 下载PDF阅读器 |
| DOI编号 10.7641/CTA.2022.10819 |
| 2023,40(3):549-557 |
| 中文关键词 两级车辆路径问题 绿色 多车型 时间窗 加权K-means算法 排超联赛算法 |
| 英文关键词 two-echelon vehicle routing problem green heterogeneous-fleet time windows weighted K-means algorithm volleyball premier league algorithm |
| 基金项目 国家自然科学基金项目(61963022, 62173169), 云南省基础研究重点项目(202201AS070030)资助. |
|
| 中文摘要 |
| 针对现实中广泛存在的带时间窗的绿色多车型两级车辆路径问题(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. |
|
|
|
|
|