Abstract: The electric vehicles powered by batteries can effectively reduce exhaust pollution and save environment harness cost, which has attracted attention and application in logistics field. The maximum driving range of an electric vehicle is limited by the capacity of the battery, and it is necessary to charge the vehicle at the charging station during driving. Secondly, the choice of a charging station will affect the distribution path of electric vehicles. The shortage of charging stations results in electric vehicles being forced to detour to the charging sites. Thirdly, the charge needed by the electric vehicle at the charging station is dynamic, which is related to the battery remaining capacity and the subsequent distribution route of the vehicle. The charge and battery status of the electric vehicle also directly affect the charging time. The electric vehicle routing problem is studied which aims to reduce the operational cost of logistics enterprises with the consideration of charging time and battery consumption cost. The problem is formulated as an integer programming model. The cost of battery loss is added to vehicle routing problem for the first time, and the distance traveled by vehicle in the state of deep discharge is taken as the optimization object. The battery charge rate used in this article is no longer a constant value, but a function related to the current state of the battery. The charging time depends not only on the battery status of the vehicle when it arrives at the charging station and the vehicle's subsequent delivery schedule, but also on the trade-off between the cost of charging time and the opportunity cost of deep discharge driving. A four-phase heuristic called MCWIGALNS is proposed to solve the problem. In the first phase, an initial routing plan is generated with a modified Clarke and Wright Saving heuristic, leading to the battery charging stations (BCSs) selection subproblem, which is then solved by the iterated greedy heuristic in the second phase. The iterated greedy heuristic algorithm first removes all the existing charging sites, and then arranges the lowest-cost charging strategy according to the existing path strategy. In the third phase, the vehicle routes resulting from the selection subproblem are determined by applying an adaptive large neighborhood search heuristic with several new neighborhood structures. Through the iterative of deleting part of the customer's point from the current path and re-putting it into the path according to the predetermined rule, a new solution is searched within the larger neighborhood scale. By exchanging the information of the charging and path strategy, the algorithm can make the feasible solution approach the optimal solution gradually in the iterative process. At the end of MCWIGALNS, the solution is further improved by a split procedure. The BCSs selection and the vehicle routing stages are alternated iteratively. Compared with the MIP solver of CPLEX on small-size instances, the MCWIGALNS can solve the problem within a shorter computing time and get reasonable solutions. Furthermore, a parameter analysis is systemically conducted for comparing two models. The one with the consideration of charge time and battery consumption cost is able to significantly reduce the total operation cost. MCWIGALNS searches the solution space more efficiently and produces better solutions than existing heuristic algorithms on the medium and large instances. To sum up, MCWIGALNS is a time-saving and stable algorithm to provide reference and help on the electric vehicle routing problem for green logistics.

Key words: electric vehicles, charging time, deep discharge, clarke and wright saving heuristic, adaptive large neighborhood search