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

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

Крылатов Александр Юрьевич

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

Специальность 01.01.09 — Дискретная математика и математическая кибернетика

Автореферат

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

8 ОКТ 2014

Санкт-Петербург 2014

005553139

Работа выполнена в Санкт-Петербургском государственном университете.

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

Захаров Виктор Васильевич

Официальные оппо- Луценко Михаил Михайлович, ненты:

доктор физико-математических наук, профессор, Петербургский государственный университет путей сообщения, профессор

Гасратов Мансур Габибулахович,

кандидат физико-математических наук, Северо-Западный филиал ОАО «МегаФон», менеджер технического контроля

Ведущая организация: Санкт-Петербургский . экономико-

математический институт Российской академии наук

Защита состоится "22"октября 2014 г. в 17 часов на заседании диссертационного совета Д 212.232.29 на базе Санкт-Петербургского государственного университета по адресу: 199178, Санкт-Петербург, 10 линия В.О., д.33/35, ауд. 74.

С диссертацией можно ознакомиться в Научной библиотеке им. М. Горького Санкт-Петербургского государственного университета по адресу: 199034, Санкт-Петербург, Университетская наб., 7/9 и на сайте http://spbu.ru/science/ disser/dissertatsii-dopushchennye-k-zashchite-i-svedeniya-o-zashchite.

Автореферат разослан " " 2014 г.

Ученый секретарь

диссертационного

совета

Нежинский В. М.

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

Актуальность темы и степень ее разработанности. На протяжении последних ста лет активно развивается теория транспортных потоков. Основы математического моделирования дорожного движения были заложены в 1912 году русским ученым, профессором Г.Д. Дубелиром, а развитие этого направления связано с именами Б.Д. Гриншильда, М. Лайтхила , Дж. Уизема, Ф. Хейта,'Б. Кернера, Я.А. Холодова, В.И. Щвецова и др. Определяющий вклад в постановку и решение задач распределения и управления транспортными потоками внесли Л.в. \Vardrop, М. Вескшапп, У. БЬеШ. Различным аспектам исследования конкурентного взаимодействия на транспортной сети и разработке для этих целей теоретико-игрового подхода посвящены публикации Е. Альтмана, Т. Башара, В.В. Захарова, В.И. Зоркальцева, А. Лазара.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Апробация результатов. Результаты исследования докладывались и обсуждались на семинарах кафедры математического моделирования энергетических процессов факультета прикладной математики - процессов управления СПбГУ, на семинарах Института проблем транспорта им. Н.С. Соломенко РАН и на международных конференциях: "International conference on computer technologies in physical and engineering appIications"(CaH Петербург, 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] A.A. Крылатовым были подготовлены раздела III-IV. В [9] диссертанту принадлежит формулировка и доказательство леммы и теоремы, а соавторам — постановка задачи и выбор методов решения.

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

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

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

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

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

zuc(хм) = min Y" [ ° da{u)du, (1)

1 ÎtAJ*

и

Z"(r'°) = minViia(i<1)ia, (2)

X '

а€/4

соответственно, с ограничениями

= Vre R, se s, (3)

k€Kr.

fk">0 VA; e Krs,re R,s e S, (4)

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

= VaGyl' (5)

гея ses ыкг,

на графе G, где N — множество последовательно пронумерованных узлов графа G; А — множество последовательно пронумерованных дуг графа G; R — множество узлов, являющихся районами отправления, R С N; S - множество узлов, являющихся районами прибытия, S С jV; подразумевается, что R П S = 0; Кга - множество маршрутов между районом отправления r e R и районом прибытия s 6 S\ ха - транспортный поток по

дуге а € А, х = (...,!„,...); йа{ха) - время передвижения (задержка) по дуге а 6 А; -транспортный поток по маршруту к € Кт„\ Рга - совокупный транспортный спрос между районом отправления г 6 Я и районом прибытия я е 5; - индикатор:

, л, если дуга а & А "входит"в маршрут к е Кг„\ 0„1 ~ '

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

Разделы 1.2 и 1.3 посвящены обсуждению методов решения оптимизационных задач (1),(3)-(5) и (2)-(5) и возможности получения этих решений в явном виде. В качестве ключевой предлагается идея получения аналитических решений, основанная на методе декомпозиции транспортной сети произвольной топологии на подсети, равновесное распределение транспортного потока на которых находятся в явном виде.

