I'm currently searching for an appropriate algorithm for the following problem.
The warehouse contains a bunch of pallets with boxes on them containing the same product. A full pallet contains 80 boxes. But there are a lot of pallets with less boxes. When the orders come in, some pallets need to be merged into one full pallet of 80 boxes. This action is done by hand so this is manual labour.
Now I'm looking for the optimal way to assign the pallets in the warehouse to the orders so that the amount of manual labour is reduced to the minimum.
example:
- Pallet A: 80 boxes
- Pallet B: 40 boxes
- Pallet C: 39 boxes
- order 1: 50 boxes
- order 2: 79 boxes
possible solutions
- order 1: pallet A - 30 boxes
- order 2: pallet B pallet C
=> total manual labour: 69 boxes moved
- order 1: pallet B 10 boxes from pallet C
- order 2: pallet A - 1 box
=> total manual labour: 11 boxes moved
The second solution is preferred because less labour is involved.
I had a look at the Hungarian algorithm, but I think that this is not the appropriate solution for this problem.
Do you have some suggestions?
CodePudding user response：
The Hungarian algorithm gives a 2-approximation (move at most twice as many boxes as needed). We match pallets to orders, where the cost of matching a pallet with an order is half the number of boxes that need to move onto or off of the pallet. (I gather that there will typically be more pallets than orders, so if your Hungarian algorithm implementation requires a square matrix, make fake orders that have zero cost to match with any pallet.) This is a 2-approximation because, to extend the observation from my comment, we save a box only if we can find both a pallet with too many boxes and a pallet with too few.
In other words, we pay the max of (the number of boxes that need to move off of a pallet) and (the number of boxes that need to move onto a pallet). This observation motivates the following two ideas.
We can formulate a mixed integer program (and then apply a solver library). There is a 0–1 variable x(i, j) for each pallet i and order j. We have constraints sum over i of x(i, j) = 1 (all orders have exactly one assigned pallet) and sum over j of x(i, j) ≤ 1 (all pallets have at most one assigned order). The objective to be minimized is a free variable z, where we constrain z ≥ sum over i, j of max(p(i) − o(j), 0) x(i, j); and z ≥ sum over i, j of max(o(j) − p(i), 0) x(i, j).
If you don’t want to do mixed integer programming for whatever reason (despite the fact that I think you really should), we can use a Lagrangian dual, introducing a parameter α ∈ [0, 1] and paying 1−α to move a box off of an order pallet and α to move a box onto an order pallet. The easy way to do this is to try a bunch of different α with the Hungarian algorithm, taking the best matching that results. The clever way is to solve the dual of the linear relaxation of the integer program above, then set α according to the dual variables corresponding to the constraints on z. But really you should use mixed integer programming.
I can give advice on solvers if you tell me your constraints.