Parallel Variable Neighbourhood Search for the Car Sequencing Problem

Abstract

Variable Nachbarschaftssuche (VNS) ist eine relative neue Metaheuristik zum Lösen von schwierigen kombinatorischen Optimierungsproblemen. Ein solches Optimierungsproblem ist das Car Sequencing Problem (CarSP), wo eine Anordnung von Autos am Fließband mit minimalen Produktionskosten gefunden werden muss. Obwohl VNS eine erfolgreiche Metaheuristik ist, dauert es für praxisnahe Instanzen von CarSP eine lange Zeit bis eine brauchbare Lösung gefunden wird. Zwei Ansätze sollen ausführlicher untersucht werden: Erstens sollte die Effizienz von Nachbarschaften, d.h. das Verhältnis von Berechnungszeit und Lösungsverbesserung, während der Programmausführung verwendet werden, um effiziente Nachbarschaftsreihenfolgen zu bestimmen. Zweitens sollte das hohes Parallelisierungspotential ausgenutzt werden. Im Rahmen dieser Diplomarbeit werden beide Ansätze kombiniert. Die Tests zeigten, dass eine beträchtliche Reduktion der Berechnungszeit möglich ist.<br />Weiters haben die Tests gezeigt, dass keine "perfekte" Nachbarschaftsreihenfolge identifiziert werden kann was bedeutet, dass ein paralleler selbst-adaptiver Ansatz nützlich und wichtig ist, um gute Lösungsqualitäten zu erhalten.<br />

Variable Neighborhood Search (VNS) is a relatively new metaheuristic for solving hard combinatorial optimisation problems. One such optimisation problem is the Car Sequencing Problem (CarSP), where a sequence of cars along the assembly line with minimum production costs has to be found.<br />Although VNS is a successful metaheuristic, it takes a long time until a suitable solution is found for real-world instances of CarSP. Two approaches should be investigated in more detail: Firstly, the efficiency of neighborhoods, i.e. the relation of computation time and the solution improvement, should be used for identifying efficient neighborhood orderings on the fly. Secondly, the high potential of parallelisation techniques should be exploited. Within this thesis both approaches are combined. Computational tests showed that a substantial reduction of the computation time is possible. Further, the tests revealed that no "perfect" neighborhood ordering can be identified which implies that such a parallel self-adaptive approach is valuable and necessary for obtaining good solution qualities.