© Strojni{ki vestnik 50(2004)11,530-535 © Journal of Mechanical Engineering 50(2004)11,530-535 ISSN 0039-2480 ISSN 0039-2480 UDK 658.78 UDC 658.78 Pregledni znanstveni ~lanek (1.02) Review scientific paper (1.02) Zaporedje prevzema naro~il: navadna hevristika, izbolj{ana hevristika in optimalni algoritem Order-Picking Routing Policies: Simple Heuristics, Advanced Heuristics or Optimal Algorithm Goran Duki} - ^edomir Olui} Prevzem naročila je postopek zbiranja in priprave izdelkov v skladišču, glede na določeno naročilo kupca. Je najbolj težavna in draga dejavnost v skladišču. Za prevoz porabimo 50 odstotkov celotnega časa prevzema naročila. Zmanjšanje prevoznih poti je eden glavnih ciljev načrtovalca skladišča.V prispevku smo predstavili obširne simulacijske analize načrtovanja poti in razporeditve polic s primerjavami hevrističnih metod načrtovanja poti in optimalnim algoritmom © 2004 Strojniški vestnik. Vse pravice pridržane. (Ključne besede: skladišča, prevzemi naročil, načrtovanja poti, skladiščenje) Order-picking, the process of retrieving items from storage locations in response to a specific customer request, is the most laborious and the most costly activity in a typical warehouse. As 50% of the total order-picking time is spent on traveling, reducing travel distances is one of a warehouse designers objectives. In this paper an extensive simulation analysis of routing and storage policies in order-picking systems is presented. The best combinations of routing and storage policies are defined with a comparison between routing heuristics and an optimal algorithm. © 2004 Journal of Mechanical Engineering. All rights reserved. (Keywords: warehouses, order-picking, routing policies, storage policies) 0 INTRODUCTION It is well known that logistic costs have an important influence on the overall success of any company. In western countries these costs are estimated to be about 10 to 15% of GDP. Mostly they are the result of the two main logistics activities: transportation and warehousing. The order-picking process, defined as the process of retrieving items from storage locations in response to a specific customer request, is the most laborious and the most costly activity in a typical warehouse, consisting of up to 55% of the warehouse’s total operating costs [11]. The fact that about 50% of the total order-picking time is spent on traveling gives the potential to improve order-picking efficiency by reducing traveling distances. One way to reduce traveling times is an entirely new design (new equipment, new layout, automation of processes). Hopefully, there are also some less radical methods, that do not require large investment costs. Using a specific routing policy in determining the sequences and routes of traveling is one way to reduce traveling distances. Assigning items to storage locations based on some rule, i.e., a storage policy, can also reduce traveling distances compared to a random assignment. Both have been proven, used separately or in combination, to improve the efficiency of the order-picking process. However, the performances of existing methods depend greatly on the layout and size of the warehouse, the size of orders and the picking volume of items. Additionally, the performance of a particular routing method depends on the chosen storage policy, and vice versa, the potential travelling- time savings using a particular storage policy are not the same for all routing policies. The purpose of this paper is to identify the performances of routing policies, depending on the given situation and the implemented storage policy. The analysis is restricted to conventional warehouses with the so-called basic warehouse layout. These are rectangular warehouses with 1 BnnBjfokJ][p)l]Olf|ifrSO | | ^SsFÜWEIK | stran 530 Duki} G., Olui} ^.: Zaporedje prevzema naro~il - Order-Picking Routing Policies parallel aisles, a central depot (pick up/delivery point), and two possibilities for changing aisles, at the front and at the rear of the warehouse. The picking aisles (the main aisles) are wide enough to allow two-way travel, but picking can be done from both sides of the aisle without a significant change in position. The location of a depot (pick-up/delivery point) is at the front corner of the warehouse. This is consistent with observations of several similar studies presented in the literature [2], [7] and [10]. 1 ROUTING POLICIES IN ORDER-PICKING There are several routing policies developed and used in practice. They range from the very simple to the slightly more complex. The performance of these heuristics depends on the particular operating conditions of the system under study, as a result of their definitions. The simplest routing heuristic is the S-shape policy. When this policy is used, the order-picker enters every aisle where an item has to be picked and traverses the entire aisle. Aisles where nothing has to be picked are skipped. An exception is made for the last aisle visited in the case that the number of aisles to be visited is odd. In this case a return travel is performed in the last aisle visited. Another very simple routing heuristic is the Return policy. The order-picker enters and leaves aisles con-taining item(s) to be picked from the front aisle. The midpoint routing policy, also one simple heuristics, looks like the return method on two halves of a ware-house. Only the first and the last aisle visited are traversed entirely. Similar to the last heuristic, with the Largest Gap policy all the aisles that contain even one item to be picked are also left at the same side as they were entered, except the first and the last vis-ited, which are traversed entirely. The gap represents the separation between any two adjacent picks, be-tween the first pick in the aisle and the front aisle, or between the last pick in the aisle and the back aisle. If the largest gap is between two adjacent picks, the picker performs a return route from both ends of the aisle. Otherwise, a return route from either the front or back aisle is used. The largest gap is therefore the portion of the aisle that the order-picker does not traverse. This policy is a slightly more complex routing heuristic than the first three mentioned. The re-sulting route is somehow similar, but definitely at least equal or better than the route defined by the Midpoint policy in all possible situations. Two rela-tively new policies developed are the Composite policy and the Combined policy. The Composite routing heuristic combines features of the S-shape and Return heuristics, minimizing the travel distance be-tween the farthest picks in two adjacent aisles for each aisle individually. Combined heuristics is also a combi-nation of S-shape and Return policies, but a small com-ponent of dynamic programming gives it a possibility to look one aisle ahead. The decision about the return or the traversal route in the aisle depend not only on minimized travel in that aisle, but also on a better start-ing point for the next aisle. This in turn leads to a better overall result than the Composite heuristic. All the routing policies described above by their definitions have some restrictions when if comes to creating a route. An optimal algorithm [9], combining a graph theory and dynamic programming, results in the shortest pos-sible, i.e., the optimal, route. Examples of routes cre-ated by these routing heuristics and an optimal algo-rithm are given in Figure 1. «*¦-- &*-¦ S-shape I : -' U De pot Return Midpoint Largest Gap Composite/Combined Optimal Fig. 1. Examples of routes using routing heuristics and the optimal algorithm gnn^nwiRaieKE 04-11 stran 531 |^BSSITIMIGC Depot Depot Depot Duki} G., Olui} ^.: Zaporedje prevzema naro~il - Order-Picking Routing Policies Even with the optimal algorithm developed, the majority of order-picking operations use heuristic routing policies [7]. The reason for this is that heuristic policies can provide near-optimal solutions and avoid the confusion inherent in optimal solutions [5]. It is true that a specific heuristic policy could in some situations result in a near-optimal route, but in some other situations it could perform badly. Therefore, it is important to know in which situations some heuristics are good or bad. Even more, which are better than others, and how much better in particular situations. 2 STORAGE POLICIES IN ORDER-PICKING Storage policies assign items to warehouse storage locations, based on popularity, demand, size, hazard etc. In order-picking systems, storage policies are solely based on the rule of assigning the frequently accessed items to the locations near the depot [3]. With a volume-based storage policy items are assigned to storage locations based on the expected volume. Large savings in travel distances are possible with volume-based storage when compared to random storage [8]. The most effective storage policy in reducing the picking travel distance seems to be the cube-per-order-index-based storage policy [4]. The COI-based storage policy means assigning items with a low ratio of the required storage space to the order frequency to the locations nearest to the p/d point. With the assumption that each type of item is dedicated to only one location, volume-based storage and COI-based storage are the same. When warehouses are divided into forward and reserve areas (picking operations are in the forward area, items are replenished from the reserve area), such a situation is likely to occur. One can also use different types (patterns) of storage, as shown in Figure 2. Items with a higher volume (or smaller COI) are stored in the darker locations. With diagonal storage, the highest volume item is stored in the location closest to the depot, while the lowest volume item is stored in the farthest location from the depot. Tompkins et al., 1996, states that this type of storage is optimal. Within-aisle storage means that high-volume items are stored in the aisle closest to the depot and the low-volume items are stored in the aisle farthest from the depot. Jarvis & McDowell [6] proposed this type of storage for an S-shape routing policy, which was confirmed by Petersen & Schmenner [8]. In along-front-aisle (across-aisle) storage, the high-volume items are stored along the front aisle and the low-volume items along the rear aisle. Caron et al. [1] used this type of storage with a Return routing policy. As the Midpoint and Largest Gap routing policies are characterized by return traveling from both the front and rear aisles, a potentially good type of storage for these routing policies could be along-front and rear-aisle storage. 3 THE COMPARISON OF ROUTING POLICIES The comparison of routing policies and their interactions with storage policies is based on an extensive analysis made by simulation. The pick size varied from 5, 10, 15, 20, 30 and 40 picks per route. Two different warehouses, with respect to their size (small and large), with four different layouts, with respect to the shape (the ratio of width and depth were 2:1, 1:1, 1:2 and 3:1, for more explanation readers are referred to [7]) were analysed. This gives 48 different situations examined for each combination of routing and storage policy. In order to explain the potential savings using the storage policies, we first present an analysis of the routing policies with random storage. The results are partly illustrated in Figure 3. The graph shows the performances of routing policies depending on the pick-list size for one examined layout. Two routing policies, Midpoint heu-ristic and Composite heuristic, are excluded from the presentation because they are very similar, but slightly worse, than two other analysed policies, Larg-est Gap and Combined heuristic, respectively. Note that despite the fact that the Composite heuristic is outperformed by the Combined heuristics, it is still generally better than simple heuristics. The Return routing policy was outperformed by all the other routing policies in all the simulated situations, while the difference increases as the pick-list size increases i 111S a) diagonal type b) within aisle type Fig. 2. The types of volume-based storage c) along front aisle type d) along front and rear aisle type 1 BnnBjfokJ][p)l]Olf|ifrSO I | ^SsFÜWEIK | stran 532 Duki} G., Olui} ^.: Zaporedje prevzema naro~il - Order-Picking Routing Policies 190 150 110 70 ¦+- S-shape -¦-Return -*- Largest Gap -*- Combined -*- Optimal 10 20 30 Pick list size 40 Number of aisles: 6 Length of an aisle: 12 m Width of front and rear aisle: 3 m Distance between two adjascent aisles: 4 m Fig. 3. Comparison of routing policies and the interaction with pick-list size for random storage (but note that this policy could be beneficial in terms of some other aspects, for instance, the total space required, as there is no need for a rear aisle). The S-shape routing policy is just a few percent over the optimal in the case of a large number of picks, but does not perform well with small pick-list sizes. In contrast, the Largest Gap policy performs well with small pick sizes (about 5% over the optimal policy), while it is not so good in the case of a large number of picks. The Combined policy is, in general, the best heuristic policy. It is slightly outperformed only by Largest Gap policy in situations with a very small number of picks in a large warehouse (long aisles). For a small number of picks per tour, the best heuris-tic policy for a given situation is only 5–10% over the optimal policy, depending on the shape of the ware-house. The difference between the optimal and the best heuristics in the case of a large number of picks per tour is neglected. To compare the routing policies with volume-based storage, the best type of storage for a particular routing policy should be determined. The simulation analysis included four different volume-based ABC curves, denoted as 50/20, 60/20, 70/20, 80/20 (the first number indicates the percentage of the total activity corresponding to items indicated in the percentage by the second number). Caron et al. [1] presented a simple function that describes well the COI-based ABC curve F(x) = (1 + s) ¦ x (1) where x indicates the ratio of the required storage space to total storage space, corresponding to the items whose order frequency represents a fraction F(x) of the total warehouse activity. The function above depends on a single parameter – the shape factor s. Note that with each type of items stored in only one location, the COI-based ABC curve is identical to the volume-based ABC curve. For an S-shape routing policy, where the order-picker entirely traverses each aisle containing a pick location(s), it is obvious that within-aisle storage will minimize the travel distance – minimizing both the “within-aisles” travel component (minimizing the visited number of aisles) and the “across-aisle” component (minimizing the furthest aisle visited). With Return policy, to minimize the “within-aisle” travel component an across-aisle storage is used. Within-aisle storage minimizes the “across aisle” travel component and the expected number of visited aisles, but due to the increased number of picks per visited aisle (increased travel per visited aisle) the total amount of travel distance reduction with the Return policy is questionable. Finally, somewhere between is diagonal storage, decreasing to the some degree the “across-aisle” component, expected travel within the visited aisles and the number of visited aisles. Petersen & Schmenner [8] proposed this type of storage for the Return policy. To determine the best type of storage for Return routing policy all three mentioned types were analyzed. The results showed that the within-aisle type of storage is outperformed either by diagonal or across-aisle storage, depending on the pick-list size, the skewness of the ABC curve and the size of the warehouse. With a large number of picks and a less-skewed ABC curve one should prefer across-aisle storage, while for smaller orders and a more-skewed ABC curve the diagonal storage is preferable. As the size of a warehouse increases, the preference region for across-aisle storage increases. With the Largest Gap routing policy, within-aisle storage also minimizes the “across-aisle” travel component and the expected number of visited aisles. Like the Return policy, an increased number of picks per visited aisle leads to a reduced largest gap in the aisle, and therefore increased travel within such aisles. Travel within aisles could be reduced using an across aisle type of storage. As the order-picker enters the aisles from the front and rear aisles, depending on gnn^dfefflRIEeKE 04-11 stran 533 |^BSSIrTMlGC Duki} G., Olui} ^.: Zaporedje prevzema naro~il - Order-Picking Routing Policies the position of the largest gap, it is logical to expect that along the front and rear aisle type of storage will result in better performance. However, these two types of storage have no influence on the number of visited aisles and the “across-aisle” travel component. Diagonal storage is again a good candidate, influencing both the “across-aisle” travel and travel within the visited aisle. The simulation results have confirmed that storing “fast movers” along front and rear aisles is better than storing them along just the front aisle. However, the diagonal storage policy generally performed better. The best type was, in any case, within-aisle storage, in all the examined situations. The routes created by Combined and Optimal routing policies are a mix of traversal and return travel (from one or both ends, respectively). Therefore, the within-aisle type seems to be the best storage type for those routing policies [8]. Additionally, diagonal storage was analyzed too. With the Combined routing policy, within-aisle storage is preferable in the case of a larger number of picks, irrespective of the skewness of the ABC curve. With just a few picks per tour, diagonal storage performs better. For the optimal algorithm the best type of storage is definetely within-aisle storage. The simulation results, partly illustrated in Figure 4., showed that all volume-based storage methods provide travel savings over random storage. Large savings (45 to 55%) are possible in the case of a small number of picks and more-skewed ABC curves, while for less-skewed curves and large pick lists the advantage of using volume-based stor-age is diminished (only a few to 15%, depending on the routing policy). The Return routing policy is no longer inferior to other heuristics in all situations. With a small number of picks and more-skewed curves it could outperform the S-shape and the Largest Gap policies. Also, the decision factor between using the S-shape or the Largest Gap routing policy is no longer only the average number of picks per (visited) aisle, but also the skewness of the ABC curve. For an 80/20 ABC curve, the Largest Gap routing performs as well as the Combined heuristic, even for a very large number of picks. Generally, the Combined policy is still the best routing heuristic. The correctly selected simple heuristic with an appropriate type of volume-based storage results in travel distances that are only 4–8% over the optimal route. Combined heuristics is even better, with only 1–5% over the optimal travel, depending on the pick-list size and the skewness of the ABC curve. 4 CONCLUSIONS Even with the optimal algorithm developed, many manual warehouses apply very simple rules for routing order-pickers [10]. The performance of such methods heavily depends on the situation, regard-ing the size and the shape of the warehouse and the size of the pick lists. The correctly selected routing heuristic could result in routes that are only a few percents over the optimal route. On the other hand, bad decisions regarding routing policy could lead to very inefficient order-picking. With storage assign-ment involved, the right selection is even more com-plex. Even though all volume-based storage meth-ods reduce the travel distances of order-pickers, each routing policy has its own best type of storage for a particular situation. Choosing the best combination of routing and storage policies is therefore a crucial task in improving order-picking efficiency. The optimal algorithm with within-aisle storage is definitely the best choice. However, it one seeks to avoid the possible confusions of order-pickers following the optimal routes, the near-optimal solutions are also available. Even the simplest routing heuristics in com-bination with a “belonging” type of storage could, in some situations, result in routes that are not more than a few percent over the optimal. Finally, it should be noted that the analysis was restricted to the manual, narrow-aisle warehouses with only one block. Having one or more cross-aisles 160 135 110 85 60 -*- S-shape -¦-Return ^- Largest Gap -k- Combined -*- Optimal 10 15 20 25 30 Pick list size 35 40 45 Number of aisles: 6 Length of an aisle: 12 m Width of front and rear aisle: 3 m Distance between two adjascent aisles: 4 m ABC curve: 80/20 Fig. 4. Comparison of routing policies with volume-based storage and the interaction with pick-list size 1 BnnBjfokJ][p)l]Olf|ifrSO | | ^SsFÜWEIK | stran 534 0 5 Duki} G., Olui} ^.: Zaporedje prevzema naro~il - Order-Picking Routing Policies (two or more blocks) in some situations could de-crease travel distances. If the aisles are wide, the traversal travel has to include crossovers from one side of the aisle to the other. As a consequence, the preferences of some routing policies (and combina-tions with storage policies) could be changed with respect to other. Also, the paper was focused on only two order-picking methods: routing and storage. Batching, grouping the customer orders into one pick-ing order; and zoning, dividing the picking area into zones, are also proven to improve the order-picking efficiency. If used, one should be aware of the possi-ble interactions of order-batching and zoning meth-ods with routing and storage policies. 5 REFERENCES [1] Caron, F., G. Marchet & A. Perego (1998, Routing policies and COI-based storage policies in picker-to part systems. International Journal of Production Research, 36(3), 713-732. Chew, E.P. & L.C. Tang (1999) Travel time analysis for general item location assignment in a rectangular warehouse. European Journal of Operational Research, 122, 582-597. Choe, K.I. & G.P. Sharp (1991) Small parts order picking: design and operation. Technical Report, Georgia Tech Research Corporation, Atlanta, Georgia. Gibson, D.R. & G.P. Sharp (1992) Order batching procedures. European Journal of Operational Research, 58, 57-67. Hall, R.W. (1993) Distance approximations for routing manual pickers in a warehouse. IIE Transactions, 25(4), 76-87. Jarvis, J.M. & E.D. McDowell (1991) Optimal product layout in an order picking warehouse. IIE Transactions, 23(1), 93-102. Petersen, CG. (1997) An evaluation of order picking routeing policies. International Journal of Operations & Production Management, 17(1), 1098-1111. Petersen, CG & R.W. Schmenner (1999) An evaluation of routing and volume-based storage policies in an order picking operations, Decision Sciences, 30(2), 481-501. Ratliff, H.D. & A.S. Rosenthal (1983) Order-picking in a rectangular warehouse: a solvable case of the travelling salesman problem. Operations Research, 31(3), 507-521. [10] Roodbergen, K.J. & CG. Petersen (1999) How to improve order picking efficiency with routing and storage policies. In: Forger, G.R. et al., Perspectives in Material Handling Practice (107-124), Charlotte, North Carolina: Material Handling Institute. [11] Tompkins, JA., JA. White., YA. Bozer, E.H. Frazelle, J.M.A. Tanchoco, & Trevino (1996) Facilities planning, John Wiley & Sons, New York. Authors’ Address:Dr. Goran Dukič ProfDr.Čedomir Oluič University of Zagreb Faculty of Mechanical Eng. and Naval Architecture Ivana Lučiča 1 10000 Zagreb, Croatia goran.dukic@fsb.hr [2] [3] [4] [5] [6] [7] [8] [9] Prejeto: Received: 4.6.2004 Sprejeto: Accepted: 30.9.2004 Odprto za diskusijo: 1 leto Open for discussion: 1 year stran 535 bcšd04