УДК: 004.94; 004.02 Лесько С.А., Алёшкин А.С., Барков А.А. Московский технологический университет (МИРЭА), г. Москва, Россия РАЗРАБОТКА МАТЕМАТИЧЕСКОГО И ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ ДЛЯ МОДЕЛИРОВАНИЯ И УПРАВЛЕНИЯ ТРАНСПОРТНЫМИ ПОТОКАМИ НА ОСНОВЕ ПЕРКОЛЯЦИОННОЙ СТОХАСТИЧЕСКОЙ МОДЕЛИ* Аннотация В представленной работе описана разработанная авторами модель динамики стохастических потоков в транспортных сетях с недетерминированными характеристиками распределения статистических параметров, позволяющая описывать зависимость вероятности блокирования отдельных узлов от характеристик дорожного движения с течением времени. В разработанной математической модели описаны правила обслуживания перекрестков (время переключения светофоров), учтен материальный баланс числа машин в системе и связи их потоков между соседними перекрестками. В работе было показано, что использование методов теории перколяции и результатов разработанной стохастической модели транспортных потоков позволяет моделировать работу транспортной сети не только на уровне отдельных узлов, но и всей структуры в целом. Предлагаемая модель позволяет, используя реальную карту транспортной сети создать её динамическую модель, эмулировать её работу и возникновение пробок. При моделировании транспортных потоков может быть использован технологический подход, основанный на перколяционных моделях транспортных систем, загрузки карт в формате Open Street Map (OSM), построении графа дорожной сети с указанием свойств (классов данных объектов) дуг (дорога) и вершин (перекресток) и набор объектов для отображения их в графической форме с целью вычисления величин порогов перколяции для существующей системы и предлагаемых решений и выбора наиболее оптимальной структуры транспортной сети, при минимизации финансовых затрат на дорожное строительство. Кроме того, в работе описана разработанная авторами структура и программное обеспечение комплекса моделирования процессов в транспортных сетях на основе перколяционной стохастической модели и представлена алгоритмическая реализация основных функциональных возможностей его работы. Ключевые слова Транспортная сеть, порог перколяции, моделирование свойств сети, стохастическая динамика транспортных потоков балансировка нагрузки, моделирование потоков, программное обеспечение. Lesko S.A., Alyoshkin A.S., Barkov A.A. Moscow Technological University (MIREA), Moscow, Russia MATHEMATICAL AND SOFTWARE DEVELOPMENT OF MODELING AND MANAGEMENT OF TRANSPORT FLOWS BASED ON PERCOLATION STOCHASTIC MODEL Abstract This paper describes the model developed of the stochastic flows dynamics in transport networks with nondeterministic characteristics of the distribution of statistical parameters, which makes it possible to describe the dependence of the blocking individual nodes probability on the characteristics of traffic in the course of time. The developed mathematical model describes the rules for servicing intersections * Труды II Международной научной конференции «Конвергентные когнитивно- информационные технологии» (Convergent’2017), Москва, 24-26 ноября, 2017 Proceedings of the II International scientific conference "Convergent cognitive information technologies" (Convergent’2017), Moscow, Russia, November 24-26, 2017 454 (the time for switching traffic lights), taking into account the material balance of the number of machines in the system and the connection of their flows between adjacent intersections. It was shown that the use of the methods of percolation theory and the results of the developed stochastic model of transport streams makes it possible to model the operation of the transport network not only at the level of individual nodes, but also the entire structure as a whole. The proposed model allows, using the real map of the transport network to create its dynamic model, to emulate its operation and the appearance of traffic jams. In the modeling of transport flows they used a technological approach based on percolation models of transport systems, loading maps in the Open Street Map (OSM) format, building a graph of the road network with the properties of the (object data classes) arcs (road) and vertices (intersection) and a set of objects for displaying them in a graphical form in order to calculate the values of percolation thresholds for the existing system and the proposed solutions and the choice of the most optimal structure of the transport network, while minimizing the financial costs for road construction. In addition, the paper describes the structure and software developed by the authors of a complex of modeling processes in transport networks based on the percolation stochastic model and presents the algorithmic implementation of the basic functional capabilities of its operation. Keywords Transport network, threshold of percolation, modeling of network properties, stochastic dynamics of transport streams load balancing, flow modeling, software. Введение На сегодняшний день, проблема организации дорожного движения, в крупных городах, с каждым годом становится все острее. Постоянное увеличение количества транспорта и аварий сильно опережает темпы строительства новых и модернизацию существующих дорог, разгрузочных развязок, тоннелей и эстакад. Как показывает практика, даже крупные проекты при активной поддержке органов государственной власти и указаний высших чинов, вносят лишь незначительные изменения в текущую ситуацию, а дороги по-прежнему не справляются с огромным потоком автотранспорта. В силу этих обстоятельств, можно сделать вывод, что образование заторов на дорогах – чаще всего непредотвратимый, порой хаотичный, процесс, причины которого не всегда легко выявить и разрешить. В случае когда, мы встречаемся с задачами подобного рода, необходимо учитывать множество факторов для планирования стратегии их решения. Дорожное моделирование позволяет упростить оценку изменений инфраструктуры. Многие параметры сети дорог могут быть оптимизированы в процессе моделирования. Для моделирования процессов в сети дорог, дорожную сеть крупного мегаполиса и транспорт на ней, часто представляют как распределенную саморегулирующуюся систему, структура которой может быть представлена как взвешенный, связный граф, где множество вершин будут представлять из себя перекрестки, ребра, соединяющие их, – дороги, веса ребер – физическую длину этих дорог или любая другая физически интерпретируемая характеристика. Актуальность разработки новых моделей управления транспортными потоками заключается, в том, что задача устранения образования пробок на дорогах, до сих пор, не решена и все больше привлекает внимание специалистов в области информационных технологий, а проекты в данной области считаются перспективными. В настоящее время, существуют различные, и создаются новые, математические и информационные модели, формулировки таких задач и методы их решения, которые активно совершенствуются. Обзор моделей, применяемых для описания транспортных потоков На сегодняшний день, сформировалась тенденция использовать новые, революционные методы решения, основанные на базе математического и информационно-технологического аппаратов, в том числе методов решения задач в условиях неопределенности, а также применять междисциплинарные математические идеи, методы и алгоритмы нелинейной динамики. Их целесообразность обоснована наличием в транспортном потоке устойчивых и неустойчивых режимов движения, потерь устойчивости при изменении условий движения, нелинейных обратных связей, и необходимости в большом числе переменных для адекватного описания системы. Первой задачей транспортной теории потоков был поиск независимых от времени связей между плотностью и скоростью, или так называемых фундаментальных диаграмм. Описание этих отношений 455 (связей) обсуждается в трудах Ф.Л. Холла. Решение этой задачи возможно только для малых промежутков времени. Полученные результаты являются достаточно усредненными и сильно колеблются. Второй шаг в развитии моделирования транспортных потоков – это введение зависимости параметров потоков от времени. Это было достигнуто в 1955 Лайтхиллом и Уиземом. Они ввели описание движения потоков, основанное на уравнении непрерывности, предполагая, что скорость зависит только от плотности, то есть происходит мгновенная адаптация. Пригожин и Херман развивали кинетическую теорию для транспортных потоков. Они дали определение модели Лайтхелла-Уизема как частного случая кинетической теории. Кинетическая теория описывает многие явления, происходящие в движении транспортных потоков, но, вероятно, потому, что математическое моделирование довольно трудоемко, эта теория не была развита до недавнего времени. Вместо этого в 1979 Пэйн заменил предположение о мгновенной адаптации в теории Лайтхелла-Уизема уравнением для инерции, которое подобно уравнению Навье-Стокса. Кишнэ в 1984 добавил термин вязкости и начал использование методов нелинейной динамики для того, чтобы проанализировать уравнения. Параллельно Муша и Хигучи предложили уравнение Бюргерса, как модель описания транспортного потока и предоставили автоматические измерения данных о количестве транспорта. Рисунок 1– Модели моделирования транспортной сети Описание стохастических моделей представляют в своей работе Джост и Нагель. Стохастические модели обладают одной гомогенной фазой движения через целый диапазон плотности (1-фазовые) или они обладают двумя. Разделяют гомогенные фазы на "пластинчатые" и "защемленные", которые разделены режимом плотности, где эти две фазы сосуществуют (2-фазовые). Предположения об этом складывались в течение довольно долгого времени (например, Пригожин и Херман (1971); Рейс и д.р. (1986); Треитерер и Майерс (1974)); соответствующие модели зависимостей были установлены позже (например. Кернер и Конхойзер (1994); Бандо и д.р. (1995)). Однако, несмотря на большое обсуждение (например, Нагель (1994); Нагель и Пацзуский (1995); Сасвэри и Кертез (1997); Ротерс и др. (1999); Чоудхури и др. (2000)), никакая ясная картина для стохастических моделей не была установлена. Но только стохастические модели позволяют рассматривать метастабильные состояния, непосредственные переходы и рекурсивно-подобную структуру, каждая из которых важна для движения в реальном мире. Эти модели рассматривают возможности автострад. Решается вопрос о максимальных потоках возможных на автострадах и являются ли они жизнеспособными, какова их частота. Имеется объемная история публикаций об образовании заторов (аварийного поведения) в движении потока, иногда называемом “обратная форма лямбды фундаментальной диаграммы” (Коши и др., 1983; Кернер, 1999), "гистерезис" (Треитерер и Майерс, 1974), “полное снижение” (Кернер и Рибон, 1996), “теория катастрофы” (Аха-Даза и Холл 1993), и т.п.. Существуют аналогии с газожидкостным переходом (Пригожин и Херман, 1971; Рейс и др., 1986), и транспортные модели, которые показывают детерминированные версии перехода "жидкого газа" (Кернер и Конхойзер, 1994; Бандо и др., 1995). С 456 другой стороны, измерения Кэссиди (1998) указывают, что может быть устойчивый гомогенный поток во всех удельных значения. На рисунке 1 представлены основные классические модели движения транспортных потоков, описание которых было сделано на основе результатов, изложенных в [1,2]. В таблице 1 представлена категоризация математических моделей, некоторые их особенности и применение для конкретных задач моделирования транспортных потоков. Таблица 1. Сравнение математических моделей Имеющиеся модели для Уровень Методы Необходимые Задачи решения моделирования решения данные поставленной задачи Модель генерации Создание Социологические активности методик данные по населения социологических количеству обследований населения, Сбор и процент Модель генерации обработка населения, маршрутов данных имеющего обследования личный Определение транспорт Предварительно подвижности Социологические е моделирование населения и данные по транспортного спроса популярным Расчет матриц Гравитационная маршрутам корреспонденций и модель поездок (дом- пассажирских Энтропийная работа). перевозок. модель Дорожная сеть. Маршруты общественного транспорта. Модель Гидродинамические Лайтхилла- модели Уизема Сбор и модель Пэйна мониторинг Оценка Классическая 4-х структуры эффективности ступенчатая транспортного строительства и модель спроса по: реконструкции Модель EVA - Целям поездок Макромоделиро транспортной (VISUM) - Видам вание инфраструктуры. Модели Модель VISEM перевозок Оценка равновесного (VISUM) (общественный эффективности мер по распределения Модель Бэкмана и/или личный регулированию Модель транспорт) транспортного спроса. Нестерова-де- - Периодам Пальма времени Стохастические модели Мезомоделирова Модель Модель следования Анализ и ние Оценка Дженерал за лидером, мониторинг: эффективности мер по Моторс разумного - Методов ОДД совершенствованию Модель водителя - Поведенческих организации Трайбера особенностей Микромоделиро дорожного движения водителей и вание (ОДД). пешеходов Клеточные Модель Нагеля- автоматы Шрекенбергера 457 Следует отметить, что для описания процессов в транспортных сетях могут быть применено множество подходов. Например, теория массового обслуживания [3-5], сети Петри [6,7], теория нечетких множеств [8,9], теория клеточных автоматов и многое другое. Несмотря на существующие разработки и конкретные решения в области управления, транспортные сети с точки зрения математического моделирования и управления являются очень сложными и плохо изученными объектами, требующими дальнейшего исследования На сегодняшний день, существует множество реализаций программных комплексов для моделирования транспортных потоков. Для обзора были выбраны два программных комплекса, которые являются на данный момент самыми известными и часто применяемыми. Рассмотрим, разработанный в немецком Институте Исследования Транспорта (Institute of Transportation Systems), программный комплекс SUMO (Simulation of Urban MObility). Разработчики позиционируют свой комплекс как, портативный пакет с открытым исходным кодом, микроскопического и непрерывного моделирования дорожного движения, предназначенный для обработки больших дорожных сетей. Он активно развивается, поддерживается и распространяется под лицензией GPL. SUMO задуман для имитации дорожной сети трафика размером города. Поток трафика моделируется микроскопически. Это означает, что каждое транспортное средство, которое движется в пределах моделируемой сети, моделируется индивидуально и имеет определенные местоположение и скорость. В каждом временном шаге, который имеет длительность 1 сек, эти значения обновляются в зависимости от транспортного средства впереди и на улице сети автомобиля движется дальше. Задача моделирование уличных транспортных средств является дискретной по времени и пространственно-непрерывной. Модель, используемая в настоящее время в рамках SUMO является расширением модели Гиппса (изобретена и описана в: Krauss 1998, Janz 1998), которая, в свою очередь, является расширением стандартной модели Лайтхилла-Уизема (гидродинамические модели второго порядка). Он способен отображать основные особенности трафика, как свободного и перегруженного потока. В каждом временном шаге скорость транспортного средства приспособлена к скорости ведущего транспортного средства таким образом, что дает к поведению без столкновений системы в следующей стадии (стадий) моделирования. Также представляют интерес отечественные разработки PTV VISSIM, VISSIM и другие пакеты программ компании A+S. VISSIM – Среда для имитационного моделирования дорожного движения (индивидуального и общественного транспорта), проверка инженерных гипотез по организации дорожного движения и т.д. Программный комплекс позволяет моделировать движение воздушных и морских судов, а также пешеходных потоков. В современной инженерной науке при планировании и анализе немыслимо обходиться без имитационного моделирования. VISSIM способен моделировать не только транспортное движение, но и движения воздушных, морских судов, а также пешеходных потоков. VISUM представляет собой обширную, гибкую программу для моделирования транспортных потоков, расчета спроса на транспорт (матрицы корреспонденций для общественного и индивидуального транспорта), анализа транспортной сети, расчет себестоимости общественного транспорта и прогноза запланированных мероприятий и их последствий. VISUM используется для моделирования транспортных потоков, транспортного планирования и оптимизации общественного транспорта: в городах, регионах, мегаполисах. VISUM интегрирует всех участников движения в единую математическую транспортную модель. В связи с тем, что проект является коммерческим, понять какую именно математическую транспортную модель использовали инженеры не представляется возможным. Перколяционная стохастическая модель транспортной сети Описание графа транспортной сети Под транспортной сетью будем подразумевать улицы, дороги, линии внеуличного транспорта (метро, монорельс, трамвай), а также маршруты общественного транспорта. Следует отметить, что модель загрузки транспортной сети требует для своего описания большое количества исходных данных, которые можно условно разделить на три группы: • Характеристики транспортной сети (количество полос и качество улиц и дорог, организация движения, маршруты и провозные способности общественного транспорта и т.д.). • Размещение объектов, порождающих передвижения (места проживания, места приложения труда, культурно-бытового обслуживания и т.д.). • Поведенческие факторы (подвижность населения, предпочтения при выборе способов и маршрутов передвижений и т.д.). При расчете кратчайших расстояний на первом этапе следует создать в памяти модель транспортной сети, что является достаточно трудоемким. Это является основным недостатком данного метода. Однако разработав модель один раз, можно по мере необходимости в любой момент очень быстро определить кратчайшие расстояния между интересующими пунктами транспортной сети. 458 Модель транспортной сети представляет собой геометрическую фигуру (граф), состоящую из вершин (точек) и отрезков (ребер), соединяющих вершины (точки графа). Для ее построения берем схему дорожной сети. На первом этапе из дорожной сети исключаем улицы, переулки и т.п., не имеющие существенного значения для транзитного движения (служащие для подъезда к домам, заводам и т.д.), и получаем схему транспортной сети. Далее, обозначив перекрестки вершинами и соединив их ребрами соответствующей длины, приходим к модели транспортной сети. Граф сети дорог изображен на рис. 2. Рисунок 2 – Граф сети дорог Каждой вершине транспортной сети присваивают порядковый номер. Отрезки, соединяющие соседние вершины, будут звеньями транспортной сети. Совокупность всех вершин и звеньев – модель транспортной сети. Проезды с односторонним движением отражают посредством ориентированного звена графа (ребро со стрелкой). Между узлами сети (перекрестками) по связям (дорогам) перемещаются автомобили, потоки которых регулируются светофорами. Они открывают на некоторое время, то или иное направление движения. Когда интенсивность движения увеличивается, то автомобили начинают скапливаться и образуется очередь. Когда число машин в очереди достигает для данного i-направления на j-перекрестке некоторый критический порог (обозначим его Li,j) возникает пробка (узел транспортной сети блокируется). В качестве аналога дорожной системы можно рассматривать компьютерную сеть, на узлах которой происходит обработка заявок, и могут образовываться очереди. Отметим, что разработка математической и информационной модели работы транспортной сети города, как и для компьютерных сетей, вряд ли возможна на основе традиционных моделей, например, теории массового обслуживания. Использование традиционных методов, основанных на пуассоновских входных потоках и экспоненциальном характере времени обслуживания не всегда оправдано. В случае отклонения коэффициентов вариаций этих распределений от единицы существующие методы аппроксимации, использующие два первых момента распределений входного потока и времени обслуживания имеют большую погрешность. Построение гистограмм реальных потоков, получаемые для компьютерных сетей в результате измерений вычислительной нагрузки и потоков, свидетельствуют об их отличии от пуассоновских (т.е. потоки имеют непредсказуемый, стохастический характер). В представленной работе рассматривается модель случайного графа. Представим себе, что мы убрали все дороги с карты и оставили одни перекрестки. Тогда основываясь на рассмотренной в исследовательском разделе данной работы, теории перколяции, которая применяется, в основном для моделирования протекания жидкостей на абстрактных решетках, применим её к нашему случайному графу дорожной сети. Допустим, есть некое свойство дороги, например, износ. Но износ для данной дороги никак не зависит от совокупного износа остальных дорог. Надо определить какова максимальная вероятность q, при которой с вероятностью больше 1/2 не исчезнет возможность перемещения между любыми двумя городами? По существу, это вопрос о надежности транспортной сети: чем выше искомая вероятность q, тем, разумеется, сеть надежнее. Нетрудно заметить, что вопрос о надежности сети – это, в свою очередь, вопрос о связности случайного графа. Таким образом, нас интересует, какова минимальная вероятность исчезновение или появления связности нашего графа. Плавно переходим к модели представления графа в теории транспортных 459 потоков, к модели Эрдеша – Реньи. Пример эволюции транспортной сети и её характеристик сети по модели Эрдеша-Реньи приведен на рисунке 3. Рисунок 3 – Эволюция транспортной сети Связный подграф называется кластером. Кластер, в котором есть путь от верхней до нижней границы решетки, называется перколяционным. В бесконечной решетке перколяционный кластер бесконечен и единственен. Порог перколяции – доля занятых узлов, при которой возникает перколяционный кластер. В теории перколяции можно рассматривать прямую и обратную задачи. Прямая задача: Какова доля р занятых элементов решетки, при которой возникает путь от верхнего края до нижнего? Обратная задача: какую долю узлов (или связей) надо удалить (блокировать), чтобы перколяционный кластер распался на несвязные части. При достижении порога перколяции по узлам занятые узлы бесконечной решетки образуют кластеры всех размеров из связанных между собой узлов. Распределение кластеров по размерам следует степенному закону. Степенной закон означает, что отношение числа кластеров одного размера к числу кластеров другого размера зависит не от их размеров s, а лишь от отношения размеров. Таким образом, перколяционные кластеры самоподобны, или независимы от масштаба, на интервале от шага решетки до размера всей решетки. Математическая модель транспортной сети на основе стохастической динамики Можно показать, что если рассматривать изменение потоков машин, как случайный процесс и для каждого направления, каждого узла транспортной сети задано критически допустимое число машин в очереди Li,j то, можно определить вероятность P(Li,j, t) того, что к моменту времени t число машин в очереди не превысит Li,j (пробка не образуется). Пусть за некоторый интервал времени τ на j – перекресток, в i – направлении в очередь поступает ε машин и уезжает ξ машин. Весь процесс обработки будет складываться из отдельных шагов h имеющих 𝜀 𝜉 продолжительность τ, причём 𝜏 = λ – интенсивность входного потока, а 𝜏 = μ- интенсивность выходного потока машин. Обозначим через, Px-ε,h – вероятность того, что в очереди после h шагов работы находится (x-ε) машин, а Px,h – вероятность того что находятся x - машин и Px+ξ,h – вероятность того, что находится (x+ξ) машин. Тогда вероятность Px,h+1 (см. рис. 4.) того, что на h+1 шаге будет находится x машин будет равна: Рисунок 4 – Схема возможных переходов между состояниями, характеризующими число машин на j – перекрестке, в i – направлении на h+1 шаге работы светофора Px,h+1 = Px-ε,h + Px+ξ,h – Px,h, введем t=hτ, где t – общее время процесса обработки и получим: P(x,t+τ)=P(x-ε,t)+P(x+ ξ,t)-P(x,t). Раскладывая полученное уравнение в ряд Тейлора получим: 𝜕𝑃(𝑥,𝑡) 𝜏 2 𝜕 2 𝑃(𝑥,𝑡) 𝜕𝑃(𝑥,𝑡) 𝜀 2 𝜕 2 𝑃(𝑥,𝑡) 𝜕𝑃(𝑥,𝑡) 𝜉 2 𝜕 2 𝑃(𝑥,𝑡) 𝑃(𝑥, 𝑡) + 𝜏 𝜕𝑡 +2 𝜕𝑡 2 + ⋯ = 𝑃(𝑥, 𝑡) − 𝜀 𝜕𝑥 +2 𝜕𝑥 2 − ⋯ + 𝑃(𝑥, 𝑡) + 𝜉 𝜕𝑥 +2 𝜕𝑥 2 +⋯− 𝑃(𝑥, 𝑡). 460 Вторую производную по t можно исключить, поскольку по своему смыслу она описывает процесс, при котором сами машины могли бы быть источниками дополнительных машин. Учитывая в левой части члены, содержащие не более чем первую производную по t, а в правой не более чем вторую производную по x, получим: 𝜕𝑃(𝑥,𝑡) 𝜀 2 +𝜉 2 𝜕 2 𝑃(𝑥,𝑡) 𝜕𝑃(𝑥,𝑡) 𝜏 𝜕𝑡 = 2 𝜕𝑥 2 − (𝜀 − 𝜉) 𝜕𝑥 , 𝜕𝑃(𝑥,𝑡) 𝜆2 +µ2 𝜕 2 𝑃(𝑥,𝑡) 𝜕𝑃(𝑥,𝑡) 𝜕𝑡 = 2µ 𝜕𝑥 2 − (𝜆 − μ) 𝜕𝑥 . µ2 +𝜆2 Cчитая, что µ и λ не зависят от x и введя обозначение 𝑎 = 2µ и 𝑏 = 𝜆 − μ получим: 𝜕𝑃(𝑥,𝑡) 𝜕 2 𝑃(𝑥,𝑡) 𝜕𝑃(𝑥,𝑡) 𝜕𝑡 = 𝑎 𝜕𝑥 2 − 𝑏 𝜕𝑥 . Поскольку функция P(x,t) является непрерывной, то от вероятности P(x,t) можно перейти к плотности вероятности ρ(x,t) и сформулировать задачу с граничными условиями. При числе машин x=L в очереди на j – перекресток, в i – направлении, где L — некоторое критическое число, мы считаем, что узел обработки (j – перекресток, в i – направлении) становится перегруженным (образуется пробка). Сама вероятность обнаружить такое состояние будет отлична от 0, а плотность вероятности, определяющая поток машин в состоянии x=L необходимо положить равной 0 (мы стремимся избежать этого состояния), т.е. ρ(x,t)x=L=0 (a) Второе граничное условие выбираем исходя из того, что состояние x=0 определяет простой в обработке. Сама вероятность обнаружить такое состояние будет отлична от 0, однако плотность вероятности, определяющая поток машин в состоянии x=0 необходимо положить равной 0 (мы также должны стремиться избежать это состояние, т.к. оно соответствует случаю, когда светофор не закрывает данное направление, а это противоречит логике его работы), т.е. ρ(x,t)x=0=0 (b) Поскольку в момент времени t=0 (начало расчета) на обработке может находиться x0 -машин, то начальное условие зададим в виде: 1, 𝑥 = 𝑥0 𝜌(𝑥, 𝑡 = 0) = 𝛿(𝑥 − 𝑥0 ) = { 0, 𝑥 ≠ 𝑥0 Т.к. начальное условие задано в виде δ- функции, то это приводит к тому, что решение полученного дифференциального уравнения оставалось непрерывным в точке 𝑥 = 𝑥0 будет испытывать в ней разрыв производной. Основываясь на возможности применения рассмотренного подхода и используя методы операционного исчисления можно получить выражение для вероятности P(Li,j, x0|t) того, что к моменту времени t пробка не образуется (число машин в очереди не превысит Li,j): 𝑏𝑖,𝑗 𝐿𝑖,𝑗 2𝑏𝑖,𝑗 𝑥0 +𝑏2 2𝑎𝑖,𝑗 𝑥 𝐿𝑖,𝑗 −𝑥0 𝜋2 𝑛2 𝑎𝑖,𝑗 𝑡 𝑖,𝑗 𝑡 𝑒 sin(𝜋𝑛 0 )+sin(𝜋𝑛 ) − − 𝐿𝑖,𝑗 𝐿𝑖,𝑗 𝐿2 𝑃(𝐿𝑖,𝑗 , 𝑥0|𝑡) = 2𝑒 4𝑎𝑖,𝑗 ∑𝑀 𝑛=1(−1) 𝑛+1 𝑏2 2 𝑒 𝑖,𝑗 (1) 𝑖,𝑗 𝐿𝑖,𝑗 𝜋𝑛+ 4𝜋𝑛𝑎2 𝑖,𝑗 µ2 2 𝑖,𝑗 +𝜆𝑖,𝑗 Где 𝑎𝑖,𝑗 = 2𝜆𝑖,𝑗 и 𝑏𝑖,𝑗 = 𝜆𝑖,𝑗 − μ𝑖,𝑗 , µi,j –число машин выходящих из j-узла транспортной сети (перекресток/светофор) в i-направлении за единицу времени (выходной поток), λi,j – число машин входящих на узел за единицу времени (входной поток), t-время, x0-число машин в очереди в момент начала шага работы светофора. Решение уравнения (1) относительно времени t позволяет определить оптимальные интервалы времени включения светофоров. Однако это является ресурсоемкой вычислительной задачей. Учитывая, что вычисления нужно одновременно проводить для множества направлений и перекрестков, а также необходимо синхронизировать (см. уравнение (2)) на соседних перекрестках входящие и выходящие потоки машин, то для моделирования движения целесообразно использовать параллельные вычисления. 1 𝑟 𝑥0𝑘 𝑖,𝑗 = 𝑥0𝑘−1 𝑘−1 𝑘−1 𝑘−1 𝑘−1 𝑘 𝑘 𝑖,𝑗 + 𝑟 ∑𝑖−1(μ𝑖,𝑗 𝜏𝑖,𝑗 + 𝛥𝜆𝑖,𝑗 𝑇𝑖,𝑗 ) − μ𝑖,𝑗 𝑡𝑖,𝑗 (2) 𝑥0𝑘 𝑖,𝑗𝑉𝐷1 𝜆𝑘𝑖,𝑗 = . 𝑙𝑖,𝑗 Где 𝑥0𝑘−1 𝑖,𝑗 - число машин оставшихся не пропущенными на данном направлении i, данного j-перекрестка, после выполнения (k-1) шага, r – число входящих на перекресток направлений, μ𝑘−1 𝑖,𝑗 - потоки, выходящие на (k-1) шаге по каждому из r – направлений на выбранный перекресток. Любая из машин, из входящих на (k-1) шаге потоков, может равновероятно выбрать на следующем шаге k одно из направлений r, поэтому 1 перед знаком суммы стоит числовой коэффициент . 𝑇𝑖,𝑗 𝑘−1 - время, в течение которого выбранное 𝑟 направление было закрыто светофором (не время открытие, а время “цикла простоя”) между двумя 461 последовательными открытиями. Заметим, что открытие всех направлений на выбранном узле может происходить не в строго периодической последовательности. Порядок работы направлений может изменяться в зависимости от характера движения. Интервал времени между двумя последовательными открытиями одного и того же выбранного направления будет являться “циклом простоя”, величина которого 𝑇𝑖,𝑗 𝑘−1 может динамически изменяться. 𝛥𝜆𝑘𝑖,𝑗 - изменение входящего в выбранном направлении на выбранный узел потока машин, за время 𝑇𝑖,𝑗 𝑘−1 . Общее число машин в сети в любой момент времени суток соответствует функции числа машин от времени суток. 𝜏𝑖,𝑗 𝑘−1 - время в течение которого на (k-1) шаге были открыты входящие направления, пока выбранное исходящие направление было закрыто в течении времени 𝑇𝑖,𝑗 𝑘−1 . μ𝑘𝑖,𝑗 - поток, исходящий по выбранному направлению на шаге k, 𝑡𝑖,𝑗 𝑘 - интервал времени включения светофором, на шаге k, выбранного направления (величину которого необходимо определить при решении уравнения для определения вероятность P(Li,j, x0|t) того, что к моменту времени t число машин в очереди не превысит Li,j (пробка не образуется)). 𝑉𝐷1 -рекомендуемая скорость. Особенности графов большой размерности Отличительными особенностями графов, возникающих в современных приложениях, являются их большая размерность и разреженность. Ускорение работы любого из известных алгоритмов решения оптимизационных задач на графах может быть достигнуто за счет предобработки исходного графа. Технология предобработки реализуется, как правило, в виде двухфазной процедуры. На первой фазе производится предобработка графа путем его редуцирования или декомпозиции. Выбор вида предобработки определяется особенностями решаемой задачи и структурой графа. На второй фазе обычно применяется известный алгоритм решения задачи к преобразованному графу и формируется решение для исходного графа. При этом требуется, чтобы предобработка существенно снижала размерность задачи, обеспечивала корректность формирования решения задачи исходя из одного или нескольких решений, полученных для преобразованного графа, вычислительная сложность предобработки не превышала сложности решения рассматриваемой задачи на исходном графе. Реализация декомпозиционного подхода, то есть процесса выделения частей исходного графа, во многом зависит от структурных особенностей этого графа, в том числе от ограничений на параметры, характеризующие его разреженность. Один из параметров разреженности графа – ограничение на его древовидную ширину. Для графов с ограниченной древовидной шириной используется разложение графа кликовыми минимальными сепараторами. Идея такого разложения была предложена Р. Тарьяном как средство реализации принципа «разделяй и властвуй» для решения NP-трудных задач на графах, базирующихся на отношениях смежности вершин графа. Полученные в результате разложения части графа были названы атомами. Тарьяном установлено, что разложение графа на атомы не разрушает клики этого графа, не порождает новые клики и в этом смысле сохраняет его структуру. Алгоритм расчета порога перколяции графа транспортной сети 1. Задать значение вероятности блокировки узла p. 2. Разыграть состояние каждого узла при заданном значении p, и тем самым построить конкретную реализацию состояния сети. 3. Определить, есть ли в этой реализации хотя бы один стягивающий кластер (закритическое состояние или гигантский компонент, см. рис. 3). Если есть, то увеличить счетчик числа стягивающих кластеров M на единицу. 4. Повторить пункты 2-3 N раз. 5. Получить оценку вероятности образования стягивающего кластера/ 6. Повторить пункты 1-5 для ряда значений вероятности p в интервале от 0 до 1. Исходные данные для моделирования транспортной сети Одним из вопросов, возникающим при моделировании транспортной сети является выбор географических данных. Моделирование поведения транспорта на дорогах необходимо проводить не на случайных сетях дорог, а на уже существующих сетях, которые отличаются специфическим строением. При разработке программного обеспечения могут возникнуть проблемы, если структуры данных описывающие дороги городов будут неоднородными. Так же следует учитывать, что ведущие поставщики картографических данных защищают их исключительными правами и требуется приобретение лицензии на использование. Поэтому для реализации целей моделирования был выбран открытый, общедоступный онлайн ресурс OpenStreetMap (OSM). OpenStreetMap создан свободным сообществом картографов, которые добавляют и поддерживают данные о дорогах, улицах, объектах инфраструктуры, вокзалах и многих других объектах по всему миру. Участники сообщества используют аэрофотоснимки, GPS-устройства и низко технологичные карты для проверки того, что данные OSM являются точными и актуальными. Главная карта на OpenStreetMap.org использует ПО рендеринга и стиль со свободной лицензией, позволяющей скачать любую часть или всю карту OpenStreetMap для использования в режиме offline. 462 Опишем основные части структуры данных OSM, более подробно остановившись на принятых типах данных и их представлении их в пространственном виде. В целом, всю структуру данных OpenStreetMap можно представить схемой, показанной на рисунке 5. Рисунок 5 – Структура данных OpenStreetMap Все данные можно условно разбить на три основные группы: • Типы данных, описывающие в виде иерархической связи сам объект, как некую пространственную сущность, имеющую свой конечный результат — известные координаты всех частей объекта. • Иинформационная часть — это описательная характеристика объекта, не имеющая к пространственной географической структуре объекта прямого отношения (его название, физические, логические и прочие свойства). • Служебные атрибуты объекта, необходимые для организации процесса хранения и обработки информации в виде набора данных, такие как уникальный идентификатор, состояние объекта в базе, время последней правки объекта в базе и т.д. Базовые типы структур: • точка (node); • линия (way); • отношение (relation). Все объекты в OSM описываются этими тремя типами данных, после чего информационно наполняются комбинациями тегов. Модель данных в OSM строится на иерархической ссылочной структуре, из чего следует, что любой последующий тип данных не содержит информацию содержащуюся в предыдущих типах а образует новую сущность, ссылаясь на некое множество объектов предыдущего типа. Так же следует упомянуть, что любой объект имеет в структуре данных OSM свой идентификатор (ID), уникальный в пределах данного типа объектов. Именно по этому идентификатору и происходит ссылка на сам объект. Рассмотрим структуру базовых типов. Первый тип: точка (node) — это минимальный набор данных, который содержит в себе информацию о паре координат: широта, долгота (lat, lon) и является базовым в иерархической модели. Это единственный тип данных, который хранит саму географическую информацию — координаты, в виде широты и долготы. В XML нотации, объект данного типа будет выглядеть так: Второй тип данных: линия (way) — это совокупность указателей на объекты типа точка (node). Как минимум, линия состоит из одной точки, т.е. должна содержать как минимум одну ссылку на уже существующий объект типа точка. Правильная XML нотация объекта типа линия будет заключаться в описании всех необходимых точек, после чего следует сама запись о линии, в которой перечисляются все её точки. В простейшем варианте это будет выглядеть так: 463 Порядок перечисления точек в линии важен, он характеризует последовательность точек в линии и направление самой линии, т.е. у линии всегда есть начало и конец, даже если она замкнутая (в этом случае они просто совпадают). Таким образом, строится цельный граф объектов (чаще всего дорожный граф для расчёта роутинга), который представляет из себя совокупность объектов (линий), имеющих связь через их общие члены (точки). Если мы хотим создать такой граф из уже существующих точек 19 и 23, то мы опишем её так: Линии 24 и 48 можно графически представить в проекции меркартора следующим образом на рисунке 6 (Подписи на рисунке — id объектов: красные у точек, чёрные у линий; стрелкой указано направление линии, т.е. обе линии заканчиваются на точке 23). Рисунок 6 – Две линии Третий тип данных: отношения (relation). По сути, все объекты кроме точки — уже отношения, однако линии выделены в отдельный тип данных как наиболее распространённые, описывающие основные геометрические примитивы: линии, полилинии и полигоны. Для всех более сложных геометрических объектов, а также для объектов, являющихся не чисто геометрическими, а логическими (коллекции, списки, иерархии взаимосвязей) предназначен универсальный тип данных — отношения. В целом, описание отношения отличается от линии тем, что линия — это всегда совокупность точек, а отношение — это совокупность любых объектов, как точек и линий, так и других отношений. Следовательно, в отношениях указывается не только id объекта, но и его тип. В самом минимальном варианте отношение может содержать ссылку только на один объект. Ниже приведён пример самого распространённого отношения типа «мультиполигон», которое описывает один замкнутый внешний полигон из трёх точек с вырезанным из него замкнутым полигоном тоже из трёх точек меньшего размера. Графический вид мультиполигон представлен на рисунке 7. Рисунок 7 – Мультиполигон Так же как и у линии, у отношения порядок перечисления членов играет роль и учитывается при использовании этого отношения. Например, отношением может быть не геометрическая фигура, а маршрут общественного транспорта (логическая схема), тогда в него входят последовательно участки дорог, по которым будет двигаться автобус и список точек — остановки на которых он останавливается, следовательно порядок включения дорог в отношение показывает последовательность прохождения маршрута, а порядок остановок — последовательность их посещения. Объект relation может быть членом другого relation, при этом уровень вложенности и иерархия вверх ничем не ограничивается. Структурное ограничение заключается в том, что объект relation не может быть 464 членом самого себя, т.е. содержать ссылок на самого себя. Рекурсия в структуре типов данных в OSM недопустима, хотя конечно ничто не мешает создать такой объект и даже вполне успешно воткнуть его в базу данных. Архитектура программного обеспечения для моделирования процессов в транспортных сетях Одним из главных требований к разработке программного обеспечения для моделирования процессов в транспортных сетях является соответствие его функциональных возможностей требованиям конечного пользователя. Одной из основных целей является разработка методов предварительной обработки изображений и систем распознавания со средствами обучения и настройки, которые, с одной стороны, справятся с загрузкой сети дорог, а с другой, смогут быть использованы не только в разработанном комплексе, но и в других программах, решающих похожие задачи. В минимальный набор функций, необходимых для корректной работы программы входят: хранение информации (сети дорог, географических данных и связей), поиск информации, в частности, перекрестков и самих дорог, и отображение информации – результатов работы отдельных групп методов и частей программного комплекса. Разработанная модель представления данных в виде диаграммы классов представлена на рисунке 8. Рисунок 8 – Диаграмма классов модели Следует подчеркнуть, что главной задачей разработки программного комплекса являлось не создание многофункциональной программы, а сравнение и реализация методов расчета перколяции для задаваемой топологии сети с учетом стохастической динамики процессов. Ниже приведен список дополнительных функций, реализованных в программном комплексе. Возможность улучшения скорости обработки данных графа путем применения поразрядной сортировки. В программном комплексе предусмотрен вариант создания или повторной загрузки карты сети на основе нового или обновленного набора тестовых данных. Кроме того, в комплексе реализован интерфейс системы условной загрузки данных, для наглядного демонстрирования работы расчета перколяции. Повышение скорости загрузки крупных карт, например графа всех дорог Москвы. Перед непосредственной загрузкой данных граф подвергается предварительной обработке, обеспечивающей отсеивание огромного количества ненужных данных за короткий промежуток времени, которое поступит на вход соответствующей системы, тем самым значительно упрощая процесс распознавания и увеличивая его скорость. Кроме того, для пользователя предусмотрена возможность управления процессом загрузки, поскольку использование методов по умолчанию и автоматически подобранных значений не всегда приводят к желаемому результату. В то же время, при выборе ручного режима обработки пользователь может использовать такие методы и задать такие значения, которые позволят верно распознать изображение, чья автоматическая обработка привела к неудовлетворительному результату. Дизайн и эргономичность программы, отображение информации. Дизайн программного комплекса выполнен в едином стиле, пользователю доступна вся необходимая информация и функционал. 465 Интерфейс комплекса не перегружен функционалом, без которого пользователь может обойтись, а его простота позволяет облегчить работу с комплексом и повысить скорость получения результата. Структура программного комплекса, предназначенного для быстрой сортировки данных графа, представлена на рисунке 9. Таким образом, при разработке программного комплекса акцент, как и в ранних версиях или на стадии тестирования многих коммерческих продуктов, был сделан на быстродействие, информативность и простоту работы. Дизайн же комплекса может меняться по мере добавления новых функций до тех пор, пока его функционал не будет соответствовать требованиям конечного пользователя. В ходе работы был применен стандартный SAX-парсер, структура которого изображена на рисунке 10. Рисунок 9 – Диаграмма классов сортировки Рисунок 10 – SAX-парсер Алгоритм его работы изображен на рисунке 11. 466 Рисунок 11 – Алгоритм работы Соответственно была разработана абстрактная архитектура – “обёртка”, которая изображена на рисунке 12. Рисунок 12 – Архитектура – “обёртка” Для нахождения порога перколяции был применен алгоритм Union Find структура которого показана на рисунках 13 и 14. Рисунок 13 – Алгоритм работы Union Find 467 Рисунок 14 – Алгоритм работы Union Find В качестве инструментов были выбраны среда разработки Eclipse и язык программирования Java. В дальнейшем предполагается дополнение и расширение функционала всего программно- математического комплекса в целом. В частности, одним из вариантов расширения функционала может являться дополнение, позволяющее пользователю после копирования специализированного изображения в браузере вставлять результат распознавания в строку ввода, что позволит повысить удобство работы и сэкономить время пользователя. Заключение 1. Разработана модель описания в транспортных сетях стохастических потоков с недетерминированными характеристиками распределения статистических параметров, позволяющая описывать зависимость вероятности блокирования отдельных узлов от характеристик дорожного движения с течением времени. 2. В разработанной математической модели описаны правила обслуживания перекрестков (время переключения светофоров), учтен материальный баланс числа машин в системе и связи их потоков между соседними перекрестками. Предлагаемая модель позволяет, используя реальную карту транспортной сети создать её динамическую модель, эмулировать её работу и возникновение пробок. 3. Использование методов теории перколяции и результатов разработанной стохастической модели транспортных потоков позволяет моделировать работу транспортной сети не только на уровне отдельных узлов, но и всей структуры в целом. 4. Моделирование дорожной ситуации с «управляемыми», согласно предлагаемой модели временами переключения, светофоров и с жёстко заданными режимами переключения («классическое движение») показывает снижение числа пробок при использовании разработанной модели «регулируемых» светофоров по сравнению с моделью «классическое движение». 5. При моделировании транспортных потоков может быть использован технологический подход, основанный на перколяционных моделях транспортных систем, загрузки карт в формате Open Street Map (OSM), построении графа дорожной сети с указанием свойств (классов данных объектов) дуг (дорога) и вершин (перекресток) и набор объектов для отображения их в графической форме с целью вычисления величин порогов перколяции для существующей системы и предлагаемых решений и выбора наиболее оптимальной структуры транспортной сети, при минимизации финансовых затрат на дорожное строительство. 6. Разработана структура и программное обеспечение комплекса моделирования процессов в транспортных сетях на основе перколяционной стохастической модели и описана алгоритмическая реализация основных функциональных возможностей его работы. Благодарности Работа выполнена при финансовой поддержке Российского фонда фундаментальных исследований (РФФИ), грант № 16-37-00373 мол_а, «Разработка перколяционных и стохастических моделей балансировки потоков и управления высоконагруженными транспортными сетями». Acknowledge The work was supported by the Russian Foundation for Basic Research (RFBR), Grant No. 16-37-00373 mole_a, "Development of percolation and stochastic models of flow balancing and management of highly loaded transport networks". 468 References 1. Shvecov V.I. Matematicheskoe modelirovanie transportnyh potokov. // Avtomatika i Telemekhanika 2003, № 11, s. 3–46. 2. Gasnikov A.V., Klenov S.L., Nurminskij E.A., Holodov YA.A., SHamraj N.B. Vvedenie v matematicheskoe modelirovanie transportnyh potokov. Moskva, Izdatel'stvo MCNMO, 2013, 428 s. 3. Klejnok L. Teoriya massovogo obsluzhivaniya. Per. s angl. I.I. Grushko. Pod red. V. I. Nejmana. – M.: Mashinostroenie. 1979. 4. Klejnok L. Vychislitel'nye seti s ocheredyami. Per s angl. – M.: Mir. 1979. 5. Kofman A., Kryuon R. Massovoe obsluzhivanie (teoriya i prilozheniya). / Per. s fr. pod red. I.N. Kovalenko. M.: Mir, 1965. – 302 s. 6. Kulagin V.P. Modelirovanie struktur parallel'nyh vychislitel'nyh sistem na osnove setevyh modelej: Uchebnoe posobie. – Moskva: Moskovskij gosudarstvennyj institut ehlektroniki i matematiki (tekhnicheskij universitet), 1998. – 102 s.: il. 62, tabl. 4, bibliogr. 78 nazv. 7. Voevodin V.V. Matematicheskie modeli i metody v parallel'nyh processah. – M.: Nauka. Gl. red. Fiz.-mat. Lit., 1986. 8. Zade L.A. Ponyatie lingvisticheskoj peremennoj i ego primenenie k prinyatiyu priblizhennyh reshenij. M.: Mir, 1976. – 164 s. 9. Nechetkie mnozhestva i teoriya vozmozhnostej (poslednie dostizheniya) / Pod red. R. YAger; Per. s angl. pod red. S.I. Travkina. – M.: Radio i svyaz', 1986. – 406 s. Литература 1. Швецов В.И. Математическое моделирование транспортных потоков. // Автоматика и Телемеханика 2003, № 11, с. 3–46. 2. Гасников А.В., Кленов С.Л., Нурминский Е.А., Холодов Я.А., Шамрай Н.Б. Введение в математическое моделирование транспортных потоков. Москва, Издательство МЦНМО, 2013, 428 с. 3. Клейнок Л. Теория массового обслуживания. Пер. с англ. И.И. Грушко. Под ред. В. И. Неймана. – М.: Машиностроение. 1979. 4. Клейнок Л. Вычислительные сети с очередями. Пер с англ. – М.: Мир. 1979. 5. Кофман А., Крюон Р. Массовое обслуживание (теория и приложения). / Пер. с фр. под ред. И.Н. Коваленко. М.: Мир, 1965. – 302 с. 6. Кулагин В.П. Моделирование структур параллельных вычислительных систем на основе сетевых моделей: Учебное пособие. – Москва: Московский государственный институт электроники и математики (технический университет), 1998. – 102 с.: ил. 62, табл. 4, библиогр. 78 назв. 7. Воеводин В.В. Математические модели и методы в параллельных процессах. – М.: Наука. Гл. ред. Физ.-мат. Лит., 1986. 8. Заде Л.А. Понятие лингвистической переменной и его применение к принятию приближенных решений. М.: Мир, 1976. – 164 с. 9. Нечеткие множества и теория возможностей (последние достижения) / Под ред. Р. Ягер; Пер. с англ. под ред. С.И. Травкина. – М.: Радио и связь, 1986. – 406 с. Об авторах: Лесько Сергей Александрович кандидат технических наук, доцент, доцент кафедры моделирования и управления систем института комплексной безопасности и специального приборостроения, Московский технологический университет (МИРЭА), sergey@testor.ru Алёшкин Антон Сергеевич кандидат технических наук, доцент, доцент кафедры автоматизированных систем управления института комплексной безопасности и специального приборостроения, Московский технологический университет (МИРЭА), antony@testor.ru Барков Андрей Александрович студент кафедры моделирования и управления систем института комплексной безопасности и специального приборостроения, Московский технологический университет (МИРЭА), andrey@testor.ru Note on the authors: Lesko Sergey A., Candidate of Technical Sciences, Associate Professor of Department of Modeling and Control Systems, Institute of Complex Security and Special Instrumentation, Moscow Technological University (MIREA), sergey@testor.ru Alyoshkin Anton S., Candidate of Technical Sciences, Associate Professor of the Department of Automated Control Systems, the Institute of Complex Security and Special Instrumentation, Moscow Technological University (MIREA), antony @ testor.ru Barkov Andrey A., the student of the Department of Modeling and Control Systems of the Institute of Comprehensive Security and Special Instrumentation, Moscow Technological University (MIREA), andrey@testor.ru 469