Гасников А.В., Кленов С.Л., Нурминский Е.А., Холодов Я.А., Шамрай Н.Б. Введение в математическое моделирование транспортных потоков

Подождите немного. Документ загружается.

Учебное пособие посвящено математическому

моделированию транспортных потоков.

Излагается математический аппарат и некоторые

физические концепции, которые могут пригодиться

при создании (модернизации) комплексной

интеллектуальной транспортной системы.

9 7 8 5 7 4 1 7 0 3 3 4 2

I SBN 5- 7417- 0334- 8

Учебное издание

В В ЕДЕ Н И Е

В МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ

ТРАНСПОРТНЫХ ПОТОКОВ

Гасников Александр Владимирович

Кленов Сергей Львович

Нурминский Евгений Алексеевич

Холодов Ярослав Александрович

Шамрай Наталья Борисовна

П р и л о ж е н ия :

Бланк Михаил Львович

Гасникова Евгения Владимировна

Замятин Андрей Андреевич

Малышев Вадим Александрович

Колесников Александр Викторович

Райгородский Андрей Михайлович

Редакторы В. А. Дружинина, И. А. Волкова

Корректор О.П. Котова, Л.В. Себова

Подписано в печать 30.11.2010. Формат 60  84

Печать офсетная. Усл. печ л. 22,5. Уч.- изд. л. 22,0. Тираж 250 экз.

Заказ № ф-003.

Государственное образовательное учреждение

высшего профессионального образования

«Московский физико-технический институт (государственный университет)»

141700, Московская обл., г. Долгопрудный, Институтский пер., 9

__________________________________________________________________

Отдел автоматизированных издательских систем «ФИЗТЕХ-ПОЛИГРАФ»

141700, Московская обл., г. Долгопрудный, Институтский пер., 9

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

МОСКОВСКИЙ ФИЗИКО-ТЕХНИЧЕСКИЙ ИНСТИТУТ

(ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ)

Под редакцией А. В. Гасникова

Допущено

Учебно-методическим объединением

высших учебных заведений Российской Федерации

по образованию в области прикладных математики и физики

в качестве учебного пособия для студентов вузов

по направлению «Прикладные математика и физика»

МОСКВА

МФТИ

2010

УДК 519.1, 519.2, 519.6, 519.8(075)

ББК 22.1я73

В24

Рецензенты:

Лаборатория волновых процессов, механико-математического факультета

МГУ им. М.В. Ломоносова

(зав. лаб. проф. Н.Н. Смирнов – зам. декана мехмата МГУ)

к. ф.-м. н. В. И. Швецов (Институт системного анализа РАН)

Научный консультант академик А. А. Петров

А в т о р ы:

А.В. Гасников, С.Л. Кленов, Е.А. Нурминский, Я.А. Холодов, Н.Б. Шамрай;

Приложения: М.Л. Бланк, Е.В. Гасникова, А.А. Замятин, В.А. Малышев,

А.В. Колесников, А.М. Райгородский

Введение в математическое моделирование транспортных потоков:

учеб. пособие / Гасников А.В., Кленов С.Л., Нурминский Е.А., Холодов Я.А.,

Шамрай Н.Б; Приложения: Бланк М.Л., Гасникова Е.В., Замятин А.А., Малышев

В.А., Колесников А.В., Райгородский А.М; Под ред. А.В. Гасникова — М.:

МФТИ, 2010. — 360 с.

ISBN 978-5-7417-0334-2

Излагается математический аппарат и некоторые физические кон-

цепции, которые могут пригодиться при создании (модернизации)

комплексной интеллектуальной транспортной системы (КИТС).

Предназначено для студентов старших курсов и аспирантов физи-

ко-математических специальностей (МФТИ, МГУ, Независимого мос-

ковского университета). Рекомендуется научным работникам, интере-

сующимся вопросами математического моделирования.

ISBN 978-5-7417-0334-2 © Гасников А.В., Кленов С.Л., Нурминский Е.А.,

Холодов Я.А., Шамрай Н.Б.,

Приложения: Бланк М.Л., Гасникова Е.В.,

Замятин А.А., Малышев В.А., Колесников А.В.,

Райгородский А.М., 2010

высшего профессионального образования

«Московский физико-технический институт

(государственный университет)», 2010

Оглавление

Предисловие………………………………………………...4

Введение………………………………………..…………..11

Глава 1. Моделирование транспортных потоков

