Модель Нестерова-де Пальмы и ее применение в задачах макроскопического моделирования транспортаных потоков тема диссертации и автореферата по ВАК РФ 00.00.00, кандидат наук Дорн Юрий Владимирович

• Дорн Юрий Владимирович
• кандидат наук
• 2022

Оглавление диссертации кандидат наук Дорн Юрий Владимирович

Введение

Глава 1. Равновесные транспортные модели

1.1 Обозначения

1.2 Мотивация: Многостадийные транспортные модели

1.3 Модель Бекмана

1.4 Модель стабильной динамики Нестерова-де Пальмы

1.5 Сведение модели Бекмана к модели Нестерова-де Пальмы

Глава 2. Алгоритмы расчета равновесной загрузки сети

2.1 Введение

2.2 Обзор алгоритмов для расчета транспортного равновесия

2.2.1 Маршрутные и дуговые алгоритмы

2.2.2 Алгоритм постепенного заполнения сети

2.2.3 Метод последовательных усреднений

2.2.4 Алгоритм Франка-Вульфа

2.2.5 Проективные методы для вариационных неравенств

2.3 Алгоритмы для расчета равновесия в модели стабильной динамики

2.3.1 Метод потенциалов

2.3.2 Альтернативные постановки

2.3.3 Сглаживание целевой функции

2.3.4 Прямо-двойственный метод двойственного усреднения

для расчета равновесия

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

2.4 Результаты численных экспериментов

2.5 Популяционные динамики, сходящиеся к равновесию

Глава 3. Задача о поиске неэффективных ребер в транспортной

сети

3.1 Введение

3.2 Парадокс Браесса

3.2.1 Поиск оптимальной конфигурации сети является

КР-трудной задачей

3.3 Цена анархии

3.4 Постановка задачи

3.5 О некоторых свойствах равновесия Нэша-Вардропа в модели Нестерова-де Пальмы

3.6 Условия единственности равновесия в модели стабильной динамики

3.7 Алгоритм расчета равновесия

3.8 Поиск неэффективных ребер

3.9 Примеры

3.10 Обсуждение

3.11 Платные дороги

Глава 4. Модель с застройщиками

4.1 Введение

4.1.1 Транспортные макромодели: Мотивация

4.1.2 Модели расчета матриц корреспонденций и многостадийные модели

4.1.3 Гравитационная модель

4.1.4 Энтропийная модель

4.2 Расширение модели стабильной динамики

4.3 Алгоритмическая модель с застройщиками

Заключение

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

Список рисунков

Приложение А. Листинг кода для расчета равновесной

загрузки сети с помощью покоординатного спуска для сглаженной модели

Введение

Актуальность темы.

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

Транспортные макроскопические модели, использующие понятие равновесия, впервые появились в начале двадцатого века в работах профессора Пи-гу. Широкое развитие данное направление получило в 50-х годах после работы Вардропа, в которой были сформулированы основные принципы поведения водителей, ставшие базой для построения моделей, а также работы Бекмана, МакГваера и Винстона, в которой была предложена транспортная макроскопическая модель и подходы для ее численного расчета. Было показано, что задача поиска равновесия в такой модели может быть сведена к решению задачи выпуклого программирования. Эта модель до сих пор используется в программных продуктах для транспортного моделирования и практически не испытывает конкуренции, хотя и имеет несколько недостатков, в том числе не позволяет идентифицировать заторы в сети. В 2003 году Нестеровым и де Пальмой была предложена альтернативная модель для описания транспортного равновесия, в которой заторы можно идентифицировать. Данная диссертация в большей степени содержит исследование именно данной модели и ее приложения для решения целого ряда задач, которые возникают в практике транспортного моделирования.

Активное исследование макроскопических равновесных транспортных моделей ведется с 60-х годов и достигло пика в 70-х - 80-х годах. Не смотря на то, что подходы для расчета равновесия были описаны в работе Бекмана с соавторами, первые реальные алгоритмы для решения задачи оптимизации, к которой сводилась задача поиска равновесия, появились лишь в 70-х годах и основывались на алгоритме Франка-Вульфа. Вариации алгоритма Франка-Вульфа и сейчас являются основным средством для расчета транспортного равновесия в профессиональных программных пакетах. Для модели Нестерова-де Паль-

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

В дальнейшем, при практическом использовании, модели транспортного равновесия, модели для расчета матрицы корреспонденции и модели дискретного выбора (типа передвижения) интегрировались между собой в одну. Такие интегрированные модели называются многостадийными. В них реализована итерационная схема, в которой последовательно расчитываются матрица корреспонденций, распределение корреспонденций по типам передвижений, поиск равновесной загрузки сети. Практически все реальные расчеты городских транспортных систем основаны на использовании таких многостадийных моделей. Как правило, в результатах такого моделирования заинтересованы не только и не столько службы, отвечающие за текущее функционирование транспортной системы, сколько департаменты, занимающиеся долгосрочным планированием городского развития. В частности, организации, занимающиеся разработкой Генерального плана города, в котором, помимо прочего, определяется план его дальнейшей застройки и развития инфраструктуры. Для таких организаций важно, чтобы используемая модель не только описывала функционирование транспортной системы, но и учитывала взаимосвязь между транспортной системой и дальнейшей застройкой города. Насколько нам известно, эффективно вычислимых моделей, в которых совмещаются многостадийные модели и модели землепользования сейчас нет, хотя такие проектные институты, как "НИ и ПИ Генплана Москвы"и испытывают острую необходимость в таких моделях.

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

могло быть внедрено в практику - платы нужно было вводить на ребрах. Для модели Бекмана эта задача была решена в 90-х годах.

Еще одна задача - задача поиска неэффективных ребер в транспортном графе, встала перед исследователями в 1968 году после работы немецкого математика Дитриха Браесса. В своей работе Браесс показал, что удаление ребра в транспортном графе может привести к снижению издержек для всех водителей. Другими словами было показано, что равновесие Нэша не обязательно является эффективным по Парето. Достаточно долгое время многие авторы в контексте модели Бекмана занимались исследованием задачи поиска неэффективных ребер в транспортном графе, пока в 2006 году Роугарден не показал, что эффективного алгоритма поиска неэффективных ребер в контексте модели Бекмана не существует. Однако при менее строгих требованиях, как было показано Спиракисом и его соавторами, можно получить нетривиальные результаты. Представляется актуальным исследование задачи о поиске неэффективных ребер в транспортном графе в рамках модели Нестерова-де Пальма.

Введение диссертации (часть автореферата) на тему «Модель Нестерова-де Пальмы и ее применение в задачах макроскопического моделирования транспортаных потоков»

Цель работы.

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

Для достижения поставленной задачи решаются следующие задачи:

1. Исследование связи между моделями Нестерова-де Пальмы и модели Бекмана равновесного распределения потоков по маршрутам.

2. Поиск эффективных алгоритмов расчета равновесия в модели Нестерова-де Пальма с учетом огромной размерности задачи.

3. Определение оптимальных цен для платных дорог в модели Нестерова-де Пальма.

4. Разработка эвристического алгоритма поиска неэффективных ребер в транспортном графе в модели Нестерова-де Пальма и его обоснование.

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

Общая методика исследования.

В первой главе вводятся модели равновесного распределения потоков по маршрутам Бекмана и Нестерова-де Пальма. Приводится теоретико-игровое

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

