Разработка математической модели интеллектуальной транспортной системы

Актуальность проблемы автомобильных пробок не нуждается в обосновании, достаточно обратиться к наиболее цитируемым исследованиям [1], где подсчитаны ежегодные потери от автомобильных пробок в крупнейших городах различных стран мира. Москва, в этом рейтинге неизменно находится в «группе лидеров», несмотря на огромные вложения в транспортную инфраструктуру и бесспорные успехи, достигнутые за. последние несколько лет.

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

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

«Московский физико-технический институт (государственный университет)», 2018

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

Авторы данной работы глубоко убеждены, что наиболее эффективным и многообещающим подходом в борьбе с автомобильными пробками как раз и является учёт планируемого маршрута и графика движения каждого транспортного средства, участвующего в движении. Рассматриваемая в данной статье математическая модель разрабатывалась именно в таком подходе. С помощью предложенной модели авторы планируют в будущем провести исследование нескольких алгоритмов управления дорожным движением, впервые предложенным в [2], путём симуляции предельной нагрузки на УДС ("час пик") в двух вариантах: 1) без регулирования и 2) с выбранным алгоритмом регулирования. Также ниже будут рассмотрены критерии эффективности функционирования транспортной системы, по которым предлагается оценивать полученный эффект.

2.    Обзор литературы

Первые научные работы, посвящённые моделированию дорожного движения, появились уже в начале 20-го века, в связи с бурным ростом автомобильной промышленности, прежде всего, в США [3]. Но особенно интенсивно это направление стало развиваться с 60-х годов прошлого столетия, когда проблема автомобильных пробок стала набирать остроту в странах с высоким уровнем автомобилизации. И, разумеется, тут же начали предлагаться различные математические модели для описания этого явления. В 1963 г. в США был создан Transportation Research Board в составе National Research Council, курируемый академией наук США, что свидетельствует о том, что проблема приобрела общенациональный масштаб. В [4] приведено наиболее полное, на наш взгляд, «генеалогическое дерево» математических моделей транспортных потоков, а детальное описание наиболее распространённых подходов дано, например, в [5]. Мы не будем подробно останавливаться на классификации математических моделей, отметим только, что согласно [4] в последнее время продолжают активно развиваться три основных подхода: микроскопический, мезоскопический и макроскопический. Но, как следует из того же обзора [4], все применявшиеся до сегодняшнего дня модели использовались, в основном, для двух целей: 1) прежде всего, для прогнозирования состояния дорожного движения на определённый момент времени, и 2) для долгосрочного планирования (при строительстве новых дорог или реконструкции существующих). И уже само предназначение этих моделей обуславливает другое их общее свойство: все они оперируют с некой усреднённой тем или иным способом нагрузкой на УДС и дают прогноз с некоей вероятностью. Главными отличиями предлагаемой в данной работе модели от использовавшихся ранее являются:

• 1)    предназначение - разрабатываемая модель создаётся не для моделирования реального движения не УДС, а для отработки алгоритмов динамического управления дорожным движением.

• 2)    степень детерминизма - разрабатываемая модель не носит прогностический характер, а предполагает 100%-й детерминизм: мы не предугадываем, а точно знаем - куда и по какому маршруту движется каждое без исключения ТС.

3.    Постановка задачи3.1.    Требования к модели

Согласно приведенной в [4] классификации такой подход следовало бы отнести к микроскопическому. Моделирование дорожного движения на уровне каждого ТС не ново (см. например, [6]), и позволяет получить весьма высокую степень приближения к реальному трафику. Так, например, в [7] авторам удалось добиться в коэффициента корреляции 0,9 при сравнении с реальным движением на квартале 2 кв. км. с помощью агентного моделирования. Но, в отличие упомянутых выше работ, авторы которых ставили главной целью добиться максимального соответствия модели реальному дорожному движению, а разработку алгоритмов управления движением либо оставляли за скобками, либо оставляли на будущее, в рамках данной работы основной целью было создание имитационной модели, изначально предназначенной для апробации вполне определённых алгоритмов централизованного управления дорожным движением в масштабах города. При этом степень приближения к реальному движению не столь принципиальна, поскольку в процессе отработки таких алгоритмов измерять предполагается относительное улучшение качества работы транспортной системы в целом.

