New formulations for the robust vehicle routing problem with time windows under demand and travel time uncertainty

Rafael Campos, Leandro C. Coelho and Pedro Munari ()
Additional contact information
Rafael Campos: Université Laval
Leandro C. Coelho: Université Laval
Pedro Munari: Federal University of São Carlos (UFSCar)

OR Spectrum: Quantitative Approaches in Management, 2025, vol. 47, issue 2, No 3, 453 pages

Abstract: Abstract We present new formulations for the robust vehicle routing problem with time windows (RVRPTW) under cardinality- and knapsack-constrained demand and travel time uncertainty. They are the first compact models to address the RVRPTW under travel time uncertainty while considering the knapsack uncertainty set. Moreover, our models employ different types of constraints to control time propagation based on Miller–Tucker–Zemlin and single commodity flow constraints, which are derived from the linearization of recursive equations. We develop branch-and-cut methods based on the proposed formulations, leveraging a dynamic programming algorithm to verify the robust feasibility of solutions concerning both demand and travel time uncertainty, in addition to specific and standard separation procedures from the literature. We present detailed computational results on RVRPTW benchmark instances to compare the performance of our models and algorithms. Furthermore, we evaluate the impact and advantages of implementing each studied uncertainty set.

Keywords: Vehicle routing problem; Time windows; Uncertainty; Robust optimization; Commodity flow; Knapsack uncertainty set (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s00291-024-00781-z Abstract (text/html)
Access to the full text of the articles in this series is restricted.

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:spr:orspec:v:47:y:2025:i:2:d:10.1007_s00291-024-00781-z

Ordering information: This journal article can be ordered from
http://www.springer. ... research/journal/291

DOI: 10.1007/s00291-024-00781-z

Access Statistics for this article

OR Spectrum: Quantitative Approaches in Management is currently edited by Rainer Kolisch

More articles in OR Spectrum: Quantitative Approaches in Management from Springer, Gesellschaft für Operations Research e.V.
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().