«Факультет_Информационных технологий и программирования Направление_Прикладная математика и информатика_ Математическое моделирование_ Специализация Магистр математики Академическая степень КафедраКомпьютерных ...»

МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ

САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ, МЕХАНИКИ И ОПТИКИ

Факультет_Информационных технологий и программирования

Направление_Прикладная математика и информатика_

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

Специализация

Магистр математики Академическая степень КафедраКомпьютерных технологий_Группа6538

МАГИСТЕРСКАЯ ДИССЕРТАЦИЯ

на тему Моделирование дорожного движения на многополосной магистрали при помощи двумерного вероятностного клеточного автомата с тремя состояниями Автор магистерской диссертации Котов А.Н.

Научный руководитель _Николенко С.И.

Санкт-Петербург, 2008 г.

ВВЕДЕНИЕ

ГЛАВА 1. ОБЗОР СУЩЕСТВУЮЩИХ МОДЕЛЕЙ ДОРОЖНОГО ДВИЖЕНИЯ

1.1. Актуальность проблемы моделирования пробок

1.2. Классификация методов моделирования дорожного движения

1.2.1. Макромоделирование

1.2.2. Микромоделирование

1.2.3. Мезомоделирование

1.3. Микромодели дорожного движения

1.3.1. Модель оптимальной скорости

1.3.2. Модель Видеманна

1.3.3. Модель умного водителя

1.4. Моделирование траффика при помощи клеточных автоматов

1.4.1. Правило 184

1.5. Выводы

ГЛАВА 2. МОДЕЛЬ МНОГОПОЛОСНОЙ МАГИСТРАЛИ

2.1. Описание математической модели

2.1.1. Модель дорожного полотна

2.1.2. Возможные состояния для клетки

2.1.3. Состояние клеточного автомата

2.1.4. Динамика клеточного автомата

2.1.5. Правила перехода

2.1.6. Описание экземпляра модели

2.1.7. Функционалы от состояния дороги

2.1.8. Глоссарий

2.2. Базовый экземпляр модели

2.2.1. Базовый экземпляр модели

2.2.2. Базовое начальное состояние

2.3. Программирование модели

2.3.1. Формат файла для сохранения экземпляра модели

2.3.2. Формат файла для сохранения состояния модели

2.3.3. Архитектура программы

2.4. Демонстрация дорожного движения

2.5. Выводы

ГЛАВА 3. ИССЛЕДОВАНИЕ НА МОДЕЛИ

3.1. Задачи моделирования

3.2. Зависимость средней скорости движения от числа машин

3.3. Вопрос о парковке в крайнем правом ряду

3.4. Исследование влияния погоды на образование пробок

3.5. Направления для дальнейших исследований

3.5.1. Серия планируемых экспериментов

3.5.2. Ограничения модели

3.6. Выводы

ЗАКЛЮЧЕНИЕ

ИСТОЧНИКИ

ВВЕДЕНИЕ

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

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

Основными подходами, применяемыми при моделировании пробок, являются макромоделирование, которое изучает движение дорожного движения подобно течению частиц в гидродинамике, а также микромоделирование, которое рассматривает каждый автомобиль в потоке индивидуально. С момента публикации работы [1] в 1992-м году основной парадигмой построения микромоделей дорожного движения стал механизм с использованием клеточного автомата для представления состояния дорожного полотна.

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

• клеточный автомат в данной работе двумерный, а не одномерный; модель изменения состояний в клеточном автомате подобна игре «жизнь» [2];

• множество возможных состояний для каждой клетки автомата расширено за счет введения дополнительного состояния «препятствие»;

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

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

• Каким образом средняя скорость движения по автомагистрали зависит от концентрации автомобилей на ней?

• В какой степени припаркованные в правом ряду автомобили уменьшают среднюю скорость движения на дороге?

• При какой вероятности дорожно-транспортного происшествия (ДТП) на автомагистрали движение на ней перестает быть свободным?

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

ГЛАВА 1. ОБЗОР СУЩЕСТВУЮЩИХ МОДЕЛЕЙ ДОРОЖНОГО

ДВИЖЕНИЯ

1.1. Актуальность проблемы моделирования пробок Уже на протяжении нескольких лет все серьезнее встает проблема большого количества автотранспорта в городе, крупных «пробок» на дорогах и, как следствие, серьезных экономических и временных затрат. Причин подобного явления несколько:

большое число «автолюбителей» – людей использующих частный автотранспорт для перемещения по городу;

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

концентрация индустриальных зон (склады, заводы, промышленные базы) в черте города, между историческим центром и «спальными» районами, сложившаяся естественным образом в процессе расширения города – дороги нагружаются грузовым транспортом;

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

неоптимальность дорожной разметки, знаков, режима работы светофоров;

неопытность водителей: согласно разработанной командой европейских математиков теории, дорожный затор может образоваться из-за резкого торможения и связанных с ним особенностей человеческого восприятия [3].

Для решения подобных проблем в различных источниках независимыми обозревателями и аналитиками предлагаются различные мероприятия, направленные на различные сферы жизни общества [4–7]:

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

различного рода ограничения, направленные на сокращение количества автомобилей: взимание платы за въезд, ограничение стоянок, ограничение въезда;

пропаганда альтернативных средств перемещения: велосипедов, мотороллеров, мотоциклов.

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

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

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

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

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

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

1.2.1. Макромоделирование Макромоделирование [15] — тип моделирования, основывающийся на применении к автомобильному трафику законов гидродинамики, по аналогии с жидкостью в трубе. Как следствие, такой тип моделирования выражается в написании систем дифференциальных уравнений в частных производных, сформулированных относительно интересующих величин — например, плотности потока автомобилей или их средней скорости. Симуляция дорожного движения и наблюдения в реальном времени показали, что в плотном, но свободном трафике пробки могут возникать спонтанно, зачастую из-за малозначимых событий (так называемый «эффект бабочки»), в частности, из-за резкого торможения единственного водителя. Такую ситуацию часто сравнивают с внезапным замерзанием переохлажденной жидкости [13]. Впрочем, в отличие от жидкости, автомобильный трафик подвержен влиянию сигналов (знаки, светофоры) и других событий (особенно на развязках), которые периодически затрагивают движение. Модели матриц энтропии учитывают этот эффект, группируя транспорт и добавляя случайную составляющую к шаблонам движения трафика на отдельных участках дорожной сети.

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

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

1.2.3. Мезомоделирование Кинетическое (мезо-) моделирование [14] — третий способ моделирования, находящийся между первыми двумя. Предлагается определить функцию f(t, x, V), которая выражает вероятность нахождения автомобиля, движущегося со скоростью V, во время t в точке x. Далее эта функция может быть вычислена с использованием методов статистической механики – решением интегродифференциального уравнения, например, уравнения Больцмана.

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

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

1.3. Микромодели дорожного движения Существует несколько способов микромоделирования дорожного трафика, разделенных на два больших класса – модели, следящие за автомобилем и модели на клеточных автоматах. Модели на клеточных автоматах подробно рассмотрены в разд. 1.4.

В моделях, следящих за автомобилем (также называемых временнонепрерывными моделями), все автомобили описываются обыкновенными дифференциальными уравнениями, включающими в себе полную динамику положения автомобиля xa и скорости va. Предполагается, что действия каждого водителя ограничены его скоростью va, расстоянием сети (от бампера до бампера) sa = xa-1 – xa – la-1 до находящегося впереди автомобиля a – 1 (la-1 определяет длину автомобиля), и скоростью va-1 находящегося впереди автомобиля. Уравнение движения каждого автомобиля характеризуется функцией ускорения, зависящей от действий водителя:

Вообще, поведение водителя автомобиля a зависит не только от находящегося непосредственно впереди него a – 1, но и от na автомобилей вблизи. В этой более обобщенной форме уравнение движения будет выглядеть так:

Теперь рассмотрим наиболее распространенные примеры таких моделей.

1.3.1. Модель оптимальной скорости Модель Оптимальной Скорости [17, 18] – предполагается, что машина сохраняет максимальную скорость, пока есть запас расстояния до предыдущей машины, и машина старается выбрать оптимальную скорость по расстоянию до предыдущей машины, когда расстояние меньше запаса. Также встречаются ее улучшения, например, модель с разделенными ускорением и торможением [19].

1.3.2. Модель Видеманна Модель Видеманна [20] — предполагается, что водитель может находиться в одном из четырех состояний:

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

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

