There is an order batching problem.
- Given a set of orders O, they need to be split into several batches, with a maximum order number of M per batch.
- Each order includes multiple SKUs and so needs to be picked from multiple storage areas (since each sku may be stored in different area). 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.
