A New Formulation for the Dial-a-Ride Problem

Yannik Rist () and Michael A. Forbes ()
Additional contact information
Yannik Rist: School of Maths and Physics, University of Queensland, St. Lucia, Queensland 4072, Australia
Michael A. Forbes: School of Maths and Physics, University of Queensland, St. Lucia, Queensland 4072, Australia

Transportation Science, 2021, vol. 55, issue 5, 1113-1135

Abstract: This paper proposes a new mixed integer programming formulation and branch and cut (BC) algorithm to solve the dial-a-ride problem (DARP). The DARP is a route-planning problem where several vehicles must serve a set of customers, each of which has a pickup and delivery location, and includes time window and ride time constraints. We develop “restricted fragments,” which are select segments of routes that can represent any DARP route. We show how to enumerate these restricted fragments and prove results on domination between them. The formulation we propose is solved with a BC algorithm, which includes new valid inequalities specific to our restricted fragment formulation. The algorithm is benchmarked on existing and new instances, solving nine existing instances to optimality for the first time. In comparison with current state-of-the-art methods, run times are reduced between one and two orders of magnitude on large instances.

Keywords: transportation; vehicle routing; dial-a-ride problem; branch and cut; valid inequalities (search for similar items in EconPapers)
Date: 2021
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/trsc.2021.1044 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ortrsc:v:55:y:2021:i:5:p:1113-1135

Access Statistics for this article

More articles in Transportation Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().