Математический анализ модели транспортных потоков на автостраде и управления ее состоянием тема автореферата и диссертации по математике, 01.01.02 ВАК РФ

Московский государственный университет имени М. В. Ломоносова Факультет вычислительной математики и кибернетики

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

01.01.02 — дифференциальные уравнения, динамические системы и оптимальное управление

На правах рукописи

Дорогуш Елена Геннадьевна

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

13 НДР 2014

Москва

2014

005545929

005545929

Работа выполнена на кафедре системного анализа факультета вычислительной математики и кибернетики Московского государственного университета имени М. В. Ломоносова.

Научный руководитель — Куржанский Александр Борисович

доктор физико-математических наук, академик РАН, заведующий кафедрой системного анализа факультета ВМК МГУ имени М. В. Ломоносова.

Официальные оппоненты — Овсянников Дмитрий Александрович

доктор физико-математических наук, профессор, заведующий кафедрой теории систем управления электрофизической аппаратурой факультета прикладной математики — процессов управления Санкт-Петербургского государственного университета,

Гасников Александр Владимирович кандидат физико-математических наук, доцент, заместитель декана по младшим курсам факультета управления и прикладной математики Московского физико-технического института.

Ведущая организация — Институт математики и механики им. Н. Н. Красовского

Уральского отделения Российской академии наук.

Защита состоится _ 2014 года в 15:30 на заседании диссертацион-

ного совета Д 501.001.43 в Московском государственном университете имени М.В. Ломоносова по адресу: 119991, ГСП-1, Москва, Ленинские горы, МГУ имени М. В. Ломоносова, 2-й учебный корпус, факультет ВМК, ауд. 685.

С диссертацией можно ознакомиться в научной библиотеке Московского государственного университета имени М. В. Ломоносова по адресу: 119192, Москва, Ломоносовский проспект, д. 27.

Автореферат разослан Ц _2014 г.

Ученый секретарь диссертационного совета доктор физико-математических наук, профессор

Е. В. Захаров

Общая характеристика работы

Актуальность темы. Данная работа посвящена исследованию математических моделей транспортных потоков на автостраде и задаче управления состоянием автострады с платными полосами.

Можно выделить несколько подходов к математическому моделированию транспортных потоков. В микроскопических моделях задается закон движения каждого автомобиля, в зависимости от его текущего положения, скорости движения, характеристик движения соседних автомобилей и других факторов. Микроскопические модели, в свою очередь, можно разделить на непрерывные по пространству и по времени модели (например,.[9; 10; 21; 27]), и на дискретные по пространству и по времени модели, так называемые клеточные автоматы (например, [19]). В макроскопических моделях транспортный поток рассматривается как поток жидкости с особыми свойствами. Уравнения макроскопической модели устанавливают зависимость между потоком, плотностью, скоростью движения, возможно, ускорением и так далее. Макроскопические модели также могут быть непрерывными или дискретными. В непрерывных моделях изменение состояния участка дороги без ответвлений и перекрестков описывается, как правило, дифференциальными уравнениями в частных производных. Так, в статье [34] исследуется модель транспортного потока, при некоторых значениях параметров имеющая вид системы уравнений в частных производных второго порядка. В книге [24] дается обзор существующих макроскопических моделей транспортных потоков на дороге без перекрестков и строится макроскопическая модель транспортных потоков в сети. Как показано в статьях [9; 10; 21] и в книге [29], некоторые макроскопические модели являются, в некотором смысле, следствиями микроскопических моделей. Также можно изучать транспортные потоки с точки зрения теории экономического равновесия. При этом решается задача поиска равновесного распределения потоков в сети исходя из равенства времени в

пути на используемых маршрутах (например, [4; 20; 23]). В книге [29] дается обзор детерминированных и стохастических моделей из каждой категории.

Настоящая работа посвящена изучению дискретной макроскопической модели потоков в транспортной сети. Эта модель довольно легко калибруется по измерениям, как это описано в работах [3; 33]. Кроме того, дискретная модель удобна для компьютерных симуляций.

Изучаемая в работе дискретная модель транспортных потоков основана на непрерывной гидродинамической модели [17; 18; 25]. В гидродинамической модели изменение состояния участка дороги без ответвлений и перекрестков подчиняется закону сохранения числа автомобилей dp/dt + df /дх = 0. Здесь р = p(t, х) — плотность потока в точке х в момент t, то есть число автомобилей на единицу длины, / = f(t, х) — поток в точке х в момент t, то есть число автомобилей, проезжающих через заданное сечение дороги х в единицу времени. Также предполагается, что существует функциональная зависимость между потоком / и плотностью р: / = /(р). График функции f(p) называется фундаментальной диаграммой. По-видимому, впервые о существовании фундаментальной диаграммы заявлено в статье [11]. В гидродинамике функция f(p) выпуклая, в моделировании транспортных потоков функция f(p) обычно считается вогнутой. Таким образом, изменение состояния автомагистрали описывается квазилинейным уравнением в частных производных относительно p(t, х)

д-Р + д-Ш = 0. (1)

at дх w

В отличие от линейных уравнений в частных производных первого порядка, уравнение (1) может иметь разрывные решения даже при гладких начальных данных. Возможна и такая ситуация, что классическое решение задачи Ко-ши для этого уравнения существует лишь до определенного момента времени. Поэтому рассматривается слабое решение уравнения (1) (см., к примеру, [16; 24]). Проблема в том, что слабое решение не единственно, и для нахожде-

ния единственного физически осмысленного решения нужны дополнительные условия, а именно энтропийные условия [15; 16; 30; 35].

Для расчетов гидродинамической модели можно применить численную схему, предложенную в статье [31]. Для устойчивости этой численной схемы и сходимости разностных решений к слабому решению исходного уравнения должно выполняться условие Куранта — Фридрихса — Леви [32].

В статье [6] была предложена дискретная динамическая модель автомагистрали СТМ (the cell transmission model, клеточная передаточная модель). Модель СТМ совпадает с представленным методом численного решения задачи Коши для уравнения (1) с фундаментальной диаграммой в форме трапеции f(p) = min{up, /шах, vu(pmB*-p)}. В статье [7] дискретная модель была расширена на слияния и разветвления дорог.

Другой важный компонент любой модели транспортных потоков в сети — модель узла сети, то есть правило вычисления потоков в узле по состоянию прилегающих ребер. Различные модели узла предлагались в работах [1; 7; 13; 22; 24].

Необходимость платных дорог в условиях перегрузки транспортной сети, как отмечено в статье [2], подчеркивается экономистами уже довольно давно. Дело в том, что в условиях перегрузки каждый дополнительный участник дорожного движения увеличивает задержки в пути для других участников дорожного движения. Такая ситуация обуславливает неоптимальное поведение всех участников дорожного движения в целом. Оптимальное в смысле суммарных затрат всех участников поведение стимулируется, как указано в обзоре [8], так называемым налогом А. С. Пигу: каждый участник дорожного движения платит за свой проезд по каждому ребру транспортной сети сумму, эквивалентную увеличению суммарных задержек всех остальных участников дорожного движения в результате его поездки. Такой подход не учитывает, однако, некоторые моменты. Во-первых, цена времени для разных водителей может различаться, и при этом не ясно, как определять плату

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

