MILP formulations and an iterated local search algorithm with tabu thresholding for the order batching problem. (English) Zbl 1346.90165
Summary: In this work we deal with the Order Batching Problem (OBP) considering traversal, return and midpoint routing policies. For the first time, we introduce Mixed Integer Linear Programming (MILP) formulations for these three variants of the OBP. We also suggest an efficient Iterated Local Search Algorithm with Tabu Thresholding (ILST). According to our extensive computational experiments on standard and randomly generated instances we can say that the proposed ILST yields an outstanding performance in terms of both accuracy and efficiency.
Keywords:
warehouse management; order batching problem; mixed integer linear programming; local searchReferences:
| [1] | Aiex, R. M.; Resende, M. G.C.; Ribeiro, C. C., TTT plots: A perl program to create time-to-target plots, Optimization Letters, 1, 355-366 (2007) · Zbl 1220.90102 |
| [2] | Albareda-Sambola, M.; Alonso-Ayuso, M.; Molina, E.; Simon de Blas, C., Variable neighborhood search for order batching in a warehouse, Asia-Pacific Journal of Operational Research, 26, 5, 655-683 (2009) · Zbl 1178.90118 |
| [3] | Baker, P.; Canessa, M., Warehouse design: A structured approach, European Journal of Operational Research, 193, 425-436 (2009) |
| [4] | 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 |
| [5] | Carpaneto, G.; Martello, S.; Toth, P., Algorithms and codes for the assignment problem, Annals of Operations Research, 13, 193-223 (1988) |
| [6] | Chen, M.-C.; Huang, C.-L.; Chen, K.-Y.; Wu, H.-P., Aggregation of orders in distribution centers using data mining, Expert Systems with Applications, 28, 3, 453-460 (2005) |
| [7] | Chen, M.-C.; Wu, H.-P., An association-based clustering approach to order batching considering customer demand patterns, Omega—The International Journal of Management Science, 33, 4, 333-343 (2005) |
| [8] | Clarke, G.; Wright, J. W., Scheduling of vehicles from a central depot to a number of delivery points, Operations Research, 12, 4, 568-581 (1964) |
| [9] | 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, 481-501 (2007) · Zbl 1121.90385 |
| [10] | de Koster, R.; Van Der Poort, E.; Wolters, M., Efficient order batching methods in warehouses, International Journal of Production Research, 37, 7, 1479-1504 (1999) · Zbl 0948.90508 |
| [12] | Elsayed, E. A., Algorithms for optimal material handling in automatic warehousing systems, International Journal of Production Research, 19, 5, 525-535 (1981) |
| [13] | Gademann, N.; Van den Berg, J.; Hoff, H., An order batching algorithm for wave picking in a parallel-aisle warehouse, IIE Transactions, 33, 5, 385-398 (2001) |
| [14] | 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) |
| [15] | Gibson, D. R.; Sharp, G. P., Order batching procedures, European Journal of Operational Research, 58, 57-67 (1992) |
| [16] | Glover, F., Tabu thresholding: Improved search by nonmonotonic trajectories, ORSA Journal on Computing, 7, 426-442 (1995) · Zbl 0843.90097 |
| [17] | Goetschalckx, M.; Ratliff, H. D., Order picking in an aisle, IIE Transactions, 20, 1, 53-62 (1998) |
| [18] | Gong, Y.; de Koster, R. B.M., A review on stochastic models and analysis on warehouse operations, Logistics Research, 3, 4, 191-205 (2013) |
| [19] | Gu, J.; Goetschalckx, M.; McGinnis, L., Research on warehouse operation: A comprehensive review, European Journal of Operational Research, 177, 1-21 (2007) · Zbl 1111.90321 |
| [20] | Gu, J.; Goetschalckx, M.; McGinnis, L., Research on warehouse design and performance evaluation: A comprehensive review, European Journal of Operational Research, 203, 539-549 (2010) · Zbl 1177.90268 |
| [21] | Hall, R. W., Distance approximations for routing manual pickers in a warehouse, IIE Transactions, 24, 4, 76-87 (1993) |
| [22] | Henn, S., Algorithms for on-line order batching in an order picking warehouse, Computers and Operations Research, 39, 2549-2563 (2012) · Zbl 1251.90007 |
| [24] | Henn, S.; Koch, S.; Doerner, K.; Strauss, K.; Wäscher, G., Metaheuristics for the order batching problem in manuel order picking systems, BuR—Business Research, 3, 1, 82-105 (2010) |
| [25] | Henn, S.; Schmid, V., Metaheuristics for order batching and sequencing in manual order picking systems, Computers and Industrial Engineering, 66, 338-351 (2013) |
| [26] | Henn, S.; Wäscher, G., Tabu search heuristics for the order batching problem in manual order picking systems, European Journal of Operational Research, 222, 484-494 (2012) · Zbl 1253.90008 |
| [27] | 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, 557-570 (2012) · Zbl 1253.90009 |
| [28] | Hoos, H. H.; Stützle, T., Evaluation Las Vegas—Pitfalls and remedies, (Cooper, G.; Moral, S., Proceedings of the 14th conference on uncertainty in artificial intelligence (1998), Morgan Kaufmann Publishers: Morgan Kaufmann Publishers San Francisco, CA), 238-245 |
| [29] | 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) |
| [30] | Hwang, H.; Kim, D. G., Order-batching heuristics based on cluster analysis in low-level picker-to-part warehousing system, International Journal of Production Research, 43, 17, 3657-3670 (2005) · Zbl 1082.90054 |
| [31] | Islam, K. M.S.; Sarker, B. R., A similarity coefficient measure and machine-parts grouping in cellular manufacturing systems, International Journal of Production Research, 38, 3, 699-720 (2000) · Zbl 0945.90522 |
| [33] | Lourenço, H. R.; Martin, O.; Stützle, T., Iterated local search, (Glover, F.; Kochenberger, G., Handbook of metaheuristics (2003), Kluwer Academic Publishers: Kluwer Academic Publishers Dordrecht), 321-353 · Zbl 1116.90412 |
| [34] | 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 |
| [35] | Öncan, T.; Kabadi, S. N.; Nair, K. P.K.; Punnen, A. P., VLSN search algorithms for partitioning problems using matching neighborhoods, Journal of the Operational Research Society, 59, 388-398 (2008) · Zbl 1145.90426 |
| [36] | Öncan, T.; Punnen, A. P., The quadratic minimum spanning tree problem: A lower bounding procedure and an efficient search algorithm, Computers and Operations Research, 37, 1762-1773 (2010) · Zbl 1188.90268 |
| [37] | Paessens, H., The savings algorithm for the vehicle routing problem, European Journal of Operational Research, 34, 336-344 (1988) · Zbl 0635.90047 |
| [38] | Petersen, C. G., An evaluation of order picking routeing policies, International Journal of Operations and Production Management, 17, 11, 1098-1111 (1997) |
| [39] | Ratliff, H. D.; Rosenthal, A. S., Orderpicking in a rectangular warehouse: Aa solvable case of the traveling salesman problem, Operations Research, 31, 507-521 (1983) · Zbl 0523.90060 |
| [40] | 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 |
| [41] | Ruben, R. A.; Jacobs, F. R., Batch construction and storage assignment, Management Science, 45, 4, 575-596 (1999) · Zbl 1231.90054 |
| [42] | Schmid, V.; Doerner, K. F.; Laporte, G., Rich routing problems arising in supply chain management, European Journal of Operational Research, 224, 435-448 (2013) · Zbl 1292.90063 |
| [43] | Tompkins, J. A.; White, J. A.; Bozer, Y. A.; Tanchoco, J. M.A., Facilities planning (2003), John Wiley & Sons: John Wiley & Sons New Jersey |
| [44] | 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: Springer Berlin), 323-347 |
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
