assignment problem on operation research

Assignment Problem: Meaning, Methods and Variations | Operations Research

After reading this article you will learn about:- 1. Meaning of Assignment Problem 2. Definition of Assignment Problem 3. Mathematical Formulation 4. Hungarian Method 5. Variations.

Meaning of Assignment Problem:

An assignment problem is a particular case of transportation problem where the objective is to assign a number of resources to an equal number of activities so as to minimise total cost or maximize total profit of allocation.

The problem of assignment arises because available resources such as men, machines etc. have varying degrees of efficiency for performing different activities, therefore, cost, profit or loss of performing the different activities is different.

Thus, the problem is “How should the assignments be made so as to optimize the given objective”. Some of the problem where the assignment technique may be useful are assignment of workers to machines, salesman to different sales areas.

Definition of Assignment Problem:

ADVERTISEMENTS:

Suppose there are n jobs to be performed and n persons are available for doing these jobs. Assume that each person can do each job at a term, though with varying degree of efficiency, let c ij be the cost if the i-th person is assigned to the j-th job. The problem is to find an assignment (which job should be assigned to which person one on-one basis) So that the total cost of performing all jobs is minimum, problem of this kind are known as assignment problem.

The assignment problem can be stated in the form of n x n cost matrix C real members as given in the following table:

How to Solve the Assignment Problem: A Complete Guide

Table of Contents

Assignment problem is a special type of linear programming problem that deals with assigning a number of resources to an equal number of tasks in the most efficient way. The goal is to minimize the total cost of assignments while ensuring that each task is assigned to only one resource and each resource is assigned to only one task. In this blog, we will discuss the solution of the assignment problem using the Hungarian method, which is a popular algorithm for solving the problem.

Understanding the Assignment Problem

Before we dive into the solution, it is important to understand the problem itself. In the assignment problem, we have a matrix of costs, where each row represents a resource and each column represents a task. The objective is to assign each resource to a task in such a way that the total cost of assignments is minimized. However, there are certain constraints that need to be satisfied – each resource can be assigned to only one task and each task can be assigned to only one resource.

Solving the Assignment Problem

There are various methods for solving the assignment problem, including the Hungarian method, the brute force method, and the auction algorithm. Here, we will focus on the steps involved in solving the assignment problem using the Hungarian method, which is the most commonly used and efficient method.

Step 1: Set up the cost matrix

The first step in solving the assignment problem is to set up the cost matrix, which represents the cost of assigning a task to an agent. The matrix should be square and have the same number of rows and columns as the number of tasks and agents, respectively.

Step 2: Subtract the smallest element from each row and column

To simplify the calculations, we need to reduce the size of the cost matrix by subtracting the smallest element from each row and column. This step is called matrix reduction.

Step 3: Cover all zeros with the minimum number of lines

The next step is to cover all zeros in the matrix with the minimum number of horizontal and vertical lines. This step is called matrix covering.

Step 4: Test for optimality and adjust the matrix

To test for optimality, we need to calculate the minimum number of lines required to cover all zeros in the matrix. If the number of lines equals the number of rows or columns, the solution is optimal. If not, we need to adjust the matrix and repeat steps 3 and 4 until we get an optimal solution.

Step 5: Assign the tasks to the agents

The final step is to assign the tasks to the agents based on the optimal solution obtained in step 4. This will give us the most cost-effective or profit-maximizing assignment.

Solution of the Assignment Problem using the Hungarian Method

The Hungarian method is an algorithm that uses a step-by-step approach to find the optimal assignment. The algorithm consists of the following steps:

• Subtract the smallest entry in each row from all the entries of the row.
• Subtract the smallest entry in each column from all the entries of the column.
• Draw the minimum number of lines to cover all zeros in the matrix. If the number of lines drawn is equal to the number of rows, we have an optimal solution. If not, go to step 4.
• Determine the smallest entry not covered by any line. Subtract it from all uncovered entries and add it to all entries covered by two lines. Go to step 3.

The above steps are repeated until an optimal solution is obtained. The optimal solution will have all zeros covered by the minimum number of lines. The assignments can be made by selecting the rows and columns with a single zero in the final matrix.

Applications of the Assignment Problem

The assignment problem has various applications in different fields, including computer science, economics, logistics, and management. In this section, we will provide some examples of how the assignment problem is used in real-life situations.

Applications in Computer Science

The assignment problem can be used in computer science to allocate resources to different tasks, such as allocating memory to processes or assigning threads to processors.

Applications in Economics

The assignment problem can be used in economics to allocate resources to different agents, such as allocating workers to jobs or assigning projects to contractors.

Applications in Logistics

The assignment problem can be used in logistics to allocate resources to different activities, such as allocating vehicles to routes or assigning warehouses to customers.

Applications in Management

The assignment problem can be used in management to allocate resources to different projects, such as allocating employees to tasks or assigning budgets to departments.

Let’s consider the following scenario: a manager needs to assign three employees to three different tasks. Each employee has different skills, and each task requires specific skills. The manager wants to minimize the total time it takes to complete all the tasks. The skills and the time required for each task are given in the table below:

The assignment problem is to determine which employee should be assigned to which task to minimize the total time required. To solve this problem, we can use the Hungarian method, which we discussed in the previous blog.

Using the Hungarian method, we first subtract the smallest entry in each row from all the entries of the row:

Next, we subtract the smallest entry in each column from all the entries of the column:

We draw the minimum number of lines to cover all the zeros in the matrix, which in this case is three:

Since the number of lines is equal to the number of rows, we have an optimal solution. The assignments can be made by selecting the rows and columns with a single zero in the final matrix. In this case, the optimal assignments are:

• Emp 1 to Task 3
• Emp 2 to Task 2
• Emp 3 to Task 1

This assignment results in a total time of 9 units.

I hope this example helps you better understand the assignment problem and how to solve it using the Hungarian method.

Solving the assignment problem may seem daunting, but with the right approach, it can be a straightforward process. By following the steps outlined in this guide, you can confidently tackle any assignment problem that comes your way.

How useful was this post?

Click on a star to rate it!

Average rating 0 / 5. Vote count: 0

No votes so far! Be the first to rate this post.

We are sorry that this post was not useful for you! 😔

Let us improve this post!

Tell us how we can improve this post?

Operations Research

1 Operations Research-An Overview

• History of O.R.
• Approach, Techniques and Tools
• Phases and Processes of O.R. Study
• Typical Applications of O.R
• Limitations of Operations Research
• Models in Operations Research
• O.R. in real world

2 Linear Programming: Formulation and Graphical Method

• General formulation of Linear Programming Problem
• Optimisation Models
• Basics of Graphic Method
• Important steps to draw graph
• Multiple, Unbounded Solution and Infeasible Problems
• Solving Linear Programming Graphically Using Computer
• Application of Linear Programming in Business and Industry

3 Linear Programming-Simplex Method

• Principle of Simplex Method
• Computational aspect of Simplex Method
• Simplex Method with several Decision Variables
• Two Phase and M-method
• Multiple Solution, Unbounded Solution and Infeasible Problem
• Sensitivity Analysis
• Dual Linear Programming Problem

4 Transportation Problem

• Basic Feasible Solution of a Transportation Problem
• Modified Distribution Method
• Stepping Stone Method
• Unbalanced Transportation Problem
• Degenerate Transportation Problem
• Transhipment Problem
• Maximisation in a Transportation Problem

5 Assignment Problem

• Solution of the Assignment Problem
• Unbalanced Assignment Problem
• Problem with some Infeasible Assignments
• Maximisation in an Assignment Problem
• Crew Assignment Problem

6 Application of Excel Solver to Solve LPP

• Building Excel model for solving LP: An Illustrative Example

7 Goal Programming

• Concepts of goal programming
• Goal programming model formulation
• Graphical method of goal programming
• The simplex method of goal programming
• Using Excel Solver to Solve Goal Programming Models
• Application areas of goal programming

8 Integer Programming

• Some Integer Programming Formulation Techniques
• Binary Representation of General Integer Variables
• Unimodularity
• Cutting Plane Method
• Branch and Bound Method
• Solver Solution

