基于混合遗传搜索求解载重约束的电动车辆路径问题  

A Hybrid Genetic Search Algorithm for Capacitated Electric Vehicle Routing Problem

作　　者：金东遥 刘敏[1,2] 朱烨娜 赵肄江 Jin Dongyao;Liu Min;Zhu Yena;Zhao Yijiang(School of Computer Science and Engineering,Hunan University of Science and Technology,Xiangtan 411201,China;Hunan Key Laboratory for Service Computing and Novel Software Technology,Xiangtan 411201,China)

机构地区：[1]湖南科技大学计算机科学与工程学院,湖南湘潭411201 [2]服务计算与软件服务新技术湖南省重点实验室,湖南湘潭411201

出　　处：《系统仿真学报》2024年第11期2528-2541,共14页Journal of System Simulation

基　　金：国家自然科学基金(41871320);湖南省教育厅科学研究重点项目(22A0341);湖南省教育厅项目(18K060)。

摘　　要：载重约束的电动车辆路径问题(capacitated electric vehicle routing problem,CEVRP)是物流配送中的一种NP困难的组合优化问题,要求满足车辆的载重和电量约束条件,最小化总配送距离。提出一种混合遗传搜索算法来解决CEVRP,将其分解为两个子问题:载重约束的车辆路径问题和固定路径车辆充电问题。设计了双层染色体结构的编码方案,表示两个子问题的决策变量。采用Split操作生成满足载重约束的车辆路径,使用Relocate、2-Opt、2-Opt^(*)、SWAP和SWAP^(*)邻域搜索算子对其进行局部优化;提出一种基于回溯的充电策略,将合适的充电站编号插入车辆路径,以满足电量约束。本文算法与五种方法实验比较的结果表明,本文算法在多数CEVRP测试问题上能找到比其它方法更好的解,尤其适合于求解大规模的CEVRP。The capacitated electric vehicle routing problem(CEVRP)is an NP-hard combinatorial optimization problem in logistics distribution,aiming to minimize the total delivery distance of electric vehicles while satisfying carrying capacity and battery charge constraints.A hybrid genetic search algorithm is proposed to solve CEVRP by decomposing it into two subproblems:capacitated vehicle routing problem(CVRP)and fixed-route vehicle charging problem(FRVCP).A coding scheme with a two-layer chromosome structure is designed to represent the decision variables of these two subproblems.A Split operation is employed to generate vehicle routes for solving CVRP,and five neighborhood search operators,including Relocate,2-Opt,2-Opt^(*),SWAP,and SWAP^(*),are adopted to perform local optimization on the routes.To solve the FRVCP,a backtracking-based charging strategy is proposed to insert the appropriate charging station number into the routes.The proposed algorithm is compared with five methods on CEVRP benchmark instances.Experimental results show that the proposed algorithm can find better solutions than the other methods in most instances and is especially suitable for solving large-scale CEVRP.

关 键 词：电动车辆路径问题 组合优化 混合遗传搜索 充电策略 邻域搜索 

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