ДонНТУ
Портал магістрів

Реферат

Тема: Підсистема оптимізації розкладу руху транспорту в залежності від пасажиропотоку

Зміст

1. Введення
2. Актуальність роботи та плановані практичні результати
3. Цілі і завдання, що повинні вирішуватися
4. Аналіз існуючих методів моделювання
5. Математична постановка задачі
6. Системи масового обслуговування з неоднорідними потоками і спеціалізованими каналами
7. Експериментальні дослідження
8. Висновок
9. Література
10. Примітка

Введення

З розвитком інформатики та інформаційних технологій вони почали проникати і розширювати інтереси у все більш широкі сфери людської діяльності. Можливості обмежувалися розвитком ЕОМ і застосуванням методів моделювання при вирішенні задач різного типу.

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

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

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

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

Актуальність роботи та плановані практичні результати

За останній час в самих різних областях практики виникла необхідність у вирішенні різних імовірнісних задач. Прикладами таких завдань можуть служити: перевезення пасажирів, ремонтні майстерні, квиткові каси, стоянки таксі, перукарні і т.п.

У зв’язку з великим пасажиропотоком з’являється проблема розрахунку оптимального розкладу руху транспорту по маршруту, щоб її усунути пропонується змоделювати перевезення пасажирів.

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

В результаті роботи планується отримати оптимальний розклад руху транспорту.

Цілі і завдання, що повинні вирішуватися

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

Для досягнення поставленої мети необхідно вирішити основні завдання:

  1. Дослідити пасажиропотік для визначення методу моделювання.
  2. Провести порівняльний аналіз методів моделювання.
  3. Розробити алгоритм.
  4. Розробити підсистему дозволяє моделювати перевезення пасажирів.
  5. Провести тестування ефективності розробленої підсистеми.

Аналіз існуючих методів моделювання

Процес моделювання – це процес переходу з реального області у віртуальну, за допомогою формалізації, далі відбувається само моделювання, після цього інтерпретація, тобто зворотний перехід від віртуальної області до реальної.

У самому простому випадку процес моделювання виглядає так:

Малюнок 1 – Процес моделювання

Кожен з методів має свої ознаками, тому їх можна розділити за багатьма ознаками.

Одним з перших ознак класифікації можна вибрати ступінь повноти моделі і розділити моделі на:

Залежно від характеру досліджуваних процесів у системі всі види моделювання можуть бути розділені на:

Залежно від уявлення об’єкта можна виділити такі види моделювання:

Серед можливих моделей найбільш придатною є імітаційне моделювання, а саме моделювання систем масового обслуговування (СМО).

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

Існуючі методи моделювання СМО можна розділити за кількома критеріями:

  1. за структурою:

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

    • багатоканальні – багатоканальної називається система, у якій одна загальна черга, а каналів для обслуговування кілька, отже даний тип моделі найбільш підходящий для реалізації, т до одиниць техніки обслуговують пасажирів в більшості випадків більше однієї. Якщо буде використовуватися тільки одна одиниця транспорту, то досить задати потрібні параметри моделі;

    • багатофазні – система, в якій канали обслуговування розташовані послідовно і виконують різні операції обслуговування. Не підходить для реалізації моделі, т до заявки обробляються тільки один раз на одному з каналів;

    • однофазні – однорідні системи, що виконують одну і ту ж операцію обслуговування, даний тип найбільш підходить для реалізації СМО, тому що модель виконує одну і ту ж операції, тобто перевезення пасажирів;

    • замкнуті – система масового обслуговування, в якій обслужених вимоги можуть повертатися в систему і знову надходити на обслуговування;

    • розімкнуті – це СМО в яких характеристики потоку заявок не залежать від того, в якому стані сама СМО.

  2. по допустимому часу очікування заявок в черзі:
    • система без відмов;
    • система з обмеженим очікуванням;
    • система без очікування.

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

  3. з дисципліни вибору черги:
    • заявки вибираються з черги в порядку надходження;

      Параметри заявок, що стоять в черзі зсуваються як зображено на мал. 3

    • заявки вибираються з черги у випадковому порядку. Якщо всі заявки рівноправні, то ймовірність вибору будь-якої з них буде дорівнює 1/к. Сам вибір – це моделювання повної групи подій. Видалення параметрів заявки з черги може здійснюватися як у другому випадку, а може як в основному алгоритмі;
    • заявки вибираються за мінімальним часом очікування. Необхідно при постановці заявки в чергу запам’ятати момент можливої відмови, а при виборі заявки з черги знайти відповідний момент з мінімальним значенням. Видалення заявки і зрушення параметрів здійснюється аналогічно попередньому пункту, але цикл починається з номера вибраної заявки;
    • вибір за пріоритетом. При постановці заявки в чергу необхідно по заданому в умові правилом сформувати пріоритет надійшла заявки і запам’ятати його. При виборі заявки проглядається масив пріоритетів і вибирається заявка з найбільшим пріоритетом. Видалення параметрів заявки з черги здійснюється як у другому випадку.

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

  4. за способом вибору каналу:
    • по мінімальному часу звільнення;
    • у випадковому порядку;
    • за пріоритетом.

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

