Логистический портал Cargotime.ru: классификация входных данных при решении задачи векторной упаковки
"Моя учебная практика посвящена работе над разделом калькулятора доставки логистического сервиса Cargotime.ru, который разрабатывается на базе лаборатории ТиМПИ СПб ФИЦ РАН.
Новый формат детализированного ввода грузовых параметров, реализованный в прошлом семестре, требует механизма эффективного распределения грузов по контейнерам. В прошлом семестре были реализованы и встроены в процесс расчета некоторые известные эвристические алгоритмы решения задачи, учитывающие вес и объем грузов. В рамках весеннего семестра работа над механизмом упаковки грузов была продолжена.
Сравнительный анализ эвристик показал, что эффективность их работы сильно зависит от параметров входного набора грузов. Эффективность эвристик была экспериментально оценена на тестовых классах, отличающихся числом уникальных грузов в наборе и размерами грузов в наборе.
Чтобы применить полученные данные об эффективности эвристик в расчете, был разработан метаэвристический алгоритм, основанный на разбиении набора грузов на кластеры и на минимизации линейной целевой функции, отвечающей за границы размеров грузов. Разработанный алгоритм классифицирует входной набор грузов и выбирает эвристику, которая работает эффективнее на данном классе. Применение метаэвристического алгоритма позволило снизить вычислительную нагрузку за счет запуска только одной эвристики вместо всех восьми.
В дальнейшем планируется использовать полученные данные об эффективности эвристик при решении задачи упаковки грузов в трехмерном пространстве."
Максим Сергеевич Есин