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

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

СОЛОВЬЕВ Вадим Анатольевич

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

Специальность 05.13.18 - Математическое моделирование, численные методы и комплексы программ

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

28 НОЯ 2013

Тюмень-2013

005540778

005540778

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

СОЛОВЬЕВ Вадим Анатольевич

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

Специальность 05.13.18 - Математическое моделирование, численные методы и комплексы программ

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

Тюмень-2013

Работа выполнена на кафедре «Комплексная защита информации» ФГБОУ ВПО «Омский государственный технический университет»

Научный руководитель: Файзуллин Ра шит Тагирович,

д.т.н., профессор

Официальные оппоненты: Блинков Юрий Анатольевич,

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

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

Ведущая организация: Федеральное государственное бюджетное

образовательное учреждение высшего профессионального образования «Томский государственный университет систем управления и радиоэлектроники»

Защита состоится 25 декабря 2013 года в 14:00 часов на заседании диссертационного совета Д 212.274.14 по защите докторских и кандидатских диссертаций при Тюменском государственном университете по адресу: 625003, г. Тюмень, ул. Перекопская, 15А, ауд. 410.

С диссертацией можно ознакомиться в библиотеке Тюменского государственного университета.

Автореферат разослан 23 ноября 2013 г.

Ученый секретарь

диссертационного совета Е. А. Олейников

к.т.н., доцент

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

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

Математическое моделирование транспортных потоков возникло в 50-е годы XX века. В работах Дж. Лайтхилла , Дж. Уизема1 (1955), П. Ричардса2 (1956) была построена первая макроскопическая модель однополосного транспортного потока, названая впоследствии моделью Лайтхилла-Уизема-Ричардса, в которой поток транспортных средств рассматривается как поток одномерной сжимаемой жидкости. В дальнейшем был предложен ряд модификаций данной модели (модель Танака3 (1963), модель Дж. Уизема4 (1974), модель Дж. Пэйна5 (1971) и другие).

В 1961-м году Ф. Ньюэллом была предложена первая микроскопическая

6

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

' Lighthill М. J., Whitham G. В. On kinanatic waves: II. Theory of traffic flow on long crowded roads // Proceeding of the royal society. London, Ser. A. 1955. V. 229. P. 281-345

2 Richards P. I. Shock Waves on the Highway // Operations Research. 1956. V. 4. P. 42-51

3 Иносэ X., Хамада Т. Управление дорожным движением. М.: Транспорт, 1983.

4 Уизем Дж. Линейные и нелинейные волны. М.: Мир, 1977.

5 Payne Н. J. Models of freeway traffic and control, in: Simulation Council Proc. 28, Mathematical Models of Public Systems. Edited by G. A. Bekey. 1971. V. l.P. 51-61.

6 Newell G. F. Nonlinear effects in the dynamics of car-following // Operations Research. 1961. V. 9. P. 209-229 ' _

скорость движения, зависящая от дистанции до лидера. Другим видом микроскопических моделей, наряду с моделями оптимальной скорости, являются модели следования за лидером789. В 1959 г. Д. Газис, Р. Херман, Р. Поте предложили одну из первых нетривиальных микроскопических моделей однополосного транспортного потока. С помощью этой модели можно определить зависимость между интенсивностью потока транспортных средств и плотностью. Ф. Хейт был первым, кто выделил исследование транспортных потоков в отдельный, самостоятельный раздел математики.

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

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

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

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

7 Traffic flow theory: A state-of-the-art report. Editors N.H. Gartner, C. J.l Messer, A. K. Rathi. Washington DC: Transportation Research Board, 2001.

8 Helbing D. Traffic and related self-driven many particle systems // Reviews of modern physics. 2001. V. 73. No 4. P. 1067-1141

9 Швецов, В. И. Математическое моделирование транспортных потоков / В.И.Швецов // Автоматика и телемеханика. - 2003. - № 11. - С. 3-46.

- разработка математической модели транспортных потоков и вариантов движения транспортных средств (ТС), в зависимости от различных ситуационных моментов;

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

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

г

Результаты, выносимые на защиту, соответствуют следующим трем пунктам паспорта специальности 05.13.18 - Математическое моделирование, численные методы и комплексы программ по техническим наукам:

