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

Merve Keskin, Bülent Çatay, Gilbert Laporte

Research output: Contribution to journalArticlepeer-review

8 Citations (Scopus)

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.

Original languageEnglish
Article number105060
JournalComputers and Operations Research
Volume125
Early online date8 Aug 2020
DOIs
Publication statusPublished - 31 Jan 2021

Keywords

  • Electric Vehicle Routing Problem
  • Metaheuristics
  • Queueing
  • Simulation
  • Stochastic Waiting Times

ASJC Scopus subject areas

  • Computer Science(all)
  • Modelling and Simulation
  • Management Science and Operations Research

Cite this