2026-07-26T03:28:52Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:14877 2024-03-06T10:31:35Z ddc:004 open_access

Solving the Dynamic Dial-a-Ride Problem Using a Rolling-Horizon Event-Based Graph Gaul, Daniela Klamroth, Kathrin Stiglmayr, Michael Dial-a-Ride Problem Ridepooling Event-Based MILP Rolling-Horizon Dynamic Requests 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Daniela Gaul and Kathrin Klamroth and Michael Stiglmayr 2021 Is Part Of OASIcs, Volume 96, 21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/OASIcs.ATMOS.2021.8 urn:nbn:de:0030-drops-148776 https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2021.8 eng https://creativecommons.org/licenses/by/4.0/legalcode