Theory and MethodologyRouting order pickers in a warehouse with a middle aisle
Introduction
In warehouses and distribution centers, products have to be picked from specified storage locations on the basis of customer orders. In general, the order picking process is the most laborious of all warehouse processes. Furthermore, it typically amounts to 55% of all warehouse operating expenses (see e.g. Tompkins et al., 1996). One way to achieve savings in equipment and the number of order pickers is by optimizing order picking tours. Given that the order picker has to collect a number of products in specified quantities at known locations, the question is in what sequence the order picker should visit these locations in order to minimize the distance traveled?
The basic warehouse layout is one with parallel aisles, a central depot, and possibilities for changing aisles at the front and rear of the warehouse. Such a warehouse is said to have two cross aisles, that is two possibilities to go from one aisle to another aisle. The problem of finding shortest order picking tours for a warehouse with basic layout can be solved in running time linear in the number of aisles and the number of pick locations, see Ratliff and Rosenthal (1983).
In practice, the problem of finding order picking tours in a warehouse is mainly solved by the so-called S-shape heuristic in which order pickers move in a S-shape curve along the pick locations skipping the aisles where nothing has to be picked. More advanced heuristics are considered in Hall (1993). Performance comparisons between heuristics and the optimal algorithm are given in Petersen, 1997, De Koster and Van der Poort, 1998.
In this paper, we construct a routing algorithm for a warehouse, where aisle changing is possible at the front, the rear, and in the middle of the warehouse (a warehouse with three cross aisles). This type of layout is fairly common in practice, but finding a shortest order picking tour is not possible with the existing algorithm for the basic layout. Other methods to determine order picking tours in a warehouse with three cross aisles include branch-and-bound (see e.g. Little et al., 1963) or heuristic methods (see Vaughan and Petersen, 1999). This paper describes an efficient algorithm to determine the shortest order picking tours. Furthermore, we compare average travel time in warehouses of basic layout to average travel time in warehouses with a middle aisle. It is shown that average travel time often is lower in warehouses with a middle aisle.
In Section 2, we model the warehouse and order picking locations using graph theory. A dynamic programming formulation is given in Section 3 to solve the problem of finding a shortest order picking tour. In Section 4, we compare average tour length in warehouses with a middle aisle to the average tour length in similar warehouses without a middle aisle. Section 5 contains concluding remarks.
Section snippets
The warehouse
A warehouse consists of a number of parallel aisles. The items are stored on both sides of the aisles. Order pickers are assumed to be able to traverse the aisles in both directions and to change direction within the aisles. Each order consists of a number of items that are usually spread out over a number of aisles. We assume that the items of an order can be picked in a single tour. Aisle changes are possible at the front end, the rear end, and in the middle of the aisles. Picked orders have
Finding a shortest tour subgraph
Let Lj− be the subgraph of the warehouse graph, consisting of vertices aj, bj, and cj together with all edges and vertices to the left of aj, bj, and cj. Let Yj be the subgraph of the warehouse graph consisting of vertices bj and cj together with all edges and vertices between bj and cj and define Lj+y=Lj−∪Yj. Similarly, let Xj be the subgraph of the warehouse graph consisting of vertices aj and bj together with all edges and vertices between aj and bj and define Lj+x=Lj+y∪Xj. We use Lj to
Performance comparison
In this section, a performance comparison is made between warehouses with a middle aisle and warehouses without a middle aisle. In order to compare the two types of warehouse layouts, we use simulation to determine the average travel time needed to pick an order. However, average travel time is not only influenced by the presence or absence of a middle aisle, but also by factors like warehouse type, warehouse size, number of aisles, location of the depot, order picking equipment, picklist size,
Concluding remarks
Average travel time in warehouses depends on many factors such as warehouse type, warehouse size, number of aisles, location of the depot, order picking equipment, picklist size and storage assignment rules. Each of these factors may have a significant influence on travel time. In this paper, we have evaluated the impact on average travel time of warehouse layout. Specifically, we evaluated whether or not a middle aisle could improve the efficiency. To this end, we have constructed a dynamic
References (7)
- et al.
Routing orderpickers in a warehouse: A comparison between optimal and heuristic solutions
IIE Transactions
(1998) Distance approximations for routing manual pickers in a warehouse
IIE Transactions
(1993)- et al.
An algorithm for the traveling salesman problem
Operations Research
(1963)