A Robust Scenario Approach for the Vehicle Routing Problem with Uncertain Travel Times
HAN, Jinil
Reformulations based algorithms for Combinatorial Optimization [Realopt]
Institut de Mathématiques de Bordeaux [IMB]
Korea Advanced Institute of Science and Technology [KAIST]
Reformulations based algorithms for Combinatorial Optimization [Realopt]
Institut de Mathématiques de Bordeaux [IMB]
Korea Advanced Institute of Science and Technology [KAIST]
LEE, Chungmok
IBM Research - Ireland
Electronics and Telecommunications Research Institute [DaeJeon] [ETRI]
IBM Research - Ireland
Electronics and Telecommunications Research Institute [DaeJeon] [ETRI]
HAN, Jinil
Reformulations based algorithms for Combinatorial Optimization [Realopt]
Institut de Mathématiques de Bordeaux [IMB]
Korea Advanced Institute of Science and Technology [KAIST]
Reformulations based algorithms for Combinatorial Optimization [Realopt]
Institut de Mathématiques de Bordeaux [IMB]
Korea Advanced Institute of Science and Technology [KAIST]
LEE, Chungmok
IBM Research - Ireland
Electronics and Telecommunications Research Institute [DaeJeon] [ETRI]
< Reduce
IBM Research - Ireland
Electronics and Telecommunications Research Institute [DaeJeon] [ETRI]
Language
en
Article de revue
This item was published in
Transportation Science. 2013-08-14, vol. 48, n° 3, p. 373-390
INFORMS
English 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 ...Read more >
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.Read less <
English Keywords
vehicle routing
stochastic travel times
robust optimization
stochastic programming
branch and cut
Origin
Hal imported