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

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

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

Материал будет полезен как заядлым специалистам по мат.оптимизации, так и ml-инженерам или data scientist’ам. Рассматриваемая задача может быть интересна специалистам из области логистики/транспортных перевозок.

RL в комбинаторной оптимизации

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

В рамках CO методы RL используются двумя основными путями:

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

Интеграция RL с другими методами оптимизации.

Комбинаторные задачи часто имеют огромное пространство решений, что затрудняет поиск оптимального варианта. Интеграция обучения с подкреплением (RL) с традиционными методами оптимизации позволяет использовать сильные стороны каждого подхода: RL даёт адаптивность и способность обучаться на опыте, а классические алгоритмы — гарантированную сходимость и эффективные эвристики.

Основные стратегии интеграции:

• RL как генератор начальных решений.RL-агент обучается генерировать «хорошие» начальные решения, которые затем уточняются с помощью точных методов (например, метода ветвей и границ или линейного программирования). Это сокращает время поиска глобального оптимума. Пример, в задаче коммивояжёра (TSP) RL может быстро построить маршрут, близкий к оптимальному, который затем дорабатывается локальным поиском или 2‑opt алгоритмом.
• Гибридные алгоритмы с локальным поиском.RL выбирает направление улучшения (например, какие рёбра заменить в маршруте), а локальные эвристики (2‑opt, 3‑opt) выполняют конкретные изменения. Агент учится, какие операции наиболее перспективны в текущем состоянии. Преимущества: снижение вычислительной сложности и ускорение сходимости за счёт фокусировки на перспективных областях.
• RL для настройки параметров метаэвристик.Метаэвристики (генетический алгоритм, имитация отжига, муравьиные алгоритмы) имеют множество параметров (вероятности мутации, температура охлаждения и т.д.). RL-агент может динамически адаптировать эти параметры в процессе решения. Например, в генетическом алгоритме RL управляет вероятностью кроссовера и мутации на основе прогресса популяции.
• Иерархическое RL для декомпозиции задач.Сложная задача разбивается на подзадачи, каждая из которых решается отдельным RL‑агентом или классическим алгоритмом: на верхнем уровне RL-агент определяет стратегию (например, кластеризует города в TSP); на нижнем уровне точные методы оптимизируют маршруты внутри каждого кластера.
• RL в рамках метода ветвей и границ.В методе ветвей и границ RL может выбирать, какую ветвь дерева решений исследовать следующей, оценивать перспективность узла (вместо эвристических функций) или сокращать пространство поиска за счёт предсказания границ.

Neural Combinatorial Optimization (NCO)

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

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

• Задача коммивояжёра (TSP).Найти кратчайший маршрут, проходящий через заданный набор городов ровно один раз и возвращающийся в исходный пункт. NCO используют Pointer Networks или GNN для генерации перестановок городов. По сути, задача сводится к сортировке. ПримерNCO(решение задачи с применением cp-sat солвера разбиралздесьи ).
• Задача маршрутизации транспортных средств (VRP).Оптимизация маршрутов для парка транспортных средств с учётом ограничений по вместимости (CVRP), по временным окнам (VRPTW) и т.д. ПримерNCO.
• Задача о рюкзаке (Knapsack Problem).Выбор предметов с максимальной суммарной ценностью при ограничении на вес/объём рюкзака. Пример длямногомерной задачи о рюкзаке.
• Задача покрытия множества (Set Cover).Выбор минимального набора множеств, покрывающих все элементы.
• Планирование работы цеха (Job‑Shop Scheduling).Распределение операций между станками с минимизацией времени выполнения всех заказов. Пример одна из свежихнаучных работ.
• Раскраска графа.Минимизация количества цветов так, чтобы смежные вершины имели разные цвета (применяется в составлении расписаний, распределении частот). Одно из ключевыхисследованийпо задаче.
• Задача размещения объектов (Facility Location).Оптимальное размещение складов, станций зарядки, вышек связи с учётом спроса и затрат на обслуживание. Вариацию решения задачи рассматривал встатье(Mixed Integer Programming).
• Оптимизация цепочек поставок.Планирование закупок, производства, хранения и доставки с учётом неопределённостей.
• Задача назначения (Assignment Problem).Оптимальное сопоставление агентов и задач (например, такси и пассажиров) с минимизацией суммарных затрат. Вариацию постановки задачи рассматривал встатье.
• SAT‑задача (выполнимость булевых формул).Определение, существует ли набор значений переменных, удовлетворяющий заданной формуле. Пример:NeuroSAT.

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