Пункт 1: Разработка новых математических методов моделирования объектов и явлений.

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

Пункт 4: Реализация эффективных численных методов и алгоритмов в виде комплексов проблемно-ориентированных программ для проведения вычислительного эксперимента.

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

3. Программный комплекс состоит из программы, моделирующей движение транспортных потоков, разработанной с применением параллельных вычислительных технологий, а также программы, визуализирующей транспортные потоки на карте города. Разработанный программный комплекс внесен в Реестр программ для ЭВМ с регистрационным номером № 2013615221.

Пункт 8: Разработка систем компьютерного и имитационного моделирования.

4. Подсистема компьютерного моделирования транспортных потоков, использующая данные, полученные с датчиков ГЛОНАСС.

Научная новизна работы по трем областям специальности 05.13.18 отражена в следующих результатах:

Математическое моделирование

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

Численные методы

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

Комплексы программ

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

Соответствие диссертации паспорту научной специальности. Научные положения диссертации соответствуют формуле специальности 05.13.18 — Математическое моделирование, численные методы и комплексы программ. Результаты проведённого исследования соответствуют областям исследования специальности, конкретно пунктам 1,4, 8 её паспорта.

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

Апробация результатов работы. Основные результаты диссертационной работы докладывались на XIV-й Всероссийской конференции «Математическое программирование и приложения» (Екатеринбург, 28 февраля - 04 марта 2011 г.); международной научной конференции «Параллельные Вычислительные Технологии 2011» (ПаВТ'2011) (Москва, 28 марта - 1 апреля 2011 г.); 11-й региональной молодежной научно-технической конференции «ОМСКИЙ РЕГИОН - МЕСТОРОЖДЕНИЕ ВОЗМОЖНОСТЕЙ» (Омск, 14-17 апреля 2011 г.); международной научной конференции «Параллельные Вычислительные Технологии 2012» (ПаВТ'2012) (Новосибирск, 26 - 30 марта 2012 г.); VIII-й Международной научно-технической конференции «ДИНАМИКА СИСТЕМ, МЕХАНИЗМОВ И МАШИН» (Омск, 13 - 15 ноября 2012 г.)

Публикации. Основные результаты диссертации опубликованы в 10 работах (см. список в конце автореферата), из которых 3 работы - в журналах, рекомендованных ВАК для публикации результатов диссертационной работы. В ходе выполнения научного исследования диссертантом была разработана программа для ЭВМ, которая зарегистрирована в реестре программ для ЭВМ (свидетельство о государственной регистрации программы для ЭВМ № 2013615221). Автором получена справка о включении результатов представляемой диссертационной работы в проект по разработке системы управления светофорами по радиоканалу, осуществляемый ООО НТК «ИНТЕКС».

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

Структура и объем диссертации. Диссертация состоит из введения, трех глав и списка литературы. Объем диссертации составляет 118 страниц. Библиографический список содержит 178 наименований.

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

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

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

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

Топологическая основа модели транспортных потоков строится с применением элементов теории графов и состоит из следующих этапов:

1. Задается ориентированный взвешенный мультиграф б = (V, Е), где V = (V;} - множество вершин (£ = 1,.., ЛУ; Е = {е,} - множество ребер (I = 1,.., Е с V х V, Ыр - количество вершин, Ые - количество ребер.

2. Для каждого ребра выбираются вес ребра соответствующий длине дороги и ориентация движения ТС по ребру.

3. Строится матрица смежности вершин ориентированного графа М5={т$(>у}, где =

4. Формируется список ребер ЕЬ = {е/7} и определяются их длины, где = 1,..,Л/е.

5. Формируется список светофоров ТЬ = где I = 1,..,Ы1!.

Результатом построения топологической основы является матрица смежности МБ, список ребер ЕЬ и список светофоров ТЬ (рис. 1).

Входные параметры

МЭ - матрица смежности; ЕЬ - список ребер; ТЬ - список светофоров; СЬ- список ТС; ДС-начапьный шаг по времени;

Инициализация внутренних переменных

1) Ассоциация входных параметров друг с другом

2) Обнуление различных счетчиков

Подготовка структуры данных для

топологической основы

1) Вычисление и установка таймеров светофоров TL

2) Упорядочивание списка ТС CL