Математическая модель должна быть адекватна цели и инструментам исследования. Определим цель создания собственной модели более детально. Как уже было сказано выше, математическая модель создаётся с целью отработки алгоритмов управления дорожным движением (АУДД) в масштабах города, т.е. интеллектуальной транспортной системы (ITS - Intelligent Transport System), которую следует отнести к классу ATMS (Advanced Traffic Management Systems), а в ещё более обобщённом смысле, к одной из разновидностей систем автоматизированного управления. Поскольку целью создания любой системы управления является повышение эффективности функционирования управляемого объекта, целью последующего численного симуляционного моделирования будет, в первую очередь, доказательство наличия положительного эффекта и его приблизительная оценка, а во вторую - тонкая настройка параметров алгоритма управления. Принципиальными, с точки зрения алгоритма управления, являются три условия:

• 1)    модель должна охватывать вето улично-дорожную сеть транспортной системы города и обеспечивать возможность моделирования на временном промежутке от нескольких часов до нескольких суток;

• 2)    модель должна учитывать индивидуальные маршруты движения каждого транспортного средства (ТС);

• 3)    модель должна быть не слишком требовательной к вычислительным ресурсам, чтобы обеспечить приемлемое время расчёта в процессе симуляции.

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

Кроме того, важно отметить, что разрабатываемая математическая модель имитирует не только собственно дорожное движение, а транспортную систему целиком, то есть:

• -    физические свойства улично-дорожной сети, влияющие на её производительность, а именно: протяжённость участков дороги между перекрёстками, ширину проезжей части (к-во полос), разрешённый скоростной режим, работу перекрёстков);

• -    поведение водителя - выбор времени начала движения и маршрута (поведение в процессе движения пока не моделируется);

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

3.2.    Критерии эффективности функционирования транспортной системы в рамках предложенной модели

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

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

Человечество потратило немало ресурсов на решение задачи обеспечения эффективного перемещения пассажиров и грузов в пространстве, но, как мы видим из [1] (и наблюдаем каждый день в «часы пик»), эффективного решения до сих пор не найдено. И не в последнюю очередь это связано с тем, что среди специалистов нет однозначного мнения о том, что считать критерием эффективности функционирования автодорожной транспортной системы. А ведь выбор критериев оптимизации в значительной степени предопределяет выбор алгоритма управления! Наиболее часто употребляемый критерий - средняя скорость движения на дороге - на наш взгляд, не является правильным, потому что не учитывает ни длину поездок, ни реальные маршруты. Из множества критериев, перечисленных, например, в [8], мы выбрали главные, на наш взгляд, а именно:

• -    более надежная - «своевременная» доставка,

• -    время в пути,

• -    транспортные затраты,

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

Кроме того, представляется весьма важным добавить «штрафы» за слишком раннее прибытие, а особенно, за опоздание. Цена последнего может быть крайне высока, если речь идёт, например, об опоздании на самолёт. На практике это компенсируется как раз более ранним прибытием, которое, тем не менее, тоже имеет свою «цену».

«Совокупную стоимость» поездки при таком подходе можно выразить как:

TOTAL_COST = F_t(travel_ time) + F_L(distan се) + FeariyV -At) + Ғ_Ые (At) где

Ft(travel_time) - функция совокупных затрат, зависящих от времени, затраченного на поездку, (например, зарплата водителя);

^(distance) - функция совокупных затрат, зависящих от пройденного расстояния, (например, износ ТС);

F_eariy( -At) - «цена» преждевременного прибытия (например, непроизводительный простой такси);

