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

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

Факультет вычислительной математики и кибернетики

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

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

Математический анализ модели

транспортных потоков на автостраде

и управления ее состоянием

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

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

доктор физико-математических наук академик А. Б. Куржанский Москва Оглавление Введение............................................ 1 Математическая модель транспортных потоков на автомагистрали.... 1.1 Динамическая модель транспортных потоков в сети............... 1.1.1 Модель узла транспортной сети....................... 1.2 Модель транспортных потоков на автомагистрали................ 1.2.1 Модель узла автомагистрали......................... 1.2.2 Краевые условия................................ 1.3 Пропускная способность автомагистрали...................... 1.3.1 Контролируемые уровни концентраций................... 1.3.2 Задача минимизации общего времени в пути................ 1.3.3 Уровень загруженности автомагистрали.................. 2 Равновесные состояния в модели автомагистрали при постоянных входных потоках........................................ 2.1 Зависимость между потоками со въездов и потоками между ячейками.... 2.1.1 Допустимые и недопустимые входные потоки............... 2.2 Общие условия на равновесные состояния..................... 2.3 Множество равновесий для фиксированных потоков со въездов......... Решение уравнения для n в модели незамкнутой автомагистрали....

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

2.3.2 2.4 Равновесные потоки со въездов........................... 2.4.1 Равновесные потоки со въездов в модели незамкнутой автомагистрали 2.4.2 Равновесные потоки в модели кольцевой автомагистрали........ 2.5 Об устойчивости равновесий............................. 2.5.1 Устойчивость наименее загруженного равновесия............. 2.5.2 Устойчивость наиболее загруженного положения равновесия в модели кольцевой автострады............................. 2.5.3 Устойчивость произвольного положения равновесия........... 2.6 Примеры........................................ 3 Управление состоянием автомагистрали при помощи выделенных полос 3.1 Модель автомагистрали с выделенными полосами................ 3.2 Построение управления................................ 3.2.1 Оценивание множества допустимых коэффициентов расщепления... 3.2.2 Условие максимального использования пропускной способности платных полос.................................... 3.2.3 Координация управления на въездах.................... 3.3 Обоснование алгоритма управления......................... 3.4 Примеры........................................ Заключение.......................................... Список литературы..................................... Введение Данная работа посвящена исследованию математических моделей транспортных потоков на автостраде и задаче управления состоянием автострады с платными полосами.

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

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

Изучаемая в работе дискретная модель транспортных потоков основана на непрерывной гидродинамической модели [14–16]. В гидродинамической модели изменение состояния участка дороги без ответвлений и перекрестков подчиняется закону сохранения числа автомобилей /t + f /x = 0. Здесь = (t, x) плотность потока в точке x в момент t, то есть число автомобилей на единицу длины, f = f (t, x) поток в точке x в момент t, то есть число автомобилей, проезжающих через заданное сечение дороги x в единицу времени. Также предполагается, что существует функциональная зависимость между потоком f и плотностью : f = f (). График функции f () называется фундаментальной диаграммой.

По-видимому, впервые о существовании фундаментальной диаграммы заявлено в статье [17].

В этой статье анализируются результаты измерений параметров транспортного потока на автомагистралях, проведенных в 1934 году в США. В гидродинамике функция f () выпуклая, в моделировании транспортных потоков функция f () обычно считается вогнутой (рисунок 1), в частности, в статье [17] фундаментальная диаграмма близка к параболе где max максимальная плотность, то есть плотность в состоянии бампер к бамперу, f max максимальный поток, или пропускная способность, участка автомагистрали. Таким Рис. 1. Фундаментальная диаграмма в непрерывной модели транспортных потоков образом, изменение состояния автомагистрали описывается квазилинейным уравнением в частных производных относительно (t, x) В отличие от линейных уравнений в частных производных первого порядка, уравнение (1) может иметь разрывные решения даже при гладких начальных данных. Возможна и такая ситуация, что классическое решение задачи Коши для этого уравнения существует лишь до определенного момента времени. Поэтому рассматривается слабое решение уравнения (1) (см., к примеру, [7; 18]). Проблема в том, что слабое решение не единственно, и для нахождения единственного физически осмысленного решения нужны дополнительные условия, а именно энтропийные условия [18–21].

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

В статье [24] была предложена дискретная динамическая модель автомагистрали CTM (the cell transmission model, клеточная передаточная модель). Модель CTM совпадает с представленным методом численного решения задачи Коши для уравнения (1) с фундаментальной диаграммой в форме трапеции f () = min{v, f max, w(max )}. В статье [25] дискретная модель была расширена на слияния и разветвления дорог. Модель CTM реализована в пакете программ [26] для ребер графа транспортной сети.

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

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

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

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

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

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

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

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

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

Теоретическая и практическая значимость

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

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

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

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

В главе 3 представлена модель автомагистрали с выделенными платными полосами.

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

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

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

1.1 Динамическая модель транспортных потоков в сети Транспортная сеть представляется ориентированным графом G = (V, E), где V множество вершин или узлов графа, E множество ребер графа, то есть упорядоченных пар вершин графа e = (u, v), u, v V. Ребра графа будем также называть соединениями. Выделяются вершины без входящих ребер, источники, и вершины без исходящих ребер, стоки.

Ребра графа, инцидентные источникам, будем называть въездами, а ребра, инцидентные стовыездами или съездами. Пусть E in E обозначает множество въездов, а E out E кам множество выездов. Мы рассматриваем только такие графы, в которых ребро не может одновременно быть въездом и выездом: E in E out =. Вершины графа, не являющиеся источниками и стоками, соответствуют перекресткам, местам слияния и разветвления дорог, а также разбивают длинные ребра на более короткие.

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

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

Шаг симуляции по времени должен быть настолько малым, чтобы выполнялись неравенства ve, we < 1.

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

На каждом шаге для каждого ребра e E определяется требуемый исходящий поток fe (t) = min{ve ne (t), Fe } (d означает demand, то есть спрос), и для каждого ребра, за исключением въездов, e E \ E in, определяется допустимый (максимальный) входящий поток fe (t) = min{we (Ne ne (t)), Fe } (s означает supply, предложение).

Изменение состояния сети происходит согласно уравнению ne (t + 1) = ne (t) + fe (t) fe (t), e E, где fe (t), fe (t) входящий и исходящий поток для ребра e. Для въездов e E in задан неотрицательный входящий поток fe (t). При этом предполагается, что число автомобилей во входящих ребрах не ограничено сверху, и этим входящие ребра отличаются от всех остальных. Исходящий поток для выездов e E out всегда равен требуемому исходящему потоку: fe = fe (t). Потоки между смежными ребрами fe1,e2 (t), где e1 E \ E out и e2 E \ E in входящее и исходящее ребро некоторого узла v V, не являющегося ни стоком, ни источником, определяются моделью узла транспортной сети. При этом, если велиin чины ne (t) неотрицательны, то все потоки неотрицательны, входящий поток fe (t) для любого ребра e, за исключением въездов, не может превышать fe (t), а исходящий поток fe (t) из любого ребра e не может превышать fe (t). Поэтому справедливо следующее утверждение.

Утверждение 1.1. Пусть для всех ребер e E на шаге t величина ne (t) неотрицательна, и для всех ребер e, кроме, может быть, въездов (то есть e E \E in ), выполнено неравенство ne (t) Ne. Тогда для всех e E \ E in справедливо неравенство 0 ne (t + 1) Ne.

Доказательство. Действительно, поскольку ne (t + 1) = ne (t) + fe (t) fe (t), ne (t) 0, fe (t), fe (t) 0 и fe (t) fe (t) ve ne (t), то Для вершин e E \ E in, кроме того, справедливо неравенство fe (t) fe (t) we (Ne ne (t)), поэтому Предполагается, что для каждого ребра e E \ E in справедливо неравенство которое гарантирует, что если ребро e на шаге t не загружено, то есть если выполнено неравенство ve ne (t) Fe, то входящий поток в ребро e ограничен лишь его пропускной способностью, то есть выполнено также неравенство we (Ne ne (t)) Fe.

Нам также понадобится следующее утверждение.

Утверждение 1.2. Пусть ребро e выезд, то есть ребро, инцидентное стоку, и в момент t ребро e не загружено: ve ne (t) Fe. Тогда ve ne (t + 1) Fe.

Доказательство. Согласно условию (1.1), поскольку ребро e не загружено на шаге t, то fe (t) = Fe fe (t). Поскольку ребро e является выездом, то fe (t) = fe (t) = ve ne (t). В итоге то есть ve ne (t + 1) Fe.

1.1.1 Модель узла транспортной сети Рассматривается вершина v, не являющаяся ни источником, ни стоком. Пусть у рассматриваемой вершины m входящих и n исходящих ребер, m, n > 0. На каждом шаге t определены требуемые исходящие потоки fid (t) для всех входящих ребер и допустимые входящие потоки fjs (t) для всех исходящих ребер (рисунок 1.1).

Задана распределительная матрица Bv (t) = {ij (t)}j=1,...,n, ее элементы ij (t), коэффиi=1,...,m циенты расщепления, неотрицательны и задают ограничения на потоки fij (t) из i-го входящего ребра в j-е исходящее ребро рассматриваемой вершины в виде пропорции Для каждого i по крайней мере один из коэффициентов ij (t), j = 1,..., n, должен быть строго положительным. При умножении i-й строки матрицы Bv (t) на положительное число (i1 (t) +... + in (t))1 сумма элементов этой строки будет равна 1, пропорция при этом не изменится. Поэтому для упрощения рассуждений будем считать, что для всех i Исходящие потоки для ребер, входящих в рассматриваемую вершину, равны сумме всех потоков из данного ребра в исходящие:

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

Кроме того, заданы неотрицательные коэффициенты приоритета для входящих ребер pi (t), i = 1,..., m. Эти коэффициенты, как будет разъяснено далее, влияют на потоки между входящими и исходящими ребрами fij (t), если какая-либо из исходящих ячеек не может принять весь требуемый поток, то есть если хотя бы для одного j выполнено неравенство Для каждого исходящего ребра j не более одного входящего ребра с ненулевым требуемым потоком fij (t) = ij (t)fid (t) может иметь нулевой коэффициент приоритета. Это условие выполнено, в частности, если все коэффициенты приоритета входящих ребер pi, кроме, быть может, одного, строго положительны.

