# Formulation and modeling of a logistics problem: Combination of bin packing and cutting stock problem?

I'm a Data Scientist with a strong mathematical background but don't know much apart from textbook material about Operations Research. I'm dealing with a logistics problem which I don't know how to approach. I've been reading the literature a bit and I think it might be a combination of a bin packing and of a cutting stock problem, but I would very appreciate if someone familiar with OR has already heard of a similar type of problem.

The idea is that we have a certain number $$m$$ of items each with defined weight, length, width and a certain number $$k$$ of customers. Typically, $$m$$ is rather small (around 50) while $$k$$ is large (around 30,000). Each customer can order a fixed quantity of each item, and we have that information in a matrix $$X=(x_{ij})_{1 \leq i \leq k, 1 \leq j \leq m}$$ where each coefficient $$x_{ij}$$ represents the demand of customer $$i$$ for item $$j$$.

We have $$N$$ ($$N$$ is rather small too, less than 6) machines that can pack objects into boxes called unit kits of 2 different types, with maximal length, width and weight capacity known for each type. Each machine can only pack one particular unit kit, meaning the same machine will always prepare the same type of unit kit with the same contents.

We're trying to find an optimal composition of these unit kits that allows us to satisfy the demand of all customers while minimizing costs (manufacturing the unit kits themselves comes with a certain cost that is increasing with the number of items contained in it). The idea is that, in order to satisfy a customer demand, one must resort to a linear combination of the unit kits :

• e.g. if unit kit number 1 contains 2 items A and unit kit number 2 contains 3 items B :
• a customer asking for 3 items A and 5 items B will get 2 unit kits number 1 and 2 unit kits number 2
• while a customer asking for 4 items B will get 2 unit kits number 2

In other words, given our capacity to prepare the unit kits and the customers’ demand, what should be the composition of the unit kits that we then combine together and dispatch to meet the customers’ demand?

This is not a classical bin packing problem as there are a limited number of unit kits, all of which are of fixed capacity, and once a machine prepares a certain unit kit, it cannot prepare another one. This is not a classical cutting stock problem as well, as the number of unit kits is limited and not infinite, and what we’re trying to find is the composition of the unit kits.

This might look like a scheduling or an assignment problem, but I have not found any standard problem in the literature that comes close with this one.

Does someone have already encountered this type of problem, or know what it's called, or have encountered literature about it and can provide references to help me approach the problem?

• Can unit kits be partially filled? In your example of a customer asking for 3 A and 5 B, is the second type 1 unit kit half-filled?
– prubin
Commented Apr 23 at 15:57
• Hi, thank you for your answer! Once the composition of unit kits has been established, it cannot be changed. And we can also only dispatch integer multiples of unit kits in orders. So the quantities constraints given by matrix $X$ are actually inequality constraints: we need to at least satisfy the customers demand. Any additional items will be either stocked or destroyed. So the only way of getting 3A and 5B with the exemple composition of units kits is as I stated. Does that answer your question?
– QLG
Commented Apr 23 at 18:10
• That's fine as long as you are OK with the stocking/destruction part.
– prubin
Commented Apr 23 at 18:15
• I am, that’s how the logistics proceed around here. And actually in the constraints set, there’s an additional stocking constraint, so we have to be above customers’ demands anyway. Any idea on how to tackle that or ever heard of similar problems? I actually found some literature on « kitting line optimization » as well, but it’s not the same type of problem. Here what we’re really trying to find as an output is the compotision of the unit kits, while minimizing a global cost.
– QLG
Commented Apr 23 at 18:23
• Search for "pack optimization" Commented Apr 23 at 20:11