Клеточные автоматы для моделирования транспортных потоков

Аннотация

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

1. Введение

Моделирование транспортных потоков является важным шагом в разработке и контроле транспортных систем. Несмотря на это значение, в существующей литературе до сих пор не предлагают всеобъемлющую модель, которая способна охватывать всю сложность реального трафика. Цель этой статьи является изучение новой парадигмы моделирования, клеточных автоматов (КА), которые появились в последние несколько лет, как очень перспективные альтернативы существующих моделей движения транспортных потоков [2, 7, 14, 16]. Модели КА умеют захватывать микро-уровень динамики и связывать их с поведением макро потока уровня трафика. Это отличие от существующих моделей, которые либо включены в лечение транспортного потока (макроскопической модели) или подробные и ограниченные по своим масштабам (микроскопические модели). Модели сотовых автоматов способны явно представлять индивидуальные взаимодействия транспортных средств и соотнести их взаимодействия в макроскопических показателях транспортных потоков, таких как пропускная способность, время в пути, и скорость автомобиля. Различные транспортные средства, обладают различным дорожным поведением (разгон/торможение, правила изменения полос, время реакции и др.), модель КА может более адекватно охватить всю сложность реального дорожного движения. Модель КА, будучи либо детерминированным или стохастической, может быть более эффективным в учете, присущего изменчивости в наиболее реальном трафике. В свою очередь, это позволяет характеризовать не только средние значения метрик потока, но также их высшие моменты (например, дисперсии). Наконец, модели КА поддаются решению как одно- так и многополосного трафика, что особенно важно для моделирования автомобильных дорог.

В данной работе мы будем опираться на пионерской работе Nagel и его коллег [7, 8, 10, 11, 15], которые были в числе первых, кто признал полезность клеточных автоматов для моделирования транспортных потоков. Их модели были расширены несколькими другими в последние несколько лет [2, 5, 6, 13, 14]. Тем не менее, большинство существующих моделей были сосредоточены на описании отношения между первых моментов транспортных потоков. В этой статье мы рассмотрим поведение высших моментов этих показателей. Мы покажем, что поведение этих высших моментов не только удивительно, но и имеют важное значение для проектирования и контроля транспортных систем. Для детерминированных систем, исследуется феномен периодичности. Покажем, что, в общем, движения транспортных потоков является периодическим с конечным периодом длины. Мы покажем, что знание этого периодического поведения может быть очень полезным в разработке автоматизированных систем проезжей части и контроля.

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

2. Транспортный поток, моделирование в области литературы

Модели транспортного потока можно разделить на две основные категории: микро- и макроскопического. Макроскопические модели обеспокоены описанием совокупного поведения трафика, характеризуя основные отношения между скоростью автомобиля, расхода и плотности. Пример макроскопической модели включает вход/выход, простой континуум, и более высокий континуум порядка [4].

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

3. Клеточные автоматы для однополосного транспортного потока

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

Наша первоначальная модель трафика определяется как одномерный массив с L клеток с закрытыми (периодическими) граничными условиями. Это означает, что общее число транспортных средств N в системе поддерживается постоянно. Каждая ячейка (слот) может быть занят одним транспортного средством, или оно может быть пустым. Каждая ячейка соответствует сегменту автодороги протяженностью l, равной средней пробки. Плотность трафика задается p = N / L. Каждое транспортное средство может иметь скорость от 0 до Vmax. Скорость соответствует количеству слотов, которые достигаются в одну итерацию. Движение транспортных средств через клетки определяется набором правил. Эти правила применяются параллельным образом на каждом транспортном средстве на каждой итерации. Длина итерации может быть произвольно выбрана с учетом требуемого уровня детализации моделирования. Выбор в достаточно малом интервале итерации, таким образом, может быть использован, чтобы приблизить систему непрерывного времени. Состояние системы на итерации определяется распределением транспортных средств между клетками и скорости каждого транспортного средства в каждой ячейке. Мы используем следующие обозначения для характеристики каждого состояния системы:

