结合聚类分解的增强蚁群算法求解复杂绿色车辆路径问题

摘要：

针对带时间窗的低能耗多车场多车型车辆路径问题(Low-energy-consumption multi-depots heterogeneous-fleet vehicle routing problem with time windows,LMHFVPR TW),提出一种结合聚类分解策略的增强蚁群算法(Enhanced ant colony optimization based on clustering decomposition,EACO_CD)进行求解.首先,由于该问题具有强约束、大规模和NP-Hard等复杂性,为有效控制问题的求解规模并合理引导算法在优质解区域搜索,根据问题特点设计两种基于K-means的聚类策略,将LMHFVPR_TW合理分解为一系列带时间窗的低能耗单车场单车型车辆路径子问题(Low-energy-consumption vehicle routing problem with time windows,LVRP_TW);其次,本文提出一种增强蚁群算法(Enhanced ant colony optimization,EACO)求解分解后的各子问题(LVRP_TW),进而获得原问题的解.EACO不仅引入信息素挥发系数控制因子进一步动态调节信息素挥发系数,从而有效控制信息素的挥发以提高算法的全局搜索能力,而且设计基于4种变邻域操作的两阶段变邻域局部搜索(Two-stage variable neighborhood search,TVNS)来增强算法的局部搜索能力.最后,在不同规模问题上的仿真和对比实验验证了所提EACO_CD的有效性.

关键词：低能耗车辆路径问题、多车场多车型、时间窗、聚类分解、增强蚁群算法

所属期刊栏目：48

分类号：TP391.9;U492.22;U661.33+6

资助基金：国家自然科学基金;国家自然科学基金;云南省应用基础研究计划重点项目

在线出版日期：2023-01-05（万方平台首次上网日期，不代表论文的发表时间）

页数：共18页

页码：3006-3023