Для обоснования сведения задачи поиска равновесия к задаче выпуклого программирования показано, что задача поиска равновесного распределения потоков по маршрутам может быть представлена как задача поиска равновесия в потенциальной игре (Розенталь, Мондерер и Шапли). Процесс "нащупы-вания"экстремума потенциальной функции игры может рассматриваться как процесс поиска точки оптимума для функции Ляпунова системы (см., например, Б.Т. Поляк, 1983).

Во второй главе исследуются алгоритмы для поиска равновесия. Сначала приводится обзор алгоритмов, применяемых для модели Бекмана. Как правило, большая часть алгоритмов является вариацией алгоритма Франка-Вульфа, или, что то же самое, метода условного градиента для потенциальной функции.

Далее исследуется задача поиска равновесия в модели Нестерова-де Пальма. Показано, что задача выпуклого программирования, к которой сводится задача поиска равновесия имеет два других представления, а именно в виде задачи линейного программирования и задачи безусловной минимизации выпуклой негладкой функции. Исходная задача являлась задачей минимизации негладкой выпуклой функции на множестве простой структуры. Для анализа сложности задачи можно применить методологию общей теории сложности (Немировский-Юдин).

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

координатного спуска для сглаженной версии задачи. Для сравнения эффективности методов были получены оценки на число операций каждого метода для достижения е-приближенного решения. При этом при оценки скорости методом использовалась структура задачи. При этом было показано, что, благодаря особой структуре целевой функции возможно эффективное применение метода покоординатного спуска. Второй метод относится к классу прямо-двойственных. Сами методы являются достаточно старыми, однако единственные оценки на их сложность, насколько нам известно, были получены в статьях Нестерова. Важно, что предложенные методы имеют разумную интерпретацию. Для метода покоординатного спуска удалось получить нетривиальные оценки скорости сходимости. Также задача поиска равновесия исследуется с помощью метода потенциалов Канторовича-Гавурина. Изначально метод потенциалов Канторовича-Гавурина был предложен для задачи поиска потока минимальной стоимости, однако может быть реализован и для задачи поиска равновесия.

Поиск равновесия можно осуществлять и по другому - иммитируя процесс выбора водителем маршрута движения и и его изменение при изменении загрузки сети. Для моделирования выбора используются модели дискретного выбора (множество альтарнатив - множество маршрутов). Выбор каждого водителя не так важен, интересно лишь агрегированное описание - распределение потоков по маршрутам. На каждом новом шаге каждый водитель может выбирать тот или иной маршрут с некоторой вероятностью (зависит от "привлекатель-ности"маршрута в предыдущий момент). Эволюция состояния системы будет описываться некоторой стохастической динамикой. Вместо исследования этой стохастической динамики осуществляется переход к исследованию динамики "средних". Эта динамика будет детерменированной. Такой подход пришел из эволюционной теории игр (см., например, [60]). Мы исследуем одну конкретную динамику репликантов, имеющую тесную связь с ^^-моделью, но свободную от ряда недостатков. Данная динамика исследуется численно, для чего был написан комплекс программ.

В четвертой главе описывается парадокс Браесса и исследуется задача поиска неэффективных ребер. Сам парадокс Браесса является классическим примером того, что равновесие Нэша может быть не эффективным по Парето ( [83]). Ранее было показано, что задача поиска оптимальной подсети для данного транспортного графа является КР-трудной. Насколько нам известно, для

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

В четвертой главе исследуется вопрос и об оптимальных платах на проезд в модели Нестерова-де Пальма. Для этого вводится понятие социального оптимума и показывается, что в модели Нестерова-де Пальма загрузка транспортной сети в равновесии совпадает с загрузкой в социальном оптимуме. При этом можно показать, что такая характеристика игры, как Цена анархии ( [83]) в данной модели может принимать неограниченно большое значение.

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

Научная новизна. Следующие результаты были получены впервые:

1. Было показано, что модель стабильной динамики может быть получена предельным переходом из модели Бекмана.

2. Для задачи условной оптимизации выпуклой функции, к которой сводится задача поиска равновесия в модели стабильной динамики, были получены два новых представления: в виде задачи линейного программирования и в виде задачи безусловной оптимизации выпуклой негладкой функции.

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

4. Была рассмотрена эволюционная динамика, сходящаяся к транспортному равновесию. Была написана программа для численного расчета равновесия.

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

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

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

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

Результат о возможности получения модели Нестерова-де Пальма в качестве предельного случая модели Бекмана является теоретическим результатом. При этом некоторые оценки для модели Нестерова-де Пальмы могут быть также получены предельным переходом оценок для модели Бекмана. Данный результат, тем не менее, был достаточно ожидаемым.

Несколько иная ситуация с алгоритмами для расчета транспортного равновесия. Несмотря на то, что прикладные пакеты, используемые для макроскопического моделирования транспортных систем, позволяют строить модели города с общим числом структурных элементов (ребер, вершин) более 105, алгоритмы, применяемые для расчета равновесия и используемые в этих пакетах, были разработаны еще в 70-е годы и расчитаны на решение задач средней, но не огромной размерности. Это приводит к тому, что зачастую задача поиска равновесия решается достаточно долго. Сама же модель Бекмана, используемая в данных программных пакетах, была разработана еще в середине 50-х годов и имеет ряд недостатков ( [75]). Это замечание относится ко всем основным программным пакетам, используемым на практике: EMME-2/3, Citilabs Cube, PTV Vissum.

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

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

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

ство оказывает влияние на транспортную ситуацию. На данный момент эффективно вычислимых моделей для расчета согласованных загрузки транспортной сети и план застройки нет. Это делает полученные результаты очень интересными с практической точки зрения. Сама же модель интересна как пример алгоритмической модели с двумя существенно различными классами игроков.

Публикации.

Основные результаты, вынесенные на защиту, опубликованы в 13 печатных работах, три из которых ( [3-5]) опубликованы в журналах, рекомендованных ВАК.

Апробация работы.

Результаты работы были апробированы на следующих конференциях и семинарах (список приведен далее), а также использованы при разработке математической модели транспортных потоков для программной модели расчета многостадийной макроскопической транспортной модели Москвы в НИ и ПИ Генплана Москвы в 2012 году. Также результаты работы были использованы при подготовке учебного курса "Математическое моделирование транспортных систем который читался в МФТИ в 2013-2014 учебном году.

Семинары:

1. Семинар Лаборатории больших случайных систем МГУ, 17 мая 2011 г.. Доклад "О сходимости одной стохастической динамики".

2. Семинар Транспортной лаборатории РАН при ИПМ РАН. 19 ноября

2011 г.. Доклады "Модели и методы расчета матрицы корреспонден-ций"и "Модели расчета равновесного распределения потоков".

3. Российско-японский транспортный симпозиум. Москва. 27-30 марта

2012 г.. Доклад "On the Calculation of Correspondence Matrix and the Traffic Assignment Problem".

4. День аспиранта лаборатории ПреМоЛаб. 16 марта 2012 г.. Доклад "Введение управляющих параметров в модель стационарной динамики и парадокс Браесса".

5. Научный семинар лаборатории ПреМоЛаб. 10 мая 2012 г.. Доклад "On the traffic assignment problem, the Braess paradox, traffic lights and road tolls".

6. Семинар по математическому моделированию транспортных потоков в НМУ. 20 октября 2012 г.. Доклад "Четырехстадийная модель".

