Matching algorithm in an order batching problem

Question

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.

Answer 1

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.

Answer 2

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.