Fi_ate (At) - «цена» опоздания;

At - абсолютная величина отклонения от запланированного (желаемого) времени прибытия.

Положительными эффектами от внедрения ИТС будут считаться:

• -    более точное и более предсказуемое время прибытия в конечную точку маршрута;

• -    уменьшение совокупных затрат на выполнение тех же самых транспортных задач как отдельными участниками движения, так и в совокупности. Выбранные критерии были предложены в [2].

Учёт фактических параметров поездки для каждого ТС позволяет ввести в модель такие понятия как:

• -    Транспортное задание (Driving_task), под которым понимается задача доставки полезной нагрузки (пассажиров или груза) из одной заданной точки УДС в другую;

• -    Успешно выполненное транспортное задание, под которым понимается прибытие в конечную точку маршрута в заданный интервал времени.

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

• -    общее количество успешно выполненных транспортных заданий за заданный промежуток времени;

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

3.3.    Сценарии численного моделирования с использованием предложенной модели

Для доказательства наличия положительного эффекта от внедрения АУДД в ИТС с учётом выбранных критериев эффективности предполагается реализовать следующий сценарий моделирования:

• 1)    В качестве «простейшего», но тем не менее наиболее репрезентативного случая задаётся ситуация типичной суточной «миграции», например: передвижение от места проживания до места работы.

• 2)    Задаётся фрагмент УДС города, достаточно протяжённый, чтобы включить в себя, как минимум, два района: район начала большинства маршрутов и район окончания поездок; назовём их условно «жилой район» и «деловой район»;

• 3)    На всех перекрёстках в рамках сформированной модели УДС задаётся режим переключения фаз светофоров; задаются правила проезда перекрёстков (допустимые повороты и развороты); задаются временные характеристики проезда перекрёстков и участков дороги между перекрёстками («скоростной режим»);

• 4)    Для выбранного типа «миграции» генерируется «эталонная нагрузка»: совокупность N маршрутов на определённом интервале времени с заданными начальными (распределёнными равномерно случайным образом в «жилом районе») и конечными (распределёнными равномерно случайным образом в «деловом районе») точками маршрута и планируемым временем выезда; интенсивность выезда (количество ТС, стартующих в единицу времени) по времени подчиняется заданному распределению (например, Эрланга) в заданном временном интервале;

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

• 6)    После получения желаемого уровня «достоверности» работы имитационной модели «эталонная нагрузка» фиксируется, т.е. в дальнейшем - при отработке АУДД - нагрузка не генерируется каждый раз заново, а используется один и тот же набор транспортных заданий и времени выезда; при этом каждый раз после симуляции для каждого ТС записывается фактическое пройденное расстояние, фактическое время в пути и время прибытия в конечную точку;

• 7)    Проводится серия симуляций дорожного движения с использованием «эталонной нагрузки» и задействованием исследуемого АУДД, который может включать в себя:

• -    либо рекомендации (или предписания) водителям по изменению времени выезда (по сравнению с «эталонным»);

• -    либо динамическое изменение планов работы светофоров (изменение длительности фаз и абсолютного времени включения фаз);

• -    либо и то, и другое;

4.    Структура математической модели 4.1.    Структура доменов

полученные по результатам симуляций фактические времена и пройденные в процессе выполнения транспортных заданий расстояния сравниваются с «эталонными» (полученными на этапе 6)) и оценивается достигнутый эффект.

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

Мы не будем приводить в статье графическое представление UML-диаграмм всех доменов, за исключением отдельных примеров, а ограничимся словесным описанием.

Структура доменов и интерфейсы взаимодействия представлены на рис. 1.

Рис. 1. Структура, доменов программного комплекса.

В домене №1 «City_Map» задаётся карта, дорожной сети города, в виде направленного графа. Никакие преобразования информации не осуществляются, этот домен является поставщиком информации для других доменов.

