В последние годы область исследования операций процветала наряду с развитием вычислительной мощности. Сейчас многие организации используют этот подход, чтобы разрабатывать оперативные, тактические и даже стратегические решения. В случае успеха компания значительно сокращает затраты или даже увеличивает прибыль. Решаемые проблемы обычно включают распределение, составление графиков и маршрутов, соединение и разделение, а также прочие задачи в рамках определенного времени и/или пространства.
Здесь мы кратко рассмотрим следующие задачи: выбор маршрута транспорта (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 также можно решить быстро в реальном времени, получив при этом оптимальное или близкое к оптимальному решение, которое позволит справиться с неожиданными изменениями. Все это демонстрирует преимущество использования методов исследования операций.
Читайте также:
- Генерируйте реалистичные датасеты с помощью Snowfakery
- Анализ социальных сетей: от теории графов до приложений на Python
- Обработка естественного языка
Читайте нас в Telegram, VK и Яндекс.Дзен
Перевод статьи ER RAQABI El Mehdi: Some Classical Applications of Operations Research
