IDEAS home Printed from https://ideas.repec.org/p/bay/rdwiwi/769.html
   My bibliography  Save this paper

A Cluster Based Scatter Search Heuristic for the Vehicle Routing Problem

Author

Listed:
  • Wendolsky, Rolf
  • Scheuerer, Stephan

Abstract

The Vehicle Routing Problem (VRP) is one of the most studied problems in the field of Operations Research. Closely related to the VRP is the Capacitated Clustering Problem (CCP). The VRP can be considered as an 'extension' of the CCP in the way that for each cluster in the CCP solution, additionally a route through all cluster customers and the depot has to be constructed to generate the routing information. In a previous study the Scatter Search methodology was used to solve the CCP. This algorithm had an excellent performance compared to other ones based on existing benchmark problems. This paper presents the necessary modifications to adopt this approach to the VRP. Das Tourenplanungs-Problem (Vehicle Routing Problem, VRP) ist eines der am häufigsten untersuchten Probleme des Operations Research. Eng verwandt mit dem VRP ist das Capacitated Clustering Problem (CCP). Das VRP kann als eine "Erweiterung" des CCP betrachtet werden, indem es für jedes Cluster einer CCP-Lösung eine Route durch alle Kunden des Clusters und das Depot zu konstruieren gilt, um die Tourreihenfolge zu bestimmen. In einem früheren Untersuchung wurde die Metaheuristik Scatter-Search zur Lösung des CCP angewendet. Dieser Algorithmus erwies sich im Vergleich mit anderen, basierend auf existierenden Benchmarkproblemen, als sehr leistungsstark. In diesem Beitrag wird gezeigt, wie dieser Algorithmus - mit einigen Modifikationen - auf das VRP übertragen werden kann.

