多车场多车型电动汽车路径优化研究

张惠珍，姜 晶

（上海理工大学 管理学院，上海 200093）

0 引言

车辆路径问题（Vehicle Routing Problem，VRP）作为一个经典的NP-hard 问题，研究最早开始于20 世纪50 年代末［1］。VRP 问题如今已不是单纯的理论研究［2-6］，所需要考虑的因素越来越多，因此根据其特性可将其分为很多种，其中，开闭合车辆路径问题、有容量（比如配送中心、车辆）约束的车辆路径问题、带时间窗的车辆路径问题、考虑周期性的车辆路径问题、多配送中心或单配送中心的车辆路径问题、考虑货物类别和客户满意度的车辆路径问题、新能源汽车车辆路径问题等是目前比较常见的车辆路径问题。随着现代物流业的崛起，新型的VRP 问题不断涌现，使其更具有研究价值和现实意义。揭婉晨等［7］用精确算法求解了多车型电动车车辆路径问题；文展等［8］使用改进的粒子群算法求解带时间窗的车辆路径问题，通过对垃圾回收运输实例的分析，说明相比其他算法，改进后的粒子群算法能够更有效地减少路径距离；孔继利等［9］根据汽车的能源消耗和污染情况研究绿色车辆路径问题；辜勇等［10］通过将多配送中心转换成单配送中心的方式，并且使用三阶段算法求解带时间窗的多中心半开放式车辆路径混合问题，能够高效解决大规模的多配送中心路径问题；Yu 等［11］在CVRP 的基础上研究了通过第三方物流参与的开放式选址车辆路径问题（Open Vehicle Routing Problem，OVRP），其与CVRP 的不同之处在于车辆在服务完所有客户之后，不用返回配送中心，并提出一种基于模拟退火的算法求解该OLRP 问题，该算法可求解最多318 个客户、4 个配送中心的车辆路径问题；……