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

  • Крылатов, Александр Юрьевич
  • кандидат науккандидат наук
  • 2014, Санкт-Петербург
  • Специальность ВАК РФ01.01.09
  • Количество страниц 107
Крылатов, Александр Юрьевич. Математическое моделирование распределения транспортных потоков: дис. кандидат наук: 01.01.09 - Дискретная математика и математическая кибернетика. Санкт-Петербург. 2014. 107 с.

Оглавление диссертации кандидат наук Крылатов, Александр Юрьевич

СОДЕРЖАНИЕ

ВВЕДЕНИЕ

ГЛАВА 1. МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ РАСПРЕДЕЛЕНИЯ ТРАНСПОРТНОГО ПОТОКА ОДНОЙ ГРУППЫ УЧАСТНИКОВ ДВИЖЕНИЯ 12 § 1. Общая постановка задачи распределения транспортных потоков . 12 § 2. Методы решения задачи распределения транспортных потоков

§ 3. Структуры транспортных сетей

§ 4. Оптимальное распределение транспортных потоков на сети с неоднородными параллельными путями

§ 5. Транспортная сеть с подсетями из параллельных неоднородных

каналов

§ 6. ВРЯ-функция задержки и парадокс Браесса

ГЛАВА 2. РАСПРЕДЕЛЕНИЕ ТРАНСПОРТНЫХ ПОТОКОВ В МНОГО-

АГЕНТНЫХ ТРАНСПОРТНЫХ СИСТЕМАХ

§ 1. Конкурентная маршрутизация транспортных потоков

§ 2. Общая постановка задачи распределения транспортных потоков с

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

§ 3. Модель с множеством групп участников на сети из параллельных

каналов

§ 4. Сравнение равновесий по Вардропу и по Нэшу

§ 5. Равновесие для маршрутов с общими дугами

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

ГЛАВА 3. МАТРИЦЫ КОРРЕСПОНДЕНЦИЙ 83 § 1. Матрицы корреснонденций в задаче распределения транспортных

потоков

§ 2. Методы построения матриц корреспонденции

§ 3. Данные видео регистрации транспортных средств и оценка матриц

корреспонденции

§ 4. Идентификация транспортных потоков между районами

отправления-прибытия

§ 5. Задача распределения датчиков систем видео регистрации транспортных потоков

ЗАКЛЮЧЕНИЕ

ЛИТЕРАТУРА

Рекомендованный список диссертаций по специальности «Дискретная математика и математическая кибернетика», 01.01.09 шифр ВАК

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

ВВЕДЕНИЕ

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

Теория транспортных потоков начала развиваться сто лет назад [22]. Основы же математического моделирования закономерностей дорожного движения были заложены в 1912 году русским ученым, профессором Г.Д. Дубели-ром [21]. Тогда ставилась задача анализа пропускной способности магистралей и пересечений, то есть речь шла исключительно об анализе мощностей самой транспортной инфраструктуры. Затем стали появляться многочисленные публикации, описывающие с помощью моделей и методов теории вероятностей и математической статистики, возникновение и взаимодействие транспортных потоков на различных узлах (перекрестках, светофорах, сужениях и проч.) транспортной сети. Такие модели, как правило, описывали поведение транспортных потоков на локальных элементах УДС, но при переносе их на всю сеть стапови-

лись чрезмерно громоздкими и оттого неприменимыми на практике. В 1934 году Б.Д. Гриншильд [44] предложил математическую модель движения транспортного потока, в которой движение каждого автомобиля было ограничено исключительно движением едущего впереди него транспортного средства. Подобные модели называют микроскопическими, так как они не дают ответа на вопрос о движении всего потока, а лишь дают некое представление о взаимодействии любых двух транспортных средств внутри потока. В 1955 году появилась первая макроскопическая модель транспортного потока, предложенная Лайтхилом и Уиземом [26, 57], в которой движение транспорта рассматривалось с позиции механики сплошной среды. Подобный подход также носил сугубо локальный характер применения и был способен лишь немного пролить свет на природу движения автомобилей в потоке.

