An alternate formulation of the classical vehicle routing problem with stochastic demands (VRPSD)is considered. We propose a new heuristic method to solve the problem. The algorithm is a modified version of the so-called Cross-Entropy method, which has been proposed in the literature as a heuristics for deterministic combinatorial optimization problems based upon concepts of rare-event simulation. In our version of the method, we incorporate Monte-Carlo sampling in order to estimate the objective function at each point in the domain. Many practical issues arise form this new feature, especially the decision as to when to draw new samples and how many samples to use. We address these issues and propose a formal algorithm, which is used to solve the underlying VRPSD. We also develop a framework for obtaining exact solutions and tight lower bounds for the problem under various conditions, which include specific families of demand distributions. This is used to assess the performance of the heuristics. Finally, numerical results are presented for various problem instances to illustrate the ideas.
Citation
Manuscript, submitted for publication.