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

作者：金东遥; 刘敏^*; 朱烨娜; 赵肄江

来源：系统仿真学报, 2023, 1-13.

DOI：10.16182/j.issn1004731x.joss.23-0863

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

载重约束的电动车辆路径问题(capacitated electric vehicle routing problem， CEVRP)是物流配送中的一种NP困难的组合优化问题，要求满足车辆的载重和电量约束条件，最小化总配送距离。提出一种混合遗传搜索算法来解决CEVRP，将其分解为两个子问题：(1)载重约束的车辆路径问题；(2)固定路径车辆充电问题。设计了双层染色体结构的编码方案，表示两个子问题的决策变量。采用Split操作生成满足载重约束的车辆路径，并使用Relocate、2-Opt、2-Opt*、SWAP和SWAP*邻域搜索算子对其进行局部优化；此外，提出一种基于回溯的充电策略，将合适的充电站编号插入车辆路径，以满足电量约束。最后，将提出的算法与五种方法进行实验比较，结果表明，提出的算法在多数CEVRP测试问题上能找到比其它方法更好的解，尤其适合于求解大规模的CEVRP。

• 单位
  湖南科技大学