Отойдем от классических стандартизированных задач и попробуем решить небольшую вполне практическую комбинаторную задачу полностью силами RL (from scratch).

Бизнес задача

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

Стратегическое планирование заправок в пути — эффективный способ снизить топливные затраты. Разброс цен на АЗС (обусловленный различиями в операторах, корпоративных контрактах и региональной ценовой политике) даёт возможность выбирать наиболее экономичные точки заправки. Особенно это актуально для дальних маршрутов, где число доступных АЗС может превышать сотню.

Процесс заправки транспортных средств зачастую не получает должного управленческого контроля и делегируется непосредственно водителям, которые самостоятельно определяют объём заправки и выбирают АЗС. Поскольку водители не всегда заинтересованы в минимизации топливных затрат, их выбор может определяться личными предпочтениями (комфортом, привычными маршрутами и т. д.). Это создаёт потенциал для оптимизации: грамотное планирование точек заправки и объёмов топлива способно обеспечить экономию до 1–1,5 %.

Задача состоит в определении оптимальных точек заправки (АЗС) на маршруте и соответствующих объёмов топлива с соблюдением следующих ограничений:

• Минимальный остаток топлива.На любом участке маршрута остаток в баке должен быть не ниже минимально допустимого уровня.
• Вместимость бака.Объём топлива в баке не может превышать его максимальную вместимость.
• Финальный остаток.В конце маршрута в баке должно оставаться не менее порогового количества топлива.
• Минимальный объём заправки.Заезд на АЗС должен быть экономически оправдан: объём заправки не может быть ниже установленного минимума (исключаются случаи дозаправки незначительных объёмов, например, 1 л).

Задача нелинейного программирования

Сформулируем задачу оптимизации выбора АЗС и объёмов заправки в терминах нелинейного программирования. Но, для начала скорректируем ограничения задачи под RL. Ограничение коснется объема заправки. Предлагаю рассмотреть пять вариантов заправки: 0%, 25%, 50%, 75% и 100% от пустого места в баке. Это позволит перейти от непрерывного пространства к дискретному пространству решений. Управление таким решением в RL проще, на исследовательской составляющей материала сильных искажений результата не предвидится.

- индексы АЗС

Постоянные

- объем потребления сдоАЗС

- стоимость заправки наАЗС

- минимальный объем заправки на АЗС

- объем топлива в баке в начале и конце маршрута

- минимальный и максимальный объем топлива в баке

- размер штрафа за нарушение минимального остатка в баке

Переменные

- вещественная переменная, объем топлива в баке на-ой АЗС после заправки на этой АЗС

- вещественная переменная, объем заправки на-ой АЗС

- целочисленная переменная, процент заправки на-ой АЗС

- бинарная переменная, индикатор наличия заправки на-ой АЗС

- вещественная переменная, размер нарушения минимального остатка в баке

Целевая функция

Минимизация стоимости заправок и нарушений минимального остатка:

Ограничения

• Баланс топлива в баке:
• Кратность заправки доли от пустого места в баке:
• Минимальный остаток в баке:
• Остаток в конце маршрута:
• Минимальная заправка:
• Индикатор заправки:

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

Реализацию оптимизационной модели нелинейного программирования с использованием солвера SCIP (pyscipopt) закинул наgit.

Reinforcement learning для решения задачи

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

Ключевые компоненты:

• среда— мир, в котором действует агент;
• агент— обучающаяся сущность, принимающая решения;
• состояние (s)— текущая ситуация в среде;
• действие (a)— шаг, который агент может выполнить;
• награда ( r )— сигнал от среды, оценивающий действие (положительный или отрицательный).

Агент стремится максимизировать суммарную награду, постепенно улучшая стратегию выбора действий. Портал в более глубокое погружение -здесь!

Перейдем к практическим аспектам реализации агента, способного решать задачу планирования заправок ТС.

Environment

Агент взаимодействует со средой (Environment) через петлю обратной связи: наблюдает состояние → выбирает действие → получает награду и новое состояние. Среда - вероятно, самое важное в RL, поэтому начинаем именно с нее.

Для типовых задач есть готовые «песочницы» — среды с понятными правилами:

• начать путь в RL помогут Gymnasium и Stable Baselines3;
• для многоагентных игр:PettingZoo и SMAC;
• для роботов и физики: PyBullet, MuJoCo, DeepMind Control Suite;
• для навигации и беспилотников: Habitat и CARLA;
• масштабирование и распределённое обучение: Ray RLlib;
• поиграть и потренировать стратегию можно в ViZDoom, NetHack или Google Football.

