学习型离散排超联赛算法求解带时间窗的绿色多车型两级车辆路径问题
李正雯1
胡蓉1
钱斌1
金怀平2
吕阳1
1.昆明理工大学信息工程与自动化学院,云南昆明650500;昆明理工大学云南省人工智能重点实验室,云南昆明6505002.昆明理工大学信息工程与自动化学院,云南昆明650500
摘要：针对现实中广泛存在的带时间窗的绿色多车型两级车辆路径问题(G2E-HVRP-TW),本文提出一种结合加权K-means算法(WKA)的学习型离散排超联赛算法(LDVPLA)进行求解.首先,根据该问题规模大、约束多的特点,采用WKA将原问题G2E-HVRP-TW分解为一个绿色多车型车辆路径子问题(GHVRP)和一组带时间窗的GHVRP(GHVRP-TW),从而实现两级问题间的部分解耦,以合理缩小搜索空间.然后,利用LDVPLA求解分解后的一系列子问题,并将各子问题的解合并后得到原问题的解.LDVPLA在竞赛阶段将标准排超联赛算法(VPLA)中实数个体更新操作替换为一系列排序操作,使其能够直接在问题离散解空间内执行基于VPLA机制的搜索,可提高搜索效率;在学习阶段构建三维概率矩阵模型合理学习并积累优质解信息,有利于驱动算法较快到达解空间中的优质解区域执行搜索;在淘汰阶段设计一种重启策略,可避免算法过早陷入局部最优.最后,通过在不同规模算例上的仿真实验和算法对比,验证了所提算法的有效性.
关键词：两级车辆路径问题绿色多车型时间窗加权K-means算法排超联赛算法
资助基金：国家自然科学基金(61963022)国家自然科学基金(62173169)云南省基础研究重点项目(202201AS070030)
论文发表日期：2023-03-28
在线出版日期：2025-08-15（本平台首次上网日期，不代表文献的发表时间）
页数：9( 549-557 )
英文信息