х (i): Положение i-го автомобиля,

v (i): скорость i-го транспортного средства, и

g (i): разрыв между i-й и (i +1)-го автомобиля (т.е. транспортного средства непосредственно перед) и задается g (i) = х (i + 1) - х (i) - 1.

3.1 Детерминированный клеточный автомат

В детерминированной одной модели полоса, движение транспортного средства определяется следующим набором обновлении правил:

1. Ускорение свободного автомобиля: Если v(i) < vmax и g(i) > v(i) + 1, тогда v(i) = v(i) + 1.
2. Замедление из-за других транспортных средств: Если v(i) > g(i) - 1, тогда v(i) = g(i).
3. Движение автомобиля: Автомобиль является передовой v(i) слота.

Эти обновления правил сначала были предложены Nagel [7], а затем используется во многих вариациях другими [5, 6, 14, 16]. Согласно этим правилам, все автомобили имеют одинаковые поведения и подчиняются максимальной скорости. Как мы обсудим позже, эти предположения могут быть легко опровергнуты. Например, различные транспортные средства могут иметь различные максимальные скорости. Разрывы между транспортными средствами также может быть автомобиль-зависимыми. Самопроизвольное ускорение и замедление также могут быть включены путем введения случайных ускорений и замедлений (см. раздел 3.2).

В течение моделирования, мы используем максимальный скорости Vmax = 5 клеток/итерацию. Мы позволяем каждой итерации соответствовать одной секунде. Длина каждой ячейки берется 7,5 метров, которая включает среднюю длину автомобиля и разрыв между двумя соседними автомобилями в пробке [7]. Таким образом, транспортные средства дискретные на скоростной v0 = 0 км / ч, v1 = 27 км / ч, v2 = 54км / ч, ..., и Vmax = 135 км / ч. Это масштабирование не единственное. Например, мы могли бы зафиксировали максимальную допустимую скорость, а затем получить продолжительность каждой итерации. Другие стратегии время масштабирования также возможны (см. раздел 4).

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

Моделирование основано на системе 300 клеток оценивали через 10 000 итераций (примерно 2,8 часа) для различных уровней плотности. Для каждого уровня плотности, были получены различные меры потока трафика (например, пропускная способность, средняя скорость, скорость дисперсия, трафик периодичность и т. д.). Можно сделать ряд интересных наблюдений:

• Максимальный расход 3000 автомобилей / час достигается при Vmax = 0,1667, за которой становится линейной снижение плотности (обратно путешествия старт-стоп волны). Такое поведение согласуется с эмпирическими наблюдениями фактического трафика [4] (более точное приближение обеспечивается стохастической версией модели, представленной в разделе 3.2).
• В фазе ламинарного потока, средняя скорость сходится к максимальной скорости Vmax. Средняя скорость становится убывающей функцией плотности для трафика плотности больше, чем Vmax. Эти результаты, опять же, не удивительны, и согласуются с имеющимися эмпирическими данными. Однако удивительно поведение скорости дисперсии. Существует максимальное отклонение плотности, которое происходит после максимальной плотности пропускной способности. Таким образом, область максимального потока также область максимальной разницы. Следует отметить, что на этапе ламинарного потока, скорость дисперсии является незначительной, но начинает возрастать с наступлением максимального потока. Первоначальное увеличение имеет существенную неоднородность в функции дисперсия плотности (например, добавление одного транспортного средства в системе с плотностью Vmax, увеличивает дисперсию 19 раз). Высокая скорость дисперсия означает, что различные транспортные средства в системе уже имеют разную скорость. Это также означает, что транспортное средство будет испытывать частые изменения скорости за поездку через систему. В свою очередь, это может привести к более высокого отключения времени в пути. На самом деле, это может также увеличить вероятность дорожно-транспортных происшествий. Таким образом, кажется разумным, попытаться направить трафик от плотности максимального потока. Рекомендации об этом, идут вразрез с преобладающей практикой, где целью является то, чтобы максимизировать поток.
• Потому что мы считаем, детерминированный и конечный КA модель с периодическими границами, соответствующая транспортная система является периодической в своих состояниях системы. То есть, число итераций, необходимых, чтобы вернуть то же состояние. Длина периода является незначительной для плотностей ниже максимальных плотностей потоков. Однако длина периода может быть значительно больше высоких плотностей. Удивительно, но длина периода не является монотонной по интенсивности движения. В самом деле, либо увеличение или уменьшение длины периода может произойти при увеличении плотности. Что еще более важно, небольшие изменения в плотности может привести к значительным колебаниям в длину периода.

