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

作     者：尹丹 胡蓉 钱斌 郭宁 YIN Dan;HU Rong;QIAN Bin;GUO Ning

作者机构：昆明理工大学信息工程与自动化学院云南昆明650500 云南省计算机技术应用重点实验室云南昆明650500 

基　　金：国家自然科学基金(62173169,61963022) 云南省基础研究重点项目(202201AS070030) 

出 版 物：《云南大学学报（自然科学版）》 (Journal of Yunnan University(Natural Sciences Edition))

年 卷 期：2024年第46卷第1期

页      码：23-37页

摘      要：针对模糊需求下的绿色两级车辆路径问题,以最小化车辆运营成本和油耗成本之和为优化目标,提出一种混合超启发式算法进行求解.首先,考虑两级问题解空间庞大且相互耦合,设计一种聚类分解策略将该问题分解为多个子问题,以合理缩小问题搜索空间;然后,提出增强超启发式分布估计算法(enhanced hyperheuristic estimation of distribution algorithm,EHHEDA)对各个子问题进行求解,进而获得原问题的解.EHHEDA基于超启发式算法框架,在高层策略域设计一种基于三维概率模型的分布估计算法,动态确定由底层操作域中各搜索算子所组成的排列(即高层个体),可有效控制和引导整个算法的搜索行为;同时,在底层操作域设计10种有效邻域搜索算子,并加入重升温操作的模拟退火机制作为问题解(即底层个体)的接受准则,有利于在问题解空间中执行深入搜索.仿真实验结果表明,所提出的算法在大多数测试集上优于近年来用于求解类似问题的算法,验证了所提出算法的有效性.

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

学科分类：12[管理学] 1201[管理学-管理科学与工程类] 081104[081104] 08[工学] 0835[0835] 0811[工学-水利类] 0812[工学-测绘类] 

D　O　I：10.7540/j.ynu.20220439

馆 藏 号：203125843...