An exact approach for the multi-depot electric bus scheduling problem with time windows

K. Gkiotsalitis*, C. Iliopoulou, K. Kepaptsoglou

*Corresponding author for this work

Research output: Contribution to journalArticleAcademicpeer-review

31 Citations (Scopus)
75 Downloads (Pure)

Abstract

This study extends the multi-depot vehicle scheduling problem with time windows (MDVSPTW) to the case of electric vehicles which can recharge at charging stations located at any point of the service operation area. We propose a mixed-integer nonlinear model for the electric bus multi-depot vehicle scheduling problem with time windows (EB-MDVSPTW). Our formulation considers not only the operational cost of vehicles, but also the waiting times. In addition, it explicitly considers the capacity of charging stations and prohibits the simultaneous charging of different vehicles at the same charger. Chargers are modeled as task nodes of an extended network and can be placed at any location utilizing the charging infrastructure of a city instead of using only bus-dedicated chargers. Further, we linearize the MINLP formulation of the EB-MDVSPTW by reformulating it to a mixed-integer linear program (MILP) that can be solved to global optimality. Because EB-MDVSPTW is NP-Hard, we also introduce valid inequalities to tighten the search space of the MILP and we investigate the trade-off between the compactness and the tightness of the problem in benchmark instances with up to 30 trips. In the numerical experiments, we show that the valid inequalities reduce the problem's compactness by increasing up to three times the number of constraints, but, at the same time, improve tightness resulting in computational time improvements of up to 73% in 20-trip instances. The implementation of our exact approach is demonstrated in a toy network and in the benchmark instances of Carpaneto et al. (1989).

Original languageEnglish
Pages (from-to)189-206
Number of pages18
JournalEuropean journal of operational research
Volume306
Issue number1
DOIs
Publication statusPublished - 1 Apr 2023

Keywords

  • Charging
  • Electric bus scheduling
  • Exact optimization
  • MDVSPTW
  • Transportation

Fingerprint

Dive into the research topics of 'An exact approach for the multi-depot electric bus scheduling problem with time windows'. Together they form a unique fingerprint.

Cite this