Title (eng)
A block relocation algorithm for the steel slab stacking problem using heavy-duty vehicles
Parallel title (deu)
Ein Stapelungsalgorithmus für das Stahlbrammenstapelungsproblem mit Schwerlastfahrzeugen
Author
Iryna Pidsadochna
Advisor
Karl Franz Dörner
Assessor
Karl Franz Dörner
Abstract (deu)
Optimierung der Lagertätigkeiten ist von großer Bedeutung für schnellere und kostengünstigere
Verwaltung des Lagers. Als Beispiel einer Situation, wo eine effiziente und automatisierte Lösung
für Stapelung und Entnahme gelagerter Objekte gesucht wird, ist ein Stahlbrammenlager. Unter
Berücksichtigung der von einem Industrie-Partner (Voestalpine Stahl GmbH) zur Verfügung gestellten Daten wurde das Stahlbrammenstapelungsproblem (engl. SSSP, Steel Slab Stacking
Problem) als Verallgemeinerung des bereits im Wissenschaftsfeld Operations Research bekannten Stapelungsproblems (engl. BRP, Block Relocation Problem) formuliert. Die Besonderheiten
des SSSP im Vergleich zum Standard-BRP sind: die Möglichkeit der Versetzung mehrerer Objekte gleichzeitig, heterogene Objekte, Bewegungs- und Inkompatibilitätsrestriktionen sowie abweichende Entnahmebedingungen. Im Rahmen dieser Masterarbeit wurden zahlreiche Lösungsmethoden für BRP untersucht und der Schluss gezogen, dass die Lösung des SSSP eine besondere Vorgehensweise erfordert, die zwar gewisse Ähnlichkeiten zu den bereits vorhandenen
BRP-Lösungsmethoden aufweisen sollte, jedoch an alle Besonderheiten des SSSP genau angepasst werden muss. Somit wurde ein neuer Algorithmus zur Lösung des SSSP entwickelt (engl.
CMTA, Combined Multi-Target Algorithm). Diese Methode ist eine Heuristik, die den Zustand
des Lagers fortgehend analysiert und schrittweise die vorteilhaften Bewegungen bestimmt, beruhend auf einer vorausblickenden Handlungsstrategie. CMTA geht weitsichtig vor, um die Möglichkeit auszunutzen, Versetzungen zu kombinieren und möglichst viele Brammen gleichzeitig zu
entnehmen. Dabei wird ständig die Sinnhaftigkeit und die Realisierbarkeit der geplanten Bewegungen überprüft. CMTA wurde sowohl auf Benchmark-Instanzen für BRP als auch auf den von
der Voestalpine Stahl GmbH bereitgestellten Echtwelt-Instanzen getestet. Im Rahmen der Testung auf den Benchmark-Instanzen wurden alle relevanten Parameter angepasst, sodass das
Problem als Standard-BRP gelöst wird (mit homogenen Objekten, ohne besondere Bewegungseinschränkungen und mit einer Hebekapazität von nur einem Objekt). So konnte die Qualität der
von CMTA gelieferten Lösung zu den in der Forschungsliteratur festgehaltenen Ergebnissen
anerkannter Lösungsmethoden für Standard-BRP verglichen werden. Im Vergleich zu den besten Methoden aus der Literatur lieferte CMTA schlechtere, jedoch akzeptable Ergebnisse. Des
Weiteren wurden die Benchmark-Instanzen mit CMTA mit größeren Hebekapazitäten als 1 gelöst, um die damit verbundenen Verbesserungen der Zielfunktion zu analysieren. Im Zusammenhang mit erhöhter Hebekapazität konnten erhebliche Verbesserungen erreicht werden. Erwartungsgemäß sank mit steigender Hebekapazität auch der Grenznutzen der Kapazitätssteigerung (d. h., die relative Verbesserung der Zielfunktion). Angesichts dieser Beobachtung sowie
auch der Tatsache, dass eine Hebekapazität von mehr als 4 Objekten in der Praxis selten vorkommt, sei es bezogen auf Stapelung von Stahlbrammen oder auch anderer Objekte, wurde für
weitere Tests die Hebekapazität von 4 ausgewählt. Mit dieser Hebekapazität wurden alle Benchmark-Instanzen auch unter der Annahme jeweils unterschiedlicher maximaler Stapelhöhe gelöst.
Wie auch erwartet, die Steigerung dieses Parameters hatte eine positive Auswirkung auf die
Zielfunktion. Jedoch war diese Verbesserung nur bis zu einer gewissen Stapelhöhe wesentlich.
Je größer ist die ursprüngliche Stapelhöhe im Lager, desto bedeutender ist die Differenz zwischen der ursprünglichen und der höchstzulässigen Stapelhöhe für die Zielfunktion. Die von
CMTA gelieferten Ergebnisse für die Echtwelt-Instanzen wurden ebenso den Erwartungen ge-
recht.
Abstract (eng)
Optimization of warehouse operations is a key aspect of improving the cost-effectiveness and
manageability of a storage facility. An example of a real-life situation where an efficient and
automated way of stacking and retrieving objects is sought is a steel slab storage. Given the
data from an industrial partner, we defined the Steel Slab Stacking Problem (SSSP) as a generalization of the Block Relocation Problem (BRP). The particularities of SSSP, as opposed to BRP,
are batch moves, heterogenous items, movement restrictions, incompatibility restrictions and
the retrieval procedure. We analyzed numerous BRP solution methods from the related literature
and concluded that SSSP requires a special approach which takes into account its particularities,
while also applying some established rules for solving BRP. Thus, a new algorithm for SSSP
named Combined Multi-Target Algorithm (CMTA) was developed. This method is a heuristic
which analyzes the state of the bay and determines the most beneficial actions step by step.
CMTA uses a look-ahead principle in order to exploit the possibility of merging moves and retrieving as many slabs as possible at a time, as long as it contributes to decreasing the total
number of moves. CMTA was tested on BRP benchmark instances, as well as real-world instances provided by the industrial partner. For testing on the benchmark instances, all relevant
parameters were adjusted in order for CMTA to approach the problem as a standard BRP (with
homogenous items, with height restrictions instead of movement restrictions and without batch
moves). Compared to the state-of-the-art BRP solution methods from the literature, CMTA
showed inferior yet acceptable performance. Furthermore, we also tested the performance of
CMTA on the benchmark instances with batch moves allowed in order to analyze the improvements of the objective value. Drastic improvements were observed as a result of increasing the
lifting capacity. We came to a conclusion that not only the lifting capacity of 4 slabs is most
realistic, but also that the relative improvement from further increasing it was not as substantial.
Having chosen the lifting capacity of 4 slabs, we also studied the changes in the objective value
while increasing the maximal stack height. Predictably, the objective value improved along with
these increases with decreasing marginal improvement. Thus, at a certain point further augmentation of the maximal stack height did not boost the objective value noticeably. The higher
the stacks in the initial bay are, however, the longer does the increase in the maximal stack
height have a significant impact on the objective value. The results of testing CMTA on real-world instances also met all expectations, although the performance of CMTA on these instance sets could not be compared to that of other methods, as there are no methods designed for
this particular type of BRP.
Keywords (eng)
Block relocation problemBRPSteel slab stacking problem
Keywords (deu)
StapelungsproblemBRPStahlbrammenstapelungsproblem
Subject (deu)
Type (deu)
Persistent identifier
https://phaidra.univie.ac.at/o:1396315
rdau:P60550 (deu)
77 Seiten : Illustrationen, Diagramme
Number of pages
78
Study plan
Masterstudium Betriebswirtschaft
[UA]
[066]
[915]
Association (deu)
Title (eng)
A block relocation algorithm for the steel slab stacking problem using heavy-duty vehicles
Parallel title (deu)
Ein Stapelungsalgorithmus für das Stahlbrammenstapelungsproblem mit Schwerlastfahrzeugen
Author
Iryna Pidsadochna
Abstract (deu)
Optimierung der Lagertätigkeiten ist von großer Bedeutung für schnellere und kostengünstigere
Verwaltung des Lagers. Als Beispiel einer Situation, wo eine effiziente und automatisierte Lösung
für Stapelung und Entnahme gelagerter Objekte gesucht wird, ist ein Stahlbrammenlager. Unter
Berücksichtigung der von einem Industrie-Partner (Voestalpine Stahl GmbH) zur Verfügung gestellten Daten wurde das Stahlbrammenstapelungsproblem (engl. SSSP, Steel Slab Stacking
Problem) als Verallgemeinerung des bereits im Wissenschaftsfeld Operations Research bekannten Stapelungsproblems (engl. BRP, Block Relocation Problem) formuliert. Die Besonderheiten
des SSSP im Vergleich zum Standard-BRP sind: die Möglichkeit der Versetzung mehrerer Objekte gleichzeitig, heterogene Objekte, Bewegungs- und Inkompatibilitätsrestriktionen sowie abweichende Entnahmebedingungen. Im Rahmen dieser Masterarbeit wurden zahlreiche Lösungsmethoden für BRP untersucht und der Schluss gezogen, dass die Lösung des SSSP eine besondere Vorgehensweise erfordert, die zwar gewisse Ähnlichkeiten zu den bereits vorhandenen
BRP-Lösungsmethoden aufweisen sollte, jedoch an alle Besonderheiten des SSSP genau angepasst werden muss. Somit wurde ein neuer Algorithmus zur Lösung des SSSP entwickelt (engl.
CMTA, Combined Multi-Target Algorithm). Diese Methode ist eine Heuristik, die den Zustand
des Lagers fortgehend analysiert und schrittweise die vorteilhaften Bewegungen bestimmt, beruhend auf einer vorausblickenden Handlungsstrategie. CMTA geht weitsichtig vor, um die Möglichkeit auszunutzen, Versetzungen zu kombinieren und möglichst viele Brammen gleichzeitig zu
entnehmen. Dabei wird ständig die Sinnhaftigkeit und die Realisierbarkeit der geplanten Bewegungen überprüft. CMTA wurde sowohl auf Benchmark-Instanzen für BRP als auch auf den von
der Voestalpine Stahl GmbH bereitgestellten Echtwelt-Instanzen getestet. Im Rahmen der Testung auf den Benchmark-Instanzen wurden alle relevanten Parameter angepasst, sodass das
Problem als Standard-BRP gelöst wird (mit homogenen Objekten, ohne besondere Bewegungseinschränkungen und mit einer Hebekapazität von nur einem Objekt). So konnte die Qualität der
von CMTA gelieferten Lösung zu den in der Forschungsliteratur festgehaltenen Ergebnissen
anerkannter Lösungsmethoden für Standard-BRP verglichen werden. Im Vergleich zu den besten Methoden aus der Literatur lieferte CMTA schlechtere, jedoch akzeptable Ergebnisse. Des
Weiteren wurden die Benchmark-Instanzen mit CMTA mit größeren Hebekapazitäten als 1 gelöst, um die damit verbundenen Verbesserungen der Zielfunktion zu analysieren. Im Zusammenhang mit erhöhter Hebekapazität konnten erhebliche Verbesserungen erreicht werden. Erwartungsgemäß sank mit steigender Hebekapazität auch der Grenznutzen der Kapazitätssteigerung (d. h., die relative Verbesserung der Zielfunktion). Angesichts dieser Beobachtung sowie
auch der Tatsache, dass eine Hebekapazität von mehr als 4 Objekten in der Praxis selten vorkommt, sei es bezogen auf Stapelung von Stahlbrammen oder auch anderer Objekte, wurde für
weitere Tests die Hebekapazität von 4 ausgewählt. Mit dieser Hebekapazität wurden alle Benchmark-Instanzen auch unter der Annahme jeweils unterschiedlicher maximaler Stapelhöhe gelöst.
Wie auch erwartet, die Steigerung dieses Parameters hatte eine positive Auswirkung auf die
Zielfunktion. Jedoch war diese Verbesserung nur bis zu einer gewissen Stapelhöhe wesentlich.
Je größer ist die ursprüngliche Stapelhöhe im Lager, desto bedeutender ist die Differenz zwischen der ursprünglichen und der höchstzulässigen Stapelhöhe für die Zielfunktion. Die von
CMTA gelieferten Ergebnisse für die Echtwelt-Instanzen wurden ebenso den Erwartungen ge-
recht.
Abstract (eng)
Optimization of warehouse operations is a key aspect of improving the cost-effectiveness and
manageability of a storage facility. An example of a real-life situation where an efficient and
automated way of stacking and retrieving objects is sought is a steel slab storage. Given the
data from an industrial partner, we defined the Steel Slab Stacking Problem (SSSP) as a generalization of the Block Relocation Problem (BRP). The particularities of SSSP, as opposed to BRP,
are batch moves, heterogenous items, movement restrictions, incompatibility restrictions and
the retrieval procedure. We analyzed numerous BRP solution methods from the related literature
and concluded that SSSP requires a special approach which takes into account its particularities,
while also applying some established rules for solving BRP. Thus, a new algorithm for SSSP
named Combined Multi-Target Algorithm (CMTA) was developed. This method is a heuristic
which analyzes the state of the bay and determines the most beneficial actions step by step.
CMTA uses a look-ahead principle in order to exploit the possibility of merging moves and retrieving as many slabs as possible at a time, as long as it contributes to decreasing the total
number of moves. CMTA was tested on BRP benchmark instances, as well as real-world instances provided by the industrial partner. For testing on the benchmark instances, all relevant
parameters were adjusted in order for CMTA to approach the problem as a standard BRP (with
homogenous items, with height restrictions instead of movement restrictions and without batch
moves). Compared to the state-of-the-art BRP solution methods from the literature, CMTA
showed inferior yet acceptable performance. Furthermore, we also tested the performance of
CMTA on the benchmark instances with batch moves allowed in order to analyze the improvements of the objective value. Drastic improvements were observed as a result of increasing the
lifting capacity. We came to a conclusion that not only the lifting capacity of 4 slabs is most
realistic, but also that the relative improvement from further increasing it was not as substantial.
Having chosen the lifting capacity of 4 slabs, we also studied the changes in the objective value
while increasing the maximal stack height. Predictably, the objective value improved along with
these increases with decreasing marginal improvement. Thus, at a certain point further augmentation of the maximal stack height did not boost the objective value noticeably. The higher
the stacks in the initial bay are, however, the longer does the increase in the maximal stack
height have a significant impact on the objective value. The results of testing CMTA on real-world instances also met all expectations, although the performance of CMTA on these instance sets could not be compared to that of other methods, as there are no methods designed for
this particular type of BRP.
Keywords (eng)
Block relocation problemBRPSteel slab stacking problem
Keywords (deu)
StapelungsproblemBRPStahlbrammenstapelungsproblem
Subject (deu)
Type (deu)
Persistent identifier
https://phaidra.univie.ac.at/o:1396316
Number of pages
78
Association (deu)
License
Citable links
Other links
Managed by
Details
Metadata
Export formats
Universitätsring 1, 1010 Wien | T
T +43-1-4277-0