{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T23:46:02Z","timestamp":1740181562676,"version":"3.37.3"},"reference-count":37,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2022,12,17]],"date-time":"2022-12-17T00:00:00Z","timestamp":1671235200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,12,17]],"date-time":"2022-12-17T00:00:00Z","timestamp":1671235200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"Wallenberg Autonomous Systems and Software Program"},{"DOI":"10.13039\/501100003252","name":"Lund University","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100003252","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["SN COMPUT. SCI."],"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Order Picking in warehouses is often optimized using a method known as Order Batching, which means that one vehicle can be assigned to pick a batch of several orders at a time. There exists a rich body of research on Order Batching Problem (OBP) optimization, but one area which demands more attention is computational efficiency, especially for optimization scenarios where warehouses have unconventional layouts and vehicle capacity configurations. Due to the NP-hard nature of the OBP, computational cost for optimally solving large instances is often prohibitive. In this paper, we compare the performance of two approximate optimizers designed for maximum computational efficiency. The first optimizer, <jats:italic>Single Batch Iterated<\/jats:italic> (SBI), is based on a Seed Algorithm, and the second, <jats:italic>Metropolis Batch Sampling<\/jats:italic> (MBS), is based on a Metropolis algorithm. Trade-offs in memory and CPU-usage and generalizability of both algorithms is analyzed and discussed. Existing benchmark datasets are used to evaluate the optimizers on various scenarios. On smaller instances, we find that both optimizers come within a few percentage points of optimality at minimal CPU-time. For larger instances, we find that solution improvement continues throughout the allotted time but at a rate which is difficult to justify in many operational scenarios. SBI generally outperforms MBS and this is mainly attributed to the large search space and the latter\u2019s failure to efficiently cover it. The relevance of the results within Industry 4.0 era warehouse operations is discussed.<\/jats:p>","DOI":"10.1007\/s42979-022-01496-0","type":"journal-article","created":{"date-parts":[[2022,12,17]],"date-time":"2022-12-17T14:02:36Z","timestamp":1671285756000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Efficient Order Batching Optimization Using Seed Heuristics and the Metropolis Algorithm"],"prefix":"10.1007","volume":"4","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6608-9621","authenticated-orcid":false,"given":"Johan","family":"Oxenstierna","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2121-1937","authenticated-orcid":false,"given":"Jacek","family":"Malec","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8836-8816","authenticated-orcid":false,"given":"Volker","family":"Krueger","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2022,12,17]]},"reference":[{"key":"1496_CR1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2020.105168","volume":"129","author":"B Aerts","year":"2021","unstructured":"Aerts B, Cornelissens T, S\u00f6rensen K. The joint order batching and picker routing problem: modelled and solved as a clustered vehicle routing problem. Comput Oper Res. 2021;129: 105168. https:\/\/doi.org\/10.1016\/j.cor.2020.105168.","journal-title":"Comput Oper Res"},{"key":"1496_CR2","doi-asserted-by":"publisher","first-page":"132","DOI":"10.1287\/ijoc.14.2.132.118","volume":"14","author":"D Applegate","year":"2002","unstructured":"Applegate D, Cook W, Dash S, Rohe A. Solution of a min-max vehicle routing problem. INFORMS J Comput. 2002;14:132\u201343.","journal-title":"INFORMS J Comput"},{"key":"1496_CR3","volume-title":"The traveling salesman problem: a computational study","author":"DL Applegate","year":"2006","unstructured":"Applegate DL, Bixby RE, Chvatal V, Cook WJ. The traveling salesman problem: a computational study. Princeton: Princeton University Press; 2006."},{"key":"1496_CR4","doi-asserted-by":"publisher","DOI":"10.1155\/2013\/246578","author":"AH Azadnia","year":"2013","unstructured":"Azadnia AH, Taheri S, Ghadimi P, Samanm MZM, Wong KY. Order batching in warehouses by minimizing total tardiness: a hybrid approach of weighted association rule mining and genetic algorithms. Sci World J. 2013. https:\/\/doi.org\/10.1155\/2013\/246578.","journal-title":"Sci World J"},{"issue":"7","key":"1496_CR5","doi-asserted-by":"publisher","first-page":"1887","DOI":"10.1080\/00207540600920850","volume":"46","author":"YA Bozer","year":"2008","unstructured":"Bozer YA, Kile JW. Order batching in walk-and-pick order picking systems. Int J Prod Res. 2008;46(7):1887\u2013909.","journal-title":"Int J Prod Res"},{"issue":"2","key":"1496_CR6","doi-asserted-by":"publisher","first-page":"497","DOI":"10.1016\/j.ejor.2020.01.059","volume":"285","author":"O Briant","year":"2020","unstructured":"Briant O, Cambazard H, Cattaruzza D, Catusse N, Ladier A-L, Ogier M. An efficient and general approach for the joint order batching and picker routing problem. Eur J Oper Res. 2020;285(2):497\u2013512. https:\/\/doi.org\/10.1016\/j.ejor.2020.01.059.","journal-title":"Eur J Oper Res"},{"key":"1496_CR7","doi-asserted-by":"publisher","unstructured":"Bu\u00e9 M, Cattaruzza D, Ogier M, Semet F. A two-phase approach for an integrated order batching and picker routing problem. In: Dell'Amico M, Gaudioso M, Stecca G, editors. A view of operations research applications in Italy, 2018. AIRO springer series, vol 2. Cham: Springer; 2019. p. 3\u201318. https:\/\/doi.org\/10.1007\/978-3-030-25842-9_1.","DOI":"10.1007\/978-3-030-25842-9_1"},{"key":"1496_CR8","doi-asserted-by":"publisher","DOI":"10.1007\/s10845-020-01653-3","author":"\u00c7 Cergibozan","year":"2020","unstructured":"Cergibozan \u00c7, Tasan A. Genetic algorithm based approaches to solve the order batching problem and a case study in a distribution center. J Intell Manuf. 2020. https:\/\/doi.org\/10.1007\/s10845-020-01653-3.","journal-title":"J Intell Manuf"},{"issue":"4","key":"1496_CR9","doi-asserted-by":"publisher","first-page":"333","DOI":"10.1016\/j.omega.2004.05.003","volume":"33","author":"M-C Chen","year":"2005","unstructured":"Chen M-C, Wu H-P. An association-based clustering approach to order batching considering customer demand patterns. Omega. 2005;33(4):333\u201343. https:\/\/doi.org\/10.1016\/j.omega.2004.05.003.","journal-title":"Omega"},{"key":"1496_CR10","unstructured":"Cordeau J-F, Laporte G, Savelsbergh M, Vigo D. Vehicle Routing. In: Transportation, handbooks in operations research and management science vol. 14. 2007. p. 195\u2013224."},{"key":"1496_CR11","doi-asserted-by":"publisher","first-page":"78","DOI":"10.1016\/j.cor.2017.02.007","volume":"83","author":"C Defryn","year":"2017","unstructured":"Defryn C, S\u00f6rensen K. A fast two-level variable neighborhood search for the clustered vehicle routing problem. Comput Oper Res. 2017;83:78\u201394. https:\/\/doi.org\/10.1016\/j.cor.2017.02.007.","journal-title":"Comput Oper Res"},{"issue":"5","key":"1496_CR12","doi-asserted-by":"publisher","first-page":"10","DOI":"10.1109\/MCC.2016.105","volume":"3","author":"C Esposito","year":"2016","unstructured":"Esposito C, Castiglione A, Choo K-KR. Challenges in delivering software in the cloud as microservices. IEEE Cloud Comput. 2016;3(5):10\u20134. https:\/\/doi.org\/10.1109\/MCC.2016.105.","journal-title":"IEEE Cloud Comput"},{"key":"1496_CR13","doi-asserted-by":"crossref","unstructured":"Gademann AJRM (noud), Van Den Berg JP, Van Der Hoff HH. An order batching algorithm for wave picking in a parallel-aisle warehouse. IIE Transactions. 2001;33(5):385\u201398.","DOI":"10.1080\/07408170108936837"},{"issue":"11","key":"1496_CR14","doi-asserted-by":"publisher","first-page":"2549","DOI":"10.1016\/j.cor.2011.12.019","volume":"39","author":"S Henn","year":"2012","unstructured":"Henn S. Algorithms for on-line order batching in an order picking warehouse. Comput Oper Res. 2012;39(11):2549\u201363.","journal-title":"Comput Oper Res"},{"issue":"1","key":"1496_CR15","doi-asserted-by":"publisher","first-page":"82","DOI":"10.1007\/BF03342717","volume":"3","author":"S Henn","year":"2010","unstructured":"Henn S, Koch S, Doerner KF, Strauss C, W\u00e4scher G. Metaheuristics for the order batching problem in manual order picking systems. Bus Res. 2010;3(1):82\u2013105.","journal-title":"Bus Res"},{"issue":"3","key":"1496_CR16","doi-asserted-by":"publisher","first-page":"484","DOI":"10.1016\/j.ejor.2012.05.049","volume":"222","author":"S Henn","year":"2012","unstructured":"Henn S, W\u00e4scher G. Tabu search heuristics for the order batching problem in manual order picking systems. Eur J Oper Res. 2012;222(3):484\u201394.","journal-title":"Eur J Oper Res"},{"issue":"2","key":"1496_CR17","doi-asserted-by":"publisher","first-page":"321","DOI":"10.1016\/j.cie.2007.12.018","volume":"55","author":"Y-C Ho","year":"2008","unstructured":"Ho Y-C, Su T-S, Shi Z-B. Order-batching methods for an order-picking warehouse with two cross aisles. Comput Ind Eng. 2008;55(2):321\u201347.","journal-title":"Comput Ind Eng"},{"key":"1496_CR18","doi-asserted-by":"publisher","first-page":"1985","DOI":"10.1016\/j.procs.2018.07.254","volume":"126","author":"X Jiang","year":"2018","unstructured":"Jiang X, Zhou Y, Zhang Y, Sun L, Hu X. Order batching and sequencing problem under the pick-and-sort strategy in online supermarkets. Proc Comput Sci. 2018;126:1985\u201393.","journal-title":"Proc Comput Sci"},{"key":"1496_CR19","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4842-3423-5","volume-title":"Practical python AI projects: mathematical models of optimization problems with google OR-tools","author":"S Kruk","year":"2018","unstructured":"Kruk S. Practical python AI projects: mathematical models of optimization problems with google OR-tools. New york: Apress; 2018."},{"issue":"1","key":"1496_CR20","doi-asserted-by":"publisher","first-page":"52","DOI":"10.1007\/s10696-011-9101-8","volume":"24","author":"O Kulak","year":"2012","unstructured":"Kulak O, Sahin Y, Taner ME. Joint order batching and picker routing in single and multiple-cross-aisle warehouses using cluster-based tabu search algorithms. Flex Serv Manuf J. 2012;24(1):52\u201380. https:\/\/doi.org\/10.1007\/s10696-011-9101-8.","journal-title":"Flex Serv Manuf J"},{"issue":"2","key":"1496_CR21","doi-asserted-by":"publisher","first-page":"447","DOI":"10.1080\/00207543.2016.1187313","volume":"55","author":"J Li","year":"2017","unstructured":"Li J, Huang R, Dai JB. Joint optimisation of order batching and picker routing in the online retailer\u2019s warehouse in China. Int J Prod Res. 2017;55(2):447\u201361. https:\/\/doi.org\/10.1080\/00207543.2016.1187313.","journal-title":"Int J Prod Res"},{"key":"1496_CR22","doi-asserted-by":"publisher","unstructured":"Mackay DJC. Introduction to Monte Carlo Methods. In: Jordan MI, editor. Learning in graphical models. NATO ASI Series, vol 89. Dordrecht: Springer; 1998. https:\/\/doi.org\/10.1007\/978-94-011-5014-9_7","DOI":"10.1007\/978-94-011-5014-9_7"},{"key":"1496_CR23","doi-asserted-by":"publisher","DOI":"10.1016\/j.ijpe.2019.107564","volume":"224","author":"M Masae","year":"2020","unstructured":"Masae M, Glock CH, Grosse EH. Order picker routing in warehouses: a systematic literature review. Int J Prod Econ. 2020;224: 107564.","journal-title":"Int J Prod Econ"},{"issue":"2","key":"1496_CR24","first-page":"58","volume":"2","author":"T Naumenko","year":"2021","unstructured":"Naumenko T, Petrenko A. Analysis of problems of storage and processing of data in serverless technologies. Technol Audit Prod Reserves. 2021;2(2):58.","journal-title":"Technol Audit Prod Reserves"},{"key":"1496_CR25","doi-asserted-by":"publisher","unstructured":"Oxenstierna J, Malec J, Krueger V. Layout-agnostic order-batching optimization. In: Mes M, Lalla-Ruiz E, Vo\u00df S, editors. Computational logistics. ICCL 2021. Lecture notes in computer science, vol 13004. Cham: Springer; 2021. https:\/\/doi.org\/10.1007\/978-3-030-87672-2_8","DOI":"10.1007\/978-3-030-87672-2_8"},{"key":"1496_CR26","doi-asserted-by":"publisher","unstructured":"Oxenstierna J, Malec J, Krueger V. Analysis of computational efficiency in iterative order batching optimization. In: Proceedings of the 11th international conference on operations research and enterprise systems\u2013ICORES. 2022. p. 345\u201353. https:\/\/doi.org\/10.5220\/0010837700003117","DOI":"10.5220\/0010837700003117"},{"issue":"1","key":"1496_CR27","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1016\/0304-3975(92)90177-H","volume":"99","author":"S Rajasekaran","year":"1992","unstructured":"Rajasekaran S, Reif JH. Nested annealing: a provable improvement to simulated annealing. Theoret Comput Sci. 1992;99(1):157\u201376. https:\/\/doi.org\/10.1016\/0304-3975(92)90177-H.","journal-title":"Theoret Comput Sci"},{"key":"1496_CR28","doi-asserted-by":"publisher","first-page":"507","DOI":"10.1287\/opre.31.3.507","volume":"31","author":"H Ratliff","year":"1983","unstructured":"Ratliff H, Rosenthal A. Order-picking in a rectangular warehouse: a solvable case of the traveling salesman problem. Oper Res. 1983;31:507\u201321.","journal-title":"Oper Res"},{"key":"1496_CR29","unstructured":"van Rensburg LJ. Artificial intelligence for warehouse picking optimization\u2014An NP-hard problem [Master\u2019s Thesis]. Uppsala University; 2019."},{"issue":"9","key":"1496_CR30","doi-asserted-by":"publisher","first-page":"1865","DOI":"10.1080\/00207540110028128","volume":"39","author":"KJ Roodbergen","year":"2001","unstructured":"Roodbergen KJ, Koster R. Routing methods for warehouses with multiple cross aisles. Int J Prod Res. 2001;39(9):1865\u201383.","journal-title":"Int J Prod Res"},{"issue":"2","key":"1496_CR31","doi-asserted-by":"publisher","first-page":"461","DOI":"10.1016\/j.ejor.2017.04.038","volume":"263","author":"A Scholz","year":"2017","unstructured":"Scholz A, Schubert D, W\u00e4scher G. Order picking with multiple pickers and due dates\u2014simultaneous solution of order batching, batch assignment and sequencing, and picker routing problems. Eur J Oper Res. 2017;263(2):461\u201378. https:\/\/doi.org\/10.1016\/j.ejor.2017.04.038.","journal-title":"Eur J Oper Res"},{"key":"1496_CR32","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1016\/0377-2217(92)90235-2","volume":"58","author":"GP Sharp","year":"1992","unstructured":"Sharp GP, Gibson DR. Order batching procedures. Eur J Oper Res. 1992;58:57\u201367.","journal-title":"Eur J Oper Res"},{"issue":"3","key":"1496_CR33","doi-asserted-by":"publisher","first-page":"479","DOI":"10.1080\/10618600.2017.1415911","volume":"27","author":"H Tak","year":"2018","unstructured":"Tak H, Meng X-L, van Dyk DA. A repelling-attracting metropolis algorithm for multimodality. J Comput Graph Stat. 2018;27(3):479\u201390. https:\/\/doi.org\/10.1080\/10618600.2017.1415911.","journal-title":"J Comput Graph Stat"},{"key":"1496_CR34","doi-asserted-by":"publisher","first-page":"460","DOI":"10.1016\/j.ejor.2020.01.022","volume":"284","author":"CA Valle","year":"2019","unstructured":"Valle CA, Beasley BA. Order batching using an approximation for the distance travelled by pickers. Eur J Oper Res. 2019;284:460\u201384.","journal-title":"Eur J Oper Res"},{"issue":"3","key":"1496_CR35","doi-asserted-by":"publisher","first-page":"817","DOI":"10.1016\/j.ejor.2017.03.069","volume":"262","author":"CA Valle","year":"2017","unstructured":"Valle CA, Beasley JE, da Cunha AS. Optimally solving the joint order batching and picker routing problem. Eur J Oper Res. 2017;262(3):817\u201334.","journal-title":"Eur J Oper Res"},{"key":"1496_CR36","doi-asserted-by":"publisher","first-page":"5111","DOI":"10.1021\/jp970984n","volume":"101","author":"DJ Wales","year":"1997","unstructured":"Wales DJ, Doye JPK. Global optimization by basin-hopping and the lowest energy structures of Lennard-Jones clusters containing up to 110 atoms. J Phys Chem A. 1997;101:5111\u20136.","journal-title":"J Phys Chem A"},{"issue":"14","key":"1496_CR37","doi-asserted-by":"publisher","first-page":"1625","DOI":"10.3390\/math9141625","volume":"9","author":"VF Yu","year":"2021","unstructured":"Yu VF, Maulidin A, Redi AP, Lin SW, Yang CL. Simulated annealing with restart strategy for the path cover problem with time windows. Mathematics. 2021;9(14):1625. https:\/\/doi.org\/10.3390\/math9141625.","journal-title":"Mathematics"}],"container-title":["SN Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s42979-022-01496-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s42979-022-01496-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s42979-022-01496-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,3,10]],"date-time":"2023-03-10T11:41:21Z","timestamp":1678448481000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s42979-022-01496-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,12,17]]},"references-count":37,"journal-issue":{"issue":"2","published-online":{"date-parts":[[2023,3]]}},"alternative-id":["1496"],"URL":"https:\/\/doi.org\/10.1007\/s42979-022-01496-0","relation":{},"ISSN":["2661-8907"],"issn-type":[{"type":"electronic","value":"2661-8907"}],"subject":[],"published":{"date-parts":[[2022,12,17]]},"assertion":[{"value":"24 May 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"31 October 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"17 December 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare that they have no conflict of interest. This article does not contain any studies with human participants or animals performed by any of the authors.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of Interest"}}],"article-number":"107"}}