Hybrid optimization methods for warehouse logistics and the reconstruction of destroyed paper documents

Abstract

Diese Dissertation beschäftigt sich mit dem Lösen von kombinatorischen Optimierungsproblemen aus zwei unterschiedlichen Anwendungsbereichen: der Platzverwaltung und Berechnung von Kommissionierungstouren aus dem Bereich der Lagerverwaltung sowie die Rekonstruktion von zerstörten Papierdokumenten aus dem Bereich der Forensik. Obwohl diese beiden Probleme aus Sicht der Anwendung wenig gemeinsam haben, kann man dennoch Parallelen feststellen, wenn man sie im Detail betrachtet, da sie Varianten von wohlbekannten kombinatorischen Optimierungsprobleme sind. So ist die Lagerplatzverwaltung mit dem als blocks world bekannten Problem verwandt und die Berechnung von Touren sowie die Dokumentenrekonstruktion stehen stark in Beziehung zum Handlungsreisendenrpoblem. Zusätzlich wird eine kurze Darstellung von Standardmethoden zum Lösen schwerer kombinatorischer Optimierungsprobleme, die im Weiteren für die untersuchten Problemstellungen adaptiert werden, präsentiert.<br />Zuerst wird eine Variante der Platzverwaltung betrachtet, die in der Papierindustrie angewandt wird. Die dort verwendeten Lagerhäuser zeichnen sich durch auf einander orthogonal stehende Lagergänge aus. Die Lagerplätze selbst werden mittels einer Last-In, First-Out-Strategie verwaltet. Will man eine weiter hinten stehende Papierrolle ausfassen, muss man alle davor platzierten Rollen entnehmen und an anderen Lagerplätzen zwischenlagern. Das Ziel der in dieser Arbeit verfolgten Variante der Platzzuweisung besteht darin Einlagerungen zu berechnen, sodass die Anzahl der Umlagerungen während der Auslagerung minimiert wird. Unglücklicherweise ist die genaue Produktionsreihenfolge der Papierrollen im Vorhinein nicht bekannt, da es immer wieder zu Maschinenausfällen kommt. Weiters sind die exakten Lieferdaten nicht bekannt beziehungsweise können sich unvorhergesehen ändern. Neben einer Ad-hoc-Zuweisungsstrategie wurden auch zwei Umordnungsalgorithmen entwickelt, die in weiterer Folge verwendet werden können, um Ad-hoc-Umlagerungen sowie größere Umorganisationen des Lagers während Stehzeiten durchzuführen. Die entwickelten Algorithmen wurden in einem Lager eines Projektpartners getestet und die erreichten Ergebnisse sowie die Rückmeldung der Arbeiter zeigten die hohe Qualität der Lösungen auf.<br />Als zweites Problem aus dem Bereich der Lagerlogistik wurde die Berechnung von Kommissionierungstouren durch ein Lager, sodass die benötigte Zeit minimiert wird, betrachtet. Dafür wurde ein exakter Algorithmus basierend auf dynamischer Programmierung zur Berechnung von optimalen Touren in einem klassischen Lagerhaus entwickelt, wobei Lagerarbeiter letztlich den Touren folgend durch das Lager gehen um die bestellten Artikel einzusammeln. Dieser exakte Ansatz wurde zum Lösen von Teilproblemen verwendet und in ein größeres Framework integriert um zusätzliche Nebenbedingungen bezüglich Lieferdaten, Kundenbestellungen und der Zuweisung von Lagerarbeitern zu Lagerwägen erfüllen zu können.<br />Das zweite große Themengebiet dieser Dissertation entstammt aus dem Gebiet der Forensik und beschäftigt sich mit der Rekonstruktion von zerstörten Papierdokumenten. Die berücksichtigten Aspekte können in drei Klassen eingeteilt werden: (a) das Rekonstruieren von händisch zerrissenen Papierseiten und die Wiederherstellung von (b) in Streifen oder (c) in Rechtecke geschreddertem Papier. Obwohl die Aufgabenstellung für alle drei Varianten auf den ersten Blick ähnlich ist, liegen gravierende Unterschiede im Detail: Während zum Beispiel bei der Rekonstruktion von händisch zerrissenem Papier geometrische Information ausgenutzt werden kann, sind in den beiden anderen Fällen alle Schnipsel (nahezu) gleich geformt. Deswegen wird eine Zielfunktion eingeführt, die versucht die Wahrscheinlichkeit, dass zwei Schnipsel nebeneinander platziert werden sollen, abzuschätzen. Obwohl ein endgültiges (halb-)automatisches System zur Rekonstruktion von Papierdokumenten auch Mustererkennung und Bildverarbeitung ausnutzen wird, konzentriert sich diese Arbeit primär auf einen gewissermaßen ergänzenden Ansatz. Dafür wird das Problem zuerst als kombinatorisches Optimierungsproblem formuliert, welches dann mittels Transformation auf das Handlungsreisendenproblem abgebildet und mittels variabler Nachbarschaftssuche gelöst wird. Zusätzlich werden Schranken mit Hilfe einer Lagrangerelaxierung berechnet. Ein Ameisensystem und eine variable Nachbarschaftssuche werden auf die Rekonstruktion von in (kleine) Rechtecke geschnittenem Papier angewandt. Testergebnisse zeigen, dass mit diesem Ansätzen Instanzen mit bis zu 300 Schnipseln (fast perfekt) gelöst werden können. Diese Instanzgrößen entsprechen in etwa Dokumenten mit zehn Seiten. Berücksichtigt man allerdings die Komplexität dieser Problemstellung, unterstreichen die Ergebnisse das große Potenzial der vorgestellten Lösungsansätze. Weiters konnte gezeigt werden, dass die Anzahl der nötigen Operationen eines menschlichen Rekonstruierers erheblich reduziert werden konnte.<br />

