Введение 2
Глава 1. Обзор литературы 14
1.1. Методы оценки матриц корреспонденций 15
1.2. Оценка матрицы корреспонденций при помощи информации с датчиков 20
Глава 2. Математическая модель оценки матрицы корреспонденций на сети из параллельных маршрутов 31
2.1. Распределение транспортных потоков в прямой и двойственной постановке 33
2.2. Оценка матрицы корреспонденций как задача обратная к равновесному распределению потоков 37
Глава 3. Математическая модель оценки матрицы корреспонденций на сети произвольной топологии 41
3.1. Распределение транспортных потоков в прямой и двойственной формулировке 41
3.2. Двухуровневая задача оценки матрицы корреспонденций на основе информации с датчиков фиксации номерных знаков 44
Глава 4. Эксперимент на транспортной сети Санк-Петербурга 47
Заключение 51
Список литературы 53
В современном мире мы все чаще сталкиваемся с проблемами на дорогах: автомобильные пробки, снижение скорости сообщения, растущее число дорожно-транспортных происшествий, резкое увеличение количества автомобилей, которое в свою очередь приводит к нехватке мест для парковки и загрязнению окружающей среды (рис.1). Решение этих проблем требует реорганизации дорожного движения и модернизации улично-дорожной сети (УДС) города. В мировой практике активно применяется, например, ограничение въезда в центр города, взымание платы за стоянку в определенной городской зоне, строительство перехватывающих парковок и платных участков дорог, ограничение владения личным транспортом, использование интеллектуальных транспортных систем (ИТС) и т.д. Однако результативность таких подходов не везде одинакова [6].
Рис. 1. Проблемы на транспортной сети
Одной из наиболее острых проблем, препятствующих устойчивому развитию транспортной системы нашей страны, является резкое повышение уровня загрузки автомобильных дорог транспортными потоками, в первую очередь, на территории крупных городов и на подходах к ним. Следствием этого являются перечисленные ранее проблемы.
По данным Федерального дорожного агентства около 30% автомобильных дорог федерального значения работают в режиме перегрузки (в первую очередь — на подходах к крупным городам). Наиболее остро проблема перегруженности проявляется в крупнейших и сверхкрупных городах, в которых уровень автомобилизации давно перешагнул уровень 300 автотранспортных средств (АТС) на 1000 жителей. Средние скорости сообщения в городах неуклонно снижаются, и нередко достигают 8-10 км/час, при оптимальных 30-35 км/час. Согласно имеющимся оценкам, суммарные дополнительные издержки, связанные с перегрузкой дорожной сети, достигают в России 49% ВВП в год [11].
Исследования проблемной области в отечественной и зарубежной литературе говорят о том, что развитие современных методов организации дорожного движения (ОДД), основанных на применении интеллектуальных транспортных технологий и математических моделей, напрямую влияет на возможности повышения пропускной способности дорожных сетей и уровня безопасно сти дорожного движения. При системной реализации математического подхода к ОДД и совершенствованию транспортной сети можно резко повысить эффективность управления дорожным движением, значительно улучшить ситуацию на дорогах, улучшить устойчивость работы транспортной системы в целом и качество жизни населения в городах.
Опыт передовых зарубежных стран свидетельствует, что эффект от внедрения в городах современных сетевых проектных решений по ОДД, разрабатываемых с использованием математических моделей транспортных потоков, выражается в сокращении числа ДТП на величину около 15%, увеличении пропускной способности дорожных сетей до 20%, снижении потреблении топлива на величину до 20%. Косвенные экономические эффекты, связанные с предотвращением транспортных заторов и обеспечением устойчивой работы автомобильного транспорта, включают прирост ВВП (до 10%) и повышение занятости населения [11].
Как сказано ранее, оптимальное планирование транспортных сетей в смысле улучшения организации дорожного движения требует применения аппарата математического моделирования, на основе которого возможно определение и прогноз всех параметров функционирования УДС. В самом общем смысле можно выделить три класса математических моделей, применимых для анализа транспортных сетей [14]:
• прогнозные модели;
• имитационные модели;
• оптимизационные модели.
Построение математической модели требует формализации транспортной сети. Дорожная сеть представляется в виде графа, узлы которого соответствуют перекресткам, а дуги — участкам улиц. Изучаемый город или район делится на некоторое условное число районов отправления и прибытия (фиксированное множество узлов графа). Общий объем перемещений между районами отправления и прибытия ^П-парами) в определенный период времени называется межрайонной корреспонденцией в этот период. Получив все значения межрайонных корреспонденций, можно со ставить матрицу корреспонденций. На рисунке 2 представлен пример формализации транспортной сети в виде графа, а на рисунке 3 — пример составления матрицы корреспонденций в виде таблицы, где на пересечении i-й строки и j-го столбца стоит объем транспортных средств, передвигающихся из района i в район j в определенный период времени.
Прогнозные модели предполагают, что известны топология, характеристики транспортной сети и расположение потокообразующих объектов в городе и необходимо определить, какими будут транспортные потоки между этими объектами [14].
Рис. 2. Пример формализации транспортной сети в виде графа
Такие модели позволяют прогнозировать последствия изменений в транспортной сети или в размещении объектов. В свою очередь имитационное моделирование воспроизводит все детали движения, в том числе развитие процесса во времени. При этом усредненные значения потоков и распределения по путям заранее известны. Отличие этих двух моделей можно кратко сформулировать следующим образом. Прогнозные модели отвечают на вопрос: «только и куда» будут ехать в данной сети. Имитационные модели отвечают на вопрос: как в деталях будет происходить движение, если известно в среднем, «сколько и куда» [14]. Прогнозные и имитационные модели ставят своей целью адекватное воспроизведение транспортных потоков, в то время как оптимизационные модели отвечают на вопросы оптимизации функционирования транспортных сетей. Рассмотрим эти три класса моделей более подробно.
Рис. 3. Представление матрицы корреспонденций в виде таблицы
Прогнозные модели
Общую схему прогнозных моделей можно свести к следующим трем взаимосвязанным задачам [13]:
• расчет общих объемов передвижения между районами города или агломерации (расчет матриц межрайонных корреспонденций);
• распределение корреспонденций по конкретным путям в транспортной сети;
• расчет загрузки всех элементов сети транспортными потоками.
К числу наиболее распространенных моделей расчета корреспонденций относятся гравитационные, энтропийные, модели конкурирующих и промежуточных возможностей Стауффера [14].
Загрузка транспортной сети определяется количеством транспортных средств, которые используют для своего передвижения элементы сети. Загрузка элементов моделируется посредством распределения межрайонных корреспонденций по конкретным путям, соединяющим пары районов. Входные данные для такой модели — матрица корреспонденций, а ее цель — определение для каждой пары районов отправления-прибытия набора путей, используемых для перемещения между этими районами.
Существует классификация моделей загрузки транспортной сети, основанная на следующих признаках [14]:
• модели, основанные на нормативном (нацеленном на поиск системного оптимума) и дескриптивном (определяющем результат пользовательской оптимизации маршрутов) подходе;
• статические и динамические модели.
Для определения объемов загрузки УДС необходимо выявить правила, по которым водители выбирают тот или иной маршрут следования. Поведенческие принципы пользователей были окончательно сформулированы в работе [48] в виде двух принципов:
• пользователи сети независимо друг от друга выбирают маршруты следования, соответствующие их минимальным транспортным расходам,
• пользователи сети выбирают маршруты следования, исходя из минимизации общих транспортных расходов в сети,
которые получили названия соответственно первого и второго принципа Вардропа [2].
Распределение транспортных потоков согласно первому принципу Вар- дропа соответствует конкурентному бескоалиционному равновесию, предполагающему совершенный эгоизм участников дорожного движения — каждый стремится достигнуть конечного пункта своей поездки как можно быстрее и из имеющихся возможных вариантов следования выбирает тот маршрут, по которому будет нести минимальные затраты (временные, финансовые, моральные и т.п.) на проезд. Этот принцип в полной мере учитывает фактор взаимного влияния пользователей. Поэтому его также называют конкурентным равновесием (user equilibrium). Суть этого принципа кратко можно сформулировать так: при равновесном распределении загрузки ни один из участников движения не может изменить свой путь так, чтобы уменьшить свое индивидуальное время поездки. Второй принцип Вардро- па предполагает централизованное управление движением в сети. Соответствующее ему распределение транспортных потоков называют системным оптимумом (system optimum). Примером пользователей, передвигающихся согласно второму принципу, служат водители маршрутизированного транспорта.
Имитационные модели
К классу имитационных по их функциональной роли можно отнести широкий спектр моделей, известных под названием модели динамики транспортного потока. В моделях этого класса может применятся разная техника — от имитации движения каждого отдельного автомобиля до описания динамики функции плотности автомобилей на дороге. При этом для динамических моделей характерна значительно большая детализация движения и, соответственно, потребность в больших вычислительных ресурсах. Применение этих моделей позволяет оценить динамику скорости движения, задержки на перекрёстках, длины и динамику образования «очередей» или «заторов» и другие характеристики движения. Основные области практического применения динамических имитационных моделей — улучшение организации движения, оптимизация светофорных циклов и др. В настоящее время актуальной задачей является разработка систем автоматизированного оперативного управления движением, работающих в режиме реального времени. Однако помимо практического применения, развитие динамических моделей представляет большой научный интерес в связи с изучением транспортного потока как физического явления со сложными и нетривиальными свойствами. Среди таких свойств — спонтанная потеря устойчивости, явления самоорганизации и коллективного поведения и многие другие.
Большинство существующих моделей динамики транспортных потоков может быть приблизительно разделено на три класса:
• макроскопические модели;
• микроскопические модели;
• стохастические модели.
В макроскопических моделях движение транспортных средств уподобляется какому-либо физическому потоку (гидро- и газодинамические модели). В микроскопических моделях существенно предположение о наличии связи между перемещением ведомого и головного автомобиля. По мере развития теории в моделях этой группы учитывалось время реакции водителей, исследовалось движение на многополосных дорогах, изучалась устойчивость движения. Этот класс моделей также называют моделями следования за лидером. В стохастических моделях транспортный поток рассматривается как результат взаимодействия транспортных средств на элементах транспортной сети. В связи с жестким характером ограничений сети и массовым характером движения в транспортном потоке складываются отчетливые закономерности формирования очередей, интервалов, загрузок по полосам дороги и т. п. Эти закономерности носят существенно вероятностный характер.
Модели динамики транспортных потоков дают достаточно простые устойчивые решения в случае малой загрузки дорог (свободное движение при избыточном ресурсе). Однако решения для случая высокой плотности потоков чрезвычайно чувствительны к малейшим флуктуациям параметров дорог и особенностей поведения участников движения.
Оптимизационные модели
В классе оптимизационных моделей решаются задачи оптимизации маршрутов пассажирских и грузовых перевозок, выработки оптимальной конфигурации сети и другие. В частности, рассматриваются задачи оптимизации работы дорожной системы на участке протяжённостью несколько километров с движением автомобилей в одном направлении. При разработке планов оптимизации указанной системы используются модели двух типов [3]. Первой из них является модель для оценки транспортной загрузки у узкого места, а второй — модель линейного программирования. В обоих случаях в качестве контрольного параметра используется полная пропускная способность дороги и делается попытка в каждом узком месте поддерживать транспортную нагрузку меньше пропускной способности. Транспортная нагрузка у узкого места дороги образуется за счёт автомобилей, въезжающих на магистраль с примыкающих въездов, расположенных перед узким местом. Если известна интенсивность каждого такого потока, то можно оценить транспортную нагрузку у данного узкого места.
Для анализа и планирования работы дорожной системы в установившемся режиме могут использоваться различные модели линейного программирования. В простейшем случае модель имеет следующий вид:
п
Е *>
;=1
при условиях
п
AjkXj 6 Вк, к = 1,..., п,
j=1
х 6 D, j = 1,...,п,
Xj > 0, j = 1,...,п.
В данной модели Xj — интенсивность j -го входящего потока; Dj — транспортная нагрузка на j -м въезде; Вк — пропускная способность к -го узкого места, а Ajk — вероятность того, что автомобиль, попадающий на магистраль с j -го въезда, пройдёт через к -ое узкое место. Построенная модель максимизирует выходящий поток системы. Первая система ограничений требует, чтобы в каждом узком месте дороги транспортная нагрузка не превышала полной пропускной способности в данном направлении. Вторая система ограничений требует, чтобы интенсивность входящего потока не превышала транспортной нагрузки при любом входящем потоке. Третья система ограничений гарантирует возможность решения.
В этой модели могут быть использованы и другие ограничения: ограничения, устанавливающие максимальную длину очереди на всех регулируемых въездах; ограничения, гарантирующие, что транспортная нагрузка не превысит пропускной способности узкого ме ста дороги на наиболее ответственной полосе движения.
Задача поиска матриц корреспонденций явно входит только в прогнозные модели. Однако, без решения этой задачи невозможно представить себе эффективной реализации и адекватного применения имитационных и оптимизационных моделей на реальных транспортных сетях. В самом деле, практическое применение результатов математического моделирования в конечном счете сводится к мероприятиям по реорганизации дорожного движения или изменению инфраструктуры транспортной сети, эффективная реализация которых невозможна без достоверной информации о трафике, точность и своевременность которой зависят от технических возможностей расчета матриц корреспонденций между выделенными на транспортной сети районами отправления-прибытия [2].
В связи с этим важно отметить, что получать данные о межрайонных корреспонденциях можно не только при помощи описанных выше математических моделей, но и другими способами: натурными замерами, проведением социологических опросов, при помощь счетчиков. Однако, стоит отметить, что такие способы крайне трудозатратны и малоэффективны. На сегодняшний день существуют и другие способы получения информации для матрицы корреспонденций, например, при помощи различных датчиков, установленных на транспортной сети, и RFID-меток. RFID-метка, например, передает радиосигнал с транспортного средства на пульт управления, что позволяет проследить весь путь его следования и однозначным образом построить матрицу корреспонденций. К сожалению, на сегодняшний день RFID-система не получила широкого распространения, но является крайне перспективной с точки зрения полноты получаемых данных.
В то же время датчики регистрации транспортных средств уже сегодня активно используются на дорогах. Эти датчики обладают различными функциями, какие-то из них многофункциональны. Некоторые из них фиксируют потоки, собирают статистическую информацию об интенсивности движения, количестве автомобилей (петлевые детекторы [41]), некоторые могут фиксировать номерные знаки (датчики фиксации номерных знаков) или скорость движущихся транспортных средств.
Датчики регистрации номерных знаков в своем большинстве установлены для фиксации нарушений правил дорожного движения, но могут быть активно использованы для получения информации о межрайонных корреспонденциях или о времени движения по участку дороги. Распознавая номерной знак транспортного средства на разных элементах сети в последовательные моменты времени, мы получем однозначную картину маршрута, по которому это транспортное средство двигалось, или времени, за которое транспортное средство преодолевает конкретный участок. Кроме того, проанализировав маршруты движения всех транспортных средств, можно получить межрайонные корреспонденции и саму матрицу корреспонденций. Однако не всегда есть возможность сделать наблюдаемыми все дуги транспортной сети. Количество датчиков может быть ограничено бюджетом, выделяемым на их закупку и установку. Тогда появляется задача восстановления потоков на ненаблюдаемых дугах, а соответственно и задачи оценки и восстановления матрицы корреспонденций. Получив время движения потоков по дугам транспортной сети, возникает вопрос: можно ли по этим данным оценить корреспонденции? В следующих главах будет продемонстрировано, что решить задачу оценки матрицы корреспонденций можно и при помощи информации о времени движения транспортных средств по участкам УДС.
Данная работа организована следующим образом. В Главе 1 рассматривается обзор литературы по теме оценки матрицы корреспонденций. Глава 2 описывает разработанный подход к оценке матрицы корреспонденций, как к решению двойственной задачи распределения транспортных потоков по первому принципу Вардропа на сети, состоящей из одной пары районов отправления-прибытия и параллельных маршрутов между ними. Двойственная по становка задачи к равновесному распределению потоков на сети произвольной топологии рассматривается в Главе 3, как и двухуровневая задача оценки матрицы корреспонденций на основе информации с датчиков фиксации номерных знаков. В Главе 4 описан эксперимент, проведенный на транспортной сети Санкт-Петербурга. В Заключении даются выводы об эффективности разработанной модели.
В данной работе представлен новый подход к оценке матрицы корреспонденций транспортной сети большого города. В основе предложенной математической модели лежит теория двойственных задач нелинейного программирования. Задача оценки матрицы корреспонденций рассматривается как задача, двойственная к задаче равновесного распределения транспортных потоков. Математическая модель составлена для упрощенной сети, состоящей из одной пары районов отправления и прибытия и параллельных маршрутов, соединяющих эту пару районов, и для сети произвольной топологии. Стоит отметить, что для сети из параллельных каналов, решения получены в явном виде. Произведены расчеты на примере транспортной сети города Санкт-Петербург в программной среде MatLab.
Определение значения t* на реальной транспортной сети для выделенной ОП-пары не представляется сложной задачей, а в предположении распределения транспортных потоков по принципу конкурентного равновесия Вардропа эта информация играет существенную роль в задаче поиска межрайонных корреспонденций. В самом деле, многие аналитические онлайн системы, исследующие транспортные заторы, накапливают большие базы данных с информацией о средней скорости движения (а значит, и времени) по всем дугам транспортных сетей крупных городов. Полезным инструментом в данном вопросе выступают датчики фиксации номерных регистрационных знаков автомобилей, которые позволяют получить достоверную и уникальную информацию о движении транспортных средств и времени преодоления ими участков дорожной сети. В данной работе моделируемые данные основаны на информации с таких датчиков. Таким образом, разрабатываемый подход к оценке и восстановлению матрицы корреспонденций показывает себя крайне эффективным с практической точки зрения.
В дальнейшем планируется разработка новых эффективных подходов к оценке матрицы корреспонденций. Более того, представляет интерес расширить полученные результаты на случай конкурентной маршрутизации [4,7].
1. Белолипецкий А. А., Горелик В. А. Экономико-математические методы. Москва, Россия: Академия. 2010. 368 с.
2. Гасников А. В., Кленов С. Л., Нурминский Е. А., Холодов Я. А., Ша- мрай Н. Б. Введение в математическое моделирование транспортных потоков / под ред. Гасникова А. В. М.: Изд-во Моск. физ.-техн. ин-та, 2010. 362 с.
3. Дрю Д. Теория транспортных потоков и управление ими / М.: Транспорт. 1972.
4. Захаров В. В., Крылатов А. Ю. Конкурентная маршрутизация транспортных потоков поставщиками услуг навигации // Управление большими системами: сборник трудов. 2014. № 49. С. 129-147.
5. Захаров В. В., Крылатов А. Ю. Конкурентное равновесие Вардропа на транспортной сети из параллельных неоднородных маршрутов // Процессы управления и устойчивость. 2014. Т. 1, № 1. С. 476-481.
6. Захаров В. В., Крылатов А. Ю. Современные проблемы использования интеллектуальной базы математического моделирования при борьбе с заторами в крупных городах России // Транспорт Российской Федерации. 2014. № 4 (53). С. 69-73.
7. Захаров В. В., Крылатов А. Ю. Системное равновесие транспортных потоков в мегаполисе и стратегии навигаторов: теоретико-игровой подход // Математическая теория игр и ее приложения. 2012. T. 4. № 4. C. 23-44.
8. Крылатов А. Ю. Оптимальные стратегии управления транспортными потоками на сети из параллельных каналов // Вестник Санкт- Петербургского университета. Серия 10: Прикладная математика. Информатика. Процессы управления. 2014. № 2. С. 121-130.
9. Лагерев Р. Ю. Методика оценки матриц корреспонденций транспортных потоков по данным интенсивности движения. Диссертация. Волгоград. 2007. 183 с.
10. Раевская А. П. Оптимальное расположение датчиков на транспортной сети для оценки матрицы корреспонденций. Дипломная работа. Санкт- Петербург. 2015. 83 с.
11. Сайт федерального дорожного агентства // www.rosavtodor.ru
12. Хабаров В. И., Молодцов Д. О., Хомяков С. Г. Марковская модель транспортных корреспонденций // Доклады ТУСУРа. № 1 (25), часть 1. 2012.
13. Швецов В. И. Алгоритмы распределения транспортных потоков / М.: Институт системного анализа РАН. 2009. С. 1-48.
14. Швецов В. И. Математическое моделирование транспортных потоков // Автоматика и телемеханика. 2003. № 11. С. 3-46.
15. Beckman M., McGuire C. B., Winsten C. B. Studies in economics of transportation // RM-1488. Santa Monica: RAND Corporation. 1955.
...