超启发蚁群优化算法求解带柔性时间窗的绿色两级多周期车辆路径问题  

Hyper-heuristic ant colony optimization algorithm for green two-echelon multi-period vehicle routing problem with flexible time windows

作　　者：郭宁[1,2] 钱斌[1,2] 申秋义 那靖[3] 胡蓉[1,2] 耿言 GUO Ning;QIAN Bin;SHEN Qiu-yi;NA Jing;HU Rong;GENG Yan(Faculty of Information Engineering and Automation,Kunming University of Science and Technology,Kunming 650500,China;The Higher Educational Key Laboratory for Industrial Intelligence and Systems of Yunnan Province,Kunming University of Science and Technology,Kunming 650500,China;Faculty of Mechanical and Electrical Engineering,Kunming University of Science and Technology,Kunming 650500,China)

机构地区：[1]昆明理工大学信息工程与自动化学院,昆明650500 [2]昆明理工大学云南省高校工业智能与系统重点实验室,昆明650500 [3]昆明理工大学机电工程学院,昆明650500

出　　处：《控制与决策》2025年第3期745-754,共10页Control and Decision

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

摘　　要：针对带柔性时间窗的绿色两级多周期车辆路径问题(G2E-MPVRPFTW),建立同时以最小化碳排放量和最大化客户满意度为目标的数学模型,提出一种结合K-means带时间窗聚类(KCTW)的超启发蚁群优化算法(HHACOA)进行求解.首先,根据G2E-MPVRPFTW大规模、多约束、强耦合的复杂特性,采用KCTW将该问题分解为多个子问题,以降低问题的求解复杂度;其次,使用HHACOA求解分解后的各子问题,并将这些子问题的解合并获得原问题G2E-MPVRPFTW的解.HHACOA在高层策略域生成9种邻域操作的不同排列,采用蚁群优化算法(ACOA)对优质排列信息进行学习,并基于重构的转移概率矩阵生成新的排列,以有效引导搜索到达优质解集中的区域;HHACOA在低层问题域利用启发式规则和随机方法生成初始种群,并将高层产生的每个排列作为一种算法,作用于种群中的每个个体,以实现在解空间更多不同区域进行搜索.For dealing with the green two-echelon multi-period vehicle routing problem with flexible time windows(G2E-MPVRPFTW),this paper establishes a mathematical model with the objectives of minimizing the carbon emissions and maximizing the customer satisfaction,and proposes a hyper-heuristic ant colony optimization algorithm(HHACOA)which combines the K-means clustering with time windows(KCTW).Firstly,according to the complex characteristics of the G2E-MPVRPFTW with the large scale,multi constraints,and strong coupling,the KCTW is adopted to decompose the problem into multiple subproblems.Thereby,the complexity of solving the problem is reduced.Secondly,the HHACOA is used to solve the decomposed subproblems,and the solution of the original problem G2E-MPVRPFTW can be obtained by merging the solutions of these subproblems.In the policy domain of the upper layer,the HHACOA generates different permutations of 9 neighborhood operations,and uses the ant colony optimization algorithm(ACOA)to learn high-quality permutation information.Based on the reconstructed transition probability matrix,new permutations are generated to effectively guide the search to reach areas where the high-quality solutions are concentrated.In the problem domain of the lower layer,the HHACOA utilizes the heuristic rules and the random method to generate the initial population,and uses each permutation generated at the upper layer as an algorithm to act on each individual in the population,so as to search more different regions in the solution space.

关 键 词：两级车辆路径问题 多周期 绿色 柔性时间窗 多目标优化 超启发蚁群优化算法 

分 类 号：TP273[自动化与计算机技术—检测技术与自动化装置]