The main topic of this thesis is the solving of real-world combinatorial optimization problems from two domains: storage location assignments and picking tour computations in warehouse management as well as from the field of forensics the reconstruction of destructed paper documents.<br />Although from the application point of view these two topics have not much in common, parallels can be identified when analyzing them in more detail. All of them are extended versions of well-known combinatorial optimization problems, i.e., the storage location assignment is a variant of blocks world; whereas the tour computations as well as the reconstruction of documents are related to the traveling salesman problem. In addition, a short overview on the standard methods for solving hard combinatorial optimization problem is given which will then be adapted for the topics of this thesis. First, a variant of the storage location assignment problem is examined which typically arises in paper industry. Related warehouses consist of aisles orthogonal to each other and storage locations are accessed using a Last-In, First-Out policy. In case someone wants to access a paper roll located not immediately accessible, all paper rolls placed in front of the requested one need to be removed and stored in other locations.<br />The goal of the storage location assignment examined within this thesis is to compute an assignment of paper rolls to stockyards such that during shipping minimal picking times arise which is equivalent to minimizing the number of necessary relocation operations when loading.<br />Unfortunately, the concrete production order of the paper rolls stored within the warehouse is not known in advance due to technical constraints. Even more, the shipping dates are only estimations and may suddenly change. However, beside the assignment of positions within the warehouse two rearrangement strategies have been developed such that ad-hoc relocations as well as warehouse reorganizations during idle times can be performed for improving the current warehouse state. The algorithms described within this part were directly applied in the warehouse of a partner company and the results obtained with respect to the warehouse states as well as the feedback of the workers underlined the high quality of the proposed approaches.<br />As a second problem from the domain of logistics and warehouse management the computation of order picking tours through a warehouse such that the total order picking times are minimized is investigated.<br />For this purpose, an exact algorithm based on dynamic programming for computing optimal tours through a "classical" stockyard which will be walked by warehouse men operating trolleys is presented. This procedure is applied as a subproblem solver within a larger framework regarding additional constraints related to shipping dates, customer orders and worker to trolley assignments.<br />The second large topic of this thesis originates from the field of forensics and focuses on the reconstruction of destroyed paper documents.<br />The aspects considered here can be divided into three subdomains:<br />reconstruction of (a) manually torn paper documents, (b) strip shredded documents and (c) cross cut shredded documents. Although the background is the same for all three of these concrete applications, they differ in important details, \eg while for the reconstruction of manually torn paper shape information can be exploited during the restoration process, the snippets produced by strip shredders or cross cut shredders are all (almost) equally shaped. Therefore, two different error estimation functions trying to estimate the likelihood that two snippets should be aligned with each other are proposed. Although a (semi-)automatic reconstruction system will finally incorporate pattern recognition and image processing techniques, we mainly focus on a somehow complimentary approach. Therefore, this problem is firstly formulated as a combinatorial optimization problem which is then solved by first applying a transformation to the traveling salesman problem, via a hybrid variable neighborhood search incorporating human user interactions and a Lagrangian relaxation for computing lower bounds. For the reconstruction of cross cut shredded documents additionally to a variable neighborhood search an ant colony optimization based method is applied. Experimental results document that instances with up to 300 shreds can be (almost perfectly) reconstructed using the presented approaches.<br />This instance size, however, corresponds to documents with only a few pages, e.g., approximately ten sheets of paper using standard shredding devices.<br />Considering the complexity of this problem the tests confirm the high potential of the proposed approaches. Even more, they show that the number of user operations when assembling destroyed documents is reduced to a minimum consisting of only a few final operations for obtaining the original document.