Решение задачи равномерного разбиения рейсов летного расписания авиакомпании

Размещено на http://www.allbest.ru/

РЕШЕНИЕ ЗАДАЧИ РАВНОМЕРНОГО РАЗБИЕНИЯ РЕЙСОВ ЛЕТНОГО РАСПИСАНИЯ АВИАКОМПАНИИ. ЭВРИСТИЧЕСКИЕ АЛГОРИТМЫ.

Васильев Ю.М.

Уният С.В.

В статье описаны эвристические алгоритмы, предназначенные для поиска решения оптимизационной задачи равномерного разбиения множества связок (оборотных рейсов) на подмножества, которая возникает на одном из этапов бизнес-процесса планирования расписания работы бортпроводников (БП) в одной из крупнейших российских авиакомпаний [1]. Следуя принятой в авиакомпании практике, единая задача планирования (достаточно сложная с точки зрения объема исходных данных) подразделяется на несколько параллельно решаемых подзадач меньшей размерности, число которых равно количеству экспертов, занятых в составлении графика работ БП.

Основной целью каждого эксперта является назначение БП на все связки на заданном горизонте планирования (как правило, на месяц) с учетом трудовых, операционных и государственных правил работы [2]. Для этого экспертами строится месячный график работы БП с использованием имеющейся системы поддержки принятия решений. Каждый эксперт занят планированием определенного подмножества БП, каждое из которых носит название «книга». Книги формируются так, что в каждой содержится примерно равное количество БП с примерно равными характеристиками (должность, класс, пол, знание иностранных языков, допуск на типы ВС). Отметим, что на практике количество БП, доступных для планирования в книгах, может существенно различаться вследствие отпусков, больничных и т.д. С периодичностью раз в месяц производится разбиение связок на подмножества, число которых равно числу книг. Книга и соответствующее ей подмножество связок образуют «рабочий стол», с которым и работает один эксперт. Для того, чтобы все эксперты действовали в одинаковых условиях, связки также должны быть равномерно распределены по подмножествам по некоторому набору заранее выбранных критериев.

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

Эвристический алгоритм

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

,

где - значение -й характеристики для -го подмножества, вычисленной после выполнения шага под номером , т.е. после распределения в одно из подмножеств -й связки, - усредненное значение -й характеристики, а - весовой коэффициент -й характеристики, . Следует отметить, что в точной постановке оптимизационной задачи равномерного распределения связок, см. [1], использована другая нелинейная целевая функция вида

,

которая, в отличие от , допускает возможность линеаризации.

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

,

где - приращение -й суммарной характеристики подмножества под номером , которое она получает при добавлении в это подмножество связки номером из множества связок, еще не распределенных к шагу под номером [1]. Значения приращений , , , рассчитываются по исходным данным всех связок и по параметрам всех книг.

Таким образом, на первом шаге осуществляется выбор из вариантов ( подмножеств и еще не распределенных связок), на втором шаге - из , и т.д. Применение пошаговой локальной оптимизации означает, что алгоритм ЭА-1 принадлежит к «жадным» алгоритмам [4]. Время работы алгоритма .

Модифицированный эвристический алгоритм

Для того, чтобы избавиться от квадратичной зависимости времени работы алгоритма ЭА-1 от числа связок , введем четыре вида сортировок для множества связок :

1. разделить множество связок на подмножества по дню вылета; отсортировать каждое подмножество по убыванию значения ; объединить подмножества;

2. разделить множество связок на подмножества по типам сообщения (ВВЛ, МВЛ и СНГ); отсортировать подмножества по возрастанию количества элементов; разделить каждое подмножество на подмножества по дню вылета; отсортировать каждое подмножество по убыванию значения ; объединить подмножества;

3. разделить множество связок на подмножества по типам сообщения; отсортировать подмножества по возрастанию количества элементов; отсортировать каждое подмножество по убыванию значения ; разделить каждое подмножество на подмножества по значению ; разделить каждое подмножество на подмножества по дню вылета; объединить подмножества;

4. разделить множество связок на подмножества по дню вылета; добавлять в новое множество по одному элементу из каждого подмножества, наполняя новое множество постепенно.

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

Числовые расчеты

Предложенные в статье эвристический алгоритм (ЭА-1) и модифицированный эвристический алгоритм (ЭА-2) были применены для расчета задачи о равномерном разбиении связок для одной из крупнейших российских авиакомпаний. Все вычисления проведены в компьютерной математической среде Wolfram Mathematica 10.3 [6].

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

Таблица 1 Натурные исходные данные для создания графика работы БП

Следует отметить, что из общего перечня критериев равномерности, см. [1], при расчетах исключен критерий «общее количество связок по типу ВС для рабочего стола», который использовался в точной постановке задачи. Это связано с тем, что на каждое направление в авиакомпании назначается один определенный тип ВС, и выполнение равномерности по исключенному критерию обеспечивается критерием «общее количество связок по направлениям для рабочего стола». Весовые коэффициенты для формул и подбирались с использованием экспертных оценок. Для ЭА-2 из четырех решений (соответствующих четырем типам предварительной сортировки связок) выбиралось лучшее по значению целевой функции . Расчет с использованием ЭА-1 длился приблизительно 1.2 часа, ЭА-2 - 3.7 секунды, эксперт решал поставленную задачу около 7 рабочих дней.

