×

zbMATH — the first resource for mathematics

General variable neighborhood search for the order batching and sequencing problem. (English) Zbl 1380.90053
Summary: Warehousing has been found as an essential issue by the industry in the last few years, being a key part of the supply chain management. It mainly focuses its attention on moving and storing materials in warehouses by performing different activities such as shipping, receiving, and picking operations. The profits obtained by warehouse management systems strongly depends on how customer orders, containing a set of goods, are collected. This picking process consists in collecting goods (items) before shipment to satisfy the orders of the customers. the order batching and sequencing problem (OBSP) involves the process of collecting orders in a warehouse by grouping orders into batches with a maximum fixed capacity. In the context of the OBSP, each order has a certain due date, i.e., it must be collected before a specific time. Otherwise, it has associated a tardiness penalty. The problem then consists in grouping orders into batches, sequencing the batches and finding a route to collect each batch, in such a way that the total tardiness is minimized. In this paper, we propose a heuristic approach based on the variable neighborhood search methodology to address the problem. Additionally, we provide an extensive experimental comparison between our procedure and the best previous method found in the related literature. The experimentation reveals that our algorithm improves the state of the art in both, quality and computing time. This fact is finally confirmed by non-parametric statistical tests.

MSC:
90B06 Transportation, logistics and supply chain management
90C59 Approximation methods and heuristics in mathematical programming
PDF BibTeX Cite
Full Text: DOI
References:
[1] Albareda-Sambola, M.; Alonso-Ayuso, A.; Molina, E.; De Blas, C., Variable neighborhood search for order batching in a warehouse, Asia-Pacific Journal of Operational Research, 26, 05, (2009) · Zbl 1178.90118
[2] Chen, M.-C.; Wu, H.-P., An association-based clustering approach to order batching considering customer demand patterns, Omega, 33, 4, 333-343, (2005)
[3] Chen, T.-L.; Cheng, C.-Y.; Chen, Y.-Y.; Chan, L.-K., An efficient hybrid algorithm for integrated order batching, sequencing and routing problem, International Journal of Production Economics, 159, 158-167, (2015)
[4] De Koster, M. B.M.; Van der Poort, E. S.; Wolters, M., Efficient order batching methods in warehouses, International Journal of Production Research, 37, 7, 1479-1504, (1999) · Zbl 0948.90508
[5] De Koster, R.; Roodbergen, K.; van Voorden, R., Reduction of walking time in the distribution center of de bijenkorf, New trends in distribution logistics, 215-234, (1999), Springer · Zbl 0969.90060
[6] Drury, J., Towards more efficient order picking, IMM Monograph, 1, (1988)
[7] Du, J.; Leung, J. Y.-T., Minimizing total tardiness on one machine is NP-hard, Mathematics of operations research, 15, 3, 483-495, (1990) · Zbl 0714.90052
[8] Duarte, A.; Pantrigo, J.; Pardo, E.; Sánchez-Oro, J., Parallel variable neighbourhood search strategies for the cutwidth minimization problem, IMA Journal of Management Mathematics, 27, 1, 55-73, (2016) · Zbl 1433.90132
[9] Duarte, A.; Pantrigo, J.; Pardo, E. G.; Mladenović, N., Multi-objective variable neighborhood search: an application to combinatorial optimization problems, Journal of Global Optimization, 63, 3, 515-536, (2015) · Zbl 1334.90142
[10] Elsayed, E.; Lee, M.-K., Order processing in automated storage/retrieval systems with due dates, IIE Transactions, 28, 7, 567-577, (1996)
[11] Elsayed, E. A.; Lee, M.-K.; Kim, S.; Scherer, E., Sequencing and batching procedures for minimizing earliness and tardiness penalty of order retrievals, The International Journal of Production Research, 31, 3, 727-738, (1993)
[12] Gademann, N.; Velde, S., Order batching to minimize total travel time in a parallel-aisle warehouse, IIE Transactions, 37, 1, 63-75, (2005)
[13] Glover, F., Ejection chains, reference structures and alternating path methods for traveling salesman problems, Discrete Applied Mathematics, 65, 1, 223-253, (1996) · Zbl 0846.90117
[14] Goetschalckx, M.; Ratliff, H. D., Order picking in an aisle, IIE Transactions, 20, 1, 53-62, (1988)
[15] Hansen, P.; Mladenović, N.; Moreno, J. A., Variable neighbourhood search: methods and applications, 4OR, 6, 4, 319-360, (2008) · Zbl 1179.90332
[16] Henn, S., Algorithms for on-line order batching in an order picking warehouse, Computers & Operations Research, 11, 2549-2563, (2012) · Zbl 1251.90007
[17] Henn, S., Order batching and sequencing for the minimization of the total tardiness in picker-to-part warehouses, Flexible Services and Manufacturing Journal, 27, 1, 86-114, (2015)
[18] Henn, S.; Koch, S.; Doerner, K.; Strauss, C.; Wäscher, G., Metaheuristics for the order batching problem in manual order picking systems, BuR Business Research Journal, 3, 1, 82-105, (2010)
[19] Henn, S.; Schmid, V., Metaheuristics for order batching and sequencing in manual order picking systems, Computers & Industrial Engineering, 66, 2, 338-351, (2013)
[20] Henn, S.; Wäscher, G., Tabu search heuristics for the order batching problem in manual order picking systems, European Journal of Operational Research, 222, 3, 484-494, (2012) · Zbl 1253.90008
[21] Hoos, H.; Stützle, T., Stochastic local search: foundations & applications, (2004), Morgan Kaufmann Publishers Inc San Francisco, CA, USA · Zbl 1126.68032
[22] Hossein, A. H.; Shahrooz, T.; Pezhman, G.; Saman, M.; Zameri, M.; Wong, K.-Y., Order batching in warehouses by minimizing total tardiness: A hybrid approach of weighted association rule mining and genetic algorithms, The Scientific World Journal, 2013, 1-13, (2013)
[23] Menéndez, B.; Pardo, E. G.; Alonso-Ayuso, A.; Molina, E.; Duarte, A., Variable neighborhood search strategies for the order batching problem, Computers & Operations Research, 78, 500-512, (2017) · Zbl 1391.90663
[24] Menéndez, B.; Pardo, G. E.; Sánchez-Oro, J.; Duarte, A., Parallel variable neighborhood search for the MIN-MAX order batching problem, International Transactions in Operational Research, 24, 3, 635-662, (2017) · Zbl 1366.90130
[25] Mladenović, N.; Hansen, P., Variable neighborhood search, Computers & Operations Research, 24, 11, 1097-1100, (1997) · Zbl 0889.90119
[26] Pardo, E. G.; Mladenović, N.; Pantrigo, J. J.; Duarte, A., Variable formulation search for the cutwidth minimization problem, Applied Soft Computing, 13, 5, 2242-2252, (2013)
[27] Pérez-Rodríguez, R.; Hernández-Aguirre, A.; Jöns, S., A continuous estimation of distribution algorithm for the online order-batching problem, International Journal of Advanced Manufacturing Technology, 79, 569-588, (2013)
[28] Roodbergen, K. J.; De Koster, R., Routing methods for warehouses with multiple cross aisles, International Journal of Production Research, 39, 9, 1865-1883, (2001) · Zbl 1060.90519
[29] Tsai, C.-Y.; Liou, J. J.; Huang, T.-M., Using a multiple-ga method to solve the batch picking problem: considering travel distance and order due time, International Journal of Production Research, 46, 22, 6533-6555, (2008) · Zbl 1154.90381
[30] Wilcoxon, F., 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.