7. Семинар молодых исследователей ПреМоЛаб. 16 ноября 2012 г.. Доклад "On detecting Braess paradox in Stable Dynamic model".

8. Семинар "Задачи дифференциальных уравнений, анализа и управления: теория и приложения"кафедры общих проблем управления МехМата МГУ. 3 и 10 декабря 2012 г.. Доклад "О некоторых равновесных моделях в математическом моделировании транспортных потоков и связанных с ними задачах".

9. Семинар по математическому моделированию транспортных потоков в НМУ. 6 апреля 2013 г.. Доклад "Парадокс Браесса в призме моделей Бекмана и Стабильной динамики".

10. Семинар по математическому моделированию транспортных потоков в НМУ. 26 апреля 2014 г.. Доклад "Расширения модели стабильной динамики".

11. Семинар "Математическое моделирование экономических систем"под рук. член-корр. РАН И.Г. Поспелова, ВЦ РАН, 21 мая 2014 г.. Доклад "О некоторых свойствах равновесия Нэша-Вардропа в модели Нестерова-де Пальмы".

12. Семинар "Методы оптимизации в функциональных пространствах"под рук. проф. Ф.П. Васильева, ВМК МГУ, 24 октября 2014. Доклад "О сложности метода покоординатного спуска при решении задачи поиска равновесия в транспортной сети".

Конференции:

1. Научная конференция МФТИ, Долгопрудный, 2009-2012.

2. 35-я конференция молодых ученых и специалистов "Информационные технологии и системы - 2012 Петрозаводск, 19-26 августа 2012. Доклад "Введение управляющих параметров в равновесные модели транспортных потоков".

3. Конференция "Интеллектуализация обработки информации - 9 Будва, Черногория, 17-21 сентября 2012, совместный доклад с А.В. Гаснико-вым и соавт.. Доклад "О некоторых задачах математического моделирования транспортных потоков".

4. Традиционная молодежная летняя школа "Информация, Управление, 0птимизация"(2012 - 2014).

5. VII Московская международная конференция по исследованию операций, Москва, 15-19 октября 2013 г.. Совместные доклады с А.В. Гасни-ковым, Ю.Е. Нестеровым, С.В. Шпирко. Доклады "On the Three-Stage version of the Stable Dynamic model "Connection between Beckmann and Stable Dynamic models "Application of primal-dual subgradient method to three-stage version of Stable Dynamic model".

6. Третья Школа междисциплинарного анализа социально-экономических процессов. Россия, Екатеринбург. 25-30 июля 2013 г.. Приглашенный докладчик. Доклад "Равновесное транспортное моделирование".

7. Байкальские чтения. Россия, Иркутск. 17-28 марта 2014 г.. Доклад "Алгоритмические транспортные модели".

8. 0PTIMA-2014. Черногория, Петровац. 28 сентября - 4 октября 2014 г.. Доклад "Equilibrium model for transportation system and land-use".

9. Конференция Frontiers of High Dimensional Statistics, Optimization, and Econometrics. Россия, Москва. 26-27 февраля 2015 г.. Доклад "First order methods for the transportation problem. Analysis of complexity".

10. International Transportation Economics Association Annual Conference and Summer School (Kuhmo Nectar). Норвегия, Осло. 15-19 июня 2015 г.. Доклад "OD-Matrix Estimation using Stable Dynamic Model".

11. Конференция Computational Multi Physics, Multi Scales and Multi Big Data in Transport Modeling, Simulation and Optimization. Финляндия, Юваскюля. 27-30 мая 2015 г.. Доклад "Computational Methods for the Stochastic Equilibrium Stable Dynamic Model".

Личный вклад соискателя в работы с соавторами (для совместной статьи с Гасниковым А.В., Нестеровым Ю.Е. и Шпирко С.В.) состоит в сведении модели Бекмана к модели стабильной динамики Нестерова-де Пальмы для случая BPR-функции и для общего случая; оценки цены анархии для модели стабильной динамики обзора работ по многостадийным моделями, (для совместной заметки с Гасниковой Е.В.) разработка комплекса программ и проведение численных экспериментов.

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

В главе, посвященной новым методам расчета равновесия новые формулировки задачи оптимизации, к которой сводится задача поиска равновесия в модели Нестерова-де Пальмы, были предложены автором. Идея использовать сглаживание исходила от Юрия Евгеньевича Нестерова. Идея использовать координатный спуск родилась в процессе непрерывного обсуждения, однако новые оценки сложности метода были получены автором самостоятельно (та их часть, которая не совпадает с оценками в статье [79]).

Структура и объем диссертации.

Диссертация состоит из введения, четырех глав и заключения. Библиография содержит 116 источников.

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

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

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

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

Заключение включает итоги исследования, рекомендации и дальнейшие направления исследования.

Благодарности.

Я очень благодарен своей любимой жене, без которой этой работы не было бы, и моему первому учителю Евгению Викторовичу Потоскуеву. Также хочу поблагодарить Александра Владимировича Гасникова и Юрия Евгеньевича Нестерова, курировавших эту работу со стороны Лаборатории структурных методов анализа данных в предсказательном моделировании (ПреМоЛаб) и научивших меня и хорошему и плохому в исследовании операций и оптимизации. Также я очень благодарен Борису Теодоровичу Поляку, Аркадию Семеновичу Немировскому, Евгению Алексеевичу Нурминскому, Александру Юрьевичу Горнову, Александру Григорьевичу Шапиро, Александру Викторовичу Нази-ну, Андрею Николаевичу Соболевскому за очень мотивирующие и благотворные беседы, а также Владимиру Григорьевичу Спокойному за возможность эти беседы иметь.

Большое спасибо моим замечательным коллегам Кате Крымовой, Паше Двуреченскому, Юре Максимову, Лене Ежовой, Егору Ершову, Максиму Панову и Вове Панову. Отдельное спасибо Леше Савватееву за жизнерадостность и Владимиру Григорьевичу Спокойному за то, что он есть.

Работа выполнена при поддержке грантов РФФИ 10-01-00321-а, 11-01-00494-а, мол-а-вед 12-01-33007, 13-01-12007 офи-м, Лаборатории структурных методов анализа данных в предсказательном моделировании, ФУПМ МФТИ, грант правительства РФ дог. 11.G34.31.0073, гранта Президента РФ № МК-5285.2013.9..

Объем и структура работы. Диссертация состоит из введения, четырёх глав, заключения и одного приложения. Полный объём диссертации составляет 143 страницы с 1 рисунком и 2 таблицами. Список литературы содержит 118 наименований.

Глава 1. Равновесные транспортные модели

1.1 Обозначения

Г(У, Е) — ориентированный транспортный граф.

Г С и - граф Г является подграфом графа и

V - множество вершин графа Г;

Е - множество ребер графа Г; IV | = щ 1ЕI = т;

/е - пропускная способность ребра е;

I = йх.Ьу.., !т)Т;

те - вес ребра е при отсутствии потока; т = (т1,Г2,...,тт);

Б - множество вершин-источников;

И - множество вершин-стоков;

{¿^},г Е Б, у Е И, (1у > 0 - матрица корреспонденций; = - генерируемый вершиной г поток;

^г = ■ Ц)Ее -поглощаемый вершиной г поток;

