Solving the Vehicle Routing Problem with Stochastic Demands using the Cross Entropy Method
Krishna Chepuri (KChepuriPRDUS.JNJ.com)
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.
Entry Submitted: 06/24/2004
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|