18 Февраля 2021 17:28 18 Фев 2021 17:28 |

Поделиться

Оптимизируй это! Как объять необъятное с помощью солвера

Оптимизация. Истоки

Начиная с XIX века оптимизация в смысле поиска наилучшего решения на ограниченном множестве (или комбинаторная оптимизация) является предметом споров и областью для поиска универсального подхода. Еще в далеком 1832 г. один из аспектов оптимизации стал поводом выхода в свет книги, в которой пока еще не приводилось математического алгоритма для решения проблемы, но все нужные акценты уже были расставлены: «Коммивояжер — как он должен вести себя и что должен делать для того, чтобы доставлять товар и иметь успех в своих делах — советы старого курьера». Так возник интерес к одной из краеугольных задач оптимизации — задаче коммивояжера (или Traveling Salesman Problem, TSP), суть которой сводится к поиску самого короткого маршрута, проходящего через набор указанных городов так, что каждый город посещается ровно один раз.

Уникальность задачи TSP состоит в том, что, несмотря на простоту формулировки, ее точное решение даже при небольшом количестве городов чрезвычайно сложно, а иногда практически невозможно. Для просчета всех вариантов требуются недостижимые вычислительные мощности. Например, для маршрута всего с тридцатью городами число вариантов решения задачи превышает 10 в 32 степени, а для их полного перебора потребуется более 3 млн лет даже на самом мощном современном суперкомпьютере.

Другая известная задача — «задача о рюкзаке». Свое название она получила от конечной цели: уложить в рюкзак вещи максимальной суммарной ценности при условии, что вместимость рюкзака ограничена. Суть — из заданного множества предметов разного веса и разной ценности требуется отобрать подмножество с максимальной полной ценностью, соблюдая при этом ограничение на суммарный вес или объем.

Уникальность данной задачи в том, что для нее не существует алгоритма, гарантированно дающего оптимальное решение за разумное время. Поэтому необходимо выбирать между точными алгоритмами, которые не работают для «больших» емкостей, и приближенными, которые работают значительно быстрее, но не гарантируют оптимального решения задачи.

Обе эти задачи легли в основу современных методов и подходов к оптимизации и актуальны сегодня как для логистики, так и для экономики, для криптографии и других отраслей.

От человека к машине

На начальных этапах использования оптимизации в работе само решение принималось лишь на основе экспертного мнения ответственного специалиста. Позднее, с развитием цифровизации, появились технологии и инструменты, поддерживающие принятие решений: карты, графики, аналитика и другие. Однако последнее слово все равно оставалось за человеком. Сегодня же рынку доступны инструменты, способные полностью заменить эксперта на этапе поиска оптимального решения — «универсальные «решатели» задач», специализированные программно-аппаратные комплексы, или солверы (от англ. to solve — решать проблему, задачу). Эти системы помогают найти оптимальные варианты решения на основе методов математической оптимизации.

Механизм работы солверов не зависит от предметной области, для которой решается задача оптимизации. Они работают по единому логическому сценарию, используя матрицу вариативных данных и ограничений. На ее основе, исходя из актуального для заказчика критерия оптимизации, солверы направленно осуществляют поиск вариантов и производят расчет параметров модели, находя в итоге оптимальное решение задачи. Если данных и ограничивающих факторов для оптимизации очень много, и они разноплановые, то сделать подобную работу только лишь ручными вычислениями практически нереально.

«Многие компании, у которых не внедрены солверы, в решении своих задач по оптимизации намеренно отказываются от учета ряда показателей при ручном расчете по причине необходимости обработки колоссального объема данных — человек просто не способен учесть все корректно. Это не позволяет сделать такую оптимизацию эффективной. Но средства и усилия, потраченные на внедрение солвера, быстро окупаются за счет реализации открывающихся возможностей в направлении оптимизации», — поясняет Максим Храменков, руководитель направления оптимизации компании RAMAX Group.

Солверы делятся на узкоспециализированные (например, платформа Яндекс.Маршрутизация) — для решения логистических задач и построения точных маршрутов с учетом статистики пробок, и на промышленные, или универсальные (такие как Gurobi и IBM CPLEX), способные решать разноплановые оптимизационные задачи с большим количеством переменных и ограничений, используемых в анализе.

Солверы применяют как на регулярной основе, так и для решения разовых задач.

