Целевая функция Bin Packing

Сначала я хочу уточнить, что английский не является моим родным языком, поэтому наберитесь терпения :)

Я пытаюсь решить проблему упаковки 3D-контейнера только с одним контейнером (рюкзаком), и у меня есть проблема с формулировкой целевой функции. У меня есть контейнер и список пакетов:

Контейнер:

  • Ширина
  • Глубина
  • Высота
  • Емкость
  • Трехмерная матрица

Упаковка:

  • Ширина
  • Глубина
  • Высота
  • Позиция (X,Y,Z)
  • Масса
  • Позиционный фактор

Каждый пакет будет иметь коэффициент положения, который говорит нам, в каком положении вы хотите загрузить пакет, коэффициент от 1 до 5, 1 означает, что пакет должен быть помещен в передней части контейнера, а 5 - в задней части контейнера. контейнер.

Теперь моя целевая функция состоит в том, чтобы максимизировать пространство в контейнере, и пакеты с большим коэффициентом должны быть в задней части контейнера, а пакеты с меньшим коэффициентом - в передней части грузовика.

Если я хочу максимизировать пространство, мне просто нужно максимизировать сумму всех объемов упаковки, но я должен комбинировать это со штрафом для целевой функции, когда, например, упаковка с коэффициентом 5 находится спереди. контейнера.

Хочу кое-что прояснить на примере пакетов одинакового размера, выстроенных в линию

  1. сзади 5 1 5 4 4 4 3 3 2 2 спереди
  2. сзади 5 5 4 4 4 3 3 2 1 2 спереди

В первом пакете раздачи вы видите, что пакет с коэффициентом 1 находится почти в задней части контейнера, а во втором пакете с коэффициентом 1 находится рядом с тем местом, где он должен быть (спереди), поэтому вторая раздача лучше.

Проблема в том, что пакеты имеют разный размер и могут располагаться в любом положении. Я надеюсь, что вы можете мне помочь :D!


algorithm knapsack-problem objective-function packing
person Gerardo Cardoso    schedule 17.04.2015    source источник

Ответы (1)


arrow_upward
0
arrow_downward

Конкретный вид целевой функции зависит от метода решения.

Поскольку проблема упаковки в контейнеры является NP-сложной задачей, я думаю, что вы будете использовать некоторые эвристики для ее решения. В этом случае решение-кандидат представляет собой набор всех пакетов (P) с заполненным атрибутом Position (X,Y,Z). И целевая функция выглядит так:

F({P}) -> int

Таким образом, вы можете добавить веса своему результату по фактору упаковки: лучший макет - это сортировка по факторам от 1 до 5, как я понимаю. Разница между ним и текущим макетом - это ваш коэффициент (используйте метод наименьших квадратов):

ideal:   back 5 5 4 4 4 3 3 2 2 1 front
current: back 5 1 5 4 4 4 3 3 2 2 front 
coefficient: (5-5)^2 + (5-1)^2 + ... + (1-2)^2
person Walking.In.The.Air    schedule 12.09.2015