A Cluster Based Scatter Search Heuristic for the Vehicle Routing Problem

Rolf Wendolsky and Stephan Scheuerer

No 415, University of Regensburg Working Papers in Business, Economics and Management Information Systems from University of Regensburg, Department of Economics

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.

Keywords: Operations Research; Metaheuristik; Tourenplanung; Scatter Search; Vehicle Routing; Scatter Search (search for similar items in EconPapers)
Date: 2006
References: View complete reference list from CitEc
Citations Track citations by RSS feed

Downloads: (external link)
http://epub.uni-regensburg.de/4537/1/ScatterSearch.pdf (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: http://EconPapers.repec.org/RePEc:bay:rdwiwi:769

Access Statistics for this paper

More papers in University of Regensburg Working Papers in Business, Economics and Management Information Systems from University of Regensburg, Department of Economics
Contact information at EDIRC.
Series data maintained by Gernot Deinzer ().