Table of Contents

Введение

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

Понимание целочисленного программирования

Целое программирование (IP) является отраслью математической оптимизации, где некоторые или все переменные решения ограничены быть целыми числами. Когда все переменные являются целыми числами, это называется чистой целочисленной программой; когда только подмножество являются целыми числами, это смешанная целочисленная программа (MIP). IP имеет важное значение для управления автопарком, потому что многие операционные решения являются естественными дискретными: вы не можете назначить 2,7 транспортных средств на маршрут или отправить половину грузовика клиенту.

Почему целочисленные переменные имеют значение в управлении флотом

Непрерывное линейное программирование (LP) предполагает, что переменные могут принимать любое реальное значение. Это работает для задач смешивания, но для назначения, планирования и маршрутизации дробные решения бессмысленны. Например, решение LP может предложить отправку 1,3 транспортных средств из депо А и 0,7 транспортных средств из депо В. Целое программирование заставляет модель выбирать целые числа, давая действенные планы. Общие целочисленные типы переменных включают:

  • Бинарные переменные (0 или 1): Используется для принятия решений «да/нет», таких как «выбран ли маршрут r?» или «выбран ли автомобиль v?».
  • Общие целочисленные переменные: Представленные значения, такие как «количество транспортных средств, назначенных для смены s» или «инвентаризация, хранящаяся на складе w».
  • Программирование со смешанным целым числом (MIP): Комбинирует целые и непрерывные переменные; например, непрерывную переменную для расхода топлива вместе с целыми переменными для назначения транспортного средства.

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

Основные компоненты модели управления флотом IP

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

Переменные решения

Переменные принятия решений переводят реальные действия в математические термины. Для автономного управления автопарком типичные переменные включают:

  • = 1, если транспортное средство v перемещается из местоположения i в местоположение j, 0 в противном случае (двоичный, для маршрутизации).
  • = 1, если транспортное средство v находится в эксплуатации в течение временного интервала t, 0 в противном случае (двоичный, для планирования).
  • = количество транспортных средств, назначенных базовой станции k (целое число, для распределения депо).

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

Объективная функция

Цель количественно определяет, что волнует оператора флота. Общие цели включают:

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

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

Ограничения

Основные ограничения, которые создают семьи автономных флотов, включают:

  • Сохранение потока: Для проблем маршрутизации каждое транспортное средство, которое входит в местоположение, должно покинуть его (кроме депо).
  • Ограничения по вместимости: Транспортные средства могут перевозить ограниченное количество пассажиров или грузоподъемность.
  • Окна времени: Каждый пикап или доставка должны происходить в течение определенного интервала (например, между 2:00 вечера и 3:00 вечера).
  • Ограничения батареи или дальности: Автономные электромобили имеют максимальное расстояние до необходимости подзарядки.
  • Ограничения по размеру: Общее количество доступных транспортных средств фиксировано, или количество транспортных средств, развернутых за смену, ограничено.
  • Эксклюзивность назначения: Каждая задача назначается ровно одному транспортному средству (или нулю, если запрос может быть отклонен).

В формуле ограничения часто используются методы «большого-М» для моделирования логических условий, таких как «если транспортное средство v служит местоположению i, то оно также должно служить местоположение j в пределах своего маршрута».

Формулирование общих проблем оптимизации флота

Несколько канонических проблем неоднократно возникают в автономном управлении автопарком. Понимание их формулировок ИС помогает практикующим строить модели для их конкретного контекста.

Проблема маршрутизации транспортных средств (VRP)

VRP является основой многих систем оптимизации автопарка. Набор локаций клиентов должен посещаться парком транспортных средств, начинающихся и заканчивающихся в депо. Классическая формулировка использует бинарные переменные и включает ограничения для степени (каждый клиент посетил ровно один раз), выбытия из субтура (для предотвращения отключенных циклов) и пропускной способности транспортного средства. Для автономных автопарков VRP часто расширяется с временными окнами (VRPTW) и парами пикапа и доставки. Цель, как правило, состоит в том, чтобы минимизировать общее расстояние или время в пути.

Простая однодепойная VRP-формация (без временных окон) выглядит так:

min Σ v Σ (i,j) c ij · x ijv
, с учетом:
Σ v Σ j x ijv = 1 для каждого клиента i (посещать каждого один раз)
Σ i x i0v = 1 для каждого транспортного средства v (листовое депо)
Σ j x 0jv = 1 для каждого транспортного средства v (возвращение в депо)
, сохранение потока, пропускная способность, удаление субтура.

