TU Darmstadt / ULB / TUprints

Developing efficient order picker routing policies in manual picker-to-parts order picking systems

Masae, Makusee (2020):
Developing efficient order picker routing policies in manual picker-to-parts order picking systems.
Darmstadt, Technische Universität, DOI: 10.25534/tuprints-00011290,
[Ph.D. Thesis]

[img]
Preview
Text
Developing efficient order picker routing policies in manual picker-to-parts order picking systems_Makusee Masae_PhD Thesis.pdf
Available under CC-BY-SA 4.0 International - Creative Commons, Attribution Share-alike.

Download (3MB) | Preview
Item Type: Ph.D. Thesis
Title: Developing efficient order picker routing policies in manual picker-to-parts order picking systems
Language: English
Abstract:

This dissertation develops several efficient order picker routing policies for manual picker-to-parts order picking systems. This work consists of six chapters and is structured as follows. Chapter 1 provides a brief introduction of the dissertation. Chapter 2 then presents the results of a systematic review of research on order picker routing. First, it identifies order picker routing policies in a systematic search of the literature and then develops a conceptual framework for categorizing the various policies. Order picker routing policies identified during the literature search are then descriptively analyzed and discussed in light of the developed framework. Our discussion of the state-of-knowledge of order picker routing shows that there is potential for future research to develop exact algorithms and heuristics for the routing of order pickers, both for order picking in specific scenarios and/or for non-conventional warehouses. One result of the literature review is that prior research on order picker routing always assumed that the picking tour starts and ends at the same location, which is usually the depot. In practice, however, it does not necessarily start and end at the same location, for example in case picking tours are updated in real time while they are being completed. Therefore, Chapter 3 proposes an exact algorithm as well as a routing heuristic for a conventional warehouse with two blocks where the starting and ending points of the picking tour are not fixed to the depot, but where they can be any locations in the warehouse instead. This chapter extends an earlier work of Löffler et al. (2018), who studied the case of a conventional warehouse with a single block, and adapts the solution procedures proposed by Ratliff and Rosenthal (1983) and Roodbergen and de Koster (2001a) that are both based on graph theory and dynamic programming procedure. Chapter 3 also develops a routing heuristic, denoted S*-shape, for solving the order picker routing problem in this scenario. In computational experiments, we compare the performance of the proposed routing heuristic to the exact algorithm. Our results indicate that the exact algorithm obtained tours that were between 6.32% and 35.34% shorter than those generated by the heuristic. One of the observations of Chapter 2 is that the order picker routing problem in non-conventional warehouses has not received much attention yet. Therefore, Chapter 4 studies the problem of routing an order picker in a non-conventional warehouse that has been referred to as the chevron warehouse in the literature. We propose an optimal order picker routing policy based on the solution procedures proposed by Ratliff and Rosenthal (1983) and Roodbergen and de Koster (2001a). Moreover, we modify three simple routing heuristics, namely the chevron midpoint, chevron largest gap, and chevron S-shape heuristics. The average order picking tour lengths resulting from the exact algorithm and the three routing heuristics were compared to evaluate the performance of the routing heuristics under various demand distributions and storage assignment policies used in warehouses. The results indicate that the picking tours resulting from the exact algorithm are 10.29% to 39.08% shorter than the picking tours generated by the routing heuristics. Chapter 5 then proposes an exact order picker routing algorithm for another non-conventional warehouse referred to as the leaf warehouse, and it again uses the concepts of Ratliff and Rosenthal (1983) and Roodbergen and de Koster (2001a). Moreover, it proposes four simple routing heuristics, referred to as the leaf S-shape, leaf return, leaf midpoint, and leaf largest gap heuristics. Similar to Chapter 4, we evaluate the performance of these heuristics compared to the exact algorithm for various demand distributions and storage assignment policies. Our results show that the picking tours resulting from the exact algorithm were, on average, between 3.96% to 43.68% shorter than the picking tours generated by the routing heuristics. Finally, Chapter 6 concludes the dissertation and presents an outlook on future research opportunities.

