The electric vehicle routing problem with energy consumption uncertainty

Samuel Pelletier, Ola Jabali, Gilbert Laporte

Research output: Contribution to journalArticlepeer-review

38 Citations (Scopus)

Abstract

Compared with conventional freight vehicles, electric freight vehicles create less local pollution and are thus generally perceived as a more sustainable means of goods distribution. In urban areas, such vehicles must often perform the entirety of their delivery routes without recharging. However, their energy consumption is subject to a fair amount of uncertainty, which is due to exogenous factors such as the weather and road conditions, endogenous factors such as driver behaviour, and several energy consumption parameters that are difficult to measure precisely. Hence we propose a robust optimization framework to take into account these energy consumption uncertainties in the context of an electric vehicle routing problem. The objective is to determine minimum cost delivery routes capable of providing strong guarantees that a given vehicle will not run out of charge during its route. We formulate the problem as a robust mixed integer linear program and solve small instances to optimality using robust optimization techniques. Furthermore, we develop a two-phase heuristic method based on large neighbourhood search to solve larger instances of the problem, and we conduct several numerical tests to assess the quality of the methodology. The computational experiments illustrate the trade-off between cost and risk, and demonstrate the influence of several parameters on best found solutions. Furthermore, our heuristic identifies 42 new best solutions when tested on instances of the closely related robust capacitated vehicle routing problem.

Original languageEnglish
Pages (from-to)225-255
Number of pages31
JournalTransportation Research Part B: Methodological
Volume126
Early online date25 Jun 2019
DOIs
Publication statusPublished - 31 Aug 2019

Keywords

  • City logistics
  • Electric vehicle routing
  • Metaheuristics
  • Robust optimization

ASJC Scopus subject areas

  • Civil and Structural Engineering
  • Transportation

Fingerprint

Dive into the research topics of 'The electric vehicle routing problem with energy consumption uncertainty'. Together they form a unique fingerprint.

Cite this