Solving the Vehicle Routing Problem with Stochastic Demands using the Cross Entropy Method

Krishna Chepuri (KChepuriPRDUS.JNJ.com)
Tito Homem-de-Mello (titonorthwestern.edu )

Abstract: 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.

Keywords: vehicle routing problem, stochastic optimization, cross-entropy method

Category 1: Applications -- OR and Management Sciences

Category 2: Global Optimization

Citation: Manuscript, submitted for publication.

Download: [PDF]

Entry Submitted: 06/24/2004
Entry Accepted: 06/24/2004
Entry Last Modified: 06/24/2004

Modify/Update this entry