IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v217y2012i2p312-323.html
   My bibliography  Save this article

Cyclic-order neighborhoods with application to the vehicle routing problem with stochastic demand

Author

Listed:
  • Goodson, Justin C.
  • Ohlmann, Jeffrey W.
  • Thomas, Barrett W.

Abstract

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.

Suggested Citation

  • Goodson, Justin C. & Ohlmann, Jeffrey W. & Thomas, Barrett W., 2012. "Cyclic-order neighborhoods with application to the vehicle routing problem with stochastic demand," European Journal of Operational Research, Elsevier, vol. 217(2), pages 312-323.
  • Handle: RePEc:eee:ejores:v:217:y:2012:i:2:p:312-323
    DOI: 10.1016/j.ejor.2011.09.023
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221711008514
    Download Restriction: Full text for ScienceDirect subscribers only

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. 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.
    2. 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.
    3. 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.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Luo, Zhixing & Qin, Hu & Zhang, Dezhi & Lim, Andrew, 2016. "Adaptive large neighborhood search heuristics for the vehicle routing problem with stochastic demands and weight-related cost," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 85(C), pages 69-89.
    2. Dimitrakos, T.D. & Kyriakidis, E.G., 2015. "A single vehicle routing problem with pickups and deliveries, continuous random demands and predefined customer order," European Journal of Operational Research, Elsevier, vol. 244(3), pages 990-993.
    3. Zhang, Junlong & Lam, William H.K. & Chen, Bi Yu, 2016. "On-time delivery probabilistic models for the vehicle routing problem with stochastic demands and time windows," European Journal of Operational Research, Elsevier, vol. 249(1), pages 144-154.
    4. Jorge Oyola & Halvard Arntzen & David L. Woodruff, 0. "The stochastic vehicle routing problem, a literature review, part I: models," EURO Journal on Transportation and Logistics, Springer;EURO - The Association of European Operational Research Societies, vol. 0, pages 1-29.
    5. Goodson, Justin C., 2015. "A priori policy evaluation and cyclic-order-based simulated annealing for the multi-compartment vehicle routing problem with stochastic demands," European Journal of Operational Research, Elsevier, vol. 241(2), pages 361-369.
    6. repec:spr:annopr:v:236:y:2016:i:2:d:10.1007_s10479-015-1949-7 is not listed on IDEAS
    7. repec:spr:eurjtl:v:6:y:2017:i:4:d:10.1007_s13676-016-0099-7 is not listed on IDEAS
    8. repec:pal:jorsoc:v:68:y:2017:i:11:d:10.1057_s41274-016-0170-7 is not listed on IDEAS
    9. Shukla, Nagesh & Choudhary, A.K. & Prakash, P.K.S. & Fernandes, K.J. & Tiwari, M.K., 2013. "Algorithm portfolios for logistics optimization considering stochastic demands and mobility allowance," International Journal of Production Economics, Elsevier, vol. 141(1), pages 146-166.
    10. Jorge Oyola & Halvard Arntzen & David L. Woodruff, 0. "The stochastic vehicle routing problem, a literature review, Part II: solution methods," EURO Journal on Transportation and Logistics, Springer;EURO - The Association of European Operational Research Societies, vol. 0, pages 1-40.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. 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). General contact details of provider: http://www.elsevier.com/locate/eor .

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service hosted by the Research Division of the Federal Reserve Bank of St. Louis . RePEc uses bibliographic data supplied by the respective publishers.