В конце 50-х выходит монография Ф. Хейта [27], в которой объединяются результаты всех проведенных к этому времени исследований о движении транспортных потоков. Считается, что именно с этого момента произошло выделение теории транспортных потоков в самостоятельный раздел прикладной математики. В 60-70-е годы активная исследовательская работа в области транспортных потоков продолжалась. Однако но большей части, эта работа носила характер расширения и уточнения уже ранее предложенных микроскопических, макроскопических и статистических моделей. Принципиально новые положения в теории транспортных потоков были выдвинуты Кернером в конце 1990-х [49-52] и окончательно сформулированы в 2009 [48]. Он выделил три основных состояния или три фазы транспортного потока. Полученные им результаты, прежде всего, базируются на идеях макроскопических и микроскопических моделей, а сама теория трех фаз посвящена скорее описанию состояний, чем моделированию. Последнее, тем не менее, ни в коей степени не должно преуменьшать заслуг Кернера, так как его выводы способны существенно помочь тем, кто берется за моделирование транспортных потоков. В современной отечественной литературе следует в первую очередь отметить работы В.И. Швецова [29, 30], посвященные моделям и алгоритмам равновесного распределения транспортных потоков крупного города, а также В.И. Зоркальцева и М.А.Киселевой [9] и

других авторов [17, 23, 24]. С разработками российских ученых, базирующихся на модели Лайтхилла-Уизема [57], можно ознакомится в следующих публикациях [4, 5, 15, 16, 28].

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

В последние годы, в результате активного внедрения в практику систем навигации на транспорте усилилось влияние на распределение транспортных потоков, особенно, в крупных городах, различных компаний и служб, предоставляющих услуги по прокладке маршрутов для транспортных средств. Вследствие этого появилась необходимость в разработке и исследовании математических моделей для оценки влияния изменившейся ситуации на формирование в транспортных системах равновесных распределений. Следует, однако, отметить, что в научной литературе пока имеется незначительное число публикаций, посвященных проблемам распределения потоков в сетях при наличии групп участников и вопросам применения теоретико-игрового подхода для решения возникающих здесь задач [6, 7, 31-34, 70]. Вместе с тем, имеется значительное число исследователей, таких как, Altman Е., Basar Т., А.Ю. Гарнаев, В.Л. Крепе, В.В. Мазалов, Л.А. Петросяи и др., предлагающих в своих публикациях методы и теоретико-игровые модели, использование и развитие которых для

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

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

• Построение и исследование математических моделей распределения транспортных потоков с ВРЯ-функцией задержки на сетях с параллельными и частично совпадающими однородными и неоднородными маршрутами.

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

• Получение условий существования ситуаций равновесия по Нэшу в бескоалиционных играх распределения транспортных потоков и ситуаций равновесия по Штакельбергу в двухуровневых играх.

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

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

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

Новыми результатами, представленными в работе, являются:

• аналитическое представление конкурентного равновесия по Вардропу в задаче распределения транспортных потоков на сетях с параллельными и частично совпадающими однородными и неоднородными путями;

• аналитическое представление системного оптимума Вардропа в задаче распределения транспортных потоков на сетях с параллельными и частично совпадающими однородными и неоднородными путями;

• необходимые и достаточные условия существования и аналитическое выражение равновесия по Нэшу в задаче распределения транспортных потоков при наличии множества конкурирующих групп участников движения на сетях с параллельными и частично совпадающими однородными и неоднородными путями;

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

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

Теоретическая и практическая значимость. Результаты исследования вносят вклад в развитие теории игр и ее приложений в задачах маршрутизации транспортных потоков и могут найти применение при принятии решений о реконструкции УДС крупных городов.

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

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