Пусть задан связанный ориентированный транспортный граф Г^,Е,т(/)) и матрица корреспонденций {(1^}. Дуплет (Г{у,Е,т(/)), {(1^}) называется конфигурацией сети.

Пусть (неориентированное) ребро е и вершины % и у инцедентны. Будем говорить, что триплет (г,е,у) задает локальную ориентацию ребра е. при этом вершина г будет называться началом ребра е, а вершина у будет называться его концом. Будем говорить, что на графе Г^, Е) задана глобальная ориентация, если для каждого ребра е определена локальная ориентация. Если для каждого ребра графа задана некоторая локальная ориентация, то мы будем говорить, что на графе задана глобальная ориентация.

Утверждение «Г^,Е) является ориентированным графом» далее означает, что каждому элементу е € Е множества ребер поставлено в соответствие

некоторая упорядоченная пара вершин (ге,]е), ъе,]е £ V, то есть что задана глобальная ориентация графа.

Пусть р = (гР1 ,еР1 ,гР2,...,еРк,гРк+1), £ V, е^ £ Е есть последовательность вершин и ребер графа. При этом каждый элемент входит в последовательность только один раз (то есть отсутствуют петли). Тогда мы назовем р путем из вершины гР1 в вершину ъРк+1. Каждый путь задает свою локальную ориентацию ребер, которые в него входят. Ориентация ребер в пути р ив графе Г не обязательно совпадает. Если задан ориентированный граф Г(У, Е) и некоторый путь р, то мы будем говорить что путь р согласован, если для всех ребер, принадлежащих пути р локальная ориентация ребер, индуцированная путем р и глобальная ориентация, заданная на Г совпадает. Если же нас не интересует совпадает или нет локальная ориентация пути и заданная на графе глобальная ориентация, то мы будем говорить о пути р как о неориентированном. «Неориентированность» значит не отсутствие локальной ориентации (она есть у любого пути), а отсутствие привязки к заданной на графе глобальной ориентации.

Рассмотрим ориентированный граф Г(V, Е). р называется маршрутом из вершины в £ V в вершину I £ V если р является путем из в в £ и локальная ориентация всех входящих в р ребер совпадает с ориентацией графа Г.

Пусть задан ориентированный граф Г(V, Е) и некоторый путь р. Опреде-

лим

7Г^(е) = <

1, е Е р и глобальная и локальная ориентация е в р совпадают; -1, е Е р и глобальная и локальная ориентация е в р не совпадаю 0, if е Е Р-

Pst - множество маршрутов из вершины s в вершину t; Кst -множество всех путей из вершины s в вершину t; Р = UPst - множество всех маршрутов в графе Г;

Для удобства мы будем понимать под р Е Р и маршрут р и номер маршрута р (то есть в зависимости от контекста под р Е Pst может пониматься просто индекс из множества индексов, которые соответствуют маршрутам из Pst)-К = UKst - множество всех путей в графе Г; хр - поток по маршруту р;

\Т

х = (xi, ..,х\р|)Т - вектор распределения потоков по маршрутам;

X = X({dij}) = {x G R+1 : X^€Pst xp = ^st} - множество допустимых распределений потоков по маршрутам;

Распределение х называется допустимым при матрице корреспонденций {dij}, если х G X

@ = {fiep}eGE,pGp - матрица инциденций ребер маршрутам. Здесь 5ер = 1 если е G р и 5ер = 0 иначе.

fe = хр • 6ер - загрузка ребра е при распределении потоков х;

Список литературы диссертационного исследования кандидат наук Дорн Юрий Владимирович, 2022 год

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

1. Anikin A., Dorn Y., Nesterov Y. Computational Methods for the Stable Dynamic Model //International Conference on Optimization and Applications. - Springer, Cham, 2019. - С. 280-294.

2. А.В. Гасников, П.Е. Двуреченский, Ю.В. Дорн, Ю.В. Максимов, Численные методы поиска равновесного распределения потоков в модели Бэкмана и в модели стабильной динамики // Матем. моделирование, Т.28., No.10., С. 40-64., 2016.

3. А. В. Гасников, Ю. В. Дорн, Ю. Е. Нестеров, С. В. Шпирко, О трехстадий-ной версии модели стационарной динамики транспортных потоков // Матем. моделирование, Т.26., No.6., С. 34-70., 2014.

4. Е.В. Гасникова и Ю.В. Дорн, О стохастической марковской динамике, приводящей к равновесию Нэша-Вардропа в модели распределения потоков // Труды МФТИ, Т.2., No.4 (8), С. 55-57. 2010.

5. Ю.В. Дорн, Поиск неэффективных ребер в транспортных сетях // Труды МФТИ, Т.6., No.1 (21), С. 162-168. 2014.

6. Ю.В. Дорн, О влиянии геометрических параметров города с сильнонеравномерной структурой распределения истоков и стоков корреспонден-ций на эффективность транспортной сети // Труды 52-й научной конференции МФТИ "Современные проблемы фундаментальных и прикладных наук": Часть VII. Управление и прикладная математика. Т.3. - М.: МФТИ, 2009. -56-58 с.

7. Ю.В. Дорн, Математическое моделирование эволюционных игр на транспортном графе: Равновесие, сходимость, бассейны притяжения // Труды 53-й научной конференции МФТИ "Современные проблемы фундаментальных и прикладных наук": Часть VII. Управление и прикладная математика. Т.1. -М.: МФТИ, 2010. 93-94 с.

8. Ю.В. Дорн, Платные дороги как средство достижения лучшего равновесия Нэша-Вардропа на транспортном графе // Труды 54-й научной конференции

МФТИ "Проблемы фундаментальных и прикладных естественных и технических наук в современном информационном обществе". Управление и прикладная математика. Т.1. - М.: МФТИ, 2011. 95-97 с.

9. Ю.В. Дорн, Поиск неэффективных ребер в транспортном графе // Труды 55-й научной конференции МФТИ "Проблемы фундаментальных и прикладных естественных и технических наук в современном информационном обществе". Управление и прикладная математика. Т.1. - М.: МФТИ, 2012. 48-50 с.

10. Ю.В. Дорн, Введение элементов управления в равновесные модели транспортных потоков // Труды 35-й конференции молодых ученых и специалистов "Информационные технологии и системы - 2012". ISBN 978-5-901158-19-7. 2012. 97-104 с.

11. Гасников А.В., Дорн Ю.В., Ивкин Н.П., Ишманов М.С., Обидина Т.С., Пет-рашко Д.С., Холодов Я.А., Хохлов М.А., Чехович Ю.В. О некоторых задачах математического моделирования транспортных потоков // Интеллектуализация обработки информации: 9-я международная конференция. Республика Черногория, г. Будва, 2012 г.: Сборник докладов. - М.: Торус Пресс, 2012. С. 211-214

12. Yu.V.Dorn. A.V.Gasnikov, Yu.E.Nesterov, S.V.Shpirko. Application of primal-dual subgradient method to three-stage version of Stable Dynamic model // VII Moscow International Conference on Optimization Research (0RM2013): Moscow, October 15-19, 2013: Proceedings: Vol.1. - Moscow, MAKS Press, 2013. p.251-253.

13. Yu.V.Dorn. A.V.Gasnikov, Yu.E.Nesterov, S.V.Shpirko. The connection between Beckmann and Stable Dynamics models // VII Moscow International Conference on Optimization Research (0RM2013): Moscow, October 15-19, 2013: Proceedings: Vol.1. - Moscow, MAKS Press, 2013. p.254-256.