на основе теории равновесия………………………...….17

Глава 2. Математические модели транспортных

потоков……………………………………...……………...69

Глава 3. Теория Кернера трех фаз в транспортном

потоке – новый теоретический базис для

интеллектуальных транспортных технологий…..…..168

Приложение М. Л. Бланка. Процессы с запретами

в моделях транспортных потоков……………………..203

Приложение Е. В. Гасниковой. О возможной динамике

в модели расчета матрицы корреспонденций…….....225

Приложение А. А. Замятина, В. А. Малышева. Введение

в стохастические модели транспортных потоков…...247

Приложение А. В. Колесникова. Транспортная задача

и концентрация.…………………………..……………...288

Приложение А. М. Райгородского. Модели случайных

графов и их применения………………………………..300

Задачи………………………...…………………………...326

Используемые сокращения…………………….……....360

Предисловие

Идея написания этого пособия принадлежит декану факультета

управления и прикладной математики (ФУПМ) МФТИ проф. Александ-

ру Алексеевичу Шананину. Более двух лет назад он предложил начать

читать на Физтехе курс по выбору «Введение в математическое модели-

рование транспортных потоков», некоторые детали которого (глава 2) к

тому моменту уже обсуждались в течение нескольких лет на семинаре

«Квазилинейные уравнения и обратные задачи» в ВЦ РАН под его ру-

ководством.

Основная цель курса заключалась в том, чтобы познако-

мить заинтересованных студентов старшекурсников и аспирантов физи-

ко-математических специальностей с математикой, необходимой для

решения, например, таких задач:

 эволюция затора (как будет распространяться информация о заторе

по транспортному потоку),

 задача о светофоре (при каких условиях перед светофором не будет

скапливаться очередь),

 задача о выборе оптимальной топологии транспортной сети (где и

какую дорогу «лучше» строить),

 расчет матрицы корреспонденций и распределения потоков,

 задача о надежности графа транспортной сети.

