现代电子技术2025，Vol.48Issue(7)：177-186,10.DOI:10.16652/j.issn.1004-373x.2025.07.025
混合文化基因算法求解带容量约束的电动车辆路径问题
Hybrid memetic algorithm for solving capacitated electric vehicle routing problem
摘要
Abstract
For the capacitated electric vehicle routing problem(CEVRP),a hybrid memetic algorithm(HMA)is proposed to solve the problem with the optimization objective of minimizing the total distance.The original problem is decomposed into two subproblems,i.e.,capacitated vehicle routing problem and charging problem of vehicles with fixed routes.A two-layer decoding is designed for the problems,with the upper decoding using the split algorithm to obtain routes that satisfy the capacity constraints,and the lower decoding using the removal heuristic algorithm to obtain feasible charging routes.Firstly,diverse coding individuals are obtained by k-nearest neighbors(kNN),and then the two-layer decoding is used to obtain a good initial population.Then,a variable neighborhood search(VNS)is performed on the population to further improve the solution quality of individuals.Next,an elite retention strategy is used,and three local reinforcement strategies are used for the elite individuals:a local search strategy is performed for the capacitated vehicle routing,the charging stations and the customer convergence points in the routing are optimized and adjusted.Finally,two selection operations are adopted,and the information is shared among different solutions by sequential crossover.The proposed algorithm is compared with the contrast algorithms by the CEVRP test dataset in the international competition.The experimental results show that the proposed algorithm is superior to the contrast algorithms on small and medium-scale instances,and can also get satisfactory solutions on large-scale instances,and has good stability.关键词
电动车辆路径问题/混合文化基因算法/k最近邻/变邻域搜索/局部搜索/精英保留策略Key words
electric vehicle routing problem/HMA/kNN/VNS/local search/elite retention strategy分类
信息技术与安全科学引用本文复制引用
骆维,陈仕军,吴华伟..混合文化基因算法求解带容量约束的电动车辆路径问题[J].现代电子技术,2025,48(7):177-186,10.基金项目
国家自然科学基金项目(71501064) （71501064）
襄阳市科技计划湖北隆中实验室专项资助研究(2024KF-22) （2024KF-22）
湖北文理学院科研能力培育基金科技创新团队项目(2020kypytd006) （2020kypytd006）
湖北文理学院研究生创新计划项目(YCX202421) （YCX202421）
