A Branch-and-Cut Algorithm for the Dial-a-Ride Problem
Top Cited Papers
- 1 June 2006
- journal article
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Operations Research
- Vol. 54 (3), 573-586
- https://doi.org/10.1287/opre.1060.0283
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.Keywords
This publication has 23 references indexed in Scilit:
- A tabu search heuristic for the static multi-vehicle dial-a-ride problemTransportation Research Part B: Methodological, 2003
- 9. VRP with Pickup and DeliveryPublished by Society for Industrial & Applied Mathematics (SIAM) ,2002
- Solving the Asymmetric Travelling Salesman Problem with time windows by branch-and-cutMathematical Programming, 2001
- A Branch & Cut Algorithm for the Asymmetric Traveling Salesman Problem with Precedence ConstraintsComputational Optimization and Applications, 2000
- A branch-and-cut algorithm for the undirected selective traveling salesman problemNetworks, 1998
- Separating capacity constraints in the CVRP using tabu searchEuropean Journal of Operational Research, 1998
- The precedence-constrained asymmetric traveling salesman polytopeMathematical Programming, 1995
- The pickup and delivery problem with time windowsEuropean Journal of Operational Research, 1991
- Improvements and extensions to the Miller-Tucker-Zemlin subtour elimination constraintsOperations Research Letters, 1991
- A Dynamic Programming Solution of the Large-Scale Single-Vehicle Dial-A-Ride Problem with Time WindowsAmerican Journal of Mathematical and Management Sciences, 1986