В статье [29] предлагается в качестве коэффициентов приоритета брать пропускные способности входящих соединений, то есть pi (t) = Fi, поскольку в этом случае выполнен принцип инвариантности: если для некоторого i, согласно модели узла, выполняется строгое неравенство fiout (t) < fid (t), то при увеличении требуемого потока fid (t) все потоки fij (t) останутся такими же. В то же время, как предложено в статье [27], можно рассматривать коэффициенты приоритета, равные требуемым исходящим потокам: pi (t) = fid (t). В этом случае несколько упрощаются формулы для результирующих потоков. В работах [13; 37] представлена модель транспортных потоков в сети, использующая именно такие значения коэффициентов приоритета.

Итак, модель узла определяет результирующие потоки fij (t) по требуемым исходящим и допустимым входящим потокам fid (t), fjs (t), и, возможно, дополнительным параметрам.

В нашей модели дополнительными параметрами являются распределительная матрица B(t) и коэффициенты приоритета pi. Приступим к изложению используемой нами модели узла.

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

1.1.1.1 Алгоритм вычисления потоков в узле сети Прежде чем вычислять потоки fij, вычисляются вспомогательные величины: ориентированные требуемые исходящие потоки fij = fid ij и коэффициенты приоритета для направd лений pij = pi ij.

На любом шаге k алгоритма определены вспомогательные множества J (k) {1,..., n}, Vj (k) {1,..., m}, j J (k), и вспомогательные величины fjs (k), j J (k).

Множество J (k) означает множество всех исходящих соединений с положительными приоритетами, потоки для которых до шага k не были определены. Величина fjs (k) есть остаток допустимого входящего потока j-го исходящего соединения, который на шаге k или позднее будет распределен по входящим соединениям из множества Vj (k), а также по входящим соединениям с нулевыми коэффициентами приоритета.

На первом шаге Ясно, что Vj (1) = для всех j J (1), и fij = 0 для всех пар (i, j), таких, что fij = 0 или pi > 0, j J (1).

Алгоритм начинается на шаге k = 1. Сначала вычисляются потоки fij для всех входящих соединений i со строго положительными коэффициентами приоритета pi, и лишь после этого вычисляются потоки fij для входящих соединений с нулевыми приоритетами.

1. Если на шаге k множество J (k) пустое, переходим на шаг 5.

2. Для каждого j J (k) вычисляем Далее будет показано, что величина в знаменателе строго положительна.

Среди всех aj (k), j J (k), находим наименьшее значение a(k), пусть его индекс (k), то есть a(k) = a(k) (k) = minjJ (k) aj (k).

3. Обозначим U(k) = {i V(k) (k) : fid a(k)pi }. Отметим, что неравенство fid a(k)pi для i V(k) (k) эквивалентно неравенству fi(k) a(k)pi(k).

(a) Если U(k) =, то для всех i U(k) определяем потоки fij = fij, j = 1,..., n, и пересчитываем вспомогательные множества и величины:

(b) В противном случае для всех i V(k) (k) и для всех j = 1,..., n определяем потоки fij = a(k)pij и пересчитываем вспомогательные множества и величины:

4. Переходим на следующий шаг алгоритма: k k + 1 и возвращаемся к пункту 1.

5. Определяем потоки fij для входящих соединений с нулевыми приоритетами pi = 0 как в модели разветвления (эта модель будет разобрана позже, на стр. 16):

На каждом шаге алгоритма определяются потоки fij по крайней мере для одного i, следовательно, алгоритм остановится не позднее, чем на шаге m + 1 (напомним, что m число входящих соединений).

Несложно видеть, что как на первом шаге, так и на всех остальных, множество Vj (k) Vj (1) = {i : pd > 0, fij > 0} для всех j J (k) содержит по крайней мере один элемент, а поскольку для всех i Vj (k) справедливо неравенство fid ij = fij > 0, то и pij = pi ij > 0.

Поскольку для каждого исходящего соединения j существует не более одного входящего соединения i с положительным требуемым потоком fij и нулевым приоритетом pi, то формулы Также справедливо следующее утверждение.

Утверждение 1.3. Величина a(k) не уменьшается: если алгоритм не завершился после шага k, то a(k + 1) a(k).

Доказательство. Множества J (k) и Vj (k) не увеличиваются, то есть, справедливы включения J (k+1) J (k) и Vj (k+1) Vj (k) для j J (k+1). Обозначим Vj (k) = Vj (k)\Vj (k+1).

Ясно, что Vj (k) = Vj (k + 1) Vj (k) (знак обозначает объединение непересекающихся множеств). Справедлива цепочка неравенств откуда следует, что С учетом того, что J (k + 1) J (k), получаем 1.1.1.2 Примеры вычисления результирующих потоков Проиллюстрируем изложенный алгоритм на нескольких примерах.

Простой узел Простым мы называем узел с одним входящим соединением и одним исходящим соединением (рис. 1.2).

В этом случае поток между входящим и исходящим ребром есть минимум из двух величин: требуемого исходящего потока входящего соединения fid (t) и максимального входящего потока исходящего соединения fis (t):

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

поток из входящего ребра в j-е исходящее.

В случае разветвления дорог коэффициент приоритета p входящего ребра не влияет на вычисления результирующих потоков fj, и важны лишь коэффициенты расщепления j :

должно выполняться равенство fj1 /j1 = fj2 /j2 для всех j1, j2 {1,..., n}.

Алгоритм завершает работу за один шаг: вычисляется и сразу определяется суммарный исходящий поток для единственного входящего ребра Поток из входящего в j-е исходящее ребро равен fj = f j.

Слияние дорог Под слиянием дорог понимается узел с несколькими входящими и одним исходящим соединением (рис. 1.4).

поток из i-го входящего в исходящее ребро.

Для слияния дорог на вычисление результирующих потоков не влияют коэффициенты расщепления i (они все должны быть равны единице), зато существенны коэффициенты приоритета pi, i = 1,..., m.

величины fi, i V(k), определены до шага k и fi a(k)f s при i V(k). Если на некотором шаге k для всех i V(k) будет выполнено неравенство fid > a(k)pi, алгоритм остановится после шага k.

Пусть все коэффициенты приоритета pi для входящих соединений с ненулевым требуm ищется решение уравнения относительно a. Решение существует и единственно, поскольку функция в левой части непрерывна и монотонно возрастает на отрезке [0, A], где A = maxi{1,...,m} (fid /pi ), от нуля при a = fid > f s при a = A. Результирующие потоки fi = min{fid, api }.

Если коэффициент приоритета одного входящего соединения i с положительным требуемым исходящим потоком fid равен нулю, сначала вычисляются результирующие потоки fi для всех остальных входящих соединений, как если бы этого соединения i с нулевым приоритетом вообще не было, затем вычисляется поток fi = min{fid, f s fi }.

1.2 Модель транспортных потоков на автомагистрали Изложенная ниже модель автомагистрали была предложена в статьях [36; 38] и диссертации [35]. Как уже было сказано, мы рассматриваем эту модель автомагистрали с измененной, как предложено в статье [29], моделью узла сети, поэтому свойства рассматриваемой нами модели отличаются от свойств оригинальной модели, изученных в работах [35; 36]. Также, кроме обыкновенной, незамкнутой автомагистрали, мы будем изучать свойства модели кольцевой автомагистрали.

На рисунке 1.5 изображена схема модели автомагистрали. Автомагистраль состоит из K соединенных последовательно ребер, которые в статьях [24; 25] называются ячейками, кроме того, в каждом узле может быть въезд и съезд. Въезд в начале и выезд в конце ячейки имеют тот же индекс, что и сама ячейка.

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

Поэтому состояние выездов мы рассматривать не будем.

Для основной ячейки i заданы следующие характеристики:

Для въезда в i-ю ячейку заданы скорость свободного движения vi и пропускная способность въезда Ri. Для выезда из i-й ячейки задана пропускная способность выезда Si. Кроме того, для въездов и основных ячеек определены коэффициенты приоритета pr, pf > 0. Для упрощения рассуждений будем считать, что pr + pf = 1. Как и прежде, скорости vi, vi, wi нормированы относительно длины ячейки и шага по времени, а пропускные способности Fi, Ri, Si нормированы относительно шага по времени. Предположение (1.1) имеет вид Неравенства такого же вида должны выполняться для всех ячеек-съездов.

На въезде перед i-й ячейкой формируется очередь, величина qi (t) обозначает число автомобилей в очереди перед i-й ячейкой на шаге t. Очередь увеличивается за счет входного потока di (t) и уменьшается за счет потока автомобилей из очереди в основную ячейку ri (t).

Входной поток di (t) есть число автомобилей, подъезжающих к i-му въезду на шаге t; ri (t) есть число автомобилей, перемещающихся из очереди перед i-й ячейкой в i-ю основную ячейку на шаге t.

Пусть fi (t) поток из i-й основной ячейки в (i + 1)-ю на шаге t, si (t) поток из i-й основной ячейки в съезд в конце ячейки.

Позиция рассматриваемой системы есть тройка {t, n(t), q(t)}. Число автомобилей в ячейках и в очередях перед въездами меняется по следующему закону:

1.2.1 Модель узла автомагистрали Распределительные матрицы в узлах следующие. Весь поток со въезда переходит в основную ячейку, но не в выезд из предыдущей ячейки, а коэффициенты расщепления для потока из основной ячейки постоянны:

В частности, если у i-й ячейки нет выезда, то is = 0. В модели кольцевой автомагистрали требуется, чтобы на автомагистрали был по крайней мере один выезд, то есть должно выполняться строгое неравенство В статье [39] показано, что коэффициенты расщепления для потоков из основных ячеек меняются довольно медленно и можно с некоторой погрешностью считать их постоянными для интервала времени порядка нескольких часов. В работе [40] приведен алгоритм оценивания, в том числе, коэффициентов расщепления по неполным данным измерений.

Для всех i определяются требуемые исходящие потоки для основных ячеек автомагистрали fid (t) и въездов ri (t):

и допустимые входящие потоки для основных ячеек автомагистрали В таком определении величины Fid и требуемого исходящего потока fid (t) учтены ограничения, накладываемые максимальным входящим потоком для выезда ss (t) = Si.

Потоки fi1 (t), si1 (t), ri (t) определяются по требуемым исходящим потокам fi1 (t), ri (t) и допустимым входящим потокам fis (t), ss (t) = Si1 (рисунок 1.6) по следующему правилу, называемому, как уже было сказано, моделью узла.

1. Если fi1 (t) + ri (t) fis (t), то fi1 (t) = fi1 (t), ri (t) = ri (t).

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

(a) Если fi1 (t) pf fis (t), то fi1 (t) = fi1 (t), ri (t) = fis (t) fi1 (t).

