# Matching algorithm in an order batching problem

There is an order batching problem.

• Given a set of orders, they need to be split into several batches, with a maximum order number of M per batch.
• Each order needs to be picked from multiple storage areas. The set of storage areas is A.
• The goal is to find an optimal batching scheme, where the number of distinct storage areas (covered) is minimized for each batch.

To give an example, order o1 = {a, b, c} means that this order should be picked from storage areas a, b and c. order o2 = {b, c, d}, o3 = {e, f}, o4 = {e, h}, o5 = {j, k}. If M = 2, then the optimal solution is batch1 = {o1, o2} with cover storage areas {a, b, c, d}, batch2 = {o3, o4}, which cover areas {e, f, h}, and batch3 = {o5}.

I have tried some heuristics. Can anyone give some exact algorithms that use dynamic programming or graph matching? Since an MIP solver is not available in my project, so I want to find some domain specific algorithms.

• Welcome to OR.SE. Would you please, elaborate more on needs to be picked from multiple storage areas? Aug 24, 2023 at 8:37
• For example, the set of storage areas is A = {a,b,c,...}. The first order should be picked from areas a and c, the second order should be picked from b and c. If they are grouped into the same batch, then the distinct areas coverd is a, b and c.
– Ying
Aug 25, 2023 at 3:58
• Still in this subject, can we say that a single SKU s belongs to multiple areas (one-to-many relation)? Or an SKU belongs exclusively to an unique area (one-to-one)? Aug 25, 2023 at 13:34
• That is one-to-one relation. Just to explain that an order covers several areas, the objective is to combine the orders with the same areas. @MatheusDiógenesAndrade
– Ying
Aug 26, 2023 at 12:48

It seems the problem you are facing is very similar to the storage location optimization and is categorized into the warehouse optimization field and the following heuristic approach is highly effective for solving that.

Suppose there is an order $$O_1$$ with an order quantity equal to $$100$$. Now, based on the working procedure, it needs to be split into two batches with a maximum order number of $$50$$ per batch. I assumed this limitation would get back to the batch’s storage area. Also, there exist four different SKUs in the $$O_1$$ that need to be distinguished in the two batches by $$2-2$$. The first two SKUs should be picked in batch one, and the second two should be in the second batch. However, I still assumed the required quantity of each SKU in each order was equal to one.

By the above assumptions, the quantity of each required SKU is equal to $$100$$. Then without losing generality, and still by knowing each SKU needs a standard pallet, carton, or any packing list, we actually need $$100$$ packing boxes for each SKU. Now, if each of the batch storage areas can store only $$50$$ boxes, the distinct storage areas would be at least $$4$$ units of storage area. (E.g. number of racks, $$M^2$$, etc.). This actually comes from a concept so-called PFEP or plan for every part.

This situation is similar to when one would like to calculate the picking/packing area in the warehouse or determine the minimum number of WIP storage areas in the production line.

It seems to be a maximal clique problem. The larger the clique (subset of vertices- orders with a common storage area as edge) smaller will be number of storage areas covered.
Seems there's no straight forward algorithm possible in polynomial time but a Bron–Kerbosch algorithm has been referred. Other than that using my simple OR skills I can try an MIP & set covering technique. Define set of batches $$B$$ of same cardinality as number of orders $$O$$ because that's the maximum batch possible
Define multiple sets $$S_o$$ as the set of storage areas $$s$$ from where order $$o$$ can be picked. It can be a matrix also as $$M_{s,o}=1$$ if order can be picked from a storage area, else $$0$$

Optimization variable:
Binary $$x_{o,b}=1$$ if order $$o$$ is assigned to batch $$b$$, $$0$$ otherwise.

Binary $$y_{s,b} = 1$$ if storage $$s$$ is covered by a batch $$b$$,

Binary $$z_b = 1$$ if batch $$b$$ is chosen

Constraints
$$\sum_b x_{o,b} = 1 \quad \forall o$$

$$z_b \le \sum_o x_{o,b} + \sum_s y_{s,b}\le C_bz_b \quad \forall b$$: where $$C_b$$ may be a batch capacity in terms of orders or storage. You can split it also into one for constraining number of orders per batch & another with $$y$$ ensuring no storage is included in a batch unless batch is chosen

$$y_{s,b} \le \sum_o M_{s,o}x_{o,b} \le Ty_{s,b}$$
where $$T$$ is a big number like $$O \times S \times B$$

$$x_{o,b} \le \sum_{o' \in O \setminus o}\sum_{s} M_{s,o}M_{s,o'}x_{o',b} \quad \forall o, b$$
Or
$$x_{o,b} \le \sum_s M_{s,o}y_{s,b} \quad \forall o,b$$
Basically trying to constraint any order from being assigned to a batch if it doesn't share any storage area with any of the other orders

Objective
$$\min \sum_{s,b}y_{s,b}$$

Another way - TSP:
@Ying multiple shared storage areas imply multiple edges (multi-graph). There will be algorithms for clique creation for multi-graphs. Otherwise you can define your own heuristic.
You can also try with Travelling Salesman problem (TSP): visiting all nodes covering minimum number of edges (storage). Typically in TSP sub-tours (batches of nodes) are eliminated. Here you may preserve subtours.

• You inspire me. The problem seems to be a MCP. I still have some questions. In the graph, a node means an Order, en edge links two nodes mean that two orders share a common storage area. If two orders share several areas, how to explain this relationship in the graph? In this problem, if two orders have completely different areas, they may be grouped into the same batch, either, to satisfy the M constraint. However, it is impossible if two nodes have no links at all in the MCP. The MIP formulate the problem well, can we solve it with a domain spesific algorithm, instead of MIP solvers?
– Ying
Aug 26, 2023 at 13:12
• No reason to introduce $z_b$ or several of the constraints. It suffices to minimize $\sum_{s,b} y_{s,b}$ subject to $\sum_b x_{o,b}=1$ for all $o$ and $\sum_o x_{o,b}\le M$ for all $b$ and $x_{o,b}\le y_{s,b}$ if $s \in S_o$. Applying Dantzig-Wolfe decomposition by batch then would yield identical blocks, leading to a column generation approach that proposes one new batch at a time. Aug 26, 2023 at 14:06
• Right, I have tested the problem with SCIP. The formulation works, thank you. @RobPratt However, it is preferable not to rely on other third-party packages for the deployment. Therefore, I believe that dynamic programming or backtracking may be the best choice.
– Ying
Aug 28, 2023 at 2:10