An ALNS algorithm for the static dial-a-ride problem with ride and waiting time minimization

Artikel

The paper investigates the static dial-a-ride problem with ride and waiting time minimization. This is a new problem setting of significant practical relevance because several ride-sharing providers launched in recent years in large European cities. In contrast to the standard dial-a-ride problem, these providers focus on the general public. Therefore, they are amongst others in competition with taxis and private cars, which makes a more customer-oriented objective necessary. We present an adaptive large neighbourhood search (ALNS) as well as a dynamic programming algorithm (DP), which are tested in comprehensive computational studies. Although the DP can only be used for a single tour and, due to the computational effort, as a restricted version or for small instances, the ALNS also works efficiently for larger instances. The results indicate that ride-sharing proposals may help to solve the trade-off between individual transport, profitability of the provider, and reduction of traffic and pollution.

Angaben zum Objekt

• Sprache: Englisch

Verweise und Beziehungen

• Erschienen in: Journal: OR Spectrum ; ISSN: 1436-6304 ; Volume: 44 ; Year: 2021 ; Issue: 1 ; Pages: 87-119 ; Berlin, Heidelberg: Springer

Klassifikation und Themen

• Klassifikation: Management
• Thema: Demand responsive transport ; Dial-a-ride ; Adaptive large neighbourhood search ; Dynamic programming

Beteiligte, Orts- und Zeitangaben

• Ereignis: Geistige Schöpfung
• (wer): Pfeiffer, Christian ; Schulz, Arne
• Ereignis: Veröffentlichung
• (wer): Springer
• (wo): Berlin, Heidelberg
• (wann): 2021

Weitere Informationen

• DOI: doi:10.1007/s00291-021-00656-7
• Letzte Aktualisierung: 10.03.2025, 11:41 MEZ