Checking the Feasibility of Dial-a-Ride Instances Using Constraint Programming

Gerardo Berbeglia (), Gilles Pesant () and Louis-Martin Rousseau ()
Additional contact information
Gerardo Berbeglia: HEC Montréal, Montréal H3T 2A7, Canada
Gilles Pesant: Département de Génie Informatique et Génie Logiciel, École Polytechnique de Montréal, Montréal H3C 3A7, Canada
Louis-Martin Rousseau: Département de Mathématiques et de Génie Industriel, École Polytechnique de Montréal, Montréal H3C 3A7, Canada

Transportation Science, 2011, vol. 45, issue 3, 399-412

Abstract: In the dial-a-ride problem (DARP), a fleet of vehicles must serve transportation requests made by users that need to be transported from an origin to a destination. In this paper we develop the first exact algorithm which is able to either efficiently prove the infeasibility or to provide a feasible solution. Such an algorithm could be used in a dynamic setting for determining whether it is possible or not to accept an incoming request. The algorithm includes solution space reduction procedures, and filtering algorithms for some DARP relaxations. Computational results show that the filtering algorithms are effective and that the resulting algorithm is advantageous on the more constrained instances.

Keywords: dial-a-ride problem; algorithms; partial routes; scheduling; dynamic programming; constraint programming (search for similar items in EconPapers)
Date: 2011
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (13)

Downloads: (external link)
http://dx.doi.org/10.1287/trsc.1100.0336 (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:45:y:2011:i:3:p:399-412

Access Statistics for this article

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