(b) Если ri (t) pr fis (t), то ri (t) = ri (t), fi1 (t) = fis (t) ri (t).

(c) Иначе fi1 (t) = pf fis (t), ri (t) = pr fis (t).

Наконец, во всех четырех случаях si1 (t) = (is /if )fi1 (t). Можно выписать формулу для потоков fi1 (t), r(t), охватывающую все случаи:

1.2.2 Краевые условия В модели кольцевой автомагистрали нулевая ячейка эквивалентна K-й, а (K +1)-я эквивалентна первой. Далее равенство индексов в модели кольцевой автомагистрали понимается как эквивалентность по модулю K.

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

Также задан входной поток f1 (t).

Также в модели незамкнутой автомагистрали добавляется ячейка-выезд после последs ней, K-й ячейки, FK+1 = FK+1 пропускная способность этой дополнительной, (K + 1)-й ячейки. Поток из K-й ячейки в (K + 1)-ю есть fK (t) = min{fK (t), FK+1 }.

Обозначения Для векторов x, y Rn вводим следующие обозначения:

1.3 Пропускная способность автомагистрали Этот параграф дополняет статью [41].

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

1.3.1 Контролируемые уровни концентраций Для обычной, то есть незамкнутой, или кольцевой автомагистрали будем решать следующую задачу. Найти такие уровни концентраций n, соответствующие свободному движению, которые можно поддерживать сколь угодно долго за счет управления в виде ограничения на потоки со въездов.

Управление для каждого въезда ui (t) 0 ограничивает требуемый поток со въезда:

а также в модели незамкнутой автомагистрали. Необходимо найти векторы n, такие, что n соответствует свободному потоку во всех ячейках автомагистрали, и для любого n(t) n найдется управление u(t) такое, что под действием этого управления траектория системы остается во множестве N = {n : 0 n n }, то есть, выполнено неравенство n(t + 1) n. Такие векторы n назовем контролируемыми уровнями концентраций.

В дальнейшем нам потребуется следующая лемма.

Лемма 1.1 (о монотонности). Рассмотрим два состояния динамической системы, соответствующей кольцевой или обычной автомагистрали, (q 1 (t), n1 (t)) и (q 2 (t), n2 (t)). Справедливы следующие утверждения.

2. Если r1,d (t) r2,d (t) (а также f0 (t) f0 (t), в модели незамкнутой автомагистрали) и n1 (t) n2 (t), то r1 (t) r2 (t), n1 (t + 1) n2 (t + 1).

Доказательство. Оба утверждения достаточно доказать для различающихся лишь в одной компоненте векторов n, q или rd.

Пусть q 1 (t) = q 2 (t), или, в доказательстве второй части леммы, r1,d (t) = r2,d (t). Пусть векторы n1 (t) и n2 (t) различаются не более чем в одной компоненте: n1 (t) n2 (t) для некоi i торого i, n1 (t) = n2 (t) при j = i. Ясно, что n1 (t + 1) = n2 (t + 1), если j = i, j = i ± 1.

Поскольку fi1,d (t) fi2,d (t), то n1 (t + 1) n2 (t + 1). Поскольку fi1,s (t) fi2,s (t), то n1 (t + 1) n2 (t + 1). Далее, где Неравенства if vi ni (t) Fid и wi (Ni ni (t)) Fis, согласно предположению 1.2, одновременно выполняться не могут, поэтому ni (t + 1) строго возрастает как функция от ni (t), следовательно, n1 (t + 1) n2 (t + 1). В случае незамкнутой автомагистрали для нулевой и последней, (K + 1)-й, ячейки величина ni (t + 1), i = 0, K + 1, также монотонно возрастает как функция от ni (t): n0 (t + 1) = n0 (t) + f1 (t) f0 (t), поток f1 (t) задан и не зависит от n0 (t), поток f0 (t) определяется по общей формуле; nK+1 (t + 1) = nK+1 (t) + fK (t) fK+1 (t), поток fK (t) определяется по общей формуле при rK+1 (t) = 0.

Пусть n1 (t) = n2 (t), q 1 (t) q 2 (t). Ясно, что в этом случае r1,d (t) r2,d (t), поэтому n1 (t + 1) n2 (t + 1). Что касается длин очередей, поток со въезда ri (t) определяется по формуле поэтому qi (t + 1) строго возрастает как функция от qi (t).

Наконец, в случае n1 (t) = n2 (t), f 1,d (t) f 2,d (t), разумеется, n1 (t + 1) n2 (t + 1).

Лемма о монотонности была доказана для несколько иной модели в работах [35; 36].

Из леммы о монотонности следует, что n nu, где nu = Fid /(if vi ), является контроi лируемым уровнем концентраций, если при n(t) = n и r(t) = 0 выполнено неравенство n(t + 1) n :

что эквивалентно неравенству fi1 fi /if для всех i, а в модели незамкнутой автомагистрали для i = 1,..., K + 1. Здесь fi = min{fid (n ), fi+1 (n )} = min{if vi n, Fi+1 }, а в модели незамкнутой автомагистрали fK+1 = vK+1 n. Пусть f полнены неравенства fi Fid для всех i, fi Fi+1 для всех i, кроме i = K + 1, в модели незамкнутой автомагистрали, а также fi1 fi /i, для всех i, кроме i = 0, в модели незамкнутой автомагистрали. Отметим, что из неравенств fi Fid и fi1 fi /i следует неравенство fi1 Fis. Тогда вектор n с компонентами n = fi /(if vi ) является контролируемым вектором концентраций.

1.3.2 Задача минимизации общего времени в пути Общим временем в пути на интервале времени [, ] назовем функционал в модели незамкнутой автомагистрали, и в модели кольцевой автомагистрали.

Поскольку то можно преобразовать выражения для общего времени в пути следующим образом. Для кольцевой автомагистрали Аналогично, для незамкнутой автомагистрали Будем решать задачу о минимизации общего времени в пути в стационарном случае, то есть когда входные потоки d, число автомобилей в ячейках n (за исключением нулевой ячейки в модели незамкнутой автомагистрали), потоки со въездов и между ячейками r, f постоянны. Поскольку входные потоки d, f1 и начальные длины очередей заданы, нужно минимизировать выражение в модели кольцевой автомагистрали или в модели незамкнутой автомагистрали, при условии, что существует равновесное состояние (n, r, f ), в котором r d, r R (а также f0 f1, f0 F0 в модели незамкнутой автомагистрали) и si /is = fi /if для всех i.

Утверждение 1.4. Минимум в задаче минимизации общего времени движения достигается при ni Fid /if vi, i = 1,..., K (а также nK+1 FK+1 /vK+1 ) для незамкнутой автомагистрали).

Доказательство. Действительно, пусть (n, r, f ) некоторое состояние равновесия. Обозначим nu (f ) = fi /(if vi ). Ясно, что nu (t) F d. Тройка (nu (f ), r, f ) также является состоянием равновесия, причем n nu (f ), поэтому значение функционала общего времени движения в состоянии (nu (f ), r, f ), во всяком случае, не больше, чем в состоянии (n, f, r).

С учетом только что доказанного утверждения, будем рассматривать лишь n nu, где nu = Fi /(if vi ), i = 1,..., K, а в модели незамкнутой автомагистрали nu Несложно видеть, что при этом в решении задачи о минимизации общего времени движения в стационарном случае вектор n является контролируемым уровнем концентраций.

Будем увеличивать временной интервал: +. При этом задача об отыскании наименьшего общего времени в пути в стационарном случае перейдет в следующую задачу.

Обозначим ri = min{di, Ri }. Для кольцевой автомагистрали Для незамкнутой автомагистрали обозначим дополнительно f0 = min{f1, F0 }, K+1 = 1, rK+1 = 0. Задача о наименьшем общем времени в пути имеет вид Максимизируемое выражение в обоих случаях является суммой исходящих потоков si и fK+ для незамкнутой автомагистрали. Поэтому имеет смысл значение максимизируемого выражения на решении задачи при достаточно больших входных потоках di, f1, а именно, при di Ri, f1 F0, назвать пропускной способностью автомагистрали.

1.3.2.1 Пропускная способность незамкнутой автомагистрали Для незамкнутой автомагистрали задача (1.4), и, в частности, задача о пропускной способности, решается явно. Для этого вычислим вектор, ограничивающий сверху все равновесные потоки f по следующему правилу: f0 уже задан: f0 = min{f1, F0 }, а поток fi вычисляется через fi1 :

После этого пересчитываем максимальные равновесные потоки f таким образом, чтобы выполнялось неравенство fi1 fi /if для i = 1,..., K + 1: fK+1 = fK+1, При этом fi /if fi1 0, и в то же время, поскольку fi fi if (fi1 + ri ), Понятно, что при таком определении f максимальный равновесный поток для заданных входных потоков d, f1.

Значение максимизируемого функционала на решении задачи (1.4), таким образом, есть а пропускная способность незамкнутой автомагистрали равна 1.3.2.2 Пропускная способность кольцевой автомагистрали Поскольку решение задачи (1.3) о пропускной способности автомагистрали содержит контролируемый уровень концентраций, то для равновесного потока f должны выполняться неравенства fi1 fi /if для всех i, а поскольку f F d, то Для вектора F справедливо следующее утверждение.

Утверждение 1.5. Для всех i справедливо неравенство Fi1 Fi /i.

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

Лемма 1.2. Если для некоторого fK, 0 fK FK, справедливо неравенство fK (fK ) fK, то поток f (fK ), определенный по формулам fK (fK ) = fK, является наибольшим равновесным потоком с заданной компонентой fK.

Доказательство. Из неравенства Fi1 Fi /if, справедливого для всех i, следует, что для всех i = 1,..., K выполнено неравенство поэтому Поскольку для i = 0 неравенство fK = f0 (fK ) fK справедливо, то Далее, для всех без исключения i справедливо неравенство fi1 (fK ) fi (fK )/if, и, кроме того, fi (fK ) fi (fk ) if (fi1 (fK ) + ri ), поэтому Таким образом, для всех i выполнены неравенства 0 fi (fK )/if fi1 (fK ) ri, следовательно, вектор f (fK ) является равновесным потоком.

Вектор f (fK ), очевидно, ограничивает сверху значения равновесных векторов потоков с заданной компонентой fK, а определение вектора f (fK ) дополнительно обеспечивает выполнение условия fi1 fi /if. Максимальность вектора f (fK ) среди всех векторов с заданной компонентой fK, таким образом, следует из самого определения f (fK ).

Справедливо следующее утверждение.