Мы рассматриваем нестандартную задачу RL. Готовой средой невоспользоваться. Более того, как эффективно организовать эту среду - отдельная задача. Ниже презентую свой вариант реализации.

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

Предлагаю этот вектор использовать в качестве вектора состояния. Поработаем над его недостатками:

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

Решение:увеличиваем размер части потребления и части с ценами до фиксированного размера. Отсутствующие значения заполняем нулями. Например, пусть это будет 100, тогда размерность вектора состояния будет 100+100+5=205.

• Масштаб значений. АЗС вдоль маршрута могут распологаться достаточно плотно (например, для маршрутов центральной части РФ) или быть сильно удалены (Забайкальский край или дальний восток). Это влияет на порядок значений в потреблении. Кроме того, максимальный, минимальный, текущий, конечный остаток и минимальная заправка могут разниться в зависимости от характеристик ТС. Значения такого вектора могут излишьне забирать внимание агента.

Решение:нормировать значения потребления и ограничений задачи поделив на максимальный остаток (все значения лягут в интервал от 0 до 1). Цены предлагаю преобразовать в относительную разность к минимальной цене.

После предложенных модификаций исходный вектор состояния преобразуется в это:

Разберем динамику взаимодействия. Сбросили среду (reset), получили вектор состояния полной оптимизационной задачи (например, как на предыдущей картинке). Агент на основе вектора состояния выбирает одно из пяти возможных дейсткий: закупить топлива на 0%, 25%, 50%, 75% и 100% от пустого места в баке. Совершаем действие и формируем новый вектор состояния: корректируем вектор потребления, вектор цен (слева убираем значение, справа дописываем 0) и значение остатка в баке (+ объем закупки - объем потребления). Эпизод заканчивается когда совершили действие на каждой АЗС маршрута.

Исходя из вектора состояния агент всегда видит:

• сколько топлива в настоящий момент в баке;
• сколько топлива еще потребится;
• когда и по какой цене можно закупить топливо;
• сколько топлива должно остаться в конце маршрута.

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

Награда (reward).Каждое действие агента оценивается средой. Основная составляющая награды - стоимость заправки. Этот показатель можно оценивать на каждом шаге взаимодействия со средой. Кроме затрат на топливо, есть ограничения на минимальный объем топлива в баке и остаток топлива в конце маршрута. Эти ограничения в исходной постановке - жесткие, но в процессе обучения дадим послабление и сделаем их мягкими. Т.е. нарушение этих ограничений будем штрафовать. Остаток в конце маршрута возможно оценить в конце эпизода.

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

Итог:создана специализированная RL‑среда для оптимизации заправок на маршруте. Она предоставляет агенту структурированную информацию, чёткие правила взаимодействия и осмысленную функцию награды. Это позволяет обучать политику, минимизирующую затраты на топливо с учётом всех ограничений задачи.

В обучении с подкреплением агент принимает решения на основе оценки качества возможных действий в текущем состоянии среды. Ключевым инструментом такой оценки выступает Q‑функция, которая прогнозирует суммарную будущую награду при выполнении действияв состоянии.

Когда для аппроксимации Q‑функции применяется нейронная сеть, соответствующий подход называют Deep Q‑Network (DQN). Обучение DQN происходит через последовательное взаимодействие агента со средой, на каждом шаге агент:

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

Такой цикл позволяет агенту постепенно улучшать стратегию выбора действий и максимизировать накопленную награду.

Dueling Deep Q‑Network (Dueling DQN)— модификация алгоритма DQN, предложенная в 2016 году. Её ключевая идея — разделение нейронной сети на две независимые части для более точной оценки Q‑функции. Это позволяет эффективнее обучаться в средах с большим числом действий и улучшает обобщающую способность агента.

Отличия от классического DQN

В DQN одна нейронная сеть напрямую аппроксимирует функцию, то есть оценивает суммарную будущую награду для каждой пары «состояние‑действие».

В Dueling DQN Q‑функция разбивается на два компонента:

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

Параметры— общие,и— параметры отдельных полносвязных слоёв.

Архитектура сети

Типичная архитектура Dueling DQN состоит из трёх частей:

1. Общая часть (бэкбон):

• обрабатывает входные данные;
• извлекает признаки.

1. Ветвь ценности состояния:

• один полносвязный слой;
• выход — одно число, оценивающее состояние.

1. Ветвь преимущества действий:

• один полносвязный слой;
• выход — вектор размером(число действий), где каждый элемент — преимущество соответствующего действия.

На финальном слое происходит объединение:

Вычитание среднего преимущества необходимо для устранения неоднозначности:ине определяются однозначно, а их сумма — да. Альтернатива — вычесть максимум преимуществ.

Ключевые улучшения по сравнению с DQN

• Более точная оценка состояний.Разделение позволяет агенту лучше понять, какие состояния принципиально выгодны или невыгодны, даже если конкретные действия пока не изучены.
• Ускорение обучения.Информация о ценности состояния распространяется на все действия, что ускоряет обобщение.
• Эффективность в средах с множеством действий.Когда большинство действий мало влияют на ценность состояния, преимуществобудет близко к нулю, а обучение сфокусируется на.
• Стабильность.Раздельная оценка снижает шум в градиентах и делает обучение более устойчивым.

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

Схема обучения

Среди разнообразных схем обучения DQN‑агентов был выбран подход Double DQN.

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

Принцип работы Double DQN

Double DQN использует две нейронные сети:

• Основная сеть (online network)— используется для выбора действия в следующем состоянии. То есть с её помощью определяется, какое действие является наилучшим в новом состоянии.
• Целевая сеть (target network)— используется для оценки Q-значения выбранного действия. То есть она вычисляет целевое Q-значение для обновления параметров основной сети.

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

Математически это можно записать так:

• — текущее состояние;
• — текущее действие;
• — полученная награда;
• — коэффициент дисконтирования;
• — основная сеть;
• — целевая сеть (target).

Как работает обучение

1. Инициализация сетей. Создаются две нейронные сети: основнаяи целевая. Изначально параметры целевой сети копируются из основной ();
2. Пронаблюдатьиз среды;
3. Для каждого:

• с вероятностьювыбрать действиеслучайно (exploration), иначе жадно:;
• отправить действиев среду, получить награду за шаги следующее состояние;
• добавление переходав буфер (replay buffer);
• если в буфере скопилось достаточное число переходов, провести шаг обучения. Для этого сэмплируем мини-батч переходовиз буфера.
• для каждого перехода считаем целевую переменную:;
• сделать шаг градиентного спуска для обновления, минимизируя;
• если пришло время (кратно- шаг синхронизации весов), тогда.

Нюансы обучения

Реплей‑буфер, хранящий переходы, имеет ограниченный объём для предотвращения избыточного потребления памяти. При достижении установленного лимита старые записи удаляются по принципу FIFO.

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

Для ускорения обучения внедрён подходcurriculum learningс привлечением экспертных решений. С заданной вероятностью выбор действия осуществляется на основе оптимального решения, рассчитанного заранее с помощью оптимизационной модели. Такой подход позволяет наполнять буфер высококачественными переходами, что способствует более быстрой сходимости алгоритма. Триггер активации экспертной стратегии срабатывает в начале маршрута: после его срабатывания весь эпизод разыгрывается с использованием оптимального решения.

Реализацию процесса обучения можно посмотретьздесь.

Что получилось

Всю описанную выше систему нужно напитать данными. Была возможность взять данные работающей оптимизационной модели. Но эти данные оказались не очень подходящими для обучения.

1. Не настроен сбор данных. Требуется собирать результаты из архивов.
2. Дублирование записей. Для одного рейса фиксируется несколько записей на разных этапах маршрута (например, отдельные запросы для первой и третьей АЗС одного маршрута).
3. Короткая история хранения данных. Ограниченный временной охват доступных данных.

Поэтому для обучения использовал искусственные данные. Генератор представленздесь. Случайные распределения настроены под разброс из реальных данных.

Распределение усредненной за последние 100 шагов награды в эпизодах в зависимости от шага обучения представлено ниже. Левый график соответствуют обучению полносвязной линейной нейронной сети, а правый - одномерной сверточной сети. Отличий практически нет, в обоих случаях обучение быстро сходится к средней награде -7 единиц.

Улучшения не удалось получить ни при увеличении исследовательских циклов, ни при добавлении эксперта, ни при ребалансировке весов в reward. Поведение повторяется и улучшений не происходит. Значит ли это, что обучили вполне качественного агента? Об этом в следующем разделе.

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

Обучены несколько вариантов Q-функций + рассмотрены различные подходу к обучению:

