Cyclic-order neighborhoods with application to the vehicle routing problem with stochastic demand
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.
If you experience problems downloading a file, check if you have the proper application to view it first. In case of further problems read the IDEAS help page. Note that these files are not on the IDEAS site. Please be patient as the files may be large.
As the access to this document is restricted, you may want to look for a different version under "Related research" (further below) or search for a different version of it.
Volume (Year): 217 (2012)
Issue (Month): 2 ()
|Contact details of provider:|| Web page: http://www.elsevier.com/locate/eor|
References listed on IDEAS
Please report citation or reference errors to , or , if you are the registered author of the cited work, log in to your RePEc Author Service profile, click on "citations" and make appropriate adjustments.:
- M.J. Brusco & L.W. Jacobs & G.M. Thompson, 1999. "A morphing procedure to supplement a simulated annealing heuristic for cost‐ andcoverage‐correlated set‐covering problems," Annals of Operations Research, Springer, vol. 86(0), pages 611-627, January.
- Renaud, Jacques & Boctor, Fayez F., 2002. "A sweep-based algorithm for the fleet size and mix vehicle routing problem," European Journal of Operational Research, Elsevier, vol. 140(3), pages 618-628, August.
- Armentano, Vinicius Amaral & de Franca Filho, Moacir Felizardo, 2007. "Minimizing total tardiness in parallel machine scheduling with setup times: An adaptive memory-based GRASP approach," European Journal of Operational Research, Elsevier, vol. 183(1), pages 100-114, November.
When requesting a correction, please mention this item's handle: RePEc:eee:ejores:v:217:y:2012:i:2:p:312-323. See general information about how to correct material in RePEc.
For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (Dana Niculescu)
If references are entirely missing, you can add them using this form.