Следование — водитель следует за идущим впереди автомобилем без ускорения или торможения, поддерживая безопасную дистанцию болееменее постоянной. Опять же, из-за несовершенства органов управления разница в скорости колеблется около нуля, но самому нулю не равна.

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

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

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

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

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

1.3.3. Модель умного водителя Модель Умного Водителя [22] — для автомобиля a описывает его положение в момент времени t и скорости va описывает величина xa. Далее, величина la задает длину автомобиля. Для простоты записи определим размер ячейки как где a – 1 относится к автомобилю непосредственно перед автомобилем a, а разность скоростей (скорость приближения) – как va = va – va-1. Движения автомобиля a в этом случае могут быть описаны при помощи двух обыкновенных дифференциальных уравнений:

причем v0, s0, T, d, и b являются параметрами модели со следующими значениями:

v0 – желаемая скорость (та скорость, с которой автомобиль перемещался бы в свободном потоке);

s0 – минимальное расстояние между автомобилями, которое сохраняется T – время движения с данной скоростью до столкновения с предыдущим автомобилем;

b – комфортное ускорение торможения Значение экспоненты обычно принимают равным четырем.

Ускорение автомобиля a на дороге в этом случае может быть представлено двумя фазами – ускорением на свободной дороге va free и ускорением при взаимодействии (при наличии находящегося впереди автомобиля) va inter :

Поведение на свободной дороге характеризуется следующим: расстояние до ближайшей машины sa велико и ускорение автомобиля находится в большей зависимости от составляющей при свободной дороге va free, которая примерно равна a для небольших скоростей и стремится к 0 по мере приближения va к v0.

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

Поведение на малых дистанциях: для незначительных разностей скоростей и a (s0 + va T ) / sa, что показывает простую отталкивающую силу, достаточную для того чтобы небольшое расстояние между автомобилями увеличилось до желаемого s0.

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

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

Время моделирования t измеряется в единицах t, а положения автомобиля xa – в единицах x.

Временная шкала обычно задается согласно реакции человека, t = 1сек. При постоянной t, длина дороги определяет гранулярность модели. В полной пробке, среднее расстояние, занимаемое автомобилем, составляет около 7, метров. Приравнивание x этому значению приводит к тому, что один автомобиль всегда занимает одну клетку, а скорость 5 клеток в секунду предполагает ехать водитель. Впрочем, в такой модели минимально возможное ускорение составит 5 x / x 2 = 7,5 м / с 2, что абсолютно нереально. Поэтому, многие современные модели на клеточных автоматах используют более мелкую дискретизацию, например x = 1,5 м. Это приводит к минимально возможному временно-непрерывным моделям, они все же способны воспроизвести большое количество дорожных ситуаций. Из-за простоты моделей, численно они наиболее эффективны и могут использоваться для моделирования больших дорожных сетей в реальном времени и даже быстрее.

Рассмотрим основную модель на клеточном автомате под названием «Правило 184» [23].

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

Число частиц остается неизменным на всем протяжении моделирования. Из-за такого применения Правило 184 называется «Правилом трафика».

На каждом шаге автомат Правила 184 применяет к массиву ячеек определенный закон для определения нового состояния: 111– *11; 110 – *11;

101 – *10; 100 – *10; 011 – *01; 010 – *01; 001 – *00; 000 – *00, который для центральной ячейки может быть записан следующим образом:

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

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

Макромодели рассматривают граф автомобильных дорог в целом, оперируя терминами из гидродинамики, такими как «поток». Микромодели рассматривают движение автомобилей на небольшом участке автодороги и измеряют те эффекты, которые суммируют влияние каждого индивидуального автомобиля на дорожную обстановку. В 1992-м году в работе [1] впервые было предложено провести микромоделирование на участке автодороги при помощи клеточных автоматов.

Клеточные автоматы являются перспективным направлением для научных исследований. Поэтому различные модели на основе клеточных автоматов в настоящий момент активно развиваются.

ГЛАВА 2. МОДЕЛЬ МНОГОПОЛОСНОЙ МАГИСТРАЛИ

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

описание модели дорожного полотна (карты клеточного автомата);

описание возможных состояний каждой клетки;

нотация для записи состояния клеточного автомата;

описание динамики клеточного автомата;

описание правил перехода;

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

• функционалы от состояния модели;

• глоссарий.

2.1.1. Модель дорожного полотна При моделировании дорожного движения с помощью клеточных автоматов в качестве модели дорожного полотна используется прямоугольная сетка размера m n, состоящая из клеток. При этом в определенные моменты времени каждая из клеток может находиться в одном из состояний, которые входят в определение конкретного клеточного автомата. Соответственно, исчерпывающее математическое описание каждой клетки в данной модели представляет собой вектор из четырех переменных: ((y, x), s, t), где:

y – целое число, которое может принимать значение от 1 до m, описывает номер конкретной полосы автомагистрали;

x – целое число, которое может принимать значение от 1 до n, описывает текущую координату клетки вдоль направления автомобильного движения;

s – описывает состояние конкретной клетки в клеточном автомате;

t – описывает конкретный момент времени с начала моделирования.

В предлагаемой модели оси x и y прямоугольной сетки имеют выраженные логические различия. Ось x моделирует направление автомагистрали, по которому движутся автомобили, в то время как ось y моделирует автомагистраль по ширине, от крайней правой полосы (y = 1) – и до крайней левой полосы (y = m).

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

Для удобства, договоримся считать, что в рассматриваемой модели дорожного полотна автомобили будут двигаться слева направо вдоль оси x.

Поэтому начало отсчета координат клеточного автомата будет располагаться в левом верхнем углу. Левый верхний угол соответствует начальной точке движения в крайней левой полосе автомагистрали и имеет координаты (1, 1) по обеим осям. Левый нижний угол соответствует начальной точке движения в крайней правой полосе автомагистрали, поэтому он имеет координаты (m, 1) – со значением один по оси х и значением m по оси y. Правый нижний угол соответствует окончанию автомагистрали в крайней правой полосе, а правый верхний угол – ее окончанию в крайней левой полосе. Правый нижний угол и правый верхний угол клеточного автомата имеют координаты (n, m) и (n, 1) соответственно. Данная схема разметки дорожного полотна в виде прямоугольной сетки проиллюстрирована на рис. 1.

Участок автомагистрали, который моделируется, типичен для Москвы и встречается в Санкт-Петербурге. В качестве числа n, определяющего длину участка, предлагается выбрать число порядка тридцати. Это соответствует среднему участку от перекрестка до перекрестка (порядка ста метров). В качестве числа m, определяющего число полос, предлагается взять 3, 4 или 5. Во-первых, такое число полос коррелирует с реальной ситуацией на автодорогах. Во-вторых, при таком числе полос роль краевых эффектов, которые могут быть прекрасно смоделированы на клеточном автомате, все еще достаточно велика. Например, нельзя перестроиться из ряда m в ряд m + 1, то есть из крайнего правого ряда на тротуар. Таким образом, такая модель позволит обеспечить имитацию, как общих закономерностей широких магистралей, так и моделирование краевых эффектов на автодороге. В дальнейшем под стандартным участком автомагистрали мы будем подразумевать модель дорожного полотна с размером 4 30 клеток, что примерно соответствует четырехполосному участку Невского проспекта от Фонтанки до Садовой улицы.

2.1.2. Возможные состояния для клетки В предлагаемой модели множество допустимых состояний для каждой клетки автомата в конкретный момент времени представлено тремя следующими состояниями:

0 – участок дорожного полотна, соответствующий данной клетке, свободен;

если слева от этой клетки присутствует автомобиль, то он может оказаться в данной клетке в один из следующих моментов времени, и клетка перейдет из состояния 0 в состояние 1;

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

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

В опубликованных к настоящему времени моделях дорожного движения на основе клеточных автоматов используется множество из двух состояний (0 и 1) для каждой конкретной клетки [1, 24–28]. Введение в модель состояния является одной из наиболее выдающихся особенностей предлагаемой модели и позволяет моделировать ситуации, более близкие к тому, что жители крупных российских городов ежедневно могут наблюдать на своих улицах. Наличие в модели этого состояния дает возможность изучать такие вопросы, как зависимость средней скорости на участке автострады от вероятности ДТП на нем.

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

Таким образом, компонента s в векторе ((y, x), s, t), который описывает состояние конкретной клетки клеточного автомата, может принимать одно из трех целочисленных значений: 0, 1 или 2.

