Оптимизация потоков в транспортных сетях

Введение

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

Рост городского транспорта требует эффективных методов управления. Исследования интеллектуальных транспортных систем (ITS) восходят к 1960. С тех пор было сделано много работы (см., например, [16]) по контролю за дорожным движением, прореживанию трафика, навигации и информации о водителях. Контроль перекрестков, принадлежащий задачам управления движением, как правило, основан либо на фиксированной стратегии по времени или на стратегии реагирования на трафик.

Стратегии с фиксированным временем (например, инструмент TRANSYT [17]), где управление светом светофора (т.е. продолжительность зеленого или красного света) запланировано заранее, является оптимальным только в случае ненасыщенных перекрестков. Фазы управления светом являются производными от исторических данных, измеренных на данном в пересечении. Есть несколько фаз управления для каждого пересечения, в зависимости от заданного времени суток (например, утренняя фаза отличается от обеденной).

Трафикозависимая стратегия основана на онлайн измерениях текущего состояния трафика (например, инструмент SCOTT [9]). Cтратегия Store-and-forward [5, 6] является одной из трафикозависимых стратегий реагирования на основе строгой математической модели. Основная идея при использовании Store-and-forward моделей для управления дорожным движением является упрощение модели, которое дает возможность математического описания транспортного потока процесса без использования дискретных переменных. Это упрощает описание пространства состояния системы и открывает возможность использования полиномиальной оптимизации и алгоритмов управления.

Наш подход основывается на Store-and-forward стратегии. Мы используем реальные данные с детекторов, размещенных за 300 метров до пересечения. Для того, чтобы получить входящий поток, мы обрабатываем эти данные с помощью фильтра Калмана [8], поскольку такой подход дает возможность оценить очереди длиной выше 300 метров. В дополнение к классической Store-and-forward стратегии [6] наша модель включает в себя время ожидания автомобиля, которое является важным входным параметром для контроллеров, разработанных в этой статье.

Эта статья вдохновлена [7], где нелинейные разностные уравнения состояния используются для моделирования и контроля трафика веб-сервера.

Другие подходы к моделированию, с разной точности и сложности, основаны на теории массового обслуживания [10, 18] и сетей Петри [3].

Эта статья организована следующим образом. В разделе 1 описывается расширенная модель очереди. Описание модели микрорайона приведено в разделе 2, а его контроль приведен в разделе 3. Выводы по работе и дальнейшая работа описаны в последнем разделе.

1. Расширенная модель очереди

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

Вектор состояния, которым описывается модель очереди записывается в виде

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

Приближенная модель включает в себя две переменных состояния. Первая – это количество автомобилей в очереди n, а вторая – E[S], среднее значение времени ожидания. Среднее значение времени ожидания E рассчитывается как S, сумма времени ожидания на всех транспортных средствах, деленная на n, количество транспортных средств. Вектор состояния записывается в виде . Это приближение модели будет обозначаться как расширенная модель очереди.

1.1. Геометрическая интерпритация эволюции расширенной модели очереди

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

Геометрическая интерпретация модели может быть изображена как прямоугольный треугольник, как показано на рисунке 1 жирной линией. Горизонтальная сторона треугольника представляет собой n, количество автомобилей в очереди. Вертикальная сторона треугольника представляет время ожидания первой машины в очереди и эквивалентна удвоенному среднему значению времени ожидания (2E). Площадь этого прямоугольного треугольника S представляет собой сумму времени ожидания всех транспортных средств. Отношение между E, N и S имеет вид

В этом разделе мы рассмотрим стабильный входящий поток и W и исходящий поток q. Эволюция модели в дискретном времени от времени k до времени k + 1 может быть разделена на 3 шага:

1. Исходящий поток транспортных средств q соответствует удалению многоугольника А из основного треугольника.
2. Все транспортные средства, которые остаются в очереди, должны увеличить свое время ожидания. На рисунке 1 это представлено прямоугольником C.
3. Входящий поток автомобилей w представлен новым треугольником D. Этот треугольник будет добавлен к области.

Новая область эквивалентна S, сумме времени ожидания всех транспортных средств в момент k + 1. Эта область S (k + 1) может быть рассчитана как сумма многоугольников B, C и D областей

