3
$\begingroup$

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?

$\endgroup$
6
  • $\begingroup$ 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? $\endgroup$
    – prubin
    Commented Apr 23 at 15:57
  • $\begingroup$ 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? $\endgroup$
    – QLG
    Commented Apr 23 at 18:10
  • $\begingroup$ That's fine as long as you are OK with the stocking/destruction part. $\endgroup$
    – prubin
    Commented Apr 23 at 18:15
  • $\begingroup$ 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. $\endgroup$
    – QLG
    Commented Apr 23 at 18:23
  • $\begingroup$ Search for "pack optimization" $\endgroup$
    – RobPratt
    Commented Apr 23 at 20:11

1 Answer 1

1
$\begingroup$

This is somewhat similar to a cutting stock problem, with one distinction. In a typical cutting stock problem, you have a limited amount of stock but no explicit limit on the number of cutting patterns. Here, the number of "cutting patterns" (kits) is limited but the supply of "stock" (the number of each type of kit you use) is unlimited.

It's unclear what the significance of the number of machines is, but basically you'll want a model that (a) assigns kits to machines from a selection of available kits and then (b) schedules production of enough kits for each customer to cover their demand. Generating the selection of kits can be approached in a couple of ways. One possibility (somewhat unlikely, and dependent on the item sizes v. kit capacities) would be to compute all possible kits and include them in the model. Another possibility, which is heuristic in nature (not guaranteed to provide a provably optimal solution) is to produce them "on the fly" in a manner similar to what is used in common cutting stock heuristics.

The heuristic approach would probably look like this. Generate an initial set of kit types that hopefully would be able to cover your needs (i.e., make the model feasible). Solve the LP relaxation of the integer program and get the optimal dual values of the demand coverage constraints. Translate these (somehow) into values for individual items going into a new kit design, and then create a kit design that is optimal with respect to those values. Add that design to the set of kits in the master problem, rinse and repeat. When the heuristic fails to design a new kit (or exhaustion sets in, whichever comes first), restore the integrality restrictions and solve the master problem one last time.

$\endgroup$
1
  • $\begingroup$ Thank you for your answer and sorry for the delay in response! I actually like your idea and I'm gonna go forward with it! Will post again, should I have any question, but I'll try to move forward by myself. Thanks! $\endgroup$
    – QLG
    Commented Apr 29 at 13:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.