14. Yu.V.Dorn. A.V.Gasnikov, Yu.E.Nesterov, S.V.Shpirko. The three-stage version of Stable Dynamic model // VII Moscow International Conference on Optimization Research (ORM2013): Moscow, October 15-19, 2013: Proceedings: Vol.1. - Moscow, MAKS Press, 2013. p.257-259.

15. Yu. Dorn. Equilibrium model for transportation system and land-use // Proccedings of V International Conference on Optimization Methods

and Applications "Optimization and Applications"(OPTIMA-2014): Petrovac. Montenegro, September 28 - October 4, 2014: - Moscow, 2014. p.53-54.

16. Л. М. Брэгман, Доказательство сходимости метода Г. В. Шелейховского для задачи с транспортными ограничениями // Ж. вычисл. матем. и матем. физ., 7:1 (1967), 147-156

17. А.Дж. Вильсон. Энтропийные методы моделирования сложных систем. М.: Наука, 1978.

18. Е. Гасникова. Моделирование динамики макросистем на основе концепции равновесия. Диссертация на соискание степени к.ф.-м.н.. Москва. 2012.

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

20. Канторович Л.В., Гавурин М.К., Применение математических методов в вопросах анализа грузопотоков. Проблемы повышения эффективности работы транспорта. М.: Л., 1949. С. 110-138.

21. Юбилейный выпуск к 100-летию со для рождения Л. В. Канторовича: Избранные труды // Под ред. и с предисл. Ю. С. Попкова. - М.: ЛЕНАНД, 2012. - 286 с.

22. Н.Н. Кузюрин, С.А. Фомин. Эффективные алгоритмы и сложность вычислений: Учебное пособие. - М.:МФТИ, 2007. - 312 с.

23. А.С. Немировский, Д.Б. Юдин. Сложность задач и эффективность методов оптимизации. - М.: Наука, 1979. 384с.

24. Ю. Нестеров. Введение в выпуклую оптимизацию. М.: МЦНМО, 2010. 280с.

25. Е. А. Нурминский, Н. Б. Шамрай, Метод локальных выпуклых мажорант для решения вариационно-подобных неравенств // Журнал вычислительной математики и математической физики, Т. 47., No. 3., с. 355-363. 2007.

26. Н. Б. Шамрай, Поиск потокового равновесия проективными методами с использованием декомпозиции и генерации маршрутов // Автоматика и телемеханика, № 3., c. 150-165. 2012.

27. Швецов В.И. Алгоритмы расчета транспортного равновесия // Автоматика и телемеханика. 2009. №10. 148-157.

28. Г. В. Шелейховский, Композиция городского плана как проблема транспорта. М., 1946.

29. R. Ahuja, T. Magnanti, J. Orlin. Network flows: theory, algorithms, and applications. Prentice-Hall, New Jersey. 1993.

30. T. Akumatsu and B. Heydecker, Detecting Dynamic Traffic Assignment Capacity Paradoxes in Saturated Networks // Transportation Science, V. 37., No.2., P. 123-138., 2003.

31. E. Anshelevich, A. Dasgupta, E. Tardos, T. Wexler, Near-Optimal Network Design with Selfish Agents // Theory of Computing, V.4., pp.77-109., 2008.

32. R. Arnott, A. de Palma, R. Lindsey. Economic of a bottleneck // Journal of urban economics, V.27, pp. 111-130., 1990.

33. Y. Askoura, J. Lebacque, H. Haj-Salem, Optimal sub-networks in traffic assignment problem and the Braess paradox // Computers and Industrial Engineering, 61, P. 382 - 390, (2011)

34. Bar-Gera H. Origin-based algorithms for transportation network modeling. Univ. of Illinois at Chicago, 1999.

35. N. Bean, F. Kelly, P. Taylor, Braess's Paradox in a Loss Network // Journal of Applied Probability, 34, P. 155-159, (1997)

36. M. Beckmann, B. McGuire, and C. Winsten. Studies in the Economics of Transportation. New Haven, CT: Yale University Press. 1956.

37. Moshe Ben-Akiva, Steven Lerman. Descrete Choice Analisys: Theory and Applications to Travel Demand. The MIT Press. 1985.

38. D. Boyce, H. Mahmassani, A. Nagurney, A retrospective on Beckmann, McGuire and Winstens Studies in the Economics of Transportation // Papers in Regional Science, 84, P. 85-103, (2005)

39. S. Boyd and L. Vanderberghe. Convex Optimization. Cambridge University Press, New-York, 2004. 716p.

40. U.S. Bureau of Public Roads. Traffic Assignment Manual. U.S. Bureau of Public Roads, U.S. Government Printing Office, Washington, D.C., 1964.

41. D. Braess, Uber ein Paradoxon aus der Verkehrsplanung // Unternehmensforschung, 12, P. 258-268, (1968)

42. D. Braess, A. Nagurney, T. Wakolbinger, On a Paradox of Traffic Planning // TRANSPORTATION SCIENCE, 39, P. 446-450, (2007)

43. H. Chen, T. Roughgarden, G. Valiant. Designing Network Protocols for Good Equilibria // SIAM Journal on Computing, V.39(5)., P. 1799-1832., 2010.

44. J. Cohen, F. Kelly, A Paradox of Congestion in a Queuing Network // Journal of Applied Probability, 27, P. 730-734, (1990)

45. R. Cole, Y. Dodis, T. Roughgarden. How much can taxes help selfish routing // Journal of Computer and System Sciences. V.72, P. 444-467, 2006.

46. S. Dafermos, Traffic Equilibrium and Variational Inequalities // Transportation Science, V.14., P. 42-54, (1980)

47. S. Dafermos, A. Nagurney, ON SOME TRAFFIC EQUILIBRIUM THEORY PARADOXES // Transportation Research B, 18B, P. 101-110, (1984)

48. J. Dong, A. Nagurney, Paradoxes in networks with zero emission links: implications for telecommunications versus transportation // Transportation Research D, 6, P. 283-296, (1984)

49. A. Epstein, M. Feildman, Y. Mansour, Efficient Graph Topologies in Network Routing Games // Games and Economic Behavior V. 66 : P. 115-125. 2009.

50. P. Ferrari, Road Pricing and Network Equilibrium // Transportation Research - B, V. 29B., No. 5., P. 357-372., 1995.

51. C. Fisk, IN A ROAD NETWORK, INCREASING DELAY LOCALLY CAN REDUCE DELAY GLOBALLY // Transportation Research, 15A, P. 245-248, (1981)

52. C. Fisk, S. Pallottino, EMPIRICAL EVIDENCE FOR EQUILIBRIUM PARADOXES WITH IMPLICATIONS FOR OPTIMAL PLANNING STRATEGIES // Transportation Research, 12, P. 419-422, (1978)

53. D. Fotakis, A. Kaporis, P. Spirakis, Efficient methods for selfish network design // Theoretical Computer Science, 448, P. 9 - 20, (2012)

54. Frank M., Wolfe P. An algorithm for quadratic programming // Naval Res. Logistics Quar- terly. 1956. V. 3. P. 95-110.

55. M. FRANK, THE BRAESS PARADOX // Mathematical Programming, 20, P. 283-302, (1981)