2.1.3. Состояние клеточного автомата Существует несколько способов описать состояние клеточного автомата в рамках данной модели в любой конкретный момент времени t. При основном способом записи состояния автомата будем считать клеточный автомат совокупностью его клеток – совокупностью из m n векторов вида ((y, x), s, t).

Конкретный список, соответствующий модели в заданный момент времени, например, может быть записан следующим образом:

Можно сократить подобную запись путем вынесения общего компонента времени t за пределы списка. В этом случае клеточный автомат будет описываться подобной неоднородной структурой A: (t, ( ((1, 1), s1,1),..., ((m, n), sm,n) )). Если считать компоненту S двумерным массивом состояний клеток автомата, который хранит в себе значения от s1,1 до sm,n, то клеточный автомат можно описать структурой вида A: (t, S[mn]). Именно в таком виде автомат разумно хранить в памяти компьютера при реализации данной математической модели.

Из такого описания становится видно, что в множестве возможных значений для матрицы состояния дорожного полотна S[mn] в любой конкретный момент времени содержится ровно 3mn элементов.

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

cars = COUNT(S | Sy,x = 1): этот функционал описывает число движущихся автомобилей в модели в конкретный момент времени;

cells = COUNT(S | Sy,x 1): показывает, сколько клеток автомагистрали открыты для движения;

d = cars / cells: показывает среднюю плотность автомобилей на открытых для движения участках;

park = COUNT(S | S1,x = 2) / n: описывает долю припаркованных в крайнем правом ряду автомобилей;

stay = COUNT(S | Sy,x = 1; Sy,x+1 = 1) / cars: показывает долю машин, которые находятся в состоянии плотного движения.

