A multi-stage stochastic integer programming approach for locating electric vehicle charging stations

Ahmed Abdelmoumene Kadri, Romain Perrouault, Mouna Kchaou Boujelben, Céline Gicquel

Research output: Contribution to journalArticlepeer-review

51 Citations (Scopus)

Abstract

Electric vehicles (EVs) represent one of the promising solutions to face environmental and energy concerns in transportation. Due to the limited range of EVs, deploying a charging infrastructure enabling EV drivers to carry out long distance trips is a key step to foster the widespread adoption of EVs. In this paper, we study the problem of locating EV fast charging stations so as to satisfy as much recharging demand as possible within the available investment budget. We focus on incorporating two important features into the optimization problem modeling: a multi-period decision making horizon and uncertainties on the recharging demand in terms of both the number of EVs to recharge and the set of long-distance trips to cover. Our objective is to determine the charging stations to be opened at each time period so as to maximize the expected value of the satisfied recharging demand over the entire planning horizon. To model the problem, we propose a multi-stage stochastic integer programming approach based on the use of a scenario tree to represent the uncertainties on the recharging demand. To solve the resulting large-size integer linear program, we develop two solution algorithms: an exact solution method based on a Benders decomposition and a heuristic approach based on a genetic algorithm. Our numerical results show that both methods perform well as compared to a stand-alone mathematical programming solver. Moreover, we provide the results of additional simulation experiments showing the practical benefit of the proposed multi-stage stochastic programming model as compared to a simpler multi-period deterministic model.

Original languageEnglish
Article number104888
JournalComputers and Operations Research
Volume117
DOIs
Publication statusPublished - May 2020

Keywords

  • Benders decomposition
  • Electric vehicles
  • Facility location problem
  • Genetic algorithm
  • Multi-stage stochastic optimization
  • Scenario tree

ASJC Scopus subject areas

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

Fingerprint

Dive into the research topics of 'A multi-stage stochastic integer programming approach for locating electric vehicle charging stations'. Together they form a unique fingerprint.

Cite this