Целевая функция упаковки бин

Question

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

Я пытаюсь решить проблему с упаковкой 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!

Answer 1

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

Поскольку проблема с упаковкой в ​​бункер является 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