Алгоритм управления транспортными потоками

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

3. Сервисов для предотвращения образования автомобильных “пробок”

1. Описание  сервисов

1. Сервисы моделирования и  управления движением  транспорта в транспортной сети

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

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

     модель  случайного движения машин в городе "классическое движение";

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

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

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

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

2. Сервис  информационной поддержки  участников дорожного  движения.

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

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

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

     

     Рис. 2. Схема общей  структуры сервисов.

     На  рисунке 2 представлена общая структура  сервисов. Основой системы является «Центр обработки данных» (ЦОД), он представляет собой вычислительный комплекс на который  поступают данные с источников данных о дорожной ситуации, ими могут быть как собственные датчики и камеры, так и услуги предоставляемые сторонними компаниями. В ЦОД производится моделирование, и выдаются данные на Сервис №1 (Сервисы моделирования и управления транспортной сетью) который предоставляет услуги по выдаче рекомендаций службам управления транспортными потоками.

     Сервис  №2 (Сервис информационной поддержки  участников дорожного движения) также  получает данные из ЦОД и предоставляет  услуги клиентам о текущей загруженности  дорог, прогноз развития дорожной ситуации и информацию о прокладке маршрутов  на основе прогнозов.

2. Математическая  модель управления транспортной сетью

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

     Моделирование процессов обработки и передачи данных в сетях с регулярной и  произвольной топологией и произвольным законом распределения интервалов времени поступления заявок, описано  в работах [1-7]. Используя некоторые из развитых в этих работах подходы можно показать, что если рассматривать изменение потоков машин, как случайный процесс и для каждого направления, каждого узла транспортной сети задано критически допустимое число машин в очереди L_i,j то, можно определить вероятность P(L_i,j, t) того, что к моменту времени t число машин в очереди не превысит L_i,j (пробка не образуется).

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

     Обозначим через, P_x-ε,h - вероятность того, что в очереди после h шагов работы находится (x-ε) машин, а P_x,h - вероятность того что находятся x- машин и P_x+ξ,h - вероятность того, что находится (x+ξ) машин. Тогда вероятность P_x,h+1 (см. рис.3.) того, что на h+1 шаге будет находится x машин будет равна:

     

     Рис. 3. Схема возможных  переходов между  состояниями, характеризующими число машин на j - перекрестке, в i - направлении на h+1 шаге работы светофора.

     P_x,h+1 = P_x-ε,h + P_x+ξ,h - P_x,h

     введем  t=hτ, где t - общее время процесса обработки и получим:

     P(x,t+τ)=P(x-ε,t)+P(x+ ξ,t)-P(x,t)

     Раскладывая полученное уравнение в ряд Тейлора  получим:

     

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

     

     

     Cчитая, что µ и λ не зависят от x и введя обозначение и получим:

     

     Поскольку функция 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 (начало расчета) на обработке может находиться x₀ -машин, то начальное условие зададим в виде:

     

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

     Основываясь на возможности применения рассмотренного подхода и используя методы операционного  исчисления можно получить выражение  для вероятности P(L_i,j, x₀|t) того, что к моменту времени t пробка не образуется (число машин в очереди не превысит L_i,j):

      (1)

     Где и , µ_i,j -число машин выходящих из j-узла транспортной сети (перекресток/светофор) в i-направлении за единицу времени (выходной поток), λ_i,j - число машин входящих на узел за единицу времени (входной поток), t-время, x₀-число машин в очереди в момент начала шага работы светофора.

     Решение уравнения (1) относительно времени  t позволяет определить оптимальные интервалы времени включения светофоров. Однако это является ресурсоемкой вычислительной задачей. Учитывая, что вычисления нужно одновременно проводить для множества направлений и перекрестков, а также необходимо синхронизировать (см. уравнение (2)) на соседних перекрестках входящие и выходящие потоки машин, то для моделирования движения целесообразно использовать параллельные вычисления.

      (2)

     

     Где - число машин оставшихся не пропущенными на данном направлении i, данного j-перекрестка, после выполнения (k-1) шага, r - число входящих на перекресток направлений, - потоки, выходящие на (k-1) шаге по каждому из r - направлений на выбранный перекресток. Любая из машина, из входящих на (k-1) шаге потоков, может равновероятно выбрать на следующем шаге k одно из направлений r, поэтому перед знаком суммы стоит числовой коэффициент . - время, в течении которого выбранное направление было закрыто светофором (не время открытие, а время "цикла простоя") между двумя последовательными открытиями. Заметим, что открытие всех направлений на выбранном узле может происходить не в строго периодической последовательности. Порядок работы направлений может изменяться в зависимости от характера движения. Интервал времени между двумя последовательными открытиями одного и того же выбранного направления будет являться "циклом простоя", величина которого может динамически изменяться. - изменение входящего в выбранном направлении на выбранный узел потока машин, за время . Общее число машин в сети в любой момент времени суток соответствует функции числа машин от времени суток. - время в течение которого на (k-1) шаге были открыты входящие направления, пока выбранное исходящие направление было закрыто в течении времени . - поток исходящий по выбранному направлению на шаге k, - интервал времени включения светофором, на шаге k, выбранного направления (величину которого необходимо определить при решении уравнения для определения вероятность P(L_i,j, x₀|t) того, что к моменту времени t число машин в очереди не превысит L_i,j (пробка не образуется)). -рекомендуемая скорость.

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

     

     Рис.4. Загруженность дорог  Москвы в течение  одного из рабочих  дней (кривая 1 - осень 2006 года, кривая 2 - осень 2007 года). Загруженности  в 10 условных единиц (баллов) соответствует случай, когда все зарегистрированные в Москве и ближнем  Подмосковье машины оказываются на дорогах. По статистике осень  является наиболее загруженным  периодом года.