Первая глава посвящена изучению математической модели распределения транспортных потоков. В качестве модели рассматривается классическая формулировка Бекманна, однако в качестве оценки времени перемещения по дуге используется линейная ВРИ-функция задержки. Исследуется возможность получения решений в явном виде для различных структур транспортных сетей. В § 1 приводится общая постановка задачи равновесного по Вардропу распределения транспортных потоков. Во 2-ом параграфе обсуждаются методы и подходы решения задачи равновесного распределения транспортных потоков, затрагивается вопрос нахождения решений в явном виде. Параграф 3 посвящен идеи декомпозиции транспортной сети произвольной топологии в виде подсетей определенной структуры. В § 4 изучается транспортные сети из параллельных неоднородных и однородных путей, решения находятся в явном виде. Параграф 5 посвящен исследованию транспортной сети, включающей подсети из параллельных неоднородных путей, выводятся условия получения аналитических решений. Последний параграф главы посвящен ромбовидной структуре транспортной сети с ВРЯ-функциями задержки на дугах, выявлены условия проявления парадокса Браесса в таком случае.

Во второй главе изучаются теоретико-игровые модели распределения транспортных потоков с множеством групп участников движения и с использованием ВРИ-фуикции задержки. В частности, одна из моделей формулируется в виде двухуровневой иерархической игры, верхней уровень которой стремится к получению оптимального по Штакельбергу решения, а нижний уровень стремится добиться равновесия по Нэшу среди множества групп участников движения. В § 1 приведено краткое описание проблематики конкурентной маршрутизации транспортных потоков. В § 2 сформулирована игра поставщиков услуг навигации в общем виде. Параграф 3 посвящен игре поставщиков услуг навигации на сети из параллельных каналов и линейной ВРЯ-функцией задержки, равновесные стратегии получены в явном виде. В 4-ом параграфе производится сравнение равновесий по Вардропу и Нэшу для сети из параллельных каналов. В § 5 исследуется проблема равновесия па транспортной сети, имеющей одновременно как независимые маршруты, так и маршруты с общей дугой. В §

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

Третья глава посвящена вопросам получения граничных условий исследуемых в диссертационной работе математических моделей, а именно - матриц корреспонденций. Параграф 1 содержит описание состояния исследований в дайной области на сегодняшний день. В § 2 приведены основные методы оценки матриц корреспонденций на транспортной сети произвольной топологии. В 3-ем параграфе приведен алгоритм построения матриц корреспонденций на базе информации, получаемой с систем фиксации регистрационных номерных знаков автотранспорта. В'§ 4 описана общая модель оценки маршрутов движения автотранспорта на основе информации с систем видеорегистрации номерных знаков. Параграф 5 адресован проблеме оптимальной расстановке на транспортной сети датчиков фиксации номерных знаков автотранспорта.

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

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

По теме диссертации опубликовано 10 работ, четыре из которых - в изданиях, рекомендуемых Высшей аттестационной комиссией (ВАК) для публикации основных научных результатов [6-8, 12], одна - в периодическом издании, индексируемом в Scopus [70].

Результаты исследования докладывались и обсуждались на международных конференциях "International conference on Computer technologies in physical and engineering applications"(Санкт-Петербург, 2014 г.), "20th Conference of the International Federation of Operational research societies" (Барселона, 2014 г.), "Процессы управления и устойчивость"(Санкт-Петербург, 2014 и

2012 гг.), "VII Московская международная конференция по Исследованию Операций "(Москва, 2013 г.), "26th European conference on Operational research" (Рим, 2013 г.), "Game Theory and Management "(Санкт-Петербург,

2013 и 2014 гг.), "Управление в технических, эргатических, организацион-

ных и сетевых системах"(Санкт-Петербург, 2012 г.), "7th Germán-Russian Logistics Workshop DR-LOG 2012"(Санкт-Петербург, 2012 г.), "Фундаментальные и прикладные исследования, разработка и применение высоких технологий в промышленности"(Санкт-Петербург, 2011 г.), а также семинаре "Fourth Workshop on Dynamic Games in Management Science"(Падуя, Италия, 2012 г.).

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

• аналитическое представление конкурентного равновесия по Вардропу в задаче распределения транспортных потоков на сетях с параллельными и частично совпадающими однородными и неоднородными путями и линейной BPR-фупкцией задержки;

