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 ().