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

Krishna Chepuri () and Tito Homem- de-Mello ()

Annals of Operations Research, 2005, vol. 134, issue 1, 153-181

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, based on the Cross-Entropy method. In order to better estimate the objective function at each point in the domain, we incorporate Monte Carlo sampling. This creates many practical issues, especially the decision as to when to draw new samples and how many samples to use. 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 algorithm. Finally, numerical results are presented for various problem instances to illustrate the ideas. Copyright Springer Science + Business Media, Inc. 2005

Keywords: vehicle routing problem; stochastic optimization; cross-entropy method (search for similar items in EconPapers)
Date: 2005
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (24)

Downloads: (external link)
http://hdl.handle.net/10.1007/s10479-005-5729-7 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:annopr:v:134:y:2005:i:1:p:153-181:10.1007/s10479-005-5729-7

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10479

DOI: 10.1007/s10479-005-5729-7

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

More articles in Annals of Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().