Целью решения задач по упаковке является поиск наилучшего способа упаковать набор предметов заданных размеров в контейнеры фиксированной вместимости . Типичным применением является эффективная погрузка коробок в грузовики. Часто невозможно упаковать все предметы из-за ограничений вместимости. В этом случае проблема состоит в том, чтобы найти подмножество предметов с максимальным общим размером, которое поместится в контейнеры.
Существует много типов проблем с упаковкой. Двумя наиболее важными являются проблемы с рюкзаком и упаковкой мусора .
Проблемы с рюкзаком
В простой задаче о рюкзаке имеется один контейнер (рюкзак). У предметов есть не только размеры , но и стоимость, и цель состоит в том, чтобы упаковать подмножество предметов, имеющее максимальную общую стоимость.
В особом случае, когда значение равно размеру, цель состоит в том, чтобы максимизировать общий размер упакованных предметов.
OR-Tools предоставляет несколько решателей задач о рюкзаке в своей библиотеке алгоритмов .
Существуют и более общие версии задачи о рюкзаке. Вот несколько примеров:
Многомерные задачи о рюкзаке , в которых предметы имеют более одной физической величины, такой как вес и объем, а рюкзак имеет вместимость для каждой величины. Здесь термин « размерность» не обязательно относится к обычным пространственным размерам высоты, длины и ширины. Однако некоторые проблемы могут быть связаны с пространственными размерами, например, поиск оптимального способа упаковки прямоугольных коробок в прямоугольное хранилище.
Задачи с несколькими рюкзаками , в которых имеется несколько рюкзаков, и цель состоит в том, чтобы максимизировать общую ценность упакованных предметов во всех рюкзаках.
Обратите внимание, что у вас может быть многомерная задача с одним рюкзаком или задача с несколькими рюкзаками только с одним измерением.
Проблема с упаковкой мусора
Одной из наиболее известных проблем с упаковкой является упаковка в контейнеры , при которых имеется несколько контейнеров (называемых контейнерами ) одинаковой вместимости. В отличие от задачи о нескольких рюкзаках, количество контейнеров не фиксировано. Вместо этого цель состоит в том, чтобы найти наименьшее количество контейнеров, в которых будут храниться все предметы.
Вот простой пример, иллюстрирующий разницу между задачей о нескольких рюкзаках и задачей об упаковке контейнеров. Предположим, у компании есть грузовики для доставки, каждый из которых имеет грузоподъемность 18 000 фунтов и 130 000 фунтов товаров для доставки.
Несколько рюкзаков: у вас есть пять грузовиков, и вы хотите загрузить в них часть предметов, имеющих максимальный вес.
Упаковка контейнеров: у вас есть 20 грузовиков (более чем достаточно, чтобы вместить все предметы), и вы хотите использовать наименьшее количество грузовиков, которые вместят их все.
В следующих разделах показано, как решать различные типы задач об упаковке с помощью OR-Tools, начиная с задачи о рюкзаке .