9 Dynamic Programming

• Dynamic Programming Methodology: An Example
• Definitions and Notations
• Dynamic Programming Applications

10 Non-Linear Programming

• Solution of a Non-linear Programming Problem
• Convex and Concave Functions
• Kuhn-Tucker Conditions for Constrained Optimisation
• Quadratic Programming
• Separable Programming
• NLP Models with Solver

11 Introduction to game theory and its Applications

• Important terms in Game Theory
• Saddle points
• Mixed strategies: Games without saddle points
• 2 x n games
• Exploiting an opponent’s mistakes

12 Monte Carlo Simulation

• Reasons for using simulation
• Monte Carlo simulation
• Limitations of simulation
• Steps in the simulation process
• Some practical applications of simulation
• Two typical examples of hand-computed simulation
• Computer simulation

13 Queueing Models

• Characteristics of a queueing model
• Notations and Symbols
• Statistical methods in queueing
• The M/M/I System
• The M/M/C System
• The M/Ek/I System
• Decision problems in queueing

Operations Research by

Get full access to Operations Research and 60K+ other titles, with a free 10-day trial of O'Reilly.

There are also live events, courses curated by job role, and more.

Assignment Problem

5.1  introduction.

The assignment problem is one of the special type of transportation problem for which more efficient (less-time consuming) solution method has been devised by KUHN (1956) and FLOOD (1956). The justification of the steps leading to the solution is based on theorems proved by Hungarian mathematicians KONEIG (1950) and EGERVARY (1953), hence the method is named Hungarian.

5.2  GENERAL MODEL OF THE ASSIGNMENT PROBLEM

Consider n jobs and n persons. Assume that each job can be done only by one person and the time a person required for completing the i th job (i = 1,2,...n) by the j th person (j = 1,2,...n) is denoted by a real number C ij . On the whole this model deals with the assignment of n candidates to n jobs ...

Get Operations Research now with the O’Reilly learning platform.

O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.

Don’t leave empty-handed

Get Mark Richards’s Software Architecture Patterns ebook to better understand how to design components—and how they should interact.

It’s yours, free.

Check it out now on O’Reilly

Dive in for free with a 10-day trial of the O’Reilly learning platform—then explore all the other resources our members count on to build skills and solve problems every day.

Operations Research/Transportation and Assignment Problem

The Transportation and Assignment problems deal with assigning sources and jobs to destinations and machines. We will discuss the transportation problem first.

Suppose a company has m factories where it manufactures its product and n outlets from where the product is sold. Transporting the product from a factory to an outlet costs some money which depends on several factors and varies for each choice of factory and outlet. The total amount of the product a particular factory makes is fixed and so is the total amount a particular outlet can store. The problem is to decide how much of the product should be supplied from each factory to each outlet so that the total cost is minimum.

Let us consider an example.

Suppose an auto company has three plants in cities A, B and C and two major distribution centers in D and E. The capacities of the three plants during the next quarter are 1000, 1500 and 1200 cars. The quarterly demands of the two distribution centers are 2300 and 1400 cars. The transportation costs (which depend on the mileage, transport company etc) between the plants and the distribution centers is as follows:

Which plant should supply how many cars to which outlet so that the total cost is minimum?

The problem can be formulated as a LP model:

The whole model is:

subject to,

The problem can now be solved using the simplex method. A convenient procedure is discussed in the next section.

• Book:Operations Research

Navigation menu

Travelling Salesman Problem

This humorously named problem refers to the following situation:

A travelling salesman , named Rover plans to visit each of n cities. He wishes to visit each city once and only once, arriving back to city from where he started. The distance between City i and City j is c ij . What is the shortest tour Rover can take?

If there are n cities, there are (n - 1)! possible ways for his tour. For example, if the number of cities to be visited is 5, then there are 4! different combinations. Such type of problems can be solved by the assignment method.

Let c ij be the distance (or cost or time) between City i to City j and

Use Horizontal Scrollbar to View Full Details

The following example will help you in understanding the travelling salesman problem of operation research.

Example: Travelling Salesman Problem

A travelling salesman, named Rolling Stone plans to visit five cities 1, 2, 3, 4 & 5. The travel time (in hours) between these cities is shown below:

How should Mr. Rolling Stone schedule his touring plan in order to minimize the total travel time , if he visits each city once a week?

"As every thread of gold is valuable, so is every minute of time." - John Mason

After applying steps 1 to 3 of the Hungarian method, we get the following assignments.

Use Horizontal Scrollbar to View Full Table.

Draw the minimum number of vertical and horizontal lines necessary to cover all the zeros in the reduced matrix.

Select the smallest element from all the uncovered elements. Subtract this smallest element from all the uncovered elements and add it to the elements, which lie at the intersection of two lines. Thus, we obtain another reduced matrix for fresh assignment. Repeating step 3 on the reduced matrix, we get the following assignments.

The above solution suggests that the salesman should go from city 1 to city 4, city 4 to city 2, and then city 2 to 1 (original starting point). The above solution is not a solution to the travelling salesman problem as he visits city 1 twice.

The next best solution can be obtained by bringing the minimum non-zero element, i.e., 1 into the solution. Please note that the value 1 occurs at four places. We will consider all the cases separately until the acceptable solution is obtained. To make the assignment in the cell (2, 3), delete the row & the column containing this cell so that no other assignment can be made in the second row and third column.

Now, make the assignments in the usual manner as shown in the following table.

He starts from city 1 and goes to city 4; from city 4 to city 2; from city 2 to city 3; from city 3 to city 5; from city 5 to city 1.

Substituting values from original table: 4 + 7 + 6+ 4 + 5 = 26 hours.

In this chapter, we focussed on a special type of transportation problem where the objective was to allocate n different facilities to n different tasks. Although an assignment problem can be formulated as a linear programming problem, it is solved by a special method known as Hungarian Method. If the number of persons is the same as the number of jobs, the assignment problem is said to be balanced. If the number of jobs is different from the number of persons, the assignment problem is said to be unbalanced. Some assignment problems entail maximizing the profit, effectiveness, or layoff of an assignment of persons to tasks or of jobs to machines. The Hungarian Method can also solve such problems. Further, the Hungarian method can also be utilized for solving crew assignment problem and the travelling salesman problem.

Share This Article

Operations Research Simplified Back Next

Goal programming Linear programming Simplex Method Transportation Problem

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

• Original Research
• Open access
• Published: 23 April 2024
• Volume 5 , article number  477 , ( 2024 )

Cite this article

You have full access to this open access article

• Johan Oxenstierna   ORCID: orcid.org/0000-0002-6608-9621 1 , 2 ,
• Jacek Malec   ORCID: orcid.org/0000-0002-2121-1937 1 &
• Volker Krueger   ORCID: orcid.org/0000-0002-8836-8816 1  

Explore all metrics

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.

Similar content being viewed by others

Optimization of the Storage Location Assignment Problem Using Nested Annealing

Efficient Order Batching Optimization Using Seed Heuristics and the Metropolis Algorithm

Robust Storage Assignment in Warehouses with Correlated Demand

Avoid common mistakes on your manuscript.

Introduction

Charris et al. [ 7 ] gives the following definition of a Storage Location Assignment Problem (SLAP): The “allocation of products into a storage space and optimization of the material handling (…) or storage space utilization [costs]”. The relationship between material handling costs, on the one hand, and storage assignment, on the other, can be showcased in an example: If a vehicle needs to pick a set of products, its travel cost clearly depends on where the products are stored in the warehouse. At the same time, the development of an effective storage strategy needs to consider various features in material handling, such as vehicle constraints, traffic conventions and picking methodologies.

In this paper, we work with a version of the SLAP which is particularly generalizable. Kübler et al. [ 18 ], name this version the “joint storage location assignment, order batching and picker routing problem”. The main characteristic of this version is the inclusion of two optimization problems in the SLAP:

The Order Batching Problem (OBP), where vehicles are assigned to carry sets of orders (an order is a set of products) [ 17 ].