Alternative Abstract:
Alternative AbstractLanguage
Die vorliegende Dissertationsschrift entwickelt effiziente Routenpolitiken für manuell betriebene Person-zur-Ware Kommissioniersysteme. Die Arbeit besteht aus insgesamt sechs Kapiteln und ist wie nachfolgend beschrieben aufgebaut. Das erste Kapitel motiviert die Themenstellung und beschreibt den Aufbau der Dissertation. Das zweite Kapitel stellt sodann die Ergebnisse eines systematischen Literaturüberblicks zu wissenschaftlichen Arbeiten zur Routenführung für Kommissionierer vor. Das Kapitel identifiziert zunächst Veröffentlichungen zu diesem Thema im Rahmen einer systematischen Literatursuche und entwickelt darauf aufbauend ein konzeptionelles Rahmenwerk, das im Anschluss für die Kategorisierung der identifizierten Forschungsarbeiten verwendet wird. Die während der Literatursuche identifizierten Arbeiten werden anschließend deskriptiv analysiert und vor dem Hintergrund des entwickelten Rahmenwerks diskutiert. Die Besprechung der Veröffentlichungen zeigt, dass eine Reihe an Forschungslücken sowohl in Bezug auf die Entwicklung exakter Lösungsverfahren als auch in Bezug auf die Weiterentwicklung von Heuristiken existiert; besonders vielversprechend erscheinen Forschungsansätze zu sein, die sich mit besonderen Eigenschaften des Kommissioniervorgangs und bislang nicht untersuchten, unkonventionellen Lagerlayouts beschäftigen. So ist ein Ergebnis des Literaturüberblicks, dass Arbeiten zur Routenführung von Kommissionierern bislang fast exklusiv angenommen haben, dass der Start- und Endpunkt der Tour identisch ist und mit dem Depot übereinstimmt; in der Praxis lassen sich jedoch Anwendungsfälle beobachten, in denen Start- und Endpunkt der Kommissioniertour andere Orte im Lager sind (etwa in Situationen, in denen die Touren während des Kommissioniervorgangs aktualisiert werden). Kapitel 3 knüpft an dieser Erkenntnis an und entwickelt ein exaktes Verfahren sowie eine Routenheuristik für ein konventionelles Lager mit zwei Blöcken, in dem der Start- und der Endpunkt der Kommissioniertour beliebige Orte sein können und damit nicht auf das Depot eingeschränkt sind. Das Kapitel erweitert damit eine frühere Arbeit von Löffler et al. (2018), die das gleiche Szenario in einem konventionellen Lager mit nur einem Block untersucht hat. Zur Lösung des Verfahrens werden die Algorithmen von Ratliff und Rosenthal (1983) sowie von Roodbergen und de Koster (2001a) adaptiert, die beide einen graphentheoretischen Ansatz sowie eine dynamische Programmierung verwenden. Das dritte Kapitel entwickelt daneben auch eine Routenheuristik, die als S*-shape bezeichnet wird und die im untersuchen Szenario angewendet werden kann. Die Leistungsfähigkeit beider Verfahren wird im Rahmen von Rechenstudien verglichen. Hierbei zeigt sich, dass das exakte Verfahren Touren generiert, die zwischen 6,32% und 35,34% kürzer als die heuristisch generierten Touren sind. Eine zweite Forschungslücke, die in Kapitel 2 identifiziert wurde, bezieht sich auf das Fehlen exakter Routenverfahren für nichtkonventionelle Lagerhäuser. Das vierte Kapitel greift eine dieser Forschungslücken auf und entwickelt ein exaktes Routenverfahren für ein nichtkonventionelles Lager, das in der Literatur als Chevron-Lager beschrieben wird. Das entwickelte exakte Verfahren baut wiederum auf den Arbeiten von Ratliff und Rosenthal (1983) sowie Roodbergen und de Koster (2001a) auf. Daneben werden drei einfache Routenheuristiken modifiziert und auf das neue Lagerlayout angepasst: Die chevron midpoint, die chevron largest gap, und die chevron S-shape Heuristik. Die Leistungsfähigkeit der entwickelten Verfahren wird sodann wiederum in numerischen Studien für unterschiedliche Nachfrageverteilungen und Lagerplatzvergabepolitiken untersucht. Dabei stellt sich heraus, dass das exakte Verfahren Touren generiert, die zwischen 10,29% und 39,08% kürzer als die heuristisch generierten Routen sind. Das fünfte Kapitel beschäftigt sich im Anschluss mit einem weiteren unkonventionellen Lager, dem Leaf Lager, für das wiederum ein exaktes Routenverfahren sowie Heuristiken entwickelt werden. Auch in diesem Fall kann auf die Arbeiten von Ratliff und Rosenthal (1983) und Roodbergen und de Koster (2001a) zurückgegriffen werden, um das exakte Lösungsverfahren zu entwickeln. Die entwickelten Routenheuristiken werden als leaf S-shape, leaf return, leaf midpoint, und leaf largest gap bezeichnet. Rechenstudien, in denen die verschiedenen Verfahren für unterschiedliche Nachfrageverteilungen und Lagerplatzvergabepolitiken vergleichen, schließen das Kapitel ab. Hier zeigt sich, dass das exakte Verfahren zu Touren führt, die zwischen 3,96% und 43,68% kürzer als die heuristisch generierten Touren sind. Das sechste Kapitel schließt die Dissertation mit einem Ausblick auf weiterführende Forschungsarbeiten ab.German
Place of Publication: Darmstadt
Classification DDC: 300 Sozialwissenschaften > 330 Wirtschaft
Divisions: 01 Department of Law and Economics > Betriebswirtschaftliche Fachgebiete > Fachgebiet Produktion und Supply Chain Management
Date Deposited: 30 Jan 2020 14:27
Last Modified: 30 Jan 2020 14:27
DOI: 10.25534/tuprints-00011290
URN: urn:nbn:de:tuda-tuprints-112901
Referees: Glock, Prof. Dr. Christoph and Sgarbossa, Prof. Dr. Fabio
Refereed: 16 December 2019
URI: https://tuprints.ulb.tu-darmstadt.de/id/eprint/11290
Export:
Actions (login required)
View Item View Item