New formulation and valid inequalities for a periodic capacitated vehicle routing problem with multiple depots, heterogeneous fleet, and hard time-windows

Alejandro Arenas-Vasco, Juan Carlos Rivera and Maria Gulnara Baldoquín

PLOS ONE, 2025, vol. 20, issue 10, 1-18

Abstract: 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.

Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
https://journals.plos.org/plosone/article?id=10.1371/journal.pone.0335389 (text/html)
https://journals.plos.org/plosone/article/file?id= ... 35389&type=printable (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:plo:pone00:0335389

DOI: 10.1371/journal.pone.0335389

Access Statistics for this article

More articles in PLOS ONE from Public Library of Science
Bibliographic data for series maintained by plosone ().