New formulation and valid inequalities for a periodic capacitated vehicle routing problem with multiple depots, heterogeneous fleet, and hard time-windows
PLOS One · 2025
DOI: 10.1371/journal.pone.0335389 ↗Kurz gefasst
Fachartikel in der Zeitschrift PLOS One, 2025. Verfasst von Alejandro Arenas-Vasco und 2 weiteren Autor:innen. Beteiligte Einrichtung: Grupo de Investigación en Análítica y Cadenas de Suministro, Escuela de Ciencias Aplicadas e Ingeniería, Universidad EAFIT, Medellín, Antioquia, Colo…. Hauptthemen laut MEDLINE: Models, Theoretical. Die Arbeit wurde bisher 1-mal zitiert (Crossref) und nennt 14 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: Universidad EAFIT, Colfuturo.
Abstract (Originalsprache)
This paper presents a new formulation and valid constraints for a periodic capacitated vehicle routing problem with multiple depots, heterogeneous fleet, and hard time-windows (MDHFPCVRP-TW). The problem raises from a real-world application in the vending machine industry in Medellín, Colombia. Our main contribution is a novel formulation that replaces binary depot-client assignment variables with continuous auxiliary variables and implements depot replication, achieving both model simplicity and computational efficiency. We introduce preprocessing techniques and valid constraints, particularly focusing on capacity-based constraints with client combinations, which significantly strengthen the formulation’s linear relaxation. Computational experiments demonstrate that our formulation consistently outperforms previous approaches across different instance sizes, achieving optimality for small instances and maintaining single-digit optimality gaps for medium-sized instances where earlier formulations showed gaps above 12%. The formulation shows particularly strong performance in solution time, often requiring less time to find feasible solutions. While limitations persist for very large instances, our results suggest promising directions for developing hybrid exact-heuristic methods for industrial-scale problems.
Schlagwörter
MeSH-Schlagwörter (MEDLINE)
Autor:innen und Institutionen
- Grupo de Investigación en Análítica y Cadenas de Suministro, Escuela de Ciencias Aplicadas e Ingeniería, Universidad EAFIT, Medellín, Antioquia, Colombia.
ORCID-Profile: Alejandro Arenas-Vasco
Förderung
- Universidad EAFIT
- Colfuturo
Zitieren
APA
Arenas-Vasco, A., Rivera, J. C., & Baldoquín, M. G. (2025). New formulation and valid inequalities for a periodic capacitated vehicle routing problem with multiple depots, heterogeneous fleet, and hard time-windows. PLOS One. https://doi.org/10.1371/journal.pone.0335389
Vancouver
Arenas-Vasco A, Rivera JC, Baldoquín MG. New formulation and valid inequalities for a periodic capacitated vehicle routing problem with multiple depots, heterogeneous fleet, and hard time-windows. PLOS One. 2025. doi:10.1371/journal.pone.0335389
BibTeX
@article{ArenasVasco2025,
author = {Arenas-Vasco, Alejandro and Rivera, Juan Carlos and Baldoquín, Maria Gulnara},
title = {New formulation and valid inequalities for a periodic capacitated vehicle routing problem with multiple depots, heterogeneous fleet, and hard time-windows},
journal = {PLOS One},
year = {2025},
doi = {10.1371/journal.pone.0335389}
}
EUVIMED