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