The Electric Vehicle Routing Problem With Backhauls,Time Windows And Recharging Stations

Recent development of e-commerce has accelerated the development of logistics.Frequent logistics and distribution activities have a negative impact on the ecological environment.In response to national policies and regulations concerning the emission of greenhouse gases,logistics companies are planning to use electric vehicles for last-mile deliveries.However,the limited battery capacity of electric vehicles may make detours to recharging stations and long recharging time necessary.Avoiding inefficient vehicle routes with long detours in the route planning is the key to sustain the competitiveness of electric vehicles compared to conventional vehicles.Motivated by Global Optimization Challenge hosted by JD Logistics,the logistics department of JD.com,which is one of the logistics company in China,we investigate the Electric Vehicle Routing Problem with Backhauls,Time Windows and Recharging Stations(E-VRPBTW)considering heterogeneous fleet and multiple trips.We model the problem to determine fleet composition and the actual vehicle routes including the choice of recharging stations and recharging times with minimizing total cost.There are two types of customers in the problem:pickups(backhauls)and deliveries(linehauls).The available vehicle types differ in their weight and volume capacity,battery size,acquisition cost and unit transportation cost.Furthermore,time window constraints require that a customer must be serviced within the given time window.Besides,we consider multiple trips in the route of a vehicle so that it can return to the depot multiple times.We present a hybrid heuristic that combines a variable neighborhood search algorithm with a local search heuristic.Considering the characteristics of the electric vehicles,we design route operators that can move customers together with recharging stations.Besides,a label setting procedure is used to optimize the recharging decisions.Computational experiments performed on test instances provided by JD Logistics demonstrate the high performance of the heuristic proposed.