EURO 2025 Leeds
Abstract Submission

1791. A Heuristic Approach for the Periodic Vehicle Routing Problem with Driver Consistency

Invited abstract in session TA-15: Heuristic Search 1, stream Combinatorial Optimization.

Tuesday, 8:30-10:00
Room: Esther Simpson 1.08

Authors (first author is the speaker)

1. Marc Benito-Marimon
Estadística e Investigación operativa, Universidad de Valencia
2. Manuel Laguna
Leeds School of Business, University of Colorado Boulder
3. Anna Martínez-Gavara
Estadística i Investigació Operativa, Universitat de València
4. Rafael Marti
Departamento de Estadística e Investigación Operativa, Universitat de València

Abstract

This paper addresses the Periodic Vehicle Routing Problem with Driver Consistency (PVRP-DC), a critical extension of classical routing problems that incorporates both temporal planning and driver assignment consistency constraints. While traditional vehicle routing focuses primarily on cost minimization, the PVRP-DC acknowledges the significant operational benefits of maintaining consistent driver-customer relationships across multiple visits within a planning horizon. Despite its practical relevance in last-mile logistics, this variant has received limited attention in the optimization literature .
We propose a novel heuristic method for efficiently solving the PVRP-DC, which extends the standard Periodic Vehicle Routing Problem by ensuring that the same driver visits a customer across all scheduled service days. Our approach balances the computational complexity of simultaneously optimizing visit day combinations, route construction, and driver assignments while maintaining consistency constraints. Through computational experiments on benchmark instances, we show that our heuristic produces high-quality solutions within reasonable computational times. Additionally it compares favorably with the previous exact method in terms of scalability. The results indicate significant potential for practical implementation in dynamic last-mile delivery operations where both routing efficiency and service consistency are essential performance metrics.

Keywords

Status: accepted

Back to the list of papers