A tight formulation for the dial-a-ride problem
Publication date
2024-11-15
Document type
Forschungsartikel
Author
Organisational unit
Scopus ID
Publisher
Elsevier
Series or journal
European Journal of Operational Research
ISSN
Periodical volume
321
Periodical issue
2
First page
363
Last page
382
Peer-reviewed
✅
Part of the university bibliography
✅
Language
English
Keyword
Dial-a-ride problem
Mixed-integer linear programming
Routing
Transportation
Valid inequalities
Abstract
Ridepooling services play an increasingly important role in modern transportation systems. With soaring demand and growing fleet sizes, the underlying route planning problems become increasingly challenging. In this context, we consider the dial-a-ride problem (DARP): Given a set of transportation requests with pick-up and delivery locations, passenger numbers, time windows, and maximum ride times, an optimal routing for a fleet of vehicles, including an optimized passenger assignment, needs to be determined. We present tight mixed-integer linear programming (MILP) formulations for the DARP by combining two state-of-the-art models into novel location-augmented-event-based formulations. Strong valid inequalities and lower and upper bounding techniques are derived to further improve the formulations. We then demonstrate the theoretical and computational superiority of the new models: First, the linear programming relaxations of the new formulations are stronger than existing location-based approaches. Second, extensive numerical experiments on benchmark instances show that computational times are on average reduced by 53.9% compared to state-of-the-art event-based approaches.
Description
This is an open access article under the CC BY license (http://creativecommons.org/licenses/by/4.0/).
Version
Published version
Access right on openHSU
Metadata only access