Contributions to exact algorithms for picker routing and packing problems

Abstract

This thesis develops exact solution methods for several combinatorial optimization problems arising in warehouse logistics and packing operations. The primary focus is on picker routing problems in warehouses with scattered storage, where individual articles may be stored at multiple locations, requiring simultaneous decisions on item retrieval locations and routing. Building on dynamic programming-based state-space formulations, the thesis introduces new exact algorithms for the Single Picker Routing Problem with Scattered Storage (SPRP-SS) in both single-block and multi-block warehouse layouts. Contributions include the first exact solution method for the SPRP-SS under heuristic routing policies, two novel mixed-integer programming formulations with linear model size, and a branch-and-cut algorithm for multi-block warehouses. Furthermore, two new routing problems for zoned warehouses—the Multi-Zone Picker Routing Problem (MZPRP) and the Balanced Multi-Zone Picker Routing Problem (BMZPRP)—are introduced, together with efficient exact solution approaches. In addition, the thesis addresses the Skiving Stock Problem (SSP), a packing problem related to the cutting stock problem, by adapting the reflect+ algorithm and its underlying arc-flow formulation. The proposed methods significantly advance the exact optimization of warehouse routing and packing problems and provide effective tools for solving practically relevant large-scale instances.

In dieser Arbeit werden exakte Lösungsmethoden für verschiedene kombinatorische Optimierungsprobleme entwickelt, die in der Lagerlogistik und bei Packvorgängen auftreten. Der Schwerpunkt liegt auf Routing-Problemen für Kommissionierer in Lagern mit „scattered storage“, in denen einzelne Artikel an mehreren Lagerpositionen gelagert sein können, was gleichzeitige Entscheidungen über die Lagerpositionen für die Artikelentnahme und die Routenführung erfordert. Basierend auf dem Zustandsgraphen von Formulierungen der dynamischen Programmierung, werden in dieser Arbeit neue exakte Algorithmen für das Single Picker Routing Problem mit Scattered Storage (SPRP-SS) sowohl für Lagerlayouts mit einem Block als auch mit mehreren Blöcken vorgestellt. Dazu zählen die erste exakte Lösungsmethode für das SPRP-SS unter heuristischen Routing-Strategien, zwei neuartige Formulierungen der gemischt-ganzzahligen Programmierung mit linearer Modellgröße sowie ein Branch-and-Cut-Algorithmus für Lager mit mehreren Blöcken. Darüber hinaus werden zwei neue Routing-Probleme für in Zonen unterteilte Lager – das Multi Zone Picker Routing Problem (MZPRP) und das Balanced Multi-Zone Picker Routing Problem (BMZPRP) – zusammen mit effizienten exakten Lösungsansätzen vorgestellt. Zudem befasst sich die Arbeit mit dem Skiving Stock Problem (SSP), einem Verpackungsproblem im Zusammenhang mit dem Cutting Stock Problem, indem der Reflect+-Algorithmus und seine zugrunde liegende Bogenflussformulierung angepasst werden. Die vorgeschlagenen Methoden stellen einen bedeutenden Fortschritt bei der exakten Optimierung von Routingproblemen in Lagern und Packungsproblemen dar und bieten wirksame Werkzeuge zur Lösung praxisrelevanter großer Instanzen.