-1

I have a problem formulation but it does not resemble the usual packing problem I find in the literature but it is a usual problem in the packing industry. I just do not know the name for it.

The problem formulation is as follows: I have a certain amount of objects with different weights (around 10000 objects with a weight between 1-4) and I want to pack them in boxes (around 100 to 200 boxes with a maxium weight of around 200). The objective is that all boxes should have the same weight (at least within a prefefined boundary). It is not mandatory that all objects are distributed.

How can I formulate this optimization problem (objective function, constraints etc.) and what algorithms may suitable to solve this problem?

Improve this question
9
  • 4
    This sounds like a Multiple knapsack problem.
    – Bart van Ingen Schenau
    Feb 22, 2021 at 13:27
  • Since you don't mention the objects' dimensions, are they the same for all objects?
    – Flater
    Feb 22, 2021 at 13:54
  • 3
    The problem description looks pretty unclear to me. Please clarify: (1) is the number of boxes fixed or subject to change? (2) What is the objective function you want to minimize? How do you measure precisely the deviation from "all boxes have the same weight"? (3) If there are non-distributed objects left, how are those taken into account in the former objective function?
    – Doc Brown
    Feb 22, 2021 at 20:57
  • 1
    This sounds like a Linear Programming (LP) problem, so a linear problem solver/optimiser may be helpful here. However, as Doc Brown mentions, you need to start by describing which parameters you're working with and particularly describe your bounds/constraints (e.g. breakdown and range of object weights, max permitted weight per box, etc), otherwise the solution will tend toward infinity (or a very high number). e.g. if the max weight for a box is unlimited then your optimal solution might just put all 10000 objects into the same box.
    – Ben Cottrell
    Feb 23, 2021 at 0:36
  • 4
    ... or the other extreme, take an arbitrary number of boxes and don't put any objects into them - all boxes have the same content weight - zero.
    – Doc Brown
    Feb 23, 2021 at 6:02

1 Answer 1

Reset to default
1

Let's start to answer the first part of the question:

  • There are n objects of weight w1, ..., wn. Their total weight is W=Σi=1..n wi

  • There are k boxes, each one with a weight limit L.

  • Your goal is to assign each object to one of the boxes, so the total weight of each box approximates M:=W/k. W/k should be ideally smaller than L, otherwise one can set M:=L.

  • An assignment (of the objects to boxes) is an k x n Matrix A containing values 0 or 1, where each column (object) contains one 1 in the row which corresponds to the box where the object is assigned to.

  • For a given assignment A, let

    WB(j,A) := Σi=1..n aj,i wi,

    which means WB(j,A) = "total weight of the objects in box number j". Then the maximum weight limit means the additional constraint WB(j,A)<=L for all j=1,...,k. Assignments will not necessarily be complete, which is especially obvious when L is smaller than M.

  • The objective function (of which a minimum shall be achieved), can be, for example, the sum of the squares from the deviation from M, like

    f(A) = Σi=1..k(WB(j,A)-M)²

    (respecting the former constraint, of course).

This is a Generalized Assignment Problem, where boxes correspond to "agents" and objects to "tasks". The "budget of an agent" is the maximum L of each box. With this problem name, you may be able to find further resources like algorithms using Google.

Improve this answer
0

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.