The Picker Routing Problem , where a short picking path of a vehicle is found for the products that the vehicle is assigned to pick. The Picker Routing Problem is a Traveling Salesman Problem (TSP) applied in a warehouse environment [ 25 ].

Henceforth, we refer to this version as the OBP-based SLAP. A key advantage of using the OBP within the SLAP is the added flexibility and generality of the order on a conceptual level: For example, optimizing the OBP-based SLAP gives opportunity to also optimize the TSP-based SLAP [ 23 ]. When it comes to product locations, the sole difference between the OBP and the OBP-based SLAP is that locations for all products are assumed fixed in the former while, in the latter, they are assumed mutable (for a subset of locations in our case).

It is of scientific importance to be able to compare optimization approaches and solutions. For the SLAP, this is made difficult by the many versions of the problem. As the extensive literature review by Charris et al. [ 7 ] shows, there is little consensus regarding which versions are more important, or specifically, which features would represent a standardized version. Examples of such features are dynamicity, warehouse layout, vehicle types, cost functions, reassignment scenarios and picking methodologies. There is also a shortage of benchmark datasets for any version of the SLAP, which prevents the reproducibility of experiments [ 2 , 16 ]. As part of our contribution for a standardized version, we suggest a modified TSPLIB format [ 26 ] (section “ Datasets ”). There are several ways in which to balance between simplicity, reproducibility and industrial applicability when developing SLAP versions and corresponding instances, however. From the generalization perspective, our model is advantageous in two main areas: Order-picking methodology and warehouse layout. But it is weak in two other areas: dynamicity and reassignment scenarios. We describe the meaning of these choices further in the light of prior work (section “ Related Work ”) and in our problem formulation (section “ Problem Formulation ”). We invite the community to debate which features are more or less important for a standardized version.

In section “ Optimization Algorithm ”, we introduce our SLAP optimizer. It is based on the Metropolis algorithm, a type of Markov Chain Monte Carlo (MCMC) method. A core feature of the optimizer is that the quality of a location assignment candidate is retrieved by optimizing an OBP. Due to the OBP’s NP-hardness, it must be optimized in a way that trades off solution quality with CPU-time. For this purpose, we use an OBP optimizer with a high degree of computational efficiency [ 22 ]. Within the SLAP optimizer, the OBP optimizer is still computationally expensive, and we show that it can be assisted by fast cost approximations from a Quadratic Assignment Problem (QAP) model. Finally, we test the performance of the SLAP optimizer with and without inclusion of the QAP approximations. Cost improvements are around 23% over 1 h with the QAP model, and 17% without. In summary, we make three concrete contributions:

Formulation of an OBP-based SLAP optimization model and a corresponding benchmark instance standard.

QAP approximation model to predict OBP travel costs and experiments on generated instances to test whether the use of QAP approximations within a SLAP optimizer can be justified.

An OBP-based SLAP optimizer (QAP-OBP) and experiments on industry instances to test its computational efficiency. Comparison of results with and without usage of QAP approximations.

Related Work

This section goes through general strategies for conducting storage location assignment, as well as ways in which their quality can be evaluated. Various SLAP formulations and proposed optimization algorithms are covered. Our primary focus will be on the standard picker-to-parts arrangement. We specifically refer to the work of Kübler et al. [ 18 ], as their proposed model aligns with ours.

There exist numerous general strategies for conducting storage location assignment [ 7 ]. Three key strategies are Dedicated, Class-based and Random:

Dedicated Each product is assigned to a specific location which never changes. This strategy is suitable if the product collection changes rarely and simplicity is desired. Additionally, human pickers can leverage this strategy by familiarizing themselves with specific products and their corresponding locations, which might speed up their picking [ 35 ].

Random Each product can be assigned any available location in the warehouse. This is suitable whenever the product collection changes frequently.

Class-based (zoning) The warehouse is partitioned into sections, and the products are classified based on their demand. Each class is assigned a zone. The outline of the zone can be regarded as dedicated in that it does not change, whereas the placement of each product in a zone is assumed to be random [ 21 ]. Class-based storage assignment can therefore be regarded as a middle ground between dedicated and random.

The quality of a location assignment is commonly evaluated based on some model of aggregate travel cost. For this purpose, a simplified simulation of order-picking in the warehouse can be used [ 7 , 21 ]. Some proposals include the simulation of order-picking by the Cube per Order Index (COI) [ 15 ]. COI includes the volume of a product and the frequency with which it is picked (historically or future-forecasted). Products with high pick frequency and relatively low volume are subsequently assigned to locations close to the depot. Since orders may contain products which are not located close to each other, COI is only adequate for order-picking scenarios where orders contain one product and vehicles carry one product at a time. This may be sufficient for pallet picking or when certain types of robots are used [ 3 ]. Mantel et al. [ 21 ], introduced Order Oriented Slotting (OOS) where the number of products in an order may be greater than one. A similar model to OOS is used by Fontana and Nepomuceno [ 10 ], Lee et al. [ 20 ] and Žulj et al. [ 37 ]. The picking cost of an order in OOS can in some cases be modeled using a Quadratic Assignment Problem (QAP) [ 21 ]. The QAP computes the sum of element-wise products of weights and frequencies [ 1 ] and for an order this can be translated into distances between products and how often they are picked. Nevertheless, a QAP on its own is often not sufficient to model a SLAP without extensive use of heuristics and constraints for warehouse layouts and picking methodologies [ 21 ]. For a layout-agnostic OBP-based SLAP, graph-based QAP techniques could be attempted, but hitherto they have only been applied on related problems [ 31 , 36 ].

There is only limited research on SLAPs where vehicles are expected to carry multiple orders and where an Order Batching Problem (OBP) is integrated into the SLAP optimization process. One example is Xiang et al. (2018) and [ 33 ], who use this approach in a robotic warehouse where the vehicles are pods or mobile racks, which is not easily comparable to a picker-to-parts system. Another example is Kübler et al. [ 18 ], which we look closer at below.

Travel distance or time are commonly used to evaluate SLAP solution quality in the above mentioned models, but there are several alternatives and extensions. Lee et al. [ 20 ], for example, study the effect of location assignment and traffic congestion in the warehouse. Assigning too many products to locations close to the depot (the goal in common COI) may lead to traffic congestion, which should ideally be considered in an industrial model. Lee et al. [ 20 ], formulate Correlated and Traffic Balanced Storage Assignment (C&TBSA) as a multi-objective problem with travel cost on the one hand, and traffic congestion avoidance on the other. Larco et al. [ 19 ], include worker welfare in their evaluation of solution quality. If picking is conducted by humans who move products from shelves onto a vehicle, the weight and volume, as well as the height of the shelf the product is placed on, can have an impact on worker welfare. Parameters such as "ergonomic loading," "human energy expenditure," or "worker discomfort" [ 7 ] can be used to quantify worker welfare.

The SLAP can be categorized into two main groups based on the number of location assignments required. Either the assignment is a “re-warehousing” operation, which means that a large portion of the warehouse’s products are (re)assigned [ 16 ]. Often, however, only a small subset of products are (re)assigned a location and this is called “healing” [ 16 ]. Solution proposals involving healing often look closely at different types of scenarios for carrying out initial assignments for new products in the warehouse, or reassignments for products already in the warehouse. Kübler et al. [ 18 ], propose four such scenarios.

Empty storage location A product is assigned to a previously unoccupied location.

Direct exchange A product changes location with another product.

Indirect exchange 1 A product is moved to another location which is occupied by another product. The latter product is moved to a third, empty location.

Indirect exchange 2 A product is moved to a new location which is occupied by a second product. The second product is moved to a new location which is occupied by a third product. The third product is moved to the original location of the first product.

The above scenarios are all associated with varying levels of effort, ranging from the lightest in scenario I, to the heaviest in IV. Kübler et al. quantify these efforts by including both physical and administrative times, which are transformed to effort terms by proposed proportionalities.