Подобные задачи решаются обычно в конце рабочего дня перед днем исполнения. По этой причине оптимизация и построение маршрутов с помощью солвера завершаются ночью, и, чтобы днем он также не оставался без работы, солвер на регулярной основе применяют, например, для оперативной оптимизации маршрутов в случае внепланового изменения условий (выход из строя транспортного средства, увеличения времени движения по ряду участков и т.д.).

В качестве разовой (выполняющейся раз в несколько месяцев или даже лет) можно указать, например, задачу планирования оптимальной локации нового распределительного центра еще до его запуска с целью обеспечения максимально экономически выгодной логистики по доставке товаров из этого центра на склады или в магазины.

Для решения подобных регулярных и разовых задач используются универсальные решения. Задачи, решаемые такими солверами, поражают своим разнообразием. Существует несколько десятков базовых типов прикладных задач (и многие сотни частных случаев), где применение солвера может принести значительную выгоду. Вот лишь некоторые примеры:

• построение оптимальных маршрутов транспортных средств (ТС);
• расчет оптимальной загрузки ТС для данной загрузки в контейнерных перевозках;
• составление графиков рабочих смен в супермаркетах в зависимости от периодов наплыва и оттока клиентов;
• оптимизация параметров инфраструктуры и порядка выполнения действий на производстве, например: порядка производства заказов на линиях с учетом технических ограничений линий, сроков и приоритетов заказа, расписаний изготовления и переналадки, наличия и сроков ожидания сырья;
• определение состава продукта из взаимозаменяемых компонентов сырья (классическая «задача раскройки», когда при определенном наборе рецептур и сырья необходимо максимизировать выгоду от производимых продуктов и порядка потребления сырья);
• поиск оптимального места хранения продуктов и материалов, например, в ритейле при распределении скоропортящихся продуктов. Пример актуален и для химической промышленности, где некоторые вещества необходимо даже изолировать друг от друга.

«Несколько подобных задач мы успешно решили с помощью солвера в своих проектах, — рассказывает Максим Храменков. — В крупном авиаперевозчике для построения расписания отпусков сотрудников и отдельно для формирования экипажей под конкретный рейс был использован IBM CPLEX. Российский почтовый оператор по итогам проекта с RAMAX осуществляет мультимодальные перевозки также с помощью этого солвера от компании IBM. После внедрения системы оптимизации затраты на перевозку почтовых грузов сократились более чем на 10% при соблюдении контрольных сроков доставки в 100% случаев! А еще один проект RAMAX с применением IBM CPLEX — в железнодорожной сфере — привел уже в первые месяцы к оптимизации управления вагонным парком оператора и повышению прибыли в размере около 9%».

Результаты, показанные конкретным солвером на проектах, натолкнули специалистов RAMAX Group на идею проведения независимого исследования и сравнения возможностей более широкого спектра этих решений от разных производителей между собой.

Исследование современных солверов

Объектами исследования стали три платформы для решения задач комбинаторной оптимизации в области логистики: Яндекс.Маршрутизация (Я.М), Gurobi и IBM CPLEX.

Для проведения сравнения была выбрана оптимизационная задача одного из проектов RAMAX Group в двух форматах: упрощенная модель и полная модель.

Задача рассчитывалась для конкретного заказчика из ритейла и состояла в том, чтобы провести планирование доставки из распределительных центров (РЦ) в магазины сроком от 1 до 4 дней в зависимости от географии РЦ таким образом, чтобы совокупная стоимость доставки была минимальна. Также требовалось учесть ряд критически важных факторов: правила разделения заказа по машинам для перевозки, параметры автомобилей (их грузовместимость и грузоподъемность, возможность подъезда к зданию РЦ и другие), наличие или отсутствие прицепа, тип экипажа (один или два водителя), требования к режиму труда и отдыха, необходимость заезда на стоянки и множество других факторов. Целью исследования стало выявление солвера, который найдет оптимальное, то есть наименее затратное, решение поставленной задачи при заданном ограничении на время расчета, равное одному часу.

Результаты расчетов по упрощенной модели показали, что универсальные солверы способны найти существенно более качественное решение (с меньшими затратами на доставку грузов), нежели Я.М. В то же время, более низкая эффективность Яндекс.Маршрутизации может быть компенсирована существенно меньшей стоимостью лицензий на его использование. Применение Я.М будет оправдано при ограниченном бюджете, если достаточно получить просто «хорошее», но не оптимальное решение.

