A Robust Scenario Approach for the Vehicle Routing Problem with Uncertain Travel Times
Jinil Han (),
Chungmok Lee () and
Sungsoo Park ()
Additional contact information
Jinil Han: RealOpt team, INRIA Bordeaux---Sud-Ouest, 33405 Talence, France; and Department of Industrial and Systems Engineering, Korea Advanced Institute of Science and Technology, Yuseong-gu, Daejeon 305-701, Republic of Korea
Chungmok Lee: IBM Research-Ireland, Damastown Industrial Park, Mulhuddart, Dublin 15, Ireland; and IT Convergence Technology Research Laboratory, ETRI, Yuseong-gu, Daejeon 305-700, Republic of Korea
Sungsoo Park: Department of Industrial and Systems Engineering, Korea Advanced Institute of Science and Technology, Yuseong-gu, Daejeon 305-701, Republic of Korea
Transportation Science, 2014, vol. 48, issue 3, 373-390
Abstract:
We consider a vehicle routing problem with uncertain travel times in which a penalty is incurred for each vehicle that exceeds a given time limit. A traditional stochastic programming approach would require precise knowledge of the underlying probability distributions of random data. In a novel approach presented here, we assume that only rough information on future travel times is available, leading to the multiple range forecasts of travel times and the probabilities of each range being realized. In this setting, we replace the point estimates of travel times on a scenario by range estimates. For each scenario, we then find the robust routes that protect the solution against the worst case within the given ranges, and finally we find the routes with the minimum expected cost. We propose a branch-and-cut algorithm to solve the problem and report computational results on both randomly generated and the well-known Solomon's instances. The results demonstrate that our approach is a favorable one when exact information of probability distributions is not available.
Keywords: vehicle routing; stochastic travel times; robust optimization; stochastic programming; branch and cut (search for similar items in EconPapers)
Date: 2014
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (4)
Downloads: (external link)
http://dx.doi.org/10.1287/trsc.2013.0476 (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:inm:ortrsc:v:48:y:2014:i:3:p:373-390
Access Statistics for this article
More articles in Transportation Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().