Утверждение 1.6. Если fK (FK ) FK, то вектор f (FK ) является решением задачи (1.3).

Доказательство. Ранее было показано, что для любого равновесного вектора потоков f выполнено неравенство f F. Кроме того, согласно лемме 1.2, f (FK ) есть максимальный из равновесных векторов с заданной компонентой FK.

Если же fK (FK ) < FK, то решение задачи о пропускной способности кольцевой автомагистрали можно отыскать следующим образом.

Утверждение 1.7. Если fK (FK ) < FK, то на отрезке [0, FK ] существует единственный корень fK уравнения fK (fK ) = fK, и максимум в задаче (1.3) достигается на векторе f (fK ), где fK Доказательство. Функция fK (fK ) представляет собою минимум из функций, линейных по fK, и, следовательно, является вогнутой функцией.

При r = 0 единственный корень уравнения fK (fK ) = fK на отрезке [0, FK ] есть fK = 0, поскольку при fK > 0 справедливо неравенство При r > 0 справедливы строгие неравенства fK (0) > 0, fK (FK ) FK < 0, и функция fK (fK ) fK вогнутая, следовательно, существует единственный корень fK уравнения fK (fK ) fK = 0 на отрезке [0, FK ], причем fK (fK ) < fK при fK < fK FK.

Согласно лемме 1.2, f (fK ) есть максимальный из равновесных векторов с заданной компонентой fK, следовательно, он и является решением задачи (1.3).

1.3.3 Уровень загруженности автомагистрали Выберем некоторый контролируемый уровень концентраций n 0, например, уровень концентраций, соответствующий решению задачи о пропускной способности. Для любого состояния системы в момент времени t, а точнее, для любого вектора состояний основных ячеек n(t), можно определить уровень загруженности автомагистрали c(t) как число шагов, за которое можно привести систему во множество N = {n : 0 n n } за счет ограничения потоков со въездов:

Для уровня загруженности автомагистрали справедливы следующие свойства.

Утверждение 1.8. Автомагистраль разгружается быстрее всего при u 0, то есть когда все въезды перекрыты.

Доказательство. Действительно, пусть 0 n1 (t) = n2 (t) N, 0 = u1 (t+t) u2 (t+t). Тоd 2,d гда 0 = r1,d (t) r2,d (t) (а также 0 = f0 (t) f0 (t) в модели незамкнутой автомагистрали).

В силу леммы 1.1 о монотонности, n1 (t + 1) n2 (t + 1).

Из неравенства n1 (t+t) n2 (t+t) следует неравенство n1 (t+t+1) n2 (t+t+1).

Применяя математическую индукцию, получаем, что неравенство n1 (t + t) n2 (t + t) справедливо для всех t = 0, 1, 2,....

Утверждение 1.9. Определение уровня загруженности автомагистрали корректно.

Доказательство. Поскольку дорога разгружается быстрее всего, когда перекрыты въезды, то уровень загруженности автомагистрали не зависит от входных потоков d (и f1, для незамкнутой автомагистрали) и длин очередей q(t) (и n0 (t)).

Утверждение 1.10. Для модели незамкнутой автомагистрали существует максимальный уровень загруженности, а именно, c(N ).

Доказательство. То, что c(N ) максимальный уровень загруженности, следует из леммы о монотонности.

Конечность уровня загруженности c(N ) вытекает из следующих соображений. Пусть в момент t неравенство n(t) n еще не выполнено: по крайней мере для одного i справедливо неравенство ni (t) > n. С учетом леммы о монотонности и контролируемости уровня концентраций n, справедливы неравенства ni+1 (t + 1) if vi n, ni+2 (t + 2) if i+1 vi vi+1 n этом шаге fK+1 (t + K + 1 i) n k=i (k vk ). Следовательно, через K + 1 шагов число автомобилей в основных ячейках автомагистрали i= mini n k=i (k vk ). Следовательно, Утверждение 1.11. В модели кольцевой автомагистрали не существует максимального уровня загруженности: для любого вектора состояний основных ячеек автомагистрали n1 N найдется вектор n2 N, такой, что c(n2 ) > c(n1 ).

Доказательство. Будем считать, что n1 nc (F d ), где nc (F d ) = Ni Fid /wi, i = 1,..., K.

Если это не так, увеличим вектор n1, при этом уровень загруженности, согласно лемме о монотонности, не уменьшится.

Для n nc поток f между ячейками при rd = 0 зависит от n линейно: fi (n) = wi+1 (Ni+ ni+1 ). Поэтому для n(t) nc Обозначим i (t) = Ni ni (t). Тогда выполнено неравенство A 1 1. Положим n2 = N 1. Пусть n1 (t) = n1, n2 (t) = n2. При нулевых входящих потоках следовательно, c(n2 ) c(n1 ) + 1.

1.3.3.1 Примеры Примеры здесь и в следующей главе будут приведены для автомагистралей с двумя основными ячейками (K = 2). Схемы незамкнутой и кольцевой автомагистрали с двумя основными ячейками изображены на рис.1.7. Первая и вторая основные ячейки выделены.

(а) Схема незамкнутой автомагистрали (б) Схема кольцевой автомагистрали Рис. 1.7. Схемы автомагистралей с двумя основными ячейками На рисунке 1.8 представлены карты уровней загруженности незамкнутой и кольцевой автомагистралей, состоящих из двух ячеек. Цветом одной яркости обозначены области с одинаковым уровнем загруженности. Чем светлее оттенок, тем меньше соответствующий этой области уровень загруженности.

(а) Уровни загруженности незамкнутой автома- (б) Уровни загруженности кольцевой автомагигистрали страли Рис. 1.8. Карты уровней загруженности кольцевой и обычной автомагистрали Глава Равновесные состояния в модели автомагистрали при постоянных входных потоках В этой главе обобщаются результаты работ [35; 36] на модель незамкнутой автомагистрали с произвольными коэффициентами приоритета и на модель кольцевой автострады.

Результаты статьи [42] переработаны с учетом изменений в модели кольцевой автострады.

Некоторые результаты этой главы изложены в статье [43].

В модели автомагистрали зафиксируем входные потоки di (t) di, i = 1,..., K, а также, в модели незамкнутой автомагистрали, f1 (t) f1. Под равновесием или положением равновесия будем понимать такое состояние автомагистрали, в котором число автомобилей в основных ячейках и потоки между ними остается неизменным: ni (t) ni, i = 1,..., K, fi (t) fi, i = 0,..., K, при этом постоянны также потоки со въездов и исходящие потоки:

ri (t) ri, si (t) si, i = 1,..., K. Ясно, что ri di, i = 1,..., K, f0 f1 (в модели незамкнутой автомагистрали). Если ri = di, то длина очереди перед i-м въездом постоянна, если же ri < di, то очередь перед i-м въездом растет со скоростью (di ri ) автомобилей за шаг симуляции. То же самое можно сказать про нулевую ячейку-въезд в модели незамкнутой автомагистрали: если f0 = f1, то число автомобилей в нулевой ячейке постоянно, если же f0 < f1, то число автомобилей в нулевой ячейке растет со скоростью (f1 f0 ) автомобилей за шаг.

2.1 Зависимость между потоками со въездов и потоками Как в модели незамкнутой автомагистрали, так и в модели кольцевой автомагистрали потоки со въездов ri (а также f0, в случае обычной, незамкнутой автомагистрали) однозначно определяют потоки между ячейками fi, i = 1,..., K. В обеих моделях эта зависимость следует из равенства суммарного входящего и суммарного исходящего потока для каждой ячейки: fi = if (fi1 + ri ), i = 1,..., K.

Для незамкнутой автомагистрали потоки fi определяются по потокам ri и f0 последоf вательно: поток f0 уже определен, а если определен fi, то fi+1 = i+1 (fi + ri+1 ). Ясно, что потоки fi (f0, r), i = 0,..., K, определяются однозначно.

Утверждение 2.1. Для незамкнутой автомагистрали Доказательство. Действительно, равенство f1 (f0, r) = 1 (f0 + r1 ) верно. Для i > Для кольцевой дороги зависимость потоков между ячейками fi от входящих потоков ri потоков между ячейками и входящих потоков, Поскольку определитель матрицы A отличен от нуля, а именно, то решение системы уравнений Af = r существует и единственно.

Напомним, что для модели кольцевой автомагистрали индексы, эквивалентные по модулю K, считаются одинаковыми.

Утверждение 2.2. Для кольцевой дороги потоки между ячейками fi зависят от потоков Доказательство. Заметим, что В частности, С учетом этого равенства и определения коэффициентов ij, получаем Наконец, для всех i выполнено равенство что завершает доказательство.

2.1.1 Допустимые и недопустимые входные потоки В модели незамкнутой автомагистрали обозначим rK+1 = 0. Поток со въездов (f0, r), f0 F0, r R, назовем допустимым, если выполнены неравенства fi (f0, r) Fid, i = = 1,..., K, fi1 (f0, r) + ri Fis, i = 1,..., K + 1. Если хотя бы одно из этих неравенств не выполнено, поток со въездов (f0, r) назовем недопустимым. Если все неравенства выполнены строго (fi (f0, r) < Fid, i = 1,..., K, fi1 (f0, r) + ri < Fis, i = 1,..., K + 1), то поток со въездов назовем строго допустимым.

Для модели кольцевой автомагистрали поток со въездов r R назовем допустимым, если для всех i = 1,..., K выполнены неравенства fi (r) Fid и fi1 (r) + ri Fis. Если не выполнено хотя бы одно из указанных неравенств, то поток со въездов r назовем недопустимым. Если все неравенства выполнены строго (fi (r) < Fid, fi1 (r) + ri < Fis, i = 1,..., K), то поток r назовем строго допустимым.

Заметим, что из неравенства fi Fid следует неравенство fi1 + ri Fis :

поскольку Fid if Fis. Поэтому в определении допустимого потока со въездов можно уменьшить число неравенств. Пусть в модели незамкнутой автомагистрали fK+1 (f0, r) = fK (f0, r), FK+1 = FK+1. Для модели незамкнутой автомагистрали поток со въездов (f0, r) является Для модели кольцевой автомагистрали поток со въездов r является Входному потоку d (и f1, в случае незамкнутой автомагистрали) в положении равновесия могут соответствовать потоки со въездов r r (и f0 f0 ), где ri = min{di, Ri }, i = 1,..., K (f0 = min{f1, F0 }). Входной поток d (и f1 ) назовем допустимым, недопустимым или строго допустимым, если поток со въездов r (и f0 ) является допустимым, недопустимым или строго допустимым соответственно.

