部分充电策略下的多车型电动汽车车辆路径优化问题研究

Heterogeneous Electric Vehicles Routing Problem under Partial Charging Strategy

为了解决电动汽车使用过程中行驶里程短、充电难的问题,本文构建了带有时间窗、资源约束且允许部分充电的混合整数规划模型。考虑不同车型载重量、固定成本、可变成本、续航里程和充电速率的异质性,模型以多车型配送的单位里程可变成本和车辆使用的固定成本加和为目标函数,设计局部搜索增强的自适应大规模邻域搜索算法进行求解,算法中引入了充电站位置优化方法,通过摧毁算子和重建算子构建配送路径搜索解空间,并使用多种路径内和路径间优化算子进一步寻优。在多组不同规模算例上验证了算法的有效性和收敛性。数值实验结果表明,部分充电策略相较于完全充电策略在顾客规模为50时平均节约成本11.05%,节约成本随算例规模的增加而增加。但是部分充电策略算法收敛速度慢于完全充电策略。在满足约束的情况下,部分充电策略通过延长电动汽车的行驶距离,减少电动汽车使用的数量,可以有效的降低配送成本,在合理的时间内得到较好的求解方案。本研究可为物流企业推广纯电动物流车的实际工作提供指导。

In order to deal with the problem of limited battery capacity,we establish a mixed integer programming model considering partial charging strategy(PCS)with time window and resource constrains.It aims to minimize the fixed and variable costs caused by heterogeneous vehicles.The load capacity,fixed cost,variable cost,battery capacity,and charging rate vary for different types of vehicles.Adaptive large neighborhood search algorithm with an enhanced local search(ALNS-LS)is designed to solve the problem.Power station optimization,multiple intra-route and inter-route operators are applied to facilitate the process.Numerical experiments with different scales are conducted to verify the model and examine the effectiveness of the PCS.The results show that,compared with the full charging strategy(FCS),the averages cost of PCS is 11.05%lower than FCS for 50 customers.In addition,the higher the number of customers,the better the PCS performance.However,the FCS is more efficient than the PCS.The PCS is able to decrease the charging time and can achieve the optimal electric vehicle routing solution within reasonable time.Our study attempts to provide operational level strategies for logistics companies.