TU Darmstadt / ULB / TUprints

Designing new models and algorithms to improve order picking operations

Žulj, Ivan (2020)
Designing new models and algorithms to improve order picking operations.
Technische Universität
doi: 10.25534/tuprints-00011836
Ph.D. Thesis, Primary publication

[img]
Preview
Text
Dissertation_Ivan_Zulj.pdf
Copyright Information: CC BY-SA 4.0 International - Creative Commons, Attribution ShareAlike.

Download (3MB) | Preview
Item Type: Ph.D. Thesis
Type of entry: Primary publication
Title: Designing new models and algorithms to improve order picking operations
Language: English
Referees: Schneider, Prof. Dr. Michael ; Glock, Prof. Dr. Christoph ; Schimmelpfeng, Prof. Dr. Katja
Date: 2020
Place of Publication: Darmstadt
Date of oral examination: 28 May 2020
DOI: 10.25534/tuprints-00011836
Abstract:

Order picking has been identified as a crucial factor for the competitiveness of a supply chain because inadequate order picking performance causes customer dissatisfaction and high costs. This dissertation aims at designing new models and algorithms to improve order picking operations and to support managerial decisions on facing current challenges in order picking.

First, we study the standard order batching problem (OBP) to optimize the batching of customer orders with the objective of minimizing the total length of order picking tours. We present a mathematical model formulation of the problem and develop a hybrid solution approach of an adaptive large neighborhood search and a tabu search method. In numerical studies, we conduct an extensive comparison of our method to all previously published OBP methods that used standard benchmark sets to investigate their performance. Our hybrid outperforms all comparison methods with respect to average solution quality and runtime. Compared to the state-of-the-art, the hybrid shows the clearest advantages on the larger instances of the existing benchmark sets, which assume a larger number of customer orders and larger capacities of the picking device. Finally, our method is able to solve newly generated large-scale instances with up to 600 customer orders and six items per customer order with reasonable runtimes and convincing scaling behavior and robustness.

Next, we address a problem based on a practical case, which is inspired by a warehouse of a German manufacturer of household products. In this warehouse, heavy items are not allowed to be placed on top of light items during picking to prevent damage to the light items. Currently, the case company determines the sequence for retrieving the items from their storage locations by applying a simple S-shape strategy that neglects this precedence constraint. As a result, order pickers place the collected items next to each other in plastic boxes and sort the items respecting the precedence constraint at the end of the order picking process. To avoid this sorting, we propose a picker routing strategy that incorporates the precedence constraint by picking heavy items before light items, and we develop an exact solution method to evaluate the strategy. We assess the performance of our strategy on a dataset provided to us by the manufacturer. We compare our strategy to the strategy used in the warehouse of the case company, and to an exact picker routing approach that does not consider the given precedence constraint. The results clearly demonstrate the convincing performance of our strategy even if we compare our strategy to the exact solution method that neglects the precedence constraint.

Last, we investigate a new order picking problem, in which human order pickers of the traditional picker-to-parts setup are supported by automated guided vehicles (AGVs). We introduce two mathematical model formulations of the problem, and we develop a heuristic to solve the NP-hard problem. In numerical studies, we assess the solution quality of the heuristic in comparison to optimal solutions. The results demonstrate the ability of the heuristic in finding high-quality solutions within a negligible computation time. We conduct several computational experiments to investigate the effect of different numbers of AGVs and different traveling and walking speed ratios between AGVs and order pickers on the average total tardiness. The results of our experiments indicate that by adding (or removing) AGVs or by increasing (or decreasing) the AGV speed to adapt to different workloads, a large number of customer orders can be completed until the respective due date.

Alternative Abstract:
Alternative AbstractLanguage

Die Kommissionierung hat sich als ein entscheidender Faktor für die Wettbewerbsfähigkeit einer Supply Chain erwiesen, da eine unzureichende Performance bei der Kommissionierung zu Kundenunzufriedenheit und hohen Kosten führt. Ziel dieser Dissertation ist es, neue Modelle und Algorithmen zu entwickeln, um die Kommissionierprozesse zu verbessern und Management-Entscheidungen zur Bewältigung aktueller Herausforderungen in der Kommissionierung zu unterstützen.

