Please use this identifier to cite or link to this item: https://hdl.handle.net/10419/286778 
Year of Publication: 
2021
Citation: 
[Journal:] 4OR [ISSN:] 1614-2411 [Volume:] 20 [Issue:] 2 [Publisher:] Springer [Place:] Berlin, Heidelberg [Year:] 2021 [Pages:] 217-239
Publisher: 
Springer, Berlin, Heidelberg
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.
Subjects: 
Stochastic VRP
Time windows
Correlated travel times
Dynamic travel times
Chance constraints
Persistent Identifier of the first edition: 
Creative Commons License: 
cc-by Logo
Document Type: 
Article
Document Version: 
Published Version

Files in This Item:
File
Size





Items in EconStor are protected by copyright, with all rights reserved, unless otherwise indicated.