Назначение и расписание

Управление автопарком также включает в себя назначение транспортных средств для смен, задач или зарядных станций. Задача назначения минимизирует стоимость (например, поездка для старта местоположения) при условии, что каждое транспортное средство получает максимум одну задачу и каждая задача покрывается одним транспортным средством. Когда задачи имеют временные окна и несколько транспортных средств могут быть назначены для одной и той же задачи в последовательности (например, для объединения поездок), проблема становится сложной задачей планирования MIP с преобладанием и ограничениями синхронизации.

Местоположение депо и состав флота

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

Ребалансировка в реальном времени

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

Технологии решений и программное обеспечение

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

Точные методы

  • Ветвь и связанность: Наиболее распространенный точный алгоритм для MIP. Он рекурсивно разделяет осуществимую область на подзадачи (ветвление) и вычисляет границы для обрезания субоптимальных ветвей.
  • Резка плоскостей: Неравенство, добавляемое к релаксации LP, чтобы затянуть осуществимую область и ускорить поиск. Современные решатели объединяют ветвь и связываются с режущими плоскостями (разветвление и разрез).
  • Ветвь и цена: Используется, когда проблема имеет огромное количество переменных (как и все возможные маршруты в VRP).Решитель генерирует новые переменные (колонки) на лету, используя ценовую подзадачу.

Ведущие коммерческие решатели для IP включают IBM ILOG CPLEX, Gurobi и FICO Xpress. Варианты с открытым исходным кодом, такие как SCIP и Google OR-Tools, широко используются в исследованиях и промышленности.

Эвристические и метаэвристические методы

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

  • Конструктивная эвристика: Построить решение шаг за шагом (например, вставка ближайшего соседа для VRP).
  • Местный поиск: Улучшить существующее решение небольшими модификациями (2-opt, relocate, swap).
  • Метагевристика: Руководство локального поиска, чтобы избежать локального оптимума. Примеры включают симулированное отжиг, генетические алгоритмы, поиск табу и поиск по крупным соседствам (LNS).

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

Реальные приложения и тематические исследования

Целые модели программирования используются в автономных парках транспортных средств в нескольких секторах.

Автономный ездовой хейлинг (Robotaxis)

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

Автономные транспортные средства доставки

Нуро, Starship Technologies и Amazon Scout разворачивают парки небольших автономных транспортных средств для доставки на последнюю милю. Целое программирование планирует маршруты и графики для сотен транспортных средств, часто с чувствительными ко времени окнами доставки и ограниченным бортовым хранилищем. VRP с временными окнами и ограничениями пропускной способности является стандартной формулировкой.

Складские автономные мобильные роботы (AMR)

В центрах исполнения парки AMR перемещают полки или пакеты между станциями. Целое число программных координат задач выбора и размещения, предотвращения заторов и графиков зарядки аккумуляторов. Исследование 2020 года в Annals of Operations Research описало MIP для назначения задач робота и маршрутизации, которая сократила время простоя на 18%.

Общественный транспорт и общая мобильность

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

Проблемы и соображения

Несмотря на силу целочисленного программирования, применение его к автономным флотам сопряжено с несколькими практическими препятствиями.

Масштаб и время вычислений

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

Неопределенность и стохастичность

Время в пути, спрос клиентов и доступность транспортных средств не известны в полной мере. Детерминированные модели IP могут стать неоптимальными, когда прогнозы ошибочны. Стохастическое программирование и надежная оптимизация расширяют IP для обработки неопределенности, но они увеличивают сложность модели. Многие операторы вместо этого часто (каждые 5-10 минут) оптимизируют обновленные данные.

Интеграция с системами реального времени

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

Справедливость и нормативные ограничения

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

Будущие направления

Интегрированное программирование автономных флотов продолжает развиваться вдоль нескольких границ.

Интеграция с машинным обучением

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

Динамическая и распределенная оптимизация

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

Конечная оптимизация платформ

Новые программные платформы объединяют IP-решатели, моделирование и визуализацию, чтобы позволить операторам флота быстро создавать, тестировать и развертывать модели. Низкокодовые и открытые среды, такие как OR-Tools и COIN-OR Foundation, снижают барьер для входа.

Заключение

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