Zunächst untersuchen wir das Standard Order Batching Problem (OBP), um die Bündelung von Kundenaufträgen mit dem Ziel zu optimieren, die Gesamtlänge der Kommissioniertouren zu minimieren. Wir stellen eine mathematische Modellformulierung des Problems vor und entwickeln einen hybriden Lösungsansatz aus einer Adaptive Large Neighborhood Search und einer Tabu Search. In numerischen Studien führen wir einen ausführlichen Vergleich unserer Methode mit allen zuvor veröffentlichten OBP-Methoden durch, die zur Bewertung ihrer Performance Standard-Benchmarks verwendeten. Unser Hybrid schneidet im Hinblick auf die durchschnittliche Lösungsqualität und Rechenzeit besser ab als alle Vergleichsmethoden. Im Vergleich zur State-of-the-Art zeigt der Hybrid die deutlichsten Vorteile auf den größeren Instanzen der bestehenden Benchmarks, die von einer größeren Anzahl von Kundenaufträgen und größeren Kapazitäten des Kommissionierwagens ausgehen. Schließlich ist unser Verfahren in der Lage, neu generierte Testinstanzen mit bis zu 600 Kundenaufträgen und sechs Artikeln pro Kundenauftrag mit vernünftigen Rechenzeiten und überzeugendem Skalierungsverhalten und Robustheit zu lösen.

Als Nächstes betrachten wir ein Problem, das auf einem praktischen Fall beruht, der von einem Lager eines deutschen Herstellers von Haushaltsprodukten inspiriert ist. In diesem Lager dürfen bei der Kommissionierung schwere Artikel nicht auf leichte Artikel gelegt werden, um eine Beschädigung der leichten Artikel zu vermeiden. Gegenwärtig legt die Fallfirma die Reihenfolge für die Entnahme der Artikel aus ihren Lagerplätzen so fest, dass sie eine einfache S-förmige Routing-Strategie anwendet, die diese Vorrangsbeschränkung vernachlässigt. Infolgedessen legen die Kommissionierer die gesammelten Artikel nebeneinander in Kunststoffbehältern ab und sortieren die Artikel unter Beachtung der Vorrangbeschränkung am Ende des Kommissionierprozesses. Um diese Sortierung zu vermeiden, schlagen wir eine Strategie vor, bei der die Vorrangsbeschränkung berücksichtigt wird, indem schwere Artikel vor leichten Artikeln kommissioniert werden. Zur Bewertung dieser Strategie entwickeln wir eine exakte Lösungsmethode und bewerten sie anhand eines Datensatzes, der uns von der Fallfirma zur Verfügung gestellt wurde. Wir vergleichen unsere Strategie mit der Strategie, die im Lager der Fallfirma verwendet wird und mit einer exakten Routing-Strategie, die die vorgegebene Vorrangsbeschränkung nicht berücksichtigt. Die Ergebnisse zeigen deutlich die überzeugende Leistung unserer Strategie, auch wenn wir unsere Strategie mit der exakten Routing-Strategie vergleichen, die die Vorrangsbeschränkung vernachlässigt.

Zuletzt untersuchen wir ein neues Kommissionierproblem, bei dem menschliche Kommissionierer des traditionellen Person-zur-Ware-Systems durch fahrerlose Transportfahrzeuge (AGVs) unterstützt werden. Wir stellen zwei mathematische Modellformulierungen des Problems vor und wir entwickeln eine Heuristik zur Lösung des NP-schweren Problems. In numerischen Studien bewerten wir die Lösungsqualität der Heuristik im Vergleich zu optimalen Lösungen. Die Ergebnisse zeigen, dass die Heuristik in der Lage ist, qualitativ hochwertige Lösungen innerhalb einer vernachlässigbaren Rechenzeit zu finden. Wir führen mehrere Rechenexperimente durch, um die Auswirkung einer unterschiedlichen Anzahl an AGVs und unterschiedlicher Fahr- und Gehgeschwindigkeitsverhältnisse zwischen AGVs und Kommissionierern auf die durchschnittliche Gesamtverspätung zu untersuchen. Die Ergebnisse unserer Experimente deuten darauf hin, dass durch Hinzufügen (oder Entfernen) von AGVs oder durch Erhöhen (oder Verringern) der AGV-Geschwindigkeit zur Anpassung an unterschiedliche Arbeitsbelastungen ein Großteil der Kundenaufträge bis zum jeweiligen Fälligkeitstermin bedient werden kann.

German
URN: urn:nbn:de:tuda-tuprints-118366
Classification DDC: 300 Social sciences > 330 Economics
Divisions: 01 Department of Law and Economics > Betriebswirtschaftliche Fachgebiete
Date Deposited: 18 Jun 2020 11:00
Last Modified: 09 Jul 2020 06:35
URI: https://tuprints.ulb.tu-darmstadt.de/id/eprint/11836
PPN: 466725256
Export:
Actions (login required)
View Item View Item