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

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.