Storage Assignment Using Nested Metropolis Sampling and Approximations of Order Batching Travel Costs

• Published in: SN computer science 2024-06, Vol.5 (5), p.477, Article 477
• Main Authors: Oxenstierna, Johan, Malec, Jacek, Krueger, Volker
• Format: Article
• Language: English
• Subjects: Algorithms; Approximation; Assignment problem; Computer Imaging; Computer Science; Computer Systems Organization and Communication Networks; Costs; Data Structures and Information Theory; Information Systems and Communication Service; Innovative Intelligent Industrial Production and Logistics 2022; Materials handling; Model accuracy; Optimization; Order picking; Original Research; Pattern Recognition and Graphics; Reproducibility; Software Engineering/Programming and Operating Systems; Traffic congestion; Travel; Traveling salesman problem; Vehicles; Vision; Warehouses
• ISSN: 2661-8907; 2662-995X; 2661-8907
• DOI: 10.1007/s42979-024-02711-w

The Storage Location Assignment Problem (SLAP) is of central importance in warehouse operations. An important research challenge lies in generalizing the SLAP such that it is not tied to certain order-picking methodologies, constraints, or warehouse layouts. We propose the OBP-based SLAP, where the quality of a location assignment is obtained by optimizing an Order Batching Problem (OBP). For the optimization of the OBP-based SLAP, we propose a nested Metropolis algorithm. The algorithm includes an OBP-optimizer to obtain the cost of an assignment, as well as a filter which approximates OBP costs using a model based on the Quadratic Assignment Problem (QAP). In experiments, we tune two key parameters in the QAP model, and test whether its predictive quality warrants its use within the SLAP optimizer. Results show that the QAP model’s per-sample accuracy is only marginally better than a random baseline, but that it delivers predictions much faster than the OBP optimizer, implying that it can be used as an effective filter. We then run the SLAP optimizer with and without using the QAP model on industrial data. We observe a cost improvement of around 23% over 1 h with the QAP model, and 17% without it. We share results for public instances on the TSPLIB format.