×

zbMATH — the first resource for mathematics

Variable neighborhood search strategies for the order batching problem. (English) Zbl 1391.90663
Summary: The order batching problem is an optimization problem belonging to the operational management aspect of a warehouse. It consists of grouping the orders received in a warehouse (each order is composed by a list of items to be collected) in a set of batches in such a way that the time needed to collect all the orders is minimized. Each batch has to be collected by a single picker without exceeding a capacity limit. In this paper, we propose several strategies based on the variable neighborhood search methodology to tackle the problem. Our approach outperforms, in terms of quality and computing time, previous attempts in the state of the art. These results are confirmed by non-parametric statistical tests.

MSC:
90C59 Approximation methods and heuristics in mathematical programming
90B06 Transportation, logistics and supply chain management
90B05 Inventory, storage, reservoirs
Software:
Tabu search
PDF BibTeX Cite
Full Text: DOI
References:
[1] Albareda-Sambola, M.; Alonso-Ayuso, A.; Molina, E.; De Blas, C. S., Variable neighborhood search for order batching in a warehouse, Asia-Pac J Oper Res, 26, 05, (2009) · Zbl 1178.90118
[2] Alvim, Adriana CF; Ribeiro, Celso C; Glover, Fred; Aloise, Dario J, A hybrid improvement heuristic for the one-dimensional bin packing problem, J Heuristics, 10, 2, 205-229, (2004)
[3] Coyle JJ, Bardi EJ, Langley CJ. The management of business logistics, vol. 6. Minneapolis/St. Paul: West Publishing Company; 1996.
[4] De Koster, M. B.M.; Van der Poort, E. S.; Wolters, M., Efficient order batching methods in warehouses, Int J Prod Res, 37, 7, 1479-1504, (1999) · Zbl 0948.90508
[5] De Koster R, Jan Roodbergen K, van Voorden R. Reduction of walking time in the distribution center of de bijenkorf. In: New trends in distribution logistics. Springer Berlin Heidelberg; 1999. p. 215-34. · Zbl 0969.90060
[6] De Koster, R.; Le-Duc, T.; Roodbergen, K. J., Design and control of warehouse order pickinga literature review, Eur J Oper Res, 182, 2, 481-501, (2007) · Zbl 1121.90385
[7] Drury, J., Towards more efficient order picking, IMM Monogr, 1, (1988)
[8] Duarte, A.; Pantrigo, J. J.; Pardo, E. G.; Sánchez-Oro, J., Parallel variable neighbourhood search strategies for the cutwidth minimization problem, IMA J Manag Math, (2013)
[9] Duarte, A.; Pantrigo, J. J.; Pardo, E. G.; Mladenovic, N., Multi-objective variable neighborhood searchan application to combinatorial optimization problems, J Glob Optim, 63, 3, 515-536, (2015) · Zbl 1334.90142
[10] Gademann, N.; Velde, S., Order batching to minimize total travel time in a parallel-aisle warehouse, IIE Trans, 37, 1, 63-75, (2005)
[11] Garey MR, Johnson DS. Computers and intractability: a guide to np-completeness; 1979.
[12] Garey MR, Graham RL, Ullman JD. An analysis of some packing algorithms. In: Combinatorial algorithms (Courant computer science symposium, no. 9; 1972); 1973. p. 39-47.
[13] Ghiani, G.; Laporte, G.; Musmanno, R., Introduction to logistics systems planning and control, (2004), John Wiley & Sons
[14] Gibson, D. R.; Sharp, G. P., Order batching procedures, Eur J Oper Res, 58, 1, 57-67, (1992)
[15] Glover, F.; Laguna, M., Tabu search, (1997), Kluwer Academic Publishers Norwell, MA, USA, [ISBN 079239965X] · Zbl 0930.90083
[16] Goetschalckx, M.; Ratliff, H. D., Order picking in an aisle, IIE Trans, 20, 1, 53-62, (1988)
[17] Gu, J.; Goetschalckx, M.; McGinnis, L. F., Research on warehouse operationa comprehensive review, Eur J Oper Res, 177, 1, 1-21, (2007) · Zbl 1111.90321
[18] Gu, J.; Goetschalckx, M.; McGinnis, L. F., Research on warehouse design and performance evaluationa comprehensive review, Eur J Oper Res, 203, 3, 539-549, (2010) · Zbl 1177.90268
[19] Hall, R. W., Distance approximations for routing manual pickers in a warehouse, IIE Trans, 25, 4, 76-87, (1993)
[20] Hansen, P.; Mladenović, N.; Moreno, P., Variable neighbourhood searchalgorithms and applications, Ann Oper Res, 175, 1, 367-407, (2010) · Zbl 1185.90211
[21] Henn, S.; Wäscher, G., Tabu search heuristics for the order batching problem in manual order picking systems, Eur J Oper Res, 222, 3, 484-494, (2012) · Zbl 1253.90008
[22] Henn, S.; Koch, S.; Doerner, K.; Strauss, C.; Wäscher, G., Metaheuristics for the order batching problem in manual order picking systems, BuR Bus Res J, 3, 1, (2010)
[23] Heragu, S. S., Facilities design, iuniverse, (2006), Lincoln NE
[24] Ho, Y.-C.; Tseng, Y.-Y., A study on order-batching methods of order-picking in a distribution centre with two cross-aisles, Int J Prod Res, 44, 17, 3391-3417, (2006) · Zbl 1094.90505
[25] Hsu, C.-M.; Chen, K.-Y.; Chen, M.-C., Batching orders in warehouses by minimizing travel distance with genetic algorithms, Comput Ind, 56, 2, 169-178, (2005)
[26] Karasek, J., An overview of warehouse optimization, Int J Adv Telecommun Electrotech Signals Syst, 2, 3, 111-117, (2013)
[27] Martí R, Moreno-Vega JM, Duarte A. Advanced multi-start methods. In: Handbook of metaheuristics. Springer US, 2010. p. 265-81.
[28] Menéndez, B.; Pardo, E. G.; Duarte, A.; Alonso-Ayuso, A.; Molina, E., General variable neighborhood search applied to the picking process in a warehouse, Electron Notes Discret Math, 47, 77-84, (2015) · Zbl 1362.90095
[29] Mladenović, N.; Hansen, P., Variable neighborhood search, Comput Oper Res, 24, 11, 1097-1100, (1997) · Zbl 0889.90119
[30] Öncan, T., Milp formulations and an iterated local search algorithm with tabu thresholding for the order batching problem, Eur J Oper Res, (2015) · Zbl 1346.90165
[31] Pan, C.-H.; Liu, S.-Y., A comparative study of order batching algorithms, Omega, 23, 6, 691-700, (1995)
[32] Pardo, E. G.; Mladenović, N.; Pantrigo, J. J.; Duarte, A., Variable formulation search for the cutwidth minimization problem, Appl Soft Comput, 13, 5, 2242-2252, (2013)
[33] Petersen, C. G., An evaluation of order picking routing policies, Int J Oper Prod Manag, 17, 11, 1098-1111, (1997)
[34] Ratliff, H. D.; Rosenthal, A. S., Order-picking in a rectangular warehousea solvable case of the traveling salesman problem, Oper Res, 31, 3, 507-521, (1983) · Zbl 0523.90060
[35] Roodbergen, K. J.; De Koster, R., Routing methods for warehouses with multiple cross aisles, Int J Prod Res, 39, 9, 1865-1883, (2001) · Zbl 1060.90519
[36] Roodbergen KJ, Petersen CG. How to improve order picking efficiency with routing and storage policies. In: Progress in material handling practice; 1999. p. 107-24.
[37] Rosenwein, M. B., A comparison of heuristics for the problem of batching orders for warehouse selection, Int J Prod Res, 34, 3, 657-664, (1996) · Zbl 0926.90007
[38] Wilcoxon, Frank, Individual comparisons by ranking methods, Biometrics bulletin, 1, 6, 80-83, (1945)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.