Ein hybrides Verfahren basierend auf Variabler Nachbarschaftssuche und Dynamischer Programmierung zur Tourenfindung in einem Ersatzteillager mit domänenspezifschen Nebenbedingungen

Abstract

Im Rahmen dieser Arbeit wird eine konkrete Problemstellung aus dem Bereich der Lagerverwaltung behandelt. Dabei soll die benötigte Zeit zum Ausfassen von Artikeln aus dem Lager unter Berücksichtigung von domänenspezifischen Nebenbedingungen minimiert werden. Ausgehend von durch Kunden laufend aufgegebenen Bestellungen sollen feste Lieferzeiten eingehalten werden und Einschränkungen wie etwa Kapazitätslimits oder das Vermeiden von Kollisionen zwischen Arbeitern beachtet werden. Die für die gegebene Problemstellung zentrale Bestimmung effizienter Touren steht im Mittelpunkt der Arbeit, welche mit Ergebnissen aus einer konkreten Implementierung des vorgestellten Ansatzes abschließt.<br />Es wird ein Algorithmus vorgestellt, der ein eigens entwickeltes Dynamisches Programm zur Berechnung optimaler Wege durch das Warenlager mit der Umsetzung einer Variablen Nachbarschaftssuche (engl.: Variable Neighborhood Search) (VNS) verbindet. In mehreren Phasen werden dabei die vorliegenden Bestellungen zerlegt und davon ausgehend Touren gebildet, welche zuletzt auf alle verfügbaren Lagerarbeiter verteilt werden. Innerhalb der VNS kommt eine Variante des Variable Neighborhood Descent (VND) als lokale Verbesserungskomponente zum Einsatz. Während über die definierten Nachbarschaftsstrukturen unterschiedliche potentielle Lösungen erzeugt werden, erfolgt deren Bewertung durch die Berechnung von konkreten Touren mittels eines für diesen Zweck entwickelten Dynamischen Programms. Dabei werden spezielle Eigenschaften der zugrundeliegenden Lagerstruktur ausgenutzt, um so in polynomieller Zeit die bestmögliche Wegführung durch das Lager berechnen zu können.<br />Für die Zuordnung von Arbeitern zu den auf diese Weise berechneten Touren wird schließlich eine zusätzliche VNS verwendet, deren Aufgabe es ist, die notwendigen Touren derart zu verteilen, dass der letzte Artikel zum frühest möglichen Zeitpunkt ausgefasst werden kann.<br />Die anhand des implementierten Programms durchgeführten Tests zeigen, dass die erfolgte Tourenplanung wertvolle Ergebnisse liefert und die notwendige Rechenzeit niedrig gehalten werden kann. Getestet wurde mit Bezug auf eine Referenzlösung, welche auf Basis eines aus der Literatur entnommenen Ansatzes erzeugt werden konnte. Eine ausführliche Auswertung der Testergebnisse zeigte, dass die Anwendung des hier vorgestellten Ansatzes im Echtbetrieb als sehr vielversprechend gilt und erhebliche Einsparungen bezüglich der benötigten Arbeitszeit erreicht werden können. Insgesamt betrachtet wird ein effizientes und zielführendes Verfahren zur Lösung des vorliegenden Problems vorgestellt.<br />

Within this thesis a real-world problem related to a warehouse for spare parts is considered. Regarding several constraints typically stated by spare parts suppliers the time needed to collect articles should be minimized. Based on continuously arriving orders by customers predefined delivery times and capacity constraints have to be met. To accomplish this task efficient pickup tours need to be determined which is the main issue covered by this work which comes to an end with experimental results of a concrete implementation of the proposed approach. The algorithm presented embeds a specifically developed dynamic program for computing optimal walks through the warehouse into a general variable neighborhood search (VNS) scheme. Several stages are used for first splitting up all orders, then creating tours out of the results and finally assigning them to available workers. The VNS uses a variant of the variable neighborhood descent (VND) as local improvement procedure. While the neighborhood structures defined are intended to produce candidate solutions, a dynamic program specially designed to compute optimal order picking tours is used to evaluate them. For this purpose properties specific to warehouses are exploited such to compute optimal routes within polynomial time. The final assignment of workers to tours is realized by another VNS. The task is then to find an allocation such that the last article to be picked up will be collected as early as possible. Evaluations of experimental results of a concrete implementation indicate that the presented approach provides valuable pickup plans and computation times can be kept low. Moreover the performed test runs have been compared to a reference solution which was computed based on an approach found in relevant literature. A detailed analysis of the obtained results showed that the application of the proposed approach to real-world instances is promising whereas the savings with respect to working time can be kept high. Overall an efficient as well as effective approach is introduced to solve this real-world problem.