В разделе 1.4 исследуется сеть, состоящая из одного района отправления и одного района прибытия, соединенных п неоднородными параллельными маршрутами. Каждый маршрут г состоит из U последовательно соединенных дуг, с временем свободного движения iy и пропускной способностью сц, где i = 1, п. Дополнительно вводится

П = jjj-^ . В качестве функции задержки используется BPR-функция: ¿¿¡(/¿) =

t% + Vi 6 {1, rt}, l € {1, ii}. Таким образом, задача (1) примет вид:

ь-(Г) = min J2 Е $ f1 + f) (7)

а задача (2) - вид:

при ограничениях

¿/i = i\ (8) ¡=1

fi^O Vi = Т7Й. (9)

При выполнении следующих условий, не умоляющих общности,

< 4 < - < t (ю)

справедлива

Теорема 1.4.1. Конкурентное равновесие в задаче (6), (8), (9), при условии (10), достигается реализацией следующих стратегий распределения транспортного потока:

/г = f -i?ri' при * * fcUC- Vie {I,n}, (11)

t 0, при г > к

V г Е {1,п}, где кие удовлетворяет условиям

к»■ к««

х: г4 с*2— -*?). <12)

при £Г=1г<(С1-*?) = °°-

Системный оптимум в задаче (7)-(9), при условии (10), достигается реализацией следующих стратегий распределения транспортного потока:

г={ У«е{1.п>. (13)

[ 0, при г >

V г £ {1,тг}, где к3" удовлетворяет условиям

(14)

. ¡=1 ¡=1

В разделе 1.5 рассматривается сеть состоящая из истока, стока и двух подсетей из параллельных неоднородных каналов, каждая из которых имеет по одной входной дуге из истока и по одной выходной дуге в сток сети (рисунок 1).

Рисунок 1. Схема транспортной сети

Опираясь на результаты Теоремы 1.4.1 удается найти решение задачи равновесного по Вардропу распределения транспортного потока в явном виде. 1 и 2 - номера выходящих из истока дуг, а п2 +1 и п2 + 2 - номера входящих в сток дуг. Первая подсеть имеет параллельные маршруты с номерами (3,..., щ), вторая подсеть - с номерами (щ + 1,...,п2). Дополнительно вводится г, = (£'¡=1 , г = и соотношения между потоками

по дугам и потоками по маршрутам: 11 = /" Х2 = /•> хз = Л' ^3 ~ ^,"2,

х„1+1 = ЕГ=з Л- = и При выполнении условий

С+1 * % < - < С (15)

справедлива

Теорема 1.5.1. Конкурентное равновесие в задаче распределения транспортного потока .Р по сети, представленной на рисунке 1, при условии (15), достигается реализацией следующих стратегий распределения транспортного потока: для г = 3, П1

pi.iV"1 /°г

1Г = и -Ли, (16)

Ь,=3 гз

0 о да^», о {0 + ^ + V

Ч + П2+2 + ч 1 "г+1 Е^зО У'2 у

^ + + + « + «4+« + Е&ч+.Ч

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

для г = rii + 1, П2

F2 4-V2 f°r-

¡г - г, ti:i="i+1 J (ig)

+1

где

to + ta , ,n ,n 'fr . Л? , C+. , i

, 'Vi | l . . . _ i

« ^ <=»2« ^ E^Tö + <* + + E;jni+1ry

(20)

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

F2> E (21)

¿="1+1

Системный оптимум в задаче в задаче распределения транспортного потока F по сети, представленной на рисунке 1, при условии (15), достигается реализацией следующих стратегий распределения транспортного потока: для i = 3, щ

F1 4- V"1 ü

f>° = г > 2 _ toÜ ,99n

где

f° + ¿0 , + - i° - t° - 4- 9 {4 f=Z±H. 4_ l _ \ r,

+ г,- 'i Wt-i -tji^T + 2 ^ + S^I + T^T^J F

To t® lö jö \ >

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

F'>f:ri(C-t°), (24)

для i = Щ + 1, rt2

где

iOri

f?» = г__^="1+1 '•J 2 _ -оП

F2_ 1+t">+1+ EiVi - f° — t° — ■'S"1 +1 fyi 2

t° 1 n1 4- ia. + £2±i + 1

Cn2 + 1 У 1 г- 1 c2

(26)

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

(27)

•=П1+1

: сети, с по-

Раздел 1.6 посвящен исследованию ромбовидной структуры транспортной < перечной диагональной дугой (рисунок 2). Опираясь на линейный вид ВРИ-функции задержки удается найти все возможные варианты равновесного по Вардропу распределения транспортного потока в зависимости от пропускных способностей, времени свободного

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

Рисунок 2. Схема транспортной сети

Следствие(к Теореме 1.6.2). Использование диагональной дуги в сети, представленной на рисунке 2 с ВРЯ-функциями задержки на дугах, ведет к проявлению парадокса Браесса в том случае, если:

• в качестве критерия оптимальности выбрано конкурентное равновесие и выполняются условия:

р1± + ~ + - +

*? 1 + ■

1 +

/о , ^оа. , 4-оа , ¿ос

у0 1/0

^ + ^Г + il~i.il.

> _С1 г-2 с5

1 ,__!_

-р—^г + ?!—;

+

в качестве критерия оптимальности выбран системный оптимум и выполняются условия:

1411 +

1 +

I ^оа. I 4. /оо.

Н + 2 С1 + С4с, ^ " Си

+

,0 1 I 1

Р +

1 I .. 1

21?" "г" И?21?

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

транспортных потоков.

В разделе 2.1 приведено краткое описание проблематики конкурентной маршрутизации транспортных потоков.

Раздел 2.2 отводится под формулировку игры поставщиков услуг навигации в общем

виде.

В разделе 2.3 изучается игра т поставщиков услуг навигации, стремящихся распределить транспортные потоки своих клиентов ^ > 0, j = 1 ,т = ]Гт=1 на сети из п параллельных маршрутов и линейной ВРИ-функцией задержки. По каждому маршруту г, с пропускной способностью с, и временем свободного движения Навигатор з направляет поток // > 0, Р =(/>,..., />) // = Также вводится = . Навигатор ] стремится1 минимизировать время движения потока своих клиентов. В связи с этим, рассматривается бескоалиционная игра максимизации выигрышей т игроков Гт(М, {#Л,ем), где У = > 0 Уг = // = € М, а

™ / V™

В качестве принципа оптимальности в этой игре рассматривается равновесие по Нэшу.

Определение 2.3.1. Равновесием по Нэшу в игре Гт называется такой набор стратегий /*, что

ЩГ) > у Г е у, з е м.

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

(28)

Теорема 2.3.1. Если Уj = 1 ,т выполняется

. (29)

то равновесие по Нэшу в игре Гт, при условии (28), достигается следующими стратегиями

1 т'

П (30)

9=1

где

/о V1" яс. с" I"11;

2^г=1 (О

Уг = 1, п, ] — 1, т.

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

■ ■ •' (■- ЬО ■+ §) *) . (32)

при ограничениях

п

= (33)

1=1

V» = (34)

где Fi - величина транспортного потока на г-ом маршруте.

Теорема 2.4.1. Сумма выигрышей игроков в игре Г,„ в ситуации равновесия по Нэ-шу строго меньше значения целевой функции задачи (32)-(34) в ситуации системного оптимума Вардропа, при выполнении условий

1=1 '

V j = 1 ,т.

В разделе 2.5 исследуется проблема равновесия на транспортной сети (?, имеющей одновременно как независимые маршруты, так и маршруты с общей дугой (рисунок 3).

''t f* Рисунок 3. Схема транспортной сети

В качестве обозначений используются следующие: N = {1,..., 4} - множество последовательно пронумерованных узлов графа G; А = {1,..., 5} - множество последовательно пронумерованных дуг графа G; R = Г\ = 1,гг = 2 - множество районов отправления, R € N; s = 4 - район прибытия, s £ N; К = {1,2,3,4} - множество маршрутов между районами отправления R и районом прибытия s; К\ = {1,2} — множество маршрутов между районом отправления гi и районом прибытия s; К2 = {3,4} - множество маршрутов между районом отправления Гг и районом прибытия s; taa — время свободного движения по дуге а 6 А; са — пропускная способность дуги а & А; ха - транспортный поток по дуге а е А, х = (xi,...,x5); da(xa) = ta (l + ff) - время передвижения (задержка) по дуге а € А] Д - транспортный поток по маршруту к € К, / = (Д,..., /4); F1 - совокупный транспортный спрос между районом отправления ri и районом прибытия s; F2 -совокупный транспортный спрос между районом отправления г2 и районом прибытия s.

В качестве ограничений выступают следующие:

Л + /2 = F1, (35)

b + h = F\ (36)

Л^О VfceAT, (37)

при условии, что Ii = /i, х2 = /г, х3 = /3, х4 = /4, х5 = /2 + /3.

В случае системного оптимума, целевой функционал имеет вид:

5 5 / \

*(/") = z(x*°(f°°)) = ттУЧ(*а)х0 = minV^ ( 1 + ^ ) х„. (38)

* ti * ti V с«/

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

распределения транспортного потока F1 первого Навигатора, а /2 = (/з, Д) - стратегия распределения транспортного потока К2 второго Навигатора. В таком случае целевой функционал первого Навигатора имеет вид:

АГ, /2) = *?(! + Л + (1 + ¿) /2 +*?(! + Л- (39)

при ограничениях (35), (37), а целевой функционал второго Навигатора - вид:

г2(/\ /2) = «5 (1 + /з + *?(! + £) Л + ^ (1 + Л- (40)

при ограничениях (36), (37).

Опираясь на линейный вид ВРИ-функции задержки удается найти все возможные варианты системно оптимального по Вардропу распределения транспортного потока в зависимости от пропускных способностей, времени свободного движения и объемов транспортных потоков из района отправления в район прибытия. Более того, удается определить инфраструктурные характеристики ромбовидной транспортной сети, при которых системный оптимум Вардропа совпадает с равновесием по Нэшу.

Следствие 2.5.1. Если выполняются условия

^+«е ^ (1+

то *(/") = Г) + Г), иначе *(/") < г\Г, /2*) + г2(.Г, /2*).

В разделе 2.6 рассматривается бескоалиционная игра Г(с, /\ /2) типа лидер-последователь, где лидер - администрация мегаполиса, а два последователя - поставщики навигационных услуг двухуровневая модель оптимизации объемов пропускных способностей транспортной сети из п параллельных маршрутов. Администрация (лидер) стремится найти оптимальное распределение пропускных способностей на существующих п параллельных маршрутах из пункта отправления в пункт прибытия с = (сь ...,сп) и соответствующий системный оптимум / = (/ъ...,/п) с тем, чтобы минимизировать общее время движения транспорта по улично-дорожной сети. В свою очередь, поставщики навигационных услуг (последователи), реагируя на заданное администрацией (лидером) распределение пропускных способностей среди возможных маршрутов движения с = (сг,..., с„), в процессе конкуренции достигают равновесного по Нэшу перераспределения своих клиентов по улично-дорожной сети. Следует отметить, что в таком случае речь уже не будет идти о системном равновесии, но - о равновесии по Штакельбергу.

Будем считать, что имеется два поставщика навигационных услуг: Навигатор 1 и 2. Тогда структура общего трапспортного потока имеет вид / = /1+/2 + Л, где / = (/1, ...,/„)-общий транспортный поток (¿"=1 /> = Р)'> Р = (/1. ••■./„)- транспортный поток, состоящий из клиентов Навигатора 1 (¿"=1 Ц = F1); /2 = (А2,...,/2) - транспортный поток, состоящий из клиентов Навигатора 2 (¿"=1 /,2 = -Р2); /( = (/¿1, ■ • ■, К) - транспортный поток, не пользующийся услугами Навигаторов 1 и 2. Через $ обозначим время свободного движения по маршруту i. Более того, будем считать, что к является оценкой системно равновесного транспортного потока, который не пользуется услугами Навигаторов 1 и 2, например, пропорциональной системно равновесному распределению к = Л(с) = ц}в (с) > 0, где /и(с) - оптимальное распределение (системный оптимум) транспортного потока в задаче верхнего уровня, соответствующее набору с количества полос; ц = \ — р рР ■ Таким

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

Для того, чтобы найти оптимальное по Штакельбергу решения лидера в игре администрация - навигаторы (оптимального количества полос, с поправкой на реакцию Пан»га-торов) необходимо решить следующую задачу оптимизации:

тт

1 4-

/'+/1 + ^1

(£ + /? +Л/Л')).

при ограничениях

(41)

(42)

(43)

(44)

F>(7(cj)L VI =1,п,

где а - коэффициент многополосности, зависящий от пропускной способности дороги, а Ь > 0 - ширина одной полосы проезжей части,

+ г + д/гв(с)] _ Сг + л/Лс)

и #

12 = -

Я + Е^Л'У + Л/»] о-

,0 -г V"

I; ¿2-1 г=1 I»

3

И/гВ(с)

(45)

(46)

при условии

^ >

{1,2},

^Сг^Со УаеД (47)

= (48)

В выражение (47) через А обозначено множество всех дуг транспортной сети, а через Ка -множество маршрутов из района отправления в район прибытия, проходящих через дугу а. й > 0 из выражения (48) является заданной величиной для г = 1,7».

Замечание 2.6.1. Следует отметить, что для каждого набора с, удовлетворяющего ограничениям (47), (48), необходимо перенумеровывать маршруты таким образом,

Пусть (с*,/1*,/2*) есть оптимальное решение задачи (41)-(48), тогда справедлива следующая

Теорема 2.6.2. Набор стратегий (с*, /и, /2*) образует ситуацию равновесия по Штакельбергу в двухуровневой игре Г(с, /2).

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

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

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

В разделе 3.3 приведена методика и алгоритм построения матриц корреспонденций на базе информации, получаемой с систем фиксации регистрационных номерных знаков автотранспорта. Рассматривается сеть G, состоящая из узлов и дуг, соединяющие эти узлы. На заданном промежутке между интервалами времени 7\ = [i}, ij] и Т2 = [t\,t]\ (fj < t\) по сети G передвигаются п маркированных агентов из одних узлов сети в другие, используя дуги. В определенных узлах сети находится тп детекторов D = {di,... ,dm}. После прохождения заданного промежутка времени, получаем базу из связанных данных: (l,t,k) - номер зафиксированного агента; время фиксации; номер детектора, зафиксировавшего агент. Считаем, что все маркированные агенты начинают свое движение в моменты времени, содержащиеся в интервале Ti (начало работы системы), и заканчивают его в моменты времени, содержащиеся в интервале Т2 (окончание работы системы).

(Си •• с1т V

• ' •. ; I называется матрицей корре-

Cnl ■ • • Спт. )

спонденций, если каждый элемент матрицы С представим в виде:

с«> = С«'Ж0 V £> "Ф = т> ¡=1

где

с = Г 1, если £(1) ф 0,гр(1) ф 0, . 41 ж ) 0, в противном случае,

при

_ Г номер детектора, зарегистрировавшего агент I в интервале Т\, т "10,

если ни один детектор не зарегистрировал агента I в Т\,

>мер детектора, зарегистрировавшего агент I в интервале если ни один детектор не зарегистрировал агента I в

vie{i,...,Ti}.

Необходимо так использовать базу данных, состоящую из наборов (l,t,k), чтобы восстановить матрицу корреспонденций С. Для этого введем матрицы М\ и М2 и массивы Ai и Л2 следующим образом.

Матрица Mi =

"ill mi2 ■ • ■ m\m \

1 1 rrt 1 ... I

\ Ki K2 ■ • • '«L /

. где

4 \ 0, 1 = (aJ, a.

«1 J k' a' = 1 0,

если детекор ^ зафиксировал агент г в интервале 7\, в противном случае.

Массив Ах = (а\, а\, а],..., а*), где

если детекор к зафиксировал агента I в интервале Т1, в противном случае.

Для интервала времени Т2 = , ¿2] так же фиксируем агентов в узлах сети с детекторами и в конце интервала строим по такому же правилу матрицу М2 и массив А2.

Тогда алгоритм построения матрицы корреспонденций по имеющейся базе данных регистрации агентов имеет следующий вид: Алгоритм 3.3.1.

1. Фиксация агентов на детекторах сети в интервалы времени 7\ и Т2.

2. Обработка полученных данных и представление их в виде:

(a) Двух матриц и М2 размерности п х т для моментов времени Т\ и Т2.

• Построение матрицы С по следующему правилу:

Поочередно сравниваем элементы в строках матриц М\ и М2, г = 1,п.

— Если есть такие М^г, к\ ^ 0 и Л/2 , ф 0 для некоторых j,k = 1 ,т (агент г был зафиксирован и в интервале времени Т\, и в интервале времени Т2), то

* к матрице корреспонденций в узле прибавляем единицу: С[к, ^ =

с[л,Л +1- _

— Если Л/1 [г, = 0 для всех к = 1,т или М2[1,]\ = 0 для всех j = 1, т (агент г не был зафиксирован либо в интервале времени Т!, либо в интервале времени Т2), то

* к матрице корреспонденций ничего не прибавляем.

(b) Двух массивов А1 и А2 для моментов времени Т\ и Т2.

• Построение матрицы С по следующему правилу: Поочередно сравниваем элементы массивов А1 и Л2, г — 1,п.

— Если А1 [г] ф 0 и А2 [г] ф 0 для некоторого г = 1, п (агент г был зафиксирован и в интервале Ть ив интервале Т2), то

* А\[г] = а^ > 0 и А2[г\ = а? > 0 и к матрице корреспонденций в узлах а} и а? прибавляем единицу: С[а},а}]

— Если А\\г\ = 0 для всех г = 1,п или А2[г\ = 0 для всех г = 1,п (агент г не был зафиксирован в интервале 7\, либо в интервале IV), то

* к матрице корреспонденций ничего не прибавляем.

3. Вывод матрицы корреспонденций С.

Приведены результаты численных экспериментов, демонстрирующие лучшие характеристики работы алгоритма (по времени работы и объемам ОЗУ) в случае использования массивов.

Раздел 3.4 посвящен проблеме реконструкции маршрутов движения между районами отправления-прибытия. В случае плотного покрытия транспортной сети детекторами фиксации регистрационных номерных знаков, предлагается польдетекторами фиксации регистрационных номерных знаков предлагается пользоваться следующим подходом. По прошествии периода времени между интервалами Тг и Т2 формируется база данных В, состоящая из наборов (/, к). Затем эта база данных В разбивается на множество баз данных Bj, ] е Ф, где Ф - множество автомобилей зарегистрированных всеми детекторами за период [О,Г]. В = 1_1/6фВ],

(з «1 кЛ

3 ¿2 к2

V и кг)

где г — количество детекторов, зафиксировавших агент с номером j за период времени [О, Т]. При этом ¿х < ¿2 < ■ • • < ¿г- В таком случае набор номеров детекторов (к\,..., кг) является реконструкцией маршрута следования агента с номером ] за период времени [О, Т] мимо детекторов Г).

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

Раздел 3.5 адресован проблеме оптимальной расстановке на транспортной сети датчиков фиксации номерных знаков автотранспорта.

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

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

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

2. Захаров В.В., Крылатов А.Ю. Оценка матрицы корреспонденции транспортных потоков крупных городов России // Материалы международной научно-практической конференции "Транспорт России: проблемы и перспективы - 2013"Санкт-Петербург,

2013. С. 93-96.

3. Захаров В.В., Крылатов А.Ю. Равновесие по Нэшу в игре поставщиков навигационных услуг // Труды XLIII международной научной конференции аспирантов и студентов, 2012. Санкт-Петербург, 2012. С. 500-505.

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

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

2014. №4(53).

6. Захаров В.В., Крылатов А.Ю. Управление транспортными потоками мегаполисов // Сборник статей Седьмой Российско-Немецкой конференции по логистике и SCM DR-LOG 2012, г. Санкт-Петербург. 2012. С. 305-310.

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

8. Крылатов А.Ю. Распределение транспортных потоков в мегаполисах // Сборник статей "Высокие технологии, фундаментальные исследования, экономика г. Санкт-Петербург, 2011.Т. 2. С. 356-359.

9. 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 Re-industrialization, 14th IFIP WG 5.5 Working Conference on Virtual Enterprises, PRO-VE 2013, Dresden, Germany, Proceedings. P. 156-163.

10. Zakharov V., Krylatov A. Nash Equilibrium in a Game of Navigation Providers // Flexibility and Adaptivity of Global Supply Chains. Proceedings of the 7th German-Russian Logistics Workshop DR-LOG 2012. Saint Petersburg, 2012. P. 224-230.

Подписано к печати 23.06.14. Формат 60x84 'Лб. Бумага офсетная. Гарнитура Тайме. Печать цифровая. Печ. л. 1,57. Тираж 100 экз. Заказ 6038.

Отпечатано в Отделе оперативной полиграфии химического факультета СГТбГУ 198504, Санкт-Петербург, Старый Петергоф, Университетский пр., 26 Тел.: (812)428-4043, 428-6919