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

Реферат

Тема: Подсистема оптимизации расписания движения транспорта в зависимости от пассажиропотока

Содержание

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

Введение

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

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

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

Существующие или проектируемые системы можно эффективно исследовать с помощью математических моделей (аналитических и имитационных), реализуемых на современных ЭВМ.

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

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

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

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

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

В результате работы планируется получить оптимальное расписание движения транспорта.

Цели и задачи, которые должны решаться

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

Для достижения поставленной цели необходимо решить основные задачи:

  1. Исследовать пассажиропоток для определения метода моделирования.
  2. Провести сравнительный анализ методов моделирования.
  3. Разработать алгоритм.
  4. Разработать подсистему позволяющую моделировать перевозку пассажиров.
  5. Провести тестирование эффективности разработанной подсистемы.

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

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

В самом простом случае процесс моделирования выглядит так:

Рисунок 1 – Процесс моделирования

Каждый из методов обладает своими признаками, поэтому их можно разделить по многим признакам.

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

В зависимости от характера изучаемых процессов в системе все виды моделирования могут быть разделены на:

В зависимости от представления обьекта можно выделить такие виды моделирования:

Рисунок 2 – Классификация моделирования систем

Среди возможных моделей наиболее подходящей является имитационное моделирование, а именно моделирование систем массового обслуживания (СМО).

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

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

  1. по структуре:

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

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

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

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

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

    • разомкнутые – это СМО в которых характеристики потока заявок не зависят от того, в каком состоянии сама СМО.

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

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

  3. по дисциплине выбора очереди:
    • заявки выбираются из очереди в порядке поступления. Параметры заявок, стоящих в очереди сдвигаются как показано на рис. 3;
    • заявки выбираются из очереди в случайном порядке. Если все заявки равноправны, то вероятность выбора любой из них будет равна 1/к. Сам выбор – это моделирование полной группы событий. Удаление параметров заявки из очереди может осуществляться как во втором случае, а может как в основном алгоритме;
    • заявки выбираются по минимальному времени ожидания. Необходимо при постановке заявки в очередь запомнить момент возможного отказа, а при выборе заявки из очереди найти соответствующий момент с минимальным значением. Удаление заявки и сдвиг параметров осуществляется аналогично предыдущему пункту, но цикл начинается с номера выбранной заявки;
    • выбор по приоритету. При постановке заявки в очередь необходимо по заданному в условии правилу сформировать приоритет поступившей заявки и запомнить его. При выборе заявки просматривается массив приоритетов и выбирается заявка с наибольшим приоритетом. Удаление параметров заявки из очереди осуществляется как во втором случае.

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

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

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

    Рисунок 3 – Выбор заявки в порядке поступления

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

Таблица 1. Описание подсистемы

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

При моделировании перевозки пассажиров можно организовать алгоритм, укрупнённый вид которого представлен на рис. 4.

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

Модель должна принимать такие параметры:

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

Выходные значения модели следующие:

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

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

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

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

Рисунок 5 – У каждой заявки отдельный канал

Рисунок 6 – Типы заявок и номера каналов переплелись

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

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

Экспериментальные исследования

Подсистема реализована в среде 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. – [Электронный ресурс]. &ndash Режим доступа: http://www.studfiles.ru/dir/cat32/subj1235/file11058/view112484/page1.html.
  9. Математические методы моделирования экономических систем [Текст] Бережная Е.В., Бережной В.И. 2-е изд., перераб. и доп. – М.: Финансы и статистика, 2006. – 432 с.
  10. Методы математического моделирования: Учебное пособие [Текст] Умнов А.Е. 3-е издание, испр. и доп – М.: МФТИ, 2012 – 295 с.

Примечание

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