56. E. Gisches, A. Rapoport, Choice of routes in congested traffic networks: Experimental tests of the Braess Paradox // Theory and Decision, 73, P. 267293, (2012)

57. D. Grosu and A. Chronopoulos, Algorithmic Mechanism Design for Load Balancing in Distribution Systems // IEEE Transactions on Systems, Man, and Cybernetics - Part B: Cybernetics, V.34., No.1., pp.77-84., 2004.

58. J. Hagstrom, R. Abrams, Characterizing Braesss Paradox for Traffic Networks // IEEE Conference on Intelligent Transportation Systems, P. 837-842, (2001)

59. J. Hershberger and S. Suri. Vickrey Prices and Shortest Paths: What is en edge worth // Foundations of Computer Science, 2001. Proceedings. 42nd IEEE Symposium. pp.252,259, 8-11 Oct. 2001. doi: 10.1109/SFCS.2001.959899

60. J. Hofbauer, K. Sigmund, Evolutionary Game Dynamics // Bulletin of the American Mathematical Society, V.40., No.4., P. 479-519., 2003.

61. Matthew O. Jackson. Social and Economic Networks. Princeton University Press. 2008.

62. F. H. Knight. Some fallacies in the interpretation of social cost // Quarterly Journal of Economics, V.38. 1924. P.582-606.

63. W. Knodel, Graphentheoretische Methoden und ihre Anwendungen // Graphentheoretische Methoden und ihre Anwendungen, 13, (1969)

64. Y. Korilis, A. Lazar, A. Orda, Avoiding the Braess Paradox in Non-Cooperative Networks // Journal Of Applied Probability, V.36., No.1., P. 211-222. 1999.

65. E. Koutsoupias and C. Papadimitriou. Worst-case equilibria // Proceedings of the 16th Annual Symposium on Theoretical Aspects of Computer Science, P. 404413, 1999.

66. LeBlanc L.J., Morlok E.K., Pierskalla W. An efficient approach to solving the road network equilibrium traffic assignment problem // Transpn. Res. B. 1975. V. 9. P. 309-318.

67. I. Milchtaich. Congestion Games with Player-Specific Payoff Functions // Games and Economic Behavior, V.13., P. 111-124., (1996)

68. I. Milchtaich, Network Topology and the Efficiency of Equilibrium. ICM Millennium Lectures on Games. 2003, pp 233-266.

69. I. Milchtaich. Topological Conditions for Uniqueness of Equilibrium in Networks // Mathematic of Operation Research, V.30., Mo.1., P. 225-244., 2005.

70. D. Monderer and L. Shapley. Potential Games // Games and Economic Behavior. V. 14, P. 124-143. 1996.

71. J. MURCHLAND, BRAESSS PARADOX OF TRAFFIC FLOW //

Transportation Research, 4, P. 391-394, (1970)

72. A. Nagurney. Network Economics: A Variational Inequality Approach. Kluwer Academic Publishers. Dordrecht. 1993.

73. J. Nash. Non-cooperative games // Annals of Mathematics, V. 54. P. 286-295, 1951.

74. A. Ben-Tal and A. Nemirovski. Lectures on Modern Convex Optimization: Analysis, Algorithms, and Engeneering Applications. MOS-SIAM Series in Optimization, 2001. 488p.

75. A. de Palma, Yu. Nesterov, Stationary Dynamic Solutions in Congested Transportation Networks: Summary and Perspectives // Networks and Spatial Economics, 3, P. 371-395, (2003)

76. Yu. Nesterov, Smooth minimization of non-smooth functions // Mathematical Programming ser.A, 103, P. 127-152, (2005)

77. Yu. Nesterov, Characteristic functions of directed graphs and applications to stochastic equilibrium problems // Optimization and Engeneering, V.8., I.2., P. 193-214, (2007)

78. Yu. Nesterov, Primal-dual subgradient methods for convex problems // Mathematical Programming Ser. B, 120, P. 221-259, (2009)

79. Yu. Nesterov, EFFICIENCY OF COORDINATE DESCENT METHODS ON HUGE-SCALE OPTIMIZATION PROBLEMS // SIAM Journal of Optimization, V.22., No.2., P. 341-362, (2012)

80. Yu. Nesterov, Subgradient methods for huge-scale optimization problems // Mathematical Programming Ser.A, DOI 10.1007/s10107-013-0686-4, (2013)

81. Yu. Nesterov, V. Shikhman. Algorithmic models of market equilibrium // CORE Discussion Paper, 2013/66.

82. Nguen S. A unified approach to equilibrium methods for traffic assignment // Traffic equilibrium methods, Proceedings of international held at the University of Montreal, November 21-23, 1974. M.A. Florian ed., vol. 118 of Lecture Notes in Economics and Mathematical Systems, Springer-Verlag, Berlin, 1976. P. 148 -182.

83. Noam Nisan, Tim Roughgarden, Eva Tardos and Vijay Vazirani. Algorithmic Game Theory. Cambridge University Press. 2007.

84. M. Naor, B. Pinkas, R. Sumner, Privacy Preserving Auction and Mechanism Design // Proceedings of the 1st ACM conference on Electronic commerce, pp. 129-139. 1999.

85. Juan Ortuzar and Luis Willumsen. Modelling transport. John Wiley and Sons. 1990.

86. M. G. Pala, S. Baltazar, P. Liu, H. Sellier, B. Hackens, F. Martins, V. Bayot, X. Wallart, L. Desplanque, and S. Huant, Transport inefficiency in branched-out

mesoscopic networks: An analog of the Braess paradox // Physical Review Letters, 108, P. 076802-1 - 076802-5, (2012)

87. K. Park, Detecting Braess Paradox Based on Stable Dynamics in General Congested Transportation Networks // Networks and Spatial Economics, 11, P. 207-232, (2011)

88. E. Pas, S. Principio, BRAESS PARADOX: SOME NEW INSIGHTS // Transportation Research B, 31, P. 265-276, (1997)

89. Patriksson M. The Traffic Assignment Problem - Models and Methods. Utrecht, Nether- lands: VSP, 1994.

90. C. Penchina, BRAESS PARADOX: MAXIMUM PENALTY IN A MINIMAL CRITICAL NETWORK // Transportation Research A, 22, P. 379-388, (1997)

91. A.C. Pigou. The economics of welfare. Macmillan. 1920.

92. M. Potamias, F. Bonchi, C. Castillo, A. Gionis, Fast Shortest Path Distance Estimation in Large Networks // Proceedings of the 18th ACM conference on Information and knowledge management. pp. 867-876. 2009.

93. A. Rapoport, T. Kugler, S. Dugar, E. Gisches, Choice of routes in congested traffic networks: Experimental tests of the Braess Paradox // Games and Economic Behavior, 65, P. 538571, (2009)

94. R. Rosenthal. Congestion Games with Player-Specific Payoff Functions // International Journal of Game Theory, V.2., I.1., pp. 65-67., 1973.

95. T. Roughgarden and E. Tardos. How bad is selfish routing // Journal of the ACM, V.49(2), P. 236-259, 2002.

96. T. Roughgarden and E. Tardos. Bounding the inefficiency of equilibria in nonatomic congestion games // Games and Economic Behavior, V. 49(2): P. 389-403, 2004.

97. T. Roughgarden. Selfish Routing and the Price of Anarchy. MIT Press. 2005.

