ник Тюменского государственного университета. Физико-математические науки. Информатика. 2014. № 7. С. 157-165.
8. Обухов А.Г., Баранникова Д.Д. Особенности течения газа в начальной стадии формирования теплового восходящего закрученного потока// Известия вузов. Нефть и газ. 2014. № 6. С. 65-70.
9. Обухов А.Г., Сорокина Е.М. Математическое моделирование и численный расчет трехмерного конвективного течения газа // Известия вузов. Нефть и газ. 2013. № 6. С. 57-63.
10. Сорокина Е.М., Обухов А.Г. Численное исследование температурной зависимости скоростных характеристик нестационарного конвективного течения газа // Вестник Тюменского государственного университета. Физико-математические науки. Информатика. 2014. № 7. С. 147-156.
анализ и рефакторинг представления моделей транспортных потоков на основе клеточного автомата
Шинкарев А.А.
Южно-Уральский государственный университет, Челябинск, Россия
В статье представлен анализ нескольких фундаментальных математических моделей транспортных потоков, построенных на основе клеточного автомата, на предмет общих этапов и закономерностей. Также предложен подход рефакторинга шагов моделей, целью которого является улучшение структуры представления моделей в целом. Выделены ключевые особенности, полученные в результате процесса рефакторинга и анализа.
Ключевые слова: рефакторинг; моделирование; транспортный поток; клеточный автомат; дорожное движение; анализ; формализация.
analysis and refactoring of representation of traffic flow models based on cellular automata
Shinkarev A.A.
South Ural State University, Chelyabinsk, Russia
This paper represents analysis of several fundamental traffic flow mathematical models based on the theory of cellular automata. This analysis covers common steps and regularity of viewed models. Also this paper provides an approach of models steps refactoring with an eye to improve structure of models representation. Also the article contains extracted key features of models as a result of refactoring and analysis process.
Keywords: refactoring; modeling; transport flow; cellular automata; traffic; analysis; formalization.
введение
На сегодняшний день среди активно используемых подходов к моделированию транспортных потоков можно выделить направление, основанное на применении теории клеточных автоматов (ТКА). Основное отличие данного вида микромоделей заключается в относительной простоте поддержки, внедрения и анализа большинства из них.
Помимо простоты использования, также важным аргументом в пользу внедрения такого рода моделей является то, что можно вести расчеты в облаке одновременно на нескольких узлах кластера. Это осуществимо за счет того, что все клетки переходят в новое состояние параллельно в конце итерации моделирования. Таким образом, возможен процесс параллельной обработки изменений состояния клеток автомата.
Основными моделями, на которых базировались дальнейшие исследования моделирования транспортных потоков с помощью КА, являются: Правило 184 [1], Модель Нагеля-Шрекенберга [2], модель медленного старта [3], модель Кернера-Клёнова-Вольфа [4] и др.
Однако все то многообразие моделей на основе ТКА, которые существуют на сегодняшний день, лишь частично согласуется друг с другом по способу формализации их поведения. Хотя зачастую законы их функционирования имеют много общего.
Рассмотрим перечисленные выше фундаментальные модели подробнее и попробуем проанализировать их на предмет общих этапов и закономерностей, которые могли бы помочь формализовать процесс построения правил, которые обновляют состояние клеток моделей на основе ТКА.
В качестве инструмента формализации и перестроения рассматриваемых моделей будем использовать рефакторинг. Этот подход давно известен и широко применяется при разработке ООП систем, формальное описание представлено М. Фаулером в книге [5]. В данной статье программирование, в каком бы то ни было виде не рассматривается, однако основные принципы и подходы, сформулированные М. Фаулером, применимы и к представлению математических моделей транспортных потоков на основе ТКА.
правило 184
Рассмотрим данную модель применимо к движению автомобилей по однополосной дороге с максимальной скоростью равной одной ячейке за единицу времени.
Математическую модель смены состояния клетки можно записать следующим образом, здесь и далее первоначальная формулировка моделей базируется на материалах работы [6]:
1. Ускорение и торможение
v (t) = mingt - 1),1) (1)
2. Перемещение
n (t) = n(t - 1)+v(t) (2)
В формуле (1) комбинируется модификация скорости и валида-ция. Новым значением скорости v(t) становится g (t - 1). Здесь и далее v (t) - значение скорости в текущем такте, (t - 1) - предыдущий такт работы автомата, а g - функция возвращающая расстояние от
i-го транспортного средства (ТС) до едущего впереди. В качестве валидации выполняется проверка того, что полученная скорость не больше 1.
Формула (2) описывает перемещение текущего ТС вперед на количество ячеек равное новому значению скорости. Здесь и далее n. - функция, возвращающая порядковый номер ячейки для /-го TC.
Теперь попробуем декомпозировать первый шаг на два: изменение скорости и валидацию. Модель примет следующий вид:
1. Ускорение и торможение
v.(t) = g ft - 1) (3)
2. Валидация превышения скорости
if v(t) > 1 then v.(t) = 1 (4)
3. Перемещение
n (t) = n (t - 1) + v.(t) (5)
модель нагеля-Шрекенберга
Данная модель представляет собой стохастический многоклеточный автомат и имеет следующий вид:
1. Ускорение
v,(t) = mm(v,(t - 1) + 1, ^maX) (6)
2. Торможение
v (t) = min(v .(t), g(t - 1)) (7)
3. Случайные возмущения
if 4(t) <p then v.(t) = max(v.(t) - 1,0) (8)
4. Движение
n (t) = n .(t - 1) + v .(t) (9)
В формуле (6), как и в случае с моделью Правило 184, модифицируется скорость и валидируется полученное значение. Здесь и далее vmax -максимально допустимая скорость транспортного средства. Разделим первый шаг данной модели на два:
1. Ускорение
v (t) = v .(t - 1) + 1 (10)
2. Валидация превышения максимально допустимой скорости
if v (t) > v then v (t) = v (11)
Л ' max Л ' max v '
За счет поведения описанного в формуле (7) исключается возможность столкновение с впереди едущим ТС, в случае если полученная на первом шаге скорость больше расстояния до впереди едущего ТС. Перепишем данную проверку, используя логическое условие, а не функцию минимума.
3. Валидация столкновения с впереди едущим ТС
if v(t) > g(t - 1) then v (t) = g(t - 1) (12)
Выражение (8) вносит элемент стохастичности, который позволяет моделировать различные случайные процессы, проходящие во время движения. Здесь и далее Ç - случайная величина, распределенная равномерно. Данное выражение также как и шаг ускорения модифицирует скорость и ограничивает новое значение скорости нулём снизу. Снова разобьём шаг на два:
4. Случайные возмущения
if ¿(t) >p then v (t) = v (t) - 1 (13)
5. Валидация снижения скорости до отрицательного значения
if v (t) > 0 then v (t) = 0 (14)
На данном этапе мы получили 2 пары шагов, состоящих из модификации скорости и валидации. Теперь сгруппируем шаги изменяющие скорость и валидирующие её новое значение. Перепишем полученную модель таким образом, чтобы за группой шагов модификации скорости шла группа шагов валидации:
1. Ускорение
v (t) = v (t - 1) + 1 (15)
2. Случайные возмущения
if ¿(t) >p then v(t) = v(t) - 1 (16)
3. Валидация снижения скорости до отрицательного значения
if v (t) > 0 then v(t) = 0 (17)
4. Валидация превышения максимально допустимой скорости
if v (t) > v then v (t) = v (18)
max max
5. Валидация столкновения с впереди едущим ТС
if v.(t) > g ft- 1) then v.(t) = g ft- 1)
6. Движение
n ft) = n ft - 1) + v .(t)
Таким образом, в общем случае удаётся выделить моделей:
1. Применение шагов изменения скорости
2. Применение шагов валидации
3. Движение с новой скоростью
модель медленного старта
Модели, рассмотренные выше, равно как и их аналоги имеют недостаток - они не способны воспроизводить явление резкого спада пропускной способности и эффект гистерезиса при переходе к фазе синхронизированного потока. Причина в слишком быстром оттоке автомобилей из образовывающихся заторов. Внедрение правила медленного старта (англ. slow-to-start) помогает сделать скорость оттока ТС из пробки меньше скорости притока.
Набор шагов модели, ограниченной скоростью в 1 ячейку за единицу времени, выглядит следующим образом:
1. Торможение
if v ft - 1) > g ft - 1) then v ft) = g ft - 1) (21)
2. Запаздывающее ускорение
if v ft - 1) = 0 and g ft - 1) > 2 then v ft) = 1 (22)
3. Движение
n ft) = n ft - 1) + v ft) (23)
Согласно предложенной стратегии декомпозиции и группировки шагов на три этапа представим данную модель в следующем виде:
1. Ускорение
v ft) = 1 (24)
2. Валидация преждевременного ускорения
if v ft - 1) = 0 and g ft - 1) < 2 then v ft) = 0 (25)
(19)
(20)
3 этапа работы
3. Валидация столкновения с впереди едущим ТС
if v/t) > g ff - 1) then v.(t) = g (t - 1) (26)
4. Движение
n (f) = n (t - 1) + v.(t) (27)
Стоит отметить, что как в модели Нагеля-Шрекенберга присутствует шаг валидации столкновения с впереди едущим ТС.
многофакторная модель Данная модель, описанная в работе [6], является компиляцией наиболее интересных частей, рассмотренных выше моделей.
Математическое описание данной модели выглядит следующим образом:
1. Ускорение
if %f) < Pfts and v (f - 1) = 0 and g(f - 1) < dsts
then v.(t) = 0 (28)
v (t) = min (v (t), v (t - 1) + 1,v ,...
i v Л Л ' ' max
v. (t - 1), v (t - 1), v (c.))
l max1 v reCj mi"
Данный шаг совмещает в себе ускорение, правило медленного старта и валидацию превышения максимально допустимой в данный момент скорости. Здесь и далее psts - вероятность срабатывания правила медленного старта, dtts - предельная дистанция, при которой правило медленного старта все ещё применимо, v/ max - скорость максимально допустимая ПДД, с учетом текущего положения ТС, vrec - рекомендуемая скорость, с учетом текущего положения ТС, vm(c ) - максимальная скорость, которую может развить данное ТС. 1. Торможени
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.