2.1.4. Динамика клеточного автомата Время в нашей модели моделируется дискретно и измеряется в количестве шагов (итераций), в течение каждого из которых автомат изменяет свое состояние. В начальный момент времени отсчет количества шагов t = 0, в следующий момент времени, когда автомат изменяет свое состояние, величина t становится равна единице и т. д. Пусть в момент времени t клеточный автомат, моделирующий дорожное движение, находится в состоянии A: (t, S[mn]). Тогда при переходе к моменту времени t + 1 происходит изменение матрицы состояний дорожного полотна в соответствии с правилами перехода, которые задают конфигурацию клеточного автомата, а сам клеточный автомат в этот момент времени описывается уже так: A: (t + 1, S'[mn]), где S'[mn] – это измененная матрица состояний дорожного полотна.

Будем обозначать функцию, которая преобразует набор из m n элементов дискретного пространства [0..2] в другой набор m n элементов этого пространства в соответствии с правилами перехода, заданными конфигурацией клеточного автомата, как функцию F: S[mn] S'[mn]. Важно отметить, что результат выполнения функции F зависит только от текущей матрицы состояний, и никаким образом не зависит от того, на каком шаге данная функция применяется – это является одной из ключевых особенностей клеточных автоматов.

Таким образом, состояние дорожного полотна в момент времени t можно выразить при помощи функции F, примененной t раз к его начальному состоянию: A: (t, S[mn]) = A: (0, F F... F( S[mn] )). В теории функций общего вида известна [29] гипотеза о том, что в результате последовательного применения одной и той же функции к точке из некоторого сложного пространства, возможно возникновение одного из трех сценариев:

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

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

3. Последовательность точек хаотически гуляет по аттрактору иррациональной конфигурации. Примеры таких функций обычно приводят в книгах по теории фракталов [30] и теории хаоса [31], однако в рамках исследуемой модели требуется очень и очень постараться, для того чтобы задать функцию F именно такого вида, которая преобразовывала бы состояние дорожного полотна.

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

Это позволяет моделировать такие, естественным образом возникающие на автодорогах вещи, как риск возникновения ДТП, желание припарковаться здесь и сейчас, наконец, простое житейское замечание «то густо, то пусто». Однако, вследствие этого, нельзя утверждать, что функция F задает однозначное преобразование состояния дорожного полотна. В общем случае, утверждение F(S[mn]) = F(S[mn]) является неверным. Отсюда вытекает ряд важных следствий. Первое следствие заключается в том что, запустив автомат два раза в результате моделирования после t шагов для одной и той же начальной конфигурации клеточного автомата, скорее всего, будет получено разные матрицы состояний, описывающих дорожное полотно. Тем не менее, значения основных функционалов, характеризующих дорожное движение, в обоих случаях должны получиться близкими друг к другу. Второе следствие из вероятностного характера функции F заключается в том, что те рассуждения, которые были рассмотрены выше по отношению к последовательному итерированию функции общего вида, не совсем верны. Несмотря на это, можно высказать еще одну гипотезу относительно процесса моделирования. Можно предположить, что в результате последовательного применения вероятностной функции к начальному состоянию автомата S[mn] должен существовать шаг t0, начиная с которого значения основных функционалов модели либо сходятся к некоторому значению, либо начинают образовывать последовательность, которая с точностью до вероятностного разброса сколь угодно близко будет сходиться к некоторой последовательности-аттрактору. Корректная математическая формализация данного утверждения с предоставлением всех необходимых доказательств может стать достойной и совершенно отдельной исследовательской работой, для нас же важно то, что это будет иметь практическое применение к описанию динамики поведения нашей модели.

Из приведенной гипотезы следует, что с момента начала итерирования функции F, весь процесс последовательного изменения состояний автомата можно разбить на два этапа:

1. 0 t t0: этап становления дорожного движения. Этап, во время которого характер дорожного движения изменяется – это может быть, например, этап образования пробки в силу постоянно увеличивающегося числа машин, либо же наоборот, этап ее рассасывания.

2. t > t0: этап устойчивого дорожного движения. Не важно, пробка ли это, равномерное движение, или же движение волнами, важно, что модель способна дать адекватное описание того, что примерно будет происходить на автодороге, для любого t, сколь угодно сильно отличающегося от t в бльшую сторону.

Таким образом, в список задач, которые могут быть поставлены перед моделью, можно как минимум внести следующие вопросы:

1. Верна ли гипотеза о существовании шага t0?

2. Как запущенная модель может определить шаг t0 осуществления перехода от этапа становления к этапу устойчивого движения?

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

Состояние 0: клетка в этом состоянии может изменить свое состояние только на состояние 1, в случае если конкретный автомобиль переместился на пустое пространство данной клетки.

Состояние 1: в зависимости от различных условий движущийся автомобиль либо освобождает клетку, занимая при этом одну из трех клеток, соседних справа и при этом свободных, в этом случае между двумя соседними клетками происходит обмен состояниями, либо с небольшой вероятностью переходит в состояние 2 (паркуется, инициирует ДТП или становится участником ДТП).

Состояние 2: клетка остается в этом состоянии до конца прогона модели. Мы будем считать, что число клеток в состоянии 2 на дорожном полотне не может уменьшаться с увеличением числа шагов.

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

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

переход из состояния 1 в состояние 2:

переход в такое состояние в качестве жертвы ДТП:

переход в такое состояние в качестве виновника ДТП, с инициированием такого перехода у жертвы;

спонтанный переход в состояние 2 (двигатель сломался, или решил продолжение работы с включенным двигателем;

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

В соответствии с правилом 1, определяется вероятность pn, определяющая возможность появления на каждом новом шаге нового автомобиля в состоянии для каждой свободной клетки из левого ряда. Более формально, для всех клеток с координатами (y, 1) таких, что sy,1 = 0, происходит генерация случайного числа ry, в диапазоне от 0 до 1. Если это случайное число оказывается больше чем pn, то клетка с координатами (y, 1) остается в состоянии 0. Однако в случае если ry,1 < pn, то в клетке с координатами (y, 1) появляется новый автомобиль, который начинает движение: s'y,1 = 1. Таким образом, функционал от состояния автомата cars = COUNT(S | Sy,x = 1) может увеличивать свое значение на каждом шагу прогона модели.

Правило 2 определяет механизм, в соответствии с которым происходят изменения движущегося автомобиля, находящегося в клетке с состоянием 1, на прямоугольной сетке дорожного полотна клеточного автомата. Пусть функция f определяет изменение конкретного движущегося автомобиля. В качестве аргументов эта функция принимает кортеж из вектора состояний нескольких соседних клеток, плюс бит «жертва ДТП», который мог быть назначен данному автомобилю одним из обработанных ранее, которые на дорожном полотне расположены слева от данного автомобиля. В предлагаемой математической модели, чтобы избежать ее излишнего осложнения, предлагается включить в вектор состояний соседних клеток состояния только тех трех клеток, которые находятся впереди по ходу движения (то есть справа) от данной клетки. Для клетки с координатами (y, x) это будут три соседних клетки с координатами (y - 1, x + 1), (y, x + 1) и (y + 1, x + 1). Каждая из этих клеток может находиться или в одном из трех состояний 0, 1 или 2, или же в псевдосостоянии -1.

Псевдосостояние -1 вводится в модель для обозначения участков по краям от дороги для корректного задания граничных условий. Механизм задания аргументов функции f проиллюстрирован на рис. 2.

Таким образом, множество возможных аргументов функции f представляет собой четырехмерное дискретное пространство вида [-1..2, -1..2, -1..2, 0..1].

Отсюда следует, что для задания полного набора правил перехода в клеточном автомате требуется определить 4 4 4 2 = 128 функций f на аргументах из множества всех возможных. На самом деле только 64 функции, так как 64 других, когда значение бита «жертва ДТП» установлено для данного автомобиля в единицу, однозначно определяют переход данного автомобиля в состояние 2.

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

Рис. 3. Возможные конфигурации аргументов функции f Для каждой из возможных конфигураций функция f задается при помощи списка из k (k 1) кортежей, каждый из которых состоит из четырех элементов (pi, s'i, celli, crashi), i = 1..k. Этот список должен удовлетворять условию SUM(pi | i = 1..k) = 1, которое определяет корректность задания вероятностных правил перехода. Рассмотрим элементы кортежей в этом списке более подробно:

pi – число от 0 до 1 (включительно) – определяет вероятность срабатывания именно правила i при вызове функции f;

s'i – 1 или 2 – определяет состояние, в котором оказывается автомобиль при условии срабатывания правила i во время вызова функции f;

celli – 0, 1, 2 или 3 – определяет номер клетки, в которой автомобиль оказывается после срабатывания правила i:

celli = 0: автомобиль остается в текущей клетке;

celli = 1: автомобиль в движении перестраивается в левую полосу, то есть оказывается в соседней клетке справа сверху;

celli = 2: автомобиль движется вперед, то есть оказывается в соседней клетке справа сверху;

celli = 3: автомобиль в движении перестраивается в правую полосу, то есть оказывается в соседней клетке справа снизу;

crashi – 0, 1, 2 или 3 – определяет номер клетки в состоянии 1, для которой данный автомобиль стал виновником ДТП:

crashi = 0: данный автомобиль спокойно продолжает движение – возвращается всегда, когда s'i = 1, и довольно часто даже когда s'i = 2;

crashi = 1: данный автомобиль стал виновником ДТП для автомобиля crashi = 2: автомобиль стал виновником ДТП для автомобиля спереди;

crashi = 3: данный автомобиль стал виновником ДТП для автомобиля спереди в правой полосе.

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

1. Если значение бита «жертва ДТП» для данного автомобиля уже установлено в единицу, клетка с данным автомобилем переходит из состояния 1 в состояние 2.

2. В противном случае значения состояний трех клеток справа от данной передаются на вход функции f.

3. Функция f определяет один из своих 46-ти экземпляров, который должен быть вызван.

4. Происходит генерация случайного числа i в диапазоне от 1 до k, которое определяет, какое из правил из списка должно сработать при вызове конкретного экземпляра функции f.

5. В соответствии с этим правилом, функция f возвращает кортеж из трех элементов (s'i, celli, crashi), который однозначно определяет изменение состояния движущегося автомобиля.

6. Если возвращенное значение crashi установлено большим нуля, то соответствующему автомобилю справа присваивается бит «жертва ДТП».

Отметим, что движущиеся автомобили могут исчезать из зоны видимости дорожного полотна, переходя прямоугольной сетке самый правый ряд. Это происходит при вызове функции f(-1, -1, -1), которая должна возвращает кортеж из элементов (1 – автомобиль продолжает движение, 2 – автомобиль в более правой клетке), 0 – автомобиль никого не повреждает). Также отметим, что чисто статистически кортеж (1, 2, 0) должен чаще всего возвращаться функцией f для самых и самых разных входных конфигураций.

Таким образом, обобщая все вышесказанное, мы наконец-то можем формально определить функцию F, задающую преобразование матрицы состояния дорожного полотна S[mn] S'[mn] на каждом шаге прогона модели. При вызове функции F происходит следующее.

1. Составляется список из координат всех клеток автомата, которые находятся в состоянии 1. Этот список отсортирован слева направо по координате x, а для клеток с одинаковыми координатами x – снизу вверх по координате y.

Например, (1, 3), (2, 3), (4, 3), (2, 4), (1, 6),... При этом значение бита «жертва ДТП» устанавливается в ноль для каждой клетки из списка.

2. В порядке, в котором этот список отсортирован, для каждой клетки из списка определяется изменение конфигурации движущегося автомобиля. При этом между вызовами функции f, дорожное полотно может находиться в состоянии, промежуточном между S[mn] и S'[mn].

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

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

Подобная дифференциация не была добавлена в модель, так как цель работы – продемонстрировать более общие закономерности в дорожном движении.

2.1.6. Описание экземпляра модели Выше было приведено математическое определение для всех элементов клеточного автомата, которые необходимы для задания конкретной модели.

Суммируя изложенное, можно дать определение для такого понятия, как экземпляр модели. Итак, составными частями определения экземпляра модели M являются:

определение дорожного полотна (m n);

определение функции F преобразования состояния дорожного полотна:

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

конкретного движущегося автомобиля, для каждой из 46-ти возможных конфигураций аргументов функции f (46 списков различной длины, где каждый элемент списка представляет собой кортеж, состоящий из элементов (pi, s'i, celli, crashi)).

Запись M(m, n, pn, f 46) будет представлять собой исчерпывающее описание для экземпляра модели.

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

2.3). Поэтому описание полного состояния будет содержать в себе как описание экземпляра модели M, так и описание состояния клеточного автомата A: (t, S[mn]).

При этом можно воспользоваться следующей нотацией для записи полного состояния – W: (M, A).

Можно утверждать, что полное состояние модели на момент ее запуска W будет содержать в себе то же самое описание экземпляра модели M. Вторым компонентом для W0 станет начальное состояние клеточного автомата A0: (0, S[mn]), которое, в свою очередь, будет содержать в себе начальную матрицу состояния дорожного полотна. Таким образом, записать полное состояние модели перед ее запуском можно следующим образом:

В компьютерной программе, которая будет реализовывать данную математическую модель, должна быть обеспечена возможность загрузки из текстового файла для двух вышеупомянутых сущностей – для экземпляра модели M и для состояния клеточного автомата A. Соответственно, в интерфейсе программы моделирования, будут присутствовать элементы управления «Загрузить модель», «Загрузить состояние» и «Сохранить состояние». Это обеспечит возможность исследования зависимости модели, как от изменения правил перехода, так и от различных конфигураций автомобилей на дороге.

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

Такие функционалы бывают двух типов: статические и динамические.

Статические функционалы зависят только от матрицы состояния клеточного автомата S[mn] в текущий момент времени, и не учитывают изменение дорожной ситуации с увеличением числа шагов. Важнейшие из статических функционалов, такие как cars, cells, d, park и stay, были описаны выше в подразделе «состояние клеточного автомата». В то же время, динамические функционалы описывают, каким образом состояние клеточного автомата в модели изменяется. Условно, можно разбить все динамические функционалы на три типа:

1. Те из них, которые описывают изменение дорожной картины за один шаг, например, средняя мгновенная скорость Vt(At, At-1).

2. Тренды, которые описывают изменение дорожной ситуации на конкретном отрезке времени, например, среднее ускорение за последние k шагов:

3. Ключевые моменты времени, такие как (гипотетический) момент стабилизации дорожной ситуации t0, который описан выше в подразделе «Динамика клеточного автомата».

Такая классификация функционалов от модели проиллюстрирована на рис. 4.

Пожалуй, не будет преувеличением утверждать, что самым важным функционалом, который необходимо отслеживать при моделировании дорожного движения, является средняя скорость Vt. В нашей математической модели средняя мгновенная скорость Vt на шаге t будет определяться как соотношение количества машин (клеток в состоянии 1), которые в течение этого шага увеличили свою координату x на один (то есть передвинулись вправо) к общему числу машин:

Для того, чтобы в модели присутствовала возможность подсчета мгновенной скорости, внутрь функции F( S[mn] ), которая задает преобразование состояния дорожного полотна, вводится дополнительная переменная moved. В ходе применения экземпляров функции f к каждой клетке, которая представляет собой движущийся автомобиль (находится в состоянии 1), происходит инкрементация переменной moved в случае, если автомобиль передвинулся вправо – в случае, когда экземпляр функции f возвращает celli > 0.

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

Кроме того, отметим, что такое определение фактически показывает, сколько клеток в среднем преодолевает автомобиль за один шаг. Непосредственно из определения следует, что 0 Vt 1. Реально, в зависимости от конкретных вероятностей, которые регулируют движение вперед в правилах перехода клеточного автомата, мгновенная скорость будет ограничена некоторой скоростью свободного движения Vmax 1. Таким образом, можно утверждать, что 0 Vt Vmax 1. Если на шаге t средняя мгновенная скорость близка к скорости свободного движения (значение (Vmax – Vt) / Vmax близко к нулю), то ситуация на дороге хорошая. С другой стороны, если средняя мгновенная скорость близка к нулю (значение Vt / Vmax близко к нулю), то клеточный автомат моделирует не то, что пробку, а самый настоящий транспортный коллапс! Основная часть главы данной работы посвящена исследованию зависимости различных факторов на среднюю мгновенную скорость дорожного движения.

Родственным функционалом является обратная мгновенная скорость 1 / Vt.

Этот параметр позволяет оценить, сколько шагов требуется среднему автомобилю для того, чтобы продвинуться вперед на одну клетку. Чем меньше этот параметр, чем он ближе к единице – тем лучше дорожная ситуация. И, наборот, в случае остановки движения на автомагистрали, этот параметр устремляется к бесконечности.

Последним функционалом, который хочется удостоить вниманием в данном разделе, является момент стабилизации ситуации на дороге t0. Для определения момента t0 мы ограничимся рассмотрением динамики только для функционала Vt, не принимая во внимание другие функционалы. Если последовательность {Vt} в итоге сходится к некоторому предельному значению V, то даже с учетом вероятностного характера модели мы можем определить момент t0, такой что для любого t t0 верно утверждение |Vt / Vt-1 - 1| < eps, как момент стабилизации ситуации на дороге. Программа моделирования будет отслеживать данную возможность. Однако, в случае если последовательность {Vt} сходится не к предельному значению V, а к последовательности-аттрактору, применяемый математический аппарат не позволяет быстро отслеживать подобные циклические изменения скорости для определения момента t0. Максимум, что можно здесь сделать – это отображать в программе моделирования график Vt(t).

2.1.8. Глоссарий В предыдущих пунктах разд. 2.1. было объяснено немало терминов, касающихся данной работы. Здесь еще раз приведем краткие определения для некоторых из этих терминов.

• Модель – совокупность определений и правил, которая описана в разд 2.1. и служит для представления дорожного движения на автомагистрали в формальном виде.

Экземпляр модели – модель, для которой определены ее размеры m n, вероятность pn и семейство из 46-ти функций f, задающих изменение для автомобилей в состоянии движения.

Дорожное полотно – прямоугольная сетка размера m n, заполненная значениями 0, 1 или 2, которая имитирует автомагистраль в данной модели.

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

Состояние дорожного полотна – матрица S размера m n, состоящая из значений 0, 1 или 2, которыми заполнено дорожное полотно.

• Полное состояние модели – совокупность из определения экземпляра модели M, состояния дорожного полотна S[mn] и шага моделирования t.

• Начальное состояние модели – полное состояние модели, в котором шаг моделирования t равен нулю, а матрица состояния дорожного полотна S[mn] является стартовой для всего процесса моделирования.

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

2.2.1. Базовый экземпляр модели Базовый экземпляр модели определяет размеры прямоугольной сетки m n дорожного полотна по умолчанию, вероятность pn по умолчанию и набор правил, по которым, если не оговорено иное, будут происходить преобразования в клеточном автомате.

В параграфе «Модель дорожного полотна» разд. 2.1 уже отмечалось, что для значений m и n по умолчанию разумно взять 4 и 30 соответственно. Таким образом, в базовом экземпляре модели можно будем исследовать дорожное полотном размера 4 30 клеток, что примерно соответствует четырехполосному участку Невского проспекта от Фонтанки до Садовой улицы.

В качестве значения по умолчанию для вероятности pn появления новых автомобилей в свободных клетках с координатой x = 1, интересно взять число 0.5.

Это, с одной стороны, позволит обеспечить постоянный приток новых автомобилей в нашу модель, с другой стороны, приток новых автомобилей не будет чересчур плотным, для того чтобы это привело к пробке. Такой выбор вероятности pn дает нам возможность провести исследование для наиболее интересной дорожной ситуации – это все еще не пробка, но уже и не свободное движение! Отметим, что фактически именно от варьирования параметра pn будут зависеть значения основных функционалов от состояния дороги, таких как cars или Vt.

Четвертым элементом в определении экземпляра модели будет являться совокупность из 46-ти определений функции f для различных конфигураций клеток дорожного полотна. В базовом варианте модели не будет происходить ни парковок, ни ДТП. Таким образом, в состоянии 2 будут находиться только те клетки, которые находились в этом состоянии изначально. Отсюда следует, что клеточный автомат перестает быть в базовом варианте вероятностным, и модель дорожного движения становится почти полностью детерминированной. Почти – так как появление новых автомобилей на автодороге по-прежнему остается случайным процессом. Тем не менее, в каждом из 46-ти списков кортежей функции f базового экземпляра модели, будет присутствовать только один элемент – кортеж вида (1, 1, cell1, 0). Здесь • p1 = 1 – модель детерминированная;

• s'1 = 1 – автомобиль продолжает находиться в движущемся состоянии;

• crash1 = 0 – автомобиль не повреждает другой движущийся автомобиль.

И все это – с вероятностью 100% на каждом шаге моделирования. Таким образом, требуется лишь формально определить клетку, на которой будет оказываться автомобиль при применении к нему функции f, для каждой из 46-ти возможных конфигураций.

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

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

• pn = 0.5;

• f(-1, -1, -1) = ((1, 1, 2, 0)); // автомобиль выходит за пределы модели • f(-1, 0, 0) = ((1, 1, 2, 0));

• f(-1, 0, 1) = ((1, 1, 2, 0));

• f(-1, 0, 2) = ((1, 1, 2, 0));

• f(-1, 1, 0) = ((1, 1, 3, 0)); // впереди «тормоз», перестраиваемся вправо • f(-1, 1, 1) = ((1, 1, 0, 0)); // ехать некуда, стоим • f(-1, 1, 2) = ((1, 1, 0, 0));

• f(-1, 2, 0) = ((1, 1, 3, 0));

• f(-1, 2, 1) = ((1, 1, 0, 0));

• f(-1, 2, 2) = ((1, 1, 0, 0));

• f(0, 0, -1) = ((1, 1, 2, 0));

• f(0, 0, 0) = ((1, 1, 2, 0));

• f(0, 0, 1) = ((1, 1, 2, 0));

• f(0, 0, 2) = ((1, 1, 2, 0));

• f(0, 1, -1) = ((1, 1, 1, 0));

• f(0, 1, 0) = ((1, 1, 1, 0)); // есть выбор, решаем уйти влево • f(0, 1, 1) = ((1, 1, 1, 0));

• f(0, 1, 2) = ((1, 1, 1, 0));

• f(0, 2, -1) = ((1, 1, 1, 0));

• f(0, 2, 0) = ((1, 1, 1, 0));

• f(0, 2, 1) = ((1, 1, 1, 0));

• f(0, 2, 2) = ((1, 1, 1, 0));

• f(1, 0, -1) = ((1, 1, 2, 0));

• f(1, 0, 0) = ((1, 1, 2, 0));

• f(1, 0, 1) = ((1, 1, 2, 0));

• f(1, 0, 2) = ((1, 1, 2, 0));

• f(1, 1, -1) = ((1, 1, 0, 0));

• f(1, 1, 0) = ((1, 1, 3, 0));

• f(1, 1, 1) = ((1, 1, 0, 0)); // вот она, пробка • f(1, 1, 2) = ((1, 1, 0, 0));

• f(1, 2, -1) = ((1, 1, 0, 0));

• f(1, 2, 0) = ((1, 1, 3, 0));

• f(1, 2, 1) = ((1, 1, 0, 0));

• f(1, 2, 2) = ((1, 1, 0, 0));

• f(2, 0, -1) = ((1, 1, 2, 0));

• f(2, 0, 0) = ((1, 1, 2, 0));

• f(2, 0, 1) = ((1, 1, 2, 0));

• f(2, 0, 2) = ((1, 1, 2, 0));

• f(2, 1, -1) = ((1, 1, 0, 0));

• f(2, 1, 0) = ((1, 1, 3, 0));

• f(2, 1, 1) = ((1, 1, 0, 0));

• f(2, 1, 2) = ((1, 1, 0, 0));

• f(2, 2, -1) = ((1, 1, 0, 0));

• f(2, 2, 0) = ((1, 1, 3, 0));

• f(2, 2, 1) = ((1, 1, 0, 0));

• f(2, 2, 2) = ((1, 1, 0, 0)).

2.2.2. Базовое начальное состояние В нашей модели базовое начальное состояние дорожного полотна будет представлять собой пустую автомагистраль, которая не заполнена ни движущимися, ни припаркованными на ней автомобилями. Матрица дорожного полотна для базового начального состояния S[430] будет выглядеть следующим образом:

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

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

• равномерно заполненная автомобилями (клетками в состоянии 1) магистраль;

• равномерно заполненная припаркованными автомобилями (клетками в состоянии 2) правая полоса;

в состоянии 2).

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

2.3.1. Формат файла для сохранения экземпляра модели Для сохранения экземпляра модели – того набора правил, которые регулируют изменение состояний клеток в клеточном автомате, было предложено хранить этот набор правил в виде простого текстового файла, который можно отредактировать в любом текстовом редакторе. Формат файла для сохранения экземпляра модели подразумевает наличие в этом текстовом файле ровно 48-ми строк с данными. В первой строке этого текстового файла сохраняется размер клеточного автомата в формате m n. Во второй строке сохраняется вероятность pn появления новых автомобилей в левом столбце дорожного полотна. В последующих 46-ти строках описываются списки кортежей вида (pi, s'i, celli, crashi) для различных наборов состояний клеток справа от клетки в состоянии (движущегося автомобиля). Пример первых нескольких строк такого текстового файла приведен ниже:

f(-1, -1, -1) = ((1, 1, 2, 0)) f(-1, 0, 0) = ((0.8, 1, 2, 0), (0.2, 1, 3, 0)) 2.3.2. Формат файла для сохранения состояния модели Состояние дорожного полотна также предложено сохранять в виде простого текстового файла, который можно редактировать в любом текстовом редакторе.

Число строк в этом текстовом файле составляет 2 + m. В первой строке файла указывается номер текущего шага t. Во второй строке файла сохраняется размер клеточного автомата в формате «m n». В последующих m строках сохраняется текущее состояние дорожного полотна. Пример текстового файла с сохраненным состоянием, который соответствует небольшой двухполосной дороге с рядом припаркованных в ее правом ряду автомобилей, приведен ниже:

2.3.3. Архитектура программы Программа для имитационного моделирования дорожного движения в соответствии с описанной моделью реализована на языке программирования Java по классической схеме «Model-View-Controller» (рис. 6) [32].

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

Ключевыми классами для сохранения этих данных здесь являются классы Model и State, а вспомогательными классами – классы Car, Rule, ArgModel и Args.

У компонента View в этой схеме два основных предназначения. Во-первых, он служит для отображения данных модели, то есть текущего состояния дорожного полотна и ряда основных функционалов, на экране компьютера. Это дает возможность интерактивно и наглядно отслеживать изменения в дорожной ситуации в ходе моделирования. Во-вторых, компонент View предоставляет GUIинтерфейс для управления моделью через компонент Controller. В базовой версии программы такой интерфейс предоставляет пользователю следующие возможности:

• перезапустить модель с нулевого шага;

• применить функцию F к текущему состоянию модели;

• загрузить экземпляр модели из текстового файла;

• загрузить состояние клеточного автомата из текстового файла;

• изменить значение вероятности pn.

Компонент View реализован в программе моделирования внутри классов View и MCanvas, которые представляют собой GUI-приложение и «холст» для рисования клеточного автомата соответственно.

Компонент Controller отвечает за применение тех действий, которые пользователь программы указывает при помощи GUI-интерфейса, к данным программы – к состоянию дорожного полотна и к экземпляру модели. Наиболее типичным действием является применение функции F к состоянию дорожного полотна по нажатию соответствующей кнопки в интерфейсе. В программе упомянутый компонент реализован в классе, который называется Runner.

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

• Java – это платформонезависимый язык программирования, программа на котором может быть запущена как под ОС Windows, так и под ОС Linux;

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

• среда разработки NetBeans IDE «Develop with pleasure» позволяет без дополнительных усилий нарисовать, просто нарисовать GUI-интерфейс к приложению, и он заработает.

Диаграмма классов, которая соответствует разработанному приложению, приведена на рис. 7. Эта диаграмма классов также была получена автоматически при помощи выбора соответствующего инструмента внутри среды разработки NetBeans IDE.

Рис. 7. Диаграмма классов для программы моделирования Исходные коды программы моделирования вместе с исполняемой частью и http://rain.ifmo.ru/~kotov_a/traffic_model.zip.

2.4. Демонстрация дорожного движения Приведем пример демонстрации работы программы моделирования дорожного движения для базового экземпляра модели с базовым начальным состоянием. В любой операционной системе программа моделирования запускается при помощи команды java –jar Model.jar.

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

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

В средней части окна отображается текущее состояние клеточного автомата, которое имитирует наличие автомобилей и препятствий на многополосной автомагистрали. Белым цветом изображаются клетки в состоянии 0 – клетки, которые открыты и свободны для движения по ним автомобилей. Красным цветом изображаются движущиеся автомобили – клетки в состоянии 1. Синим цветом в программе моделирования отмечены те клетки, которые не могут быть заняты движущимися автомобилями – клетки в состоянии 2. Такие клетки означают либо припаркованные в правом ряду автомобили, либо препятствия, либо автомобили, попавшие в ДТП.

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

После нескольких подряд нажатий на кнопку “>”, представляющую собой элемент управления, который применяет функцию F к текущему состоянию дорожного полотна, в средней части окна появляется ряд движущихся автомобилей (рис. 9).

Как видно из представленного рисунка, в базовом экземпляре модели автомобили движутся более-менее свободно. Об этом факте свидетельствует средняя скорость движения автомобилей, которая близка к значению Vmax = 1.

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

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

• двумерность клеточного автомата;

• наличие состояния клетки, которое описывает препятствие;

• вероятностный характер правил перехода.

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

ГЛАВА 3. ИССЛЕДОВАНИЕ НА МОДЕЛИ

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

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

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

фиксированного стартового состояния дорожного полотна;

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

вероятность возникновения ДТП.

Более формально эти три эксперимента, вместе с их результатами, описаны в разд. 3.2 – 3.4. При этом для каждого эксперимента мы определяем следующие его атрибуты:

экземпляр модели;

стартовое состояние;

момент наблюдения t0;

варьируемый параметр.

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

3.2. Зависимость средней скорости движения от числа машин Цель первого эксперимента – показать, как средняя скорость движения на автодороге или на отдельных ее участках будет зависеть от того, насколько много машин (клеток в состоянии 1) присутствует в модели. Если машин много – это пробка, и машины будут не давать друг другу проехать вперед. Если машин мало – то движение близко к свободному, и скорость будет стремиться к параметру Vmax, который определяется исходя из набора правил перехода. Будет ли зависимость средней скорости от числа машин линейной?! Покажет эксперимент!

модификациями. Первая модификация заключается в том, что параметр Vmax определен как 0,5. При этом с вероятностью одна вторая, каждый из автомобилей не будет двигаться вперед, даже если хотя бы одна из трех клеток оказалась свободной. Это реализовано за счет добавления кортежа (0.5, 1, 0, 0) ко всему подмножеству из 46-ти списков, в которых разрешен переход автомобиля на одну клетку вперед. Вторая модификация экземпляра модели заключается в том, что с вероятностью, большей, чем ноль, разрешаются перестроения из ряда в ряд при перемещении вперед, при условии, что перед автомобилем есть более чем одна свободная клетка – клетка в состоянии 0. Такая вероятностная модификация экземпляра модели подходит для моделирования реальных процессов, происходящих на автомобильной дороге, где и скорость дорожного движения, и вероятность перестроения могут быть описаны некоторыми случайными величинами. Ниже приведено содержимое текстового файла, в котором сохранено описание данной модификации базового экземпляра модели в формальном виде:

f(-1, -1, -1) = ((1, 1, 2, 0)) f(-1, 0, 0) = ((0.4, 1, 2, 0), (0.1, 1, 3, 0), (0.5, 1, 0, 0)) f(-1, 0, 1) = ((0.5, 1, 2, 0), (0.5, 1, 0, 0)) f(-1, 0, 2) = ((0.5, 1, 2, 0), (0.5, 1, 0, 0)) f(-1, 1, 0) = ((0.5, 1, 3, 0), (0.5, 1, 0, 0)) f(-1, 1, 1) = ((1, 1, 0, 0)) f(-1, 1, 2) = ((1, 1, 0, 0)) f(-1, 2, 0) = ((0.5, 1, 3, 0), (0.5, 1, 0, 0)) f(-1, 2, 1) = ((1, 1, 0, 0)) f(-1, 2, 2) = ((1, 1, 0, 0)) f(0, 0, -1) = ((0.4, 1, 2, 0), (0.1, 1, 1, 0), (0.5, 1, 0, 0)) f(0, 0, 0) = ((0.4, 1, 2, 0), (0.05, 1, 1, 0), (0.05, 1, 3, 0), f(0, 0, 1) = ((0.4, 1, 2, 0), (0.1, 1, 1, 0), (0.5, 1, 0, 0)) f(0, 0, 2) = ((0.4, 1, 2, 0), (0.1, 1, 1, 0), (0.5, 1, 0, 0)) f(0, 1, -1) = ((0.5, 1, 1, 0), (0.5, 1, 0, 0)) f(0, 1, 0) = ((0.3, 1, 1, 0), (0.2, 1, 3, 0), (0.5, 1, 0, 0)) f(0, 1, 1) = ((0.5, 1, 1, 0), (0.5, 1, 0, 0)) f(0, 1, 2) = ((0.5, 1, 1, 0), (0.5, 1, 0, 0)) f(0, 2, -1) = ((0.5, 1, 1, 0), (0.5, 1, 0, 0)) f(0, 2, 0) = ((0.3, 1, 1, 0), (0.2, 1, 3, 0), (0.5, 1, 0, 0)) f(0, 2, 1) = ((0.5, 1, 1, 0), (0.5, 1, 0, 0)) f(0, 2, 2) = ((0.5, 1, 1, 0), (0.5, 1, 0, 0)) f(1, 0, -1) = ((0.5, 1, 2, 0), (0.5, 1, 0, 0)) f(1, 0, 0) = ((0.4, 1, 2, 0), (0.1, 1, 3, 0), (0.5, 1, 0, 0)) f(1, 0, 1) = ((0.5, 1, 2, 0), (0.5, 1, 0, 0)) f(1, 0, 2) = ((0.5, 1, 2, 0), (0.5, 1, 0, 0)) f(1, 1, -1) = ((1, 1, 0, 0)) f(1, 1, 0) = ((0.5, 1, 3, 0), (0.5, 1, 0, 0)) f(1, 1, 1) = ((1, 1, 0, 0)) f(1, 1, 2) = ((1, 1, 0, 0)) f(1, 2, -1) = ((1, 1, 0, 0)) f(1, 2, 0) = ((0.5, 1, 3, 0), (0.5, 1, 0, 0)) f(1, 2, 1) = ((1, 1, 0, 0)) f(1, 2, 2) = ((1, 1, 0, 0)) f(2, 0, -1) = ((0.5, 1, 2, 0), (0.5, 1, 0, 0)) f(2, 0, 0) = ((0.4, 1, 2, 0), (0.1, 1, 3, 0), (0.5, 1, 0, 0)) f(2, 0, 1) = ((0.5, 1, 2, 0), (0.5, 1, 0, 0)) f(2, 0, 2) = ((0.5, 1, 2, 0), (0.5, 1, 0, 0)) f(2, 1, -1) = ((1, 1, 0, 0)) f(2, 1, 0) = ((0.5, 1, 3, 0), (0.5, 1, 0, 0)) f(2, 1, 1) = ((1, 1, 0, 0)) f(2, 1, 2) = ((1, 1, 0, 0)) f(2, 2, -1) = ((1, 1, 0, 0)) f(2, 2, 0) = ((0.5, 1, 3, 0), (0.5, 1, 0, 0)) f(2, 2, 1) = ((1, 1, 0, 0)) f(2, 2, 2) = ((1, 1, 0, 0)) В качестве стартового состояния дорожного полотна для данного эксперимента выступает интересная модификация базового стартового состояния, которая моделирует сужение проезжей части на Невском проспекте с четырех полос до одной полосы в ходе проведения реконструкции Аничкова моста [33].

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

Ниже представлено данное стартовое состояние, которое сохранено в виде текстового файла:

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

В качестве измеряемого параметра при проведении эксперимента выступают количество машин cars и средняя скорость движения V на шаге t0. Исходя из горизонтального размера дорожного полотна, которое составляет 30 клеток, время измерения t0 выбрано как 60 шагов с момента запуска программы. Результатом эксперимента будут считаться два графика зависимости (рис.10, 11):

график зависимости числа машин cars от вероятности pn;

график зависимости средней скорости V от числа машин cars.

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

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

Из первого полученного графика, который показывает зависимость числа машин cars от вероятности pn возникновения новых автомобилей в левом ряду автомагистрали следует, что в случае, если эта вероятность превышает значение 0.35, то возможности этого участка автомобильной дороги по пропусканию траффика исчерпываются. Непосредственно, перед сужением с четырех полос до одной образуется пробка. Дальнейшее увеличение вероятности pn в этом эксперименте не приводит к какому-либо изменению ситуации, так как движение после сужения по-прежнему остается относительно свободным, а до сужения клетки в состоянии 0 почти отсутствуют. Уплотнение движения перед сужением при pn = 0.15 проиллюстрировано ниже:

Динамика дорожного движения перед сужением в районе Аничкова моста проиллюстрирована при помощи серии из скриншотов (рис.12–17). На рис. представлен вид окна программы моделирования перед началом эксперимента.

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

Рис. 12. Сужение Аничкова моста перед началом движения На рис. 14 представлено состояние клеточного автомата по прошествии сорока шагов моделирования. Автомобили, отмеченные красным цветом, начинают скапливаться непосредственно перед сужением. В то время как автомобили, проехавшие критический участок, двигаются свободно.

На рис. 15 представлено состояние дорожного полотна после шестидесяти шагов моделирования. Видно, что непосредственно перед сужением скопление автомобилей начинает превращаться в настоящую пробку. Средняя скорость движения падает со значения 0.41 (после сорока шагов) до значения 0.27.

Рис. 15. Образование пробки в районе сужения Аничкова моста На рис 16. проиллюстрировано состояние Невского проспекта в районе сужения Аничкова моста после 80-ти шагов моделирования. Размеры пробки перед сужением, то есть количество автомобилей, находящихся в состоянии плотного движения, продолжают увеличиваться. Средняя скорость движения продолжает падать, и ее значение составляет теперь 0.22. Образование пробки свидетельствует о том, что данный участок автодороги не способен пропускать автомобили, плотность появления которых определяется вероятностью pn = 0,1.

Рис. 16. Выраженная пробка в районе сужения Аничкова моста На рис. 17, по прошествии ста шагов с момента начала моделирования, все отмеченные ранее тенденции к закреплению пробки перед сужением и замедлению дорожного движения сохраняются. Интересно, что при достаточно большом размере пробки, модель начинает отражать еще один закон плотного движения. Появляются так называемые «свободные окна» – участки дорожного полотна, которые появляются, когда автомобиль впереди уезжает, освобождая пространство. Когда следующий за ним автомобиль, в свою очередь, переезжает на освободившийся участок, «свободное окно» автоматически перемещается назад. В модели «свободные окна» формализованы в виде клеток в состоянии 0, рядом с которыми отсутствуют какие-либо другие клетки в состоянии 0.

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

3.3. Вопрос о парковке в крайнем правом ряду Целью данного эксперимента является показать, в какой мере запрет парковки в крайнем правом ряду автомагистрали способны улучшить дорожную ситуацию. Экземпляром модели в данном эксперименте выступает тот же самый набор правил, что и в разд. 3.2. При этом автомобили умеют объезжать препятствия, самопроизвольно перестраиваться из ряда в ряд. Их средняя скорость не превышает Vmax = 0,5. В качестве стартового состояния выступает базовое стартовое состояние при наличии на нем ровно k припаркованных в случайном порядке автомобилей. Такой набор из экземпляра модели и стартового состояния соответствует четырехполосному участку Невского проспекта от Аничкова моста до Садовой улицы, на котором в настоящий момент еще не запрещена парковка в крайнем правом ряду. Стартовое состояние для k = автомобилей может выглядеть сохраненным в виде текстового файла примерно так:

Как и в эксперименте, который описан в разд. 3.2, будем проводить контрольное измерение средней скорости движения на автомагистрали в момент времени t0 = 60 шагов. В ходе проведения эксперимента будут изменяться целых два параметра, которые относятся к модели:

• число припаркованных автомобилей k будет варьироваться от 0 до длины магистрали n с шагом 1;

• вероятность pn появления автомобилей в крайнем левом ряду будет варьироваться от 0 до 1 с шагом 0.01.

Предварительным результатом эксперимента является зависимость средней скорости движения от двух параметров: V(k, pn). Как следует из результатов эксперимента, проведенного в разд. 3.2, существует некоторое критическое значение скорости Vp, ниже которого движение можно считать плотным, а выше – относительно свободным. В данном эксперименте будем считать Vp = 0,25.

Определим булеву функцию существования пробки P(k, pn) следующим образом:

Таким образом, для каждого k в диапазоне от 0 до n, модель способна показать, начиная с какого критического значения pn, движение автомобилей на дороге будет являться плотным. Для того чтобы визуализировать эти результаты эксперимента, определим еще одну функцию p*n(k) таким образом, что для всех pn > p*n будет выполняться P(k, pn) = 1, и, наоборот, для всех pn p*n будет верно, что P(k, pn) = 0. В результате эксперимента можно построить график (рис. 18) зависимости p*n(k):

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

Ситуация, в которой небольшое число припаркованных в правом ряду автомобилей, приводит к образованию локальной пробки, проиллюстрирована ниже: (скриншоты) Независимо от результатов проведенного эксперимента, правительство Санкт-Петербурга приняло решение о запрете парковки для Невского проспекта [35]. Наша модель показывает, что при этом пропускная способность Невского проспекта возрастет пропорционально отношению p*n(0) / p*n(k). Таким образом, принятое решение окажет существенную пользу в вопросе оздоровления дорожной ситуации на главной городской автомагистрали.

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

В данном эксперименте будем использовать экземпляр модели с ненулевой вероятностью перехода из состояния 1 в состояние 2 при условии наличия хотя бы одной из трех клеток – аргументов функции f в состоянии 1. При этом устанавливается соответствующее значение бита «жертва ДТП» для автомобиля впереди. Все остальные правила перехода из состояния в состояние остаются такими же, как и в эксперименте, который описан в разд. 3.2.

одновременно в состояние 2 в данном эксперименте является варьируемым параметром. То, как набор правил, описывающий экземпляр модели при pдтп = 0.02, представляется в виде текстового файла, показано ниже:

f(-1, -1, -1) = ((1, 1, 2, 0)) f(-1, 0, 0) = ((0.4, 1, 2, 0), (0.1, 1, 3, 0), (0.5, 1, 0, 0)) f(-1, 0, 1) = ((0.48, 1, 2, 0), (0.02, 2, 0, 3), (0.5, 1, 0, 0)) f(-1, 0, 2) = ((0.5, 1, 2, 0), (0.5, 1, 0, 0)) f(-1, 1, 0) = ((0.48, 1, 3, 0), (0.02, 2, 0, 2), (0.5, 1, 0, 0)) f(-1, 1, 1) = ((0.98, 1, 0, 0), (0.02, 2, 0, 2)) f(-1, 1, 2) = ((0.98, 1, 0, 0), (0.02, 2, 0, 2)) f(-1, 2, 0) = ((0.5, 1, 3, 0), (0.5, 1, 0, 0)) f(-1, 2, 1) = ((0.98, 1, 0, 0), (0.02, 2, 0, 3)) f(-1, 2, 2) = ((1, 1, 0, 0)) f(0, 0, -1) = ((0.4, 1, 2, 0), (0.1, 1, 1, 0), (0.5, 1, 0, 0)) f(0, 0, 0) = ((0.4, 1, 2, 0), (0.05, 1, 1, 0), (0.05, 1, 3, 0), (0.5, 1, 0, 0)) f(0, 0, 1) = ((0.38, 1, 2, 0), (0.1, 1, 1, 0), (0.02, 2, 0, 3), (0.5, 1, 0, 0)) f(0, 0, 2) = ((0.4, 1, 2, 0), (0.1, 1, 1, 0), (0.5, 1, 0, 0)) f(0, 1, -1) = ((0.48, 1, 1, 0), (0.02, 2, 0, 2), (0.5, 1, 0, 0)) f(0, 1, 0) = ((0.28, 1, 1, 0), (0.2, 1, 3, 0), (0.02, 2, 0, 2), (0.5, 1, 0, 0)) f(0, 1, 1) = ((0.48, 1, 1, 0), (0.02, 2, 0, 2), (0.5, 1, 0, 0)) f(0, 1, 2) = ((0.48, 1, 1, 0), (0.02, 2, 0, 2), (0.5, 1, 0, 0)) f(0, 2, -1) = ((0.5, 1, 1, 0), (0.5, 1, 0, 0)) f(0, 2, 0) = ((0.3, 1, 1, 0), (0.2, 1, 3, 0), (0.5, 1, 0, 0)) f(0, 2, 1) = ((0.48, 1, 1, 0), (0.02, 2, 0, 3), (0.5, 1, 0, 0)) f(0, 2, 2) = ((0.5, 1, 1, 0), (0.5, 1, 0, 0)) f(1, 0, -1) = ((0.48, 1, 2, 0), (0.02, 2, 0, 1), (0.5, 1, 0, 0)) f(1, 0, 0) = ((0.38, 1, 2, 0), (0.1, 1, 3, 0), (0.02, 2, 0, 1), (0.5, 1, 0, 0)) f(1, 0, 1) = ((0.48, 1, 2, 0), (0.02, 2, 0, 1), (0.5, 1, 0, 0)) f(1, 0, 2) = ((0.48, 1, 2, 0), (0.02, 2, 0, 1), (0.5, 1, 0, 0)) f(1, 1, -1) = ((0.98, 1, 0, 0), (0.02, 2, 0, 2)) f(1, 1, 0) = ((0.48, 1, 3, 0), (0.02, 2, 0, 2), (0.5, 1, 0, 0)) f(1, 1, 1) = ((0.98, 1, 0, 0), (0.02, 2, 0, 2)) f(1, 1, 2) = ((0.98, 1, 0, 0), (0.02, 2, 0, 2)) f(1, 2, -1) = ((0.98, 1, 0, 0), (0.02, 2, 0, 1)) f(1, 2, 0) = ((0.48, 1, 3, 0), (0.02, 2, 0, 1), (0.5, 1, 0, 0)) f(1, 2, 1) = ((0.98, 1, 0, 0), (0.02, 2, 0, 1)) f(1, 2, 2) = ((0.98, 1, 0, 0), (0.02, 2, 0, 1)) f(2, 0, -1) = ((0.5, 1, 2, 0), (0.5, 1, 0, 0)) f(2, 0, 0) = ((0.4, 1, 2, 0), (0.1, 1, 3, 0), (0.5, 1, 0, 0)) f(2, 0, 1) = ((0.48, 1, 2, 0), (0.02, 2, 0, 3), (0.5, 1, 0, 0)) f(2, 0, 2) = ((0.5, 1, 2, 0), (0.5, 1, 0, 0)) f(2, 1, -1) = ((0.98, 1, 0, 0), (0.02, 2, 0, 2)) f(2, 1, 0) = ((0.48, 1, 3, 0), (0.02, 2, 0, 2), (0.5, 1, 0, 0)) f(2, 1, 1) = ((0.98, 1, 0, 0), (0.02, 2, 0, 2)) f(2, 1, 2) = ((0.98, 1, 0, 0), (0.02, 2, 0, 2)) f(2, 2, -1) = ((1, 1, 0, 0)) f(2, 2, 0) = ((0.5, 1, 3, 0), (0.5, 1, 0, 0)) f(2, 2, 1) = ((0.98, 1, 0, 0), (0.02, 2, 0, 3)) f(2, 2, 2) = ((1, 1, 0, 0)) В качестве стартового состояния в данном эксперименте выступает базовое стартовое состояние – поле размера 4 30 клеток, где все клетки первоначально находятся в состоянии 0. При этом первоначально этот участок дороги пуст – на нем нет ни ям, ни движущихся автомобилей, ни припаркованных автомобилей.

Подробно базовое стартовое состояние описано в разд. 2.2.

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