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

Pfeiffer, Christian; Schulz, Arne

doi:10.1007/s00291-021-00656-7

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

Publication date

2021-11-05

Document type

Forschungsartikel

Author

Pfeiffer, Christian

Schulz, Arne

Organisational unit

Institute of Operations Management, University of Hamburg

DOI

10.1007/s00291-021-00656-7

URI

https://openhsu.ub.hsu-hh.de/handle/10.24405/22179

Scopus ID

2-s2.0-85118583009

Publisher

Springer Science and Business Media

Series or journal

OR Spectrum

ISSN

0171-6468

Periodical volume

44

Periodical issue

1

First page

87

Last page

119

Part of the university bibliography

Nein

Language

English

Keyword

Adaptive large neighbourhood search

Demand responsive transport

Dial-a-ride

Dynamic programming

Abstract

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.

Description

This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/.

Cite as

Pfeiffer, C., Schulz, A. An ALNS algorithm for the static dial-a-ride problem with ride and waiting time minimization. OR Spectrum 44, 87–119 (2022). https://doi.org/10.1007/s00291-021-00656-7

Version

Published version

Access right on openHSU

Metadata only access