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

Заключение

Разработан способ использования визуальной и автоматической таксономии для анализа задержек при прохождении маршрута. Введение таксономии в технологическую цепочку системы GisAuto ПОЗВОЛИЛО повысить качество анализа результатов редукции графа за счет одновременного учета нескольких параметров. Показано хорошее совпадение разбиений на таксоны при использовании визуальных эвристических методов и автоматической таксономии по алгоритму FOREL-2. Изображение результатов таксономии на ГИС -карте графа маршрута значительно улучшает их восприятие и информативность.

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

Дальнейшее развитие GisAuto планируется связать с созданием средств анализа методов управления автодорожным движением.

Библиографический список

1. Пуртов А. М. Разработка геоинформацион-ной системы для анализа автотранспортных сетей // Вестник СибАДИ. - 2013. - № 1 (29). - С. 89-95.

2. Пуртов А. М. Анализ производительности сетей ЭВМ на графах и имитационных моделях: Автореф. дис. канд. техн. наук / - Новосибирск, 1995. - 17с.

3. Задорожный В. Н., Пуртов А. М. Анализ чувствительности в имитационном моделировании сетей массового обслуживания // Омский научный вестник.- 2005. - № (33). - С. 165-171.

4. Пуртов А. М., Татауров С. Ф., Шлюшинский А. В.. Разработка ГИС «Археологические памятники юга Западной Сибири». // Омский научный вестник.- 2006. - № 7(43). - С. 136-139.

5. Долгушин Д. Ю., Мызникова Т. А. Имитационное моделирование автотранспортных потоков для оценки альтернативных схем организации дорожного движения в городских условиях // Вестник СибАДИ. - 2011. - № 2 (20). - C. 47-51.

6. Пуртов А. М. Интеграция технологии ГИС и метода редукции графов для анализа транспортных сетей // Омский научный вестник. - 2011. - № 1 (97). - C. 164-168.

7. Загоруйко Н. Г. Прикладные методы анализа данных и знаний. - Новосибирск: Изд-во Изд-во ИМ СО РАН, 1999. - 270с.

8. Борисова И. А., Загоруйко Н. Г., Функции конкурентного сходства в задаче таксономии // Знания-Онтологии-Теории (30НТ-07): C6, науч. тр. Т.2 - Новосибирск: Изд-во ИМ СО РАН, 2007 - С 67-76.

9. Пуртов А. М., Использование ГИС-технологии и таксономии для визуального анализа данных о субъектах РФ// Знания-Онтологии-Теории (ЗОНТ-09): материалы конф. с междун. участием. Т.2. (Новосибирск, 22-24 окт. 2009г.). - Новосибирск: Изд-во ИМ СО РАН, 2009.- С. 207-211.

USE OF TAXONOMY AT THE ANALYSIS OF DELAYS IN AUTO-TRANSPORT NETWORKS

A. M. Purtov

The way of application of taxonomy, a reduction of graphs and geoinformation systems Is developed for the analysis of routes in transport networks. The technology is shown on examples of the analysis of popular routes of Omsk. The example of use of taxonomy for the analysis of results of a reduction of graphs are shown. Similarity of results of visual and automatic taxonomy is shown. Results of taxonomy are represented on GIS - maps the graph of delays.

Пуртов Андрей Михайлович - кандидат технических наук, доцент, с.н.с. лаб. МППИ ОФ ИМ СО РАН, 632288. Основные направления работы: Геоинформационные системы, имитационное моделирование, компьютерные сети, автотранспортные сети. Общее количество опубликованных работ более: 40 научных работ. E-mail: andr.purto v@yan dex. ru

УДК 519.8

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

В. А. Соловьев, Р. Т. Файзуллин

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

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

Ключевые слова: собственные числа, транспортный поток, устойчивая пробка.

Введение

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

Микроскопические модели транспортного потока появились несколько позднее. В основе подходов лежит концепция «о желании придерживаться при движении безопасной дистанции до лидера». Так в 1961-м году Ньюэллом была предложена модель [3], которую можно считать первой микроскопической моделью. В ней постулируется, что для каждого водителя существует «безопасная» скорость движения, зависящая от дистанции до лидера. Другим важным классом микроскопических моделей, наряду с моделями оптимальной скорости, являются модели следования за лидером. В 1959 г. сотрудники концер-

