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.2021.8
URN: urn:nbn:de:0030-drops-148776
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/14877/
Go to the corresponding OASIcs Volume Portal

Gaul, Daniela ; Klamroth, Kathrin ; Stiglmayr, Michael

Solving the Dynamic Dial-a-Ride Problem Using a Rolling-Horizon Event-Based Graph

pdf-format:
OASIcs-ATMOS-2021-8.pdf (0.7 MB)

Abstract

In many ridepooling applications transportation requests arrive throughout the day and have to be answered and integrated into the existing (and operated) vehicle routing. To solve this dynamic dial-a-ride problem we present a rolling-horizon algorithm that dynamically updates the current solution by solving an MILP formulation. The MILP model is based on an event-based graph with nodes representing pick-up and drop-off events associated with feasible user allocations in the vehicles. The proposed solution approach is validated on a set of real-word instances with more than 500 requests. In 99.5% of all iterations the rolling-horizon algorithm returned optimal insertion positions w.r.t. the current schedule in a time-limit of 30 seconds. On average, incoming requests are answered within 2.8 seconds.

BibTeX - Entry

@InProceedings{gaul_et_al:OASIcs.ATMOS.2021.8,
  author =	{Gaul, Daniela and Klamroth, Kathrin and Stiglmayr, Michael},
  title =	{{Solving the Dynamic Dial-a-Ride Problem Using a Rolling-Horizon Event-Based Graph}},
  booktitle =	{21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021)},
  pages =	{8:1--8:16},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-213-6},
  ISSN =	{2190-6807},
  year =	{2021},
  volume =	{96},
  editor =	{M\"{u}ller-Hannemann, Matthias and Perea, Federico},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2021/14877},
  URN =		{urn:nbn:de:0030-drops-148776},
  doi =		{10.4230/OASIcs.ATMOS.2021.8},
  annote =	{Keywords: Dial-a-Ride Problem, Ridepooling, Event-Based MILP, Rolling-Horizon, Dynamic Requests}
}

Keywords: Dial-a-Ride Problem, Ridepooling, Event-Based MILP, Rolling-Horizon, Dynamic Requests
Collection: 21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021)
Issue Date: 2021
Date of publication: 27.09.2021

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