Пять направлений применения исследования операций

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

Здесь мы кратко рассмотрим следующие задачи: выбор маршрута транспорта (Vehicle Routing Problem  —  VRP), планирование полетов (Airline Planning Problem  —  APP), составление графика для водителей автобусов (Bus Driver Scheduling Problem  —  BDSP), распределение локомотивов (Locomotive Assignment Problem  —  LAP) и составление расписания смен (Shift Scheduling Problem  —  SSP).

Задача выбора маршрута транспорта (VRP)

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

Проблему можно обобщить до VRP с временными интервалами (VRPTW). В таком случае в дополнение к предыдущим условиям обслуживание клиента должно начинаться в интервале, определенном по самому раннему и самому позднему времени начала обслуживания.

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

Ниже представлена простая модель.

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

Задача планирования полетов (APP)

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

Список подзадач включает следующие категории.

  • Составление графика рейсов. Здесь нужно определить набор рейсов с установленным временем вылета и прибытия с целью максимизации ожидаемой прибыли.
  • Распределение самолетов. Каждому регулярному рейсу назначается тип воздушного судна с учетом их возможностей и числа доступных авиасредств, а также максимизации прибыли.
  • Составление маршрутов воздушного движения. Здесь требуется распределить самолеты по рейсам, удовлетворяя требования технического обслуживания.
  • Составление графиков работы сотрудников экипажа. Последним этапом определяется график сотрудников. Он должен охватить все запланированные рейсы и соблюсти необходимые ограничения. Обычно проводится в два этапа: объединение и присвоение. В первом генерируются наборы пар с учетом регулярных рейсов, а во втором  —  составляется месячный график на каждого члена экипажа с учетом набора пар.

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

Задача составления графика для водителей автобусов (BDSP)

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

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

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

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

Задача распределения локомотивов (LAP)

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

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

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

Задача составления расписания смен (SSP)

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

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

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

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

Читайте также:

Читайте нас в Telegram, VK и Яндекс.Дзен


Перевод статьи ER RAQABI El Mehdi: Some Classical Applications of Operations Research

Предыдущая статьяКак улучшить работу с кодом на TypeScript с VSCode
Следующая статья10 полезных инструментов для фронтенд-разработчика