Ясно, что если входной поток d (или (f1, d), в случае незамкнутой дороги) не является допустимым, то не существует положений равновесия, в которых r = r (и f0 = f0 ), поэтому в любом положении равновесия по крайней мере на одном въезде будет расти очередь.

2.2 Общие условия на равновесные состояния кроме того, для модели незамкнутой автомагистрали fK+1 = FK+1, rK+1 = 0.

Множество положений равновесия есть множество наборов векторов (n, f, r), r r (и f0 f0 для незамкнутой автомагистрали), для которых справедливы равенства суммарных входящих и суммарных исходящих потоков для основных ячеек автомагистрали и правила приоритета:

1. Если fi1 + ri fis, то fi1 = fi1, ri = ri.

2. Иначе, если fi1 pf fis, то fi1 = fi1, ri = fis fi1.

4. Если же fi1 > pf fis и ri > pr fis, то fi1 = pf fis, ri = pr fis.

Правила приоритета должны выполняться для всех i = 1,..., K, а в случае незамкнутой автомагистрали также при i = K + 1.

2.3 Множество равновесий для фиксированных потоков со въездов Для фиксированных потоков со въездов r (и f0 для незамкнутой дороги) потоки f между ячейками, как уже было сказано, определяются однозначно: f = f (r) для кольцевой автомагистрали и f = f (f0, r) для обычной, незамкнутой автомагистрали, а значения n определяются из вытекающего из правил приоритета уравнения fi = min{fid, fi+1 ri+1 }:

где Fi = min{Fid, Fi+1 ri+1 }, Ni = Ni ri /wi.

Ясно, что уравнение (2.2) имеет решение, только если fi Fi, то есть если выполнены неравенства fi Fid, fi + ri+1 Fi+1, а это равносильно допустимости потока со въездов.

Обозначим Поскольку для решений n уравнения (2.2) if vi ni fi и wi (Ni ni ) fi1, то справедливы неравенства nu (f, r) ni nc (f, r).

Утверждение 2.3. Для допустимого потока со въездов nu (f, r) nc (f, r).

Доказательство. С учетом предположения (1.2), для допустимого потока со въездов Заметим, что для всех n из множества nu n nc выполнены неравенства fid (n) fi, fis (n)ri fi1. Для каждого равновесного n для всех i хотя бы одно из равенств fi1 = fi1, fi1 = fis ri выполнено, поскольку fi1 = min{fi1, fis ri }.

Выпишем ограничения, накладываемые на n каждым из четырех случаев правил приоритета в отдельности. В случае 1, поскольку неравенство fi1 +ri fis выполнено для всех n, таких, что nu n nc, то Наконец, в случае Выпишем теперь все ограничения на n, происходящие из правил приоритетов при фиксированных значениях потоков со въездов.

• Если ri = ri, то выполнены пункты 1 или 3 из правила приоритетов:

Поскольку хотя бы одно равенств fi1 = fi1, fis = fi1 + ri выполнено для всех n, решающих уравнение (2.2), то дополнительные ограничения на n возникают лишь в том случае, когда fi1 /pf < ri /pr : если при этом fi1 < Fi1, то ni1 = nu.

• Если ri < ri, то могут выполняться лишь пункты 2 или 4 из правила приоритетов, что накладывает следующие ограничения на n:

Это означает, что если fi1 /pf > ri /pr, то неравенство ri < ri в положении равновесия невозможно; если fi1 + ri < Fis, то ni = nc ; если fi1 /pf < ri /pr и fi1 < Fi1, то, кроме того, ni1 = nu.

• Аналогично, в случае незамкнутой автомагистрали, если f0 = f0, то выполнены пункты 1 или 2 из правила приоритетов:

Неравенства r1 < r1 и f0 /pf > ri /pr, как уже было отмечено, одновременно выполняться в положении равновесия не могут. Дополнительные ограничения на n возникают, если r1 < r1, f0 /pf ri /pr, и при этом f0 + r1 < F1 : при таких условиях n1 = nc.

• Если же f0 < f0, то выполнены пункты 3 или 4 из правила приоритетов:

Здесь должны выполняться неравенство f0 /pf r1 /pr и одно из равенств r1 = r1, f0 /pf = r1 /pr, а ограничение на n появляется при f0 + r1 < F1 : n1 = nc.

Если в положении равновесия ri < ri, то ri < ri = Ri, поскольку ri Ri. Если же ri = ri, то возможны как равенство ri = ri, так и неравенство ri < ri, впрочем, последнее неравенство возможно лишь в случае ri < Ri, и при этом ri < ri Ri.

Неравенство ri < ri необходимо выполнено лишь в случае ri < ri, а равенство ri = ri необходимо выполнено лишь при ri = ri = Ri. В остальных случаях, то есть если ri = ri < Ri может выполняться как строгое неравенство ri < ri, так и равенство ri = ri. Аналогично, неравенство f0 < f0 необходимо выполнено при f0 < f0, а равенство f0 = f0 необходимо выполнено при f0 = f0 = F0.

Обозначим Для незамкнутой автомагистрали множество C содержит индекс 1, если выполнены неравенs ства f0 < f0 и f0 + r1 < F1 :

При фиксированных входных потоках d, f1, множество положений равновесия в проекции на пространство n есть множество решений уравнения (2.2), таких, что для i U выполняется равенство ni = nu, для i C выполняется равенство ni = nc. Множество равновесий в пространстве n пусто, если хотя бы для одного i одновременно выполнены неравенства fi1 /pf > ri /pr и ri < ri = min{di, Ri }.

Теперь найдем решения уравнения (2.2) для каждой из двух моделей.

2.3.1 Решение уравнения для n в модели незамкнутой автомагистрали Решение системы уравнений при допустимых потоках со въездов, то есть если для всех i = 1,..., K выполнено неравенство fi Fi, приведено в работах [35; 36].

В систему (2.6) не включено уравнение на nK+1, поскольку (K + 1)-я ячейка предполагается незагруженной, и потому nK+1 = nu.

Положим i0 = 0. Введем множества индексов Если I =, то есть M = 0, то SM +1 = S1 = {1,..., K}.

Следующая теорема описывает структуру решения.

Теорема 2.1. Решения системы (2.6) на множествах индексов Sm определяются независимо, поэтому множество решений E представимо в виде декартова произведения где множество EM +1 состоит из единственного вектора, EM +1 = {(nuM,..., nu )}, а остальi K ные множества Em, m = 1,..., M, представляются в виде объединения где Эта теорема, как уже было сказано, доказана в работах [35; 36].

2.3.2 Решение уравнения для n в модели кольцевой автомагистрали Напомним, что индексы i, i ± K, i ± 2K и т. д. в модели кольцевой автомагистрали эквивалентны.

Решается система уравнений Обозначим, как и для незамкнутой автомагистрали, I = {i : fi = Fi }. Упорядочим индексы во множестве I по возрастанию: I = {i1,..., iM }, i1 < · · · < iM, при этом 0 M = |I| K.

Если I =, то положим i0 = im K и введем множества индексов Теорема 2.2. Множество решений E системы уравнений (2.7) имеет следующий вид.

Если I =, то множество E состоит всего из двух векторов: E = {nu, nc }.

Если же I =, то решения уравнения (2.7) на множествах индексов Sm определяются независимо, поэтому множества Em можно представить в виде где, как и в случае незамкнутой автомагистрали, Доказательство. Если fi = Fi, то уравнение fi = min{if vi ni, Fi, wi+1 (Ni+1 ni+1 )} эквивалентно системе неравенств Поскольку ni и ni+1 больше никакими уравнениями между собой не связаны, то решение, действительно, определяется независимо на каждом из множеств индексов Sm.

Несложно видеть, что если ni+1 = nu и fi < Fi, то nu < nc, и потому должно выполняться равенство ni = nu. Аналогично, если ni = nc и fi < Fi, то nc > nu, поэтому должно выполняться равенство ni+1 = nc. Следовательно, если ni = nu, im1 + 1 i im, всех j {i,..., im }. То есть, на множестве индексов Sm любое решение представимо в виде где im1 iu < ic im + 1, nu < ni < nc для iu < i < ic. Поскольку для всех i {im1 + 1,..., im 1} должно выполняться хотя бы одно из равенств ni = nu и ni+1 = nc, то ic iu 2, то есть либо ic = iu + 1, либо ic = iu + 2.

Мы только что доказали, что множество E, определенное в формулировке теоремы, содержит все решения системы (2.7). В том, что все векторы из множества E являются решениями системы (2.7), легко убедиться непосредственной проверкой.

2.4 Равновесные потоки со въездов Наконец, следует выяснить, для каких потоков со въездов проекция множества равновесий на пространство n не является пустым множеством.

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

Допустимый входной поток Утверждение 2.4. В модели незамкнутой автомагистрали если входной поток (f1, d) является допустимым, то единственный равновесный поток (f0, r) есть f0 = f0, r = r.

Доказательство. Пусть для некоторого равновесного потока ri < ri или f0 < f0. Пусть i наибольший индекс, для которого выполнено строгое неравенство ri < ri, или же i = 1, если r = r, f0 < f0. Поскольку входной поток является допустимым, то для рассматриваемого равновесного потока выполнены строгие неравенства fj < Fjd, fj1 + rj < Fjs для всех j = i,..., K + 1, поэтому fj < Fj, j = i,..., K. Отсюда следует, что, в обозначениях теоремы 2.1, SM +1 {i,..., K}, следовательно, ni = nu во всех положениях равновесия, соi ответствующих рассматриваемому потоку со въездов (f0, r). В то же время, i C, значит, ni = nc. Однако nu < nc, поскольку fi < Fi. Значит, проекция множества равновесий, соi i i ответствующих рассматриваемому потоку со въездов (f0, r), на пространство n есть пустое множество.

Недопустимый входной поток Для недопустимого входного потока (f1, d) обозначим Ясно, что в положении равновесия f f.

Для дальнейшего исследования нам потребуется следующая лемма.

Лемма 2.1. Если fi < fi, то fi < fid.

Доказательство. Для i = 0 утверждение очевидно и было пояснено ранее. Будем доказывать лемму для 1 i K + 1.

Ясно, что, поскольку fi < fi, то либо rj < rj для некоторого j i, либо f0 < f0. Пусть I наибольший из таких индексов j. Если rj = rj для всех j = 1,..., i и f0 < f0, то I = 1.

Для всех j = I,..., i выполнено неравенство fj < fj, потому что в противном случае было бы невозможно строгое неравенство fi < fi.

