автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.14, диссертация на тему:Алгоритмизация управления потоками транспортных объектов на основе интеграции средств имитационного моделирования

:Л

* «Л^

На правах рукописи

Оче ретов Дмшрин Владимирович

АЛГОРИТМИЗАЦИЯ УПРАВЛЕНИЯ ПОТОКАМИ ТРАНСПОРТНЫХ ОБЪЕКТОВ НА ОСНОВЕ ИНТЕГРАЦИИ СРЕДСТВ ИМИТАЦИОННОГО МОДЕЛИРОВАНИЯ

Специальность 05.13. ¡4. - Системы о5рабо1ки информации к у^ъдвлеьия

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

Воронеж

1998

Работа выполнена в Воронежском государственном техническом университете

Научный руководитель: д-р техн. наук, проф. Бурковский B.JI.

Официальные оппоненты: д-р техн. наук, проф. Бухарин C.B.,

канд. техн. наук Кулаков A.B.

Ведущая организация: АО НПК(о) "Энергия" (г. Воронеж)

Защита диссертации состоится 19 ноября 1998 г. в 10 часов в конференц-зале на заседании диссертационного совета К063.81.04 при Воронежском государственном техническом университете по адресу: 394026 г. Воронеж, Московский проспект, 14.

С диссертацией можно ознакомиться в библиотеке Воронежского государственного технического университета

Автореферат разослан " lê> " Olirl/3-i1998 г.

Ученый секретарь диссертационного совета

Бурковский В.Л.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

Таким образом, актуальность темы диссер1 аиионной рг-.Зс-ть; > «^диктована необходимостью повышения качества обслуживания л^'са.-. яропс-токов в рамках информационно-управляющей системы маршруте» транспортной сети за счет использования специальных средств имитационного моделирования и алгоритмических средств азтематизаш-.и уиреь-ления потоками транспортных объектов

Тематика диссертационной работы связана с реализацией разделов НИР, выполненных по гранту "Разработка «митпциопттх соед< га умаления потоками транспортных объектов", и соответствус. ::ауч»с.и> направлению ВГ'ГУ "САПР я системы автоматизации произвс/дстьа"'.

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

Исходя из этой цели, в работе решались следующие основные задачи:

• определение структуры и состава информационно-управляющей системы управления потоками транспортных объектов, а также средств алгоритмического и программного обеспечения;

• построение и исследование объектно-ориентированной имитационной модели потоков транспортных объектов;

• разработка алгоритмов автоматизации управления потоками транспортных объектов для решения следующих задач: 1) определение потребности транспортного ресурса; 2) перераспределение транспортного ресурса между маршрутами сети; 3) формирование экспресс и укороченных маршрутов; 4) оперативная маршрутизация в условиях сбойных ситуаций; 5) оперативное перераспределение пассажиропотоков;

• создание специального программного обеспечения системы управления потоками транспортных объектов, в рамках которого интегрированы объектно-ориентированная имитационная модель и алгоритмические средства решения задач автоматизации управления потоками транспортных объектов.

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

Научная новизна основных результатов диссертационной работы:

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

• Предложен способ формализованного описания процессов обслуживания пассажиропотоков, реализующий математические средства теории массового обслуживания и позволяющий воспроизвести сложную стратегию функционирования компонентов объекта управления.

• Осуществлена алгоритмизация процедур моделирования в рамках объектно-ориентированной имитационной модели потоков транспортных объектов, позволяющая реализовать оперативную адаптацию модели к изменяющимся условиям объекта управления.

• Разработан комплекс алгоритмических средств решения задач автоматизации управления потоками транспортных объектов.

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

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

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

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

Реализация и внедрение результатов работы. Осноздмг лне-'v--чес кие и практические результаты работы реализованы г. .силе сг.„ (дальнего программного обеспечения, интегрированного ч рамкач кочпямся ipo-граммных средств автоматизированной системы диспетчер;:-ore v.ipwe-ния городским пассажирским транспортом г.Вороисжа. Ожизаг»'*.4. ' еловой экономический эффект от внедрения результатов диссертапгочой работы в рамках трех маршрутов городского пассажирского трансг-.ч-га составляет сто двадцать тысяч рублей в ценах мая 1998г. Эффект дос~>;гаегс>' за счет рационального использования транспортного ресурса и повышен.н уровня транспортного обслуживания пассажиров.