3) Установка пунктов назначения для ТС DCL

4) Вычисление путей следования для ТС PCL

Вывод данных TL, CL, DCL, PCL

Рис. 1. Блок-схема построения топологической основы

В рамках математической модели считаем, что по дороге е/у длиной /у в момент времени £0 движется ТС в координатах х Є [0, со скоростью V Є [О, Ртах], где итах - максимально допустимая скорость для дороги е/;. Шаг дискретизации Лі равен нескольким секундам, х" и V* - координата и скорость в момент времени ґ0 + Ді:. В зависимости от рассматриваемой ситуации шаг дискретизации может изменяться. Скорости ТС и длины ребер выбираются из соображения согласования с реальностью.

Позиционирование ТС осуществляется через задание ребра, на котором находится ТС, и координаты на нем. Следует еще раз отметить, что направление движения определяется ориентацией ребра. Начальный список ТС формируется с привязкой к ребрам, после построения топологической основы. Каждому ребру еі] поставлен в соответствие список ТС

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

При построении модели, принято во внимание, что ТС ускоряется за время 6 « Д£. Это предположение сделано для того, чтобы сохранить порядок движения ТС без уменьшения шага дискретизации Ді и избежать проблем возникающих в рассмотренных классических моделях, т.е., с появлением отрицательных значений скоростей. Таким образом путь, пройденный ТС за один шаг, определяется следующим образом:

х'-Х^У'М. (1)

Рассматривается две модели поведения водителя в ситуациях при различных сигналах светофора на перекрестке, к которому движется ТС.

Первая ситуация соответствует зеленому сигналу светофора. Здесь водитель ограничивается только безопасным расстоянием до движущегося впереди ТС. Пусть по одному ребру движутся два ТС: ТС! и ТС2. Их координаты:

х{ = хг + v{At, (2)

х2 =х2 + v2At. (3)

Считается, что ТС2 стремится к безопасному расстоянию ¿* до ТСХ на следующем шаге:

V = х\ - х\, (4)

где, например,

_ Г 10, если v■í < (.10 + V, если V1

< 5м/с (5)

> 5м/с'

Из (2)-(4) скорость ТС2 будет:

17* = + М - Г - х2)/М. (6)

Вторая ситуация соответствует красному сигналу светофора, когда транспортный поток движется накатом, чтобы потери скорости перед перекрёстком были минимальны. Пусть по одному ребру движутся три ТС: ТС,, ТС2 и ТС3. Их координаты задаются выражениями (2), (3) и:

х'3 =х3 + у*3М. (7)

Положение ТС2 между ТСг и ТС3 определяется выражением:

+ (8) ¿. 2 >

где В* - отклонение ОТ середины между ТС! и ТС3, если В*=0, то ТС2 стремится занять место посередине. Считаем VI и 173 известными, тогда из (2), (3), (7), (8):

VI = (*! + + х3 + vl^t-2x3 + 2В*)/(2ДС). (9)

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

Для первой модели поведения считается, что если ТС! регулирует скорость = У1еайег на свое усмотрение, тогда скорость остальных ТС вычисляется согласно:

= + -¡А- хд/Ы, 0°)

где I = 2,..., И, и N - количество ТС на ребре.

Для второй модели поведения текущие координаты хь скорости уь отклонения от середины В[. Движением будут «управлять» крайние ТС: ТС! и ТСМ. Известными будут VI - у1еайег и Ун = для остальных ТСг решается сис-

тема с N — 2 неизвестными:

г = Уьеайег

2и* - VI = - + х1- 2х2 + х3)

- 2vl1-v^ =^t(2Br_1-v'i_2^t+xi_2-2xi^+xl) , (11)

2v^N-l - ^ - v^N_2At + хы_2 - 2х1Я_1 + хы)

V ^ЛГ =

где I = 2,..., N - 1, и N - количество ТС на ребре.

Блок-схема модуля управления движением транспортных потоков представлена на рисунке 2.

Предварительная оценка сложности вычислений приводит к необходимости повышения производительности, которую можно достичь за счет применения параллельных вычислений при моделировании движения транспортных потоков. Предлагается разделение топологической основы на части, далее «регионы», и их ассоциация с узлами вычислительного кластера. Для разделения графа транспортной сети на части используется алгоритм кластеризации к-средних. Критерий разбиения: фиксированное количество кластеров; одинаковая общая длина дорог в регионе; наименьшее количество связей между регионами. Показан алгоритм применения и его параметры. Построена схема моделирования в случае распределенной вычислительной системы (рис. 3).

Рис. 2. Блок-схема управления движением транспортных потоков

Рис. 3. Блок-схема управления движением транспортных потоков

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

1. Обеспечение пропускной способности маршрута следования через регион.

2. Исследование топологии транспортной сети для выявление мест потенциального образования заторов.

3. Накопление статистики и прогнозирование средней скорости потока в выбранном сегменте транспортной сети.

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

светофоров. Режим работы каждого светофора задается с помощью регулировки интервалов времени разрешающего и запрещающего сигналов, а так же начального смещения относительно момента старта. Светофор в вершине с номером I характеризуется управляющим набором Изучаемым объектом является регион (район города), для которого назначаются входные и выходные ребра. Транспортный поток, который начинается на входном ребре и заканчивается на выходном, называем транзитным транспортным потоком. Решение задачи заключается в отыскании такого сочетания /? = (Р1,...,/?,,) управляющих наборов для светофоров региона (где Р - количество светофоров в регионе), чтобы увеличить среднюю скорость транзитного потока через регион. Задачу предлагается решать с помощью алгоритма случайного поиска:

Шаг 1. Для управляющего набора /? находим среднюю скорость потока по маршруту следования.

Шаг 2. Переходим к управляющему набору /3'.

Шаг 3. Методом прогонки моделируем состояние региона через некоторое время Т.

Шаг 4. Находим среднюю скорость потока по маршруту следования для нового состояния региона и сравниваем с найденным ранее. При увеличении средней скорости, сохраняем /?' для следующей итерации алгоритма и переходим в эту «ветку» алгоритма поиска (шаг 1 для /?'), в противном случае пропускаем это решение.

