混合文化基因算法求解带容量约束的电动车辆路径问题

针对带容量约束的电动车辆路径问题(CEVRP),以最小化总行驶里程为优化目标,提出一种混合文化基因求解算法。将原问题分解为两个子问题,即带容量约束的车辆路径问题和固定路径下的车辆充电问题。针对该问题设计双层解码,上层解码采用分割算法获得满足容量约束的路径,下层采用移除启发式算法获得可行的充电路径。首先,利用k最近邻算法获得多样性的编码个体,再采用双层解码获得优良初始种群;然后,对种群执行变邻域搜索改进个体的解质量;接着,使用精英保留策略对精英个体继续采用三种局部强化策略,对带容量约束的车辆路径进行局部搜索,对车辆路径中的充电站和客户点进行优化调整;最后,采用两种选择操作并使用顺序交叉在不同解之间共享信息。实验部分采用国际竞赛中的CEVRP测试数据集,将所提算法与对比算法进行比较,实验结果表明,所提算法在中小规模实例上优于对比算法,在大规模实例上也能得到满意解,并且具有良好的稳定性。