×

zbMATH — the first resource for mathematics

A hybrid of adaptive large neighborhood search and tabu search for the order-batching problem. (English) Zbl 1375.90066
Summary: Given a set of customer orders and a routing policy, the goal of the order-batching problem (OBP) is to group customer orders to picking orders (batches) such that the total length of all tours through a rectangular warehouse is minimized. Because order picking is considered the most labor-intensive process in warehousing, effectively batching customer orders can result in considerable savings. The OBP is NP-hard if the number of orders per batch is greater than two, and the exact solution methods proposed in the literature are not able to consistently solve larger instances. To address larger instances, we develop a metaheuristic hybrid based on adaptive large neighborhood search and tabu search, called ALNS/TS. In numerical studies, we conduct an extensive comparison of ALNS/TS to all previously published OBP methods that have used standard benchmark sets to investigate their performance. ALNS/TS outperforms all comparison methods with respect to both average solution quality and run-time. Compared to the state-of-the-art, ALNS/TS shows the clearest advantages on the larger instances of the existing benchmark sets, which assume a higher number of customer orders and higher capacities of the picking device. Finally, ALNS/TS is able to solve newly generated large-scale instances with up to 600 customer orders and six articles per customer order with reasonable run-times and convincing scaling behavior and robustness.

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. S., Variable neighborhood search for order batching in a warehouse, Asia-Pacific Journal of Operational Research, 26, 5, 655-683, (2009) · Zbl 1178.90118
[2] Bozer, Y. A.; Kile, J. W., Order batching in walk-and-Pick order picking systems, International Journal of Production Research, 46, 7, 1887-1909, (2008) · Zbl 1153.90302
[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, 1, 158-167, (2015)
[4] Cheng, C.-Y.; Chen, Y.-Y.; Chen, T.-L.; Yoo, J. J.-W., Using a hybrid approach based on the particle swarm optimization and ant colony optimization to solve a joint order batching and picker routing problem, International Journal of Production Economics, 170, Part C, 805-814, (2015)
[5] Clarke, G.; Wright, J., Scheduling of vehicles from a central depot to a number of delivery points, Operations Research, 12, 4, 568-581, (1964)
[6] Coyle, J. J.; Bardi, E. J.; Langley, J., The management of business logistics. A supply chain perspective, (2002), South-Western College Publishing Mason
[7] Drury, J., Towards more efficient order picking, (1988), The Institute of Materials Management Cranfield
[8] Elsayed, E. A., Algorithms for optimal material handling in automatic warehousing systems, International Journal of Production Research, 19, 5, 525-535, (1981)
[9] Elsayed, E. A.; Unal, O. I., Order batching algorithms and travel-time estimation for automated storage/retrieval systems, International Journal of Production Research, 27, 7, 1097-1114, (1989) · Zbl 0668.90016
[10] Frazelle, E., World-class warehousing and material handling, (2001), McGraw-Hill New York
[11] Gademann, N.; van den Berg, J.; van den Hoff, H., An order batching algorithm for wave picking in a parallel-aisle warehouse, IIE Transactions, 33, 5, 385-398, (2001)
[12] Gademann, N.; van de Velde, S., Order batching to minimize total travel time in a parallel-aisle warehouse, IIE Transactions, 37, 1, 63-75, (2005)
[13] Gendreau, M.; Potvin, J.-Y., Tabu search, (Gendreau, M.; Potvin, J.-Y., Handbook of metaheuristics, International series in operations research & management science, Vol. 146, (2010), Springer US), 41-59
[14] Gibson, D. R.; Sharp, G. P., Order batching procedures, European Journal of Operational Research, 58, 1, 57-67, (1992)
[15] Glover, F., Future paths for integer programming and links to artificial intelligence, Computers & Operations Research, 13, 5, 533-549, (1986) · Zbl 0615.90083
[16] Goetschalckx, M.; Ratliff, H. D., Order picking in an aisle, IIE Transactions, 20, 1, 53-62, (1998)
[17] Grosse, E. H.; Glock, C. H.; Ballester-Ripoll, R., A simulated annealing approach for the joint order batching and order picker routing problem with weight restrictions, International Journal of Operations and Quantitative Management, 20, 2, 65-83, (2014)
[18] Hall, R. W., Distance approximations for routing manual pickers in a warehouse, IIE Transactions, 24, 4, 76-87, (1993)
[19] Henn, S., Algorithms for the on-line order batching in an order picking warehouse, Computers and Operations Research, 39, 11, 2549-2563, (2012) · Zbl 1251.90007
[20] Henn, S.; Koch, S.; Doerner, K. F.; Strauss, C.; Wäscher, G., Metaheuristics for the order batching problem in manual order picking systems, Business Research, 3, 1, 82-105, (2010)
[21] Henn, S.; Koch, S.; Wäscher, G., Order batching in order picking warehouses: A survey of solution approaches, Warehousing in the global supply chain: Advanced models, tools and applications for storage systems, 105-137, (2012), Springer London
[22] Henn, S.; Schmid, V., Metaheuristics for order batching and sequencing in manual order picking systems, Computers & Industrial Engineering, 66, 2, 338-351, (2013)
[23] 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
[24] Hong, S.; Johnson, A. L.; Peters, B. A., Batch picking in narrow-aisle order-picking systems with consideration for picker blocking, European Journal of Operational Research, 221, 3, 557-570, (2012) · Zbl 1253.90009
[25] Hong, S.; Kim, Y., A route-selecting order batching model with the s-shape routes in a parallel-aisle order picking system, European Journal of Operational Research, 257, 1, 185-196, (2017) · Zbl 1394.90089
[26] Hsu, C.-M.; Chen, K.-Y.; Chen, M.-C., Batching orders in warehouses by minimizing travel distance with genetic algorithms, Computers in Industry, 56, 2, 169-178, (2005)
[27] Jarvis, J. M.; McDowell, E. D., Optimal product layout in an order picking warehouse, IIE Transactions, 23, 1, 93-102, (1991)
[28] Koch, S.; Wäscher, G., A grouping genetic algorithm for the order-batching problem in distribution warehouses, Journal of Business Economics, 86, 1, 131-153, (2016)
[29] de Koster, R.; van der Poort, E. S.; Wolters, M., Efficient orderbatching methods in warehouses, International Journal of Production Research, 37, 7, 1479-1504, (1999) · Zbl 0948.90508
[30] de Koster, R.; Tho, L.-D.; Kees, J. R., Design and control of warehouse order picking: A literature review, European Journal of Operational Research, 182, 2, 481-501, (2007) · Zbl 1121.90385
[31] Matusiak, M.; de Koster, R.; Kroon, L.; Saarinen, J., A fast simulated annealing method for batching precedence-constrained customer orders in a warehouse, European Journal of Operational Research, 236, 3, 968-977, (2014) · Zbl 1304.90040
[32] Muter, I.; Öncan, T., An exact solution approach for the order batching problem, IIE Transactions, 47, 7, 728-738, (2015)
[33] Parikh, P. J.; Meller, R. D., Estimating picker blocking in wide-aisle order-picking systems, IIE Transactions, 41, 3, 232-246, (2009)
[34] Petersen, C. G.; Schmenner, R. W., An evaluation of routing and volume-based storage policies in an order picking operation, Decision Sciences, 30, 2, 481-501, (1999)
[35] Ratliff, H. D.; Rosenthal, A. S., Order-picking in a rectangular warehouse: A solvable case of the traveling salesman problem, Operations Research, 31, 3, 507-521, (1983) · Zbl 0523.90060
[36] Ropke, S.; Pisinger, D., An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows, Transportation Science, 40, 4, 455-472, (2006)
[37] Ropke, S.; Pisinger, D., A unified heuristic for a large class of vehicle routing problems with backhauls, European Journal of Operational Research, 171, 3, 750-775, (2006) · Zbl 1116.90019
[38] Schmid, V.; Doerner, K. F.; Laporte, G., Rich routing problems arising in supply chain management, European Journal of Operational Research, 224, 3, 435-448, (2013) · Zbl 1292.90063
[39] Shaw, P., A new local search algorithm providing high quality solutions to vehicle routing problems, Technical report, (1997), University of Strathclyde Glasgow
[40] Tompkins, J. A.; White, J. A.; Bozer, Y. A.; Tanchoco, J. M.A., Facilities planning, (2010), John Wiley & Sons
[41] Tsai, C.-Y.; Liou, J. J.M.; 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
[42] Wäscher, G., Order picking: A survey of planning problems and methods, (Dyckhoff, H.; Lackes, R.; Reeves, J., Supply chain management and reverse logistics, (2004), Springer Berlin), 323-347
[43] Öncan, T., MILP formulations and an iterated local search algorithm with tabu thresholding for the order batching problem, European Journal of Operational Research, 243, 1, 142-155, (2015) · Zbl 1346.90165
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.