学习型蚁群算法求解一类复杂两级车辆路径问题  

Learning-based Ant Colony Optimization Algorithm for Solving a Kind of Complex 2-Echelon Vehicle Routing Problem

作　　者：陈雪 胡蓉[1] 王辉 李作成[1] 钱斌[1] 李熠胥 Chen Xue;Hu Rong;Wang Hui;Li Zuocheng;Qian Bin;Li Yixu(School of Information Engineering and Automation,Kunming University of Science and Technology,Kunming 650500,China;Zhaotong Cigarette Factory,Hongta Tobacco Co.,Ltd,Zhaotong 657000,China)

机构地区：[1]昆明理工大学信息工程与自动化学院,云南昆明650500 [2]红塔烟草(集团)有限公司昭通卷烟厂,云南昭通657000

出　　处：《系统仿真学报》2023年第11期2476-2495,共20页Journal of System Simulation

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

摘　　要：针对考虑同时取送货的绿色两级车辆路径问题,以最小化带碳排放成本的总运输成本为优化目标,提出一种结合聚类分解的学习型蚁群优化算法。针对两级问题相互耦合的特点,采用基于距离的聚类算法将原问题分解为一组子问题,提出一种学习型蚁群优化算法对各子问题进行求解,进而获得原问题的解。提出一种考虑问题结构特征的三维概率矩阵作为信息素矩阵,用于学习优质解的优良特征信息,以提高算法的全局搜索能力;提出一种考虑算法行为特征的局部搜索策略,用于学习所设计的六种邻域算子的搜索信息,以提高算法的局部搜索能力。通过仿真实验和算法比较,验证了所提算法的有效性。Aiming at green 2-echelon vehicle routing problem with simultaneous pick-up and delivery,a learning-based ant colony optimization algorithm combined with clustering decomposition is proposed.The objective function to be minimized is total transportation cost wherein carbon emission cost is specially considered.Associated with the mutual coupling features of the 2-echelon vehicle routing problem,we propose a distance-based clustering method to decompose the original problem into a set of sub-problems.Then,a learning-based ant colony optimization algorithm is presented to find the solutions of the sub-problems based on which the solution of the original problem can be obtained.In the algorithm,we introduce a problem-dependent three-dimensional probability matrix to represent pheromone matrix,which is used to learn valuable information about high-quality solutions and improve global search ability.Thereafter,we propose a local search strategy based on the search behavior of the algorithm to learn information about excellent individuals for six dedicated neighborhood search operators,so as to enhance local search ability.Results of numerical experiments and algorithm comparisons demonstrate the effectiveness of the proposed algorithm.

关 键 词：绿色两级车辆路径问题 蚁群优化 聚类分解 学习 三维概率矩阵 同时取送货 

分 类 号：TP391.9[自动化与计算机技术—计算机应用技术]