This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via HighWire Citing Articles via Google Scholar Google Scholar Articles by Cordeau, J.-F. Search for Related Content

A Branch-and-Cut Algorithm for the Dial-a-Ride Problem

HEC Montréal, 3000 chemin de la Côte-Sainte-Catherine, Montréal, Quebec, Canada H3T 2A7
jean-francois.cordeau{at}hec.ca

In the dial-a-ride problem, users formulate requests for transportation from a specific origin to a specific destination. Transportation is carried out by vehicles providing a shared service. The problem consists of designing a set of minimum-cost vehicle routes satisfying capacity, duration, time window, pairing, precedence, and ride-time constraints. This paper introduces a mixed-integer programming formulation of the problem and a branch-and-cut algorithm. The algorithm uses new valid inequalities for the dial-a-ride problem as well as known valid inequalities for the traveling salesman, the vehicle routing, and the pick-up and delivery problems. Computational experiments performed on randomly generated instances show that the proposed approach can be used to solve small to medium-size instances.

Subject classifications: transportation; vehicle routing; programming; cutting plane.
History: Received September 2003; revision received August 2004; accepted March 2005.

This article has been cited by other articles:

				S. Ropke and J.-F. Cordeau Branch and Cut and Price for the Pickup and Delivery Problem with Time Windows Transportation Science, August 1, 2009; 43(3): 267 - 286. [Abstract] [PDF]

				T. Hanne, T. Melo, and S. Nickel Bringing Robustness to Patient Flow Management Through Optimized Patient Transports in Hospitals Interfaces, May 1, 2009; 39(3): 241 - 255. [Abstract] [PDF]

				D. Espinoza, R. Garcia, M. Goycoolea, G. L. Nemhauser, and M. W. P. Savelsbergh Per-Seat, On-Demand Air Transportation Part I: Problem Description and an Integer Multicommodity Flow Model Transportation Science, August 1, 2008; 42(3): 263 - 278. [Abstract] [PDF]