Leveraging machine learning for column generation in the dial-a-ride problem with driver preferences

Aug 5, 2026

The dial-a-ride problem (DARP) addresses door-to-door transportation scheduling by building feasible vehicle routes that satisfy operational constraints for pickup and delivery requests. This work targets a variant with time windows and drivers’ preferences (DARPDP). A unified methodology embeds machine learning into a column generation framework by reformulating the task into a master problem and pricing subproblem. Clustering-based initialization and an ML-driven heuristic reduce newly generated columns by up to 25%, accelerate convergence, and achieve only a 1.08% cost gap on large instances with substantially lower computation time.

LanguageEnglish

CategoryResearch & Report

FormatPDF

Pages13

Reading Time33 min

AccessFree to download

Introduction

Problem Background: DARP and DARPDP

Column Generation Overview

Related Work on DARP and CG

Motivation for Integrating ML into CG

IAES International Journal of Artificial Intelligence (IJ-AI) Vol. 14, No. 4, August 2025, pp. 2826∼2838 ISSN: 2252-8938, DOI: 10.11591/ijai.v14.i4.pp2826-2838 ❒ 2826 | Leveraging machine learning for column generation in the dial-a-ride problem with driver preferences
Sana Ouasaid, Mohammed Saddoune
Machine Intelligence Laboratory, Department of Computer Science, Faculty of Sciences and Technologies, University of Hassan II
Casablanca, Casablanca, Morocco | | | | --- | --- | --- | | Article Info
Article history:
Received Jun 18, 2024 Revised Mar 24, 2025 Accepted Jun 8, 2025
Keywords:
Binary classification Clustering-based initialization Column generation algorithm Dial-a-ride problem
Pricing subproblem | | ABSTRACT
The dial-a-ride problem (DARP) is a significant challenge in door-to-door transportation, requiring the development of feasible schedules for transportation requests while respecting various constraints. This paper addresses a variant of DARP with time windows and drivers’ preferences (DARPDP) . We introduce a solution methodology integrating machine learning (ML) into a column generation (CG) algorithm framework. The problem is reformulated into a master problem and a pricing subproblem. Initially, a clustering-based approach generates the initial columns, followed by a customized ML-based heuristic to solve each pricing subproblem. Experimental results demonstrate the efficiency of our approach: it reduces the number of the new generated columns by up to 25%, accelerating the convergence of the CG algorithm. Furthermore, it achieves a solution cost gap of only 1.08% compared to the best-known solution for large instances, while significantly reducing computation time.
This is an open access article under the CC BY-SA license. | | Corresponding Author: | | | | Sana Ouasaid
Machine Intelligence Laboratory, Department of Computer Science, Faculty of Sciences and Technologies University of Hassan II Casablanca
Casablanca, Morocco
Email: sana.ouasaid1-etu@etu.univh2c.ma | | | 1. INTRODUCTION The dial-a-ride problem (DARP) is a well-known and thoroughly explored area of study that focuses on designing efficient routing schedules for a fleet of vehicles to fulfill transportation requests, each involving a pickup and delivery point [1] . Optimizing DARP requires balancing cost-effectiveness with high service quality. It considers factors such as customer ride times and deviations from desired departure or arrival times. This challenge becomes even more complex when incorporating driver preferences, as in the DARP with time windows and drivers’ preferences (DARPDP) [2],[3] . In DARPDP, drivers aim to maximize served requests while also considering preferred destinations and arrival times, adding another layer of complexity to the optimization process. Existing approaches for DARPDP, such as those based on iterated local search metaheuristics, have shown promise but struggle with large-scale instances [3] . This scalability issue motivates the need for more efficient solution methodologies, particularly those well-suited to large-scale problems. One such method is column generation (CG), an iterative optimization technique that starts with a restricted set of columns representing a feasible solution. The master problem is solved using this initial subset, producing a current solution and dual variable values (shadow prices) . These dual variables guide the pricing subproblem, which identifies new columns with negative reduced costs. If such columns are found, they are added to the master problem, and the process is repeated until no further improvement is possible. CG has proven effective for addressing DARP and similar transportation challenges. Garaix et al. [4] optimized passenger occupancy in low-demand scenarios through efficient continuous relaxation of a setpartitioning model. Hybrid approaches further enhance CG, such as Parragh and Schmid [5], who combined

FAQs

What is the dial-a-ride problem variant studied in the paper?

The paper studies DARP with time windows and drivers’ preferences, called DARPDP, where drivers aim to serve requests and also consider preferred destinations and arrival times.

How does the proposed method integrate machine learning into column generation?

It reformulates the problem into a master problem and a pricing subproblem, then uses clustering-based initialization and a customized ML-based heuristic to solve the pricing subproblem inside the CG loop.

What performance improvements does the approach achieve?

Experiments show up to a 25% reduction in the number of newly generated columns, faster CG convergence, and only a 1.08% solution cost gap compared with the best-known solution for large instances, along with reduced computation time.

Aug 5, 2026

Upload by Clementine