Апробация работы. Основные результаты докладывались а обсуждались на X научно-технической отраслевой конференции "Сес • .«»»«с • пути повышения надежности видеомагнитофонов" (Воронеж, ! W>\ !i Республиканской электронной научной конференции "Современные проблемы информатизации" (Воронеж, 1997), Всероссийском совещании-семинаре "Математическое обеспечение информационных технологий ч технике, образовании и медицине" (Воронеж, 1998), Ш Международно»'' электронной научной конференции "Современные проблемы »'кформати-зации" (Воронеж, ¡998).

Публикации. По результатам исследований опубликован-"1 11 леча!-ных работ.

Структура и объем работы. Диссертационная работа состоит из введения, пяти глав, заключения, списка литературы из 131 наименования

и содержит 119 страниц машинописного текста, 22 рисунка, 3 таблицы и приложения на 15 страницах.

СОДЕРЖАНИЕ РАБОТЫ

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

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

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

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

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

-

Моделирование: 1) является хорошим способом накопления обширной информации о характеристиках транспортной системы; 2) позволяет определить, какие переменные являются важными и каким образом они воздействуют, в конечном счете это може! привести ic übt году тна-щп'ч--ских выражений (при моделировании можно использовать различные терии оптимизации), 3) дешевле многих других экспериментов, 4) лает интуитивное представление об исследуемой транспортной системе; 5) обеспечивает контроль над временем, позвал."* сзгичзть и растягивать руемый транспортный процесс по сравнению с реальным процессом; 6) является безопасным способом исследования.

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

Анализ вопросов, связанных с проблемами автоматизации управления потоками транспортных объектов, а также теоретических и практических наработок по данной теме позволил определить ряд задач оперативного управления, не получивших достаточного рассмотрение я [Мые.:.1 с позиции их алгоритмизации.

Дана характеристика технического и программного обечис ;ен действующих промышленных систем лвтоматизирочачного унра-зл» m« транспортными сетями.

На основании проведенных исследований сформулирован*i cVrfc требования к разработке математического и программного оосспсч;«« ' средств имитационного моделирования и алгоритмязгшш /рровг.гчь • гг-токами транспортных объектов.

Вторая глава посвящена вопросам обоснования рь-юра eruyi;;\: i информационно-управляющей системы управления потоками транспортных объектов применительно к маритрутяой сети.

С помощью системы управленат потоками транспорта?,:* о," ..s "" становится возможным гибко управлять транспортным ресурсом на маршрутах, получать и обрабатывать большое количество информации об условиях движения: пиковых нагрузках и перевозках пассажиров, критических потоках на транспортных сетях, заторах и сбоях я движении ;гх причинах и др.

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

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

Рис.1. Структура интегрированной информационно-управляющей системы транспортной маршрутной сети

Разграничение в составе специального программного обеспечения (ПО) аппарата имитационного моделирования и алгоритмических средств

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

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

Имитационная модель моделирует движение транспортных единиц (ТЕ) по маршрутам сети и процесс перевозки пассажиров; она состоит кз набора функциональных блоков, каждый из которых ориентирован на выполнение определенной процедуры, что существенно упрощает формирование вариантов модели. Функциональные блоки реализую с^Тсучико процесс моделирования, имитируя движение ТЕ, их ъирузьу ьз т.с • вечных пушаах, посадку пассажиров в ТЕ, и обрабатывает ге.; ■ з;:' моделирования. Выбор ТЕ, которая будет моделироваться, опрг-гд "г минимизацией времени подхода всех ТЕ к их очередным остп.чс>-¿ч»: пунктам. Это минимальное времч принимается за очередное рр!'рап:*ы значения текущего времени моделирования. Информ?ция о т-'сс.г^иго^о-токах используется в виде матрицы корреспонденция по лархрут? < о? г

Информационную компоненту имитационной модели с>»л<ч.;»еО!.

1) структура сети У = {5,£>,/?}, где ¿" - множество сстансгочн-.г-' пунктов, О - множество возможных перемещений транспортных единиц, К - множество всех маршруток транспортной сети;

2) матрицы корреспонденции описывают количестве;,.;..:г- \: рактерисники пассажиропотоков в рамках каждого маршрута транспортной сети

Ипа- Л2а— \аа !!

|!., - .1

Г

Иу„. \а-Луа 2 £?•••■ А\'аЛ'агг'!

где Хца- интенсивность поступления пассажиропотоков с гелия, зочно-п пункта с номером г на остановочный пункт с номером } в рамках маршрута а; Ыа- количество остановочных пунктов маршрута а;

3) транспортный ресурс В = где N - общее количе-

ство транспортных единиц транспортной сети.

