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

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