Этюды для программистов

17. Тише едешь — дальше будешь, или Моделирование движения на автостраде

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

Вспомните, как вы однажды «с ветерком» катили по шоссе, миль на 5 превышая допустимую скорость, хотя машин было много. Внезапно все стали еле ползти, и вам тоже пришлось нажать на тормоза. Затем последовала четверть, половина, а то и целая миля конвульсивного чередования остановок и движения. Наконец затор остался позади, и вы смогли вновь прибавить скорость. Но все это происходило без всякой видимой причины! Что же нарушило плавность движения?

Для объяснения причины задержки необходимо привлечь гидродинамику. Движущиеся по шоссе автомобили ведут себя во многом аналогично частицам протекающей в трубе жидкости. Если плотность и скорость частиц достаточно велики, любая кратковременная задержка потока приведет к возникновению ударной волны. Ударная волна — это область очень высокой плотности; автомобили (или частицы) резко замедляются, попадая в эту область, и затем ускоряются, когда, преодолев довольно четко очерченный ударный фронт, оказываются в области с гораздо более низкой плотностью. Ударная волна продолжает существовать длительное время, медленно двигаясь навстречу потоку и медленно рассеиваясь. Отметим, что рассеяние объясняется уменьшением плотности в ударной области и может быть ускорено, если водители заранее слегка притормозят, увидев впереди затор.

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

Для проведения эксперимента нужны генератор автомобилей и генератор возмущений. В начале каждого эксперимента автострада пуста. Запустите генератор автомобилей, который поместит машину на дорогу, придаст ей скорость и выберет интервал до порождения следующего автомобиля. Начальные скорости автомобилен подчиняются равномерному случайному распределению на отрезке от 50 до 60 миль в час, а интервалы между порождениями также равномерно распределены на отрезке от 4 до 6 с. Минимальное допустимое сближение составляет одну длину автомобиля (10 футов) на каждые 10 миль в час скорости передней машины. Когда автомобиль приближается к идущей впереди машине на утроенное допустимое расстояние, он начинает притормаживать, пока скорости не сравняются, теряя по одной миле в час за секунду. Если передний автомобиль начинает резко замедляться, идущий сзади выжидает 0,2 с и затем тормозит, снижая каждую секунду свою скорость на 15 миль в час. В результате может произойти авария, которой и закончится эксперимент.

Собственно эксперимент состоит в заполнении дороги машинами, введении искусственного замедления и наблюдении результата. Начните запускать машины на пустую дорогу; продолжайте делать это, пока не пройдет 2 минуты (модельного времени) с момента прохождения заданного участка дороги первым автомобилем. Затем, не прекращая запускать машины, выберите автомобиль, который раньше всех пересечет отметку в 4 мили, сбросьте с его скорости как можно резче 0, 10, 20, 30, 40 или 50 миль в час, удержите на новой скорости 100 ярдов, после чего придайте ему ускорение 5 миль в час за секунду, пока автомобиль не наберет свою первоначальную скорость (машины всегда стремятся сохранить первоначальную скорость). Продолжайте эксперимент еще 5 минут после того, как виновник затора начал замедляться, и подсчитайте количество машин, прошедших участок дороги за это время. Полученная величина и есть наблюдаемый результат эксперимента. Машины, следующие за виновником, также могут ускоряться на 5 миль в час за секунду, если дорога перед ними освобождается. Проведите эксперимент несколько раз для каждого значения замедления. Если произойдет авария, все машины, находящиеся позади, автоматически остановятся и не смогут пройти заданный участок дороги. В аварию может попасть не сам виновник, а машины, идущие сзади.

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

Указания исполнителю. Наиболее трудным в предлагаемой задаче является отслеживание всех автомобилей на дороге[24]. Можно организовать цикл и примерно через одну сотую — одну десятую секунды модельного времени должным образом подправлять положение каждого автомобиля. Если интервал достаточно мал, заметного накопления ошибок не произойдет, а выглядеть программа будет красиво — как семейство вложенных циклов. Однако при использовании метода пошаговой фиксации цикл может выполняться слишком большое число раз. В нашем случае эксперимент продлится примерно 12 минут модельного времени, в каждый момент на дороге будет около 90 машин, и, даже если выбрать большой интервал в одну десятую секунды, потребуется примерно 1200 циклов, или около 650 000 операций с отдельными автомобилями. Если программа тратит много времени на продвижение одного автомобиля, эксперимент слишком затянется. Положение можно подправить, варьируя интервал в зависимости от дорожной обстановки.

Другой подход состоит в том, чтобы подправлять положение автомобилей только в моменты критических событий. При таком подходе заводится список всех событий, ожидаемых в недалеком будущем; например, запускается или исчезает автомобиль, одна машина догоняет другую, прошло две минуты с момента исчезновения первого автомобиля, пора вновь ускорять автомобиль-виновник. Головным элементом списка событий всегда должно быть ближайшее событие; список в целом не обязан быть упорядоченным — его можно представить и как очередь с приоритетами, и как кучу. В основном цикле от списка отделяется головной элемент, описывающий очередное событие, все автомобили устанавливаются в позиции, соответствующие новому времени, запоминаются все события, которые следует планировать, эти события вставляются в список и список переупорядочивается, чтобы ближайшее событие оказалось в голове. Достоинство моделирования методом критических событий в том, что порой довольно долго, 4–5 секунд, ничего не происходит. Сэкономленное время можно употребить на более сложную обработку списка событий.

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

Длительность исполнения. Одному исполнителю на 3 недели; еще неделя на изготовление фильма.

Развитие темы. Строго говоря, в предложенной задаче не изучается ситуация, описанная в нескольких первых абзацах. Вместо выяснения того, что происходит с ударной волной при различных средних скоростях движения на автостраде, в эксперименте рассматривались удары различной силы. Проделайте все еще раз, взяв диапазон начальных скоростей от 40 до 50 или от 60 до 70 миль в час. Попробуйте для некоторых переменных нормальное распределение вместо равномерного. Поварьируйте законы торможения и ускорения. Иными словами, изучите влияние всех параметров, а не только одного, выбранного нами.

Герман, Гардел (Herman R., Gardels К). Vehicular Traffic Flow. Scientific American, pp. 35–43, December 1963.

Авторы описывают проведение нескольких физических экспериментов над движением транспорта и развитие математической теории. Конечно, использовавшийся ими Голландский туннель в Нью-Йорке для большинства из нас недоступен Если вам интересно проследить за работами по этой тематике после 1963 г., научитесь пользоваться Science Citation Index или другими библиографическими средствами, помогающими довести старую информацию до наших дней.