On the stochastic vehicle routing problem with time windows, correlated travel times, and time dependency

Federica Bomboi (), Christoph Buchheim () and Jonas Pruente ()
Additional contact information
Federica Bomboi: University of Cagliari
Christoph Buchheim: Fakultät für Mathematik, TU Dortmund
Jonas Pruente: Fakultät für Mathematik, TU Dortmund

4OR, 2022, vol. 20, issue 2, No 3, 217-239

Abstract: Abstract Most state-of-the-art algorithms for the Vehicle Routing Problem, such as Branch-and-Price algorithms or meta heuristics, rely on a fast feasibility test for a given route. We devise the first approach to approximately check feasibility in the Stochastic Vehicle Routing Problem with time windows, where travel times are correlated and depend on the time of the day. Assuming jointly normally distributed travel times, we use a chance constraint approach to model feasibility, where two different application scenarios are considered, depending on whether missing a customer makes the rest of the route infeasible or not. The former case may arise, e.g., in drayage applications or in the pickup-and-delivery VRP. In addition, we present an adaptive sampling algorithm that is tailored for our setting and is much faster than standard sampling techniques. We use a case study for both scenarios, based on instances with realistic travel times, to illustrate that taking correlations and time dependencies into account significantly improves the quality of the solutions, i.e., the precision of the feasibility decision. In particular, the nonconsideration of correlations often leads to solutions containing infeasible routes.

Keywords: Stochastic VRP; Time windows; Correlated travel times; Dynamic travel times; Chance constraints (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10288-021-00476-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:aqjoor:v:20:y:2022:i:2:d:10.1007_s10288-021-00476-z

Ordering information: This journal article can be ordered from
https://www.springer ... ch/journal/10288/PSE

DOI: 10.1007/s10288-021-00476-z

Access Statistics for this article

4OR is currently edited by Yves Crama, Michel Grabisch and Silvano Martello

More articles in 4OR from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().