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. 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.
    4. 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.
    5. 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.
    6. 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.
    7. 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.
    8. 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.
    9. 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.
    10. Andersson, Gert & Flisberg, Patrik & Lidén, Bertil & Rönnqvist, Mikael, 2007. "RuttOpt – A decision support system for routing of logging trucks," Discussion Papers 2007/16, Norwegian School of Economics, Department of Business and Management Science.
    11. Drexl, M. & Schneider, M., 2014. "A Survey of the Standard Location-Routing Problem," Publications of Darmstadt Technical University, Institute for Business Studies (BWL) 65940, Darmstadt Technical University, Department of Business Administration, Economics and Law, Institute for Business Studies (BWL).
    12. Felipe, Angel & Teresa Ortuño, M. & Tirado, Gregorio, 2011. "Using intermediate infeasible solutions to approach vehicle routing problems with precedence and loading constraints," European Journal of Operational Research, Elsevier, vol. 211(1), pages 66-75, May.
    13. M Caramia & F Guerriero, 2010. "A heuristic approach for the truck and trailer routing problem," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 61(7), pages 1168-1180, July.
    14. Olli Bräysy & Michel Gendreau, 2005. "Vehicle Routing Problem with Time Windows, Part II: Metaheuristics," Transportation Science, INFORMS, vol. 39(1), pages 119-139, February.
    15. Drexl, Michael & Schneider, Michael, 2015. "A survey of variants and extensions of the location-routing problem," European Journal of Operational Research, Elsevier, vol. 241(2), pages 283-308.
    16. 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.
    17. G I Zobolas & C D Tarantilis & G Ioannou, 2009. "A hybrid evolutionary algorithm for the job shop scheduling problem," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 60(2), pages 221-235, February.
    18. Angel Juan & Javier Faulin & Albert Ferrer & Helena Lourenço & Barry Barrios, 2013. "MIRHA: multi-start biased randomization of heuristics with adaptive local search for solving non-smooth routing problems," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 21(1), pages 109-132, April.
    19. Manousakis, Eleftherios G. & Kasapidis, Grigoris A. & Kiranoudis, Chris T. & Zachariadis, Emmanouil E., 2022. "An infeasible space exploring matheuristic for the Production Routing Problem," European Journal of Operational Research, Elsevier, vol. 298(2), pages 478-495.
    20. Christian Brabänder & Maximilian Braun, 2020. "Bringing economies of integration into the costing of groupage freight," Journal of Revenue and Pricing Management, Palgrave Macmillan, vol. 19(6), pages 366-385, December.

    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.