• Linear: полносвязная нейронная сеть с линейными слоями;
• Conv1d: одномерная сверточная сеть;
• Overload: корректировка среды. В конце маршрута есть требование минимального конечного остатка. В исходном варианте среды установлено штраф за нарушение ограничения снизу. Эта модификация штрафует остаток в конце маршрут в том числе сверху.
• Explore: увеличенный размер цикла исследования в процессе обучения.
• Expert: в процессе обучения некоторые действия формируются экспертом (оптимизационной моделью).
• Opt: решение задачи с помощью математического программирования.

Сравнения будем проводить по суммарным значениям 86 сценариям. Напомню, что задача заключается в минимизации затрат на заправку топлива. Этот параметр будем исследовать.

Исходя из графиков видим, что RL тратит и заправляет больше. Это обусловлено тем, что rl агенты не мотивированы в конце маршрута оставлять остаток близкий к требуемому остатку в конце маршрута (кроме overload). На протяжении маршрута объем заправок не очень оптимальный с точки зрения полного маршрута. Исключение Overload, который оказался достаточно близок к оптимальному решению.

Разброс по затратам от оптимального решения 8-54%. Если брать во внимание только эти показатели, то есть куда расти. Посмотрим на среднюю стоимость закупок.

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

Такой эффект с моделью Opt возник из-за корректировки условия задачи: кратность заправки от пустого места в баке. Если рассматривать непрерывную область решений для объема заправки, то таких проблем у оптимизационной модели не должно возникнуть.

Этот момент выходит за рамки задачи, мы останемся в рамках задачи.

Нарушение минимального остатка в баке - еще один важный показатель. Посмотрим что у нас с нарушением этого параметра.

Среди 86 сценариев был один с несовсем консистентными условиями, поэтому минимальное значение: нарушений минимального остатка 57л. В силу большого штрафа за нарушение минимального остатка, rl модели научились достаточно хорошо следовать этому правилу. В модели Overload возможно требуется более качественная настройка весов между штрафами.

Нарушение остатка в конце маршрута незначительные, не более 10л. Этот показатель не будет удостоен своего графика.

Последнее, на что хочу обратить внимание - производительность. Для решения оптимизационной задачи использовался коммерческий солвер.

Суммарная длительность расчетов (inference) у rl моделей ниже, чем у солвера. Но это не такое большое преимущество, учитывая порядок и нефункциональные требования к решению. Если учесть время обучения модели (около 1ч), то ситуация кардинально меняется в пользу Opt.

Послесловие

Что касается RL у меня академические познания. Постарался учесть “хорошие” практики организации среды, распределения награды и организовать хороший процесс обучения. Но этого оказалось недостаточно. В планах попробовать:

• Распределение награды после завершения эпизода. Это должно уменьшить объем закупок топлива;
• Рассмотреть непрерывную область решений по объему заправок. Это приблизит к реальной задаче;
• Усложнить структуру нейронной сети для Q-функции;
• Скорректировать среду. Изменение нормировок и системы штрафов. Это позволит точнее формировать цель для агента.

Что касается RL как инструмента для решения комбинаторных задач. Вместо постановки задачи в виде правил и ограничений в RL дополнительно возникают работы по:

• Разработке среды и системы наград. Как в оптимизационной задаче напрямую передавать данные задачи уже не получится. Много зависит от представления данных и размера награды.
• Данные. Требуются большие объемы разных данных/ситуаций для качественного обучения (проблема обобщения). В оптимизационных задачах эти данные в очень скудном объеме. Генераторы данных как компромисс, но не универсальный.
• Подбор нейронной сети для обучения. Здесь как минимум нужно разбираться и иметь опыт.

RL требует много исследований, мало общедоступных примеров решения комбинаторных задач (в основном TSP/VRP). Как дополнительные требования к задаче будут встраиваться в уже решаемые задачи с помощью RL, тоже большая неопределенность. В сравнении с математическим программированием - бОльшие инвестиции в трудозатраты.

Исследование не претендует на исчерпывающую оценку применимости RL к задачам математической оптимизации: речь идёт о базовой проверке гипотезы. Тем не менее, если вера в возможности RL сохранится, это может стать отправной точкой для более глубоких изысканий.

Заключение

Разработанный алгоритм решения оптимизационной задачи демонстрирует работоспособность даже в академическом варианте исполнения. Текущая реализация подтверждает перспективность RL, хотя ряд аспектов требует углублённого исследования.

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

• Gitрепозиторий решения задачи заправки ТС с помощью RL и NLP;
• NoMLсеминарпо материалу статьи;
• Neural Combinatorial Optimizationдля задач TSP и VRP (CVRP).