Partial recharge strategies for the electric vehicle routing problem with time windows

Keskin, Merve and Çatay, Bülent (2015) Partial recharge strategies for the electric vehicle routing problem with time windows. [Working Paper / Technical Report] Sabanci University ID:UNSPECIFIED

[thumbnail of WP_EVRPTW-Partial_Recharge_KeskinCatay.pdf] PDF
WP_EVRPTW-Partial_Recharge_KeskinCatay.pdf

Download (362kB)

Abstract

The Electric Vehicle Routing Problem with Time Windows (EVRPTW) is an extension to the well-known Vehicle Routing Problem with Time Windows (VRPTW) where the fleet consists of electric vehicles (EVs). Since EVs have limited driving range due to their battery capacities they may need to visit recharging stations while servicing the customers along their route. The recharging may take place at any battery level and after the recharging the battery is assumed to be full. In this paper, we relax the full recharge restriction and allow partial recharging (EVRPTW-PR) which is more practical in the real world due to shorter recharging duration. We formulate this problem as 0-1 mixed integer linear program and develop an Adaptive Large Neighborhood Search (ALNS) algorithm to solve it efficiently. We apply several removal and insertion mechanisms by selecting them dynamically and adaptively based on their past performances, including new mechanisms specifically designed for EVRPTW and EVRPTW-PR. We test the performance of ALNS by using benchmark instances from the recent literature. The computational results show that the proposed method is effective in finding high quality solutions and the partial recharging option may significantly improve the routing decisions.
Item Type: Working Paper / Technical Report
Uncontrolled Keywords: Electric vehicle; vehicle routing problem with time windows; adaptive large neighborhood search; metaheuristics; partial recharge
Subjects: T Technology > T Technology (General) > T055.4-60.8 Industrial engineering. Management engineering
T Technology > T Technology (General) > T055.4-60.8 Industrial engineering. Management engineering > T57.6-57.97 Operations research. Systems analysis
Divisions: Faculty of Engineering and Natural Sciences > Academic programs > Industrial Engineering
Faculty of Engineering and Natural Sciences
Depositing User: Bülent Çatay
Date Deposited: 08 Dec 2014 09:59
Last Modified: 26 Apr 2022 10:52
URI: https://research.sabanciuniv.edu/id/eprint/26033

Actions (login required)

View Item
View Item