A Cluster Based Scatter Search Heuristic for the Vehicle Routing Problem

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.