В таблице 2 представлены рассчитанные по формуле числовые данные для среднеарифметического и максимального отклонений от усредненного значения по критерию «средний налет на БП по типу сообщения» для расчета №1 по алгоритмам ЭА-1 и ЭА-2 и экспертному расчету.

Таблица 2 Среднеарифметическое и максимальное отклонение от усредненного значения по критерию «средний налет на БП по типу сообщения» для расчета №1

Как видно из таблицы 2, оба эвристических алгоритма дают результат значительно лучший, чем у эксперта. При этом, ЭА-1 показал наилучший результат для международных рейсов и рейсов на территории стран СНГ, а ЭА-2 - для внутренних рейсов. Решения, найденные с помощью эвристических алгоритмов, сопоставимы, с практической точки зрения, по данному критерию.

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

Таблица 3 Отклонения по критериям «равномерное разбиение связок по направлениям» и «равномерное разбиение связок по дням» для расчета №1

Этот критерий важен с точки зрения соблюдения в авиакомпании принципа «социальной справедливости расписания для БП», под которым понимается, что индивидуальные графики работ у БП одной квалификации должны как можно меньше отличаться друг от друга. Наилучший результат дал алгоритм ЭА-1. Максимальная разница по всем направлениям у алгоритмов ЭА-1 и ЭА-2 оказалась вдвое меньше, чем в решении, полученном экспертом.

Вдобавок, в таблице 3 представлен анализ результатов работы ЭА-1, ЭА-2 и эксперта по критерию «равномерное разбиение связок по дням» с использованием тех же показателей.

По данным таблицы 3, по критерию «равномерное разбиение связок по дням» можно сделать аналогичные выводы, что и по критерию «равномерное разбиение связок по направлениям»: алгоритмы ЭА-1 и ЭА-2 показывают результаты лучше, чем у эксперта. Равномерность распределения связок между рабочими столами по дням - крайне важный показатель, поскольку это исключает нарушения режима труда и отдыха в персональных графиках работы БП. В среднем на одном рабочем столе каждый день оказывается связок (всего около 2000 связок, 6 рабочих столов и 31 день в месяце), и в случае значительной неравномерности этого критерия у эксперта может возникнуть экстремальная ситуация (превышение еженедельного рабочего времени). С этой точки зрения, максимальная разница числа связок по всем дням являются ключевым показателем качества решения.

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

Наилучшее решение для расчета №1 по значению целевой функции получено при помощи алгоритма ЭА-1, алгоритм ЭА-2 оказался хуже на 6%, а решение эксперта хуже на 57%.

Весовые коэффициенты, подобранные для расчета №1, были использованы и в расчете №2, однако показали качественно более низкие результаты. Поэтому для расчета №2 были подобраны новые веса, которые улучшили результат.

В таблице 4 приведены значения отклонений для разных критериев равномерности для расчета №2 на базе алгоритмов ЭА-1 и ЭА-2 и двух наборов весовых коэффициентов. В решениях с 1 по 5 использовался тот же набор весовых коэффициентов, который применялся и для расчета №1, а в решениях с 6 по 10 использован новый набор весовых коэффициентов. Решения 5 и 10 получены при помощи алгоритма ЭА-1, остальные - на базе ЭА-2 с четырьмя вариантами предварительной сортировки множества связок. Колонка «ЦФ*» показывает отношение значения целевой функции для алгоритма ЭА-2 к соответствующему значению для алгоритма ЭА-1.

Таблица 4 Результаты расчета №2 для эвристических алгоритмов с разными наборами весовых коэффициентов

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

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

Модернизация бизнес-процесса

Необходимость модернизации производственного процесса связана со следующими факторами:

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

· несоответствие процесса современным требованиям;

· неэффективность существующей системы поддержки принятия решения;

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

Сформулированы следующие бизнес-требования к работе отдела планирования:

· внедрение автоматизированного производственного процесса для преобразования работы отдела планирования;

· повышение уровня автоматизации и осуществление планирования при помощи системы принятия решений [3];

· результаты работы отдела планирования должны ориентироваться на минимизацию затрат авиакомпании на выполнение летных заданий БП.

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