Рис.2. Обобщенная информационная структура объектно-ориентированной имитационной модели потоков транспортных объектов

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

___________________О------------

Рис.3. Структурная схема взаимодействия модулей функциональной компоненты объектно-ориентированной имитационной модели потоков транспортных объектов

Приведено назначение и -математическое описание всех модулей функциональной компоненты объектно-ориентированной имитационной модели потоков транспортных объектов.

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

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

Предлагаемые алгоритмические средства позволяют решить следующие задачи оперативного управления потоками транспортных объектов: 1) определение потребности транспортного ресурса; 2) перераспределение транспортного ресурса между маршрутами сети; 3) формирование экспресс и укороченных маршрутов; 4) оперативная маршрутизация в ус-

ловиях сбойных ситуаций; 5) оперативное перераспределение пассажиропотоков.

Задачи определения потребности транспортного ресурса, перераспределения транспортного ресурса между маршрутами сети, формирования экспресс и укороченных маршрутов относятся к классу задач нелинейного программирования с нечетко выраженной целевой функцией. В качестве основных оценочных критериев качества предлагаемых решений выступают: 1) минимизация числа отказов в обслуживании; 2) минимизация числа пустых прогонов ТЕ.

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

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

Задача формирования экспресс и укороченных .маршрутов возникает в том случае, когда определены маршруты транспортной сети а = 1,£, матрицы корреспонденции каждого маршрута Ла = |/1уа |, транспортный ресурс Ма и требуется сформировать новый маршрут в рамках уже существующего маршрута а транспортной сети для обеспечения более качественного обслуживания пассажиропотоков, не прибегая к потребностям дополнительного транспортного ресурса, за счет учета значительного разброса суммарных интенсивностей пассажиропотоков, поступающих на остановочные пункты маршрута транспортной сети. Предлагаемое решение данной задачи позволяет на основании множества Па ~ {1,2,..., }, которое определяет остановочные пункты маршрута а с учетом внутренней нумерации, определить подмножество сО„, в которое войдут номера остановочных пунктов формируемого экспресс или укороченного маршрута, а также количество ТЕ М* для обслуживания нового маршрута из общего числа ТЕ Ма, задействованных на маршруте а.

Задача оперативной маршрутизации возникает при наличии сбоев в транспортной сети, связанных с невозможностью нормального функционирования действующих маршрутов вследствие блокировки возможного пути перемещения транспортной единицы между двумя и более остановочными пунктами (затор на дороге, ремонтные работы отрезка пути). В данной ситуации возникает необходимость в формировании нового маршрута, в состав которого могут входить как остановочные пункты временно блокируемых маршрутов, так и не относящиеся к последним. Транспортная сеть представляется в виде графа 0 = (5,£>), где 5- множество вершин графа, соответствующее остановочным пунктам; Г) -множество ребер графа, соответствующее возможным путям перемещения ТЕ между остановочными пунктами. Решение данной задачи базируется на использовании модифицированного алгоритма ДеЙкстры, осуществляющего поиск множества возможных путей между двумя вершинами графа. Выбор конкретного варианта решения осуществляется на основании условий: 1) отсутствия внутренних циклов в формируемом маршруте; 2) минимальная протяженность варианта соединения.

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

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

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

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

Особенности проектирования и использования АРМ диспетчера системы управления потоками транспортных объектов на городских террито-

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

В качестве инструментальных средств проектирования и разработки специального программного обеспечения системы управления потоками транспортных объектов был использован пакет Borland C++Builder 3.0 Client / Server Suite, уникальным образом сочетающий высокопроизводительный компилятор, объектно-ориентированные средства визуального программирования и универсальный механизм доступа, как к локальным, так и удаленным базам данных.

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

Для организации доступа к локальным и удаленным базам данных со стороны специального программного обеспечения системы управления потоками транспортных объектов используются стандартные средства, интегрированные в пакет Borland C++Builder 3.0 Client / Server Suite. Использование готовых решений позволяет с одной стороны сэкономить время, необходимое на разработку, а с другой - существенно упростить структуру, разрабатываемого программного обеспечения.

BDE предоставляет единый набор функций (API - Application Program Interface) обработки локальных и серверных данных. Обращение к различным источникам данных основано на концепции драйверов. Таким образом, обеспечивается интерфейс к наиболее распространенным форматам/способам хранения данных:. dBase, Paradox и серверным источникам InterBase, Oracle, Sybase, Informix, MS SQL-Server, DB/2. В силу того, что достаточное количество данных имеет ODBC-интерфейс, BDE предоставляет для доступа к ним так называемый ODBC Socket, построенный на технологии Idapter, разработанной Borland.

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