на Дженерал Моторе Д. Газис, Р. Херман, Р. Потс предложили одну из первых [4] (хотя ранее похожие результаты были в моделях А. Рашеля (1950) и Л. Пайпса (1953)) нетривиальных микроскопических моделей однополосного транспортного потока, с помощью которой можно получить фундаментальную диаграмму - зависимость между интенсивностью потока транспортных средств и плотностью. Ф.Хейт был первым, кто выделил исследование транспортных потоков в отдельный, самостоятельный раздел математики.

Описание задачи

Рассмотрим уравнение движения для алгоритмической схемы модели транспортного потока, описанного в [5]:

- х11

- хм (:) - vi+1 (t + АЧ)АЧ = Pi

где х. (!) - положение нго транспортного средства, движущегося со скоростью

vi (!), в момент времени !; At - сдвиг по

времени; Д. - модификатор схемы движения,

отвечающий за положение точки, которую стремится занять транспортное средство при движении в потоке; / - номер от 1 до М, где М - количество транспортных средств на ребре (дороге, трассе).

2( х1 + ^А!) — Х2 — V2At : 0 0 0 0 0 = А

0 0 ! - Х-1 - V-1А 2( х. + V. А!) - X+1 - V+1А! 0 0 = А

0 0 ! 0 0 0 ; - хм-1 - УМ-1А! 2( хм + умА!) = Рм

Если рассмотрим участок трассы и уело- вующую системе (2), составленной из урав-

вия, которые определяют движение, то полу- нений типа (1).

чим трехдиагональную матрицу, соответст-

М М-1 1+1 / И

Рис. 1. Движение по участку трассы

1

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

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

Эта конструкция кажется искусственной, но если рассмотреть усреднения по времени (будем считать светофоры модификаторами

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

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

Рис. 2 . Колебание струны, ДАламбер

Если воздействие на стержень будет гладким, то результат возмущения будет также гладким, и коэффициенты разложения по собственным функциям будут убывать в зависимости от степени гладкости и возмущения. Если возмущение непрерывно, то коэффициенты убывают как 1/п2. Если возмущение дифференцируемо, то убывание будет пропорционально 1/п3.

Таким образом, если возмущение похоже на 2-ю собственную форму, то узел не изменится.

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

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

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

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

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

Рис. 3. Области, содержащие узлы, совпадающие с реальными пробками

Заключение

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

Библиографический список

1. Lighthill M. J., Whitham G.B. On kinematic waves:

II. Theory of traffic flow on long crowded roads // Proc. R. Soc. London, Ser. A. 1955. V. 229. P. 281-345.

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

3. Newell G. F. Nonlinear effects in the dynamics of car - following // Oper. Res. 1961. V. 9. P. 209-229.

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

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

THE EIGENVALUE PROBLEM ASSOCIATED WITH THE SEARCH FOR STABLE TRAFFIC JAMS PROBLEM IN TRAFFIC FLOW MODEL

V. A. Solovev, R. T. Faizullin

Proposed by the task of finding nodes of the transport network, the presence of plugs that do not depend on the change of the schedule of traffic lights (or other factors alter the flow rate). Considered the analogy between the problem of the vibration of the rod and secured the proposed objective of the nodes of the transport network with strong caps. Solution of the problem involves the use of computer algebra methods based on finding the eigenvalues and eigenvectors.

Соловьев Вадим Анатольевич - аспирант ФГБОУ ВПО «ОмГТУ», каф. «КЗИ». Основные направления научной деятельности - Математическое моделирование транспортных потоков, со-бвенные числа и векторы. Общее количество опубликованных работ: 7. e-mail:

v. a. solo ve v@gmail. com.

Файзуллин Рашит Тагирович - д.т.н., профессор; проректор по информатизации ФГБОУ ВПО ОмГТУ. Основные направления научной деятельности - математическое моделирование, защита информации. Общее количество опубликованных работ: 100 публикаций; e-mail: почта: frt@omgtu.ru