Возможно, наиболее распространенной из всех математических тем, которые появляются в промышленных приложениях, является тема комбинаторной оптимизации. Комбинаторная оптимизация - это класс задач, состоящий в поиске оптимального объекта из конечного набора объектов. Известные и вездесущие примеры таких проблем включают задачу коммивояжера, задачу маршрутизации транспортных средств (CVRP), задачу о ранце, максимальную проблема потока и любая проблема целочисленного программирования. По определению пространство поиска для комбинаторной оптимизации конечно, и поэтому всегда существует точное оптимальное решение. Однако для наиболее интересных проблем (включая перечисленные выше) размер области поиска растет экспоненциально с размером входных данных проблемы, поэтому найти точное оптимальное решение обычно невозможно с вычислительной точки зрения.
Из-за вычислительной невозможности нахождения точных решений на практике приходится довольствоваться использованием эвристических алгоритмов, дающих приблизительно оптимальные решения. Эвристики часто бывают быстрыми и эффективными, но, в отличие от точных решений, в них отсутствуют какие-либо теоретические гарантии оптимальности. Люди генерируют новые эвристические алгоритмы методом проб и ошибок, имея очень мало общей теории для руководства их разработкой. По этой причине потенциально можно много выиграть от использования искусственного интеллекта (ИИ) для автоматизации и систематизации процесса эвристического проектирования.
Алгоритм ИИ отличается от традиционных эвристических подходов тем, что он может учиться на собственном опыте и со временем улучшать свою производительность по мере того, как он получает доступ к большему количеству данных. По этой причине алгоритм ИИ можно рассматривать как метаэвристику для изучения новой эвристики. Применение ИИ к задачам комбинаторной оптимизации в настоящее время является активной областью научных исследований. Некоторые недавние влиятельные статьи включают: 1) Изучение алгоритмов комбинаторной оптимизации по графам; 2) Обучение с подкреплением для решения задачи маршрутизации транспортных средств; 3) Внимание, научитесь решать задачи маршрутизации. В этих трех документах применяются модели глубокого обучения с подкреплением для выработки решений проблемы коммивояжера и некоторых версий проблемы маршрутизации транспортных средств с ограниченными возможностями. Вышеупомянутые документы сообщают о результатах, которые в некоторых случаях являются конкурентоспособными или близкими к конкурентоспособным с текущими (не-AI) современными решателями. По мере проведения дополнительных исследований результаты должны улучшаться.
Наша работа над проблемой выбора маршрута транспорта
В Crater Labs в течение последнего года мы проводили исследовательскую программу, применяя методы машинного обучения и искусственного интеллекта для решения задач комбинаторной оптимизации. Мы опирались на недавнюю работу из вышеупомянутых документов для решения более сложных (и, следовательно, более реалистичных) версий проблемы маршрутизации транспортных средств, задач оптимизации цепочки поставок и других связанных проблем оптимизации. До сих пор нам удавалось воспроизвести результаты в вышеупомянутых документах, и сейчас мы активно работаем над тем, чтобы продвинуть их работу дальше для решения более сложных проблем. Некоторые из этих проблем включают:
[a] CVRP с несколькими грузовиками для доставки, размещенными на нескольких складах. Заказы на доставку имеют временные ограничения, а грузовики подчиняются ограничениям совместимости в отношении предметов, которые они могут перевозить.
[b] Очень большие экземпляры CVRP, состоящие из тысяч или десятков тысяч узлов вместо сотен. Действительно, в упомянутых выше статьях рассматривается только CVRP с сотней узлов или меньше.
[c] Задача стохастической маршрутизации транспортных средств. Здесь заказы на доставку и / или позиции узлов меняются случайным образом, пока грузовик доставки движется по маршруту. Задача здесь состоит в том, чтобы спрогнозировать будущее предложение и спрос различных узлов на графике, а затем сгенерировать маршруты в соответствии с этими прогнозами.
[d] Проблемы оптимизации цепочки поставок. Подобно проблеме выбора маршрута транспортного средства, но когда грузовики совершают и пикап, и доставку, а начальное и конечное местоположения грузовика доставки не обязательно совпадают.
Ниже мы опишем некоторые детали наших рабочих моделей для задачи выбора маршрута транспортного средства.
Модели искусственного интеллекта для задачи маршрутизации транспортных средств
Наша текущая рабочая модель для решения проблемы маршрутизации транспортных средств состоит из двух основных компонентов: кодировщика и декодера. Задача кодировщика - получить экземпляр CVRP (в форме графа) и вернуть векторное представление для каждого из узлов входного графа. Декодер принимает выходные данные кодировщика в качестве входных данных. Его работа состоит в том, чтобы последовательно возвращать пункты назначения путешествия грузовика в порядке, определенном его изученной политикой. Кодер и декодер состоят из нейронных сетей с обучаемыми коэффициентами. Оптимальные коэффициенты изучаются с помощью обучения с подкреплением с градиентом политики с использованием алгоритма REINFORCE (см. Методы градиента политики для обучения с подкреплением с аппроксимацией функций). Модель является модульной в том смысле, что можно заменить кодер и декодер на различные нейронные архитектуры, пока логика обработки выходного маршрута остается постоянной.
В следующих абзацах мы подробно опишем нейронные архитектуры, которые мы используем для кодировщика и декодера.
Кодировщик
Как упоминалось в предыдущем абзаце, работа кодировщика состоит в том, чтобы получить граф, представляющий конкретный экземпляр CVRP, и вернуть векторное представление для каждого из узлов входного графа. Входной граф представлен парой (N, E), где N = (x_ {1}, .., x_ {n}) \ in \ R ^ {n * k} - список узлов, а E \ in \ R ^ {n²} - взвешенная матрица смежности для графа. Каждый x_ {i} \ in \ R ^ {k} - это вектор, описывающий особенности, приписываемые данному узлу, то есть его географическое положение, объем и вес его спроса, время начала и окончания его временного окна доступности, и т. д. Выходными данными кодировщика является список новых векторов \ hat {x} _ {1},…, \ hat {x} _ {n}) \ in \ R ^ {n * m}, кодирующих топологическую структуру график. Выходной вектор \ hat {x} _ {i} \ in \ R ^ {m} соответствует входному узлу x_ {i}. Но в результате обработки кодировщиком \ hat {x} _ {i} содержит информацию о своих соседях (и соседях соседей, и соседях соседей соседей и т. Д.), А вход x_ {i } - это просто изолированный узел без знания топологии графа. Обратите внимание, что вывод кодировщика больше не содержит матрицу смежности, он содержит только последовательность закодированных’ ’узловых векторов. Целое число m - это выбранный гиперпараметр в модели. Обычно выбирается больше, чем $ k $, длина характеристик входного узла. Нейронная архитектура, используемая для кодировщика, представляет собой графическую сеть внимания, аналогичную той, что используется в «Индуктивном представлении обучения по графам, и Графические сети внимания . Модели, предлагаемые в этих статьях, очень гибкие, и они оставляют много места для наших собственных корректировок и дополнений, адаптированных к особенностям нашей конкретной проблемы. Еще одна возможная модель кодировщика, с которой мы экспериментировали, - это преобразователь. Это архитектура, которая сначала использовалась для нейронного машинного перевода (и других задач НЛП) в Внимание - это все, что вам нужно, а затем была применена к проблеме маршрутизации транспортных средств в Внимание, учиться для решения проблем с маршрутизацией .
Архитектуры декодеров
Как упоминалось выше, декодер принимает выходные данные кодировщика в качестве входных данных. Его работа состоит в том, чтобы последовательно возвращать пункты назначения тура грузовика. Обычно он содержит три подмодуля: рекуррентную нейронную сеть (RNN), механизм внимания и выходной классификатор softmax. Этот дизайн вдохновлен моделями, традиционно используемыми для нейронного машинного перевода, и был принят для решения задач маршрутизации транспортных средств. Возникает некоторый вопрос, насколько действительно полезен элемент RNN в этой модели, и что, `` усилив '' механизм внимания, можно обойтись без него. Это было показано в Внимание, научитесь решать проблемы маршрутизации , и это то, с чем мы тоже экспериментируем.
