Модель дорожного движения Бихама – Миддлтона – Левина - Biham–Middleton–Levine traffic model - Wikipedia

Эта статья о модели транспортного потока. Для модели турбулентности при горении см. Модель Брея – Мосса – Либби.

В Модель дорожного движения Бихама – Миддлтона – Левина это самоорганизующийся клеточный автомат модель транспортного потока. Он состоит из ряда автомобилей, представленных точками на решетке со случайной начальной позицией, где каждая машина может быть одного из двух типов: те, которые движутся только вниз (показаны синим в этой статье), и те, которые движутся только по направлению к справа (показано красным в этой статье). Два типа автомобилей по очереди двигаются. В течение каждого хода все машины соответствующего типа продвигаются на один шаг, если они не заблокированы другой машиной. Его можно считать двумерным аналогом более простого Правило 184 модель. Возможно, это простейшая система с фазовыми переходами и самоорганизация.^[1]

История

Модель движения Бихама – Миддлтона – Левина была впервые сформулирована Офер Бихам, А. Алан Миддлтон и Дов Левин в 1992 г.^[2] Бихам и другие обнаружили, что по мере увеличения плотности трафика устойчивое состояние транспортный поток внезапно перешел от плавного движения к полной пробке. В 2005 году, Раисса Д'Суза Установлено, что для некоторых плотностей движения существует промежуточная фаза, характеризующаяся периодическими заторами и плавным потоком.^[3] В том же году Энджел, Холройд и Мартин были первыми, кто строго доказал, что при плотностях, близких к единице, система всегда будет заклинивать.^[4] Позже, в 2006 году, Тим Остин и Итаи Бенджамини обнаружили, что для квадратной решетки со стороной N модель всегда будет самоорганизовываться для достижения полной скорости, если их меньше, чем N/ 2 машины.^[5]

Пространство решетки

Основной многоугольник тора, по которому движутся автомобили

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

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

Фазовые переходы

Несмотря на простоту модели, в ней есть две четко различимые фазы: застрявшая фаза, а сыпучая фаза.^[2] Для небольшого количества автомобилей система обычно организовать себя для достижения плавного потока трафика. Напротив, при большом количестве автомобилей система будет заблокирована до такой степени, что ни одна машина не двинется с места. Как правило, в квадратной решетке переходная плотность составляет примерно 32% от количества автомобилей, равного возможному пространству в решетке.^[6]

Воспроизвести медиа А сыпучая фаза наблюдается на прямоугольной решетке 144 × 89 с плотностью движения 28%

Воспроизвести медиа А глобально заклинившая фаза наблюдается на прямоугольной решетке 144 × 89 с плотностью движения 60%

Решетка 512 × 512 с плотностью 27% после 64000 итераций. Трафик находится в фазе свободного движения.

Решетка 512 × 512 с плотностью 29% после 64000 итераций. Трафик находится в фазе свободного движения.

Решетка 512 × 512 с плотностью 38% после 64000 итераций. Трафик находится в фазе глобальных пробок.

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

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

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

Промежуточная фаза

Промежуточная фаза возникает вблизи переходной плотности, сочетая в себе черты как застрявшей, так и сыпучей фаз. В основном есть две промежуточные фазы - беспорядочный (что могло быть метастабильный ) и периодический (которые доказуемо стабильны).^[3] На прямоугольных решетках с совмещать размеров существуют только периодические орбиты.^[3] В 2008 г. периодические промежуточные фазы наблюдались также в квадратных решетках.^[7] Однако на квадратных решетках чаще наблюдаются неупорядоченные промежуточные фазы, которые имеют тенденцию к доминировать плотности близкие к переходной области.

Воспроизвести медиа А периодический промежуточная фаза наблюдается на прямоугольной решетке 144 × 89 с плотностью движения 38%

Воспроизвести медиа А беспорядочный промежуточная фаза наблюдается на прямоугольной решетке 144 × 89 с плотностью движения 39%

Решетка 512 × 512 с плотностью 31% после 64000 итераций. Движение находится в неупорядоченной промежуточной фазе.

Решетка 512 × 512 с плотностью 33% после 64000 итераций. Движение находится в неупорядоченной промежуточной фазе.

Решетка 512 × 512 с плотностью 37% после 64000 итераций. Движение находится в неупорядоченной промежуточной фазе.

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

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

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

Строгий анализ

Несмотря на простоту модели, строгий анализ очень нетривиален.^[6] Тем не менее, были математические доказательства относительно модели движения Бихама – Миддлтона – Левина. Доказательства пока ограничиваются экстремальной плотностью движения. В 2005 году Александр Холройд и другие доказал, что при плотностях, достаточно близких к единице, в системе не будет автомобилей, движущихся бесконечно часто.^[4] В 2006 году Тим Остин и Итаи Бенджамини доказали, что модель всегда достигнет фазы свободного движения, если количество автомобилей меньше половины длины ребра квадратной решетки.^[5]

Неориентируемые поверхности

