License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/OASIcs.ATMOS.2023.14
URN: urn:nbn:de:0030-drops-187753
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/18775/
Go to the corresponding OASIcs Volume Portal

de Bruin, Philip ; van den Akker, Marjan ; Hoogeveen, Han ; van Kooten Niekerk, Marcel

Scheduling Electric Buses with Stochastic Driving Times

pdf-format:
OASIcs-ATMOS-2023-14.pdf (2 MB)

Abstract

To try to make the world more sustainable and reduce air pollution, diesel buses are being replaced with electric buses. This leads to challenges in scheduling, as electric buses need recharging during the day. Moreover, buses encounter varying traffic conditions and passenger demands, leading to delays. Scheduling electric buses with these stochastic driving times is also called the Stochastic Vehicle Scheduling Problem. The classical approach to make a schedule more robust against these delays, is to add slack to the driving time. However, this approach doesn't capture the variance of a distribution well, and it doesn't account for dependencies between trips. We use discrete event simulation in order to evaluate the robustness of a schedule. Then, to create a schedule, we use a hybrid approach, where we combine integer linear programming and simulated annealing with the use of these simulations. We show that with the use of our hybrid algorithm, the punctuality of the buses increase, and they also have a more timely arrival. However, we also see a slight increase in operating cost, as we need slightly more buses compared to when we use deterministic driving times.

BibTeX - Entry

@InProceedings{debruin_et_al:OASIcs.ATMOS.2023.14,
  author =	{de Bruin, Philip and van den Akker, Marjan and Hoogeveen, Han and van Kooten Niekerk, Marcel},
  title =	{{Scheduling Electric Buses with Stochastic Driving Times}},
  booktitle =	{23rd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2023)},
  pages =	{14:1--14:19},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-302-7},
  ISSN =	{2190-6807},
  year =	{2023},
  volume =	{115},
  editor =	{Frigioni, Daniele and Schiewe, Philine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2023/18775},
  URN =		{urn:nbn:de:0030-drops-187753},
  doi =		{10.4230/OASIcs.ATMOS.2023.14},
  annote =	{Keywords: Electric Vehicle Scheduling Problem, Simulated Annealing, Hybrid Algorithm, Simulation, Stochastic Driving Times}
}

Keywords: Electric Vehicle Scheduling Problem, Simulated Annealing, Hybrid Algorithm, Simulation, Stochastic Driving Times
Collection: 23rd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2023)
Issue Date: 2023
Date of publication: 31.08.2023

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI