时间窗约束下多车型电动车辆路径问题建模与优化

摘要

针对带时间窗的多车型电动车辆路径问题(heterogeneous electric vehicle routing problem with time windows,HEVRPTW)，综合考虑客户需求差异、车辆异构特性和充电约束等因素，构建以总行驶成本最小化为目标的混合整数规划模型，并提出结合层次聚类机制的混合变邻域搜索算法(hybrid variable neighborhood search,HVNS)进行求解。该算法采用层次聚类机制对客户节点进行空间划分，并结合贪婪算法生成初始解；在局部搜索阶段，整合单点插入、两点交换、两段交换及2–opt等多种邻域操作算子，并引入充电站优化策略优化路径选择。基于标准测试案例通过与Gurobi求解器和遗传算法(genetic algorithm,GA)进行仿真对比实验，并对电池容量、充电时间、时间窗宽度、车辆数量等关键参数进行敏感性分析。结果表明：HVNS能在更短时间内获得与Gurobi相近的优质解，验证了模型的正确性及其在不同规模问题求解中的优越性能；与GA相比，HVNS在求解质量上实现了10%～20%的提升，同时在稳定性和收敛性方面更优；通过参数优化确定了最佳配置方案(电池容量为150 kWh、充电时间为45 min、时间窗宽度为90 min、车辆数量为8辆)，实现了总行驶成本最小化与客户满意度最大化的平衡。研究结果验证了HVNS是求解HEVRPTW的有效方法，本研究为物流企业电动车辆路径优化提供了科学的决策支持工具。

关键词

电动车辆路径问题 / 时间窗约束 / 多车型 / 层次聚类算法 / 变邻域搜索算法 / 充电策略优化 / 物流配送 / 智能算法