Содержание к диссертации
Введение
ГЛАВА 1. Математическое моделирование распределения транспортного потока одной группы участников движения 12
1. Общая постановка задачи распределения транспортных потоков . 12
2. Методы решения задачи распределения транспортных потоков . 14
3. Структуры транспортных сетей 15
4. Оптимальное распределение транспортных потоков на сети с неоднородными параллельными путями17
5. Транспортная сеть с подсетями из параллельных неоднородных каналов 29
6. BPR-функция задержки и парадокс Браесса 35
ГЛАВА 2. Распределение транспортных потоков в много-агентных транспортных системах 48
1. Конкурентная маршрутизация транспортных потоков 48
2. Общая постановка задачи распределения транспортных потоков с множеством групп участников движения51
3. Модель с множеством групп участников на сети из параллельных каналов 53
4. Сравнение равновесий по Вардропу и по Нэшу 60
5. Равновесие для маршрутов с общими дугами 62
6.Двухуровневая модель распределения транспортных потоков. 77
ГЛАВА3.Матрицы корреспонденций 83
1. Матрицы корреспонденций в задаче распределения транспортных потоков 83
2. Методы построения матриц корреспонденций 87
3.Данные видео регистрации транспортных средств и оценка матриц корреспонденций 90
4. Идентификация транспортных потоков между районами отправления-прибытия 94
5. Задача распределения датчиков систем видео регистрации транспортных потоков 98
Заключение 100
Литература 101
- Оптимальное распределение транспортных потоков на сети с неоднородными параллельными путями
- Общая постановка задачи распределения транспортных потоков с множеством групп участников движения
- Двухуровневая модель распределения транспортных потоков
- Данные видео регистрации транспортных средств и оценка матриц корреспонденций
Введение к работе
Актуальность темы и степень ее разработанности. На протяжении последних ста лет активно развивается теория транспортных потоков. Основы математического моделирования дорожного движения были заложены в 1912 году русским ученым, профессором Г.Д. Дубелиром, а развитие этого направления связано с именами Б.Д. Гриншильда, М. Лайтхила , Дж. Уизема, Ф. Хейта, Б. Кернера, Я.А. Холодова, В.И. Щвецова и др. Определяющий вклад в постановку и решение задач распределения и управления транспортными потоками внесли J.G. Wardrop, M. Beckmann, Y. Sheffi. Различным аспектам исследования конкурентного взаимодействия на транспортной сети и разработке для этих целей теоретико-игрового подхода посвящены публикации Е. Альтмана, Т. Башара, В.В. Захарова, В.И. Зоркальцева, А. Лазара.
В современных условиях наибольшее влияние на распределение транспортных потоков могут оказывать администрация города, а также поставщики услуг навигации, количество клиентов у которых неуклонно возрастает. При этом, если административное влияние может быть реализовано через опосредованные инфраструктурные или организационные преобразования, то поставщики услуг навигации, предлагая маршруты движения своим клиентам, оказывают непосредственное влияние на процесс распределения транспортных потоков в режиме он-лайн. В связи с этим, разработка новых подходов к моделированию транспортных потоков в условиях конкурентной маршрутизации и методов нахождения равновесных стратегий распределения потоков поставщиками услуг навигации является актуальной исследовательской задачей, решение которой еще не нашло достаточного отражения в научных публикациях.
Существенную роль для практического применения методов математического моделирования распределения транспортных потоков играет точность задания объемов потоков транспорта, направляющегося по имеющимся маршрутам между районами отправления и прибытия. Основным инструментом получения этих объемов считаются матрицы кор-респонденций (OD-matrix). Различным подходам и методам расчета матриц корреспон-денций посвящено много исследований, однако проблеме получения значений элементов матриц корреспонденций на основе систем видео регистрации номеров автомобилей на больших улично-дорожных сетях посвящено еще незначительное число публикаций.
Целью диссертационной работы является построение и исследование многоагентных математических моделей распределения и управления транспортными потоками в условиях ограниченных инфраструктурных мощностей мегаполиса. Для достижения поставленной цели в работе ставятся и решаются следующие задачи:
-
Построение и исследование математических моделей распределения транспортных потоков c BPR-функцией задержки на сетях с параллельными и частично совпадающими однородными и неоднородными маршрутами.
-
Исследование теоретико-игровых моделей распределения транспортных потоков с множеством групп участников движения и с использованием BPR-функции задержки.
-
Получение условий существования ситуаций равновесия по Нэшу в бескоалиционных играх распределения транспортных потоков и ситуаций равновесия по Штакельбергу в двухуровневых играх.
-
Разработка методов нахождения и аналитического представления ситуаций равновесия по Вардропу и Нэшу. Проведение сравнительного анализа полученных решений.
5. Разработка и реализация быстродействующих алгоритмов расчета значений корре-спонденций между районами отправления-прибытия на основе информации систем видео регистрации транспортных потоков.
Методы исследований. В процессе проведения исследования автор опирался на научную методологию проведения исследования, общепризнанные принципы и подходы к исследовательской деятельности в области прикладной математики, методы теории оптимизации и теории игр.
Научную новизну работы составляют следующие результаты, выносимые на защиту:
-
Аналитическое представление конкурентного равновесия по Вардропу в задаче распределения транспортных потоков на сетях с параллельными и частично совпадающими однородными и неоднородными путями.
-
Аналитическое представление системного оптимума Вардропа в задаче распределения транспортных потоков на сетях с параллельными и частично совпадающими однородными и неоднородными путями.
-
Необходимые и достаточные условия существования и аналитическое выражение равновесия по Нэшу в задаче распределения транспортных потоков при наличии множества конкурирующих групп участников движения на сетях с параллельными и частично совпадающими однородными и неоднородными путями.
-
Математическая двухуровневая модель распределения транспортных потоков и метод выработки решений по реконструкции транспортной сети произвольной топологии, основанный на аналитическом представлении распределений потоков автотранспорта в многоагентной транспортной системе.
-
Методика и алгоритм восстановления матриц корреспонденций, основанный на информации систем фиксации регистрационных номерных знаков автотранспорта.
Теоретическая и практическая значимость. Результаты исследования вносят вклад в развитие теории игр и ее приложений в задачах маршрутизации транспортных потоков и могут найти применение при принятии решений о реконструкции улично-дорожных сетей крупных городов.
Апробация результатов. Результаты исследования докладывались и обсуждались на семинарах кафедры математического моделирования энергетических процессов факультета прикладной математики – процессов управления СПбГУ, на семинарах Института проблем транспорта им. Н.С. Соломенко РАН и на международных конференциях: "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 German-Russian Logistics Workshop DR-LOG 2012"(Санкт-Петербург, 2012 г.), "Фундаментальные и прикладные исследования, разработка и применение высоких технологий в промышленности"(Санкт-Петербург, 2011 г.), а также семинаре "Fourth Workshop on Dynamic Games in Management Science"(Падуя, Италия, 2012 г.).
Выполненный в ходе работы над диссертацией проект «Оптимизация структуры улично-дорожной сети большого города» был отмечен дипломом победителя конкурса грантов
Санкт-Петербурга для студентов, аспирантов, молодых ученых, молодых кандидатов наук 2013 г.
Публикации. По теме диссертации опубликовано 10 работ, в том числе 4 в изданиях из перечня ВАК, 1 - в периодическом издании, индексируемом в Scopus. Работы [1, 4, 5, 9] написаны в соавторстве. В работе [1] А.Ю. Крылатову принадлежит доказательство теоремы, предлагающей аналитическое выражение равновесных по Нэшу стратегий распределения транспортных потоков конкурирующими поставщиками услуг навигации и доказательства вспомогательных утверждений (лемм и следствий), также диссертант нашел условия при которых появление конкурирующих между собой навигационных систем может разве что только увеличить среднее время прохождения транспортных потоков по сети из параллельных каналов. В работе [4] диссертант получил условия для нахождения равновесия по Штакельбергу в двухуровневой игре лидер (администрация) - последователь (поставщики услуг навигации). В [5] А.А. Крылатовым были подготовлены раздела III-IV. В [9] диссертанту принадлежит формулировка и доказательство леммы и теоремы, а соавторам - постановка задачи и выбор методов решения.
Объем и структура работы. Диссертация объемом 107 страниц состоит из введения, трех глав, заключения и списка используемой литературы, включающего 71 наименование. Работа содержит 15 рисунков и 3 таблицы.
Оптимальное распределение транспортных потоков на сети с неоднородными параллельными путями
Трудоемкость нахождения равновесных по Вардропу распределений транспортных потоков при решении описанных в первом параграфе оптимизационных задач, очевидно, возрастает с увеличением мощностей множеств Krs. В самом деле, чем больше маршрутов из района г в район s имеют одинаковые дуги, тем сложнее становятся вычисления (увеличивается количество индикаторов 6та\). Более детально ознакомиться с этим феноменом можно в [29]. В то же время, на практике, не всегда рационально включать в рассмотрение абсолютно все дуги транспортной сети. Бывает, что из-за некоторых дуг (подчас незначительных с практической точки зрения) алгоритм нахождения равновесных по Вардропу распределений транспортных потоков между парами районов отправления-прибытия "зацикливается"вблизи оптимального решения, но так до него дойти и не может [30].
Избежать подобных проблем можно, в частности, воспользовавшись идеей представления транспортной сети произвольной топологии в виде множества пар районов отправления-прибытия r-s, соединенных между собой набором параллельных маршрутов Krs. В основе такой идеи лежит предположение о том, что основные потоки между районами отправления и прибытия не должны пересекаться. Здесь под основными потоками мы понимаем наиболее значимые по своему объему потоки между районами отправления и прибытия, составляющие значительную долю всего объема потоков на УДС. C одной стороны, целесообразность использования данной идеи описана в исследовании [39], согласно которому сужение дороги (использование несколькими маршрутами одной и той же дуги или системы дуг) всегда приводит к возникновению пробок при нарастании потока во времени. С другой стороны, как было показано в [53, 54], предотвращение проявления в сети парадокса Браесса гарантируется конструированием транспортной сети таким образом, чтобы из района отправления в район прибытия потоки распределялись по параллельным (непересекающимся) маршрутам.
Предположим, что УДС представлена в виде множества пар районов отправления-прибытия r-s, для каждой из которых множество Krs состоит из параллельных маршрутов. Более того, мы будем считать, что множества Krs и Kqp для любых районов отправления r и q и районов прибытия s и p не имеют общих дуг. Такое предположение представляется разумным и с практической точки зрения, так как в действительности позволит определять, в каком именно месте необходимо построить мост, виадук или туннель в первую очередь (то есть убрать пересечение между основными транспортными потоками города). Таким образом получаем, что разные пары районов отправления и прибытия являются независимыми друг от друга в смысле использования соответствующими потоками ресурсов транспортной сети. В связи с этим, мы можем сформулировать задачу равновесного по Вардропу распределения транспортного потока для любой пары районов отправления и прибытия, и полученные результаты смогут быть перенесены на любую другую пару районов.
При этом следует отметить, что представление транспортной сети произвольной топологии в виде множества подсетей, состоящих из одной пары районов отправления-прибытия и набора параллельных маршрутов, является частным случаем метода декомпозиции [40, 43] задачи поиска равновесного распределения транспортного потока. Основным преимуществом такого частного случая является простота получения аналитического решения, однако ясно, что это не единственная структура сети, по отношению к которой существует возможность получения решений в явном виде. В настоящем исследовании мы также рассмотрим ромбовидную структуру транспортной сети и транспортную сеть с двумя истоками, одним стоком и общей дугой для движения. Более того, в качестве примера будут рассмотрены случаи формирования сети из параллельных каналов, а также сети с подсетями из параллельных каналов на прямоугольной регулярной (состоящей из одинаковых геометрических элементов) транспортной сети.
Оптимальное распределение транспортных потоков на сети с неоднородными параллельными путями
Перейдем к математической постановке задачи равновесного по Вардропу распределения транспортного потока, в качестве транспортной сети в которой будет выступать ориентированный граф, состоящий из одного района отправления, одного района прибытия и n параллельных путей, каждый из которых состоит из нескольких последовательных дуг, характеризующихся разными значениями пропускной способности и времени свободного движения. Такие пути будем называть неоднородными (рисунок 1.1). В качестве функции задержки выберем BPR-функцию, довольно часто используемую на практике региональными Бюро общественных дорог (Bureau of Public Road) США, которые обеспечивают монитроинг трафика при изучении движения транспорта по отдельным сегментам УДС [47, 66].
Введем обозначения: і номер маршрута, і Є {1,... ,n}; k количество последовательно пронумерованных дуг маршрута i; F 0 - объем общего транспортного потока из района отправления в район прибытия; ft 0 - объ ем транспортного потока, направляемого по i-му маршруту; f = (f1, . . . , fn) – вектор распределения транспортного потока по n маршрутам; t0il – время свободного движения по l-ой дуге i-го маршрута; t0i = lli=1 t0il – время свободного движения по i-му маршруту; cil 0 – пропускная способность l-ой дуги i-го маршрута; dil(fi) 0 – функция задержи потока fi на l-ой дуге маршрута i.
Общая постановка задачи распределения транспортных потоков с множеством групп участников движения
В условиях повышенной загрузки ограниченных инфраструктурных мощностей улично-дорожных сетей (УДС) крупных городов крайне актуальной является задача оценки распределения транспортных потоков на сети и маршрутизации транспорта. В современных условиях наибольшее влияние на распределение транспортных потоков могут оказывать администрация города, а также поставщики услуг навигации, количество клиентов у которых неуклонно возрастает. При этом, если административное влияние может быть реализовано через опосредованные инфраструктурные или организационные преобразования [7], то поставщики услуг навигации, предлагая маршруты движения своим клиентам, оказывают непосредственное влияние на процесс распределения транспортных потоков в режиме он-лайн [70]. В настоящем исследовании нас будут интересовать стратегии распределения транспортных потоков поставщиками услуг навигации. Следует также отметить, что вопрос организации работы различных систем навигации актуален и с точки зрения исследования кибер-физических систем [71].
Важнейшей концепцией в области распределения транспортных потоков на УДС города является равновесие по Вардропу [29, 67], рассматриваемое в двух контекстах. Первый состоит в предположении, что транспортные потоки в течение определенного периода времени сами приходят в равновесное по Вардропу состояние [4]. Второй заключается в том, что администрация УДС, доступными ей средствами, приводит транспортные потоки на сети в равновесное по Вардро-пу состояние [69]. В данной работе мы будем исследовать проблему конкурентной маршрутизации (competitive routing) – когда на сети действует несколько поставщиков услуг навигации, и каждый из них стремится распределить транспортный поток своих клиентов наилучшим образом (например, предлагая своим клиентам наиболее быстрые маршруты) [31, 32, 61]. Навигаторы, как правило, выбирают решения о маршрутах своих клиентов независимо от действий других навигаторов, ориентируясь лишь на имеющуюся у них информацию о текущей дорожной обстановке. Однако следует заметить, что время перемещения потока по выбранному навигатором маршруту будет зависеть не только от объема этого потока, но и от потоков, направляемых по тому же маршруту другими навигаторами. В этом случае в качестве модели конкурентной маршрутизации представляется целесообразным использовать бескоалиционную игру (игроки – поставщики услуг навигации), а в качестве принципа оптимальности – равновесие по Нэшу. Ситуация равновесия по Нэшу представляет собой набор стратегий игроков, от которых невыгодно отклоняться каждому из них, если все другие игроки придерживаются своих равновесных стратегий. Известно, что если ситуация равновесия по Нэшу единственна, то игрокам для реализации равновесия не требуется прибегать к услугам какого-либо посредника, координирующего их действия. Естественно, что в таком случае вопрос о соотношении равновесных по Нэшу и по Вардропу состояний системы вызывает исследовательский интерес.
Впервые вопрос о соотношении равновесий по Нэшу и Вардропу был рассмотрен в [45], где в качестве игроков были взяты пары районов отправления-прибытия. В работе было показано, что равновесие по Нэшу в поставленной задаче стремится к равновесию по Вардропу, при определенных условиях. Однако, несмотря на естественный интерес к такого рода исследованиям, работа [45] так и осталась, по большому счету, единственной в своем роде. Конечно, существуют работы, в которых поднимается вопрос о соотношении двух видов равновесия, как например [33], однако, к сожалению, ставится он в большей степени в дискуссионной форме и, как правило, не касается аналитической формы представления оптимальных решений. Общая постановка транспортной задачи с несколькими перевозчиками, в которой затраты на перевозки по отдельным дугам каждого участника являются квадратичной функцией от объемов перевозимых им грузов при фиксированных объемах перевозок других участников, описана в работе [9]. В ней показано, что задача поиска равновесия Нэша для этой модели сводится к решению задачи выпуклого квадратичного программирования. Предлагаемая в нашей работе модель конкурентной маршрутизации, являясь частным случаем рассмотренной авторами модели, позволяет описать равновесные по Нэшу стратегии маршрутизации в аналитическом виде.
В данной главе, как и в предыдущей, исследуя проблему распределения транспортных потоков, мы будем опираться на идею, согласно которой УДС произвольной топологии следует представлять набором независимых подсетей, каждая из которых состоит из двух узлов (районы отправления и прибытия) и параллельных маршрутов [12]. Будем считать, что УДС представлена в виде множества независимых (не имеющих общих дуг) подсетей, каждая из которых содержит одну пару районов отправления-прибытия и определенное количество параллельных маршрутов. В связи с этим, мы можем сформулировать задачу конкурентной маршрутизации для любой пары районов отправления-прибытия, и перенести полученные результаты на любую другую пару районов. Более того, сопоставление полученных равновесных по Нэшу стратегий распределения транспортных потоков со стратегиями равновесными по Вардропу мы также можем проводить для отдельно взятой пары районов отправления-прибытия (подсети) УДС [53, 54].
Таким образом, в данной статье мы будем рассматривать задачу маршрутизации транспортных потоков конкурирующими поставщиками услуг навигации (Навигаторами) на УДС большого города, представленной как совокупность подсетей, включающих в себя пары районов оправления-прибытия. В силу того, что каждый Навигатор должен принимать решения о маршрутизации своих клиентов с учетом постоянно обновляющейся информации об улично-дорожной ситуации в режиме он-лайн, крайне важно для сокращения времени принятия решений иметь явный вид стратегий распределения транспортных потоков.
Пусть имеется т 2 поставщиков услуг навигации на УДС. Все Навигаторы стремятся минимизировать общее время движения транспортных средств своих клиентов. При этом, в качестве оценки времени движения транспортного потока по дуге любой подсети выберем BPR-функцию задержки [66], часто используемую Бюро общественных дорог в США. Ситуации равновесия по Нэшу в сформулированной игре на подсети из параллельных каналов будут найдены в явном виде. Более того, будет показано, что если на транспортной сети появляются конкурирующие между собой поставщики услуг навигации, то среднее время передвижения транспортных потоков между районами отправления-прибытия может только увеличится, по сравнению с тем, которое может обеспечить одна централизованная система навигации.
В качестве модели транспортной сети будем рассматривать ориентированный граф G, состоящий из множества последовательно пронумерованных узлов и множества последовательно пронумерованных дуг. На сети G распределяют транспортные потоки своих клиентов т 2 Навигаторов. Введем следующие обозначения: N - множество последовательно пронумерованных узлов графа G; А - множество последовательно пронумерованных дуг графа G; R- множество узлов, являющихся районами отправления, R С N; S - множество узлов, являющихся районами прибытия, S С N; подразумевается, что RC\S = 0; Krs -множество маршрутов между районом отправления г Є Л и районом прибытия s Є S; ха - транспортный поток по дуге а Є А, х = (... , жа,...); da(xa) - время передвижения (задержка) потока объемом ха по дуге а Є Л; М = {1,... ,ш} - множество номеров Навигаторов; F rs 0 величина транспортного потока (число клиентов), распределяемого Навигатором j между районом отправления г Є Л и районом прибытия s Є S; Frs = Y%=i FJ,rs – совокупный транспортный спрос между районом отправления г Є Л и районом прибытия s Є S; xJa-величина транспортного потока, направляемого Навигатором j по дуге а Є А,
Двухуровневая модель распределения транспортных потоков
Рассмотрим бескоалиционную игру Г(с,/1,/2) типа лидер-последователь, где лидер - администрация мегаполиса, а два последователя - поставщики навигационных услуг. Администрация (лидер) стремится найти оптимальное распределение пропускных способностей на существующих п параллельных маршрутах из пункта отправления в пункт прибытия с = (сі,..., сп) и соответствующий системный оптимум / = (/і,..., /п) с тем, чтобы минимизировать общее время движения транспорта по УДС. В свою очередь, поставщики навигационных услуг (последователи), реагируя на заданное администрацией (лидером) распределение пропускных способностей среди возможных маршрутов движения с = (сі,... ,сп), в процессе конкуренции достигают равновесного по Нэшу перераспределения своих клиентов по УДС.
В силу того, что клиенты поставщиков навигационных услуг (последователи) являются составной частью общего транспортного потока /, их реакция на заданное администрацией (лидером) распределение пропускных способностей, в общем случае, может нарушить системное равновесие и тем самым увеличить общее время движения транспорта по УДС. Таким образом, администрации (лидеру) следует заранее учитывать реакцию поставщиков навигационных услуг (последователей) и именно с поправкой на эту реакцию искать оптимальное распределение пропускных способностей для движения по существующим параллельным маршрутам и соответствующее оптимальное распределение транспортных потоков. Следует отметить, что в таком случае речь уже не будет идти о системном равновесии, но - о равновесии по Штакельбергу.
Будем считать, что имеется два поставщика навигационных услуг: Навигатор 1 и 2. Тогда структура общего транспортного потока имеет вид: где / = (/ь...,/п) - общий транспортный поток ("=1/i = F); f = (/iV-- /n) - транспортный поток, состоящий из клиентов Навигатора 1 (Г=і// = Fl); Р = (/? - /n) - транспортный поток, состоящий из клиентов Навигатора 2 (i ft = F2); h = (hh ..., /in) - транспортный поток, не пользующийся услугами Навигаторов 1 и 2. Через t{ обозначим время свободного движения по маршруту і. Более того, будем считать, что h является оценкой системно равновесного транспортного потока, который не пользуется услугами Навигаторов 1 и 2, например, пропорциональной системно равновесному распределению:где - оптимальное распределение (системный оптимум) транспортного потока в задаче верхнего уровня, соответствующее набору с количества полос; м = 1 - 1-±-. Таким образом, ц характеризует долю общего транспортного потока, которая, не пользуясь услугами Навигаторов, действует так, как будто Навигаторов в принципе не существует, и все участники движения стремятся к состоянию системного равновесия.
В параграфе 3 найдены равновесные по Нэшу стратегии в игре нижнего уровня для случая, когда на сети не предполагается наличия транспортных потоков, не пользующихся услугами Навигаторов. В связи с этим, рассмотрим целевые функционалы Навигаторов в случае наличия свободного (не пользующегося услугами Навигаторов) транспортного потока:
Данные видео регистрации транспортных средств и оценка матриц корреспонденций
Пусть имеется сеть G, состоящая из узлов и дуг, соединяющие эти узлы. Пусть на заданном промежутке времени [0,T] по сети G передвигаются n маркированных агентов из одних узлов сети в другие, используя дуги. В определенных узлах сети находится m детекторов D = {d1,...,dm}. После прохождения заданного промежутка времени, получаем базу из связанных данных: (l,t, k) – номер зафиксированного агента; время фиксации; номер детектора, зафиксировавшего агент. На основании данных из полученной базы оцениваем матрицы корреспонденций между всеми парами районов отправления-прибытия, используя алгоритмический подход, описанный в 3. Следующим шагом является оценка маршрутов движения транспорта из района отправления в район прибытия.
Задача нахождения существующих распределений транспортного потока на заданной сети является крайне актуальной и довольно сложной вычислитель ной проблемой. Рассмотрим подход оценки маршрутов движения транспорта из района отправления в район прибытия, основанный на информации, получаемой с систем видеорегистрации номерных знаков. По прошествии периода времени [0,Т] формируется база данных В, состоящая из наборов (l,t,k). Затем эта база данных В разбивается на множество баз данных Bj, j Є , где - множество автомобилей зарегистрированных всеми детекторами за период зафиксировавших агент с номером j за период времени [0,T]. При этом t1 t2 ... tr. В таком случае набор номеров детекторов (k1, . . . , kr) является реконструкцией маршрута следования агента с номером j за период времени [0,T] мимо детекторов D.
Таким образом, при достаточно плотном покрытии транспортной сети детекторами реконструкция маршрутов движения транспортных потоков между районами отправления-прибытия происходит с высокой точностью. Однако, если покрытие детекторами не достаточно плотное, то возникает вопрос о восстановлении маршрутов движения транспортных потоков между детекторами. В таком случае можно воспользоваться следующей довольно распространенной где OV множество районов отправления-прибытия; V% множество маршрутов между г-ой парой районов отправления-прибытия; fik - искомый транспортный поток, движущийся между г-ой парой районов отправления-прибытия по маршруту к; / предшествующий (prior) транспортный поток; 7нМ2 2 -весовые коэффициенты, vd количество зафиксированных агентов детектором d Є D; 5dk - индикатор: 1, если детектор d Є D расположен на маршруте к Є Vi, О, в противном случае.
Следует отметить, что под предшествующим транспортным потоком в данного рода моделях понимается полученные (оцененные) ранее данные о движении транспорта между районами отправления-прибытия, что является несомненным недостатком данной модели. Таким образом, наилучший способ оценки маршрутов движения транспортных потоков между районами отправления-прибытия является плотное распределение детекторов системы видеорегистрации номеров агентов на транспортной сети.
В условиях ограниченного бюджета на закупку и расстановку детекторов системы видеорегистрации транспортных потоков возникает задача оптимального распределения детекторов при ограниченности ресурсов [60, 56]. Подразумевая под оптимальным распределением детекторов установку их минимального количества, соответствующая задача может быть сформулирована в виде следующей бинарной линейной программы [37]:Таким образом, решение данной задачи целочисленного программирования обеспечит ответ на вопрос оптимального распределения детекторов системы видеорегистрации транспортных потоков.
Основными результатами, полученными в ходе диссертационного исследования и выносимыми на защиту, являются следующие:
аналитическое представление конкурентного равновесия по Вардропу в задаче распределения транспортных потоков на сетях с параллельными и частично совпадающими однородными и неоднородными путями и линейной BPR-функцией задержки;
аналитическое представление системного оптимума Вардропа в задаче распределения транспортных потоков на сетях с параллельными и частично совпадающими однородными и неоднородными путями и линейной BPR-функцией задержки;
условия существования и аналитическое представление ситуаций равновесия по Нэшу в бескоалиционной игре конкурентной маршрутизации транспортных потоков на сетях с параллельными и частично совпадающими однородными и неоднородными путями и линейной BPR-функцией задержки;
двухуровневая теоретико-игровая модель распределения транспортных потоков и метод нахождения ситуации равновесия по Штакельбергу в условиях конкурентной маршрутизации;
методика использования информации систем видео регистрации транспортных потоков в узлах улично-дорожной сети для расчета корреспон-денций между районами отправления-прибытия мегаполиса.
