TY  - THES
AB  - The dial-a-ride problem (DARP) consists of two interrelated tasks: on the one hand, a series of transport requests defined by origin, destination, number of seats as well as time windows and ride time need to be assigned to a set of vehicles routes and on the other hand, vehicle schedules need to be computed, both while minimizing a given objective function. State-of-the-art MILP formulations for the DARP are based on binary variables which indicate whether two locations are visited directly after each other. In contrast to these location-based formulations, we propose the concept of event-based modeling. In the resulting event-based (EB) formulation, capacity, pairing and precedence constraints are implicitly encoded. We show that this formulation outperforms the location-based formulations from the literature. Next, the EB MILP is combined with a location-based formulation into a location-augmented-event-based (LAEB) MILP, whose superiority is proven theoretically and computationally. Under the assumption that time windows imply a unique pairwise ordering of locations and other conditions, the LAEB formulation is integral. Ultimately, the concept of event-based modeling is transferred to the dynamic DARP by iteratively solving the EB formulation in a rolling-horizon algorithm, resulting in optimal insertion positions in 99.5% of all iterations on real-life instances.
AU  - Gaul, Daniela
CY  - Wuppertal
DA  - 2023
DO  - 10.25926/BUW/0-303
DP  - Bergische Universität Wuppertal
LA  - eng
N1  - Tag der Verteidigung: 18.03.2024
N1  - Bergische Universität Wuppertal, Dissertation, 2024
PB  - Veröffentlichungen der Universität
PY  - Dezember 2023
T2  - Mathematik und Informatik
TI  - Exact and Heuristic Methods for Dial-a-Ride Problems
UR  - https://nbn-resolving.org/urn:nbn:de:hbz:468-2-2299
Y2  - 2024-11-20T16:34:22
ER  -