ДонНТУ Портал магистров ФКНТ Кафедра АСУ Научный руководитель

Реферат по теме выпускной работы

Содержание

Введение

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

1. Актуальность темы

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

2. Цель и задачи

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

основные задачи:

3. Постановка задачи

Каждая авиакомпания имеет определенный перечень слотов, на которых она может реализовать авиарейсы. Этот факт ограничивается правовыми актами государства. Разделяют летний и зимний полупериод. Для каждого полупериода расписание формируется за месяц до его начала.[2] Для задачи построения расписания данный факт является ограничением по направлению и времени вылета самолетов. Данное ограничение можно обойти при выполнении рейса от имени другой авиакомпании по договоренности.

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

Любой груз имеет свою ценность для авиакомпании и объём. Авиакомпания несет ответственность за транспортировку груза без физических и химических изменений.[3]

Возможности каждого ВС ограничены летными и грузовыми характеристиками. К летным характеристикам относится: дальность полета, расход топлива, размер бака, цена эксплуатации. К грузовым характеристикам относится: ограничения по объему груза, грузоподъёмность ВС.

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

4. Структура системы

Математическую модель системы можно разделить на 2 взаимосвязанные подсистемы:

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

4.1 Обзор подзадачи Распределение груза по ВС

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

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

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

схема расположения груза в McDonnell Douglas MD-11

Рисунок 1 - схема рассположения груза в McDonnell Douglas MD-11

4.1.1 Математическая модель подзадачи Распределение груза по ВС

Для решения требуемой задачи нам необходимы такие данные[4]:

А – Множество аэропортов (индекс a) ;

L – множество всех рейсов (индекс l);

P – множество всех классов грузов (индекс p);

F – множество типов самолетов (индекс f);

T– множество моментов времени отравления и прибытия рейсов расписания (индекс t);

CL(f) – множество рейсов, пересекающих нулевую линию

I(f,a,t) – множество прибывающих рейсов в аэропорт а в момент времени t на самолете типа f;

O(f,a,t) – множество вылетающих рейсов из аэропорта а в момент времени t на самолете типа f;

Параметры задачи:

– доход от накладных класса груза p ∈ P

– количество имеющихся в распоряжении самолетов типа

– вместимость ВС, назначенного на рейс f ∈ F

– затраты на полет по рейсу i ∈ L самолета типа f∈F

спрос на продукт p∈P

Неизвестные в данной задачи, которые необходимо найти:

– количество самолетов типа f∈F аэропорта

– количество самолетов типа f∈F аэропорта a∈A непосредственно до момента времени t∈T

– вес всего груза, отдельного класса p∈P.

Функция цели:

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

Необходимо найти ,, при которых функция цели будет максимальна, с учетом ограничений:

Условия покрытия:

,при этом ∈i ∈L

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

Условие баланса:

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

Использовать можно не больше, чем имеешь:

(5)

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

Условие ограниченной вместимости:

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

Дополнительные ограничения:

Для решения задачи оптимизации можно использовать следующие методы[5]:

4.2 Обзор подзадачи формирование цепочек рейсов

Постановка задачи: Каждый рейс может выполнить определенный тип ВС, или несколько типов, в зависимости от летных характеристик ВС и расстояния. Необходимо определить борт, на котором будет выполнена определенная цепочка. Данная задача являеться довольно популярная. Пример решения данной задачи для областных центров Украины можно посмотреть на Рисунке 2.

решения задачи коммивояжера для областных центров Украины

Рисунок 2 - Решения задачи коммивояжера для областных центров Украины(анимация: 11 кадров, 5 циклов, 61 Кб)

4.2.1 математическая модель подзадачи формирование цепочек рейсов

В модели используются следующие переменные и множества[6]:

количество имеющихся в распоряжение самолетов типа f

– затраты на полет по рейсу iсамолета типа f,

K – множество типов самолетов авиапарка, индекс f.

Необходимо найти такое решение x,f,I (вектор распределения ВС по рейсам), при котором линейная функция цели при условиях и ограничениях будет максимальна.

Ограничения:

Условие разбиения – в финальной совокупности цепочек каждый рейс, может быть, присутствовать в одной и только одной цепочке:

где

L : множество рейсов с индексом i∈L.

Условия мощности парка – количество цепочек, на которые назначен самолет данного типа, не должно превосходить количества имеющихся самолетов данного типа:

где

имеющееся количество ВС типа

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

где

IS( f , a) : множество цепочек рейсов, оканчивающихся в аэропорту , на которые назначен самолет типа .

OS( f , a) : множество цепочек рейсов, начинающихся в аэропорту , на которые назначен самолет типа .

Данная задача является классической задачей коммивояжёра с дополнительными ограничениями и решается с помощью модифицированного генетического алгоритма.[7]

Выводы

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

При написании данного реферата магистерская работа еще не завершена. Окончательное завершение: декабрь 2014 года. Полный текст работы и материалы по теме могут быть получены у автора или его руководителя после указанной даты.

Список источников

  1. Виноградов Л.В., Шебалов С.М. , Математическое моделирование в оптимизации планирования авиационных перевозок: формулы и методы расчетов типовых задач/
  2. Технология формирования сезонного расписания регулярных и стыковочных авиарейсов ИАТА [Электронный ресурс]. — Режим доступа: http://www.fly-jet.biz/tech.php.
  3. Федосин С.А., Есин Ю.Д. Прогнозирование спроса на рынок авиаперевозок, ГОУВПО Мордовский государственный университет им. Н. П. Огарева, г. Саранск.
  4. Зернова Н.А., Носова Е.В. , Фридман Г.М. Оперативная расстановка парка воздушных судов по рейсам, связанная с изменениями данных по спросу // Экономическая кибернетика: Сб. науч. тр. 2009. Вып. 19. с. 164-168.
  5. Задача о рюкзаке[Электронный ресурс]. — Режим доступа: http://ru.wikipedia.org/....
  6. Зернова Н.А, Фридман Г. М., Цепочки рейсов : определение, условий и алгоритмов построения
  7. Обобщённая задача коммивояжёра для определения рациональных маршрутов поставки[Электронный ресурс]. — Режим доступа: http://econference.ru/.../.