Creative Commons Attribution 4.0 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: https://drops.dagstuhl.de/opus/volltexte/2021/14877/
Gaul, Daniela ; Klamroth, Kathrin ; Stiglmayr, Michael
Solving the Dynamic Dial-a-Ride Problem Using a Rolling-Horizon Event-Based Graph
| pdf-format: |
|
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 | |
| Seminar: | 21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021) | |
| Issue date: | 2021 | |
| Date of publication: | 27.09.2021 |