Из неравенства fI < fI FId следует неравенство fI1 + rI < FIs, а поскольку rI < rI, то I C, то есть nI = nc. Поскольку fj < fj Fjd для всех j = I,..., i, то fj1 + rj < Fjs, j = I,..., i, и, следовательно, fj < min{Fjd, Fj+1 rj+1 } = Fj для j = I,..., i 1, поэтому nj = nc также для j = I + 1,..., i. Следовательно, fI = min{I vI nc, FId } = FId fI > fI.

Из леммы 2.1 сразу же следует, что fK+1 = fK+1, поскольку (K + 1)-я ячейка является выездом и, следовательно, выполнено равенство fK+1 = fK+1.

Пусть теперь для некоторого i {1,..., K + 1} определен равновесный поток fi fi.

Покажем, что потоки fi1 и ri определяются однозначно.

Если fi = if (fi1 + ri ), то, разумеется, fi1 = fi1, ri = ri. Если же fi < if (fi1 + ri ), то выполнено по крайней мере одно из неравенств fi1 < fi1, ri < ri.

Если ri < ri, то ri < ri и выполнены случаи 2 или 4 и правила приоритетов, поэтому Если при этом fi1 = fi1, должно выполняться неравенство fi1 /pf ri /pr. Поскольку ri + fi1 = fi /if, то должно выполняться неравенство fi1 pf fi /if.

Если же ri < ri, fi1 < fi1, то, согласно утверждению 2.1, fi1 < fi1, поэтому должно выполняться равенство fi1 /pf = ri /pr, а поскольку ri + fi1 = fi /if, то в этом случае выполнены неравенства fi1 > pf fi /if, ri > pr fi /if.

Наконец, если ri = ri, fi1 < fi1, должны выполняться случаи 3 или 4 из правил приоритета, поэтому fi1 /pf ri /pr = ri /pr. Поскольку ri + fi1 = fi /if, то в этом случае должно выполняться неравенство ri pr fi /if.

Сформулируем только что обоснованный алгоритм определения равновесных потоков в виде теоремы.

Теорема 2.3. В модели незамкнутой автомагистрали равновесные потоки со въездов (f0, r) и, следовательно, потоки между ячейками fi, i = 1,..., K, единственны и определяются по следующему правилу.

Вычисляются максимальные потоки между ячейками fi, i = 1,..., K, а также максимальный исходящий поток из последней ячейки fK+1 :

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

1. Если fi1 pf fi /if, то fi1 = fi1, ri = fi /if fi1.

3. Если же fi1 > pf fi /if и ri > pr fi /if, то fi1 = pf fi /if, ri = pr fi /if.

Завершим этот раздел описанием множества равновесий в модели незамкнутой автомагистрали.

После того, как найдены потоки r и f, определяются множество U по формуле (2.3), множество C по формуле (2.5) и множество I = {i K : fi = Fid или fi + ri+1 = Fi+1 }.

Индексы из множества I упорядочиваются по возрастанию, I = {i1,..., iM }, i1 <..., iM, и определяются множества где i0 = 0. Если I =, то M = 0 и SM +1 = {1,..., K + 1}. Множество положений равновесия а множества Em, m = 1,..., M определяются согласно следующему правилу.

Вычисляются индексы Если ic iu = 1, то 2.4.2 Равновесные потоки в модели кольцевой автомагистрали Множество равновесных потоков в модели кольцевой автомагистрали состоит из двух частей. Опишем каждую из двух частей отдельно.

Первая часть множества равновесий В первой части множества равновесий выполнены равенства r = r, если входной поток является допустимым, и fi = Fid для некоторого i, если входной поток не является строго допустимым.

Если входной поток является допустимым, то этим условиям соответствует поток со въездов r = r и поток между ячейками f = f (). При этом C =, поэтому в проекции на пространство n множество положений равновесия для потока со въездов r = r содержит по крайней мере один вектор, а именно nu.

Запись E|r обозначает равновесное множество в пространстве n при заданном потоке со въездов r.

Строго допустимый входной поток Если входной поток строго допустимый, то Допустимый, но не строго допустимый входной поток Если входной поток допустимый, но не строго допустимый, определяем множество Sm как в теореме 2.2 и множество U по формуле (2.3). Для всех m = 1,..., M определяем множества Em определены в теореме 2.2.

Недопустимый входной поток Пусть фиксирован поток f0 или, что то же, fK, Определим максимальные потоки f0 = f0, Ясно, что f0 может быть компонентой равновесного потока, лишь если fK f0.

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

Лемма 2.2. Если для некоторого i {1,..., K} выполнено неравенство fi < fi, то выполнено также неравенство fi < fid.

Доказательство этой леммы аналогично доказательству леммы 2.1.

С учетом леммы 2.2, равновесные потоки f1,..., fK1 однозначно определяются потоком fK = f0, а именно, для известного потока fi, i > 1, потоки fi1 и ri вычисляются по такому же правилу, как и в модели незамкнутой автомагистрали:

1. Если fi1 pf fi /if, то fi1 = fi1, ri = fi /if fi1.

3. Если же fi1 > pf fi /if и ri > pr fi /if, то fi1 = pf fi /if, ri = pr fi /if.

Если f0 + r1 = f1 /1, то f0 = f0, r1 = r1. Если же f0 + r1 < f1 /1, то, поскольку f0 = f0, выполнено неравенство r1 < r1, следовательно, f0 /pf r1 /pr, откуда f0 pf f1 /1. В обоих случаях f0 и r1 должны определяться из f1 по общему правилу (то есть, по тому же правилу, по которому fi1 и ri определяются из fi для i > 1), только в этом случае поток f может быть равновесным.

Фактически, мы доказали следующее утверждение.

Утверждение 2.5. Равновесный поток f в модели кольцевой автомагистрали однозначно определяется любой своей компонентой: например, по компоненте fK все остальные компоненты fi, i = 1,..., K 1 восстанавливаются однозначно.

Ясно, что величины fi монотонно не убывают как функции fK, то же самое можно сказать о величинах fi, i = 0,..., K 1. Вместе с утверждением 2.5 это приводит нас к следующему результату.

Утверждение 2.6. В модели кольцевой автомагистрали при недопустимом входном потоке существует не более одного равновесного потока со въездов r, для которого fi (r) = Fid по крайней мере для одного i.

Доказательство. Пусть существует два различных равновесных потока f 1, f 2 с указанным свойством. Поскольку любая компонента определяет весь равновесный поток (утверждение 2.5), то потоки f 1 и f 2 не совпадают ни в одной компоненте. Значит, существуют индексы i1 = i2, такие, что fi1 = Fid > fi2, fi2 = fid > fi1. Но это противоречит тому, что при увеличении одной компоненты равновесного потока остальные компоненты не уменьшатся.

Этот равновесный поток можно найти, отыскав значение потока fK [0, FK ], такое, что вычисленный согласно общему правилу поток f0 совпадает с заданным потоком fK, и хотя бы для одного i выполнено равенство fi = Fid.

После того, как найден равновесный поток с заданными свойствами, если он вообще существует, определяются множества I, Sm как в теореме 2.2, U и C по формулам (2.3), (2.4), индексы iu, ic как в модели незамкнутой автомагистрали. Множество равновесий в пространстве n, как и прежде, представляется в виде декартова произведения E = Em.

Если ic iu = 1, то Вторая часть множества равновесий Во второй части множества равновесий для равF d.

новесных потоков справедливы неравенства r < r, f Поскольку f входных потоков r и потоков между ячейками f, согласно теореме 2.2, может состоять лишь из векторов nu и nc, а поскольку для всех i выполнено неравенство fi1 + ri < Fis, следующее из неравенства fi < Fid, и r < r, то C =, поэтому множество E|r, если оно не пустое, состоит из единственного вектора: E|r = {nc }.

Множество E|r не пустое, если U =, то есть для всех i должно выполняться неравенство fi1 /pf ri /pr, которое, с учетом равенства fi1 +ri = fi /if, равносильно неравенству fi1 pf fi /if. При этом для участков без въезда, то есть для таких i, что ri = 0, неравенi ство fi1 /pf ri /pr выполнено автоматически.

Заметим, что второй части множества равновесий в любом случае принадлежит точка r = 0, f = 0, n = nc = 0. Есть ли во второй части множества равновесий другие точки, зависит от величины А именно, справедливы следующие три утверждения.

Утверждение 2.7. Если > 1, то, кроме r = 0, f = 0, других равновесных потоков во второй части множества равновесий нет.

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

Поскольку fi1 = fi /if, если ri = 0, и fi1 pf fi /if, если ri > 0, то Поскольку fK > 0, то 1. Отсюда следует, что при > 1 вторая часть множества равновесий не содержит ненулевых равновесных потоков.

Утверждение 2.8. Если = 1, то множество равновесных потоков во второй части множества равновесий есть однопараметрическое семейство 0 max, где max = max{ : r() r, f () F d }. Причем если r(max ) = r или хотя бы для одного i выполнено равенство fi (max ) = Fid, то 0 < max, поскольку потоки r(max ) и f (max ) принадлежат первой части множества равновесий.

fi1 pf fi /if, если ri > 0. Обозначим Тогда поэтому все неравенства должны выполняться как равенства: fi1 = i fi /if, или Ясно поэтому, что множество равновесных потоков есть однопараметрическое семейство r(), f (), описанное в формулировке утверждения, = f0 = fK.

Утверждение 2.9. Если < 1, то во второй части множества равновесий не более двух равновесных потоков, один из которых нулевой (r = 0, f = 0), а второй определяется следующим образом. Определим функцию () = f0 (), где fK () =, Уравнение () = имеет ровно два решения, одно из которых = 0, а второе > 0.

Если для всех i = 1,..., K выполнено строгое неравенство fi ( ) < Fid, то второй ненулевой равновесный поток из второй части есть f ( ), в противном случае вторая часть множества равновесий содержит лишь нулевой равновесный поток.

Доказательство. Во второй части множества равновесий в модели кольцевой автомагистраF d, n = nc, поэтому fi < fid для всех i. Если ri < ri, то ri < ri и fi1 /pf = ri /pr, поэтому Если же ri = ri, то fi1 = fi /if ri и выполняется неравенство fi1 /pf ri /pr, поэтому fi1 pf fi /if. В обоих случаях Положим fK =. Тогда потоки fK1,..., f1, а также f0 определяются однозначно по формуле (2.8). Для того, чтобы f был равновесным потоком, необходимо и достаточно, чтобы выполнялось равенство f0 = fK и неравенства fi Fid, i = 1,..., K. При этом ri = fi /if fi [0, ri ].