• аналитическое представление системного оптимума Вардропа в задаче распределения транспортных потоков на сетях с параллельными и частично совпадающими однородными и неоднородными путями и линейной BPR-фупкцией задержки;

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

• двухуровневая теоретико-игровая модель распределения транспортных потоков и метод нахождения ситуации равновесия по Штакельбергу в условиях конкурентной маршрутизации;

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

ГЛАВА 1

МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ РАСПРЕДЕЛЕНИЯ ТРАНСПОРТНОГО ПОТОКА ОДНОЙ ГРУППЫ УЧАСТНИКОВ ДВИЖЕНИЯ

§ 1. Общая постановка задачи распределения транспортных потоков

В 1952 году Вардроп предположил, что любая транспортная система, по прошествии некоторого времени, приходит в равновесное состояние, сформулировав два принципа равновесного распределения транспортных потоков [67]. Согласно первому принципу: «Время передвижения по всем используемым маршрутам одинаково для всех участников движения, и меньше времени, которое потратит любой участник движения, изменив свой маршрут», а согласно второму принципу: «Среднее время передвижения является минимальным».

Впервые математическую формулировку данных принципов предложил Бекманн [35]. Впоследствии, предложенная математическая модель стала классической [62], и, на сегодняшний день, является одним из ключевых конструктов в теории транспортных потоков [4, 69]. Приведем общую постановку задачи распределения транспортных потоков. Как это принято в теории транспортных потоков, будем понимать под транспортным потоком количество автомобилей, проезжающих через элемент транспортной сети в единицу времени.

В качестве модели транспортной сети будем рассматривать ориентированный граф состоящий из множества последовательно пронумерованных узлов и множества последовательно пронумерованных дуг [62, 29]. Введем обозначения: N - множество последовательно пронумерованных узлов графа (7; А -множество последовательно пронумерованных дуг графа С; /2 - множество узлов, являющихся районами отправления, К С ./V; Б - множество узлов, являющихся районами прибытия, С подразумевается, что Я П 5 = 0; КГ8 -

множество маршрутов между районом отправления г Е R и районом прибытия s Е S] ха - транспортный поток по дуге а Е А, х = (...,ха,...); da(xa) - время передвижения (задержка) по дуге a G A] f£s - транспортный поток но маршруту к Е Krs\ Frii - совокупный транспортный спрос между районом отправления г Е R и районом прибытия s Е 5; - индикатор:

J 1, если дуга а Е Л 11 входит" в маршрут /с Е Я"™;

Од — ч

[О, в противном случае.

Математическая формализация первого и второго принципов Вардропа возможна в виде задач минимизации с ограничениями [35], при этом множества ограничений у обеих задач одинаковы и имеют вид:

J2frks = Frs VreR,seS, (1.1)

keKrs

frks ^ О У к Е Kra, г eR,seS} (1.2)

при условии, что

= VaEA, (1.3)

т-еД seS

целевые же функционалы различаются. Так для реализации первого принципа Вардропа необходимо при заданных выше ограничениях (1.1)-(1.3) решить задачу минимизации:

ГХ

ги\хие) = ттУ" / °da(u)du, (1.4)

х —' /п

aeA J(]

а в соответствии со вторым принципом при тех же ограничениях решить задачу:

(1.5)

X --

аеА

Следуя Шэффи (Sheffi Y.) [62], будем полагать, что решение оптимизационной задачи (1.4) с ограничениями (1.1)-(1.3) приводит транспортные потоки между парами районов отправления-прибытия к конкурентному равновесию (user-equilibrium), а решение оптимизационной задачи (1.5) с ограничениями (1.1)-

(1.3) - к системному оптимуму (system optimum). Будем называть эти решения конкурентным равновесием и системным оптимумом Вардроиа соответственно.

§ 2. Методы решения задачи распределения транспортных потоков