Получены предварительные замечания о сложности этой задачи. Для этого проведена аналогия между предложенной задачей об увеличении средней скорости транзитного потока и задачей «МНОГОПРОЦЕССОРНОЕ РАСПИСАНИЕ»10, которая принадлежит классу ЫР.

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

10 Пападимитриу X., Стайглиц К. Комбинаторная оптимизация. Алгоритмы и сложность. М: МИР. 1984. С. 375-377.

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

В этом подходе рассматривается матрица скоростей УМ - {уту}, ассоциированная с графом дорожной сети, где утп1} - средняя скорость ТС при перемещении между вершиной I и }. Берется усреднение по скорости за продолжительный промежуток времени, при котором влиянием светофоров на движение можно пренебречь.

Алгоритм поиска потенциальных заторов:

Шаг 1. Строится матрица скоростей УМ.

Шаг 2. Определяются собственные векторы матрицы УМ.

Шаг 3. Выделяются номера узлов, которые соответствуют нулевым компонентам собственных векторов.

Шаг 4. Среди узлов, найденных на предыдущем шаге, выделяются номера узлов, в которых средняя скорость мала.

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

Стоит отметить, что имеет смысл рассматривать только первые 3-4 собственных вектора, поскольку их вклад в колебания скоростей будет наибольшим.

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

Шаг 1. Середина каждого ребра представляется дополнительной вершиной.

Шаг 2. Строится новый граф дорожной сети б и матрица смежности МБ.

Шаг 3. Алгоритм поиска потенциальных заторов: Шаги 1-4.

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

Накопление статистики для ребра выбранного региона осуществляется следующим образом:

Шаг 1. Выбирается временной интервал (шаг) Т для усреднения скоростей (обычно 15 минут).

Шаг 2. При прогонке алгоритма моделирования находится средняя скорость потока для рассматриваемого ребра и усредняется по Т.

Шаг 3. Определяется скоростной интервал, в который попадает найденное среднее значение скорости, и записывается в округленном виде:

Скорость, м/с 0-15 15-30 30-45 45-60

Округляется до, м/с 15 30 45 60

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

Время 13:00 13:15 13:30 13:45 14:00 14:15 14:30

Скорость, м/с 45 45 30 30 30 30 45

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

