Journal article
Cyclic-order neighborhoods with application to the vehicle routing problem with stochastic demand
European journal of operational research, Vol.217(2), pp.312-323
03/01/2012
DOI: 10.1016/j.ejor.2011.09.023
Abstract
► We design neighborhoods to search the space of cyclic orders for VRPs. ► We match 16 of 19 known a priori VRPSD solutions. ► An updating procedure speeds computation in local search schemes.
We examine neighborhood structures for heuristic search applicable to a general class of vehicle routing problems (VRPs). Our methodology utilizes a cyclic-order solution encoding, which maps a permutation of the customer set to a collection of many possible VRP solutions. We identify the best VRP solution in this collection via a polynomial-time algorithm from the literature. We design neighborhoods to search the space of cyclic orders. Utilizing a simulated annealing framework, we demonstrate the potential of cyclic-order neighborhoods to facilitate the discovery of high quality a priori solutions for the vehicle routing problem with stochastic demand (VRPSD). Without tailoring our solution procedure to this specific routing problem, we are able to match 16 of 19 known optimal VRPSD solutions. We also propose an updating procedure to evaluate the neighbors of a current solution and demonstrate its ability to reduce the computational expense of our approach.
Details
- Title: Subtitle
- Cyclic-order neighborhoods with application to the vehicle routing problem with stochastic demand
- Creators
- Justin C. Goodson - Saint Louis UniversityJeffrey W. Ohlmann - University of IowaBarrett W. Thomas - University of Iowa
- Resource Type
- Journal article
- Publication Details
- European journal of operational research, Vol.217(2), pp.312-323
- Publisher
- Elsevier B.V
- DOI
- 10.1016/j.ejor.2011.09.023
- ISSN
- 0377-2217
- eISSN
- 1872-6860
- Language
- English
- Date published
- 03/01/2012
- Academic Unit
- Business Analytics; Bus Admin College
- Record Identifier
- 9984380446002771
Metrics
2 Record Views