Среди основных недостатков классической формулировки равновесия по Вардропу, касающихся применения модели па практике, можно выделить чрезвычайно трудоемкие вычисления, когда сеть становится довольно большой [1]. При этом, трудоемкость вычислений обусловлена тем, что решение задачи о равновесном распределении потоков в общем случае можно получить только численными методами. Наиболее распространенным методом численного решения задач (1.4) и (1.5) с ограничениями (1.1)-(1.3) является алгоритм Франка-Вульфа [42].

В задаче распределения транспортных потоков мегаполиса нас, прежде всего, интересует разработка и использование быстродействующих алгоритмов для создания эффективных приложений решения конкретных транспортных проблем. Другими словами, в настоящем исследовании мы заинтересованы в решении задачи распределения потоков больше с точки зрения возможности практического применения полученных результатов. В частности, мы будем использовать идею, согласно которой транспортную сеть произвольной топологии следует представлять в виде множества пар районов отправления-прибытия, соединенных между собой набором параллельных маршрутов [53]. В результате использования данной идеи удается свести задачу маршрутизации транспорта на произвольной УДС к множеству однотипных задач распределения транспортного потока между двумя узлами по параллельным маршрутам и получить равновесные по Вардропу распределения транспортного потока в явном виде. В свою очередь, явный вид полученных распределений дает возможность существенно сократить временные затраты на вычисления [7, 70].

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

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

§ 3. Структуры транспортных сетей

Трудоемкость нахождения равновесных по Вардропу распределений транспортных потоков при решении описанных в первом параграфе оптимизационных задач, очевидно, возрастает с увеличением мощностей множеств Кгз. В самом деле, чем больше маршрутов из района г в район в имеют одинаковые дуги, тем сложнее становятся вычисления (увеличивается количество индикаторов 6™к). Более детально ознакомиться с этим феноменом можно в [29]. В то же время, на практике, не всегда рационально включать в рассмотрение абсолютно все дуги транспортной сети. Бывает, что из-за некоторых дуг (подчас незначительных с практической точки зрения) алгоритм нахождения равновесных по Вардропу распределений транспортных потоков между парами районов отправления-прибытия "зацикливается"вблизи оптимального решения, но так до него дойти и не может [30].

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

щие значительную долю всего объема потоков на УДС. С одной стороны, целесообразность использования данной идеи описана в исследовании [39], согласно которому сужение дороги (использование несколькими маршрутами одной и той же дуги или системы дуг) всегда приводит к возникновению пробок при нарастании потока во времени. С другой стороны, как было показано в [53, 54], предотвращение проявления в сети парадокса Браесса гарантируется конструированием транспортной сети таким образом, чтобы из района отправления в район прибытия потоки распределялись по параллельным (непересекающимся) маршрутам.

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

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

Похожие диссертационные работы по специальности «Дискретная математика и математическая кибернетика», 01.01.09 шифр ВАК

Список литературы диссертационного исследования кандидат наук Крылатов, Александр Юрьевич, 2014 год

ЛИТЕРАТУРА

1. Алиев А. С., Стрельников А. И., Швецов В. И., Шершевский Ю. 3. Моделирование транспортных потоков в крупном городе с применением к Московской агломерации // Автомат, и телемех. 2005. №11. С. 113-125.

2. Гавурин М. К., Малозсмов В. Н. Основы теории квадратичного программирования // Вестник ЛГУ. 1980. №1. С. 9-16.

3. Гавурин М. К., Малоземов В. Н. Экстремальные задачи с линейными ограничениями. Л.: Изд-во ЛГУ, 1984. 176 с.

4. Гаспиков A.B., Кленов С.Л., Нурминский Е.А., Холодов Я.А., Шамрай Н.Б. Введение в математическое моделирование транспортных потоков, [под ред. А. В. Гасникова, с приложениями М. Л. Бланка, Е. В. Гасниковой, А. А. Замятина и В. А. Малышева, А. М. Райгородского]. М.: Изд-во МФТИ, 2010. 360 с.

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

6. Захаров В.В., Крылатов А.Ю. Конкурентная маршрутизация транспортных потоков поставщиками услуг навигации // Управление большими системами. 2014. Вып. 49. С. 129-147.

