The vehicle routing problem with hard time windows and stochastic service times

F. Errico (), G. Desaulniers, M. Gendreau, W. Rei and L.-M. Rousseau
Additional contact information
F. Errico: CIRRELT Interuniversity Research Center on Enterprise Networks, Logistics and Transportation, GERAD Group for Research in Decision Analysis
G. Desaulniers: GERAD Group for Research in Decision Analysis
M. Gendreau: École Polytechnique de Montréal
W. Rei: CIRRELT Interuniversity Research Center on Enterprise Networks, Logistics and Transportation
L.-M. Rousseau: École Polytechnique de Montréal

EURO Journal on Transportation and Logistics, 2018, vol. 7, issue 3, No 2, 223-251

Abstract: Abstract In this paper we consider the vehicle routing problem with hard time windows and stochastic service times (VRPTW-ST); in this variant of the classic VRPTW the service times are random variables. In particular, given a set of vehicle routes, some of the actual service times might not lead to a feasible solution, given the customer time windows. We consider a chance-constrained program to model the VRPTW-ST and provide a new set partitioning formulation that includes a constraint on the minimum success probability of the set of vehicle routes. Under some mild conditions, we develop a method to exactly compute the success probability of the routes. We then solve the VRPTW-ST by a branch-price-and-cut algorithm, where the main challenges are in the solution of the subproblems of the column generation procedure. We adapt the dynamic programming algorithm to account for the probabilistic resource consumption by extending the label dimension and by providing new dominance rules. Extensive computational experiments prove the effectiveness of both the solution method and the stochastic model.

Keywords: Vehicle routing problem; Service time; Stochastic programming; Chance constraint; Column generation (search for similar items in EconPapers)
Date: 2018
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (17)

Downloads: (external link)
http://link.springer.com/10.1007/s13676-016-0101-4 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:eurjtl:v:7:y:2018:i:3:d:10.1007_s13676-016-0101-4

Ordering information: This journal article can be ordered from
http://www.springer. ... search/journal/13676

DOI: 10.1007/s13676-016-0101-4

Access Statistics for this article

EURO Journal on Transportation and Logistics is currently edited by Michel Bierlaire

More articles in EURO Journal on Transportation and Logistics from Springer, EURO - The Association of European Operational Research Societies
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().