В домене №2 «Crossroads» описывается конфигурация перекрёстков, задаются «правила, проезда» и осуществляется «регулирование проезда» - переключение сигналов светофоров.

Домен №3 «Driving Tasks» отвечает за создание нагрузки на УДС, т.е. генерирует множество транспортных заданий, которые должны быть выполнены за определённый промежуток времени.

В домене №4 «Motion_Simulator» происходит собственно симуляция движения ТС по УДС, с учётом работы светофоров и текущей фактической загрузки УДС.

Домен №5 «Router» (маршрутизатор) занимается преобразованием транспортных заданий (Driving_Tasks) в реальные маршруты с учётом текущей загрузки УДС, взятой из Motion Simulator.

Домен №6 «Routs_Schedules» содержит информацию о поездках, которые уже осуществляются: задан маршрут движения в виде последовательности рёбер, по которым должно «проехать» ТС, и ТС либо уже движется по УДС, либо стоит в очереди выезда на ребро графа в начальной точке маршрута.

Домен №7 «Traffic_Manager» как раз и должен будет реализовывать функцию управления дорожным движением, воздействуя на водителей и на светофоры. Наполнение этого домена будет описано детально в будущем, на этапе моделирования.

4.2.    Домен City Мар —

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

На рис. 2 представлен пример карты радиально-кольцевого типа, имитирующей структуру главных магистралей Москвы в пределах ТТК.

4.3.    Домен Crossroads

Конфигурация перекрёстков в терминах входящих и исходящих рёбер задаётся в домене «City_Map». Наличие дополнительного (отдельного от «City_Map») описания конфигурации перекрёстка необходимо по нескольким причинам: во-первых, в описании графа отсутствует возможность запретить некоторые виды переходов между рёбрами (например, поворот налево или разворот), во-вторых, эти правила могут меняться динамически, в то время как граф дорожной сети предполагается статичным; и наконец, в-третьих, в домене также есть метод, отвечающий за переключение сигналов светофоров. Светофоры функционируют либо в автономном режиме - по жестко заложенному плану, не подверженному изменениям извне домена, либо управляются командами домена №7 «Traffic_Manager». Вместе с доменом «City_Map» домен «Crossroads» служит поставщиком информации для прокладки маршрутов в домене №5 «Router».

4.4.    Домен Driving Tasks —

В этом домене создаётся нагрузка на УДС в виде множества «транспортных заданий» (т.е. поездок), которые должны быть выполнены за определённый промежуток времени. Причем нагрузка эта существует в двух видах:

• 1)    потенциальная нагрузка в виде множества планируемых поездок, которые либо реализуются так, как было запланировано (при определенных условиях), либо могут быть изменены или даже отменены;

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

4.5.    Домен Motion Simulator — 4.6.    Домен Router

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

Рис. 2. Пример представления радиально-кольцевой УДС в виде графа.

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

Поездки, которые уже осуществляются, описываются в домене №6 «Routes_Schedules». Как было описано ранее, на. определённом этапе моделирования потенциальная нагрузка, фиксируется в виде «эталонной».

Этот домен оперирует с теми ТС, которые уже приступили к осуществлению поездки, и движутся по маршрутам, описанным в домене «Routs_Schedules». Для того чтобы рассчитать положение конкретного ТС на. УДС домен обращается в домен «City_Map» за. параметрами рёбер графа, (длиной и вместимостью) и в домен «Crocssroads», чтобы узнать, в какой момент ТС можно переместить с одного ребра, графа, в маршруте на. другое. Также этот домен служит поставщиком информации о текущей фактической загрузке рёбер графа УДС в домен «Router» для прокладки маршрутов; а на этапе отработки АУДД -ив домен «Tra.ffic_Ma.na.ger» для выработки управляющих воздействий.