7. Захаров В. В., Крылатов А. Ю. Системное равновесие транспортных потоков в мегаполисе и стратегии навигаторов: теоретико-игровой подход // МТИП. 2012. Т. 4. Вып. 4. С. 23-44.

8. Захаров В.В., Крылатов А.Ю. Современные проблемы использования интеллектуальной базы математического моделирования при борьбе с заторами в крупных городах России // Транспорт Российской Федерации. 2014. №4(53).

9. Зоркальцев В.И., Киселева М.А. Равновесие Нэша в транспортной модели с квадратичными затратами // Дискретн. анализ и исслед. опер. 2008. Т. 15. №3. С. 31-42.

10. Зырянов В.В., Кочерга В.Г., Поздняков М.Н. Современные подходы к разработке комплексных схем организации дорожного движения // Транспорт Российской Федерации. 2011. №1(32). С. 54-59.

11. Крепе B.JI. Конечные бескоалиционные игры с единственными ситуациями равновесия // Вестник Санкт-Петербургского университета. Серия 10: Прикладная математика. Информатика. Процессы управления. 2009. № 3. С. 55-62.

12. Крылатов А.Ю. Оптимальные стратегии управления транспортными потоками на сети из параллельных каналов // Вестн. С.-Петербург, ун-та. Сер. 10. Прикл. матем. Ипформ. Проц. упр. 2014. №2. С. 121-130.

13. Лагерев Р.Ю. Методика оценки матриц корреспонденций транспортных потоков по данным интенсивности движения: дис. ... канд. тех. наук: 05.22.10. - Иркутск, 2006. - 183 с.

14. Мазалов В.В. Математическая теория игр и приложения. СПб: Изд-во «Лань», 2010. 448 с.

15. Морозов И.И., Гасников A.B., Тарасов В.Н., Холодов Я.А., Холодов A.C. Численное исследование транспортных потоков на основе гидродинамических моделей // Компьютерные исследвоания и моделирование. 2011. Т.З. №4. С. 389-412.

16. Морозов И.И., Холодов Я.А. Моделирование динамики транспортных потоков // Труды 51-й научной конференции МФТИ «Современные проблемы фундаментальных и прикладных науюь. 2008. Т. 2. С. 128-129.

17. Нурминский Е.А., Шамрай Н.Б. Прогнозирование моделирования трафика Владивостока. // Труды МФТИ. 2010. Т. 2. №4. С. 119-129.

18. Петрович М.Л. Градостроительный подход к решению транспортных проблем городов // Транспорт Российской Федерации. 2010. №6(31). С. 21-25.

19. Петросян Л.А., Зенкевич H.A., Семина Е.А. Теория игр. М.: Высшая школа, 1998. 304 с.

20. Петросян Л.А., Кузютин Д.В. Устойчивые решения позиционных игр. СПб: Изд-во С.-Петербургского университета, 2008. 326 с.

21. Семенов В.В.Математические методы моделирования транспортных потоков // Сборник "Новое в синергетике. Новая реальность, новые проблемы, повое поколение". М.: Наука. 2007. С. 102-133.

22. Семенов В.В. Математическое моделирование динамики транспортных потоков мегаполиса. М.: ИПМ РАН, 2004. 44 с.

23. Семенов В.В. Смена парадигмы в теории транспортных потоков. М.: ИПМ РАН, 2006. 32 с.

24. Смирнов H.H., Киселцв A.B., Никитин В.Ф., Юмашев М.В. Математическое моделирование автомобильных потоков на магистралях // Вестник Московского университета. Серия 1. Математика и механика. 2000. № 4. С. 39-44.

25. Taxa Х.А. Введение в исследование операция. М.: Изд-во Вильяме, 2005. 902 с.

26. Уизем Дж. Линейные и нелинейные волны. М.: Мир, 1977. 624 с.

27. Хейт Ф. Математическая теория транспортных потоков. М.: Мир, 1966. 288 с.

28. Холодов Я.А., Холодов A.C., Гасников A.B., Морозов И.И., Тарасов В.Н. Моделирование транспортных потоков - актуальные проблемы и перспективы их решения // Труды МФТИ. 2010. Т. 2. № 4. С. 152-162.