Условие f0 = fK приводит к уравнению () = из формулировки доказываемого утверждения. Ясно, что нуль является корнем этого уравнения. Функция () есть максимум из 2K линейных по выражений, следовательно, функция (·) непрерывная и выпуклая.

При малых значениях, начиная с нуля, () =, поэтому производная функции () меньше единицы: () = < 1. При очень больших значениях производная функции () потоком из второй части множества равновесий, если же f ( ) F d, и при этом хотя бы для одного i выполнено равенство fi ( ) = Fid, то f ( ) равновесный поток для первой части множества равновесий.

2.5 Об устойчивости равновесий Поскольку длина очереди q не входит в определение равновесия, необходимо определить, что мы понимаем под устойчивым и неустойчивым равновесием. Для этого наложим некоторые ограничения на значения q в начальный момент времени.

Пусть в начальный момент времени t = 0 в очереди перед каждым въездом i есть столько автомобилей, что ri (0) = ri : если ri < Ri, то qi (0) = ri /vi, если же ri = Ri, то qi (0) Ri /vi. Величина n0 в модели незамкнутой автомагистрали также считается длиной очереди, и для нее в начальный момент должно выполняться аналогичное условие, f0 (0) = f0, здесь и дальше это специально не оговаривается. При таких ограничениях на длину очереди в начальный момент выполнено неравенство q(t) q(0) и, следовательно, ri (t) ri для всех t. Действительно, если ri < Ri, то di = ri, и если qi (t) qi (0) = ri /vi, то Если же ri = Ri, то di Ri, и если qi (t) qi (0) Ri /vi, то Кроме того, если тройка (f, r, n) является равновесием и в начальный момент выполнено равенство rd (0) = r, то f (t) = f, r(t) = r, n(t) = n для всех t = 1, 2,.... Таким образом, вектор n (в случае незамкнутой автомагистрали вектор n не включает компоненту n0, то есть n = (n1,..., nK+1 )) однозначно определяет равновесные потоки f, r. Действительно, если в равновесии ri = ri, то в равновесии ri = ri. Если же в равновесии ri < ri = ri (0), то в равновесии ri = Ri. Согласно модели узла, если ri (t) < ri (t), то при увеличении ri (t) величина ri (t) не изменится. Поэтому имеют смысл следующие определения.

Пусть ne равновесный вектор концентраций. Вектор ne назовем устойчивым равновесием, если для любого сколь угодно малого > 0 найдется > 0, такое, что при n(0) ne и rd (0) = r выполнено неравенство n(t) ne для всех t = 1, 2,....

Вектор ne назовем асимптотически устойчивым равновесием, если он является устойчивым равновесием и для некоторого > 0 n(t) ne при t при любом значении n(0) из -окрестности вектора ne.

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

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

2.5.1 Устойчивость наименее загруженного равновесия Исследуем устойчивость равновесия n = nu в модели обычной и кольцевой автострады.

Утверждение 2.10. Если равновесный поток f устойчиво как в модели незамкнутой автострады, так и в модели кольцевой автострады.

Доказательство. Если f точке n = nu и в небольшой ее окрестности выполнены равенства fi = if vi ni, ri = ri = ri для всех i.

Поэтому если n(t) находится в небольшой окрестности точки nu и rd (t) = r (и f0 (t) = f в случае незамкнутой автострады), то rd (t + 1) = r и f0 (t + 1) = f0 в модели незамкнутой автострады.

Следовательно, n(t + 1) nu = A(n(t) nu ), где в модели кольцевой автострады. В модели незамкнутой автострады n(t) обозначает вектор (n1 (t), · · ·, nK (t)), n(t + 1) nu = A(n(t) nu ), матрица A такая же, как в модели кольцевой автомагистрали, но правый верхний элемент a1K = 0, то есть матрица A нижнетреугольная.

Как в модели незамкнутой автострады, так и в модели кольцевой автострады операx1 | + · · · + |xK |. Действительно, в обоих случаях 2.5.2 Устойчивость наиболее загруженного положения равновесия в модели кольцевой автострады Будем исследовать устойчивость наиболее загруженного положения равновесия в модели кольцевой автомагистрали, а именно, f = 0, r = 0, n = N.

Величина определяет устойчивость положения равновесия f = 0, r = 0, n = N.

А именно, имеет место следующее утверждение.

Утверждение 2.11. Положение равновесия f = 0, r = 0, n = N устойчиво, если и только если 1, и асимптотически устойчиво, если и только если < 1.

Доказательство. В окрестности положения равновесия f = 0, r = 0, n = N состояние системы на шаге t + 1 зависит от состояния системы на шаге t линейно:

то есть (t + 1) = A(t), где Все элементы матрицы A неотрицательны.

Если = 0, то i = 0 по крайней мере для одного i. Пусть, например, K = 0. Тогда матрица A верхнетреугольная, на главной диагонали стоят числа 1 wi (0, 1), следовательно, At 0 при t, следовательно, (t) 0 при t для любого значения (0), то есть положение равновесия = 0 (n = N ) асимптотически устойчиво. Действительно, рассмотрим матрицы D = diag(1 w1,..., 1 wK ), S = A D. Матрица S верхнетреугольная, с нулями на главной диагонали, следовательно, S K = 0. Поэтому при t > K, t N где Ctk биномиальный коэффициент:

Далее, tk Dtk 0 при t, поскольку Dtk = diag((1w1 )tk,..., (1wK )tk ) и tk xtk при t, если |x| < 1. Следовательно, At 0 при t.

Пусть > 0. Тогда матрица A является неразложимой, и к ней можно применить теорему Фробениуса Перрона (см. [44], глава XIII): существует положительное собственное значение матрицы A, такое, что все остальные собственные значения матрицы A не превосходят его по модулю, этому собственному значению соответствует собственный вектор с положительными компонентами.

Рассмотрим характеристический многочлен матрицы A Максимальное по модулю положительное собственное значение матрицы A является наибольшим корнем характеристического многочлена A (). Заметим, что функция A () монотонно возрастает при 1 mini wi, и A () + при +. Следовательно, для максимального корня характеристического многочлена A () выполнены следующие условия:

Кроме того, собственному значению соответствует собственный вектор с положительными компонентами. Отсюда сразу же следует, что при > 1 положение равновесия = (n = N ) неустойчиво. Если же 1, то для любого (0), 0 (0), справедливо неравенство 0 (t) ( )t. Следовательно, положение равновесия = 0 (n = N ) устойчиво при 1 и асимптотически устойчиво при < 1.

2.5.3 Устойчивость произвольного положения равновесия В силу монотонности системы (лемма 1.1), для выяснения устойчивости любого положения равновесия ne необходимо проверить лишь точки n ne и n ne.

Лемма 2.3. Для любого положения равновесия ne вектор n(t + 1) зависит от n(t) линейно в областях {n ne } { n ne < }, {n ne } { n ne < } для некоторого малого > 0.

Точнее, n(t + 1) ne = A+ (n(t) ne ), если n ne, n ne <, и n(t + 1) ne = A (n(t) ne ), Доказательство. Пусть f e, re равновесные потоки, соответствующие равновесию ne.

берем из следующих соображений. В любом случае, Ni ne. Если ne < Ni Fis /wi, то поэтому по-прежнему выполнено неравенство fis (n) > fi1 (n) + ri.

Если же, напротив, fis (ne ) fi1 (n) + ri, условия на следующие. Если ri < pr fis (ne ), то тогда в рассматриваемой области выполняется равенство ri (t) = ri при ri (0) = ri. Если fi1 (ne ) < pf fis (ne ), то тогда fi1 (t) = fi1 (t).

При указанных ограничениях на потоки f (t), r(t) в области {n ne } { n ne < } определяются следующим образом.

1. Если fis (ne ) fi1 (ne ) + ri, то Поток fi1 (t) определяется следующим образом.

2. Если же fis (ne ) > fi1 (ne ) + ri, то ri (t) = ri, Поскольку потоки f (t), r(t) зависят от n(t) линейно, то и n(t+1) зависит от n(t) линейно, поэтому n(t + 1) ne = A+ (n(t) ne ), где A = {a+ }j=1,...,K a+ = 0, если |i j| > 1 (в модели кольцевой магистрали элементы aK1 и a1K могут быть ненулевыми), В модели кольцевой автострады aK1 и a1K определяются по формулам для ai,i+1 и ai,i1.

В любом случае, ni для всех i. Если if vi ne > Fid, то ne Fid (if vi ). Если При этом fi1 (t) + ri (t) = fis (t). Если ri > pr fis (ne ), то ne (Ni ri /(pr wi )). Если fi1 (ne ) > pf fis (ne ), то При таких ограничениях на потоки f (t), r(t) в области {n ne } { n ne < } определяются по следующему правилу.

1. Если fi1 (ne ) + ri > fis (ne ), то Поток fi1 (t) определяется следующим образом.

2. Если fi1 (ne ) + ri fis (ne ), ri (t) = ri, то ri (t) = ri, Потоки f (t) и r(t) зависят от n(t) линейно, поэтому n(t + 1) ne = A (n(t) ne ). Элементы матрицы A определяются так же, как элементы матрицы A+, но в формулах (2.9) все строгие неравенства следует заменить на нестрогие и наоборот.

Положение равновесия ne устойчиво в том и только в том случае, если все элементы матриц (A± )t равномерно ограничены для всех t = 1, 2,..., и асимптотически устойчиво, если (A± )t 0 при t. Эти условия равносильны следующим. Положение равновесия ne устойчиво, если и только если все собственные значения матриц A± по модулю не превосходят 1, а собственным значениям, равным по модулю 1, соответствует ровно столько собственных векторов, какова их кратность. Положение равновесия ne является асимптотически устойчивым, если все собственные значения матриц A± по модулю строго меньше 1.

Из леммы 2.3, а именно, из вида матриц A±, вытекают следующие факты, справедливые как для матрицы A+ (все знаки ± заменяются на + ), так и для матрицы A (все знаки ± заменяются на ).

1 wi+1. Следовательно, если a± = 1, то a± = a± = 0.

Утверждение 2.13. Для каждого i по крайней мере одна из двух величин a±, a± равна нулю.

2.5.3.1 Устойчивость равновесий в модели незамкнутой автострады Используя утверждения 2.12, 2.13, можно сразу же показать, что все положения равновесия в модели незамкнутой автострады являются устойчивыми, но не все асимптотически устойчивыми.

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

Доказательство. Покажем, что для любого положения равновесия диагональные элементы матриц A+ и A, и только они, являются собственными значениями.

