We study the chance-constrained vehicle routing problem CCVRP, a version of the vehicle routing problem VRP with stochastic demands, where a limit is imposed on the probability that each vehicle's capacity is exceeded. A distinguishing feature of our proposed methodologies is that they allow correlation between random demands, whereas nearly all existing methods for the stochastic VRP require independent demands. We first study an edge-based formulation for the CCVRP, in particular addressing the challenge of how to determine a lower bound on the number of trucks required to serve a subset of customers. We then investigate the use of a branch-and-cut-and-price BCP algorithm. While BCP algorithms have been considered the state of the art in solving the deterministic VRP, few attempts have been made to extend this framework to the stochastic VRP.
['Thai Dinh', 'Ricardo Fukasawa', 'James R. Luedtke']
Exact Algorithms for the Chance-Constrained Vehicle Routing Problem