Suggested Citation

  • Wendolsky, Rolf & Scheuerer, Stephan, 2006. "A Cluster Based Scatter Search Heuristic for the Vehicle Routing Problem," University of Regensburg Working Papers in Business, Economics and Management Information Systems 415, University of Regensburg, Department of Economics.
    • Handle: RePEc:bay:rdwiwi:769
    as

    Download full text from publisher

    File URL: https://epub.uni-regensburg.de/4537/1/ScatterSearch.pdf
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. J-F Cordeau & M Gendreau & G Laporte & J-Y Potvin & F Semet, 2002. "A guide to vehicle routing heuristics," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 53(5), pages 512-522, May.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Massimiliano Caramia & Francesca Guerriero, 2010. "A Milk Collection Problem with Incompatibility Constraints," Interfaces, INFORMS, vol. 40(2), pages 130-143, April.
    2. Nicolas Rincon-Garcia & Ben J. Waterson & Tom J. Cherrett, 2018. "Requirements from vehicle routing software: perspectives from literature, developers and the freight industry," Transport Reviews, Taylor & Francis Journals, vol. 38(1), pages 117-138, January.
    3. Zhixue Zhao & Xiamiao Li & Xiancheng Zhou, 2020. "Optimization of transportation routing problem for fresh food in time-varying road network: Considering both food safety reliability and temperature control," PLOS ONE, Public Library of Science, vol. 15(7), pages 1-19, July.
    4. José-Fernando Camacho-Vallejo & Lilian López-Vera & Alice E. Smith & José-Luis González-Velarde, 2022. "A tabu search algorithm to solve a green logistics bi-objective bi-level problem," Annals of Operations Research, Springer, vol. 316(2), pages 927-953, September.
    5. Barry B. & Quim Castellà & Angel A. & Helena Ramalhinho Lourenco & Manuel Mateo, 2012. "ILS-ESP: An Efficient, Simple, and Parameter-Free Algorithm for Solving the Permutation Flow-Shop Problem," Working Papers 636, Barcelona School of Economics.
    6. Christian Brandstätter, 2021. "A metaheuristic algorithm and structured analysis for the Line-haul Feeder Vehicle Routing Problem with Time Windows," Central European Journal of Operations Research, Springer;Slovak Society for Operations Research;Hungarian Operational Research Society;Czech Society for Operations Research;Österr. Gesellschaft für Operations Research (ÖGOR);Slovenian Society Informatika - Section for Operational Research;Croatian Operational Research Society, vol. 29(1), pages 247-289, March.
    7. Crevier, Benoit & Cordeau, Jean-Francois & Laporte, Gilbert, 2007. "The multi-depot vehicle routing problem with inter-depot routes," European Journal of Operational Research, Elsevier, vol. 176(2), pages 756-773, January.
    8. E A Silver, 2004. "An overview of heuristic solution methods," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 55(9), pages 936-956, September.
    9. Calvete, Herminia I. & Gale, Carmen & Oliveros, Maria-Jose & Sanchez-Valverde, Belen, 2007. "A goal programming approach to vehicle routing problems with soft time windows," European Journal of Operational Research, Elsevier, vol. 177(3), pages 1720-1733, March.
    10. Stefan Vonolfen & Michael Affenzeller, 2016. "Distribution of waiting time for dynamic pickup and delivery problems," Annals of Operations Research, Springer, vol. 236(2), pages 359-382, January.
    11. Derigs, U. & Kaiser, R., 2007. "Applying the attribute based hill climber heuristic to the vehicle routing problem," European Journal of Operational Research, Elsevier, vol. 177(2), pages 719-732, March.
    12. Ho, Sin C. & Szeto, W.Y. & Kuo, Yong-Hong & Leung, Janny M.Y. & Petering, Matthew & Tou, Terence W.H., 2018. "A survey of dial-a-ride problems: Literature review and recent developments," Transportation Research Part B: Methodological, Elsevier, vol. 111(C), pages 395-421.
    13. Jeet, V. & Kutanoglu, E., 2007. "Lagrangian relaxation guided problem space search heuristics for generalized assignment problems," European Journal of Operational Research, Elsevier, vol. 182(3), pages 1039-1056, November.
    14. Fleming, Christopher L. & Griffis, Stanley E. & Bell, John E., 2013. "The effects of triangle inequality on the vehicle routing problem," European Journal of Operational Research, Elsevier, vol. 224(1), pages 1-7.
    15. ARNOLD, Florian & SÖRENSEN, Kenneth, 2017. "A simple, deterministic, and efficient knowledge-driven heuristic for the vehicle routing problem," Working Papers 2017012, University of Antwerp, Faculty of Business and Economics.
    16. repec:spr:compst:v:68:y:2008:i:2:p:361-382 is not listed on IDEAS
    17. Z Fu & R Eglese & L Y O Li, 2005. "A new tabu search heuristic for the open vehicle routing problem," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 56(3), pages 267-274, March.
    18. Saira Latif & Torbjörn Lindbäck & Magnus Karlberg & Johanna Wallsten, 2022. "Bale Collection Path Planning Using an Autonomous Vehicle with Neighborhood Collection Capabilities," Agriculture, MDPI, vol. 12(12), pages 1-20, November.
    19. Bhoopalam, Anirudh Kishore & Agatz, Niels & Zuidwijk, Rob, 2018. "Planning of truck platoons: A literature review and directions for future research," Transportation Research Part B: Methodological, Elsevier, vol. 107(C), pages 212-228.
    20. Phan Nguyen Ky Phuc & Nguyen Le Phuong Thao, 2021. "Ant Colony Optimization for Multiple Pickup and Multiple Delivery Vehicle Routing Problem with Time Window and Heterogeneous Fleets," Logistics, MDPI, vol. 5(2), pages 1-13, May.
    21. Marc Reimann & Heinz Ulrich, 2006. "Comparing backhauling strategies in vehicle routing using Ant Colony Optimization," Central European Journal of Operations Research, Springer;Slovak Society for Operations Research;Hungarian Operational Research Society;Czech Society for Operations Research;Österr. Gesellschaft für Operations Research (ÖGOR);Slovenian Society Informatika - Section for Operational Research;Croatian Operational Research Society, vol. 14(2), pages 105-123, June.

    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:bay:rdwiwi:769. See general information about how to correct material in RePEc.

    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 bibliographic 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.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Gernot Deinzer (email available below). General contact details of provider: https://edirc.repec.org/data/wfregde.html .

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

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.