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

TLDR

The dial‑a‑ride problem requires designing minimum‑cost vehicle routes that satisfy capacity, duration, time‑window, pairing, precedence, and ride‑time constraints for user requests between specific origins and destinations. This study proposes a mixed‑integer programming formulation and a branch‑and‑cut algorithm to solve the dial‑a‑ride problem. The algorithm incorporates novel valid inequalities for the dial‑a‑ride problem together with established inequalities from the traveling salesman, vehicle routing, and pickup‑and‑delivery problems. Experiments on randomly generated instances demonstrate that the approach can solve small to medium‑size problems efficiently.

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.