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

Keskin, Merve (2014) An adaptive large neighborhood search approach for solving the electric vehicle routing problem with time windows. [Thesis]

[thumbnail of MerveKeskin_10049790.pdf] PDF
MerveKeskin_10049790.pdf

Download (1MB)

Abstract

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.
Item Type: Thesis
Uncontrolled Keywords: Electric vehicle. -- Large neighborhood search. -- Metaheuristics. -- Recharging. -- Vehicle routing. -- Vehicle routing problem. -- Elektrikli araç. -- Geniş komşuluk arama. -- Metasezgisel. -- Şarj. -- Araç rotalama. -- Araç yönlendirme problemi.
Subjects: T Technology > T Technology (General) > T055.4-60.8 Industrial engineering. Management engineering
Divisions: Faculty of Engineering and Natural Sciences > Academic programs > Industrial Engineering
Faculty of Engineering and Natural Sciences
Depositing User: IC-Cataloging
Date Deposited: 09 Mar 2016 15:36
Last Modified: 26 Apr 2022 10:06
URI: https://research.sabanciuniv.edu/id/eprint/29201

Actions (login required)

View Item
View Item