We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
A Branch-and-Cut Algorithm for the Dial-a-Ride Problem.
- Authors
Cordeau, Jean-François
- Abstract
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.
- Subjects
SHUTTLE services; TRANSPORTATION; MANAGEMENT science; PROBLEM solving; INTEGER programming; ALGORITHMS
- Publication
Operations Research, 2006, Vol 54, Issue 3, p573
- ISSN
0030-364X
- Publication type
Article
- DOI
10.1287/opre.1060.0283