[Back]


Doctor's Theses (authored and supervised):

M. Prandtstetter:
"Hybrid Optimization Methods for Warehouse Logistics and the Reconstruction of Destroyed Paper Documents";
Supervisor, Reviewer: G. Raidl, U. Pferschy; Institut für Computergraphik und Algorithmen, 2009.



English abstract:
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 the reconstruction of destructed
paper documents from the field of forensics. 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 among others in paper industry. Related warehouses consist of aisles orthogonal to
each other and storage locations are accessed using a Last-In, First-Out policy, i.e., only
the last stored item is directly accessible from each storage location. 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 (temporarily) stored in other locations.
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. 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, e.g., due to
delays of the carrier. 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 warehouse worker underlined the high quality of the
proposed approaches.
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. 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.
The second large topic of this thesis originates from the field of forensics and focuses on
the reconstruction of destroyed paper documents. The aspects considered here can be
divided into three subdomains: 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, e.g., 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/heuristic 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. This instance size,
however, corresponds to documents with only a few pages, e.g., approximately ten sheets
of paper using standard shredding devices. 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.

German 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.
Zuerst wird eine Variante der Lagerplatzverwaltung betrachtet, die unter anderem 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. Das heißt, nur auf die letzte an einem Lagerplatz
eingelagerte Papierrolle kann direkt zugegriffen werden. Will man hingegen eine
weiter hinten stehende Papierrolle ausfassen, muss man alle davor platzierten Rollen entnehmen
und (temporär) an anderen Lagerplätzen zwischenlagern. Das Ziel der in dieser
Arbeit verfolgten Variante der Lagerplatzzuweisung besteht darin Einlagerungen zu berechnen,
sodass die Anzahl der Umlagerungen während der Auslagerung, und somit die
benötigte Zeit, 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, zum Beispiel aufgrund von Verspätungen der Frächter. 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.
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.
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.


Electronic version of the publication:
http://publik.tuwien.ac.at/files/PubDat_181230.pdf


Created from the Publication Database of the Vienna University of Technology.