Курс содержал дополнительные главы следующих дисциплин:

 уравнений математической физики (обобщенные решения законов

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

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

 теории вероятностей и случайных процессов (аппарат производящих

функций, системы массового обслуживания, концентрация меры, ис-

следование асимптотик с помощью метода перевала);

Здесь также хотелось бы обратить внимание на ту огромную роль, которую сыграл зав.

каф. вычислительной математики МФТИ чл.-корр. РАН А. С. Холодов во внедрении этой

тематики в образовательный процесс на Физтехе. За несколько лет до того, как был по-

ставлен упомянутый курс, Александр Сергеевич уже читал лекцию по гидродинамиче-

ским моделям транспортного потока в рамках своего семестрового курса для студентов

ФУПМ МФТИ «Нелинейные вычислительные процессы». Энтузиазм Александра Сергее-

вича «зажег» тогда многих (и не только студентов). Отметим также, что с 2005 года В. И.

Швецов ведѐт курс «Математические модели транспортных потоков» для студентов

ФУПМ МФТИ на базовой кафедре Института системного анализа РАН.

 функционального анализа (сжимающие отображения, монотонные

операторы, конусные методы);

 теории динамических систем (методы функционалов Ляпунова) и

эргодической теории (концентрация инвариантной меры, элементы

статистической физики);

 кинетической теории (уравнения Колмогорова, социодинамика, ди-

намика систем с мотивацией, самоорганизация);

 теории игр (эволюционные игры: равновесие Нэша как устойчивое

положение равновесия динамической системы локального «нащупы-

вания» наилучших ответов);

 оптимизации в конечномерных и бесконечномерных пространствах

(принцип Лагранжа, двойственность, отделимость, принцип Беллма-

на, элементы теории управления);

 дискретной математики (задачи на графах и эффективные (прибли-

женные, вероятностные) алгоритмы их решения);

 численных методов выпуклой оптимизации (полиномиальные алго-

ритмы внутренней точки Нестерова–Немировского, стохастические

квазиградиентные методы для задач огромной размерности).

Настоящее пособие представляет собой попытку связно преподнести

как материалы прочитанных курсов, так и в целом математический ап-

парат и некоторые «физические концепции», которые могут пригодить-

ся при создании (модернизации) комплексной интеллектуальной транс-

портной системы (КИТС). О важности такой системы в «борьбе с проб-

ками» (в Москве) было много сказано за последнее время.

По сути, речь идет о том, как оптимальным образом использовать

имеющуюся информацию. Например, в Москве сейчас установлено (в

основном на крупных перекрестках) в общей сложности более 500 ви-

деокамер. Порядка

10 10

автомобилей,

курсирующих по Москве и

области, оснащены GPS-навигаторами, что позволяет получать треки

(пути следования) автомобилей, с информацией о скоростях движения

вдоль этих треков. Заметим, что всего в Москве ежедневно бывает более

3 10

автомобилей.

Создание КИТС на основе имеющихся данных предполагает вы-

полнение следующих действий.

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

меньше.

 Выработку адекватной (имеющимся данным

) математической мо-

дели, описывающей транспортный поток. Например, можно в не-

плохом приближении уподоблять транспортный поток сжимаемой

жидкости с мотивацией и использовать гидродинамические модели

(или модели клеточных автоматов). Калибровка таких моделей на

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

довольно просто осуществляется исходя из исторической информа-

ции.

 Для постановки начально-краевых условий: описание характеристик

источников и стоков автомобилей, узлов графа транспортной сети

(перекрестки, въезды, съезды и т.п.) – также требуется работа с ис-

торическими данными. В результате такой работы получается мат-

рица корреспонденций, на основе этой матрицы рассчитываются

распределения потоков, а затем и матрицы перемешивания в узлах

графа транспортной сети. На наш взгляд, адекватная постановка на-

чально-краевых условий – это одна из самых сложных текущих за-

дач. И наметки приведенного здесь пути – далеко не единственный

способ получения краевых условий.

 Откалиброванная модель может использоваться для локального (по

времени) управления на основе текущей информации, например,

светофорной сигнализацией (въездами на крупные магистрали).

Возникающие здесь задачи связаны с управлением сложными (гиб-

ридными) динамическими системами в условиях неопределенности.

Такое локальное управление позволит несколько разгрузить склады-

вающуюся на дорогах в данный момент ситуацию (правильным об-

разом распределяя ресурсы транспортной сети между ее пользовате-

лями). Например, в Калифорнии коллектив, работающий в Беркли и

возглавляемый П. Варайя и А. Б. Куржанским, предложил несколько

лет назад способ локального управления въездами на основные ма-

гистрали. Это привело к тому, что в результате управления время в

пути среднестатистического водителя уменьшилось на 30%.

 Помимо задач локального управления имеются задачи долгосрочно-

го управления. Где и какую дорогу следует построить при заданных

бюджетных ограничениях? Каким образом (в каком размере) взи-

мать плату за проезд с трасс в центре Москвы?

На каких трассах

Важно подобрать модель, адекватную имеющимся данным, дабы «не забивать микро-

скопом гвозди».

Нужна некая «золотая середина», с одной стороны, плата за проезд должна разгрузить

эти трассы, с другой желательно, чтобы пропускные ресурсы трасс использовались по

максимуму.

стоит в первую очередь увеличивать число полос? Где стоит в пер-

вую очередь переделывать развязки – делать новые (в частности,

решать вопрос: а выгодно ли увеличивать степень непланарности

графа транспортной сети)? Эти задачи так же, как и задачи преды-

дущего пункта, должны решаться для всей сети в целом (не локально

по пространству!). Иначе говоря, сумматорные функционалы каче-

ства критериев должны в себя включать всех участников дорожного

движения. Понятно, что для решения этих задач достаточно про-

сматривать различные сценарии (в том числе предложенные руково-

дством города) с помощью выработанной и откалиброванной модели

на предмет их состоятельности. Путем (разумного) перебора выби-

рать лучшие предложения по разгрузке ситуации на дорогах.

Рис. 1. Транспортный затор на одной из улиц Москвы

Некоторые рассмотренные в пособии задачи имеют также и ком-

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

является задача маршрутизации: выбор оптимального (кратчайшего)

маршрута следования. Понятно, что если считать веса ребер графа

транспортной сети известными и не меняющимися со временем, то эта

задача довольно эффективно решается. Но на практике далеко не всегда

все нужные веса ребер бывают известными. В зависимости от времени

суток ситуация на дорогах может кардинально меняться, поэтому воз-

Решение которой может быть интересно, например, НИС ГЛОНАСС, ЗАО «Российские

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

дорогах, и компаниям, производящим КПК-навигаторы (с выходом в интернет) для авто-

мобилей.