Из изображенной геометрической интерпретации и уравнений (2) и (3) мы можем определить следующие дискретные уравнения состояния

Уравнения состояния действительны только при условиях n(k) > 0 и n(k) > q(k) - w(k), что означает, что в очереди должно быть некоторое число транспортных средств, в противном случае Е (k + 1) должно быть равно 0.

1.2. Расширенная оценка модели очереди

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

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

1.3. Расширенная модель равновесия очереди

Равновесие – это состояние системы (точка равновесия), в котором все переменные состояния являются сбалансированными, то есть х (k) = х (k + 1). Точка равновесия используется для линеаризации и в дальнейшем для контрольного синтеза, описанного в разделе 3.

Точка равновесия для нашего вектора состояния должна удовлетворять следующим условиям

Решение этих уравнений дает следующие условия равновесной точки

Знак круга означает, что значение данной переменной является значением в равновесии. Условие (8) означает, что входящий поток w должен быть равным исходящему потоку q. Это означает постоянное количество автомобилей в очереди. Из второго условия (9) следует, что среднее значение времени ожидания пропорционально длине очереди и обратно пропорционально потоку автомобилей.

Условие (9) между Е и n в равновесии хорошо известно как закон Литтла [13]. Теорема Литтла, интерпретируемая в нашей терминологии, гласит: "Среднее количество транспортных средств в стабильной очереди (за некоторый промежуток времени) равно среднему входящему потоку, умноженному на среднее время пребывания в очереди".

2. Модель микрорайона

Модель очереди, описанная выше, будет использоваться для построения модели микрорайона (см. Рисунок 3). Микрорайон состоит из двух улиц и одного пересечения. Улица – это место, где находится очередь транспортных средств. Перекресток – это место, где транспортные средства из очередей разделяют один и тот же ресурс. Исходящий поток w каждой очереди контролируется светофором на перекрестке.

Модель микрорайона может быть описана как

где - вектор состояния, объединяющий модели очередей и , описанные в разделе 1. Вектор состояния может быть разложен на n и E, поэтому

F – это нелинейная функция, заданной уравнениями (4) и (5). Вектор представляет исходящий поток очередей, а вектор - входящий поток. Индекс обозначает номер очереди.

2.1. Линейная модель

Линейная модель построена с помощью линеаризации функции F (10) в точке равновесия (см. раздел 1.3). Равновесная точка O была выбрана в качестве средней точки в реальной дорожной ситуации, эта точка описывается как

Линеаризованная модель микрорайона описывается выражением

Матрицы вычисляются как решения матриц Якоби для функции F в точке равновесия О.

3. Управление микрорайоном

Цель управления состоит в нахождении оптимального расписания для светофоров перекрестка. В этом разделе будут использоваться и сравниваться два контроллера из современной теории управления.

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

Микрорайон, описанный выше, включает две контрольные фазы. Каждая фаза позволяет двигаться только машинам с одной из улиц (см. Рис.3). В наших контрольных алгоритмах сумма времени фаз считается постоянной, т.е. контрольный период постоянен и равен Т. В этой секции контрольный период установлен равным 90 секундам. Время, когда одна фаза сменяется другой, обозначено как время переключения . Время переключения может быть использовано для получения закона управления моделью (10) следующим образом:

где - максимальный исходящий поток из очереди j, а i=0, 1, 2, 3... - номер контрольного периода.

3.1. Линейно-квадратичный контроллер

В этом пункте линейно-квадратичный контроллер (ЛК) [11] будет использоваться для управления движением на перекрестке. Цель контроллера - минимизировать время ожидания автомобилей. Это означает, что все машины, попадающие в очередь с различных направлений будут ждать одинаковое время. Эта цель может быть записана как

С учетом (11) это можно записать как

где матрица Q

Закон управления ЛК, который минимизирует цель за один день , может быть записан как Где к - решение уравнения Риккати для системы (12). Таким образом, путем простых преобразований мы получим

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

Из времени переключения и выражения (13) мы получим окончательный закон управления q(k). Закон управления вычисляется во время начала контрольного периода и остается неизменным в течение всего периода.

ЛК-контроллер был применен к модели (10). Ответ системы на реальный сигнал показан на Рис.4а со значительной разницей времени ожидания очередей 1 и 2, связанной с линеаризацией модели в точке равновесия.