29. Швецов В. И. Математическое моделирование транспортных потоков // Автомат, и телемех. 2003. № 11. С. 3-46.

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

31. Altman Е., Basar Т., Jimenez T., Shimkin N. Competitive routing in networks with polynomial cost // IEEE Transactions on Automatic Control. 2002. Vol. 47. № 1. P. 92-96.

32. Altman E., Combes R., Altman Z., Sorin S. Routing games in the many players regime // Proceedings of the 5th International ICST Conference on Performance Evaluation Methodologies and Tools. 2011. P. 525-527.

33. Altman E., Wynter L. Eguilibrium, games, and pricing in transportation and telecommunication networks // Networks and Spatial Economics. 2004. Vol. 4. P. 7-21.

34. Altman E., Kameda, H. Equilibria for Multiclass Routing in Multi-Agent Networks // Decision and Control, 2001. Proceedings of the 40th IEEE Conference on. Vol. 1. 2001. P. 604-609.

35. Beckmann M. J., McGuire C. B., Winston C. B. Studies in the Economics of Transportation. New Haven, CT: Yale University Press, 1956. 359 p.

36. Boyce D. Future research on urban transportation network modeling // Regional science and Urban Economics. 2007. №37. P. 427-481.

37. Castillo E., Mencndcz J.M., Jimenez P. Trip matrix and path flow reconstruction and estimation based on plate scanning and link observations // Transport Research Part B. 2008. Vol. 42. P. 455-481.

38. Castillo, E., Menendez, J.M., Sanchez-Cambronero, S. Traffic estimation and optimal counting location without path enumeration using Bayesian networks // Computer Aided Civil and Infrastructure Engineering. 2008. Vol. 23. № 3. P. 189-207.

39. Daganzo C. F. The cell transmission model: A dynamic representation of highway traffic consistent with the hydrodynamic theory // Transpn. Res. B. 1994. Vol. 28. P. 269-287.

40. Dantzig, G.B., Harvey, R.P., Lansdowne, Z.F., Robinson, D.W., Maier, S.F. Formulating and solving the network design problem by decomposition // Transportation Research Part B. 1979. Vol. 13. № 1. P. 5-17.

41. Farahani R.Z., Miandoabchi E., Szeto W.Y., Rashidi H. A review of urban transportation network design problems // European Journal of Operational Research. 2013. №229. P. 281-302.

42. Frank M., Wolfe P. An algorithm for quadratic programming // Naval Res. Logistics Quarterly. 1956. Vol. 3. P. 95-110.

43. Friesz T.L. Transportation network equilibrium, design and aggregation: key developments and research opportunities // Transportation Research Part A. 1985. Vol. 19. P. 413-427.

44. Greenshields B.D.A study of traffic capacity // Proc. (US) highway research, board. 1934. V. 14. P. 448-494.

45. Haurie A., Marcotte P. On the relationship between Nash-Cournot and Wardrop Equilibria // Networks. 1985. Vol. 15. P. 295-308.

46. Hollander Y., Prashker J.N. The applicability of non-cooperative game theory in transport analysis // Transportation. 2006. № 33. P. 481-496.

47. Horowitz A. J. Delay/Volume Relations for Travel Forecasting Based upon the 1985 Highway Capacity Manual. U.S. Department of Transportation, Federal Highway Administration. 1991. 87 p.

48. Kerner B.S. Introduction to modern traffic flow theory and control: the long road to three-phase traffic theory. Berlin: Springer. 2009. 265 p.

49. Kerner B.S. Experimental Features of SelflJOrganization in Traffic Flow // Phys. Rev. Let. 1998. Vol. 81. № 20. P. 3797-3800.

50. Kerner B.S., Rehborn H. Experimental features and characteristics of traffic jams // Phys. Rev. E. 1996. Vol. 53. № 2. P. 1297-1300.

51. Kerner B.S., Rehborn H. Experimental properties of complexity in traffic flow // Phys. Rev. E. 1996. Vol. 53. № 5. P. 4275-4278.

