A Branch-and-Cut Algorithm for the
Canada Research Chair in Distribution Management, HEC Montréal
3000, chemin de la Côte-Sainte-Catherine
Montréal, Canada H3T 2A7
October 28, 2003
Submitted to Operations Research
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 pickup and delivery
and the vehicle routing 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.
Area of review: Transportation.
In the Dial-a-Ride Problem (DARP), users formulate requests for transportation from a
specific origin (or pick-up point) to a specific destination (or drop-off point). Transportation
is carried out by vehicles that provide a shared service in the sense that several users may
be in a vehicle at the same time. The aim is to design a minimum-cost set of vehicle
routes accommodating all requests under a number of side constraints. A common DARP
application arises in door-to-door transportation services for the elderly and the disabled.
In this context, users often formulate two requests per day: an outbound request from home
to a destination, and an inbound request for the return trip.
Most dial-a-ride services are characterized by the presence of two conflicting objectives:
minimizing operating costs and minimizing user inconvenience. Operating costs ar