ровлнкой системы диспетчерского управления городским пассажирским транспортом.

Практическая реализация инструментальных средств, ориентированных на IBM-совместимые ЭВМ. интегрированных в рамках АРМ диспетчера маршрутной сети городского пассажирского транспорта (ГПТ), позволяет на основе комплексного имитационного моделирования оперативно решать следующие задачи:

» определение потребности транспортного ресурса;

» перераспределение транспортного ресурса между маршрутами сети;

• формирование экспресс и укороченных маршрутов;

• оперативная маршрутизация;

• оперативное перераспределение пассажиропотоков;

• визуализация процессов моделирования и принятия решений.

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

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

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

В таб. 1 представлены сравнительные данные результатов имитационного моделирования различных режимов обслуживания пассажиропотоков транспортной сети. Результаты имитационного моделирования свидетельствуют о высокой эффективности' разработанных алгоритмических средств автоматизации управления потоками транспортных объектов." Отмечается общее повышение качества функционирования транспортной системы за счет уменьшения числа отказов в обслуживании, уменьшения среднего времени ожидания ТЕ, увеличения загруженности ТЕ и экономии транспортного ресурса при организации комбинированных режимов обслуживания пассажиропотоков. > Out-"-!!'

Таблица 1.

Сравнительные характеристики различных режимов обслуживания в

процентах от традиционного режима обслуживания

Режим Среднее Среднее вре- Средняя за- Количество

обслуживания число отка- мя ожидания гружен- ТЕ, необхо-

зов в об- ТЕ ность ТЕ димых для

служивании обслуживания

Традицион- 1 1 1 1

ный

После перераспределения 0.4 0.96 1.08 1

транспортного

ресурса

Комбинированный с экс- 0.63 0.98 1.11 0.85

пресс обслу-

живанием

Комбинированный с уко- 0.68 0.95 1.11 0.92

роченным

рейсом

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

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

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

' 3. Предложен способ формального описание процесса обслуживания пассажиропотоков в терминах теории массового обслуживания и обобщенном математическом определении объекта управления.

4. Разработана объектно-ориентированная имитационная модель потоков транспортных объектов, позволяющая осуществлять моделирование

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

5. Разработаны алгоритмы автоматизации управления потоками транспортных объектов для решения следующих задач: !) определение потребности транспортного ресурса; 2) перераспределение транспортного ресурса между маршрутами сети; 3) формирование экспресс и укороченных маршрутов; 4) оперативная маршрутизация в условиях сбойных ситуаций; 5) оперативное перераспределение пассажиропотоков.

6. На сновании предложенных модели и алгоритмов разработано специальное программное обеспечение системы управления потоками транспортных объектов, в рамках которого интегрированы объектно-ориентированная имитационная модель, алгоритмические средства решения задач автоматизации управления потоками транспортных объектов и средства доступа к локальным и удаленным базам данных.

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

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Очеретов Д.В., Бурковский B.JI. Алгоритмы решения задачи рационального выбора технологических маршрутов // Состояние и пути повышения надежности видеомагнитофонов: Тез. докл. X науч.-техн. отрасл. конф.- Воронеж, 1996. С.16.

2. Бурковский B.J1, Очеретов Д.В. Структура математического обеспечения АРМ диспетчера маршрутной сети городского пассажирского транспорта // "Математическое обеспечение информационных технологий в технике, образовании и медицине". - Воронеж, 1996. С.42. '

3. Очеретов Д.В. Оптимизационные модели' перераспределения' транспортного ресурса // "Математическое обеспечение информационных техноло! ий в технике, образовании и медицине". - Воронеж , 1996. С.45.

4. Очеретов Д.В. Алгоритмическое обеспечение АРМ диспетчера маршрутной сети городского пассажирского транспорта // Тез. докл. II Республиканской электронной научной конференции: "Современные проблемы информатизации".- Воронеж: Изд-во Воронежского педуниверсите-та, 1997. С.86-87.

5. Очеретов Д.В., Бурковский B.JI Пользовательский интерфейс системы управления потоками транспортных объектов // Тез. докл. II Республиканской электронной научной конференции: "Современные проблемы информатизации",- Воронеж: Изд-во Воронежского педуниверситета, 1997. С.101-102.

