An adaptive large neighborhood search approach for solving the electric vehicle routing problem with time windows

Official URL: http://risc01.sabanciuniv.edu/record=b1589538 (Table of Contents)

The Electric Vehicle Routing Problem with Time Windows (E-VRPTW) is an extension to the well-known Vehicle Routing Problem with Time Windows (VRPTW). Different from VRPTW, the fleet in E-VRPTW consists of electric vehicles (EVs) which have a limited driving range due to their battery charge capacities. Since the battery charge level decreases proportional to the distance traveled, an EV may need to visit recharging stations to have its battery recharged in order to be able to continue servicing the customers along its route. The recharging may take place at any battery level and after the recharging the battery is assumed to be full. Recharging time is proportional to the amount charged. The number of stations is usually small and the stations are dispersed in distant locations, which increases the difficulty of the problem. In this thesis, we propose an Adaptive Large Neighborhood Search (ALNS) method to solve this problem. ALNS is based on the destroy-and-repair framework where at any iteration the existing feasible solution is destroyed by removing some customers and recharging stations from their routes and then repaired by inserting the removed customers to the solution along with the stations when recharging is necessary. Several removal and insertion algorithms are applied by selecting them dynamically and adaptively based on their past performances. The new solution is accepted according to the Simulated Annealing criterion. Our approach combines the removal and insertion mechanisms from the literature with some new mechanisms designed specifically for E-VRPTW. To test the performance of the proposed ALNS we use the instances and benchmark results presented in by Schneider et al (2014). Our computational results show that the proposed method is effective in finding good solutions in reasonable amount of time.