Optimizing the retrieval effort in stack-based storage systems
Creators: name: Boge, Sven
Publisher: name: Universität Osnabrück
Year: 2022
Subjects: subject: operations research
subject: combinatorial optimization
subject: robust optimization
subject: integer programming
subject: data uncertainty
subject: logistics
subject: storage
subject: stacking problems
subject: storage unloading
subject: storage loading
subject: parallel stack loading problem
subject: premarshalling
subject: blocks relocation problem
subject: relocations
subject: reshuffles
subject: heuristics
subject: 004 - Informatik
subject: 54.99 - Informatik: Sonstiges

description: In this thesis we investigate three different aspects of stacking problems. In the context of stacking problems, a certain amount of items are usually stored in a limited number of stacks with limited stack height. At first we focus on an elementary loading problem, the parallel stack loading problem (PSLP). We consider the PSLP with the objective to minimize the number of reshuffles in the unloading phase. Since in the PSLP the incoming items have to be stored according to a fixed arrival sequence, some relocations cannot be avoided later on. In this context, we give a strengthened NP-completeness proof and study the two surrogate objective functions minimizing the total number of unordered stackings of adjacent items and the total number of badly placed items. These objective functions are established in the literature to estimate the number of reshuffles and we compare them theoretically as well as in a computational study with the desired objective function to minimize the number of reshuffles. For this purpose, mixed-integer programming (MIP) formulations and a simulated annealing (SA) algorithm are proposed. Altogether, it turned out that minimizing the number of reshuffles directly with a two-stage SA approach is superior to the application of exact MIP approaches to the surrogate objective function mentioned above. Furthermore, we consider the premarshalling problem, where items in a storage area have to be sorted for convenient retrieval. A new model for uncertainty is introduced, where the priority values induced by the retrieval sequence of the items are uncertain. We propose a robust optimization approach for this setting, study complexity issues and provide different MIP formulations. Moreover, we investigate helpful properties which can speed up the solution process in several cases. In a two-stage approach we use the results from the theoretical analysis and MIP formulations to calculate optimal objective values of optimally robust storage configurations in a first step and compute premarshalling solutions with a minimal number of reshuffles to reach optimal configurations in a second step. In a computational study using a wide range of benchmark instances from the literature, we investigate both the efficiency of the approach as well as the benefit and cost of robust solutions. We find that it is possible to achieve a considerably improved level of robustness by using just a few additional relocations in comparison to solutions which do not take uncertainty into account. Finally, we consider the process of unloading items from a storage in the case of the blocks relocation problem with item families. For a given sequence of families, it has to be decided which item of each demanded family is unloaded from the storage with the objective to minimize the total number of reshuffles. Besides new complexity results, we propose IP formulations and a two-stage SA algorithm. Computational results are presented for real-world data from a company, benchmark instances from the literature, and randomly generated instances with different characteristics.