articleOperations ResearchMay 31, 2006Closed access

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

JCJean‐François Cordeau

HEC Montréal

Indexed incrossref

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…

Citation impact

666
total citations
FWCI
38.52
Percentile
100%
References
31
Citations per year

Authors

1

Topics & keywords

Topics
Keywords
  • Branch and cut
  • Travelling salesman problem
  • Vehicle routing problem
  • Computer science
  • Integer programming
  • Mathematical optimization
  • Set (abstract data type)
  • Routing (electronic design automation)
No related works found for this paper.

Funding