Разработанные методы включены в проект по разработке системы управления светофорами по радиоканалу, разрабатываемый НТК «Интекс».

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

Для всех вычислений использовался ПК (ноутбук) со следующими характеристиками: двухъядерный процессор - Intel Core 2 Duo 2.5 ГГц; оперативная память - 4 ГБ; под управлением операционной системы Windows 7 х64. Эксперименты, связанные с параллельными вычислениями проводились на кластере Омского государственного технического университета. Он состоит из четырех узлов, представленных компьютерами Hewlett-Packard, соединенных сетью Ethernet. Характеристики отдельного узла: четырехъядерный процессор - 2.6 ГГц; оперативная память - 4 ГБ. Прикладные программы, реализующие алгоритмы предложенной модели и численных методов, реализованы на С++ с использованием MPI. Графическая подсистема, отображающая транспортную сеть, реализована на Java.

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

Разработанная система позволяет:

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

- осуществлять вычислительный эксперимент по компьютерному моделированию работы транспортной сети;

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

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

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

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

Результаты апробации программного комплекса включают результаты вычислительных экспериментов.

Результаты кластеризации топологической основы для различных городов при делении на 2 и 8 регионов приведены в таблицах 1,2. Количество связей минимизируется, количество дорог усредняется.

Таблица 1

Результаты работы алгоритма к-средних при к=2

Город Распределение дорог по регионам Количество связей Максимальное количество дорог на границе региона

Новосибирск 1071 / 1816 1/1 47

Омск 2328/1561 1/1 45

Москва 15036/16284 1/1 149

Таблица 2 Результаты работы алгоритма к-средних при к=8

Город Распределение дорог по регионам Количество связей Максимальное количество дорог на границе региона

1 2 3 4

Новосибирск 214/504/312/281/ 228/ 181 /661 /506 1/3/4/5/3 /3/4/3 59

Окончание табл. 2

1 2 3 4

0/254/0/891/526/ 0/3/0/3/4 44

Омск /2/3/3

348 / 1327 / 543

Москва 3857/3817/2335/ 2936/4187/5451/ 5323/3414 3/3/3/3/4 /2/5/5 186

Приводятся результаты численных экспериментов с применением случайного поиска для нахождения такого управляющего набора режимами работы светофоров Р = (/?!, ...,/?р), чтобы средняя скорость транзитного ТС при прохождении через регион после поиска оптимального управляющего набора /? = 0?1# ...,/Зр) была бы больше средней скорости прохождения через регион до поиска. Показана возможность увеличения среднюю скорость прохождения при небольшой загруженности дорог вплоть до 16%.

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

Результаты численных экспериментов по проверке адекватности прогноза основывались на данных о перемещении транспортных средств, оборудованных датчиками ГЛОНАСС, предоставленных НТК «Интекс». При увеличении количества рассматриваемых ТС, точность прогноза растет. Результаты вычислительных экспериментов позволяют сделать вывод, что в 84% случаев удается верно предсказать среднюю скорость потока, которая будет через 15-30 минут от текущего временного интервала.

Для всех экспериментов приведены условия, в которых они проведены.

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

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

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

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

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

- обеспечение пропускной способности маршрута следования через регион;

- исследование топологии транспортной сети для выявление мест потенциального образования заторов;

- накопление статистики и прогнозирование средней скорости потока в выбранном сегменте транспортной сети.

Получена справка о включении результатов представляемой диссертационной работы в проект по разработке системы управления светофорами по радиоканалу, осуществляемый ООО НТК «ИНТЕКС».

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

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

Статьи, опубликованные в ведущих рецензируемых журналах, определенных ВАК

1. Соловьев В.А., Файзуллин Р.Т. Математическое моделирование транспортных потоков на основе схемы с двумя масштабами времени. // Омский научный вестник. Сер. Приборы, машины и технологии. — 2011. - №3(103). -С. 37-40.

2. Соловьев В.А., Файзуллин Р.Т. Математическое моделирование и управление транспортными потоками на основе схемы с двумя масштабами времени // Доклады Томского государственного университета систем управления и радиоэлекроники. - 2012. - №2(26) - С. 214-218.

