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

106 Citations (SciVal)


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
Early online date8 Aug 2020
Publication statusPublished - 31 Jan 2021

Bibliographical note

Funding Information:
This work was partly supported by the Canadian National Sciences and Engineering Research Council under grant 2015–06189 and by The Scientific and Technical Research Council of Turkey under grant #118M412. These supports are gratefully acknowledged. The authors also thank two anonymous referees for their valuable comments and suggestions.


  • Electric Vehicle Routing Problem
  • Metaheuristics
  • Queueing
  • Simulation
  • Stochastic Waiting Times
  • electric vechicles
  • Sustainability

ASJC Scopus subject areas

  • General Computer Science
  • Modelling and Simulation
  • Management Science and Operations Research


Dive into the research topics of 'A simulation-based heuristic for the electric vehicle routing problem with time windows and stochastic waiting times at recharging stations'. Together they form a unique fingerprint.

Cite this