В зависимости от выбранной модели транспортной сети модели и алгоритмы вычисления платы за проезд могут быть разными. Так, в работе [12] разрабатывается теория платных дорог в рамках модели экономического равновесия. Стоимость времени для всех агентов считается одинаковой, плата за проезд по каждому ребру устанавливается такая, чтобы любое равновесное по Нэшу — Вардропу распределение в системе с платными ребрами было в то же время оптимальным (в смысле системного оптимума, то есть минимизации суммарного времени в пути) в системе без платы за проезд по ребрам. В статье [26] используется динамическая модель транспортной сети, и предлагается устанавливать стоимость проезда по платным ребрам сети и выделенным полосам автомагистрали динамически, в зависимости от текущих и желаемых условий (точнее, плотностей). В статье [28] рассматривается динамическая модель автомагистрали, близкая к модели, исследуемой в данной работе, и предлагается следующий способ управления состоянием автострады. При слишком большом входном потоке ограничиваются потоки со въездов. При этом, конечно, образуются очереди перед въездами. В то же время, есть возможность въехать на автомагистраль, минуя очередь перед въездом, но за плату, которая зависит от въезда, и от того, через какой съезд водитель покинет автомагистраль.

В работе [8] дан обзор существующих методов и технологий платных дорог и платных полос.

Цель работы. Целью данной работы является изучение свойств математической модели автострады, в том числе кольцевой автострады, и разработка алгоритма управления состоянием незамкнутой автострады с выделенными платными полосами путем изменения стоимости въезда в платные полосы.

Научная новизна. Полученные результаты являются новыми. Исследование равновесных состояний в математической модели автомагистрали обобщает результаты работ [5; 14] на случай произвольных коэффициентов приоритета в модели незамкнутой автострады и на модель кольцевой автострады.

Теоретическая и практическая ценность. Работа носит в основном теоретический характер. Исследование множеств положений равновесия — первый шаг к пониманию законов развития динамической системы, описывающей изменение состояния автострады. Результаты, касающиеся управления состоянием автострады с помощью платы за въезд на выделенные полосы, могут быть применены на практике, если будут реализованы бесконтактные высокоскоростные системы оплаты въезда в платные полосы.

Методы исследования. Для выяснения структуры множества равновесий используются факты и приемы из работ [5; 14]. Вопрос об устойчивости произвольного равновесия сводится к исследованию устойчивости двух линейных динамических систем, в некоторых случаях применяется теорема Фробениуса — Перрона. При обосновании алгоритма управления состоянием автострады с помощью платных полос неоднократно используется монотонность динамической системы, описывающей изменение состояния автострады.

Апробация работы. Результаты работы докладывались на научном семинаре «Прикладные задачи системного анализа» под руководством академика А. Б. Куржанского на кафедре системного анализа ВМК МГУ, на конференции «Ломоносов-2011» (Москва, 2011), на семинаре «Современные тенденции в теории управления динамическими системами» (Киев, октябрь 2012), на конференции «Динамические системы: устойчивость, управление, оптимизация» (Минск, октябрь 2013), на VII Московской международной кон-

7

ференции по исследованию операций (ОИМ 2013) (Москва, октябрь 2013), на конференции «Тихоновские чтения» (Москва, октябрь 2013) и на семинаре «Математическое моделирование транспортных потоков» под руководством А. В. Гасникова и Ю. Е. Нестерова в Независимом Московском университете.

Публикации. Результаты диссертации опубликованы в 3 работах, список которых приведен в конце автореферата. Из них 2 работы [36; 37] опубликованы в журналах из перечня ВАК.

Идея исследований принадлежит научному руководителю автора, академику А. Б. Куржанскому. Автором получены доказательства теорем и подготовлены к публикации результаты исследований.

Структура и объем диссертации. Диссертация состоит из введения, трех глав, заключения и списка литературы, включающего 49 наименований. Общий объем диссертации составляет 90 страниц.

Содержание работы

Во введении раскрывается актуальность работы, изложены цели работы и основные результаты.

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

В § 1.1 излагается динамическая модель транспортных потоков в сети. Транспортная сеть представлена ориентированным графом С = (V, Е), где V — множество вершин или узлов графа, Е — множество ребер графа (которые также будем называть соединениями), то есть упорядоченных пар

8

вершин е = (и, v), u,v е Ребра графа соответствуют участкам дорог без пересечений с другими дорогами, без примыкания других дорог и без ответвлений. Вершины графа соответствуют перекресткам, местам слияния и разветвления дорог и разбивают длинные ребра на более короткие. Выделяются вершины без входящих ребер — источники, и вершины без исходящих ребер — стоки. Ребра, инцидентные источникам, называются въездами, а ребра, инцидентные стокам — съездами или выездами.

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

Каждое ребро е характеризуется своей пропускной способностью Fe, то есть максимальным числом автомобилей, въезжающих в это ребро или выезжающих из него, за один шаг по времени; максимальным числом автомобилей на нем Ne, скоростью свободного движения, то есть максимальной разрешенной скоростью ve и скоростью распространения затора we. Пропускные способности ребер нормализованы относительно шага по времени, а скорости свободного движения и роста затора нормализованы относительно длины ребра и шага по времени.

Состояние системы на шаге t есть число автомобилей на каждом ребре ne{t) (это число не обязательно целое), 0 < ne{t) < Ne. Для входных ребер, то есть для въездов, величины Ne и uie не определены, и на этих ребрах могут скапливаться очереди неограниченной длины, то есть, единственное ограничение на ne(t) для входных ребер — неотрицательность.

Суммарный входящий поток на шаге t для любого ребра, кроме въездов, ограничен величиной fse{t) = min{Fe,we{Ne-ne(t))}. Суммарный исходящий поток для любого ребра ограничен величиной ff{t) — min{Fe, vene(t)}, причем для съездов исходящий поток на шаге t в точности равен /ed(i).

Для внутренних вершин, то есть вершин, не являющихся источниками или стоками, потоки fij(t) из каждого входящего ребра i в каждое исходящее ребро j определяется правилом, называемым моделью узла. Модель узла, ис-

пользуемая в диссертации, изложена в п. 1.1.1. Ясно, что, зная лишь максимальные исходящие потоки /¡(Ь) для входящих ребер i и максимальные входящие потоки /■" для исходящих ребер однозначно определить потоки /¿ ¡(¿) в нетривиальных случаях невозможно. Поэтому в используемой нами модели узла для каждой вершины определяются дополнительные параметры. Во-первых, задана матрица коэффициентов расщепления Вь(р) = где т — число входящих ребер вершины V, п — число исходящих ребер вершины v. Все элементы матрицы неотрицательны, Р^Ц) = 1 для всех г, и потоки должны быть пропорциональны коэффициентам расщепления /¿л (*)//%(£) = /у2(*)/Ая (*) Для всех г. Кроме того, для всех входящих ребер заданы неотрицательные коэффициенты приоритета р*, которые влияют на величины потоков /¡¿(¿), только если максимальные входящие потоки для исходящих ребер невелики, а именно, если хотя бы для одного з выполнено неравенство АК*)/»^) > Используемая в диссертации модель узла взята из работы [1] и расширена на случай не только строго положительных, но и, с некоторыми оговорками, неотрицательных коэффициентов приоритета.