3. Соловьев В.А., Файзуллин Р.Т. Корреляция между расположением автомобильных пробок и структурой графа дорожной сети // Вестник СибАДИ. -2013. - Вып. 2(30) - С. 78-81.

Другие публикации

4. Соловьев В.А., Файзуллин Р.Т. Математическое моделирование транспортных потоков на основе микроскопической схемы предиктор-корректор. // Информационный бюллетень Ассоциации математического программирования. - №12. - Научное издание. - Екатеринбург: УрО РАН, 2011. - С. 135-136.

5. Соловьев В.А., Файзуллин Р.Т. Математическое моделирование транспортных потоков на основе микроскопической схемы предиктор-корректор. // Параллельные вычислительные технологии (ПаВТ'2011): труды междун. научн. конф. (Москва, 28 марта - 1 апреля) - Челябинск: Издательский центр ЮУрГУ, 2011.-С. 657-662.

6. Faizullin R.T., Solovev V.A. Mathematical model of traffic flow with two time scales. // Proceeding include abstract of reports presented at II International conference «Optimization and applications» (OPTIMA-2011) help at Petrovac, Montenegro, in September 25 - October 2, 2011. P. 78-81.

7. Соловьев B.A., Сунгуров И.С. Математическое моделирование транспортных потоков на основе микроскопической схемы предиктор-корректор. //

Омский регион - месторождение возможностей: матер, научн.-техн. конф. Омск: Изд-во ОмГТУ, 2011. - С. 88-89.

8. Соловьев В.А., Сунгуров И.С. Математическая модель транспортных потоков на основе схемы с двумя масштабами времени. // Параллельные вычислительные технологии (ПаВТ'2012): труды междунар. научн. конф. - Челябинск, 2012.-С. 774.

9. Соловьев В.А., Сунгуров И.С., Файзуллин Р.Т. Математическое моделирование транспортных потоков. // Суперкомпьютеры. М.: ООО «Издательство СКР-Медиа». - 2012. - №2 (10). - С. 55-58.

10. Соловьев В.А. Задача на собственные значения, ассоциированная с задачей поиска устойчивых пробок в модели транспортного потока. // Электронные средства и системы управления: Материалы докл. Междунар. научн.-практ. конф. (8-10 ноября 2012 г.): В 2 ч. - Ч. 2. - Томск: В-Спектр, 2012. - С. 73-76.

Печатается в авторской редакции

Компьютерная верстка О. Г. Белименко

Подписано в печать 21.11.13. Формат 60х841/16. Бумага офсетная. Отпечатано на дупликаторе. Усл. печ. л. 1,5. Уч.-изд. л. 1,5. Тираж 100 экз. Заказ 638.

Издательство ОмГТУ. 644050, г. Омск, пр. Мира, 11; т. 23-02-12 Типография ОмГТУ

Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования

ОМСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

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

04201451832

УДК 519.6, 519.8

Соловьев Вадим Анатольевич

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

КРУПНОГО ГОРОДА

Специальность 05.13.18 - Математическое моделирование, численные методы и комплексы программ

Диссертация на соискание ученой степени кандидата технических наук

Научный руководитель д.т.н., проф., Файзуллин Р.Т.

Тюмень - 2013

ОГЛАВЛЕНИЕ

Стр.

ВВЕДЕНИЕ..............................................................................................................4

Глава 1. Анализ математических моделей транспортных потоков...................9

1.1. Моделирование транспортных потоков...................................................9

1.1.1. Макроскопические модели................................................................10

1.1.2. Микроскопические модели...............................................................18

1.2. Выводы по Главе 1......................................................................................29

Глава 2. Математическая модель и методы оптимизации управления движением транспортных потоков......................................................................30

2.1. Топологическая основа модели транспортных потоков.........................31

2.2. Математическая модель транспортных потоков.....................................32

2.3. Кластеризация топологической основы транспортной сети..................37

2.4. Численные методы оптимизации управления движением транспортных потоков..........................................................................................46

2.4.1. Задача обеспечение пропускной способности маршрута следования через регион................................................................................46

2.4.2. Предварительные замечания о сложности задачи об увеличение средней скорости транзитного потока через «регион»...............................55

2.4.3. Задача о поиске устойчивых пробок...................................................58

2.4.4. Накопление статистики и прогнозирование средней скорости потока в выбранном сегменте транспортной сети......................................63