3.2. Нелинейный интеллектуальный контроллер модели

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

Очевидно, НИК находит оптимальное время переключения с помощью выпуклых методов оптимизации [2]. Но наша проблема оптимизации невыпукла. Поэтому мы находим наше оптимальное время переключения путем перебора. Реакция модели на НИК показана на Рис. 4b.

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

Форма кривой функции для разных контроллеров показана на Рис.5. Можно видеть, что НИК показывает лучшие результаты, чем ЛК.

С другой стороны, НИК имеет большую временную сложность. Еслы мы увеличим горизонт предсказания с 90 до 180 секунд, то время расчета увеличится с менее чем одной минуты до пяти минут. Горизонт, увеличенный до 270 секунд, приводит к проблеме невозможности расчета задачи за один день.

Выводы и дальнейшая работа

В данной статье представлена новая модель для очередей автомобильного трафика. Расширенная модель очереди описывается числом машин в очереди и, в основном, значением времени ожидания, которое описывает динамику очереди. Модель основана на нелинейных разностных (т.е. с дискретным временем) уравнениях состояния. Эти уравнения описывают поведение модели в обоих, равновесном и неравновесном, состояниях. Мы показали, что точка равновесия находится в соответствии с законом Литтла.

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

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

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

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

Данная работа была поддержана Министерством образования Чехии по Проекту 1M0567.

Список использованной литературы

1. Karl Johan Astrom and Bjorn Wittenmark.Computer-Controlled Systems: Theory and Design. Prentice Hall, November 20 1996.

2. Stephen Boyd and Lieven Vandenberghe. Convex Optimization. Cam-bridge University Press, New York, NY, USA, March 2004.

3. A. Di Febbraro, D. Giglio, and N. Sacco. Urban traffic control structure based on hybrid Petri nets. IEEE Transactions on Intelligent Transportation Systems, 5:224–237, 2004.

4. Rolf Findeisen and Frank Allgower. An Introduction to Nonlinear Model Predictive Control. In 21st Benelux Meeting on Systems and Control, March 2002.

5. D. Gazis and R. Potts. The oversaturated intersection. In Proc. 2nd Int. Symp. Traffic Theory , pages 221–237, 1963.

6. Denos C. Gazis. Traffic theory. Kluwer, 2002.

7. Dan Henriksson, Ying Lu, and Tarek F. Abdelzaher. Improved Prediction for Web Server Delay Control. In ECRTS, pages 61–68. IEEE Computer Society, 2004.

8. Jitka Homolova and Ivan Nagy. Traffic Model of a Microregion. In IFAC World Congress, 2005.

9. P. B. Hunt, D. I. Robertson, and R. D. Bretherton. The SCOOT on-line traffic signal optimization technique. Traffic Eng. Control, 23:190– 192, 1982.

10. Rajat Jain and J. M. Smith. Modeling Vehicular traffic flow using M/G/C/C state dependent queueing models. Transportation Science, 31(4):324–336, 1997.

11. Huibert Kwakernaak. Linear Optimal Control Systems. John Wiley & Sons, Inc., New York, NY, USA, 1972.

12. Jia Lei and Umit Ozguner. Decentralized hybrid intersection control. In Proceedings of the 40th IEEE Conference on Decision and Control, volume 2, pages 1237–1242, 2001.

13. J. D. C. Little. A Proof of the Queueing Formula L = W. Operations Research, 9:383–387, 1961.

14. L.Magni, G. De Nicolao, R. Scattolini, and F. Allgwer. Robust model predictive control for nonlinear discrete-time systems. Int. J. Robust Nonlinear Control, 13(3-4):229–246, 2003.

15. K. Ogata. Discrete-Time Control Systems. Prentice-Hall, 1987.

16. Markos Papageorgiou, Christina Diakaki, Vaya Dinopoulou, Apostolos Kotsialos, and Yibing Wang. Review of Road Traffic Control Strategies. PROCEEDINGS - IEEE, 91:2043–2067, 2003.

17. D. Robertson. TRANSYT method for area traffic control. Traffic Eng. Control, 10:276–281, 1969.

18. Nico Vandaele, Tom VanWoensel, and Aviel Verbruggen. A queueing based traffic flow model. Working papers, University of Antwerp, Faculty of Applied Economics, May 1999.