首页|混合超启发式算法求解复杂两级车辆路径问题

混合超启发式算法求解复杂两级车辆路径问题

Hybrid hyper-heuristics algorithm for solving complex two-echelon vehicle routing problem

扫码查看
原文链接
  • 维普
  • 万方数据
针对模糊需求下的绿色两级车辆路径问题,以最小化车辆运营成本和油耗成本之和为优化目标,提出一种混合超启发式算法进行求解.首先,考虑两级问题解空间庞大且相互耦合,设计一种聚类分解策略将该问题分解为多个子问题,以合理缩小问题搜索空间;然后,提出增强超启发式分布估计算法(enhanced hyper-heuristic estimation of distribution algorithm,EHHEDA)对各个子问题进行求解,进而获得原问题的解.EHHEDA基于超启发式算法框架,在高层策略域设计一种基于三维概率模型的分布估计算法,动态确定由底层操作域中各搜索算子所组成的排列(即高层个体),可有效控制和引导整个算法的搜索行为;同时,在底层操作域设计10种有效邻域搜索算子,并加入重升温操作的模拟退火机制作为问题解(即底层个体)的接受准则,有利于在问题解空间中执行深入搜索.仿真实验结果表明,所提出的算法在大多数测试集上优于近年来用于求解类似问题的算法,验证了所提出算法的有效性.
Aiming at the green two-echelon vehicle routing problem with fuzzy demand,a hybrid hyper-heuristic algorithm is proposed to solve the problem with the objective of minimizing the sum of vehicle operation cost and fuel consumption cost.Firstly,considering that the solution space of the two-echelon problem is huge and coupled,a clustering decomposition strategy is designed to decompose the problem into several sub problems,so as to reduce the search space of the problem reasonably.Then,an enhanced hyper-heuristic estimation of distribution algorithm(EHHEDA)is proposed to solve each sub problem and obtain the solution of the original problem.Based on the hyper heuristic algorithm framework EHHEDA designs a distribution estimation algorithm based on three-dimensional probability model in the high-level strategy domain,dynamically determines the arrangement(i.e.the high-level individual)composed of search operators in the low-level operation domain,and can effectively control and guide the search behavior of the entire algorithm.At the same time,10 effective neighborhood search operators are designed in the bottom operation domain,and the simulated annealing mechanism of reheating operation is added as the acceptance criterion of the problem solution(i.e.the bottom individual),which is conducive to the in-depth search in the problem solution space.The simulation experimental results show that the proposed algorithm outperforms the algorithms used to solve similar problems in recent years on most test sets,which verifies the effectiveness of the proposed algorithm.

green two-echelon vehicle routing problemfuzzy demandclustering decompositionhyper-heuristic algorithmestimation of distribution algorithmsimulated annealing

尹丹、胡蓉、钱斌、郭宁

展开 >

昆明理工大学信息工程与自动化学院,云南昆明 650500

云南省计算机技术应用重点实验室,云南昆明 650500

绿色两级车辆路径问题 模糊需求 聚类分解 超启发式算法 分布估计算法 模拟退火

国家自然科学基金国家自然科学基金云南省基础研究重点项目

6217316961963022202201AS070030

2024

10.7540/j.ynu.20220439

云南大学学报(自然科学版)
云南大学

云南大学学报(自然科学版)

CSTPCD北大核心
影响因子：0.663
ISSN：0258-7971
年,卷(期)：2024.46(1)
  • 8