МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ ПОТОКОВ АВТОТРАНСПОРТА НА ОСНОВЕ МАКРО- И МИКРОСКОПИЧЕСКИХ ПОДХОДОВ
Журнал: ВЕСТНИК АСТРАХАНСКОГО ГОСУДАРСТВЕННОГО ТЕХНИЧЕСКОГО УНИВЕРСИТЕТА. СЕРИЯ: УПРАВЛЕНИЕ, ВЫЧИСЛИТЕЛЬНАЯ ТЕХНИКА И ИНФОРМАТИКА
Том 2014 № 1
, 2014
Рубрики: МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ
Авторы:
1.
Институт прикладной математики им. М. В. Келдыша Российской академии наук
2.
Институт прикладной математики им. М. В. Келдыша Российской академии наук
3.
Институт прикладной математики им. М. В. Келдыша Российской академии наук
4.
Институт математики Национальной академии Беларуси
Тип:
Статья
Страницы:
с 130
по 139
Статус:
Опубликован
Получено:
05.01.2014
Одобрено:
25.01.2014
Опубликовано:
25.01.2014
Классификаторы:
ВАК 05.12.2013 Системы, сети и устройства телекоммуникаций
ВАК 05.13.01 Системный анализ, управление и обработка информации (по отраслям)
ВАК 05.13.06 Автоматизация и управление технологическими процессами и производствами (по отраслям)
ВАК 05.13.10 Управление в социальных и экономических системах
ВАК 05.13.18 Математическое моделирование, численные методы и комплексы программ
ВАК 05.13.19 Методы и системы защиты информации, информационная безопасность
УДК 656.13:519.872
ГРНТИ 20.01 Общие вопросы информатики
ГРНТИ 28.01 Общие вопросы кибернетики
ГРНТИ 49.01 Общие вопросы связи
ГРНТИ 50.01 Общие вопросы автоматики и вычислительной техники
ГРНТИ 82.01 Общие вопросы организации и управления
ББК 39.31:22.183.5
ВАК 05.13.01 Системный анализ, управление и обработка информации (по отраслям)
ВАК 05.13.06 Автоматизация и управление технологическими процессами и производствами (по отраслям)
ВАК 05.13.10 Управление в социальных и экономических системах
ВАК 05.13.18 Математическое моделирование, численные методы и комплексы программ
ВАК 05.13.19 Методы и системы защиты информации, информационная безопасность
УДК 656.13:519.872
ГРНТИ 20.01 Общие вопросы информатики
ГРНТИ 28.01 Общие вопросы кибернетики
ГРНТИ 49.01 Общие вопросы связи
ГРНТИ 50.01 Общие вопросы автоматики и вычислительной техники
ГРНТИ 82.01 Общие вопросы организации и управления
ББК 39.31:22.183.5
Язык материала:
русский
Ключевые слова:
автотранспортные потоки, микроскопические и макроскопические модели, многополосное движение
Аннотация (русский):
Рассматриваются два основных подхода к математическому моделированию потоков транспорта на протяжённых магистралях и элементах городской сети, а именно получают дальнейшее развитие модели, созданные авторами ранее: макроскопическая, основанная на квазигазодинамической системе уравнений, и микроскопическая, использующая подход клеточных автоматов. Обе модели описывают случай многополосного движения, т. е. учитывают реальную геометрию трассы. Результаты тестовых расчётов демонстрируют хорошую согласованность моделей, а также их адекватность реальным дорожным ситуациям.
Рассматриваются два основных подхода к математическому моделированию потоков транспорта на протяжённых магистралях и элементах городской сети, а именно получают дальнейшее развитие модели, созданные авторами ранее: макроскопическая, основанная на квазигазодинамической системе уравнений, и микроскопическая, использующая подход клеточных автоматов. Обе модели описывают случай многополосного движения, т. е. учитывают реальную геометрию трассы. Результаты тестовых расчётов демонстрируют хорошую согласованность моделей, а также их адекватность реальным дорожным ситуациям.
Ключевые слова:
автотранспортные потоки, микроскопические и макроскопические модели, многополосное движение
автотранспортные потоки, микроскопические и макроскопические модели, многополосное движение
Введение В связи с бурным развитием автотранспорта, быстрым увеличением количества автомобилей у населения вычислительный эксперимент при строительстве новых дорог и развязок, управляемых перекрёстков и т. д. приобретает в последнее время всё большее, а в некоторых случаях и решающее значение. Математическое моделирование потоков автотранспорта начало развиваться в 50-е гг. XX в., тогда же сформировались основные подходы: так называемые макроскопический и микроскопический, различающиеся способом описания движения автомобильных потоков. Первый из них – макроскопический [1] – рассматривает достаточно протяжённые расстояния при достаточном скоплении транспортных средств, когда можно вводить осреднённые характеристики, аналогичные характеристикам жидкости или газа в газовой динамике, такие как плотность (количество автомобилей на одной полосе и единице длины трассы) и средняя скорость, с которой каждый автомобиль вынужден двигаться при достаточно плотном движении. В этих условиях все водители вынуждены придерживаться одинаковых правил и стратегий и подчиняться общим закономерностям. В такой ситуации справедливо приближение сплошной среды, используемой в динамике жидкости и газа. В своё время для описания газодинамических течений с успехом начал использоваться кинетический подход, в частности была выведена кинетически согласованная система уравнений (КСРС) [2], позволяющая описывать течения в большом диапазоне чисел Маха, в том числе и течения слабосжимаемых жидкостей. В данном исcледовании движение автотранспорта в стеснённом режиме можно рассматривать как поток слабосжимаемой жидкости и для его описания использовать аналогию с КСРС и родственной им квазигазодинамической (КГД) системой уравнений. Второй подход – микроскопический – рассматривает каждый автомобиль как самостоятельную частицу. Эта частица может иметь свою собственную стратегию движения, свою текущую скорость, которая может изменяться со временем и иметь своё собственное ограничение. Конечные цели автомобилей могут быть различными. Движение автомобилей происходит по некоторым общим законам, обеспечивающим, помимо правил передвижения, безопасность движения. В рамках микроскопического подхода [3] были созданы и предложены разными авторами такие модели, как модель следования за лидером, модель оптимальной скорости, модель «умного» водителя и др. В рамках данного исследования дальнейшее развитие получит предложенная нами ранее микроскопическая модель, основанная на теории клеточных автоматов, являющаяся обобщением одномерной модели Нагеля – Шрекенберга [4]. Отличие предлагаемых моделей от имеющихся в настоящее время аналогов в том, что в них учитывается реальная геометрия трассы, её многополосность, возможность сужения или расширения и т. д., причём переход в соседние полосы рассматривается как реальный физический процесс, а не путем введения в правые части уравнений дополнительных источников или стоков. Такой подход слишком громоздок, а в случае четырёх и более полос вообще труднореализуем. Макроскопическая модель Как упоминалось выше, в случае макроскопического подхода к описанию движения автотранспорта, по аналогии с газовой динамикой могут быть введены некоторые осреднённые характеристики движения. Такими характеристиками являются, например, плотность потока как число машин на полосе на единицу длины дороги, скорость как средняя скорость автомобилей, а также поток как функция плотности и скорости. Система уравнений для описания автомобильного движения отличается от систем уравнений газовой динамики тем, что в ней присутствуют члены, возникающие благодаря наличию так называемого «человеческого фактора». Это, например, ускоряющая или замедляющая сила: (1) где ускорение или замедление зависит от того, насколько реальная скорость отличается от равновесной скорости, т. е. скорости, характерной для движения при данной плотности машин: , (2) При этом равновесная скорость , (3) где – скорость свободного движения автомобилей; – плотность, при которой возникают автомобильные «пробки» (как видно из формулы, при плотности потока, равной плотности «пробки», равновесная скорость становится равной нулю, а при малой плотности автомобилей становится равной скорости свободного движения), а время релаксации (реакции водителя на дорожную ситуацию) (4) где и – феноменологические константы; скоростное ограничение: , где – максимальная разрешённая скорость. Вводится аналог давления как реакция водителя на ситуацию впереди автомобиля: (5) где , , и – феноменологические константы. Следует отметить, что, в отличие от газовой динамики, в случае автотранспортных потоков перемещения вдоль и поперёк трассы неэквивалентны (например, вдоль трассы отрицательная скорость невозможна, в то время как перестроение из полосы в полосу возможно как в левую, так и в правую стороны). В [5, 6] для описания перехода машины из одной полосы в другую было введено понятие «боковой» скорости. Таким образом, машины могут перестраиваться в полосу с большей скоростью или с меньшей плотностью или если водитель хочет достичь определённой цели, например выехать с трассы. В данном исследовании предлагается ввести понятие равновесной боковой скорости, которая состоит из следующих трёх слагаемых: – перестроение на полосу с большей скоростью – ; – перестроение на полосу с меньшей плотностью – ; – движение к определённой цели – Здесь , , – феноменологические константы; – координаты желаемой цели. Тогда равновесная боковая скорость будет описываться следующим уравнением: (6) В конечном виде двумерная система уравнений, описывающая автотранспортные потоки, была получена по аналогии с КГД-системой [3]. Одним из критериев газодинамических течений является число Кнудсена – отношение характерной длины газовой среды (длина свободного пробега молекул) к характерной длине течения. В газовой динамике . Для автотранспортных потоков в качестве длины свободного пробега можно рассматривать среднее расстояние между автомобилями, следовательно, в этом случае . КГД-система хорошо зарекомендовала себя в широком диапазоне чисел Кнудсена, в том числе и в сторону его увеличения, что явилось причиной ее использования для вывода системы уравнений транспортных потоков. По аналогии с КГД-системой вводятся дополнительные потоки массы, обеспечивающие сглаживание решения на расстоянии, равном характерной длине рассматриваемой среды. Для транспортных потоков характерные длины вдоль и поперёк движения не равны друг другу. Вдоль дороги это среднее расстояние между автомобилями, зависящее от скорости а поперёк дороги характерная длина – это ширина одной полосы. В КГД-системе вводится также понятие характерного времени (время преодоления молекулой длины свободного пробега). Для автотранспортных потоков можно также ввести характерное время как пересечение некоторой точки несколькими автомобилями: , (7) Для простоты и можно считать неизменными, т. к. при синхронизованном движении они мало зависят от скорости. В правой части уравнения неразрывности вводятся дополнительные потоки и , сглаживающие решение вдоль и поперёк магистрали: (8) (9) Аналогичные потоки вводятся и в уравнения сохранения импульса. Учитывая (1)–(9) и обобщая всё вышесказанное, мы получили следующую систему уравнений, описывающую движение транспортных потоков: В модели используется большое количество констант и параметров, которые можно определить только эмпирическим путём из статистических или экспериментальных данных. В расчётах, приведённых ниже, использовались следующие значения: Микроскопическая модель При построении микроскопической модели, способной адекватно описывать движение автотранспорта на небольших расстояниях, использовалась теория клеточных автоматов. Основой послужила одномерная модель Нагеля – Шрекенберга [4], в которой трасса представляется в виде одномерной решетки. Пространство имеет дискретную структуру, время тоже дискретно, т. е. рассматривается состояние всей системы в отдельные последовательные моменты времени. На каждом слое по времени происходит обновление состояния системы по определённым правилам с определёнными вероятностными характеристиками. В каждую ячейку решетки может быть помещена (или нет) частица, которая в данной модели означает машину. Частицы перескакивают с одной ячейки на другую (свободную) в одном направлении. В случае однополосного движения они не могут обгонять друг друга. Так как время и пространство дискретны, скорость и ускорение также принимают только дискретные значения. Правила передвижения одинаковы для всех ячеек и применяется ко всем ячейкам параллельно, т. е. за один шаг по времени меняются все ячейки. В модели Нагеля – Шрекенберга для каждой машины заданы скорость от до некоторой величины , величина – расстояние между текущей машиной и следующей перед ней, – скорость текущей машины с номером . Правило обновления состоит из следующих подшагов: 1. Ускорение. Если , то скорость -го автомобиля увеличивается на единицу, если , то скорость не изменяется. 2. Торможение. Если , то скорость n-го автомобиля уменьшается до . 3. Случайные возмущения. Если, то скорость -го автомобиля может быть уменьшена на единицу с вероятностью , скорость не изменяется, если . 4. Движение. Каждый автомобиль продвигается вперед на количество ячеек, соответствующее его новой скорости после выполнения предыдущих шагов. Для моделирования многополосного движения приведенная выше модель была обобщена на двумерный случай. Трасса в этом случае представляет собой двумерную решетку, где количество ячеек в поперечном направлении соответствует числу полос трассы. В такой модели разрешены перестроения машин из полосы в полосу и обгоны. Процесс обновления состояний ячеек делится на два подшага. 1. Для каждой машины выясняется возможность и необходимость смены полосы. Производится смена полосы. Этот подшаг выполняется параллельно для всех машин. 2. Производится движение вперед по каждой полосе по правилам однополосного движения. Смена полос должна происходить за один временной шаг. Если в одном направлении существуют больше, чем две полосы, то может возникать конфликт, когда две машины с крайних полос желают сместиться в среднюю и занять одну и ту же ячейку. Такой конфликт легко преодолеть, если разрешить перестроение вправо только на четных шагах, а влево – только на нечетных. Условия для смены полосы выглядят следующим образом. 1. Машина находится в зоне, где разрешена смена полосы. 2. Смена полосы ведет к увеличению скорости (снижению плотности) или необходима для достижения цели. 3. Ячейка, на которую перестраивается машина, свободна. 4. Условие безопасности: расстояние на целевой полосе позади больше или равно Vmax, впереди больше или равно V машины, и при этом смена полосы происходит с некоторой вероятностью. Алгоритм, предлагаемый в настоящем исследовании, обеспечивает возможность достижения цели. Целями автомобилей при многополосном движении могут быть, например, съезд с дороги или поворот в определенную сторону на светофоре. В обоих случаях машины, начиная с определенного момента времени, стремятся перестроиться в целевую полосу, игнорируя значения плотности и скорости на ней. Таким образом, в описываемой модели для каждой машины необходимо хранить параметр цели. Цели у автомобилей обязательны, и поменять их они не могут. Тестовые расчёты Далее представлены результаты расчетов двумерных тестовых задач, проведенных с использованием макроскопической и микроскопической моделей. Первая задача – движение по трассе, имеющей локальное расширение (рис. 1). Рис. 1. Трасса с локальным расширением На рис. 2 показаны результаты расчётов, полученные с использованием макроскопической модели. Рис. 2. Поле плотности на четыре момента времени Сначала на широком участке дороги плотность автомобилей падает (рис. 2). Однако со временем в точке сужения трассы она нарастает, что приводит в конце концов и к увеличению плотности в средней части трассы по сравнению с тем значением, которое было в начале движения. В результате можно сделать вывод о том, что локальное расширение ухудшает общую ситуацию на дороге: пропускная способность трассы с локальным расширением меньше, чем была бы у трассы без расширения. На рис. 3 приведён график осреднённой по ширине трассы плотности, посчитанной с использованием микроскопической модели. Видно, что в конце расширения также наблюдается уплотнение потока. Рис. 3. Осреднённая плотность вдоль трассы Для сравнения та же задача была посчитана с использованием коммерческого программного обеспечения Aimsun TSS [7]. На рис. 4 приведены результаты расчётов. Рис. 4. Поле плотности, полученное с использованием Aimsun TSS Из рис. 4 видно, что использованное программное обеспечение не позволяет получить более точное описание структуры течения – представлены только средние значения плотности на трёх самых крупных деталях автотрассы. Как и в расчётах с использованием микромодели, в средней части трассы наблюдается увеличение плотности автомобильного потока, что приводит к снижению пропускной способности данного участка. Второй тестовой задачей была задача о движении автотранспорта на регулируемом перекрёстке. Целью этой задачи является поиск оптимального светофорного режима, а именно определение длительности сигналов светофоров, обеспечивающей минимальное время прохождения перекрёстка всеми участниками движения. Перекрёсток состоит из двух пересекающихся дорог, по которым автомобили движутся в двух направлениях, и каждое направление имеет по две полосы. На рис. 5 представлено состояние перекрёстка в некоторый момент времени. На полосах движения изображены автомобили, различающиеся по конечной цели. Каждому автомобилю предписывается своя цель - после прохождения перекрёстка оказаться на заданной дороге. Рис. 5. Постановка задачи о движении на перекрёстке На пересечении дорог стоят светофоры, которые пропускают машины в определенных направлениях в определенные моменты времени. Всего у светофоров существуют 4 фазы работы. Порядок их переключения и возможность пропуска в различных направлениях соответствуют некоторому реальному объекту г. Москвы. По условиям задачи на двух направлениях - снизу и справа - поток машин значительно превышает поток машин на двух других направлениях. При подъезде к перекрёстку выполняется следующий алгоритм: 1. За 200 метров до светофора происходит перестроение из полосы в полосу по вышеописанным правилам или запрет перестроения, если это необходимо для поворота (согласно правилам дорожного движения). 2. Осуществляется ускорение или торможение автомобиля на выбранной полосе согласно модели Нагеля – Шрекенберга. 3. При следующих условиях происходит дополнительное снижение скорости: 3.1. Если машина собирается поворачивать на перекрестке и находится в пределах 15 клеток от поворота, то ее скорость ограничивается двумя ячейками. При достижении точки поворота машина останавливается. 3.2. Учет светофорного режима: машины сбрасывают скорость при приближении к горящему красному сигналу светофора: если V > D - 1 , то V = D - 1, где D – дистанция до светофора. 3.3. Предотвращение столкновений. Если V > d - 1, то V = d - 1, где d – дистанция до ближайшей машины на полосе либо на перекрестке. 4. Случайные возмущения – аналогично модели Нагеля – Шрекенберга. 5. Перемещение автомобилей с учётом изменений скорости, возникших на шагах 3-4. 6. Поворот. Автомобили, находящиеся на точке поворота и имеющие соответствующую цель, меняют дорогу. 7. Начинается новый временной шаг. На рис. 6 представлены результаты расчётов, проведенных с использованием предложенной нами микроскопической модели и программного обеспечения Aimsun TSS. При различных светофорных режимах (длительностях фаз светофоров) проводилось исследование пропускной способности перекрестка. Рис. 6. Пропускная способность перекрестка при различных режимах работы светофора Меняя длительность фаз светофоров, можно повысить пропускную способность перекрёстка, т. е. увеличить количество автомобилей, пересёкших перекрёсток за 10 минут. Из рис. 6 можно сделать вывод о том, какие режимы обеспечивают наибольшую и наименьшую пропускную способность перекрестка. Полученные результаты для микроскопической модели и для Aimsun TSS качественно совпадают. Заключение В заключение отметим, что оба предложенных алгоритма расчётов обладают внутренним параллелизмом и допускают эффективную адаптацию к высокопроизводительным многопроцессорным системам, в том числе к суперкомпьютерам с гибридной архитектурой на базе графических ускорителей вычислений. В обоих случаях в качестве основного принципа распараллеливания можно использовать геометрический параллелизм и модель передачи сообщений: расчетная область разбивается на подобласти, вычисления в которых проводятся одновременно на разных процессорах (ядрах CPU или графических процессорах), на внутренних границах подобластей производится обмен информацией. Для обеспечения высокой эффективности параллельного счета и оптимальной балансировки загрузки процессоров существенно, чтобы процессоры были загружены равномерно и время полезных расчетов преобладало над временем операций обмена и временем загрузки/выгрузки данных из оперативной памяти в собственную память GPU и обратно. В этой связи целесообразно разделять дорожную сеть на некоторые стандартные элементы, например прямой участок дороги, четырехсторонний перекресток, Т-образный перекресток (рис. 7). road2.png node2.png node3.png а б в Рис. 7. Стандартные элементы улично-дорожной сети: а – прямой участок дороги; б – четырехсторонний перекресток; в – Т-образный перекресток При многопроцессорной реализации эти стандартные элементы могут рассчитываться разными процессорами, при этом один элемент должен целиком размещаться в памяти одного процессора за исключением прямого участка дороги, который можно разбивать на любое количество подобластей в зависимости от его протяженности. Разрабатываемые параллельные алгоритмы и программы для моделирования движения автотранспорта могут послужить ядром интеллектуальных транспортных систем мегаполисов, что позволит проводить исследования транспортных потоков на масштабных дорожных сетях в режиме реального времени и способствовать улучшению ситуации на дорогах.
1. Lighthill M. H. On kinematic waves: A theory of traffic flow on long crowded roads / M. H. Lighthill, G. B. Witham // Proc. Royal. Soc. Ser. A. 1955. Vol. 229, N 1178. P. 317-345.
2. Четверушкин Б. Н. Кинетические схемы и квазигазодинамическая система уравнений / Б. Н. Четверушкин. М.: МАКС Пресс, 2004. 332 с.
3. Klar A. A hierarchy of models for multilane vehicular traffic I: Modeling / A. Klar, R. Wegener R. SIAM J. Appl. Math., 1999, vol. 59, pp. 983-1001.
4. Nagel K. A Cellular automation model for freeway traffic / K. Nagel, M. Schreckenberg // J. Phys. I France. 1992. Vol. 2. P. 2221-2229.
5. Карамзин Ю. Н. Двумерная модель автомобильных потоков / Ю. Н. Карамзин, М. А. Трапезникова, Б. Н. Четверушкин, Н. Г. Чурбанова // Математическое моделирование. 2006. Т. 18, № 6. С. 85-95.
6. Сухинова А. Б. Двумерная макроскопическая модель транспортных потоков / А. Б. Сухинова, М. А. Трапезникова, Б. Н. Четверушкин, Н. Г. Чурбанова // Математическое моделирование. 2009. Т. 21, № 2. С. 118-126.
7. [Электронный ресурс]: http://www.aimsun.com.
