Добрый день. Нас зовут Илья Баштанов (разработчик, Точка-Точка) и Татьяна Воронова (аналитик данных, Центр 2М). И мы хотим рассказать о технической реализации задачи подбора грузов для перевозок.
Суть задачи в следующем. На складе есть грузы, которые нужно перевезти из города А в город Б. Можно считать, что учитывается только вес грузов, а их размеры более-менее стандартные (европаллеты). Перевозчик, желающий взять попутный груз, хочет перевезти как можно больше, но ограничен весом и количеством грузовых мест. Нужно сформировать для него несколько вариантов партий из имеющихся на складе грузов.
Решаемые задачи для бизнеса в данном случае:
Проект сразу показался привлекательным. Во-первых, с точки зрения математики: предлагалось реализовать алгоритм решения классической задачи комбинаторной оптимизации. Во-вторых, в качестве СУБД предложили PostgreSQL, популярность которого последние годы постоянно растет за счет большого количества возможностей, надежности и хороших характеристик по производительности. И, конечно, важность практической задачи и масштаб проекта, в котором задействовано множество различных участников, также стали большим стимулом.
Эта задача – вариант классической задачи об укладке рюкзака. Задача о рюкзаке – NP-полная. Такие задачи не решаются за полиномиальное время, хотя математически это до сих пор не доказано. Это означает, что точные алгоритмы, такие как полный перебор вариантов или его оптимизированные разновидности, на практике не работают, так как имеют сложность . Приближенные методы дают решения за лучшее время. Например, жадный алгоритм предполагает, что в рюкзак кладётся максимально тяжёлый груз до тех пор, пока это возможно. Его сложность не превосходит сложности сортировки , но результат может быть далек от оптимума. Есть ещё класс генетических алгоритмов, дающих хорошие результаты за ограниченное время, но они недетерминированные, что в нашем случае приводило бы к разным вариантам выдачи при повторных вызовах, это было бы трудно объяснить заказчику и перевозчикам. В итоге выбор пал на приближенные методы, дающие результат с гарантированной точностью за полиномиальное время.
Итак, у нас есть:
Требуется найти подмножество грузов с максимальным суммарным весом, удовлетворяющее ограничениям.
Идея состоит в том, чтобы уменьшить разнообразие грузов за счёт огрубления их весов и применить жадный алгоритм. В этом случае приближённое решение находится за полностью полиномиальное время, то есть решение с гарантированной точностью получается со сложностью, являющейся полиномом от и .
На входе алгоритма имеем табличку, содержащую округлённые веса грузов и количество мест для каждого веса. Пытаемся с помощью жадного алгоритма получить варианты укладки для суммарных весов . Для этого, установив целевой суммарный вес, в цикле отбираем из оставшихся грузов груз максимального веса так, чтобы не превысить целевой суммарный вес. Если достигнуто максимально допустимое количество , цикл завершается. Полученные комбинации сохраняем во временном массиве.
Количество возможных комбинаций может быть большим, а пользователю удобно выбирать из небольшого числа вариантов, но при этом выбор всё-таки должен быть. Появляется дополнительная задача выбора предпочтительных комбинаций. Чтобы не усложнять, решили всегда выдавать два варианта, если это возможно. Для склада желательно в первую очередь отправлять наиболее тяжелые грузы, поэтому комбинации ранжируем по убыванию наибольшего веса груза. Если комбинаций с максимальным наибольшим весом больше двух, выдаем две: с наибольшим и наименьшим количеством грузов.
Для тестирования мы выбрали две реализации рассмотренного алгоритма, отличающиеся незначительными деталями: одна – на Java, другая – на PL/pgSQL – процедурном языке СУБД PostgreSQL. Стоит сразу отметить, что на окончательный выбор повлияли не только результаты тестирования, но и архитектурные соображения, удобство использования и другие факторы. Но сначала стояла задача выбора одной из двух реализаций.
Использовались две среды тестирования: настольная для разработки теста и серверная для тестирования в условиях, похожих на реальные.
В БД PostgreSQL была подготовлена тестовая таблица, содержащая 7000 грузов со случайными весами от 20 до 800 кг. Для тестирования использовалась штатная утилита pgBench из поставки PostgreSQL, которая в процессе теста выполняла 500 транзакций (10 соединений по 50 транзакций). Каждая транзакция делала один вызов алгоритма со случайными параметрами (ограничением на вес от 10 до 1000 кг и на количество грузов от 1 до 50 штук). Все случайные величины распределены равномерно.
Для первого алгоритма каждая транзакция запускала Java-машину и передавала ей на выполнение архив JAR с кодом алгоритма. Основной класс Java соединялся с БД через JDBC-драйвер, получал тестовые данные из таблицы и применял к ним алгоритм.
Для второго алгоритма каждая транзакция выполняла вызов хранимой функции БД PostgreSQL, которая читала тестовые данные из таблицы и применяла алгоритм.
Таблица 1. Результаты основного теста
Кроме основного теста, результаты которого приведены в таблице 1, был проведен дополнительный тест алгоритма 2, в котором сравнивались разные варианты получения исходных данных: из БД, из файла, генерация случайного массива. Оказалось, что для 7000 грузов передача данных из СУБД в локальный массив требует большего времени, чем собственно работа алгоритма укладки.
Выводы.
В результате был выбран второй алгоритм, который с незначительными переделками эксплуатируется второй год. В итоге решение ищется с приемлемой точностью со средним временем транзакции менее 1 секунды.
Как всегда, жизнь внесла коррективы, и пришлось подправлять реализацию.
В реальности перевозчик резервирует партии грузов в условиях янки аукциона с плавающей ценой. Строго говоря, такой вариант продажи аукционом не является, но это уже тема отдельного разговора на другой площадке. Помимо максимального веса груза и максимального количества, перевозчик задает два города (начало и конец маршрута) и желаемое время загрузки. После этого процедура отбора для каждой пары складов (в городе отправки и городе назначения) отфильтровывает грузы по нескольким критериям, в частности, учитывая время работы склада и максимальную стоимость перевозки, при которой расходы еще покрываются оплатой отправителя, и передаёт их веса алгоритму укладки. На выходе алгоритма получается список весов, по ним подбираются наборы конкретных грузов, которые и выдаются как предложения аукциона.
Изначально веса округлялись в большую сторону до значений, кратных 10 кг. При эксплуатации стало ясно, что заметно страдает точность, и результаты начинают противоречить здравому смыслу, например, при наличии грузов весом 12 и 19 кг система может выбирать первый. Складские весы дают данные с точностью 1 кг, и для текущих объемов и нагрузки производительность алгоритма при целочисленных значениях весов оказалась вполне приемлемой, поэтому от округления пока отказались. В дальнейшем, при увеличении количества перевозок, планируется использовать округление до значений, кратных 5 кг.
Накладные расходы на работу алгоритма укладки при текущем объеме данных и интенсивности запросов не являются критичными. Заметно больше ресурсов требуется на этапе подбора грузов, а также для других процессов эксплуатации системы.
Миссия Точки-Точки – эффективный логистический процесс, в частности, оптимальное использование транспортного средства с точки зрения загруженности: при перевозке минимум пустот.
Глобальные цели решения оптимизационных задач в грузоперевозках: экономия ресурсов способствует экономическому росту, создаются дополнительные возможности для малого и среднего бизнеса, улучшается экология.
Специалистами Центр 2М и Точки-Точки было найдено программно-математическое решение, подходящее всем участникам процесса перевозки. Его можно применить для федеральной сети, в каждой точке которой 7 тысяч паллет (соответствует размеру футбольного поля) при запросе 500 перевозчиков и с получением результата менее, чем за 1 секунду.
Авторы статьи: Илья Баштанов (i-bash), Татьяна Воронова (tvoronova)
Суть задачи в следующем. На складе есть грузы, которые нужно перевезти из города А в город Б. Можно считать, что учитывается только вес грузов, а их размеры более-менее стандартные (европаллеты). Перевозчик, желающий взять попутный груз, хочет перевезти как можно больше, но ограничен весом и количеством грузовых мест. Нужно сформировать для него несколько вариантов партий из имеющихся на складе грузов.
Решаемые задачи для бизнеса в данном случае:
- Максимально эффективно загружать транспортные средства и тем самым увеличить доход от перевозок.
- Решать задачу доставки в приемлемые сроки для пользователя (включая принцип FIFO).
Проект сразу показался привлекательным. Во-первых, с точки зрения математики: предлагалось реализовать алгоритм решения классической задачи комбинаторной оптимизации. Во-вторых, в качестве СУБД предложили PostgreSQL, популярность которого последние годы постоянно растет за счет большого количества возможностей, надежности и хороших характеристик по производительности. И, конечно, важность практической задачи и масштаб проекта, в котором задействовано множество различных участников, также стали большим стимулом.
Алгоритм
Эта задача – вариант классической задачи об укладке рюкзака. Задача о рюкзаке – NP-полная. Такие задачи не решаются за полиномиальное время, хотя математически это до сих пор не доказано. Это означает, что точные алгоритмы, такие как полный перебор вариантов или его оптимизированные разновидности, на практике не работают, так как имеют сложность . Приближенные методы дают решения за лучшее время. Например, жадный алгоритм предполагает, что в рюкзак кладётся максимально тяжёлый груз до тех пор, пока это возможно. Его сложность не превосходит сложности сортировки , но результат может быть далек от оптимума. Есть ещё класс генетических алгоритмов, дающих хорошие результаты за ограниченное время, но они недетерминированные, что в нашем случае приводило бы к разным вариантам выдачи при повторных вызовах, это было бы трудно объяснить заказчику и перевозчикам. В итоге выбор пал на приближенные методы, дающие результат с гарантированной точностью за полиномиальное время.
Итак, у нас есть:
- Грузы с весами
- Ограничение на суммарный вес грузов
- Ограничение на количество грузов
Требуется найти подмножество грузов с максимальным суммарным весом, удовлетворяющее ограничениям.
Идея состоит в том, чтобы уменьшить разнообразие грузов за счёт огрубления их весов и применить жадный алгоритм. В этом случае приближённое решение находится за полностью полиномиальное время, то есть решение с гарантированной точностью получается со сложностью, являющейся полиномом от и .
На входе алгоритма имеем табличку, содержащую округлённые веса грузов и количество мест для каждого веса. Пытаемся с помощью жадного алгоритма получить варианты укладки для суммарных весов . Для этого, установив целевой суммарный вес, в цикле отбираем из оставшихся грузов груз максимального веса так, чтобы не превысить целевой суммарный вес. Если достигнуто максимально допустимое количество , цикл завершается. Полученные комбинации сохраняем во временном массиве.
Количество возможных комбинаций может быть большим, а пользователю удобно выбирать из небольшого числа вариантов, но при этом выбор всё-таки должен быть. Появляется дополнительная задача выбора предпочтительных комбинаций. Чтобы не усложнять, решили всегда выдавать два варианта, если это возможно. Для склада желательно в первую очередь отправлять наиболее тяжелые грузы, поэтому комбинации ранжируем по убыванию наибольшего веса груза. Если комбинаций с максимальным наибольшим весом больше двух, выдаем две: с наибольшим и наименьшим количеством грузов.
Тесты
Для тестирования мы выбрали две реализации рассмотренного алгоритма, отличающиеся незначительными деталями: одна – на Java, другая – на PL/pgSQL – процедурном языке СУБД PostgreSQL. Стоит сразу отметить, что на окончательный выбор повлияли не только результаты тестирования, но и архитектурные соображения, удобство использования и другие факторы. Но сначала стояла задача выбора одной из двух реализаций.
Использовались две среды тестирования: настольная для разработки теста и серверная для тестирования в условиях, похожих на реальные.
- dev: клиентская станция HP Probook 4740s + сервер 32-bit 2 x Pentium® Dual-Core CPU E5300 @ 2.60GHz и 4 ГБ оперативной памяти, Ubuntu Linux 16.04, PostgreSQL 10.3.
- test: сервер 64-bit с 2 x Intel Xeon CPU E5-2673 v4 @ 2.30GHz и 14 ГБ оперативной памяти, CentOS Linux 7.4, PostgreSQL 10.3
В БД PostgreSQL была подготовлена тестовая таблица, содержащая 7000 грузов со случайными весами от 20 до 800 кг. Для тестирования использовалась штатная утилита pgBench из поставки PostgreSQL, которая в процессе теста выполняла 500 транзакций (10 соединений по 50 транзакций). Каждая транзакция делала один вызов алгоритма со случайными параметрами (ограничением на вес от 10 до 1000 кг и на количество грузов от 1 до 50 штук). Все случайные величины распределены равномерно.
Для первого алгоритма каждая транзакция запускала Java-машину и передавала ей на выполнение архив JAR с кодом алгоритма. Основной класс Java соединялся с БД через JDBC-драйвер, получал тестовые данные из таблицы и применял к ним алгоритм.
Для второго алгоритма каждая транзакция выполняла вызов хранимой функции БД PostgreSQL, которая читала тестовые данные из таблицы и применяла алгоритм.
Таблица 1. Результаты основного теста
Кроме основного теста, результаты которого приведены в таблице 1, был проведен дополнительный тест алгоритма 2, в котором сравнивались разные варианты получения исходных данных: из БД, из файла, генерация случайного массива. Оказалось, что для 7000 грузов передача данных из СУБД в локальный массив требует большего времени, чем собственно работа алгоритма укладки.
Выводы.
- В нашей задаче производительность в большей степени зависела от архитектуры системы и скорости взаимодействия с БД, чем от применяемого алгоритма. Это подтверждается дополнительным тестом алгоритма 1, в котором выборка данных из БД заняла основную часть времени.
- Вариант 2 масштабируется немного лучше, видимо, за счёт более скромных требований к оперативной памяти (для хранения промежуточных результатов используются временные таблицы БД).
В результате был выбран второй алгоритм, который с незначительными переделками эксплуатируется второй год. В итоге решение ищется с приемлемой точностью со средним временем транзакции менее 1 секунды.
Эксплуатация
Как всегда, жизнь внесла коррективы, и пришлось подправлять реализацию.
В реальности перевозчик резервирует партии грузов в условиях янки аукциона с плавающей ценой. Строго говоря, такой вариант продажи аукционом не является, но это уже тема отдельного разговора на другой площадке. Помимо максимального веса груза и максимального количества, перевозчик задает два города (начало и конец маршрута) и желаемое время загрузки. После этого процедура отбора для каждой пары складов (в городе отправки и городе назначения) отфильтровывает грузы по нескольким критериям, в частности, учитывая время работы склада и максимальную стоимость перевозки, при которой расходы еще покрываются оплатой отправителя, и передаёт их веса алгоритму укладки. На выходе алгоритма получается список весов, по ним подбираются наборы конкретных грузов, которые и выдаются как предложения аукциона.
Изначально веса округлялись в большую сторону до значений, кратных 10 кг. При эксплуатации стало ясно, что заметно страдает точность, и результаты начинают противоречить здравому смыслу, например, при наличии грузов весом 12 и 19 кг система может выбирать первый. Складские весы дают данные с точностью 1 кг, и для текущих объемов и нагрузки производительность алгоритма при целочисленных значениях весов оказалась вполне приемлемой, поэтому от округления пока отказались. В дальнейшем, при увеличении количества перевозок, планируется использовать округление до значений, кратных 5 кг.
Накладные расходы на работу алгоритма укладки при текущем объеме данных и интенсивности запросов не являются критичными. Заметно больше ресурсов требуется на этапе подбора грузов, а также для других процессов эксплуатации системы.
Выводы бизнеса
Миссия Точки-Точки – эффективный логистический процесс, в частности, оптимальное использование транспортного средства с точки зрения загруженности: при перевозке минимум пустот.
Глобальные цели решения оптимизационных задач в грузоперевозках: экономия ресурсов способствует экономическому росту, создаются дополнительные возможности для малого и среднего бизнеса, улучшается экология.
Специалистами Центр 2М и Точки-Точки было найдено программно-математическое решение, подходящее всем участникам процесса перевозки. Его можно применить для федеральной сети, в каждой точке которой 7 тысяч паллет (соответствует размеру футбольного поля) при запросе 500 перевозчиков и с получением результата менее, чем за 1 секунду.
Авторы статьи: Илья Баштанов (i-bash), Татьяна Воронова (tvoronova)
agershun
Если не ошибаюсь, с помощью Лагранжевской релаксации рюкзак с 7000 предметами должен неплохо раскладываться за меньшее время и точно, а не приближенно.
В замечательном курсе на Курсере по Дискретной оптимизации (https://www.coursera.org/learn/discrete-optimization) на второй неделе подробно рассказывается, как это делается.
Если хотите, могу в личку прислать код.
crustal
Здесь вроде как фишка не в том, чтобы формально решить математическую задачу, а в том, чтобы хоть как-то формализовать факторы существенные для «всех участников процесса перевозки». То что они пишут «Эта задача – вариант классической задачи об укладке рюкзака.» — на мой взгляд — немного надуть щеки для важности, к действительности имеет мало отношения, но, на мой взгляд это может быть оправдано в существующих реалиях, — таковы правила игрыв этом, и не только этом секторе бизнеса.
Пытаюсь вот так с ходу сразу хотя бы перечислить упомянутые факторы, даже и не пытаюсь их как-то упорядочить по значимости, — нифига сходу не получается. Как я понимаю, никто особо и не парится с «загрузкой под завязку», Кто-то предпочтет быстро уйти половинной нагрузкой, доставить быстро и не «отдыхать» суботу и воскресенье в ожидании разгрузки черт знает где, черт знает в каких условиях с риском нарваться на неприятности. Какой-то груз в принципе нельзя доставить, если машина загружена по максимуму — ограничения по весу на дорогах из-за ремонта дорог или чего-то еще. Где-то штрафные санкции за доставку груза не точно в срок могут сильно превышать всю экономиию. Всего не перечислить, а если и перечислить, то к действительности эти фантазии могут не иметь отношения.
То, что им удалось выработать какое-то компромисное решение, хоть как-то работающее в реальности, — ну респект им, что тут еще скажешь.