На данный момент, работа по распределению связок по рабочим столам начинается за 7 недель до начала месяца планирования и включает в себя три этапа. На первом этапе формируются все связки в соответствии с требованиями работы БП (срок выполнения этапа 1-2 дня). На втором этапе создается предварительное, без учета информации об отпусках БП, распределение связок по рабочим столам. За 20 дней до начала планируемого месяца в систему автоматизации поддержки принятия решения вводится информация по мероприятиям, не связанным с выполнением рейса, включая отпуска, и, следовательно, становится известна численность доступных для планирования БП по рабочим столам на месяц планирования. С появлением данной информации начинается третий этап работы: происходит перераспределение связок по рабочим столам с учетом появившейся информации по отпускам БП и мероприятиям (срок выполнения этапа 2-3 дня), и затем полученное распределение передается экспертам отдела планирования для составления графика работы БП. Таким образом, на планирование графика работы БП остается 2 недели.

Разработанное авторами статьи решение на базе эвристического алгоритма дает возможность повысить автоматизацию производственного процесса. Усовершенствованный бизнес-процесс содержит два этапа.

Первый этап начинается за 7 недель до начала планируемого месяца и включает в себя:

· переформирование связок по требованиям для БП (1-2 дня);

· формирование исходной информации с учетом имеющихся данных по планируемым отпускам и мероприятиям, что позволит рассчитать численность доступных для планирования БП по рабочим столам со значительной степенью достоверности (менее 1 дня);

· распределение по рабочим столам большей части связок (например, 85% от числа всех связок). Оставшиеся нераспределенными связки необходимы для обеспечения равномерности распределения по рабочим столам после получения реальных данных о численности доступных для планирования БП по рабочим столам на планируемый месяц (менее 1 дня);

· выдача работникам отдела планирования распределения по рабочим столам 85% связок (менее 1 дня).

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

Второй этап начинается за 20 дней до начала планируемого месяца:

· использование реальной информации о численности доступных для планирования БП по рабочим столам (менее 1 дня);

· распределение оставшихся 15% связок по рабочим столам (менее 1 дня);

· выдача экспертам полного распределения связок по рабочим столам.

Соответственно, окончательное распределение связок по рабочим столам сформировано за 20 дней до начала месяца планирования.

Предложенная корректировка производственного процесса имеет следующие преимущества:

· сокращение затраченных человеко-часов на работу по распределению связок с существенным увеличением качества;

· эксперты, выполняющие работу по составлению расписания БП, могут начинать планирование значительно раньше;

· возможно автоматическое переформирование связок, что позволит сэкономить ещё 1-2 дня на первом этапе и сократить объем человеко-часов на данную подзадачу.

Заключение

В статье представлены следующие результаты работы:

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

· в компьютерной математической среде Wolfram Mathematica 10.3 разработан программный модуль математического обеспечения;

· процесс распределения множества связок по рабочим столам сокращен с одной недели до нескольких минут;

· сформулированы предложения по внедрению программного решения в бизнес-процесс по составлению графика работ БП в одной из крупнейших российских авиакомпаний.

Следует также отметить особенности разработанного автоматизированного подхода:

· полученное на базе предложенных алгоритмов решение является субоптимальным;

· алгоритмы учитывают все необходимые критерии равномерности распределения связок;

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

· алгоритмы простые и удобные и могут быть реализованы на языке программирования любого уровня с использованием базовых технологий;

· алгоритмы гибкие, в них предусмотрена возможность выбора числа рабочих столов, критериев равномерности, выставление значимости критериев (весовых коэффициентов), существует механизм добавления новых критериев, возможен выбор модификаций эвристического алгоритма;

· алгоритм используется в системе поддержки принятия решения и автоматизирует процесс не полностью.

Литература

1. Васильев Ю.М., Уният С.В., Фридман Г.М. Решение задачи равномерного разбиения рейсов летного расписания авиакомпании. Точная математическая постановка // Известия Санкт-Петербургского государственного экономического университета. 2016.

2. Приказ Минтранса РФ от 21.11.2005 N 139 (ред. от 17.09.2010) «Об утверждении положения об особенностях режима рабочего времени и времени отдыха членов экипажей воздушных судов гражданской авиации Российской Федерации».

3. Barnhart C., Belobaba P., Odoni A. Application operation research in the air transport industry // Transportation Science, vol. 37, No. 4, 2003. pp. 368-391.

4. Cormen Thomas H., Leiserson Charles E., Rivest Ronald L., Stein Clifford. Introduction to Algorithms Third ed. // MIT Press. 2009. pp. 414-450.

5. Van Veldhuizen D.A., Lamont G.B. Multiobjective Evolutionary Algorithms: Analyzing the State-of-the-Art // Evolutionary Computation, 8(2). 2000. pp. 125-147.

Аннотация

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

Ключевые слова. планирование, составление графика работ бортпроводников, математическая моделирование, оптимизационная задача, задача разбиения множества, эвристические алгоритмы

Two heuristic algorithms have been proposed in the paper for solution to the uniform partitioning problem for flight schedule. Both algorithms were applied to full-scale data of one of the major Russian airlines. A modification of business-process is advocated for an airline crew planning which enables one to increase efficiency and decrease labor costs.

Keywords. planning, airline crew planning, mathematical model, optimization problem, set partitioning problem, heuristic algorithms

Размещено на Allbest.ru