98. T. Roughgarden, On the severity of Braess's Paradox: Designing networks for selfish users is hard // J.Computer System Sci., 72 (5), P. 922 - 953, (2006)

99. W. Sandholm, Evolutionary Implementation and Congestion Pricing // Review of Economic Studies, V.69., P. 667-689., 2002.

100. W. Sandholm, Negative Externalities and Evolutionary Implementations // The Review of Economic Studies, V. 72 (3): P. 885-915., 2005.

101. W. Sandholm, Pigovian Pricing and Stochastic Evolutionary Implementation // Journal of Economic Theory, V. 132., I. 1., P. 367-382., 2007.

102. William H. Sandholm. Population Games and Evolutionary Dynamics. The MIT Press. Cambridge, Massachusetts. 2010.

103. M. Scarsini, T. Tomala, Repeated congestion games with bounded rationality // International Journal of Game Theory, V.41, pp. 651-669., 2012.

104. Sheffi, Y. Urban Transportation Networks. Prentice Hall, Englewood Cliffs, NJ. 1985.

105. Yoav Shoham and Kevin Leyton-Brown. Multiagent Systems: Algorithmic, Game-Theoretic and Logical Foundations. Cambridge University Press. New York. 2009.

106. M. Smith. Existence, Uniqueness and Stability of Traffic Equilibria // Transportation Research, V.13B, pp. 259-304., 1979.

107. M. Smith, MORE PARADOXES IN THE EQUILIBRIUM ASSIGNMENT PROBLEM // Transportation Research, 13B, P. 305-309, (1979)

108. M. Smith, IN A ROAD NETWORK, INCREASING DELAY LOCALLY CAN REDUCE DELAY GLOBALLY // Transportation Research, 12, P. 419-422, (1978)

109. R. Solow and W. Vickrey, Land Use in a Long Narrow City // Journal of Economic Theory, V.3., P.430-447., 1971.

110. R. Steinberg, W. Zangwill, The Prevalence of Braess's Paradox // Transportation Science, 17, P. 301-318, (1983)

111. R. Steinberg, R. Stone, The Prevalence of Paradoxes in Transportation Equilibrium Problems // Transportation Science, 31, P. 231-241, (1988)

112. G. Valiant, T. Roughgarden, Braess's Paradox in Large Random Graphs // Random Structures and Algorithms, 37, P. 495 - 515, (2010)

113. W. Vickrey, Pricing in Urban and Suburban Transport // The American Economic Review, V. 53., No.2., P. 452-465., 1963.

114. Wardrop, J. (1952). "Some Theoretical Aspects of Road Traffic Research." Proceedings of the Institute of Civil Engineers Part II, 1, 325-378.

115. H. Yang, M. Bell, A CAPACITY PARADOX IN NETWORK DESIGN AND HOW TO AVOID IT // Transportation Research A, 32, P. 539 - 545, (1998)

116. H. Yang and M. Bell, Traffic Restraint, Road Pricing and Network Equilibrium // Transportation Research - B, V. 31., No.4., P. 303-314., 1997.

117. H. Yang, W. Bu, B. He, Q. Meng, Road pricing for congestion control with unknown demand and cost functions // Transportation Research - C, V. 18., P. 157-175., 2010.

118. V. Zverovich1, E. Avineri, Braess' paradox in a generalised traffic network // Journal Of Advanced Transportation, 2014, DOI: 10.1002/atr.1269.

Список рисунков

3.1 Падаокс Браесса

72

Приложение А

Листинг кода для расчета равновесной загрузки сети с помощью покоординатного спуска для сглаженной модели

Листинг А.1 подгружается из внешнего файла. Приходится загружать без окружения дополнительного. Иначе по страницам не переносится.

Листинг А.1

Листинг из внешнего файла

#1пе1иёе <1ов-Ьгеат> #1пе1иёе <уе^ог> #1пс1иёе <string> #1пс1иёе <fstream> #^с1иёе <assert.h> #inc1ude <math.h> #^с1иёе <sys/time.h>

10

15

20

25

using namespace std;

const double mu = 0.1;

typedef pair<int, int> arc;