6. Очеретов Д.В., Бурковский В.Л. Задача перераспределения пассажиропотоков сети маршрутов городского пассажирского транспорта // Всероссийское совещание-семинар: "Математическое обеспечение информационных технологий в технике, образовании и медицине". Часть 2.- Воронеж, 1997. С.83.

7. Очеретов Д.В., Бурковский В.Л Оптимальное перераспределение транспортного ресурса при комбинированных режимах функционирования маршрутов городского пассажирского транспорта И Всероссийское совещание-семинар: "Математическое обеспечение информационных технологий в технике, образовании и медицине". Часть 2,- Воронеж, 1997. С.82.

8. Очеретов Д.В., Бурковский В.Л. Задача оперативной маршрутизации сети маршрутов городского пассажирского транспорта в условиях сбойных ситуаций // Тез. докл. III Международной электронной научной конференции: "Современные проблемы информатизации",- Воронеж: Изд-во Воронежского педуниверситета, 1997. С.123-124.

9. Очеретов Д.В. Особенности алгоритмического обеспечения процесса управления системой транспортных маршрутов // Тез. докл. III Международной электронной научной конференции: "Современные проблемы информатизации",- ■ Воронеж: Изд-во Воронежского педуниверситета, 1997. С.108-109.

10. Бурковский В.Л, Очеретов Д.В. Модель маршрутной сети городского пассажирского транспорта // Высокие технологии в технике, медицине и образовании: Межвуз. сб. науч. тр.- Воронеж, 1997. С.151-155.

11. Очеретов Д.В., Бурковский В.Л. Особенности алгоритмизации задачи оперативной маршрутизации сети маршрутов ГПТ в условиях сбойных ситуация // Системы управления и информационные технологии: Межвуз. сб. науч. тр.- Воронеж, 1998. С. 142-145.

/г I ' ' / { / >

, - - ; / Л л,- / I. . ■ /

/

воронежский государственный технический

университет

На правах рукописи

Очеретов Дмитрий Владимирович

АЛГОРИТМИЗАЦИЯ УПРАВЛЕНИЯ ПОТОКАМИ ТРАНСПОРТНЫХ ОБЪЕКТОВ НА ОСНОВЕ ИНТЕГРАЦИИ СРЕДСТВ ИМИТАЦИОННОГО

МОДЕЛИРОВАНИЯ

Специальность 05.13.14 - Системы обработки информации и управления

ДИССЕРТАЦИЯ на соискание ученой степени кандидата технических наук

Научный руководитель: доктор технических наук, профессор В.Л. Бурковский

Воронеж - 1998

СОДЕРЖАНИЕ

Введение 4

Глава 1. Анализ математических методов и моделей систем управления потоками транспортных объектов 10

1.1. Общая проблематика вопросов управления потоками транспортных объектов 10

1.2. Модели и алгоритмы анализа и управления элементами маршрутной сети 14

1.3. Средства программного и аппаратного обеспечения промышленных систем управления транспортом 20

Выводы 23

Глава 2. Система управления потоками транспортных объектов 25

2.1. Структура и состав системы 25

2.2. Информационное взаимодействие основных функциональных компонент системы 29

2.3. АРМ диспетчера системы управления потоками транспортных объектов 32

Выводы 35

Глава 3. Объектно-ориентированная имитационная модель потоков транспортных объектов 36

3.1. Структура и состав объектно-ориентированной имитационной модели потоков транспортных объектов 36

3.2. Математическое описание элементов функциональной компоненты объектно-ориентированной имитационной модели потоков транспортных объектов 44

Выводы 59

Глава 4. Алгоритмические средства автоматизации управления потоками транспортных объектов 61

4.1. Определение потребности транспортного ресурса 61

4.2. Перераспределение транспортного ресурса между маршрутами

сети 66

4.3. Формирование экспресс и укороченных маршрутов 72

4.4. Оперативная маршрутизация 7 9

4.5. Оперативное перераспределение пассажиропотоков 85 Выводы 91 Глава 5. Специальное программное обеспечение системы управления потоками транспортных объектов и результаты практической апробации 92

5.1. Структура специального программного обеспечения и функциональное назначение его отдельных компонент 92

5.2. Средства и методы доступа к локальным и удаленным базам данных 97

5.3. Некоторые результаты практической апробации элементов специального программного обеспечения 102

Выводы 105

Заключение 107

Литература 109

Приложения 120

ВВЕДЕНИЕ

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

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

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

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

Тематика диссертационной работы связана с реализацией разделов, НИР, выполненных по гранту "Разработка имитационных средств управления потоками транспортных объектов", и соответствует научному направлению ВГТУ "САПР и системы автоматизации производства".

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

Исходя из этой цели, в работе решались следующие основные задачи:

• определение структуры и состава информационно-управляющей системы управления потоками транспортных объектов, а также средств алгоритмического и программного обеспечения;

• построение и исследование объектно-ориентированной имитационной модели потоков транспортных объектов;

• разработка алгоритмов автоматизации управления потоками транспортных объектов для решения следующих задач: 1) определение потребности транспортного ресурса; 2) перераспределение транспортного ресурса между маршрутами сети; 3) формирование экспресс и укороченных маршрутов; 4) оперативная маршрутизация в условиях сбойных ситуаций; 5) оперативное перераспределение пассажиропотоков;