Наконец, следует отметить, что для детерминированной модели КA, можно получить аналитические выражения для средней скорости и среднего расхода. Средняя скорость в фазе ламинарного потока Vmax, в то время как на фазе, он задается у = (1 - p) / p. Средний поток можно рассчитать как J=pv. Максимальная плотность потока происходит на пересечении двух фаз. Это приводит к pmax = 1 / (1 + Vmax). Однако получение аналитических выражений для высших моментов потока или скорости трудно. Кроме того, трудно аналитически характеризовать длину периода.

3.2 Стохастические клеточные автоматы

Детерминированная модель КA не отражает присущую случайность в поведении автомобилей в условиях реального дорожного движения. В частности, он не учитывает недетерминистическое ускорение и замедление, присущее изменчивости скорости автомобиля, и автомобиль на реакции при замедлении. Это стохастичность может быть, в частности, захвачена добавлением правил рандомизации до трех обновлений правил на каждой итерации модели КA. Правило рандомизации применяется после первых двух правил и результатов в снижении скорости каждого автомобиля на один с некоторой вероятностью р (т.е., если у> 0, то V = V - 1 с вероятностью р, 0 < р < 1).

Моделирование проводится более 10000 итераций, первые 1000 из которых исключены из рассмотрения (переходный период). Результаты аналогичны результатам, полученным для детерминированного случая, с тем важным исключением, что поток, в зависимости от плотности, не является непрерывным в течение задней бегущей фазы. Такое поведение снова согласуется с наблюдаемой в реальном мире движения. Большинство наших предыдущих наблюдений можно обобщить на стохастическом случае. Это еще раз подчеркивает, что плотность максимального потока находится в области от плотности максимальной скорости дисперсии. Таким образом, трафик при более низких плотностях должен осуществляться по мере возможности. Например, в нашей моделируемой системе, работающей при плотности, что уменьшает максимальный поток на 6% снижает скорость дисперсии более чем на 105 %.

Когда изменчивость является высокой (например, р = 0,5 ), снижение может быть значительным. Изменчивость также снижает среднюю скорость и продолжительность фазы ламинарного потока. Заметим, что для высокой изменчивости, средняя скорость на этапе ламинарного потока меньше максимально выполнимой скорости Vmax. Кроме того, изменчивость уменьшает среднюю скорость и снижает плотность, при которой максимальная скорость дисперсии возникает. Однако, интересно отметить, что частичное сокращение изменчивости (т.е. меньше, р) приводит только ограниченное снижение скорости дисперсии. Это означает, что наличие любой изменчивости количество является достаточным привести к высокой скорости дисперсии. Наши данные согласуются с результатами, полученными Nagel и др. проведенных несколько подобных экспериментов [10].

3.3 Стохастические клеточные автоматы для двух полосного транспортного потока

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

Нагатани первый рассмотрел КA модель в две полосы движения [6]. Его начальная модель была детерминированной и использовала Vmax = 1. Однако эта модель привела к ситуации, когда блоки нескольких автомобилей двигались вперед. Позже эта ошибка была исправлена путем введения случайности в смене полосы движения. Основываясь на модели Нагатани, в Риккерт и др.. [13] рассмотрена модель с Vmax < 1. Эти модели служат в качестве основы для модели, представленной здесь.

4. Время масштабирования

