基于两阶段求解策略的动态电动车辆路径优化研究

由于政府对新能源汽车的补贴政策和市区对燃油车限行政策的实时,越来越多的物流公司在城市配送中广泛采用电动汽车。然而,电动车续航里程受限,需要在途充电或者换电,同时客户需求的动态性以及充/换电设施的排队等现实因素也应该被考虑。为此,提出了分阶段策略求解动态电动车辆路径优化问题,并建立了两阶段的EVRP模型。其中第一阶段针对静态客户建立了静态EVRP模型,第二阶段在设计了换电站及动态客户插入策略的基础上,建立了动态EVRP模型以路径更新策略。最后,设计改进的CW-TS混合启发式算法来求解静态模型,设计贪婪算法求解动态模型。实验结果表明,模型与算法具有较好的适用性和有效性。

Dynamic Electric Vehicle Routing Problem Based on Two-stage Solution Strategy

As electric vehicles are subsidized by the government and are not restricted in urban areas, as well as their energy-saving, environmentally friendly, and low-noise characteristics, more and more logistics companies have begun to use electric vehicles for logistics distribution, such as Jd Logistics, SF Express, China Post and other enterprises. However, different from traditional fuel vehicles, in order to ensure the smooth completion of the distribution task, electric vehicles usually need to charge or swap battery on the way due to their range limitations, which will increase the time cost and route cost. It is necessary to develop a reasonable charging/swapping strategy to ensure minimum cost. Some realistic factors in the actual distribution cannot be ignored. (1)Dynamic demand of customers. The order of customers may change during the delivery process, and whether enterprises can make rapid response to improve customer experience on the basis of ensuring the economy will become crucial. (2)Congestion at charging/swapping stations. The number and density of public charging/swapping facilities are not enough, which can easily lead to congestion and increase the time cost. How to make a reasonable distribution plan based on the current charging/swapping facilities is the key to the logistics distribution of electric vehicles. Therefore, the two-stage strategy is used to research the dynamic electric vehicle routing problem. The first stage is static scheduling. The enterprise plans a delivery route for the initial static customer order, the vehicles start from the distribution center at the initial time, visit the customers in turn according to this route, and starts to receive new orders, and sets a certain period of time interval. The second stage is dynamic scheduling. All dynamic customer information is known during this period, and the dynamic network can be converted to a static network. Meanwhile, the system will insert the corresponding dynamic customer according to the current vehicle, so as to complete the path update. Based on the phased solution strategy, static EVRP mathematical model and dynamic EVRP mathematical model are established with the objective function of minimizing the routing cost and vehicle usage cost, and an improved CW-TS hybrid heuristic algorithm and greedy algorithm are designed to solve the models at each stage. The validity and feasibility of the proposed algorithm are verified by the designed instances respectively. The results show that the proposed algorithm can obtain a satisfactory solution in a reasonable time.