Солвер Gurobi быстрее, чем IBM CPLEX, нашел оптимальное решение и показал более качественный результат по оптимизации с точки зрения суммарной стоимости и времени доставки (то есть нашел более экономичный вариант развозки грузов). Однако, как оказалось, у Gurobi «плавает» воспроизводимость, и результаты просчетов зачастую не совпадают при загрузке идентичных данных и повторных запусках.

Солвер IBM CPLEX показал себя сильнее Gurobi в части стабильности результата: при повторных запусках и загрузке изначальных данных результаты просчетов получались практически одинаковыми. Стабильность и воспроизводимость результатов для решения определенных задач может быть не менее важным требованием, нежели скорость вычислений или совокупные затраты, что само по себе может повлиять на выбор солвера.

«Если говорить о разнице между IBM CPLEX и Gurobi, то с первого взгляда она может быть неочевидна, — делится результатами исследования Максим Храменков. — Исследование показало, что они используют совершенно разные подходы к работе. У результатов этих солверов есть свои особенности, которые могут оказаться важными для той или иной предметной области. Поэтому при выборе между этими двумя решениями компания прежде всего должна четко понимать приоритеты в требованиях, предъявляемых к решению.

«Оптимизируй это!», или Вместо заключения

Исследованные RAMAX Group солверы применяет в своей работе огромное количество компаний, решая свои локальные в рамках отрасли и специфики деятельности оптимизационные задачи.

В логистике и транспорте рассчитывают маршруты доставки грузов, загрузку, расположение складов и распределительных центров. В нефтегазовой отрасли оптимизируют хранение запасов, проводят симуляцию сценариев обработки негативных событий в сети с поиском оптимального решения, управляют спросом на нефтепродукты при оптимальных затратах. В ритейле и FMCG (fast moving consumer goods — быстро оборачиваемые потребительские товары) планируют производственные мощности на заводах, занимаются формированием необходимого количества сотрудников в смену, маршрутов доставки товаров в магазины, планированием оптимальных территорий мерчандайзеров с учетом географии и объема работ.

При этом математическая оптимизация на базе солверов независимо от отраслевой специфики может эффективно сочетаться с другими технологиями, такими как искусственный интеллект и машинное обучение.

«В проекте с крупным российским ритейлером при решении логистической задачи оптимизации маршрутов мы использовали элементы машинного обучения, — рассказывает Максим Храменков. — Основная особенность такого подхода заключалась в том, что учет всех правил и ограничений требовал перебора огромного количества вариантов, а технологический процесс был жестко лимитирован по времени. На этом проекте мы использовали методы машинного обучения на исторических данных о маршрутах предыдущих дней (разумеется, рассчитанных солвером, а не логистом) для формирования начального решения для расчета оптимальных маршрутов текущего дня, что помогло значительно ускорить процесс дальнейшей оптимизации. Интеграция машинного обучения в работу солвера привела к тому, что он получил возможность учитывать свой опыт прошлых периодов расчетов и находить более качественные решения за допустимое расчетное время».

Таким образом, универсальный солвер на сегодняшний день — это венец технологической мысли в области оптимизации. Идея создания солверов имеет свою историю, их появление обусловлено ростом и разнообразием задач в области оптимизации, их выбор зависит от множества факторов, начиная с величины бюджета и заканчивая необходимой глубиной анализа и требований к результату. И, конечно, указанные примеры и результаты использования солверов, фигурирующие в материале, показывают, что внедрение подобных решений в технологические процессы компании будет максимально эффективным при участии профильных специалистов компании-интегратора с «живым» проектным опытом.

Post Scriptum

Экспертиза RAMAX Group позволяет не только браться за решение задач оптимизации для заказчиков из различных отраслей бизнеса, но и делиться накопленным опытом. Так, с 20 по 22 февраля 2021 г. пройдет первый онлайн-хакатон по оптимизации Ramaximization, где участникам предстоит решить задачи, подобные которым все чаще встречаются в практических проектах. В хакатоне примут участие команды со всего мира, соревнование позволит выявить лучших из них, а также подчеркнет актуальность использования технологий и методов оптимизации в современных реалиях. В жюри конкурса, помимо RAMAX Group, войдут технические и бизнес-эксперты из компании IBM и научно-исследовательской ИТ-лаборатории R-Labs.

Поделиться

Подписаться на новости Короткая ссылка