• создание специального программного обеспечения системы управления потоками транспортных объектов, в рамках которого интегрированы объектно-ориентированная имитационная модель и алгоритмические средства решения задач автоматизации управления потоками транспортных объектов.

Методы исследования основаны на использовании теории имитационного моделирования, теории массового обслуживания, теории графов, тео-

рии множеств, математической статистики, вычислительной математике, объектно-ориентированного программирования, компьютерных технологий.

Научная новизна основных результатов диссертационной работы:

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

• Предложен способ формализованного описания процессов обслуживания пассажиропотоков, реализующий математические средства теории массового обслуживания и позволяющий воспроизвести сложную стратегию функционирования компонентов объекта управления.

• Осуществлена алгоритмизация процедур моделирования в рамках объектно-ориентированной имитационной модели потоков транспортных объектов, позволяющая реализовать оперативную адаптацию модели к изменяющимся условиям объекта управления.

• Разработан комплекс алгоритмических средств решения задач автоматизации управления потоками транспортных объектов.

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

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

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

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

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

Апробация работы. Основные результаты докладывались и обсуждались на X научно-технической отраслевой конференции "Состояние и пути повышения надежности видеомагнитофонов" (Воронеж, 1996), II Республиканской электронной научной конференции "Современные проблемы информатизации" (Воронеж, 1997), Всероссийском совещании-семинаре "Математическое обеспечение информационных технологий в технике, образовании и медицине" (Воронеж, 1998 ), III Международной электронной научной конференции "Современные проблемы информатизации" (Воронеж, 1998).

Публикации. По результатам исследований опубликовано 11 печатных работ.

Структура и объем работы. Диссертационная работа состоит из введения, пяти глав, заключения, списка литературы из 131 наименования и содержит 119 страниц машинописного текста, 22 рисунка, 3 таблицы и приложения на 15 страницах.

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

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

В третьей главе рассмотрена структура и состав объектно-ориентированной имитационной модели потоков транспортных объектов. Дано математическое описание элементов функциональной компоненты имитационной модели. Произведена теоретическая оценка сложности модели. Разработано формализованное описание процесса обслуживания пассажиропотоков в терминах теории массового обслуживания и обобщенном математическом определении объекта управления.

В четвертой главе приведено обоснование, анализ и описание алгоритмов решения следующих задач автоматизации управления потоками транспортных объектов: 1) определение потребности транспортного ресурса, обеспечивающего требуемый уровень обслуживания пассажиропотоков; 2) перераспределение транспортного ресурса между маршрутами сети; 3) формирование экспресс и укороченных маршрутов; 4) оперативная маршрутизация в

условиях сбойных ситуаций; 5) оперативное перераспределение пассажира-потоков.

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

В заключении формируются основные научные и практические результаты диссертационного исследования.

Прилагается список используемых литературных источников.

ГЛАВА 1. АНАЛИЗ МАТЕМАТИЧЕСКИХ МЕТОДОВ И МОДЕЛЕЙ СИСТЕМ УПРАВЛЕНИЯ ПОТОКАМИ ТРАНСПОРТНЫХ ОБЪЕКТОВ

1.1. Общая проблематика вопросов управления потоками транспортных объектов

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

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

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

Исключительная сложность данной задачи обусловлена многофункциональным и многоуровневым характером транспортных систем, децентрализацией планирования и управления, динамическим и вероятностным характером изучаемых процессов, активностью объекта управления, которая требует учета многочисленных психологических и социально-экономических факторов [2, 15, 16].

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

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

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

ние результатов трудно-сопоставимыми; разработанные модели часто информационно несовместимы, что затрудняет их стыковку и повторное использование. Кроме того, имеется терминологический разнобой и дублирование экспериментальных и теоретических разработок [15, 27].

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

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