В § 1.2 представлены модели незамкнутой и кольцевой автострады. Автомагистраль состоит из К основных последовательно соединенных ячеек, в каждом узле может быть въезд и съезд. Через щ(£) мы обозначаем число автомобилей в г-й основной ячейке на шаге t, <?{(£) обозначает число автомобилей перед въездом в г-ю основную ячейку на шаге £. А^ — максимальное число автомобилей в г-й основной ячейке. Съезды в начальный момент считаются свободными. Показано, что при таком предположении максимальный входящий поток для каждого съезда всегда равен пропускной способности съезда, поэтому состояние съездов можно не рассматривать. Р{ есть пропускная способность г-й основной ячейки, Щ — пропускная способность въезда перед г-й основной ячейкой, — пропускная способность съезда в конце г-й основной ячейки. Для основных ячеек и въездов заданы скорости свободного движе-

ния V{ и г>[, только для основных ячеек заданы скорости роста затора Все величины нормированы относительно длин ячеек и шага по времени. Для основных ячеек заданы коэффициенты расщепления потоков в следующую основную ячейку /?/ и на съезд /3?, /3{ + /?? = 1. Если съезда в конце г-й основной ячейки нет, то = 0. Предполагается, что для всех основных ячеек г выполнено неравенство

Vi Wi

Для въездов и основных ячеек автострады на каждом шаге t определяются максимальные исходящие потоки rf(t) = min{vlq^t), Ri}, ff{t) = = min{¡3{vini(t),Ff}, где

Ff=h

{^min {Ft,Si№,

Для основных ячеек также определяются максимальные входящие потоки ff(t) = min{Fj, Wi{Ni-ni{t))}. Кроме того, в каждом узле определены коэффициенты приоритета р\ для потока со въезда и для потока из предыдущей основной ячейки. Без ограничения общности можно считать, что коэффициенты приоритета нормированы: р\+р{_\ = 1- Потоки с г-го въезда в г-ю основную ячейку r,(i) и из (г - 1)-й основной ячейки в г-ю /¿-i(t) определяются по следующему правилу, являющемуся частным случаем общей модели узла.

1. Если ff_.it) +rf(t) < f?{t), то /(_i(t) = fU{t), n{t) = rf(i).

2. В противном случае учитываются коэффициенты приоритета.

(a) Если fUt) < pLJ№. то fi-i(t) = fU(t)> nit) = f№ - fUt).

(b) Если rf(t) < Pifi(t), то n(t) = rf(t), /i-i(i) = f!(t) - rf(t).

(c) Иначе f^t) = p{_Jf{t), r<(t) =

Число автомобилей в основных ячейках и на въездах изменяется по следующим законам:

m(t +1) = m(t) + /,_i(i) + ф) - №/0{, ф +1) = ®(t) + di(t) - n(t).

Входной поток di(t) задан.

В модели незамкнутой автострады появляются еще две ячейки: нулевая, являющаяся въездом, для нее задан входной поток f-i(t), и (К + 1)-я, являющаяся съездом. В модели кольцевой автострады последняя, К-я ячейка, соединена с первой.

В § 1.3 предлагаются определения и способы вычисления пропускной способности и уровня загруженности автострады.

В п. 1.3.1 вводится понятие контролируемого уровня концентраций, используемое в дальнейшем.

В п. 1.3.2 речь идет о пропускной способности автострады. Задача о пропускной способности возникает в результате решения задачи о минимизации функционала общего времени в пути

эк 0 К+1

Пт, *) = £!>(*)+£!>(*).

t~T г—1 t=T i=О

в модели незамкнутой автострады, и

t=T i= 1

в модели кольцевой автострады, за счет ограничения потоков со въездов г и /о. Пусть входные потоки d и /_i постоянны. Обозначим f; = min{<i;, Щ], /о = min{/_i,Fo}. Задачи о пропускной способности имеют следующий вид:

12

в модели незамкнутой автострады

' 0 < Д <

о < Л//?/ - /¿-1 < й,

О < /о < /о,

* в3 . 1=1 "г

в модели кольцевой автострады

О < /г < #

г = 1,...,К + 1, i = l,...iK + l,

О < fi/P{ - fi—i <

к

or .

шах.

г = 1, • ■

.К,

(3)

. г—1 Pi

Пропускной способностью автострады называется решение задач (2) или (3) при больших входных потоках, а именно ^ > Щ, /-1 > Еа.

В модели незамкнутой автострады задача (2) и, в частности, задача о пропускной способности автострады решается явно. Сначала определяются максимальные потоки /;. Максимальные входные потоки г и /0 уже определены; /, = тт {/?/ (Л_1 1 = После этого определяются максимальные равновесные потоки /*: /¿+1 = /к+ъ /*-1 = шМ/г*//1-1}-Пропускная способность незамкнутой автострады есть

¡=1 "г

В модели кольцевой автострады вычисляются величины

"н-к

1

'¡+1

, ■ • • . П о/

Здесь и далее, если речь идет о модели кольцевой автострады, индексы г, j, такие, что г = j (mod К), соответствуют одной и той же ячейке. Вводятся функции /,(■): /„(/*) = /к, Шк) = min{l3((fUfK) F?}. г = 1, • • -, К.

13

Утверждение. Если /к(^к-) > то вектор f*(Fявляется решением задачи (3).

Утверждение. Если Jk{Fk) < 7710 т отрезке [О, существует единственный корень fy уравнения /к(/к) — fк, и максимум в задаче (3) достигается на векторе f*(fic)-

В п. 1.3.3 предлагается определение уровня загруженности автострады. Для этого выбирается некоторый контролируемый уровень концентраций п*, например, соответствующий решению задачи о пропускной способности. Уровнем загруженности автострады предлагается считать наименьшее число шагов по времени, необходимое для приведения вектора плотностей п системы во множество п < п* за счет ограничения потоков со въездов г (rf(t) = min{vlqi(t),Ri,Ui(t)}), а также /0, в модели незамкнутой автострады (/о (i) = mm{vono(t),Fo,uo{t)}). Таким образом,

c(i) = c(n(i)) = min min{Ai > 0: n(t + At) < n*}.

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

В главе 2 описывается множество равновесий в модели незамкнутой и кольцевой автострады при постоянных входных потоках d, а также /_ь в модели незамкнутой автострады, и исследуется устойчивость всех положений равновесия.

Под равновесием понимается такое состояние системы, в котором не меняются число автомобилей в каждой основной ячейке щ и все потоки со въездов и между ячейками /, г. При этом, в равновесии число автомобилей перед въездом $ либо не изменяется, если п = сЦ, либо растет с постоянной скоростью di — г,-, если di> г¿.

В § 2.1 показано, что потоки между основными ячейками / зависят от потоков со въездов линейно, / = /(г) в модели кольцевой автострады,

f = /(/о, г) в модели незамкнутой автострады, и получены явные формулы для этих зависимостей. Вводятся понятие допустимого, строго допустимого и недопустимого входного потока. Входной поток называется допустимым, если (1) в модели кольцевой автострады: для всех i = 1,... ,К, справедливо неравенство /¡(f) < F?, (2) в модели незамкнутой автострады: для всех г = 1,..., К+1, справедливо неравенство /¡(/0, f) < F?. Здесь, как и прежде, /о = min{/_i, F0}, fj = min{dj, Л,}. Входной поток является строго допустимым, если для всех г указанные неравенства выполнены строго.

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

В § 2.3—§ 2.4 исследуется структура множеств всех равновесных потоков и концентраций.

Теорема. В модели незамкнутой автострады равновесные потоки fur единственны и определяются по следующему правилу.

Вычисляются максимальные потоки между ячейками fi, г = 1,..., К, а также максимальный исходящий поток из последней ячейки 1-

fi = min {¿/(/w + fj), Ft), i = 1, • • •, К + 1.

Равновесный исходящий поток из (К + 1)-й ячейки равен максимальному своему значению: fK+1 = Ik+i- Пусть уже определено равновесное значение потока fi для некоторого г € {1,.. ■, К +1}. Тогда потоки /,_ь гг определяются по следующему правилу.

1. Если fi-1 < Pi-ifi/Pi, то fi-x - fi-ь п = fi/P{ - fi-1-

2. Если й < fifi/P(, mo r{ ~ n, /¿_i = fi/p{ - fi-

3. Если же fi-1 > p{-Ji/P{ un> prifi/p{, mo fi-1 = p{-ifi/p{, П = Pifi/Pi-

При этом, если входной поток является допустимым, то г = г, /о = /о, / = /(/о,г).

Обозначим п? = п*(/,г) =.МР{ъ), п\ = п?(/,г) = ЛГ< - (г, + /¿-ОМ, введем множества индексов ^ и С: ^ = {г: /¿/р[ < гш/р{+1, ./• < С = {г: г, < т^, /¡_1 + ^ < в модели кольцевой автострады, а в модели незамкнутой автострады

С = {»: г,- < й, /¿-1 + г< < Р?) и {1, если /о < /о, /о + П <

Для индексов г е Ы в положении равновесия выполнено равенство щ — п^, а для г € С выполнено равенство щ = гг-.

Рассматривается множество «узких» участков

г = {г < К: /г = ^ или /; + Г;+1 = ^.ц}.

Пусть I = {¿1,... ,гм}, где М — число элементов множества 1, индексы ¿1,... ,гм упорядочены по возрастанию. Рассмотрим множества участков между соседними узкими участками Зт = {?: 1 < г ^ гт }, где в модели незамкнутой автострады ¿о = 0, 5м+1 = {ш + !,..•, К + 1}, а в модели кольцевой автострады й = {гм + 1. • • •. К, 1,..., ¿1}. Вычислим индексы

¿¿П5т = 0,

г™ =

тах(УП5т),

гт + 1, СП<?т = 0,

тт(СП5т), СП<5т^0.

Для равновесных векторов п компоненты с индексами из разных множеств 5т определяются независимо.

Множество равновесных векторов п, соответствующих заданным потокам /, г будем обозначать как £ = £(/,г).

Теорема. В модели незамкнутой автострады множество £(/, г) предста-вимо в виде декартова произведения £ = <2)^=1 где множество £м+1 состоит из единственного вектора, £м+1 = {{п1м< ■■■ >пк)}' а остальные

16

множества £т, т = 1,..., М, состоят из единственного вектора,

£т = (^„-1+1' • • •' п*к>'''' п*т)>

если 1ст - г^ = 1, или, если гст - г^ > 1, представляются в виде объединения

£т~ £т>

где

£т = {(»Чп-1+1» ■ • ■»»4») = г< к п1<пк< п\, щ = п?, г > /г}.

В модели кольцевой автострады равновесные потоки не единственны. Множество равновесных потоков можно условно разделить на две части. В первой части выполнено хотя бы одно из условий (1) г = г, или (2) /, = ^ для некоторого г. Для первой части множество £ равновесных п определяется следующим образом.

Теорема. Множество £ в модели кольцевой автострады имеет следующий вид.

Опишем сначала случай 1=0. Здесь £ = {пи}, если Ы ф 0, £ = {пс}, если Сф0, и£ = пи, пс, если К = С = 0.

Если же X Ф 0, то £ = £т, множества £т, как и в модели

незамкнутой автострады, состоят из единственного вектора,

или же представимы в виде

с — I I

— т'

Л=г»+1

где, как и в модели незамкнутой автострады,

£Нш = {«._,+!.• ' * • ■ • • ' П

17

Во второй части множества равновесий модели кольцевой автострады для всех равновесных потоков п = nc(f,r). Второй части, в частности, принадлежит равновесие / = 0, г = 0, п = N. Принадлежат ли второй части множества равновесий еще какие-либо точки, зависит от величины

t=l Pi i: fj>0

Так, если 7 > 1, то, кроме нулевых потоков и максимальной плотности, других равновесий во второй части нет. Если 7 < 1, то вторая часть может содержать еще одну точку. Если же 7 = 1, то вторая часть множества равновесий содержит целый отрезок или полуинтервал равновесных потоков и соответствующих им концентраций пс. Точка / = 0, г = 0 является концом этого отрезка или полуинтервала.

В § 2.5 исследуется устойчивость всех положений равновесия. Поскольку длина очереди не входит в определение равновесия и может меняться, дополнительно требуется, чтобы в начальный момент времени выполнялось равенство rf(0) = fj.

Теорема. В модели незамкнутой автострады все равновесия устойчивы.

Для любого положения равновесия пе вектор n(t + 1) зависит от n(t)

линейно в областях {п > пе} П {||п - пе|| < е}, {п < пе} П {||п - пе|| < е} для

некоторого малого £ > 0. Точнее, n(t + 1) - пе = A+(n(t) - пе), если п > пе,

[|n - neII < £, и n{t + 1) - Пе = A'(n(t) - пе), если п < пе, ||га - пе\\ < е, где

А~, А+ — матрицы с неотрицательными компонентами.

Все элементы матриц А± для произвольного равновесия выписаны явно.

Для матрицы А £ RKxK определим функционал

к к ^

7(Л) = Па;,г-+1хЦ-. ¡=1 ¿=1 1

Напомним, что иц — скорость роста затора в ячейке г.

18

Теорема. В модели кольцевой автострады положение равновесия пе является неустойчивым, если и только если одно из чисел 7(А~), 7(А+) строго больше единицы. Положение равновесия пе является асимптотически устойчивым, если 7(Л±) < 1 и все элементы главных диагоналей матриц А± строго меньше единицы.

В частности, для равновесия / = 0, г = 0, п = N неравенство 7 < 1 является критерием устойчивости, а неравенство 7 < 1 — критерием асимптотической устойчивости.

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

Математическая модель автострады с выделенными полосами, представленная в § 3.1, получается из модели незамкнутой автострады путем разделения каждой основной ячейки автострады на две: первая ячейка содержит все платные полосы исходной ячейки, вторая — бесплатные полосы. В каждом узле, таким образом, может быть до трех входящих соединений (две основные ячейки выше по течению и въезд) и до трех исходящих соединений (две основные ячейки ниже по течению и съезд). Величины, относящиеся к платным полосам, обозначаются верхним индексом 1, а величины, относящиеся к бесплатным полосам — верхним индексом 2.

Стоимость въезда в платные полосы влияет на коэффициенты расщепления потоков со въездов. Изменяя стоимость въезда в платные полосы, алгоритм стремится поддерживать платные полосы в состоянии свободного движения, используя при этом пропускную способность платных полос полностью. Условие максимального использования пропускной способности

платных полос важно потому, что без него могут быстрее расти очереди на въездах, и даже водители, готовые заплатить за въезд в платные полосы, вынуждены ждать своей очереди перед въездом на автостраду.

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

В п. 3.2.2 разбираются два условия, обеспечивающих максимальное использования пропускной способности платных полос: условие миимизации скорости роста очереди перед въездом (t) —> max и условие максимизации входящего потока для основных ячеек автострады ^/_i(//_i(i) + fi-i(t)) + + r,(i) min.

В п. 3.2.3 строится координированное управление коэффициентами расщепления потоков со въездов. Для этого вычисляется максимальный контролируемый уровень концентраций (определен в главе 1) и соответствующие ему потоки f1-*: = //•* = min{F/'d, /ft/^J, i — K,...,\. Далее определяются максимальные равновесные потоки для платных полос /1,е, как если бы пропускные способности существующих въездов были достаточно большими. Поясним это. Пусть ii < г2 < • • ■ < гм ~ индексы участков, перед которыми есть въезды. Обозначим 1м+\ = К + 2. Максимальные равновесные потоки для выделенных полос /1,е определяются следующим образом: = = ß(ft\, г = im + 1.....Wi - 1. Предлагаемый

алгоритм управления стремится поддерживать суммарное число автомобилей между соседними въездами на уровне, не превышающем 1 ni гДе пЬе = f}'e/{ß(vi). Кроме того, алгоритм стремится обеспечить, чтобы суммарный входящий поток для ячеек со въездом не превосходил максимального равновесного потока. Если где-то возникает затор на платных полосах, целевые уровни суммарного числа автомобилей между въездами для участков вверх по течению могут быть уменьшены.

В § 3.3 приводится обоснование предложенного алгоритма. Доказываются следующие утверждения. Речь идет только о платных полосах, поэтому

верние индексы 1 опущены.

Теорема. Пусть п<пе и для всех ячеек со въездами гт, т = 1,..., М, выполнено неравенство < - Тогда п(1 + ^

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

»'т+1-1

Е ^ Е <

для каждой пары соседних въездов (гт,гт+1)> и

л__!(*)+< дЛ. ш * /и-1

для каждой ячейки со въездом гт.

Тогда для любого е > О найдется момент времени Т = Т(е), начиная с которого будут выполняться неравенства гц(Т + Д£) < п\ + е для всех г и для всех Д4 = 0,1,2где п\ = /*/(/?/ В условиях этой теоремы неравенство

tm.fl-1 »т+1-1

Е *(«) ^ Е <

можно заменить на условие

¡т+1-1 'ст+1-1

Итвир Е - Е

г->+оо гг • •

г=1т г—

В заключении кратко сформулированы основные результаты, полученные в диссертации.

Основные результаты работы

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

2. Описано множество положений равновесия в моделях незамкнутой и кольцевой автострады. Доказано, что в модели незамкнутой автострады все равновесия являются устойчивыми. Получен критерий устойчивости равновесий в модели кольцевой автострады.

3. Предложен алгоритм управления состоянием незамкнутой автострады с помощью выделенных платных полос. Цель управления — поддерживать выделенные полосы в состоянии свободного движения, при условии максимального использования их пропускной способности.

Автор благодарит своего научного руководителя академика Александра Борисовича Куржанского за постановку задачи и постоянное внимание к работе, Александра Александровича Куржанского (PhD) за плодотворные обсуждения, доцента А. В. Гасникова за ценные замечания и В. Д. Ширяева за помощь в вычитке диссертации и автореферата.

Работа выполнена при финансовой поддержке РФФИ (гранты 12-01-00261-а и 13-01-90419-Укр_ф_а) и программы «Государственная поддержка ведущих научных школ» (грант НШ-2239.2012.1).

Список ЛИТЕРАТУРЫ

1. A generic class of first order node models for dynamic macroscopic simulation of traffic flows / С. M. Татрёге [et al.] // Transportation Research Part B: Methodological. — 2011. — Vol. 45, no. 1. — Pp. 289-309.

2. Arnott R., Small K. The Economics Of Traffic Congestion // American Scientist. — 1994. — Vol. 82, no. 5. — Pp. 446-455.

3. Automatic Calibration of the Fundamental Diagram and Empirical Observations on Capacity / G. Dervisoglu [et al.] // 8th Annual Transportation Research Board Meeting. — 2009.

4. Beckmann M., McGuire С. В., Winsten С. B. Studies in the economics of transportation. — Yale University Press, 1956.

5. Behavior of the cell transmission model and effectiveness of ramp metering / G. Gomes [et al.] // Transportation Research Part C: Emerging Technologies. — 2008. — Vol. 16, no. 4. — Pp. 485-513.

6. Daganzo C. F. The cell transmission model: a dynamic representation of highway traffic consistent with the hydrodynamic theory // Transportation Research Part B: Methodological. — 1994. — Vol. 28, no. 4. — Pp. 269-287.

7. Daganzo C. F. The cell transmission model, part II: Network traffic // Transportation Research Part B: Methodological. — 1995. — Vol. 29, no. 2. — Pp. 79-93.

8. de Palma A., Lindsey R. Traffic congestion pricing methodologies and technologies // Transportation Research Part C: Emerging Technologies. — 2011. — Vol. 19, no. 6. — Pp. 1377-1399.

9. Gazis D. C., Herman R., Potts R. B. Car-Following Theory of Steady-State Traffic Flow // Operations Research. — 1959. — Vol. 7, issue 4. — Pp. 499-505.

10. Gazis D. C., Herman R., Rothery R. W. Nonlinear FolIow-the-Leader. Models of Traffic Flow // Operations Research. — 1961. — Vol. 9, issue 4. — Pp. 545-567.

11. Greenshields B. D. A study of traffic capacity // Proceedings of the Fourteenth Annual Meeting of the Highway Research Board. Vol. 14. — 1935. — Pp. 448-477. — (Highway Research Board Proceedings).

12. Hearn D. W., Ramana M. V. Solving congestion toll pricing models // Equilibrium and Advanced Transportation Modeling / ed. by P. Marcotte, S. Nguyen. —1998. — Pp. 109124.

13. Jin W. L., Zhang H. M. On the distribution schemes for determining flows through a merge // Transportation Research Part B: Methodological. — 2003. — No. 6. — Pp. 521— 540.

14. Kurzhanskiy A. A. Modeling and Software Tools for fYeeway Operational Planning: Ph.D. thesis / Kurzhanskiy Alex A. — EECS Department, University of California, Berkeley, 2007.

15. Lax P. D. Hyperbolic Systems of Conservation Laws and the Mathematical Theory of Shock Waves. — Society for Industrial and Applied Mathematics, 1973.

16. LeVeque R. J. Numerical Methods for Conservation Laws. — Birkhauser, 1992.

IT. Lighthill M. J., Whitham G. B. On Kinematic Waves. I. Flood Movement in Long Rivers // Proceedings of the Royal Society of London. Series A, Mathematical and Physical Sciences. — 1955. — Vol. 229, no. 1178. — Pp. 281-316.

18. Lighthill M. J., Whitham G. B. On Kinematic Waves. II. A Theory of Traffic Flow on Long Crowded Roads // Proceedings of the Royal Society of London. Series A, Mathematical and Physical Sciences. — 1955. — Vol. 229, no. 1178. — Pp. 317-345.

19. Nagel K., Schreckenberg M. A cellular automaton model for freeway traffic // Journal de Physique I. — 1992. — Vol. 2, no. 12. — Pp. 2221-2229.

20. Nesterov Y., de Palma A. Stationary dynamic solutions in congested transportation networks: summary and perspectives // Networks and Spatial Economics. — 2003. — Vol. 3, no. 3. — Pp. 371-395.

21. Newell G. F. Nonlinear effects in the dynamics of car following // Operations Research. — 1961. — Vol. 9, no. 2. — Pp. 209-229.

22. Ni D., Leonard J. D. A simplified kinematic wave model at a merge bottleneck // Applied Mathematical Modelling. — 2005. - Vol. 29, no. 11. - Pp. 1054 -1072. - ISSN 0307-904X.

23. Ortuzar J. de Dios, Willumsen L. G. Modelling Transport. — 4th. — John Wiley & Sons, 2011.

24. Piccoli B., Garavello M. Traffic Flow on Networks. — American Institute of Mathematical Sciences, 2006. — (AIMS Series on Applied Mathematics).

25. Richards P. I. Shock waves on the highway // Operations Research. — 1956. — Vol. 4, no. 1. — Pp. 42-51.

26. State-dependent pricing for real-time freeway management: Anticipatory versus reactive strategies / J. Dong [et al.j // Transportation Research Part C: Emerging Technologies. — 2011. — Vol. 19. — Pp. 644-657.

27. Treiber M., Hennecke A., Helbing D. Congested traffic states in empirical observations and microscopic simulations // Physical Review E. — 2000. — Vol. 62, issue 2. — Pp. 1805-1824.

28. Varaiya P. Congestion, ramp metering and tolls // Philosophical transactions of the royal society A. — 2008. — Vol. 366. — Pp. 1921-1930.

29. Введение в математическое моделирование трапспортных потоков / А. В. Гасников [и др.] ; под ред. А. В. Гасникова. — М.: Изд-во МЦНМО, 2013.

30. Гельфанд И. М. Некоторые задачи теории квазилинейных уравнений // Успехи математических наук. — 1959. — Т. XIV, 2 (86). — С. 87—158.

31. Годунов С. К. Разностный метод численного расчета разрывных решений уравнений гидродинамики // Математический сборник. — 1959. — Т. 47(89), № 3. — С. 271—306.

32. Курант Р., Фридрихе К., Леви Г. О разностных уравнениях математической физики // Успехи математических наук. — 1941. — № 8. — С. 125—160.

33. Куржанский А. А., Куржанский А. Б., Варайя П. Роль макромоделировапия в активном управлении транспортной сетью // Труды Московского физико-технического института. - 2010. - Т. 2, № 4. - С. 100-118.

34. Математическое моделирование движения автотранспортных потоков методами механики сплошной среды. Двухполосный транспортный поток: модель Т-образного перекрестка, исследование влияния перестроений транспортных средств на пропускную способность участка магистрали / Н. Н. Смирнов [и др.] // Труды Московского физико-технического института. — 2010. — Т. 2, № 4. — С. 141—151.

35. Олейник О. А. О единственности и устойчивости обобщенного решения задачи Коши для квазилинейного уравнения // Успехи математических наук. - 1959. - Т. XIV, 2 (86). - С. 165-170.

Публикации по теме диссертации

36. Дорогуш Е. Г. Вычисление пропускной способности и уровня загруженности кольцевой автомагистрали / / Вестник Московского университета. Серия 15. Вычислительная математика и кибернетика. — 2013. — № 3. — С. 16-24.

37. Дорогуш Е. Г. Динамическая модель транспортных потоков на кольцевой автостраде // Доклады Академии Наук. — 2013. — Т. 453, № 4. — С. 363-367.

38. Дорогуш Е. Г. Математичское моделирование транспортных потоков на кольцевой автостраде // Сборник статей молодых ученых факультета ВМК МГУ. - 2011. - Вып. 8. - С. 54-68.

Напечатано с готового оригинал-макета

Подписано в печать 19.02.2014 г. Формат 60x90 1/16. Усл.печл. 1,0. Тираж 70 экз. Заказ 021.

Издательство ООО "МАКС Пресс" Лицензия ИД N 00510 от 01.12.99 г. 119992, ГСП-2, Москва, Ленинские горы, МГУ им. М.В. Ломоносова, 2-й учебный корпус, 527 к. Тел. 8(495)939-3890/91. Тел./факс 8(495)939-3891.

Московский государственный университет имени М. В. Ломоносова Факультет вычислительной математики и кибернетики

04201457078

На правах рукописи

Дорогуш Елена Геннадьевна

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

01.01.02 — дифференциальные уравнения, динамические системы и оптимальное управление

Диссертация на соискание ученой степени кандидата физико-математических паук

Научный руководитель:

доктор физико-математических паук

академик А. Б. Куржанский

Москва 2014

Оглавление

Введение........................................................................................4

1 Математическая модель транспортных потоков на автомагистрали .... 9

1.1 Динамическая модель транспортных потоков в сети..............................9

1.1.1 Модель узла транспортной сети..............................................11

1.2 Модель транспортных потоков на автомагистрали................................17

1.2.1 Модель узла автомагистрали..................................................18

1.2.2 Краевые условия................................................................20

1.3 Пропускная способность автомагистрали............................................20

1.3.1 Контролируемые уровни концентраций......................................21

1.3.2 Задача минимизации общего времени в пути................................23

1.3.3 Уровень загруженности автомагистрали....................................28

2 Равновесные состояния в модели автомагистрали при постоянных входных потоках................................................................................31

2.1 Зависимость между потоками со въездов и потоками между ячейками .... 31 2.1.1 Допустимые и недопустимые входные потоки..............................33

2.2 Общие условия на равновесные состояния..........................................34

2.3 Множество равновесий для фиксированных потоков со въездов..................35

2.3.1 Решение уравнения для п в модели незамкнутой автомагистрали .... 38

2.3.2 Решение уравнения для п в модели кольцевой автомагистрали..........39

2.4 Равновесные потоки со въездов ......................................................40

2.4.1 Равновесные потоки со въездов в модели незамкнутой автомагистрали 40

2.4.2 Равновесные потоки в модели кольцевой автомагистрали . . . ..........43

2.5 Об устойчивости равновесий..........................................................48

2.5.1 Устойчивость наименее загруженного равновесия...... ........ 49

2.5.2 Устойчивость наиболее загруженного положения равновесия в модели кольцевой автострады..........................................................50

2.5.3 Устойчивость произвольного положения равновесия......................52

2.6 Примеры................................................................................59

3 Управление состоянием автомагистрали при помощи выделенных полос 63

3.1 Модель автомагистрали с выделенными полосами ................................63

3.2 Построение управления................................................................65

3.2.1 Оценивание множества допустимых коэффициентов расщепления ... 66

3.2.2 Условие максимального использования пропускной способности платных полос........................................................................67

3.2.3 Координация управления на въездах........ ........................73

3.3 Обоснование алгоритма управления..................................................75

3.4 Примеры................................................................................79

Заключение ....................................................................................84

Список литературы ..........................................................................86

Введение

. Данная работа посвящена исследованию математических моделей транспортных потоков на автостраде и задаче управления состоянием автострады с платными полосами.

Можно выделить несколько подходов к математическому моделированию транспортных потоков. В микроскопических моделях задается закон движения каждого автомобиля, в зависимости от его текущего положения, скорости движения, характеристик движения соседних автомобилей и других факторов. Микроскопические модели, в свою очередь, можно разделить на непрерывные по пространству и по времени модели (например, [1-4]), и на дискретные по пространству и по времени модели, так называемые клеточные автоматы (например, [5]). В макроскопических моделях транспортный поток рассматривается как поток жидкости с особыми свойствами. Уравнения макроскопической модели устанавливают зависимость между потоком, плотностью, скоростью движения, возможно, ускорением и так далее. Макроскопические модели также могут быть непрерывными или дискретными. В непрерывных моделях изменение состояния участка дороги без ответвлений и перекрестков описывается, как правило, дифференциальными уравнениями в частных производных. Так, в статье [6] исследуется модель транспортного потока, при некоторых значениях параметров имеющая вид системы уравнений в частных производных второго порядка. В книге [7] дается обзор существующих макроскопических моделей транспортных потоков па дороге без перекрестков и строится макроскопическая модель транспортных потоков в сети. Как показано в статьях [1-3] и в книге [8], некоторые макроскопические модели являются, в некотором смысле, следствиями микроскопических моделей. Также можно изучать транспортные потоки с точки зрения теории экономического равновесия, что включает в себя отыскание равновесного распределения потоков в сети исходя из равенства времени в пути на используемых маршрутах (например, [9-11]). В книге [8] дается обзор детерминированных и стохастических моделей из каждой категории.

Настоящая работа посвящена изучению дискретной макроскопической модели потоков в транспортной сети. Эта модель довольно легко калибруется по измерениям, как это описано в работах [12; 13]. Кроме того, дискретная модель удобна для компьютерных симуляций.

Изучаемая в работе дискретная модель транспортных потоков основана на непрерывной гидродинамической модели [14-16]. В гидродинамической модели изменение состояния участка дороги без ответвлений и перекрестков подчиняется закону сохранения числа автомобилей др/дЬ + д//дх = 0. Здесь р — р(Ь,х) — плотность потока в точке х в момент то есть число автомобилей на единицу длины, / = /(¿, х) — поток в точке х в момент то есть число автомобилей, проезжающих через заданное сечение дороги х в единицу времени. Также предполагается, что существует функциональная зависимость между потоком / и плотностью р: / = /(р). График функции /(р) называется фундаментальной диаграммой. По-видимому, впервые о существовании фундаментальной диаграммы заявлено в статье [17]. В этой статье анализируются результаты измерений параметров транспортного потока на автомагистралях, проведенных в 1934 году в США. В гидродинамике функция /(р) выпуклая, в моделировании транспортных потоков функция /(р) обычно считается вогнутой (рисунок 1), в частности, в статье [17] фундаментальная диаграмма близка к параболе

Яр) = 4/тах- р

ртах \ ртах

где ртах — максимальная плотность, то есть плотность в состоянии «бампер к бамперу», ушах _ максимальный поток, или пропускная способность, участка автомагистрали. Таким

Л

/тг

0 ртах Р

Рис. 1. Фундаментальная диаграмма в непрерывной модели транспортных потоков

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

^ + = (1)

от ах

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

(см., к примеру, [7; 18]). Проблема в том, что слабое решение не единственно, и для нахождения единственного физически осмысленного решения нужны дополнительные условия, а именно энтропийные условия [18-21].

Для расчетов гидродинамической модели можно применить численную схему, предложенную в статье [22]. Для устойчивости этой численной схемы и сходимости разностных решений к слабому решению исходного уравнения должно выполняться условие Куранта — Фридрихса — Леви [23].

В статье [24] была предложена дискретная динамическая модель автомагистрали СТМ (the cell transmission model, клеточная передаточная модель). Модель СТМ совпадает с представленным методом численного решения задачи Коши для уравнения (1) с фундаментальной диаграммой в форме трапеции /(р) = minjwp, /тах, w(ртах — р)}. В статье [25] дискретная модель была расширена на слияния и разветвления дорог. Модель СТМ реализована в пакете программ [26] для ребер графа транспортной сети.

Другой важный компонент любой модели транспортных потоков в сети — модель узла сети, то есть правило вычисления потоков в узле по состоянию прилегающих ребер. Различные модели узла предлагались в работах [7; 25; 27-29].

Необходимость платных дорог в условиях перегрузки транспортной сети, как отмечено в статье [30], подчеркивается экономистами уже довольно давно. Дело в том, что в условиях перегрузки каждый дополнительный участник дорожного движения увеличивает задержки в пути для других участников дорожного движения. Такая ситуация обуславливает неоптимальное поведение всех участников дорожного движения в целом. Оптимальное в смысле суммарных затрат всех участников поведение стимулируется, как указано в обзоре [31], так называемым налогом А. С. Пигу: каждый участник дорожного движения платит за свой проезд по каждому ребру транспортной сети сумму, эквивалентную увеличению суммарных задержек всех остальных участников дорожного движения в результате его поездки. Такой подход не учитывает, однако, некоторые моменты. Во-первых, цена времени для разных водителей может различаться, и при этом не ясно, как определять плату за проезд по конкретному ребру транспортной сети. Во-вторых, состояние транспортной сети постоянно меняется, а вместе с ним должны меняться и стоимости проезда по ребрам.

В зависимости от выбранной модели транспортной сети модели и алгоритмы вычисления платы за проезд могут быть разными. Так, в работе [32] разрабатывается теория платных дорог в рамках модели экономического равновесия. Стоимость времени для всех агентов считается одинаковой, плата за проезд по каждому ребру устанавливается такая, чтобы любое равновесное по Нэшу — Вардропу распределение в системе с платными ребрами было в то

же время оптимальным (в смысле системного оптимума, то есть минимизации суммарного времени в пути) в системе без платы за проезд по ребрам. В статье [33] используется динамическая модель транспортной сети, и предлагается устанавливать стоимость проезда по платным ребрам сети и выделенным полосам автомагистрали динамически, в зависимости от текущих и желаемых условий (точнее, плотностей). В статье [34] рассматривается динамическая модель автомагистрали, близкая к модели, исследуемой в данной работе, и предлагается следующий способ управления состоянием автострады. При слишком большом входном потоке ограничиваются потоки со въездов. При этом, конечно, образуются очереди перед въездами. В то же время, есть возможность въехать на автомагистраль, минуя очередь перед въездом, но за плату, которая зависит от въезда, и от того, через какой съезд водитель покинет автомагистраль. В работе [31] дан обзор существующих методов и технологий платных дорог и платных полос.

Цель работы Целью данной работы является изучение свойств математической модели автострады, в том числе кольцевой автострады, и разработка алгоритма управления состоянием незамкнутой автострады с выделенными платными полосами путем изменения стоимости въезда в платные полосы.

Основные результаты

1. Для дискретной динамической модели автомагистрали предлагаются понятия пропускной способности и уровня загруженности. Получены правила вычисления пропускной способности.

2. Полностью описано множество положений равновесия в модели незамкнутой и кольцевой автострады. Исследована устойчивость всех положений равновесия.

3. Предложен алгоритм управления состоянием автострады с выделенными платными полосами. Цель алгоритма — максимальное использование пропускной способности выделенных полос, и при этом поддержание их в состоянии свободного движения, насколько это возможно.

Научная новизна Полученные результаты являются новыми. Исследование равновесных состояний в математической модели автомагистрали обобщает результаты работ [35; 36] на случай произвольных коэффициентов приоритета (в модели незамкнутой автострады) и на модель кольцевой автострады.

Теоретическая и практическая значимость Работа носит в основном теоретический характер. Исследование множеств положений равновесия — первый шаг к пониманию законов развития динамической системы, описывающей изменение состояния автострады. Результаты, касающиеся управления состоянием автострады с помощью платы за въезд на выделенные полосы могут быть применены па практике, если будут реализованы бесконтактные высокоскоростные системы оплаты въезда в платные полосы.

Структура диссертации Диссертация организована следующим образом.

В главе 1 представлена дискретная динамическая модель транспортных потоков в сети и модели незамкнутой и кольцевой автострады как ее частные случаи. Предлагается понятие пропускной способности автомагистрали и выясняется способ вычисления этой характеристики автомагистрали. Вводится понятие уровня загруженности автострады и изучаются его свойства.

В главе 2 модель автомагистрали исследуется как динамическая система: находится множество равновесий этой системы и исследуется устойчивость всех состояний равновесия.

В главе 3 представлена модель автомагистрали с выделенными платными полосами. Предлагается алгоритм управления состоянием такой автомагистрали за счет изменения стоимости въезда в платные полосы. Цель управления — при условии полного использования пропускной способности выделенных полос поддерживать их, насколько возможно, в незагруженном состоянии.

Глава 1

Математическая модель транспортных потоков на автомагистрали

В этой главе математическая модель транспортных потоков на автомагистрали, в том числе на кольцевой автомагистрали, изучается как динамическая система. Исследуются множества положений равновесия этой системы при фиксированных входных потоках, предлагаются определения пропускной способности и уровня загруженности автомагистрали.

Исследуемая модель транспортных потоков на автомагистрали является сужением модели транспортных потоков в сети иа графы специального вида. Поэтому сначала будет изложена общая модель транспортных потоков в сети. За основу взята модель транспортной сети, изложенная в статье [13], а правило перераспределения потоков в узле сети взято из статьи [29].

1.1 Динамическая модель транспортных потоков в сети

Транспортная сеть представляется ориентированным графом С = (V, Е), где V — множество вершин или узлов графа, Е — множество ребер графа, то есть упорядоченных пар вершин графа е = (и, и), и, у Е V. Ребра графа будем также называть соединениями. Выделяются вершины без входящих ребер, источники, и вершины без исходящих ребер, стоки. Ребра графа, инцидентные источникам, будем называть въездами, а ребра, инцидентные стокам — выездами или съездами. Пусть Ет С Е обозначает множество въездов, а Е<м1 С -Е — множество выездов. Мы рассматриваем только такие графы, в которых ребро не может одновременно быть въездом и выездом: ЕПЛ П ЕоаЪ = 0. Вершины графа, не являющиеся источниками и стоками, соответствуют перекресткам, местам слияния и разветвления дорог, а также разбивают длинные ребра па более короткие.

Динамическая модель транспортных потоков в сети дискретна как по времени, так и по

пространству.

Каждое ребро е транспортной сети характеризуется своей длиной, числом полос, пропускной способностью Fe, то есть максимальным потоком через это ребро, вместимостью Ne, то есть максимальным числом автомобилей на ребре, скоростью свободного движения ve, то есть наибольшей разрешенной скоростью, и скоростью распространения затора we. Пропускная способность ребра нормализована относительно шага по времени, а скорости свободного движения и распространения затора нормализованы относительно длины ребра и шага по времени. Пропускная способность ребра и вместимость пропорциональны числу полос. Шаг симуляции по времени должен быть настолько малым, чтобы выполнялись неравенства ve,we < 1.

Позиция системы есть пара (i,n(i)}, где t — шаг симуляции, n(t) = {ne(t), е € Е}, ne(t) — число автомобилей на ребре е на шаге t.

На каждом шаге для каждого ребра е G Е определяется требуемый исходящий поток feit) — min{veneit),Fe} (d означает demand, то есть спрос), и для каждого ребра, за исключением въездов, е € Е\Ет, определяется допустимый (максимальный) входящий поток feit) = mm{we(iVe — neit)),Fe} is означает supply, предложение).

Изменение состояния сети происходит согласно уравнению ne(t + 1) = ne{t) + /¿n(£) — — /°ut(i), e G E, где /™(i), /pout(i) — входящий и исходящий поток для ребра е. Для въездов е £ Ет задан неотрицательный входящий поток /¿n(t). При этом предполагается, что число автомобилей �