В этом домене потенциальная поездка (транспортное задание) преобразовывается в фактический маршрут. Сценарий взаимодействия доменов «DrivingTasks» и «Router» имитирует поведение водителя перед выездом, когда прокладывается маршрут поездки с учётом текущей загрузки УДС с помощью сервисов типа Яндекс-навигатор или Google Maps. Поскольку текущая загрузка УДС становится известна только в процессе симуляции движения, преобразование должно осуществляться непосредственно перед выездом, в отличие от потенциальной нагрузки, генерируемой заранее. Расчётный маршрут возвращается в домен «Driving Tasks» в качестве «рекомендуемого» (proposed). Если маршрут принимается к исполнению (акцептуется), он записывается в домен «Routes_Schedules» и ставится в очередь на исполнение. Таким способом закладывается возможность моделирования процесса вмешательства системы управления движением в процесс принятия решения водителем ТС на этапе отладки АУДД: если в прокладку маршрута будут внесены рекомендации (или предписания) Traffic_Manager-a, но предложенный вариант будет неприемлем для водителя, он может отказаться от поездки.

4.7.    Домен Routes Schedules —

Этот домен имеет самую простую структуру и состоит только из одного класса Route, его диаграмма приведена на рис. 3.

Рис. 3. Диаграмма, класса. Route домена. Routes_Schedules

Этим классом описывается множество всех проложенных маршрутов, которые в процессе симуляции становятся осуществлёнными поездками. На момент порождения маршрута в нем присутствуют расчётные данные о запланированной поездке:

• 1)    список рёбер графа, по которым положен маршрут (Path);

• 2)    планируемое время старта. (Pla.nned_sta.rt);

• 3)    ожидаемое время в пути (ЕТТ - Estimaged Travel Time).

5.    Модель движения

После завершения поездки добавляется информация о фактическом времени старта (Actual_Start) и фактическом времени завершения поездки (Finish_time). Пройденное расстояние всегда, может быть вычислено по набору рёбер графа. (Path), но для ускорения аналитической обработки данных после симуляции целесообразно это значение сохранить сразу, поскольку оно с необходимостью вычисляется в процессе прокладки маршрута. Сравнение запланированного и фактического времени поездки, как уже было сказано выше, позволяет судить об эффективности функционирования системы в целом и АУДД в частности.

На рис. 4 проиллюстрирован алгоритм расчёта, движения ТС по ребру графа, (участку УДС между двумя перекрёстками).

Рис. 4. Схема, расчёта, движения ТС по участку УДС между перекрёстками

Здесь:

N_max - «вместимость» ребра - максимальное количество ТС, которое может находиться на. данном ребре;

N_q - количество ТС, находящихся в очереди на выезд (ожидающих разрешающего сигнала. светофора);

N,,, - количество ТС, въехавших на данное ребро за время шага симуляции;

N_start ~ количество ТС, стартовавших на данном ребре за время шага симуляции (считается, что все ТС стартуют в начале ребра);

N - текущее количество количество ТС на УДС; N = N_q + N,,, + N_start.

В рамках данной модели считается, что г-е ТС преодолевает участок свободного движения от начала, ребра, до «хвоста, очереди» с постоянной скоростью, равной скорости движения по абсолютно свободной дороге, а. затем, встав в очередь на. выезд, перемещается к выезду по мере того как впереди стоящие ТС покидают очередь. Покинув ребро, ТС пересекает перекрёсток за время tcorss. Следовательно, время прохождения г-м ТС данного участка, дороги равно

Tpass — tf + tq + ^tcross^.

Работа, самого перекрёстка, моделируется с помощью метода, конечных автоматов. Таким образом исключается вероятность конфликтов, т.е. включения разрешающих сигналов одновременно на. нескольких направлениях, движение по которым привело бы к «столкновению» ТС. В процессе симуляции модуль «Motion_Simulator» последовательно перемещает ТС из очереди N_q на следующее ребро в маршруте г-го ТС, с учётом времени пересечения перекрёстка t_cross.

6.    Выводы

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

Работа, выполнена, на. кафедре ТЭРПИТ МФТИ.