Малюнок 3 – Вибір заявки в порядку надходження

Математична постановка задачі

Таблиця 1. Опис підсистеми

Підсистема Заявки Канали
Перевезення пасажирів Пасажири Транспорт (автобуси)

При моделюванні перевезення пасажирів можна організувати алгоритм, укрупнений вид якого представлений нижче.

Малюнок 4 – Блок-схема алгоритму

Модель повинна приймати такі параметри:

Модель розробляється і реалізується з метою оцінити певні показники якості, вони є вихідними значеннями моделі.

Вихідні значення моделі наступні:

Системи масового обслуговування з неоднорідними потоками і спеціалізованими каналами

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

Для моделювання неоднорідних потоків системи можна розділити на три класи.

  1. Cистема має один або кілька каналів, і на всіх каналах можна обстежити будь-який тип заявки. Моделювання таких систем не викликає труднощів і виконується як одне або багатоканальної системи з урахуванням різних параметрів обслуговується заявки;
  2. У системи для кожного типу заявки є окремий канал (один або декілька) зображені на мал. 5. Моделювання таких систем виконується так само, як і для однорідних потоків, але по-перше, необхідно передбачити роздільник заявок відповідно до типами і передбачити те, що ці заявки можуть обстежитися як кожна в своєму каналі;
  3. Системи, в яких типи заявок та номери каналів переплелися зображені на мал. 6. При моделюванні таких систем необхідно передбачити розподіл потоків заявок по відповідних каналах. Один з варіантів розподілу цих потоків передбачає створення масиву відповідних параметрів.

Малюнок 5 – У кожної заявки окремий канал

Малюнок 6 – Типи заявок та номери каналів переплелися

(анімація: 5 кадрів, 6 циклів повтору, 32 кілобайт)

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

Експериментальні дослідження

Підсистема реалізована в середовищі Microsoft Visual Studio 2010 на мові C#. При проведенні експериментів підсистема показала допустиме відхилення від реальних даних, достатній для вирішення поставленого завдання.

Висновок

Був проведений аналіз різних методів моделювання. Основними недоліками більшості методів є:

  1. Обмеження алгоритму моделі приводило до неповного моделювання перевезення пасажирів.
  2. Неможливість моделювати поставлену задачу.

Алгоритм з неоднорідними потоками і спеціалізованими каналами позбавлений цих недоліків і повністю підходить для вирішення поставленого завдання.

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

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

Литература

  1. Светличная В.А. Моделирование систем. [Текст] В.А. Светличная 2009. – 36 c.
  2. Stratum. Моделируй свою реальность. – 1998–2011. – [Электронный ресурс]. – Режим доступа: http://stratum.ac.ru/textbooks/modelir/lection30.html.
  3. Элементы теории массового обслуживания. – 1998–2011. – [Электронный ресурс]. – Режим доступа: http://edu.dvgups.ru/METDOC/EKMEN/ETR/WEBUMK/frame/4.htm.
  4. Советов Б.Я.. Яковлев С.А. «Моделирование систем» [Текст] Б.Я. Советов, С.А. Яковлев. Учебное пособие 3-е юд., перераб. и доп. 2001.
  5. Бусленко Н. П.. Моделирование сложных систем. М.: Наука, 1978, 400 с.
  6. Лоу Аверил М., Кельтн В. Девид «Имитационное моделирование» [Текст] М. Лоу Аверил, В. Девид Кельтн. Питер, Издат.группа BHV 2004 – 848 с.
  7. Поляк, Ю. Г. Вероятностное моделирование на ЭВМ [Текст] / Ю.Г. Поляк. – М. : Сов. Радио, 1971. – 400 с.
  8. Лекции по моделированию систем – 2009–2011. – [Электронный ресурс]. – Режим доступа: http://www.studfiles.ru/dir/cat32/subj1235/file11058/view112484/page1.html.
  9. Математические методы моделирования экономических систем [Текст] Бережная Е.В., Бережной В.И. 2-е изд., перераб. и доп. – М.: Финансы и статистика, 2006. – 432 с.
  10. Методы математического моделирования: Учебное пособие [Текст] Умнов А.Е. 3-е издание, испр. и доп – М.: МФТИ, 2012 – 295 с.

Примітка

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