Как мы уже упоминали в разделе 3, стратегии масштабирования возможны. Нагель и Шрекенберг [11] определили три различные схемы для интерпретации шкал времени моделирования. Первая схема основана на максимально допустимой скорости и предопределенной длины каждой ячейки. Затем они используются для вычисления продолжительности каждой итерации. Вариация на этой схеме была использована в данной работе. Вторая схема масштабирует модель с учетом диаграммы плотности. Используя известную максимальную емкость, соответствующую длину итерации можно рассчитать. Таким образом, одна итерация соответствует 0,68 секунды. Третья схема использует известное значение для скорости фазы, чтобы получить длину итерации. В нашей моделируемой стохастической системе, моделируемая максимальная скорость во время обратной бегущей фазы 0,38 слоты/итерация, что означает, что одна итерация снова соответствует 0,68 секунды. Другие схемы масштабирования по времени также могут быть возможными. Тем не менее, характер макроскопических идей, полученных в результате моделирования не влияют на этих временных масштабах.

5. Обсуждение и вывод

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

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

Список источников

1. Biham, O., Middleton, A. and D. Levine, "Self-Organization and a Dynamical Transition in Traffic Flow Models," Physical Review A, Vol. 46, No. 10, pp. 6124-6127, 1992.
2. Blue, V., Bonetto, F. and M. Embrechts, "A Cellular Automata of Vehicular Self Organization and Nonlinear Speed Transitions," Transportation Research Board Annual Meeting, Washington, DC, 1996.
3. FRESIM User Guide, Version 4.5, Federal Highway Administration, US Department of Transportation, Washington, DC, 1994.
4. Gerlough, D. L. and M. J. Hunber, Traffic Flow Theory - A Monograph, Transportation Research Board National research Council, Special Report 165, 1991.
5. Nagatani, T., "Jamming Transition in the Traffic Flow Model with Two-Level Crossings," Physical Review E, Vol. 48, No. 5, pp. 3290-3294, 1993.
6. Nagatani, T., "Self Organization and Phase Transition in the Traffic Flow Model of a Two-Lane Roadway," Journal of Physics A, Vol. 26, pp. 781-787, 1993.
7. Nagel, K., "Particle Hopping Models and Traffic Flow Theory," Physical Review E," Vol. 3, No. 6, pp. 4655-4672, 1996.
8. Nagel, K., Barrett, C. L. and M. Rickert, "Parallel Traffic Micro-Simulation by Cellular Automata," Transportation Research C, submitted, 1996.
9. Nagel, K. and H. Hermann, "Deterministic Models for Traffic Jams," Physica A, Vol. 199, pp. 254-263, 1993.
10. Nagel, K. and S. Rasmussen, "Traffic at the Edge of Chaos," Proceedings of the Fourth International Workshop on the Synthesis and Simulation of Living Systems, MIT Press, pp. 222-235, 1994.
11. Nagel, K. and M. Schreckenberg, "A cellular Automaton Model for Freeway Traffic," Journal de Physique, Vol. 2, pp. 2221-2229, 1992.
12. Rathi, A. K. and and A. J. Santiago, "The New NETSIM Simulation Program," Traffic Engineering and Control, pp. 317-320, 1990.
13. Rickert, M., Nagel, K., Schreckenberg, M. and A. Latour, "Two Lane Traffic Simulations using Cellular Automata," Physica A, submitted, 1995.
14. Schadschneider, A. and M. Schreckenberg, "Cellular Automaton Models and Traffic Flow," Journal of Physics A, Vol. 26, pp. 679-683, 1993.
15. Schreckenberg, M., schreckenberg, A., Nagel, K. and N. Ito, "Discrete Stochastic Models for Traffic Flow, Physical Review E, Vol. 51, No. 4, pp 2939-2949, 1995.
16. Villar, L. and A. de Souza, "Cellular Automata Models for General Traffic Conditions on a Line," Physica A, Vol. 211, pp. 84-92, 1994.
17. Wolfram, S., Theory and Applications of Cellular Automata, World Scientific, New York, NY, 1986.