Модель обычно изучается на ориентируемой тор, но можно реализовать решетку на Бутылка Клейна.^[8] Когда красные автомобили достигают правого края, они снова появляются на левом краю, за исключением перевернутых вертикально; те, что внизу, теперь наверху, и наоборот. Более формально для каждого ${\displaystyle y\in \lbrace 0,\ldots ,N-1\rbrace }$, красная машина выезжает с сайта ${\displaystyle (N-1,y)}$ войдет на сайт ${\displaystyle (0,N-y-1)}$. Также возможно реализовать его на реальная проективная плоскость.^[8] Помимо красных машин, то же самое делается и для синих машин: для каждого ${\displaystyle x\in \lbrace 0,\ldots ,N-1\rbrace }$, синяя машина выезжает с сайта ${\displaystyle (x,N-1)}$ войдет на сайт ${\displaystyle (N-x-1,0)}$.

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

Рандомизация

Рандомизированный вариант модели трафика BML, названный BML-R, был изучен в 2010 году.^[9] При периодических границах вместо обновления всех автомобилей одного цвета сразу на каждом шаге рандомизированная модель выполняет ${\displaystyle L^{2}}$ обновления (где ${\displaystyle L}$ - длина стороны предположительно квадратной решетки): каждый раз выбирается случайная ячейка, и, если она содержит автомобиль, она перемещается в следующую ячейку, если это возможно. В этом случае промежуточное состояние, наблюдаемое в обычной модели трафика BML, не существует из-за недетерминированного характера рандомизированной модели; вместо этого переход от застрявшей фазы к свободно текущей фазе резкий.

В открытых граничных условиях, вместо того, чтобы машины, съезжающие с одного края, оборачивались вокруг другого, с вероятностью добавляются новые автомобили на левом и верхнем краях. ${\displaystyle \alpha }$ и удалены с правого и нижнего краев ${\displaystyle \beta }$ соответственно. В этом случае количество автомобилей в системе может со временем меняться, и локальные заторы могут привести к тому, что решетка будет сильно отличаться от обычной модели, например, при одновременном существовании заторов и участков со свободным течением; содержащие большие пустые пространства; или содержащие в основном автомобили одного типа.^[9]

Рекомендации

1. Д'Суза, Раиса. «Транспортная модель Бихама – Миддлтона – Левайна». Получено 4 января 2015.
2. Бихам, Офер; Миддлтон, А. Алан; Левин, Дов (ноябрь 1992 г.). «Самоорганизация и динамический переход в моделях транспортного потока». Phys. Ред. А. Американское физическое общество. 46 (10): R6124 – R6127. arXiv:cond-mat / 9206001. Bibcode:1992ПхРвА..46.6124Б. Дои:10.1103 / PhysRevA.46.R6124. ISSN  1050-2947. PMID  9907993. Архивировано из оригинал на 2013-02-24. Получено 14 декабря 2012.
3. Д'Суза, Раиса М. (2005). «Сосуществующие фазы и решеточная зависимость модели клеточного автомата для транспортного потока». Phys. Ред. E. Американское физическое общество. 71 (6): 066112. Bibcode:2005PhRvE..71f6112D. Дои:10.1103 / PhysRevE.71.066112. PMID  16089825. Архивировано из оригинал 24 февраля 2013 г.. Получено 14 декабря 2012.
4. Ангел, Омер; Холройд, Александр Э .; Мартин, Джеймс Б. (12 августа 2005 г.). «Застрявшая фаза модели движения Бихама – Миддлтона – Левайна». Электронные коммуникации в вероятности. 10: 167–178. arXiv:математика / 0504001. Дои:10.1214 / ECP.v10-1148. ISSN  1083-589X. Архивировано из оригинал на 2016-03-04. Получено 14 декабря 2012.
5. Остин, Тим; Бенджамини, Итаи (2006). «Для какого количества автомобилей должна происходить самоорганизация в модели движения Бихам – Миддлтон – Левин из любой возможной стартовой конфигурации?». arXiv:математика / 0607759.
6. Холройд, Александр Э. «Транспортная модель Бихама – Миддлтона – Левина». Получено 14 декабря 2012.
7. Линеш, Николас Дж .; Д'Суза, Раиса М. (15 октября 2008 г.). «Периодические состояния, локальные эффекты и сосуществование в модели пробок BML». Physica A. 387 (24): 6170–6176. arXiv:0709.3604. Bibcode:2008PhyA..387.6170L. Дои:10.1016 / j.physa.2008.06.052. ISSN  0378-4371.
8. Кампора, Даниэль; де ла Торре, Хайме; Гарсиа Васкес, Хуан Карлос; Капаррини, Фернандо Санчо (август 2010 г.). «Модель BML на неориентируемых поверхностях». Physica A. 389 (16): 3290–3298. Bibcode:2010PhyA..389.3290C. Дои:10.1016 / j.physa.2010.03.037.
9. Дин, Чжун-Цзюнь; Цзян, Руи; Ван, Бинг-Хун (2011). «Транспортный поток в модели Бихама – Миддлтона – Левина с правилом случайного обновления». Физический обзор E. 83 (4): 047101. Bibcode:2011PhRvE..83d7101D. Дои:10.1103 / PhysRevE.83.047101.

внешняя ссылка

• Реализация CUDA Даниэль Лу
• Реализация WebGL Джейсон Дэвис
• Реализация JavaScript от Maciej Baron