52. Kerner B.S., Rehborn H. Experimental Properties of Phase Transitions in Traffic Flow // Phys. Rev. Let. 1997. Vol. 79, №20. P. 4030-4033.

53. Korilis Y. A., Lazar A. A., Orda A. Architecting noncooperative networks // IEEE Journal on selected areas in communications. 1995. Vol. 13. № 7. P. 12411251.

54. Korilis Y. A., Lazar A. A., Orda A. Avoiding the Braess paradox in non-cooperative networks //J. Appl. Prob. 1999. Vol. 36. P. 211-222.

55. Kuhn H. W. Nonlinear programming: a historical view // In: SIAM-AMS Proceedings. Vol. IX. AMS, Providence, 1976. P. 1-26.

56. Li X., Ouyang Y. Reliable sensor deployment for network traffic surveillance // Transportation Resaerch Part B. 2011. Vol. 45. P. 218-231.

57. Ligthill M.J., Whitham F.R.S. On kinetic waves II. A theory of traffic flow on crowded roads // Proc. of the Royal Society Ser. A. 1995. Vol. 229. № 1178. P. 317-345.

58. Magnanti T.L., Wong R.T. (1984) Network design and transportation planning: models and algorithms // Transportation Science. Vol. 18. № 1. P. 1-55.

59. Medina A., Taft N., Salamatian K., Bhattacharyya S., Diot C. Traffic matrix estimation: existing techniques and new directions // Proceedings of the 2002 conference on Applications, technologies, architectures, and protocols for computer communications. 2002. P. 161-174.

60. Minguez R., Sanchez-Cambronero S., Castillo E., Jimenez P. Optimal traffic plate scanning location for OD trip matrix and route estimation in road networks // Transportation Research Part B. 2010. Vol. 44. P. 282-298.

61. Orda A., Rom R., Shimkin N. Competitive routing in multiuser communication networks // IEEE/ACM Transactions on Networking. 1993. Vol. 1. № 5. P. 510-521.

62. Sheffi Y. Urban transportation networks: equilibrium analysis with mathematical programming methods. Prentice-Hall, Inc, Englewood Cliffs, N.J. 1985. 416 p.

63. Shen W., Wynter L. A new one-level convex optimization approach for estimating origin-destination demand // Transportation Research Part B. 2012. Vol. 46. P. 1535-1555.

64. Simonelli F., Marzano V., Papola A., Vitiello I. A network sensor location procedure accounting for o-d matrix estimate variability // Transportation Research Part B. 2012. Vol. 46. P. 1624-1638.

65. Tong C. O., Wong S. C. A predictive dynamic traffic assignment model in congested capacity-constrained road networks // Transportation Research Part B. 2000. Vol. 34. P. 625-644.

66. U.S. Bureau of Public Roads, editor. Traffic Assignment Manual. U.S. Department of Commerce, Washington, D.C., 1964. 358 p.

67. Wardrop J. G. Some theoretical aspects of road traffic research // Proc. Institution of Civil Engineers. 1952. Vol. 2. P. 325-378.

68. Xie F., Levinson D. Modeling the growth of transportation networks: a comprehensive review // Netw Spat Econ. 2009. №9. P. 291-307.

69. Yang H., Huang H.-J. The multi-class, multi-criteria traffic network equilibrium and systems optimum problem // Transportation Research Part B. 2004. Vol. 38. P. 1-15.

70. Zakharov V., Krylatov A., Ivanov D. Equilibrium traffic flow assignment in case of two navigation providers // IFIP Advances in Information and Communication Technology, 2013. Vol. 408, Collaborative Systems for Reindustralization, 14th IFIP WG 5.5 Working Conference on Virtual Enterprises, PRO-VE 2013, Dresden, Germany, Proceedings. P. 156-163.

71. Zhuge H. Semantic linking through spaces for cyber-physical-socio intelligence: A methodology // Artif Intell. 2011. Vol. 175. № 5. P. 988-1019.

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