关键词: 电动车辆路径问题, 动态需求, 节约里程算法, 禁忌搜索算法

Abstract: 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.

Key words: electric vehicle routing problem, dynamic demand, Clarke and Wright's saving method, tabu search algorithm