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

Реферат за темою випускної роботи

Зміст

Вступ

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

1. Актуальність теми

На даний момент все більше компаній у сфері торгівлі потребують послуг з транспортування товару. У конкурентній боротьбі виграє компанія з мінімальними транспортними витратами. Актуальність даної проблеми підтверджується тим, що за оцінками експертів до 50% всіх витрат в торгівлі пов'язано з транспортними витратами. [1] За швидкістю виконання і віддалі авіаіндустрія не має конкурентів у транспортуванні вантажу. Для підвищення власного прибутку, в ситуації, що склалася, авіакомпанії хочуть скоротити витрати на власні послуги за рахунок раціонального використання власних ресурсів та організації виробництва.

Магістерська робота присвячена актуальній науковій задачі розробки уніфікованого підходу до синтезу автоматів Мура, спрямованого на зменшення апаратурних витрат у результуючому пристрої та складеного з алгоритмічних, комбінаторних та схемотехнічних оптимізаційних прийомів. У якості цільового базису використовуються мікросхеми FPGA фірми Xilinx, що сполучають функціональність, програмованість, реконфігурованість і доступність широкому споживачу, а інструментальними засобами дослідження виступають САПР Xilinx ISE, Verilog HDL і Java SE.

2. Мета і задачі

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

основні задачі:

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

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

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

Будь–який вантаж має свою цінність для авіакомпанії і об'єм. Авіакомпанія несе відповідальність за транспортування вантажу без фізичних і хімічних змін.[3]

Можливості кожного НД обмежені льотними і вантажними характеристиками. До льотним характеристикам відноситься: дальність польоту, витрата палива, розмір бака, ціна експлуатації. До вантажним характеристиками належить: обмеження за обсягом вантажу, вантажопідйомність ВС.

При формуванні розкладу вантажних авіаперевезень необхідно враховувати всі перераховані вище фактори. З–за численних параметрів, які впливають на складання розкладу НД випливає завдання автоматизації цього процесу, вирішення якої дозволить зменшити трудові витрати, витрати на паливо, на експлуатацію ПС, видатки навантаження.

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

Математичну модель системи можна розділити на 2 взаємопов'язані підсистеми:

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

4.1 Огляд підзадачі Розподіл вантажу по НД

У кожному аеропорті є вантаж, що очікує транспортування. Кількість вантажу, його вага, розмір вказуються у накладній на перевезення вантажу. Крім цього в накладній вказується ціна транспортування, яка обчислюється в пунктах прийому вантажу і залежить від типу вантажу. Кожне НД характеризується вантажопідйомністю та льотними характеристиками, які визначають можливі перельоти без пересадок і витрата палива.

Необхідно перевезти вантаж у зазначений пункт призначення при заданих величинах необхідної перевезення вантажу (вага і витрачена ціна), вибравши для нього певний тип ПС, отримавши максимальний прибуток від транспортування. Приклад розподiлу вантажу в найпопуярнiшому вантажному ВС можлвиво побачити на Малюнкi 1.

Рішення даної задачі дозволить раціонально використовувати повітряні ресурси (ВР), що, у свою чергу, мінімізує витрати на паливо та експлуатацію повітряних суден. Приклад рассположенія вантажу в найпопулярнішому вантажному НД можна подивитися на Малюнку 1.

Схема розташування завантажує McDonnell Douglas MD-11

Рисунок 1 – Схема rasspoloženiâ Вантажі 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 Огляд підзадачі формування ланцюжків рейсів

Постановка завдання: Кожен рейс може виконати певний тип ПС, або кілька типів, залежно від льотних характеристик НД і відстані. Необхідно визначити борт, на якому буде виконана певна ланцюжок. Приклад рiшення данно;1 задачi для обласних центрiв Укра;1ни можно подивитись на Малюнку 2.

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

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

4.2.1 математична модель підзадачі формування ланцюжків рейсів[6]

У моделі використовуються такі змінні і безлічі:

кількість наявних у розпорядження літаків типу f

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

K – безліч типів літаків авіапарку, індекс f.

Необхідно знайти таке рішення x, f, I (вектор розподілу НД по рейсах), при якому лінійна функція мети при умовах і обмеженнях буде максимальна.

Обмеження:

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

де

L: безліч рейсів з індексом i ∈ L.

Умови парк об'єктів – кількість tsepochek на kotorиe призначений dannogo типу повітряного судна НЕ Dolj prevoshodity кількостях imeyushtihsya Літаків dannogo типів:

де

наявну кількість ПС типу

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

де

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/.../.