Рассмотрим, к примеру, матрицу EA+ (для матрицы A+ доказательство аналогично).

В модели незамкнутой автострады a+ = 0, j = K, j = K 1 и a+ = 0, i = K, i = K 1. Кроме того, согласно утверждению 2.13, по крайней мере одна из величин a+ K1,K равна нулю. Следовательно, ( aKK ) единственный ненулевой элемент матрицы (E A+ ) или в своей строке, или в своем столбце. Следовательно, det(E A+ ) = K = ( a+ )K1, где i определитель матрицы, стоящей на пересечении первых i строк и i столбцов матрицы (E A+ ). Как и для минора K, несложно показать, что i = ( образом, диагональные элементы матрицы A+, и только они, являются ее собственными значениями.

Все диагональные элементы матрицы A+ положительны и не превосходят единицы.

Диагональным элементам, равным единице, a+ = 1, соответствуют собственные векторы (0,..., 0, 1, 0,..., 0), где единственный ненулевой элемент стоит в i-й позиции. Действительно, если a+ = 1, то, согласно утверждению 2.12, a+ + i-го столбца матрицы A+, кроме a+, нулевые, поскольку матрица A+ трехдиагональная.

Таким образом, собственному значению 1 матрицы A+ соответствует ровно столько линейно независимых собственных векторов, какова его кратность.

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

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

Вспомним, что множество равновесий в модели незамкнутой автострады представляет собою односвязное множество. То есть, если множество равновесий содержит более одной точки, то в окрестности каждого равновесия есть другие равновесия, поэтому ни одно равновесие не является асимптотически устойчивым. Таким образом, равновесие может быть асимптотически устойчивым, только если оно единственно. С другой стороны, собственные значения матриц A±, соответствующих единственному равновесию ne, по модулю строго меньше 1. Действительно, пусть, например, у матрицы A+ есть собственное значение 1. Как уже было показано, ему соответствует собственный вектор вида = (0,..., 0, 1, 0,..., 0).

Тогда для некоторого малого положительного вектор ne + также является равновесием.

Таким образом, справедлива следующая теорема.

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

2.5.3.2 Устойчивость равновесий в модели кольцевой автострады Квадратную матрицу A назовем устойчивой, если все ее собственные значения по модулю не превосходят единицы, а собственным значениям, по модулю равным единице, соответствует ровно столько линейно независимых собственных векторов, какова кратность этих собственных значений. Квадратную матрицу A назовем асимптотически устойчивой, если все ее собственные значения по модулю строго меньше единицы.

В дальнейшем, если утверждение формулируется для матрицы A = {aij }j=1,...,K, то имеется ввиду как матрица A+, так и матрица A. Для напоминания будем обозначать это так: A = A±.

Лемма 2.4. Пусть aij = 0 для некоторого i и для всех j = i, то есть aii единственный ненулевой элемент в своем столбце. Тогда диагональные элементы матрицы A = A±, и только они, являются ее собственными значениями, и матрица A является устойчивой.

При этом матрица A является асимптотически устойчивой, если все ее диагональные элементы строго меньше единицы.

Доказательство. Пусть, к примеру, aKK единственный ненулевой элемент в своем столбце (в общем случае этого можно добиться сдвигом индексов). Как в доказательстве теоремы 2.4, можно показать, что определитель матрицы E A равен произведению ее диагональных элементов, поэтому диагональные элементы матрицы A, и только они, являются собственными значениями этой матрицы. При этом диагональные элементы, равные 1, являются единственными ненулевыми элементами в своем столбце, и им соответствуют линейно независимые собственные вектора вида (0,..., 0, 1, 0,..., 0).

Следовательно, матрица A является устойчивой. Асимптотически устойчивой матрица A является лишь в том случае, если все ее диагональные элементы строго меньше 1.

Пусть для любого i один из элементов ai1,i, ai+1,i не равен нулю. Пусть, например, aK1,K = 0. Согласно утверждению 2.13, aK,K1 = 0, значит, при i = K 1, aK2,K1 = 0.

Рассуждая таким образом, мы придем к тому, что ai1,i = 0, ai+1,i = 0 для всех i. Аналогично, если a2,1 = 0, то a1,2 = 0, потому, при i = 2, a3,2 = 0, и так далее: ai+1,i = 0, ai1,i = 0.

То есть, если в каждом столбце матрицы A по крайней мере два ненулевых элемента, то ненулевыми являются (а) либо главная диагональ, и диагональ снизу под главной, а также элемент a1,K, и в этом случае ai,i1 = i1 vi1, aii = 1 vi. Либо (б) не нулевые лишь главная диагональ, диагональ сверху от главной, и элемент aK,1. В этом случае ai,i+1 = wi+1 /if или ai,i+1 = pf wi+1 /if, aii = 1 wi.

Случай (а) разобран в доказательстве утверждения 2.10. Матрица A в этом случае устойчивая. Более того, несложно показать, что матрица A асимптотически устойчивая. Это можно доказать, например, используя теорему Фробениуса Перрона.

Случай (б), фактически, разобран в доказательстве утверждения 2.11. Устойчивость матрицы A в этом случае зависит от величины А именно, матрица A является устойчивой, если и только если (A) 1, и асимптотически устойчивой, если (A) < 1.

Таким образом, справедлива следующая теорема.

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

В частности, если в положении равновесия ne хотя бы для одного i справедливо неравенство ne < Ni Fis /wi, то это положение равновесия является устойчивым.

2.6 Примеры Примеры, как и в предыдущей главе, будут для незамкнутой и кольцевой автомагистрали с двумя основными ячейками, K = 2. Схемы таких автомагистралей приведены на рис. 1.7 на стр. 30.

Расчеты к примерам в этой и в следующей главе выполнены с помощью программы [45].

Незамкнутая автомагистраль На рис. 2.1 приведены проекции траекторий системы на пространство (n1, n2 ) плотностей в основных ячейках автомагистрали, широкими линиями и небольшими незакрашенными кругами выделены точки множества равновесия.

(в) Недопустимый входной поток, (г) Недопустимый входной поток, Рис. 2.1. Траектории системы и положения равновесия в модели незамкнутой автострады Все траектории начинаются на границе прямоугольника 0 ni Ni, i = 1, 2. В начальный момент времени число автомобилей на въездах таково, что выполнены равенства f0 (0) = f0, ri (0) = ri, i = 1, 2.

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

Отметим, что в модели незамкнутой автомагистрали с двумя основными ячейками выполнено равенство f2 = f2, если, конечно, в третьей ячейке нет сужения, то есть F3 F2.

Для строго допустимого входного потока fi = fi F1, i = 1, 2, для любого допустимого потока fi = fi Fid, i = 1, 2.

В примерах на рис. 2.1 коэффициенты приоритета пропорциональны пропускным способностям. Посмотрим, как зависит множество равновесий и траектории системы от коэффициентов приоритета (рис. 2.2). Рассмотрим два крайних случая: нулевые приоритеты въездов (рис. 2.2а) и нулевые приоритеты основных ячеек автомагистрали (рис. 2.2б). Входной поток недопустимый, f1 = F1, f2 = F2, сужений нет, F1 = F2 = F3. Если у въездов нулевые приоритеты, pr = 0, i = 1, 2, то fi = fi, i = 1, 2, если же нулевые приоритеты у основных ячеек, Рис. 2.2. Влияние коэффициентов приоритета на траектории системы и равновесия Кольцевая автомагистраль На рис. 2.3 представлены примеры траекторий системы и множеств положений равновесия в модели кольцевой автомагистрали с двумя ячейками. При < 1 положение равновесия n = N асимптотически устойчиво, при > 1 неустойчиво. При = 1 множество равновесий содержит отрезок, начинающийся в точке n = N (см. утверждение 2.8).

(а) Строго допустимый входной поток, < 1 (б) Недопустимый входной поток, < (в) Строго допустимый входной поток, = 1 (г) Недопустимый входной поток, = (д) Строго допустимый входной поток, > 1 (е) Недопустимый входной поток, > Рис. 2.3. Траектории системы и равновесия в модели кольцевой автострады Глава Управление состоянием автомагистрали при помощи выделенных полос В этой главе представлена модель автомагистрали с выделенными полосами. Предлагается алгоритм управления коэффициентами расщепления потоков в узлах посредством изменения стоимости въезда в платные полосы, поддерживающий выделенные полосы в состоянии свободного движения, насколько это возможно при условии максимального использования пропускной способности выделенных полос. При построении управления существенно используются результаты первых двух глав, касающиеся пропускной способности автострады и структуры множества равновесий.

3.1 Модель автомагистрали с выделенными полосами Модифицируем модель автомагистрали из § 1.2. В каждой ячейке есть l1 выделенных и l2 обычных полос. Параметры и переменные, относящиеся к выделенным полосам, обозначаются верхним индексом = 1, а относящиеся к обычным полосам верхним индексом = 2.

Схема модели автомагистрали с выделенными полосами приведена на рисунке 3. Рис. 3.1. Схема модели автомагистрали с выделенными полосами Пропускные способности Fi, вместимости Ni, коэффициенты приоритетов p, пропускi ные способности выездов Si, и, следовательно, пропускные способности Fi,d, Fi,s, = 1, 2, пропорциональны числу выделенных и обычных полос в ячейке: Fi = Fi l /(l1 + l2 ), = 1, 2, Ni = Ni l /(l1 + l2 ), = 1, 2, и так далее.

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

Рис. 3.2. Схема узла в модели автомагистрали с выделенными полосами Требуемые исходящие и допустимые входящие потоки определяются как в модели автомагистрали без выделенных полос:

Водители могут выбрать выделенные или обычные полосы только в момент въезда на автомагистраль. Управление устанавливает стоимость въезда на платные полосы для каждого въезда. Для некоторых категорий транспортных средств (например, общественный транспорт или автомобили с несколькими пассажирами) стоимость въезда на выделенные полосы может быть снижена вплоть до нуля. Выбор водителя зависит от текущего состояния выделенных и обычных полос, от стоимости въезда на выделенные полосы, а также от цены времени для конкретного водителя. Об этом речь пойдет позже. Управление, таким образом, на каждом шаге определяет коэффициенты расцепления i, i для потока со въездов. Разумеется, i, i 0, i + i = 1. Стоимость въезда на платные полосы может быть ограничена как снизу (например, условие неотрицательности), так и сверху (задана максимальная стоимость въезда в платные полосы). Пусть Bi множество пар коэффициентов расщепления (i, i ), соответствующих допустимым ценам въезда на выделенные полосы в узле i.