A simulation-based heuristic for the electric vehicle routing problem with time windows and stochastic waiting times at recharging stations

Keskin Özel, Merve and Çatay, Bülent and Laporte, Gilbert (2021) A simulation-based heuristic for the electric vehicle routing problem with time windows and stochastic waiting times at recharging stations. Computers and Operations Research, 125 . ISSN 0305-0548 (Print) 1873-765X (Online)

Full text not available from this repository. (Request a copy)

Abstract

The Electric Vehicle Routing Problem with Time Windows and Stochastic Waiting Times at Recharging Stations is an extension of the Electric Vehicle Routing Problem with Time Windows where the electric vehicles (EVs) may wait in a queue before the recharging service starts due to limited number of chargers available at stations. Since the customers and the depot are associated with time windows, long waiting times at the stations in addition to the recharging times may cause disruptions in logistics operations. To solve this problem, we present a two-stage simulation-based heuristic using Adaptive Large Neighborhood Search (ALNS). In the first stage, the routes are determined using expected waiting time values at the stations. While the vehicles are following their tours, upon arrival at the stations, their queueing times are revealed. If the actual waiting time at a station exceeds its expected value, the time windows of the subsequent customers on the route may be violated. In this case, the second stage corrects the infeasible solution by penalizing the time-window violations and late returns to the depot. The proposed ALNS applies several destroy and repair operators adapted for this specific problem. In addition, we propose a new adaptive mechanism to tune the constant waiting times used in finding the first-stage solution. To investigate the performance of the proposed approach and the influence of the stochastic waiting times on routing decisions and costs, we perform an experimental study using both small and large instances from the literature. The results show that the proposed simulation-based solution approach provides good solutions both in terms of quality and of computational time. It is shown that the uncertainty in waiting times may have significant impact on route plans.
Item Type: Article
Uncontrolled Keywords: Queueing; Stochastic Waiting Times; Electric Vehicle Routing Problem; Simulation; Metaheuristics
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: 12 Apr 2021 18:22
Last Modified: 16 Aug 2022 21:19
URI: https://research.sabanciuniv.edu/id/eprint/41381

Actions (login required)

View Item
View Item