ПРОСТОЙ АЛГОРИТМ ПЛОТНОЙ УПАКОВКИ НЕСКОЛЬКИХ ВИДОВ СТАНДАРТНОГО ГРУЗА В ГРУППУ ВАГОНОВ

Катаева Лилия Юрьевна

Одним из приоритетных направлений является автоматизация и оптимизация процесса погрузки вагонов. В данной статье описывается алгоритм ортогональной плотной упаковки нескольких типов стандартных грузов в группу вагонов и приводятся примеры моделирования на основе этого алгоритма. Алгоритм основан на сочетании метода динамического программирования с мемоизацией. Для повышения эффективности алгоритма вводится критерий оценки каждого вида груза на предмет удобства его упаковки в вагон. Целевая функция в этом случае учитывает частичную загрузку последнего контейнера. Предполагается, что у нас есть много грузов каждого вида. Исследуются эвристики алгоритма упаковки для различных наборов входных данных. Установлено, что классические эвристики более эффективны для случая упаковки большого количества разнородных грузов, однако эффективность алгоритма динамического программирования с мемоизацией при объединении эвристик для фактора неудобства погрузки конкретных видов грузов возрастает при наличии большого количества нескольких видов грузов. Результаты показывают, что использование такой комбинации алгоритмов приводит к минимизации количества автомобилей, необходимых для перевозки грузов.

Ключевые слова:упаковка груза, группа вагонов, оптимизация, динамическое программирование