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

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

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

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

"Часто специальная команда может потратить месяцы или даже годы на разработку алгоритма для решения только одной из этих комбинаторных задач. Современное глубокое обучение дает нам возможность использовать новые достижения, чтобы помочь оптимизировать разработку этих алгоритмов. Мы можем взять то, что, как мы знаем, хорошо работает, и использовать искусственный интеллект для ускорения этого", - говорит Кэти Ву, доцент кафедры гражданского строительства и охраны окружающей среды Томаса Д. и Вирджинии У. Кэбот (CEE) и Института данных, систем и общества (IDSS) Массачусетского технологического института и член лаборатория информационных систем и систем принятия решений (LIDS).

К ней присоединились ведущий автор статьи Сируи Ли, аспирант IDSS; Венбин Оуянг, аспирант из Центральной и Восточной Европы; и Инин Ма, постдок LIDS. Исследование будет представлено на Международной конференции по обучению репрезентациям.

Устранение избыточности

Одним из мотивов для этого исследования является практическая проблема, выявленная магистранткой Девин Камилл Уилкинс на курсе начального уровня Wu по транспортировке. Студент хотел применить обучение с подкреплением к реальной задаче отправки поезда на Северном вокзале Бостона. Транзитной организации необходимо назначить много поездов к ограниченному числу платформ, где их можно развернуть задолго до прибытия на станцию.

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

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

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

Такие задачи быстро становятся слишком большими и громоздкими для традиционных решателей, поэтому пользователи могут использовать rolling horizon optimization (RHO), чтобы разбить проблему на управляемые блоки, которые могут быть решены быстрее.

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

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

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

"Возможно, эти предварительные решения хороши и не нуждаются в повторном вычислении, но, возможно, они и не очень хороши. Вот тут-то и появляется машинное обучение", - объясняет Ву.

Для своей методики, которую они называют оптимизацией скользящего горизонта, управляемой обучением (L-RHO), исследователи обучают модель машинного обучения предсказывать, какие операции или переменные следует пересчитать, когда горизонт планирования сдвигается вперед.

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

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

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

Адаптируемый, масштабируемый подход

Чтобы протестировать свой подход, исследователи сравнили L-RHO с несколькими базовыми алгоритмическими решателями, специализированными решателями и подходами, использующими только машинное обучение. Это превзошло их все, сократив время решения на 54 процента и улучшив качество решения до 21 процента.

Кроме того, их метод продолжал превосходить все базовые показатели, когда они тестировали его на более сложных вариантах проблемы, таких как поломка заводских машин или дополнительные перегрузки поездов. Это даже превзошло дополнительные базовые показатели, которые исследователи создали, чтобы бросить вызов своему решателю.

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

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

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

Эта работа была частично поддержана Национальным научным фондом, Комитетом поддержки исследований Массачусетского технологического института, стипендией Amazon Robotics PhD и MathWorks.