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

2006/05/31 by Jean-François Cordeau, Jean‐François Cordeau · 677 citations
Engineering · Mathematics · #2-opt #Algorithm #Branch and cut #Branch and price #Computer network #Computer science #Integer programming #Mathematical optimization #Mathematics #Routing (electronic design automation) #Set (abstract data type) #Smart Parking Systems Research #Transportation and Mobility Innovations #Traveling purchaser problem #Travelling salesman problem #Vehicle Routing Optimization Methods #Vehicle routing problem

paper · doi:10.1287/opre.1060.0283

published in Operations Research 54(3), 573-586 (Institute for Operations Research and the Management Sciences)

openalex publication_date 2006/05/31 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/25

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.

Citations

• Approximation algorithms for combinatorial problems

Cited by

• Variable Neighborhood Search Algorithms for the multi-depot dial-a-ride problem with heterogeneous vehicles and users
• The Bi-objective Electric Autonomous Dial-a-Ride Problem
• A Dynamic Tree Algorithm for Peer-to-Peer Ride-sharing Matching
• A multi-objective optimization framework for on-line ridesharing systems
• Finding optimal solutions for vehicle routing problem with pickup and delivery services with time windows: A dynamic programming approach based on state-space-time network representations
• An Optimization Framework for the Time-Dependent Electric Vehicle Routing Problem with Shared Mobility: A Step Toward Smart Cities
• A Matrix Representation of the Multiple Vehicle Routing Problem for Pickup and Delivery
• Paratransit Optimization with Constraint Programming: A Case Study in Savannah, Georgia
• Multi-atomic Annealing Heuristic for Static Dial-a-ride Problem
• Embedding Assignment Routing Constraints through Multi Dimensional Network Construction for Solving the Multi Vehicle Routing Problem with Pickup and Delivery with Time Windows
• Models and branch‐and‐cut algorithms for pickup and delivery problems with time windows
• Robust and Flexible Microtransit Design: Chance-Constrained Dial-a-Ride Problem with Soft Time Windows
• A Dynamic Tree Algorithm for On-demand Peer-to-peer Ride-sharing Matching
• On green routing and scheduling problem
• Optimizing Demand-Responsive Paratransit Operations: A Mixed Integer Programming Approach
• Energy-efficient Rail Guided Vehicle Routing for Two-Sided Loading/Unloading Automated Freight Handling System
• Commuting with Autonomous Vehicles: A Branch and Cut Algorithm with Redundant Modeling
• Large Scale Real-time Ridesharing with Service Guarantee on Road Networks
• An Improved Tabu Search Heuristic for Static Dial-A-Ride Problem
• On-demand high-capacity ride-sharing via dynamic trip-vehicle assignment
• A transformer-based deep reinforcement learning for the Dial-a-Ride problem
• An ALNS algorithm for the static dial-a-ride problem with ride and waiting time minimization
• A capacitated multi pickup online food delivery problem with time windows: a branch-and-cut algorithm. [europepmc]
• A Comparison of Multiple Objective Algorithms in the Context of a Dial a Ride Problem [europepmc]

Related

• A Branch-and-Cut algorithm for an urban dial-a-ride problem
• A Branch-and-Price Algorithm for the Electric Autonomous Dial-A-Ride Problem
• The Dial-a-Ride Problem with Limited Pickups per Trip
• Maximizing Revenues for Online-Dial-a-Ride
• A chance-constrained dial-a-ride problem with utility-maximizing demand and multiple pricing structures