Concerning SLAP optimizers, proposals include models capable of obtaining optimal solutions, such as Mixed Integer Linear Programming (MILP), dynamic programming and branch and bound algorithms [ 7 ]. The warehouse environment is often simplified to a significant degree when optimal solutions are sought [ 7 , 13 , 16 , 19 ]. The main simplification relates to order-picking using COI or OOS. Other simplifications involve limiting the number of products [ 13 ], number of locations [ 30 ], or by requiring the conventional warehouse rack layout [ 18 ]. The conventional layout assumes Manhattan style blocks of aisles and cross-aisles, and it is used almost exclusively in existing literature on the SLAP (we are only aware of two exception cases using the “fishbone” and “cascade” layouts [ 6 , 7 ].

Most proposed SLAP optimizers provide non-exact solutions using heuristics or meta-heuristics. One example is multi-phase optimization where the first phase proposes possible locations for products, and the second phase carries out the assignments and evaluates them [ 32 ]. In Kübler et al. [ 18 ], a heuristic zoning optimizer is used to generate location assignments, and a Discrete Evolutionary Particle Swarm Optimizer (DEPSO) is used to optimize an OBP for the evaluation of the assignments. DEPSO is a modification of a standard PSO algorithm that addresses the risk of convergence on local minima and allows for a discrete search space. Other heuristic or meta-heuristic approaches include Genetic and Evolutionary Algorithms [ 9 , 20 ], Ant Colony Optimization [ 34 ] and Simulated Annealing [ 35 ]. If TSP optimization is desired within a SLAP, S-shape or Largest Gap algorithms [ 28 ] are often utilized. For TSP-optimization on unconventional layouts with a pre-computed distance matrix, Google OR-tools or Concorde have been proposed [ 22 , 27 ].

Evaluating the quality of results in prior work is challenging due to the variability of SLAP models. Below are a few examples where result quality is judged based on a percentage saving in travel distance or time: For conventional warehouse layouts, reassignment costs and dynamic picking patterns, Kofler et al. [ 16 ], report best savings around 21%. Kubler et al. (2020), report best savings around 22% in a similar scenario. Zhang et al. [ 35 ] report best savings around 18% on simulated data with thousands of product locations, but without reassignment costs. In a similar setting, for a few hundred products, Trindade et al. (2022) report best savings around 33%.

Nested Metropolis Sampling

The proposed optimizer (section “ Optimization Algorithm ”) is based on a nested Metropolis algorithm first introduced by Christen and Fox [ 8 ]. The Metropolis algorithm is a type of Markov Chain Monte Carlo (MCMC) method, which first draws a sample \({x}_{i+1}\) based on a desired feature distance (excluding costs) to a previous sample \({x}_{i}\) . The distance is given by some probability distribution \(q\left({x}_{i+1}|{x}_{i}\right)\) , and it is usually chosen such that the distance between \({x}_{i+1}\) and \({x}_{i}\) is low with a high probability (Mackay 1998). The accept probability is then computed based on some function that takes the costs of the new and previous samples as input [ 29 ]. Common Metropolis sampling assumes that there is only one cost function, \({f}^{*}\) , and since we wish to include an approximation of this cost, \(f\) , we use a modification [ 8 ]. Nested Metropolis sampling is shown in flowchart form in Fig.  1 .

Nested Metropolis Sampling. The inner loop computes a cheap (in terms of CPU-time) approximation of a sample cost and if the approximation is strong, the sample is promoted to the outer loop where an expensive ground-truth cost is computed

After a first sample \({x}_{i}\) has been initialized (i), a new sample \({x}_{i+1}\) is generated (ii) and its cost approximated \(f\left({x}_{i+1}\right)\) (iii). If the approximation is deemed strong enough (probabilistically) relative to \(f\left({x}_{i}\right)\) , the sample is promoted (iv) to the next step where its ground-truth cost \({f}^{*}\left({x}_{i+1}\right)\) is computed (v). The accept filter (vi) is only used for promoted samples.

For a cost minimization problem, the promote and accept probabilities can be computed based on the following equations [ 8 ]:

where \(\alpha \left({x}_{i+1}|{x}_{i}\right)\) denotes the promote probability and \({\alpha }^{*}\left({x}_{i+1}|{x}_{i}\right)\) the accept probability.

Problem Formulation

Objective function.

The objective function in the OBP-based SLAP is based on the ones formulated in Henn and Wäscher [ 14 ] and Oxenstierna et al. [24], i.e., the minimization of cost in an Order Batching Problem (OBP):

where \(\mathcal{O}\) denotes orders, where \(\mathcal{B}\) denotes batches and where \({D}^{x}\left(b\right)\) denotes the distance of a TSP solution, i.e., the distance needed to pick batch \(b\) . Batch \(b\) is a set of orders and \(v\in V\) denotes a vehicle. Each vehicle can carry one batch and the number of orders that can fit in the batch is governed by vehicle capacity (such as dimensions, bins, number of orders or products). \({a}_{vb}\) denotes a binary variable set to 1 if vehicle \(v\) is assigned to pick \(b\) and 0 otherwise. Orders consist of products \(\mathcal{O}\in {2}^{\mathcal{P}}\) , where each product \(p\in \mathcal{P}\) is a tuple consisting of a unique key (Stock Keeping Unit), a Cartesian location \(loc\left(p\right)\) , and a positive quantity of how many \(p\) are available at \(loc\left(p\right)\) . The locations of all products are given by location assignment vector \(x\) , where the elements represent products and the indices locations (each index is mapped to a Cartesian coordinate).

The mapping of location keys to coordinates and computation of distances between pairs of locations is based on a digitization pipeline for warehouses on any 2D obstacle layout and usage of the Floyd-Warshall graph algorithm. Details on this digitization pipeline and the OBP (including TSP-optimization for \({D}^{x}(b)\) and usage of vehicle capacity in \({a}_{vb}\) ) are beyond the scope of this paper, so for specifics we refer to Oxenstierna et al. [24] and Rensburg [ 27 ].

The difference between the OBP and the OBP-based SLAP mainly concerns product locations. In Oxenstierna, van Rensburg, et al. (2021) each product p  ∈  “has a [fixed] location”, meaning that \(x\) in \({f}^{*}\left(x\right)\) is immutable. In the OBP-based SLAP, however, a subset of products \({\mathcal{P}}_{s}\subset \mathcal{P}\) do not have fixed locations, which means that some elements in \(x\) can change indices in the vector. The OBP-based SLAP objective consists of finding location assignment \(x\) such that the OBP in Eq.  3 is minimized:

This objective lacks reassignment costs and is therefore a version of the “empty storage location” scenario I in Kübler et al. [ 18 ] (section “ Related Work ”). Exclusion of reassignment costs is motivated for this scenario, since the initial location assignment of new products in a warehouse is not optional, but a requirement. The other of Kübler et al.’s scenarios are all reassignments. Contrary to the initial assignments that we work with, reassignments are optional and potential gains in travel cost must there be weighed against reassignment costs.

Although reassignments should ideally be included in a complete SLAP model, a standardized SLAP needs to be a trade-off between simplicity and complexity. In the TSP-based SLAP [ 23 ] it is shown that the optimization of reassignments is NP-hard and not easily combined with order-picking optimization within a SLAP. The TSP-based SLAP includes reassignments, but uses the TSP instead of the OBP to optimize order-picking. The OBP-based SLAP excludes reassignments, but includes the OBP, a significantly more challenging problem than the TSP. As is often the case in literature on the SLAP, choice of optimization model depends on which features are considered more important for the usecase at hand.

Fast OBP Cost Approximation

One key difficulty with the OBP-based SLAP is that the OBP poses a highly intractable problem. Even for relatively small OBP instances, a significant amount of CPU-time is needed to obtain substantial cost improvements [ 18 , 22 ]. In the case of the OBP-based SLAP, this means that it would require a large amount of CPU-time to minimize cost for many assignment candidates \(x\) (Eq.  4 ). To resolve this problem, we propose to include an approximation of \({f}^{*}\left(x\right)\) :

where \(w\) denotes weight, where \({d}_{{l}_{1}{l}_{2}}^{x}\) denotes distance between two locations \({l}_{1},{l}_{2}\) and \(a\left(p,l\right)\) a function which returns 1 if product \(p\) is located at location \(l\) and 0 otherwise. \(f\left(x\right)\) is the element-wise summation of weights times distances. The cell values in the weight matrix represent the number of times two products, \({p}_{1},{p}_{2}\) , appear in the same order \(o\in \mathcal{O}\) . The (shortest) distances between all pairs of product locations are assumed pre-computed and stored in memory. We refer to Eq.  5 as the Quadratic Assignment Problem (QAP) model. Note that we never minimize it. For the \(f\left(x\right)\) approximation to be of use, we proceed to discuss how its ability to predict \({f}^{*}\left(x\right)\) can be evaluated.

Assuming a dataset of finite samples with approximated and ground truth costs \(\left(x,{f\left(x\right), f}^{*}\left(x\right)\right)\in X,|X|\in {\mathbb{Z}}^{+}\) , \({f\left(x\right), f}^{*}\left(x\right) \in {\mathbb{R}}^{+}\) , the predictive quality of \(f\left(X\right)\) versus \({f}^{*}\left(X\right)\) is obtainable through softmax cross-entropy [ 4 , 5 ]:

where \({\mathbb{P}}\left(f\left({x}_{i}\right)\right)\) and \({\mathbb{P}}\left({f}^{*}\left({x}_{i}\right)\right)\) denote the probabilities of approximate and ground truth costs of sample \({x}_{i}\) , respectively, where \(\left({x}_{i},{f\left({x}_{i}\right), f}^{*}\left({x}_{i}\right)\right)\in X\) . \(L\) is the loss , i.e., a distance heuristic between \(f\left(X\right)\) and \({f}^{*}\left(X\right)\) . This approach can be extended into Normalized Discounted Cumulative Gain (NDCG) [ 4 ].

\({\pi }_{f\left(X\right)}\) is a ranking (an ordering of samples \(X\) according to their costs \(f(X)\) ) and \(rel({\pi }_{f\left(X\right)}\left(i\right))\) is the relevance at rank \({\pi }_{f\left(X\right)}\left(i\right)\) . \(IDCG\) denotes an ideal value, where \(rel({\pi }_{{f}^{*}\left(X\right)}\left(1\right))>rel({\pi }_{{f}^{*}\left(X\right)}\left(2\right))>\dots > rel({\pi }_{{f}^{*}\left(X\right)}\left(|X|\right))\) , i.e., the case when the relevance of a sample corresponds with how highly it is ranked. Bruch et al. [ 4 ] argue that NDCG is a stronger choice than softmax cross-entropy whenever cost is non-binary, which is the case in \({f}^{*}\left(x\right)\) (Eq.  3 ). In Fig.  13 (Appendix) an example is shown where NDCG is computed from \(\left|X\right|\) samples.

In summary, we can quantify the predictive quality of the QAP model by its ability to rank a list of samples \(X\) against a ground truth ranking by the OBP optimizer. Since the nested Metropolis algorithm in section “ Nested Metropolis Sampling ” only stores two samples at any iteration, we modify the algorithm to instead work with more samples (section “ Optimization Algorithm ”). We also want to avoid the computation of \({f}^{*}\left(X\right)\) in each iteration, so in the optimization algorithm we only compute \({f}^{*}\left(argmi{n}_{x} f\left(X\right)\right)\) . In section “ Experiments ”, we conduct an experiment to test the validity of using the NDCG-based \({f}^{*}\left(argmi{n}_{x} f\left(X\right)\right)\) in SLAP optimization. In section “ Datasets ” we also discuss choice of datatype for the relevance values.

Optimization Algorithm

The proposed optimization algorithm includes three main modules: 1. a sample (location assignment) generator. 2. a fast cost approximator based on a model of the Quadratic Assignment Problem (QAP). 3. an Order Batching Problem (OBP) optimizer. In this paper, we mainly focus on how QAP approximations can be effectively utilized within the nested Metropolis sampler described in section “ Nested Metropolis Sampling ”. In sections “ Sample Generator ” and “ Promote and Accept Thresholds and Cost Computations ”, we therefore describe two main modifications. The final version (QAP-OBP) is shown in flowchart form in Fig.  2 and pseudocode in Algorithm 1.

QAP-OBP optimization algorithm

Sample \(x\) contains both the assigned products (products already in the warehouse) and the unassigned products \({\mathcal{P}}_{s}\) (section “ Problem Formulation ”). \({x}_{1}\) is initialized such that products \({\mathcal{P}}_{s}\) are assigned locations randomly without replacement. Choices for iterations \(K\) , the cost distance function \(\Delta\) and constant \({c}_{1}\) are discussed in section “ Experiments ”.

Sample Generator

The input to the sample generator (step ii in Fig.  2 ) is a single sample \({x}_{i}\) and the output is a list of new samples \({X}_{i+1}\) . There are two main parameters in use by the sample generator. \(N\in {\mathbb{Z}}^{+}\) dictates how many new samples are generated, i.e., \(|{X}_{i+1}|\) , and \(\uplambda \in {\mathbb{R}}^{+}\) dictates how much each new sample in \({X}_{i+1}\) differs from \({x}_{i}\) . The way \(N\) and \(\uplambda\) are utilized to generate new samples is shown in Algorithm 2.

Every time the sample generator is called, an empty list is first initialized. Then, for \(N\) iterations, a new sample \(x\) is generated by first copying \({x}_{i}\) and then by computing \(m\) , the number of products for which the index in \(x\) can change. For \(m\) we use a truncated Poisson distribution with rate \(\uplambda\) and upper bound \(m\le {|\mathcal{P}}_{s}|\) . A uniform random selection of \(m\) products, \({\mathcal{P}}_{m}\) , are then removed from \(x\) . For each \(p\in {\mathcal{P}}_{m}\) , a uniform random free index (either an empty location or an index holding a product in \({\mathcal{P}}_{s}\) ) in \(x\) is then selected such that the quantity ( \(q\) ) of the product does not exceed the location’s capacity. After \(x\) has been filled, it is appended to \({X}_{i+1}\) .

Promote and Accept Thresholds and Cost Computations

After a list of samples \({X}_{i+1}\) has been generated (step ii in Fig.  2 ), their costs are approximated using the QAP model (iii). The sample with the lowest cost approximation is then always promoted (iv). Steps ii, iii and iv in both the nested Metropolis sampler and QAP-OBP (Figs.  1 and 2 , respectively) are the same considering that the final output is a single promoted sample. There are advantages and disadvantages of both versions regarding how they conduct this selection. In the nested Metropolis sampler, the promote probability depends on the ratio of approximated cost between previous and new single samples. In QAP-OBP, the sample generator is instead set to output \(N=\left|{X}_{i+1}\right|\) candidates, followed by argmin (compare step iv in Figs.  1 and 2 ). This modification simplifies evaluation of the QAP model’s accuracy, since we can set up an experiment to compute OBP costs on the same samples (Fig.  5 ). Generating multiple samples could also facilitate parallelization, which, for future work, could reduce the QAP model’s CPU-time. The main consideration, however, is that it simplifies the original algorithm for a particularly complex optimization scenario, where it cannot be expected to behave according to Christen and Fox’s [ 8 ] performance guarantees. The problem with the original algorithm is that it assumes optimal ground-truth costs, but these are not generally available for OBPs [ 22 ] (as far as we are aware, there exists no proposal for how to obtain optimal results for but the smallest OBP instances within reasonable CPU-time). A relatively minor problem with the modification is that it requires tuning of the number of samples ( \(N\) ) that the sample generator is outputting each iteration. The reason we use a Metropolis algorithm instead of possibly more capable meta-heuristic alternatives, is mainly due to implementation. The Metropolis algorithm does not have many parameters which could be tuned based on iterations \(K\) (such as the temperature in Simulated Annealing) and therefore, a time-based condition can be used instead of \(K\) to terminate the algorithm (we will use this in section “ SLAP optimization with and without QAP approximation ”).

Concerning computation of \({f}^{*}(x)\) we use the Single Batch Iterated (SBI) optimizer and its main features are its high computational efficiency and its ability to handle warehouses with unconventional rack layouts [ 22 ]. OBP optimization and its internal use of TSP optimization, is beyond the scope of this paper, and we here treat SBI as a black-box which outputs a \({f}^{*}\left(x\right)\) for Eq.  3 . The sample \(x\) with the lowest \({f}^{*}\left(x\right)\) found is always stored throughout the optimization procedure (sample storage is omitted in Figs.  1 , 2 and the pseudo-code).

For this paper, we have generated and shared instances in L17_533, Footnote 1 which are based on OBP instances in L6_203 Footnote 2 and L09_251. Footnote 3 We also use data from a real warehouse (Aba Skol AB). The generated instances use the TSPLIB format [ 26 ] with certain amendments for the SLAP, including 6 types of warehouse obstacle layouts, various depot configurations, vehicle capacities and orders (see Fig.  3 for an example of one of the layouts). L17_533 does not include any unidirectional travel rules, meaning that the distance between any two locations is equal both ways. The number of orders range between 4 to 1000 and number of products range between 10 to 3000. The products that are to be assigned a location, \({\mathcal{P}}_{s}\) , are tagged as “SKUsToSlot” in the instance set. The “assignmentOptions” includes the available empty locations and how cost is to be computed (it is always set to the “empty storage location” scenario). For analysis, instances are categorized according to vehicle capacities, number of orders, products and parameters \(N\) and \(\uplambda\) .

Example storage assignment of four products and subsequent order-picking for the SLAP model used in the paper. Rectangles denote warehouse racks. Red and blue diamonds denote origin/destination for picking paths. Colored dots denote products and the four orders they belong to. Black crosses denote available locations for the new products. Note that products are often more spread out than what is shown in this example

The industrial warehouse dataset (Fig.  4 ) contains 210,277 products in 37,014 orders collected using batch picking over a 4-month period. There are 1289 pick-locations (in the graph representation) and most batches exist within one of six picking zones, but 24.4% include picks from several zones. As with the generated instances, shortest distances and paths between any two locations are assumed equal. For a proof of concept, we select product subsets from this data to be of relevance to warehouse management and real-world utility, on the one hand, and comparability to the generated instances, on the other. We build 150 subsets from 3-week periods with selections of between 50–1800 products for \(\mathcal{P}\) and between 10 and 225 corresponding products for \({\mathcal{P}}_{s}\) . The subset selection is random apart from that the products in a subset must exist within the same 3 week period. Number of free locations is given on a per-product basis, since each product has specific constraints regarding where it can be placed, and on average it varies between 50 – 481 locations. For parameters \(N\) and \(\uplambda\) , we explore suitable values on the generated instances within shorter optimization runs, followed by longer runs with chosen constants on the real dataset.

Top-view of the Aba Skol AB warehouse. The picking zones are color-coded. The red circle denotes the most commonly used depot location

Experiments

Overview and constants.

The experiments are divided into two parts. The first part involves tuning the QAP model and comparing its ability to rank SLAP assignment samples against an OBP ground truth model and a random baseline (Fig.  5 ).

Steps involved to obtain QAP predictive quality on samples generated from an instance

A SLAP test-instance (orders with products) is first loaded (i) and \({x}_{1}\) initialized (products \({\mathcal{P}}_{s}\) are assigned free locations in \({x}_{1}\) randomly) (ii). Then, \(N\) location assignments, \({X}_{i+1}\) , are generated according to Algorithm 2 (iii). The cost of the generated assignments is estimated using the QAP model and the OBP optimizer SBI (iv). The samples and costs are used to compute IDCG and DCG (v). IDCG is computed from the ranking of costs according to the OBP optimizer and DCG is computed from the ranking of costs according to the QAP model. A random DCG value is also pre-computed using the average of \({10}^{6}\) random rankings. This random baseline represents the case when \(f\left({X}_{i+1}\right)\) and \(argmi{n}_{x+1} f\left({X}_{i+1}\right)\) (steps iii and iv in Fig.  3 ) cannot help produce a lower value in \({f}^{*}\left({x}_{i+1}\right)\) (step v) [ 11 , 12 ]. Relevance values \(rel({\pi }_{{f}^{*}\left(X\right)})\) and \(rel({\pi }_{f\left(X\right)})\) are chosen to be the ordinal ranks of samples \(x\) according to respective cost functions. For \(N\) samples, the values are \(rel\left({\pi }_{{f}^{*}\left(X\right)}\right)={(\pi }_{{f}^{*}\left(X\right)}\left(N\right), {\pi }_{{f}^{*}\left(X\right)}\left(N-1\right), \dots , {\pi }_{{f}^{*}\left(X\right)}\left(1\right))\) and \(rel\left({\pi }_{f\left(X\right)}\right)={(\pi }_{f\left(X\right)}\left(N\right), {\pi }_{f\left(X\right)}\left(N-1\right), \dots , {\pi }_{f\left(X\right)}\left(1\right))\) (this corresponds to the set up shown in Fig.  13 in Appendix). The DCG value obtained from the QAP model is then used to compute NDCG according to Eq.  9 (vi). The predictive quality is finally calculated by subtracting the achieved NDCG value with the random NDCG baseline, with a positive value implying that the QAP model is stronger. We also record the CPU-time needed for the QAP model and the OBP-optimizer, respectively. The tuning of the QAP model concerns parameters \(N\) (number of samples) and \(\uplambda\) (rate of change for the samples) to maximize NDCG. We further investigate whether NDCG is impacted by other factors, including warehouse layout and instance size. Instance size is used to provide a quantification of instance difficulty, and here we restrict it to number of orders, total number of products \(\left|\mathcal{P}\right|\) and products which are to be assigned a location \({|\mathcal{P}}_{s}|\) . The latter number, \({|\mathcal{P}}_{s}|\) , is computed as 5–10% of \(\left|\mathcal{P}\right|\) in the instance.

We proceed with a second experiments part, where we run the SLAP optimizer (Algorithm 1) on the industrial instances with and without the QAP model. For the experiments without the QAP model, \(N=1\) and lines 11 and 12 in Algorithm 1 are removed. This second part is carried out after suitable constants for \(N\) and \(\uplambda\) values have been found on the L17_533. In order to find such constants, we run the steps in Fig.  5 for 10 \(N\) values ranged between 1–200 and 10 \(\uplambda\) values set between 5–50% of \({|\mathcal{P}}_{s}|\) . For the experiments to test \(N\) , we use \(\uplambda =15\mathrm{\%}\) of \({|\mathcal{P}}_{s}|\) . For the experiment to test \(\uplambda\) , we use \(N= 50\) . For the cost distance function \(\Delta\) we use a scaled sigmoid, which is set to approach 1 when the ratio \({f}^{*}\left({x}_{i}\right)/{f}^{*}\left({x}_{i+1}\right)\) exceeds 1.05. This means that sample \({x}_{i+1}\) is unlikely to be accepted if its cost is 5% higher than that of \({x}_{i}\) . For each instance, the global best OBP result is tracked and uploaded as the current best result. We refer to the documentation in L17_533 for further details. We use Intel Core i7-4710MQ 2.5 GZ 4 cores, 32 GB RAM, Python3, Cython and C.

The Impact of Parameters \({\varvec{N}}\) and \(\uplambda\) on QAP Predictive Quality

Concerning \(N\) , we first observe that the average predictive quality of the QAP model is equivalent to the random baseline when \(N=1\) (Fig.  6 ). We further observe that mean predictive quality rises steadily until \(N\) is 20, after which it tapers off.

Boxplot showing number of samples ( \(N\) ) against QAP predictive quality. The red line denotes the NDCG random baseline. The box edges show the first and third quartiles of the data (Q1, Q3) and the whiskers show (Q1 – 1.5 * IQR, Q3 + 1.5 * IQR), where IQR is the Inter Quartile Range

The result clearly shows that the QAP model is able to rank samples better than the random baseline (negative values imply the opposite). The positive initial trend could be impacted by the choice of ordinal relevance values \(rel({\pi }_{f\left(X\right)})\) for the NDCG computation (section “ Overview and Constants ”), which could favour the baseline for smaller \(N\) .

Concerning rate of change of new samples \(\uplambda\) , the best results are achieved when it is set toward the lower end of the 5–50% range of \(\left|{\mathcal{P}}_{S}\right|\) (Fig.  7 ). This provides some validation for the use of a Metropolis algorithm, since it shows that a Markov Chain can be used to nudge samples closer towards lower costs. Otherwise, NDCG would be similar regardless of the x-axis in Fig.  7 . This result is in line with Oxenstierna et al. [ 23 ], where a slightly stronger pattern is observed on the related TSP-based SLAP.

How much new samples are changed compared to previous samples ( \(\uplambda\) ) against QAP predictive power

The Impact of Other Factors on QAP Predictive Quality

Results for all factors are shown in Tables  1 , 2 and 3 (Appendix). We find that QAP predictive quality decreases as instance size increases (Fig.  8 ). This may be due to that the quality of \({f}^{*}(x)\) costs provided by the OBP optimizer decrease with instance size (they are sub-optimal, see section “ Promote and Accept Thresholds and Cost Computations ”), making analysis of results for larger instance classes more difficult in general. We find that the fraction of CPU-time required by the QAP model versus the OBP optimizer is between 0.006–0.019, or around 50–150 times faster. The difference is largest for the largest instances and smallest for the smallest instances (Table  2 ). We do not observe any relationship between QAP predictive quality and warehouse layout.

Instance size in terms of number of orders, versus the predictive quality of the QAP model and the random baseline

Overall, the result provides evidence that QAP approximations of OBP costs within an OBP-based SLAP optimizer may be justified. Its predictive quality may decrease with instance size, relative to the OBP optimizer (Fig.  7 ), but its relative usage of CPU-time also decreases. Another way to visualize the performance difference between the QAP model and the random baseline is through a frequency distribution (Fig.  9 ).

Frequency distribution of NDCG values (20 bins) from QAP and random ranking of samples when \(N=20\) and \(\lambda =10\%\) (of \(\left|{\mathcal{P}}_{S}\right|\) )

SLAP Optimization With and Without QAP Approximation

We report results from running the QAP-OBP SLAP optimizer (section “ Optimization Algorithm ”) on the industrial dataset with and without the use of QAP approximations. Apart from general settings (section “ Overview and Constants ”), \(K\) is set to \({10}^{8}\) and the algorithm is set to terminate after 60 min (which, given maximum OBP and QAP CPU-times, ensures iterations never exceed \(K\) ). \(\lambda\) is set to \(10\%\) of \(\left|{\mathcal{P}}_{S}\right|\) and \({c}_{1}=1\) . \(N\) is set to 20, which means that the QAP model will have a relatively small impact on overall CPU-time. \(N\) could theoretically be set to a much larger number, but this may not necessarily yield better results. The QAP model in the form of Eq.  5 likely needs to be further developed before its extended use can be motivated. One risk with setting \(N\) to a large number is that the SLAP optimizer will spend too much time in search regions with a low QAP cost, rather than in regions with a low OBP cost.

In Fig.  10 , we see that Algorithm 1, on average, improves cost by around 23% in 1 h. Without QAP approximations, cost improves by around 17%.

SLAP optimization cost improvements with and without the QAP model during 1 h. The shaded areas denote 95% confidence intervals

The size of the instances has a significant impact on computational efficiency. In Figs.  11 and 12 , we see that the impact of instance size, in terms of number of products that are assigned a location, | \({\mathcal{P}}_{s}\) |, has a similar effect on computational efficiency regardless of whether the QAP is used. The stronger performance of the smaller instances can largely be attributed to more samples being generated within the 60 min. On average, cost improvement continues throughout the time, which is explainable due to the large SLAP search space.

QAP-OBP SLAP cost improvement using QAP approximations for 5 categories of instance sizes (in terms of | \({\mathcal{P}}_{s}\) |). Shaded areas denote data within 1 standard deviation

Same as Fig.  11 , but without using QAP approximations

In this paper, we:

formulate an optimization model for the Storage Location Assignment Problem (SLAP), where the costs of assignments are evaluated using Order Batching Problem (OBP) optimization.

share generated SLAP test instances, with the goal to standardize formats and comparability between solution approaches.

propose a Quadratic Assignment Problem (QAP) model to quickly approximate OBP costs in SLAP optimization. The QAP model is tested and tuned on the generated instances.

propose a SLAP optimizer (QAP-OBP), which we test on industrial instances with a 1 h optimization timeout.

Within the QAP-OBP optimizer, the QAP and OBP modules are utilized in a Metropolis algorithm, where samples are modified by a variable amount each iteration. The algorithm is nested such that OBP costs are only computed for samples with a relatively strong QAP cost approximation.

In order to motive the use of the QAP model within the algorithm, experiments are first conducted to test its predictive quality against costs obtained by the OBP optimizer and a random baseline. Results show that QAP predictive quality is stronger than the baseline, and that they are around 50–150 times faster to compute than the cost obtained through OBP optimization.

We then proceed to run the SLAP optimizer with and without the QAP approximations. We find that the optimizer performs better when using the QAP approximations, with cost improvements of around 23% after 1 h. This result is in line with results in related work on SLAPs that are less difficult in some regards (for example concerning warehouse layouts), but more difficult in others (dynamicity or larger number of products).

For future work, the parameter which controls the number of samples that should be approximated by the QAP model for every OBP cost computation, \(N\) , could be tuned. The QAP computations could be significantly sped up by the use of parallelization and Graphical Processing Units (GPU), extending its utility within the SLAP optimizer for larger \(N\) . Also, alternative optimization approaches could be explored. These include meta-heuristic techniques such as Simulated Annealing or Particle Swarm Optimization. The QAP cost approximator could also be developed for a Machine Learning approach and used in a similar fashion as the weak estimators in boosting or aggregate bootstrapping. The factorial search space remains a fundamental problem for learning, however. Finally, we invite discussions into how to best represent SLAP features in public benchmark data and which features to choose for a standardized version of the problem.

https://github.com/johanoxenstierna/L17_533 , collected 13–02–2023.

https://github.com/johanoxenstierna/OBP_instances , collected 15–01–2023.

https://github.com/johanoxenstierna/L09_251 , collected 15–01–2023.

Abdel-Basset M, Manogaran G, Rashad H, et al. A comprehensive review of quadratic assignment problem: variants, hybrids and applications. J Ambient Intell Human Comput. 2018. https://doi.org/10.1007/s12652-018-0917-x .

Article   Google Scholar  

Aerts B, Cornelissens T, Sörensen 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 .

Article   MathSciNet   Google Scholar  

Azadeh K, De Koster R, Roy D. Robotized warehouse systems: developments and research opportunities. ERIM report series research in management Erasmus Research Institute of Management. ERS-2017-009-LIS. 2017.

Bruch S, Wang X, Bendersky M, Najork M. An analysis of the softmax cross entropy loss for learning-to-rank with binary relevance. In: Proceedings of the 2019 ACM SIGIR international conference on the theory of information retrieval (ICTIR 2019). 2019. pp. 75–8.

Cao Z, Qin T, Liu T-Y, Tsai M-F, Li H. Learning to rank: from pairwise approach to listwise approach. In: Proceedings of the 24th international conference on machine learning, vol. 227. 2007. pp. 129–36. https://doi.org/10.1145/1273496.1273513 .

Cardona LF, Rivera L, Martínez HJ. Analytical study of the fishbone warehouse layout. Int J Log Res Appl. 2012;15(6):365–88.

Charris E, Rojas-Reyes J, Montoya-Torres J. The storage location assignment problem: a literature review. Int J Ind Eng Comput. 2018;10.

Christen JA, Fox C. Markov Chain Monte Carlo using an approximation. J Comput Graph Stat. 2005;14(4):795–810.

Ene S, Öztürk N. Storage location assignment and order picking optimization in the automotive industry. Int J Adv Manuf Technol. 2011;60:1–11. https://doi.org/10.1007/s00170-011-3593-y .

Fontana ME, Nepomuceno VS. Multi-criteria approach for products classification and their storage location assignment. Int J Adv Manuf Technol. 2017;88(9):3205–16.

Freund Y, Iyer R, Schapire RE, Singer Y. An efficient boosting algorithm for combining preferences. J Mach Learn Res. 2003;4(Nov):933–69.

MathSciNet   Google Scholar  

Freund Y, Schapire RE. Experiments with a new boosting algorithm. 1996.

Garfinkel M. Minimizing multi-zone orders in the correlated storage assignment problem. School of Industrial and Systems Engineering, Georgia Institute of Technology. 2005.

Henn S, Wäscher G. Tabu search heuristics for the order batching problem in manual order picking systems. Eur J Oper Res. 2012;222(3):484–94.

Kallina C, Lynn J. Application of the cube-per-order index rule for stock location in a distribution warehouse. Interfaces. 1976;7(1):37–46.

Kofler M, Beham A, Wagner S, Affenzeller M. Affinity based slotting in warehouses with dynamic order patterns. Advanced methods and applications in computational intelligence. 2014. pp. 123–43.

de Koster R, Le-Duc T, Roodbergen KJ. Design and control of warehouse order picking: a literature review. Eur J Oper Res. 2007;182(2):481–501.

Kübler P, Glock CH, Bauernhansl T. A new iterative method for solving the joint dynamic storage location assignment, order batching and picker routing problem in manual picker-to-parts warehouses. Comput Ind Eng. 2020;147: 106645.

Larco JA, de Koster R, Roodbergen KJ, Dul J. Managing warehouse efficiency and worker discomfort through enhanced storage assignment decisions. Int J Prod Res. 2017;55(21):6407–22. https://doi.org/10.1080/00207543.2016.1165880 .

Lee IG, Chung SH, Yoon SW. Two-stage storage assignment to minimize travel time and congestion for warehouse order picking operations. Comput Ind Eng. 2020;139: 106129. https://doi.org/10.1016/j.cie.2019.106129 .

Mantel R, Schuur P, Heragu S. Order oriented slotting: a new assignment strategy for warehouses. Eur J Ind Eng. 2007;1:301–16.

Oxenstierna J, Malec J, Krueger V. Efficient order batching optimization using seed heuristics and the metropolis algorithm. SN Comput Sci. 2022;4(2):107.

Oxenstierna J, Rensburg L, Stuckey P, Krueger V. Storage assignment using nested annealing and hamming distances. In: Proceedings of the 12th international conference on operations research and enterprise systems—ICORES. 2023. pp. 94–105. https://doi.org/10.5220/0011785100003396 .

Oxenstierna J, van Rensburg LJ, Malec J, Krueger V. Formulation of a layout-agnostic order batching problem. In: Dorronsoro B, Amodeo L, Pavone M, Ruiz P, editors. Optimization and learning. Berlin: Springer International Publishing; 2021. p. 216–26.

Chapter   Google Scholar  

Ratliff H, Rosenthal A. Order-picking in a rectangular warehouse: a solvable case of the traveling salesman problem. Oper Res. 1983;31:507–21.

Reinelt G. TSPLIB—a traveling salesman problem library. INFORMS J Comput. 1991;3:376–84.

Rensburg LJ. Artificial intelligence for warehouse picking optimization—an NP-hard problem [Master’s Thesis]. Uppsala University. 2019.

Roodbergen KJ, Koster R. Routing methods for warehouses with multiple cross aisles. Int J Prod Res. 2001;39(9):1865–83.

van Ravenzwaaij D, Cassey P, Brown SD. A simple introduction to Markov Chain Monte-Carlo sampling. Psychon Bull Rev. 2018;25(1):143–54. https://doi.org/10.3758/s13423-016-1015-8 .

Wu J, Qin T, Chen J, Si H, Lin K. Slotting optimization algorithm of the stereo warehouse. In: Proceedings of the 2012 2nd international conference on computer and information application (ICCIA 2012). 2014. pp. 128–32. https://doi.org/10.2991/iccia.2012.31 .

Wu X, LuWuZhou JSX. Synchronizing time-dependent transportation services: reformulation and solution algorithm using quadratic assignment problem. Transport Res Part B Methodol. 2021;152:140–79. https://doi.org/10.1016/j.trb.2021.08.008 .

Wutthisirisart P, Noble JS, Chang CA. A two-phased heuristic for relation-based item location. Comput Ind Eng. 2015;82:94–102. https://doi.org/10.1016/j.cie.2015.01.020 .

Yang N et al. Evaluation of the joint impact of the storage assignment and order batching in mobile-pod warehouse systems. Math Probl Eng. 2022;2022.

Yingde L, Smith JS. Dynamic slotting optimization based on SKUs correlations in a zone-based wave-picking system. In: IMHRC proceedings, vol. 12. 2012.

Zhang R-Q, Wang M, Pan X. New model of the storage location assignment problem considering demand correlation pattern. Comput Ind Eng. 2019;129:210–9. https://doi.org/10.1016/j.cie.2019.01.027 .

Zhou F, De la Torre F. Factorized graph matching. IEEE Trans Pattern Anal Mach Intell. 2016;38(9):1774–89. https://doi.org/10.1109/TPAMI.2015.2501802 .

Žulj I, Glock CH, Grosse EH, Schneider M. Picker routing and storage-assignment strategies for precedence-constrained order picking. Comput Ind Eng. 2018;123:338–47. https://doi.org/10.1016/j.cie.2018.06.015 .

Download references

Acknowledgements

This work was partially supported by the Wallenberg AI, Autonomous Systems and Software Program (WASP) funded by the Knut and Alice Wallenberg Foundation. We also convey thanks to Kairos Logic AB for software.

Open access funding provided by Lund University. This work was partially supported by the Wallenberg AI, Autonomous Systems and Software Program (WASP).

Author information

Authors and affiliations.

Dept. of Computer Science, Lund University, Lund, Sweden

Johan Oxenstierna, Jacek Malec & Volker Krueger

Kairos Logic AB, Lund, Sweden

Johan Oxenstierna

You can also search for this author in PubMed   Google Scholar

Corresponding author

Correspondence to Johan Oxenstierna .

Ethics declarations

Conflict of interest.

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.

Additional information

Publisher's note.

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

This article is part of the topical collection “Innovative Intelligent Industrial Production and Logistics 2022” guest edited by Alexander Smirnov, Kurosh Madani, Hervé Panetto and Georg Weichhart.

NDCG flowchart: the below example shows how Normalized Discounted Cumulative Gain (NDCG) can be computed from input permutations (products to locations), approximated ( \(f\) ) and ground truth ( \({f}^{*}\) ) values. Note that \(f\left(X\right)\) denotes a sorting of \(X\) according to the cost valuation of elements in the cost step. Also note that relevance values can be formulated in several ways.

NDCG procedure flowchart

Rights and permissions

Open Access This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article's Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article's Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/ .

Reprints and permissions

About this article

Oxenstierna, J., Malec, J. & Krueger, V. Storage Assignment Using Nested Metropolis Sampling and Approximations of Order Batching Travel Costs. SN COMPUT. SCI. 5 , 477 (2024). https://doi.org/10.1007/s42979-024-02711-w

Download citation

Received : 04 April 2023

Accepted : 14 February 2024

Published : 23 April 2024

DOI : https://doi.org/10.1007/s42979-024-02711-w

Share this article

Anyone you share the following link with will be able to read this content:

Sorry, a shareable link is not currently available for this article.

Provided by the Springer Nature SharedIt content-sharing initiative

• Storage location assignment problem
• Order batching problem
• Quadratic assignment problem
• Metropolis algorithm
• Warehousing

Advertisement

• Find a journal
• Publish with us
• Track your research