A Cluster Based Scatter Search Heuristic for the Vehicle Routing Problem

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.