struct arc_info {

double capacity,

free_flow_time;

arc_info(double .capacity, double _free_flow_time) {

capacity = .capacity; free_flow_time = _free_flow_time;

}

arc_inf o () {

capacity = 0.0; free_flow_time = 0.0;

40

45

50

55

60

65

struct OD_item {

int start , end; double demand;

OD_item(int _start , int _end, double _demand) {

start = _start ; end = _end ; demand = _demand;

}

};

struct network {

int n, m, l ;

vector<vector<int> >in_table, out_table; //+ vector<vector<arc_info> >arc_info_table ; // +

vector<arc> arc_list; //+ vector<int> origin_list;

vector<OD_item> OD_list;

vector<vector<double> > demand_table;

vector<vector<int> > dest_table;

vector<vector<double> > T;

vector<vector<double> > T_grad;

vector<vector<double> > T_grad_lin_part;

vector<vector<double> > y;

vector<vector<double> > z;

vector<vector<double> > denom_table;

vector<vector<vector<double> > > numer_table;

double L;//, sigma_2;

vector<vector<double> > L_table;

80

85

90

95

100

105

vector<int> seg_tree; vector <int > origin_index;

network(string file_net, string file_trips) {

load_network(file_net); load_trips(file_trips); L = 0.0;

gradient_linear_part () ; compute_lip_const () ;

gradient();

}

///##############

///INITIALIZATION ///##############

void load_network(string filename) {

if stream file;

file.open(filename);

assert(file >> n >> m);

in_table = vector<vector<int> >(n); out_table = vector<vector<int> >(n);

arc_info_table = vector<vector<arc_info> >(n, vector< arc_inf o > (n)) ;

for(int i = 0; i < m; ++i) {

int start = 0, end = 0; assert (file >> start >> end);

120

125

130

135

140

145

start -= 1; end -= 1;

double capacity = 0.0; assert(file >> capacity); //capacity *= 2.0; capacity * = 2000.0;

double length = 0.0; assert (file >> length);

double free_flow_time = 0.0; assert(file >> free_flow_time);

double B = 0.0; assert(file >> B) ;

double power = 0.0; assert(file >> power);

double speed_limit = 0.0; assert(file >> speed_limit);

double toll = 0. 0; assert(file >> toll);

int type = 0; assert(file >> type);

char end_of_line; assert(file >> end_of_line); assert(end_of_line == ';');

arc_list.push_back(arc(start, end)); arc_info_table[start][end] = arc_info(capacity

free_flow_time) ; in_table [end] .push_back(start) ; out_table[start].push_back(end);

}

file.close () ;

}

160

165

170

175

180

185

void load_trips(string filename) {

if stream file;

file.open(filename);

assert(file >> l);

T = vector<vector<double> >(n); T_grad = vector<vector<double> >(n); T_grad_lin_part = vector<vector<double> >(n); demand_table = vector<vector<double> >(n); dest_table = vector<vector<int> >(n); z = vector<vector<double> >(n); y = vector<vector<double> >(n);

L_table = vector<vector<double> >(n);

denom_table = vector<vector<double> >(n, vector<double>( n, 0.0)) ;

numer_table = vector<vector<vector<double> > >(n); origin_index = vector<int>(n, -1);

for(int i = 0; i < l; + + i) {

string origin = "" ; assert(file >> origin); assert(origin == "Origin");

int start = 0; assert(file >> start); start -= 1;

origin_index[start] = i;

origin_list.push_back(start); T[start] = vector<double>(n); T_grad[start] = vector<double>(n) ; T_grad_lin_part[start] = vector<double>(n) ; demand_table [ start] = vector<double>(n) ;

200

205

210

215

220

225

z[start] = vector<double>(n); y[start] = vector<double>(n);

L_table[start]= vector<double>(n);

numer_table[start] = vector<vector<double> >(n, vector<double>(n, 0.0));

while(true) {

int end = 0;

char dell = 0, del2 = 0;

if(!(file >> end)) {

file.clear () ; break;

}

end -= 1;

double demand = 0.0;

assert(file >> dell >> demand >> del2); assert(dell == ':'); assert(del2 == ';');

OD_list.push_back(OD_item(start, end, demand)); demand_table[start][end] = demand; dest_table[start].push_back(end);

file.close () ;

}

void gradient_linear_part() {

for(int s = 0; s < origin_list.size(); ++s)

T_grad_lin_part [origin_list [s]] = vector<double>(n 0.0) ;

for (i nt od = 0; od < OD_list . size () ; + + od)

}

}

240

245

250

255

T_grad_lin_part[OD_list [od] .start] [OD_list [od] . end]

-= OD_list [od] .demand ; T_grad_lin_part[OD_list [od] .start] [OD_list [od] .start ] += OD_list[od] .demand ;

}

void compute_lip_const () {

double a12 = 0.0; double inv_sigma_2 = 0.0;

for(vector<arc>::iterator e = arc_list.begin(); e != arc_list.end(); ++e)

{

if(a12 < arc_info_table[e->first] [e->second] . capacity)

a12 = arc_info_table[e->first][e->second]. capacity;

if(inv_sigma_2 < 1.0 / arc_info_table[e->first] [e-> second] .capacity / arc_info_table[e->first] [e-> second].free_flow_time) inv_sigma_2 = 1.0 / arc_info_table [e->first][e-> second] .capacity / arc_info_table[e->first] [e ->second].free_flow_time;

L = a12 * a12 * inv_sigma_2 / mu;

for(int s = 0; s < n; ++s)

for(int i = 0; i < L_table [s] .size () ; + + i) {

L_table [s] [i] = 0;

for(vector<int>::iterator iter = in_table[i]. begin(); iter != in_table [i] .end() ; ++iter) if(L_table [s] [i] < arc_info_table[*iter] [i] capacity)

L_table[s][i] = arc_info_table[*iter][i ] . capacity;

{

}

}

265

270

275

280

285

290

for(vector<int>::iterator iter = out_table [i] . begin(); iter !=out_table[i].end(); ++iter) if(L_table [s] [i] < arc_info_table[i] [*iter] capacity)

L_table[s] [i] = arc_info_table[i] [*iter ] . capacity; L_table [s] [i] *= a12 *inv_sigma_2 / mu ;

///#######

///COMPUTE ///#######

double compute() {

double res = 0. 0;

for(int i = 0; i < OD_list.size() ; ++i) {

double T_ij = T[OD_list [i] .start] [OD_list [i] .end] ; double T_ii = T[OD_list [i] .start] [OD_list [i] .start] ; res -= OD_list [i] .demand * (T_ij - T_ii);

}

for(int i = 0; i < arc_list.size(); ++i) {

double logarithm = 0. 0;

for(int s = 0; s < origin_list.size(); ++s) {

double add = T[origin_list [s]] [arc_list [i] . s e c o nd ] ;

add -= T[origin_list [s]] [arc_list [i] .first] ; add -= arc_inf o_table [arc_list [i] . f irst] [ arc_list [i] .second] .free_flow_time ;

}

}

add /= arc_info_table[arc_list [i] .first] [ arc_list [i] .second] .free_flow_time * mu ;

295

300

305

310

315

320

325

330

logarithm += exp(add);

}

logarithm = log(logarithm + 1.0);

logarithm *= arc_info_table[arc_list[i] .first] [

arc_list [i] .second] .free_flow_time ; logarithm *= arc_info_table[arc_list[i].first] [ arc_list [i] .second] .capacity * mu;

res += logarithm;

return res;

//########################

//GRADIENT COMPUTE UTILITY //########################

double compute_denom(int i, int j) {

denom_table[i][j] = 1.0;

for(vector<int>::iterator k = origin_list.begin(); k != origin_list.end(); ++k) denom_table [i] [ j] += exp((T [*k] [ j] - arc_info_table[ i] [j] .free_flow_time - T[*k][i]) / ( arc_info_table [i] [j] .free_flow_time) / mu) ; return denom_table[i][j];

}

void compute_denom_table() {

for(int i = 0; i < n; ++i)

for(int j = 0; j < n; ++j) compute_denom(i, j);

}

double compute_numer(int s, int i, int j) {

numer_table[s][i][j] = arc_info_table[i][j].capacity;

}

}

335

340

345

350

355

numer_table [s] [i] [j] *= exp((T[s][j] - T[s][i] -arc_info_table [i] [j] .free_flow_time) /

arc_info_table [i] [j] . free_flow_time / mu);

return numer_table [s] [i] [j] ;

}

void compute_numer_table() {

for(vector<int>::iterator s = origin_list.begin(); s ! origin_list.end () ; ++s) for(int i = 0; i < n; + + i)

for(int j = 0; j < n; + + j)

compute_numer(*s, i, j);

}

///########

///GRADIENT ///########

double gradient_component(int start, int end, bool seg_tree = false)

{

double res = 0. 0;

for(vector<int>::iterator iter = in_table[end] .begin () ; iter != in_table [end] .end () ; ++iter) res += numer_table[start] [*iter] [end] / denom_table [* iter] [end] ;

for(vector<int>::iterator iter = out_table [end] .begin() ; iter != out_table [end] .end () ; ++iter)

res -= numer_table[start] [end] [*iter] / denom_table [ end] [* iter] ;

res += T_grad_lin_part [start] [end] ;

if(seg_tree)

st_set_value(res, start, end);

370

375

380

385

390

395

else

T_grad[start][end] = res; return res;

}

void gradient() {

compute_denom_table(); compute_numer_table(); for(int i = 0; i < n ; ++i)

for(int j = 0; j < T_grad [i] .size () ; + + j)

T_grad[i][j] = gradient_component(i, j);

}

///#############################

///ACCELERATED GRADIENT DESSCENT ///#############################

void agd_gradient() {

compute_denom_table(); compute_numer_table();

for(int s = 0; s < origin_list.size(); ++s)

T_grad[origin_list [s]] = vector<double>(n , 0.0);

for(vector<arc>::iterator e = arc_list.begin(); e != arc_list.end(); ++e)

{

int i = e- > second; int j = e->f irst;

for(vector<int>::iterator s = origin_list.begin() ; s != origin_list.end () ; ++s)

T_grad [*s] [i] += numer_table [*s] [j] [i] / denom_table [j] [i] ;

i = e->f irst ; j = e->second ;

405

410

415

420

425

for(vector<int>::iterator s = origin_list.begin(); s != origin_list.end () ; ++s)

T_grad [*s] [i] -= numer_table[*s] [i] [j] / denom_table [i] [j] ;

}

for (i nt od = 0; od < OD_list . size () ; + + od) {