2.5. Выводы по главе 2......................................................................................66

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

3.1. Описание комплекса программ.................................................................68

2

3.2. Формирование топологической основы.................................................76

3.3. Кластеризация топологической основы.................................................77

3.4. Численные методы и их апробация........................................................88

3.4.1. Обеспечение пропускной способности маршрута..........................88

3.4.2. Анализ топологии транспортной сети.............................................90

3.4.3. Прогнозирование средней скорости потока в регионе..................94

3.5. Выводы по главе 3....................................................................................99

ЗАКЛЮЧЕНИЕ...................................................................................................100

СПИСОК ТАБЛИЦ.............................................................................................101

СПИСОК ЛИТЕРАТУРЫ...................................................................................102

ВВЕДЕНИЕ

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

Математическое моделирование транспортных потоков возникло в 50-е годы XX века. В работах Дж. Лайтхилла, Дж. Уизема (1955), П. Ричардса (1956) была построена первая макроскопическая модель однополосного транспортного потока, названая впоследствии моделью Лайтхилла-Уизема-Ричардса, в которой поток транспортных средств рассматривается как поток одномерной сжимаемой жидкости [1],[2]. В дальнейшем был предложен ряд модификаций данной модели (модель Танака (1963), модель Дж. Уизема (1974), модель Дж. Пэйна (1971) и другие).

В 1961-м году Ф. Ньюэллом была предложена первая микроскопическая модель, в основе построения которой лежит концепция «о желании придерживаться при движении безопасной дистанции до лидера». В данной модели постулируется следующее: для каждого водителя существует «безопасная» скорость движения, зависящая от дистанции до лидера. Другим видом микроскопических моделей, наряду с моделями оптимальной скорости, являются модели следования за лидером. В 1959 г. Д. Газис, Р. Херман, Р. Поте предложили одну из первых нетривиальных микроскопических моделей однополосного транспортного потока. С помощью этой модели можно определить зависимость между интенсивностью потока транспортных средств

и плотностью. Ф. Хейт был первым, кто выделил исследование транспортных потоков в отдельный, самостоятельный раздел математики.

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

Для достижения поставленной цели в работе решаются следующие задачи:

- проведение анализа предметной области, на основе которого обосновывается алгоритм по построению модели;

- разработка математической модели транспортных потоков и вариантов движения транспортных средств (ТС), в зависимости от различных ситуационных моментов;

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

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

Актуальность работы

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

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

Содержание работы

Диссертационная работа состоит из введения, трех глав, заключения и библиографии.

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

Вторая глава посвящена описанию предлагаемой микроскопической математической модели и методов, решающих следующие задачи:

® увеличение средней скорости транзитного потока при прохождении региона;

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

• прогнозирование параметров транспортного потока.

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

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

Научная новизна работы по трем областям специальности 05.13.18 отражена в следующих результатах:

Математическое моделирование

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

Численные методы

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

Комплексы программ

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

Результаты, выносимые на защиту, соответствуют следующим трем пунктам паспорта специальности 05.13.18 - Математическое моделирование, численные методы и комплексы программ по техническим наукам:

Пункт 1: Разработка новых математических методов моделирования объектов и явлений.

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

Пункт 4: Реализация эффективных численных методов и алгоритмов в виде комплексов проблемно-ориентированных программ для проведения вычислительного эксперимента.

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

3. Программный комплекс состоит из программы, моделирующей движение транспортных потоков, разработанной с применением параллельных вычислительных технологий, а также программы, визуализирующей транспортные потоки на карте города. Разработанный программный комплекс внесен в Реестр программ для ЭВМ с регистрационным номером № 2013615221.

Пункт 8: Разработка систем компьютерного и имитационного моделирования.

4. Подсистема компьютерного моделирования транспортных потоков, использующая данные, полученные с датчиков ГЛОНАСС.

Соответствие диссертации паспорту научной специальности. Научные положения диссертации соответствуют формуле специальности 05.13.18 - Математическое моделирование, численные методы и комплексы программ. Результаты проведённого исследования соответствуют областям исследования специальности, конкретно пунктам 1, 4, 8 её паспорта.

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

Апробация результатов работы

