Routing Order Pickers in Warehouses with Occurrences of Blocking Effects
Year:
2009
Authors/Eds.:
Johannes Wirges, Robert Scheffermann (Betr.)
Type of publication:
diploma thesis
Abstract:
Order picking is the activity of combining merchandise from a given assortment of goods to ful ll customer orders. In most warehouses this task is performed manually, by order
pickers walking/driving through the warehouse and retrieving the needed items by hand.
Of all processing tasks taking place within warehouses, this task is by far the most costly and laborious. Therefore, many di erent methods are in use today for designing and operating manual order picking systems to achieve a high level of performance. It has been
observed that occurrences of blocking e ects or order picker congestion lead to signi cant losses in performance, due to order pickers having to wait, or having to deviate from their intended sequence of activities. Such phenomena can for example be caused by order pickers being unable to pass each other within storage aisles, or only one order picker
being allowed to access one aisle at a time. The state of research on methods which help to avoid performance loss due to such phenomena is still in an early stage.
This works makes a contribution to research in this area. We present a literature survey on the topic of blocking e ects in manual order picking systems. Based on these ndings
we discuss reasonable constructive methods for minimizing the occurrences of such e ects.
The approach we take in this work is to treat is as a problem of routing: if order pickers move through the warehouse \just right" they can retrieve their needed items with little or no direct interferences. Before setting out to design our own algorithmic method for
the problem of optimally routing order picker under consideration of blocking e ects, we perform a thorough literature research on similar algorithmic problems. This survey shows that the considered problem seems to be a genuinely new variant of the traveling salesman problem, not directly solvable with priorly designed algorithms.
Thus we set out to design our own algorithmic solution. We state several methods for solving this problem within the framework of integer linear programming. For our
algorithmic models, we introduce several new intuitive modeling ideas. We introduce a visibility concept on graphs, which allows di ering computations on the same graph
topology. We also present a preprocessing step which eliminates events lying outside a possible \event horizon". Additionally, we show how the method of graph contraction can be applied to this problem. We also present a formulation for modeling movements on undirected instead of directed edges.
In addition to these optimal methods we present several ILP-based heuristics. Order picker tours can be constrained to shortest-tour \rails". Another heuristic calculates
order picker tours sequentially. The sequence the tours are computed in can be set up by quantifying the conflict potential of each tour. We evaluate our optimal and heuristic methods via experiments. These experiments
show that our algorithms can already solve problem instances of considerable complexity.
Some of the implemented heuristics lead to a speed-up in a magnitude of scale in comparison to the optimal methods, while still providing solutions of high quality.
publication index