×

zbMATH — the first resource for mathematics

Order batching using an approximation for the distance travelled by pickers. (English) Zbl 1441.90015
Summary: In this paper we investigate the problem of order batching for picker routing. Our approach is applicable to warehouses (storage areas) arranged in the standard rectangular grid layout, so with parallel aisles and two or more cross-aisles. The motivation underlying our work is online grocery shopping in which orders may be composed of dozens of items. The approach presented directly addresses order batching, but uses a distance approximation to influence the batching of orders without directly addressing the routing problem.
We present a basic formulation based on deciding the orders to be batched together so as to optimise an objective that approximates the picker routing distance travelled. We extend our formulation by improving the approximation for cases where we have more than one block in the warehouse. We present constraints to remove symmetry in order to lessen the computational effort required, as well as constraints that significantly improve the value of the linear programming relaxation of our formulation. A heuristic algorithm based on partial integer optimisation of our mathematical formulation is also presented. Once order batching has been decided we optimally route each individual picker using a previous approach presented in the literature.
Extensive computational results for publicly available test problems involving up to 75 orders are given for both single and multiple block warehouse configurations.
MSC:
90B06 Transportation, logistics and supply chain management
90C10 Integer programming
90C59 Approximation methods and heuristics in mathematical programming
PDF BibTeX XML 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] Angelelli, E.; Mansini, R.; Speranza, M. G., Kernel search: A general heuristic for the multi-dimensional knapsack problem, Computers & Operations Research, 37, 11, 2017-2026 (2012) · Zbl 1188.90207
[3] Azadnia, A. H.; Taheri, S.; Ghadimi, P.; Saman, M. Z.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, 1-13 (2013)
[4] Boschetti, M. A.; Maniezzo, V.; Roffilli, M.; Rohler, A. B., Matheuristics: Optimization, simulation and control, (Blesa, M. J.; Blum, C.; Di Gaspero, L.; Roli, A.; Sampels, M.; Schaerf, A., (vol.5818 (2009), Springer, Berlin), 171-177)
[5] Boysen, N.; Briskorn, D.; Emde, S., Sequencing of picking orders in mobile rack warehouses, European Journal of Operational Research, 259, 1, 293-307 (2017) · Zbl 1394.90265
[6] Celik, M.; Sutal, H., Order picking in parallel-aisle warehouses with multiple blocks: complexity and a graph theory-based heuristic, International Journal of Production Research, 57, 3, 888-906 (2019)
[7] Chabot, T.; Coelho, L. C.; Renaud, J.; Cote, J.-F., Mathematical model, heuristics and exact method for order picking in narrow aisles, Journal of the Operational Research Society, 69, 8, 1242-1253 (2018)
[8] Chabot, T.; Lahyani, R.; Coelho, L. C.; Renaud, J., Order picking problems under weight, fragility and category constraints, International Journal of Production Research, 55, 21, 6371-6379 (2017)
[9] Chen, F. Y.; Wang, H. W.; Qi, C.; Xie, Y., An ant colony optimization routing algorithm for two order pickers with congestion consideration, Computers & Industrial Engineering, 66, 1, 77-85 (2013)
[10] CPLEX Optimizer (2018). IBM. Available from https://www.ibm.com/products/ilog-cplex-optimization-studio, last accessed 3 March 2019.
[11] De Koster, R.; Le-Duc, T.; Roodbergen, K. J., Design and control of warehouse order picking: a literature review, European Journal of Operational Research, 182, 2, 481-501 (2007) · Zbl 1121.90385
[12] De Koster, R.; van der Poort, E., Routing orderpickers in a warehouse: a comparison between optimal and heuristic solutions, IIE Transactions, 30, 5, 469-480 (1998)
[13] 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
[14] De Santis, R.; Montanari, R.; Vignali, G.; Bottani, E., An adapted ant colony optimization algorithm for the minimization of the travel distance of pickers in manual warehouses, European Journal of Operational Research, 267, 1, 120-137 (2018) · Zbl 1403.90101
[15] Dorigo, M.; Maniezzo, V.; Colorni, A., Ant system: Optimization by a colony of cooperating agents, IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics), 26, 1, 29-41 (1996)
[16] Floyd, R., Algorithm 97: Shortest path., Communications of the ACM, 5, 6, 345 (1962)
[17] Gademann, A. J.R. M.N.; Van Den Berg, J. P.; Van Der Hoff, H. H., An order batching algorithm for wave picking in a parallel-aisle warehouse, IIE Transactions, 33, 5, 385-398 (2001)
[18] 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)
[19] Guastaroba, G.; Savelsbergh, M.; Speranza, M. G., Adaptive kernel search: A heuristic for solving mixed integer linear programs, European Journal of Operational Research, 263, 3, 789-804 (2017) · Zbl 1380.90290
[20] Hall, R. W., Distance approximations for routing manual pickers in a warehouse, IIE Transactions, 25, 4, 76-87 (1993)
[21] Hart, P.; Nilsson, N.; Raphael, B., A formal basis for the heuristic determination of minimum cost paths, IEEE Transactions on Systems Science and Cybernetics, 4, 2, 100-107 (1968)
[22] Henn, S., Algorithms for on-line order batching in an order picking warehouse, Computers & Operations Research, 39, 11, 2549-2563 (2012) · Zbl 1251.90007
[23] Henn, S.; Koch, S.; Wäscher, G., Order batching in order picking warehouses: a survey of solution approaches, (Manzini, R. (2012), Springer London), 105-137)
[24] Henn, S.; Schmid, V., Metaheuristics for order batching and sequencing in manual order picking systems, Computers & Industrial Engineering, 66, 2, 338-351 (2013)
[25] 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
[26] 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
[27] Hong, S.; Johnson, A. L.; Peters, B. A., Large-scale order batching in parallel-aisle picking systems, IIE Transactions, 44, 2, 88-106 (2012)
[28] 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
[29] Article Number: 3931
[30] Kulak, O.; Sahin, Y.; Taner, M. E., Joint order batching and picker routing in single and multiple-cross-aisle warehouses using cluster-based tabu search algorithms, Flexible Services and Manufacturing Journal, 24, 1, 52-80 (2012)
[31] Lam, C. H.Y.; Choy, K. L.; Ho, G. T.S.; Lee, C. K.M., An order-picking operations system for managing the batching activities in a warehouse, International Journal of Systems Science, 45, 6, 1283-1295 (2014) · Zbl 1302.90115
[32] Lin, S.; Kernighan, B. W., An effective heuristic algorithm for the traveling-salesman problem, Operations Research, 21, 2, 498-516 (1973) · Zbl 0256.90038
[33] Lu, W.; McFarlane, D.; Giannikas, V.; Zhang, Q., An algorithm for dynamic order-picking in warehouse operations, European Journal of Operational Research, 248, 1, 107-122 (2016) · Zbl 1346.90148
[34] Marchet, G.; Melacini, M.; Perotti, S., Investigating order picking system adoption: a case-study-based approach, International Journal of Logistics Research and Applications, 18, 1, 82-98 (2015)
[35] 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
[36] Matusiak, M.; de Koster, R.; Saarinen, J., Utilizing individual picker skills to improve order batching in a warehouse, European Journal of Operational Research, 263, 3, 888-899 (2017) · Zbl 1380.90052
[37] Menendez, B.; Bustillo, M.; Pardo, E. G.; Duarte, A., General variable neighborhood search for the order batching and sequencing problem, European Journal of Operational Research, 263, 1, 82-93 (2017) · Zbl 1380.90053
[38] Menendez, 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
[39] Menendez, B.; Pardo, E. G.; Sanchez-Oro, J.; Duarte, A., Parallel variable neighborhood search for the minmax order batching problem, International Transactions in Operational Research, 24, 3, 635-662 (2017) · Zbl 1366.90130
[40] MySQL Foodmart Database (2008). Available from http://pentaho.dlpage.phi-integration.com/mondrian/mysql-foodmart-database (last accessed 24 July 2018).
[41] Padberg, M.; Rinaldi, G., Optimization of a 532-city symmetric traveling salesman problem by branch-and-cut, Operations Research Letters, 6, 1, 1-7 (1987) · Zbl 0618.90082
[42] Padberg, M.; Rinaldi, G., A branch-and-cut algorithm for the resolution of large-scale symmetric traveling salesman problems, SIAM Review, 33, 1, 60-100 (1991) · Zbl 0734.90060
[43] Petersen II, C. G., An evaluation of order picking routeing policies, International Journal of Operations & Production Management, 17, 11, 1098-1111 (1997)
[44] Rao, S. S.; Adil, G. K., Class-based storage with exact S-shaped traversal routeing in low-level picker-to-part systems, International Journal of Production Research, 51, 16, 4979-4996 (2013)
[45] 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
[46] 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
[47] Roodbergen, K. J.; de Koster, R., Routing order pickers in a warehouse with a middle aisle, European Journal of Operational Research, 133, 1, 32-43 (2001) · Zbl 0989.90025
[48] Schloz, A.; Henn, S.; Stuhlmann, M.; Wascher, G., A new mathematical programming formulation for the single-picker routing problem, European Journal of Operational Research, 253, 1, 68-84 (2016) · Zbl 1346.90175
[49] Theys, C.; Bräysy, O.; Dullaert, W.; Raa, B., Using a TSP heuristic for routing order pickers in warehouses, European Journal of Operational Research, 200, 3, 755-763 (2010) · Zbl 1177.90044
[50] Valle, C. A.; Beasley, J. E.; Cunha, A. S., Optimally solving the joint order batching and picker routing problem, European Journal of Operational Research, 262, 3, 817-834 (2017) · Zbl 1375.90025
[51] Van Gils, T.; Ramaekers, K.; Braekers, K.; Depaire, B.; Caris, A., Increasing order picking efficiency by integrating storage, batching, zone picking, and routing policy decisions, International Journal of Production Economics, 197, 243-261 (2018)
[52] Van Gils, T.; Ramaekers, K.; Caris, A.; de Koster, R. B.M., Designing efficient order picking systems by combining planning problems: State-of-the-art classification and review, European Journal of Operational Research, 267, 1, 1-15 (2018) · Zbl 1403.90196
[53] Warshall, S., A theorem on Boolean matrices, Journal of the ACM, 9, 1, 11-12 (1962) · Zbl 0118.33104
[54] Weidinger, F., Picker routing in rectangular mixed shelves warehouses, Computers & Operations Research, 95, 139-150 (2018) · Zbl 06901600
[55] Weidinger, F.; Boysen, N.; Schneider, M., Picker routing in the mixed-shelves warehouses of e-commerce retailers, European Journal of Operational Research, 274, 2, 501-515 (2019) · Zbl 1404.90035
[56] Zulj, I.; Kramer, S.; Schneider, M., A hybrid of adaptive large neighborhood search and tabu search for the order-batching problem, European Journal of Operational Research, 264, 2, 653-664 (2018) · Zbl 1375.90066
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.