Основные результаты работы опубликованы в работах [179-178](из них работы [169-171] опубликованы в журналах, входящих в перечень ВАК) и прошли апробацию в виде выступлений на научных конференциях и семинарах: ХГУ-й Всероссийской конференции «Математическое программирование и приложения» (Екатеринбург, 28 февраля - 04 марта 2011 г.); международной научной конференции «Параллельные Вычислительные Технологии 2011» (ПаВТ'2011) (Москва, 28 марта - 1 апреля 2011 г.); П-й региональной молодежной научно-технической конференции «ОМСКИЙ РЕГИОН - МЕСТОРОЖДЕНИЕ ВОЗМОЖНОСТЕЙ» (Омск, 14-17 апреля

2011 г.); международной научной конференции «Параллельные Вычислительные Технологии 2012» (ПаВТ'2012) (Новосибирск, 26 - 30 марта

2012 г.); УШ-й Международной научно-технической конференции «ДИНАМИКА СИСТЕМ, МЕХАНИЗМОВ И МАШИН» (Омск, 13-15 ноября 2012 г.)

В ходе выполнения научного исследования диссертантом была разработана программа для ЭВМ, которая зарегистрирована в реестре программ для ЭВМ (свидетельство о государственной регистрации программы для ЭВМ №2013615221). Автором получена справка о включении результатов представляемой диссертационной работы в проект по разработке системы управления светофорами по радиоканалу, осуществляемый ООО НТК «ИНТЕКС».

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

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

1.1. Моделирование транспортных потоков

В настоящее время в математическом моделировании транспортных потоков существует два подхода к постановке задачи моделирования.

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

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

Далее подробнее остановимся на имитационных математических моделях транспортных потоков.

1.1.1. Макроскопические модели

Впервые о математическом моделировании транспортных потоков упоминается в научных трудах середины XX века. Оно возникает как приложение к активно изучаемым в то время явлениям, связанным с ударными волнами. Оказалось, что транспортный поток достаточно адекватно аппроксимируется потоком жидкости с определенными свойствами. Этой жидкости приписывают свойства «упругости», «эластичности», «сжимаемости». Поскольку транспортный поток сравнивается с жидкостью, то детализация, с которой рассматривается движение, не предполагает выделения отдельных автомобилей.

Ключевыми характеристиками транспортного потока, которыми оперируют в этом классе моделей, являются:

1. Плотность потока - количество ТС на единицу длины дороги.

2. Поток - количество ТС, проходящих сечение дороги за единицу времени.

3. Средняя скорость транспортных средств в потоке.

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

Гидродинамические модели

Первой моделью в данном классе и одной из первых математических моделей транспортных потоков вообще является модель Лайтхилла-Уизема-Ричардса (Ь\УК) [1], [2]. Она легла в основу всех последующих разработок в области макроскопических моделей. В ней описывается транспортный поток с учетом того, что существует однозначная зависимость между скоростью и плотностью потока.

Основным требованием является выполнение условия сохранения количества транспортных средств, которое предполагает, как существование зависимости между скоростью х) и плотностью р(£,х) потока, так и выполнение закона сохранения количества ТС. Классические обозначения плотности и скорости потока: р(Ь,х) и у(Ь,х). Под плотностью потока понимают число ТС на единицу длины в момент времени С в некоторой окрестности точки дороги с координатой х. Скорость ТС в момент времени £ также рассматривается в окрестности точки с координатой х.

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

Первая часть условия, позволяющие выразить требования условия сохранения количества транспортных средств:

у(Ь,х) = У(р{Ь,х)) (1)

Интенсивность потока ТС:

<2(р) = рУ(р) (2)

Зависимость (}(р) называют фундаментальной диаграммой.

Эта модель содержит условие, которое можно понимать следующим образом [4]: «движение по двум одинаковым и независимым полосам с разными плотностями менее «эффективно», чем движение по этим полосам с одинаковой плотностью, равной среднему арифметическому первоначальных плотностей. Однако если агрегировать несколько полос в одну, то, как показывают наблюдения за реальными транспортными потоками, от вогнутости функции (}(р), вообще говоря, придется отказаться».

После появляются различные модификации Ь\УЯ модели. Модель Танака (1963) [3], предполагает наличие коэ