Содержание к диссертации
Введение
ГЛАВА 1. Основные тенденции развития модельно-алгоритмического обеспечения компью-терных систем управления транспортными потоками 9
ГЛАВА 2. Анализ возможных подходов к моделиро-ванию транспортных потоков в городах 27
2.1. Постановка задачи 27
2.2. Структура оптимизационных задач 32
2.3. Подходы к построению модели 32
2.4. Уровни моделирования 34
2.5. Типы моделей 36
2.6. Пути реализации модели 38
2.7. Объект управления 40
2.8. Макро модели транспортного потока 42
2.9. Основные понятия и определения, касающиеся транспортного потока 42
2.10. Классификация пересечений 44
2.11. Взаимосвязь управляющих воздействий 45
2.12. Преобразование характеристик потока на элементах сети 47
ГЛАВА 3. Модельно-алгоритмические решения по оптимизации воздействий на транспортные потоки 49
3.1. Постановка задачи 49
3.2. Формализация оптимизационной задачи 49
3.3. Формирование целевой функции 52
3.4. Управляемый перекресток 55
3.5. Неуправляемый перекресток 57
3.6. Перегон 58
3.7. Построение операторов преобразования характеристик потоков 65
3.8. Критерии качества 66
3.9. Оценка критериальных функций 68
3.10. Модели и методы принятия управляющих решений 69
3.11. Анализ характера зависимости критериальных функций от управляющих воздействий 78
3.12. Формирование критериальных функций 83
3.13. Имитационное моделирование 89
ГЛАВА 4. Оценка эффективности методов расчета управляющих воздействий 99
4.1. Постановка задачи 99
4.2. Задачи, объект и методика проведения исследования 100
4.3. Порядок проведения исследования 101
4.4. Особенности проведения моделирования 102
Выводы и предложения 111
Список литературы 112
Приложение 119
- Подходы к построению модели
- Взаимосвязь управляющих воздействий
- Формализация оптимизационной задачи
- Особенности проведения моделирования
Введение к работе
Для большинства развитых стран мира, включая и Россию, во второй половине XX и начала XXI веков характерен значительный рост автомобильного парка. Если в 1970 г. автомобилей в мире было около 250 млн. единиц, то к 2004 г. - свыше 500 млн. единиц.
Сосредоточение основной массы автомобилей в пределах городских территорий вызывает огромные трудности в организации дорожного движения и обеспечении его безопасности.
Резкое снижение скоростей движения, острый дефицит городских площадей для организации кратковременной и длительной стоянки автомобилей, загрязнение окружающей среды, транспортный шум и, наконец, рост количества дорожно-транспортных происшествий (ДТП) -являются основными негативными последствиями автомобилизации, характерными для многих зарубежных городов. При этом необходимо отметить, что научно-технические прогнозы указывают на сохранение ведущей роли автомобильного транспорта в городах.
Отсюда следует, что автомобиль на ближайшие годы сохранит и усилит свое значение в качестве транспортного средства, а это еще более увеличит отрицательные последствия автомобилизации, если не будут предприняты соответствующие меры.
В г. Москве автомобильный парк за последнее десятилетие увеличился в несколько раз и в настоящее время составляет более 3 млн. автомашин.
При сложившемся дефиците протяженности магистралей в 250-300 км их плотность в 1,6 раза ниже нормативной. При этом 80% улиц, особенно в центральной части и срединной зонах города, практически исчерпали пропускную способность или работают на ее пределе, а кольцевые и поперечные связи, разгружающие центр составляют лишь 35-40% от потребности.
При таких показателях наиболее острой в дорожном движении стали проблемы участившихся заторов и автомобильных пробок.
Изучение зарубежного опыта показывает, что для управления транспортными потоками (ТП) на улично-дорожной сети (УДС) города прежде всего должна быть создана единая комплексная общегородская система управления, включающая оперативную связь с городскими службами, теленаблюдение, датчики контроля автотранспорта, электронные информационные табло и дорожные знаки с меняющейся информацией, указывающие водителям о возможных путях объезда сложных участков. В настоящее время г. Москва имеет лишь отдельные фрагменты такой общегородской системы, а регулирование дорожного движения остается прерогативой ГИБДД. С этой проблемой ГИБДД уже столкнулась при управлении транспортом на таких современных скоростных магистралях как МКАД и 3-е транспортное кольцо, где перераспределение транспортных потоков при осложнении обстановки осуществляется в основном «милицейскими» методами оперативного влияния, а не за счет полного использования технических средств регулирования.
В Советском Союзе первая экспериментальная система подобного назначения, имеющая в своем составе ЭВМ, была введена в действие в 1967г. в одном из районов Москвы. В 1975 году в г. Алма-Ате начала функционировать автоматизированная система управления дорожным движением, выполненная на базе ЭВМ и серийных технических средств, выпускаемых отечественной промышленностью.
Рядом научно-исследовательских институтов и проектно-конст-рукторских организаций страны в 70-е годы велась разработка и внедрение в городах России агрегатной системы средств управления дорожным движением (АСС-УД), которая представляет собой комплекс технических средств и программного обеспечения, позволяющих проектировать системы различной мощности и в широком диапазоне функциональных возможностей.
В комплексе мероприятий, направленных на решение задачи обеспечения нормального функционирования современного города в условиях повышенной автомобилизации, автоматизация управления дорожным движением занимает одно из ведущих мест. Работы по данной проблеме проводятся как в нашей стране, так и в целом ряде наиболее развитых зарубежных стран: США, Японии, ФРГ, Великобритании, Франции, Сингапуре, Канаде и др. В последние годы происходит процесс интенсивного внедрения автоматизированных систем управления движением транспортных потоков. Накопленный опыт эксплуатации таких систем убедительно свидетельствует о том, что они действительно являются эффективным средством сокращения задержек на городском транспорте, повышения скоростей движения, увеличения пропускной способности городских магистралей и уровня безопасности движения.
Широкое внедрение средств автоматизации управления дорожным движением, значительные затраты на внедрение и эксплуатацию АСУД определяют необходимость разработки моделей и методов расчета управляющих воздействий на транспортные потоки.
Цель диссертационной работы - разработка путем теоретического обобщения моделей ТП, а также методов принятия на их основе сетевых управляющих решений.
Достижение этой цели связано с необходимостью решения следующих задач: разработка методов, математических моделей и алгоритмов оптимизации сетевых воздействий на ТП: разработка стохастической модели для оценки качества принятия решений; анализ работоспособности методов и моделей. Основным научным результатом диссертации является создание комплекса моделей и алгоритмов, в совокупности составляющих методологию расчета сетевых воздействий на ТП.
Новизна работы заключается в постановке, формализации и решении задачи расчета воздействий на ТП по комплексу показателей, а также в стохастической модели анализа качества принятия решений.
На защиту выносятся следующие научные результаты:
1. Постановка и формализация задачи принятия сетевых управляющих решений.
2. Математические модели, методы решения.
3. Стохастическая модель оценки качества принятия решений. Достоверность результатов работы подтверждается апробированием научных основ исследования, базированием на фундаментальных трудах отечественных и зарубежных ученых, внедрением в практику.
Основной практический результат исследования - внедрение разработанных методов, математических моделей и алгоритмов в практику проектирования и функционирования компьютерных систем управления дорожным движением в городах.
Результаты диссертационной работы используются в учебном процессе МИЭМ и МАДИ (ГТУ).
Основные результаты диссертации опубликованы в Г работах.
Диссертация состоит из введения, трех глав, заключения, списка литературы и приложения.
Структура изложения материала следующая.
В первой главе дается анализ отечественных и зарубежных публикаций по направлениям исследования.
Во второй главе излагаются подходы к моделированию транспортного потока.
В третьей главе формируются показатели качества, приводятся постановки задач, модели и методы решения. Анализируются результаты расчетов.
В четвертой главе исследуется эффективность моделей и методов принятия решений.
В приложении приводятся дополнительные материалы исследования, а также документы, подтверждающие практическую ценность результатов исследования.
Подходы к построению модели
Описание и построение модели реальной системы - важнейший этап оптимизационного исследования, так как он определяет практическую ценность получаемого решения и возможность его реализации. Процесс оптимизации с использованием модели можно рассматривать как метод отыскания оптимального решения для этой реальной системы без непосредственного экспериментирования с самой системой. Обычно «прямой» путь, ведущий к оптимальному решению, заменяется «обходным», включающим построение и оптимизацию модели, а также преобразование полученных результатов в практически реализуемую форму. Такой подход к оптимизации системы требует использования некоторого упрощенного представления реальной системы. При формировании такого приближенного представления или модели следует учитывать только важнейшие характеристики системы, которые должны быть отражены в модели, а менее существенные особенности в модель можно не включать. Необходимо также сформулировать логически обоснованные допущения, выбрать форму представления модели, уровень ее детализации и метод реализации на ЭВМ. Указанные соображения относятся к этапу построения модели и являются в той или иной мере произвольными. Специалисты, обладающие одинаковым уровнем подготовки, рассматривая одну и туже реальную систему, могут предложить совершенно разные модели. Однако ни одну из таких моделей независимо от степени ее детализации и сложности нельзя считать единственно «правильной». Модели можно упорядочить по степени адекватности описания поведения реальной системы в представляющей интерес области эксплуатации. Таким образом, качество модели нельзя оценивать ни по структуре, ни по форме. Единственным критерием такой оценки может служить лишь достоверность полученных на модели прогнозов поведения реальной системы. Модель, включающую нелинейные функции, можно считать предпочтительнее линейной модели лишь при условии, что нелинейная модель более точно описывает реальную систему.
В то же время адекватность модели часто невозможно строго оценить и поэтому выбор той или иной модели в значительной степени субъективен. Так, например, одна модель может оказаться более адекватной, чем другая в определенном диапазоне измерения переменных, но менее точной в другом диапазоне. В этом случае может быть выбрана менее точная модель, поскольку она оказывается более точной в критической области. Иногда точность полной модели вообще невозможно оценить, а можно лишь судить о точности некоторых описывающих ее уровней.
Следует отметить, что соответствие модели моделируемой системе носит в лучшем случае правдоподобный характер. Поскольку модель по самой своей сути не более чем упрощение реальных соотношений, то не существует абсолютных критериев, с помощью которых можно было бы ранжировать модели. Всегда есть ситуации, требующие субъективной оценки и «предвидения» того, как поведет себя реальная система. Таким образом, компетентные специалисты могут разойтись во мнении по поводу деталей построения модели. Как следствие очень важно, чтобы разработчик модели детально знал моделируемую систему, понимал принципы, лежащие в основе компонентов модели, а в случае оптимизации проекта сам руководил всеми вычислениями, необходимыми для получения практически реализуемого проекта.
Обычно самым сложным этапом оптимизационного исследования является работа по созданию модели, так как она требует привлечения компетентных специалистов, хорошо знающих изучаемую систему. Поскольку стоимость создания моделей резко растет по мере детализации модели, необходимо тщательно продумывать уровень детализации, чтобы он соответствовал целям исследования и отвечал качеству доступной информации о системе. Очевидно, нет необходимости создавать детализированную динамическую модель работы предприятия, если для решения задачи достаточно иметь простую модель типа затраты - выпуск. Более того, бесполезно разрабатывать сложную модель, если доступная информация, по которой определяются коэффициенты модели, разрознена и ненадежна. С другой стороны, поскольку оптимизируется именно модель, а не реальная система, бессмысленно проводить оптимизационное исследование с упрощенной моделью, которая дает неправильное значение истинного оптимума системы.
При разработке модели стремятся к тому, что иногда называют «принципом оптимальной неточности»: модель должна быть настолько детализирована, насколько это необходимо для целей исследования, для которого ее создали. Однако достичь этой цели всегда трудно. Методом проб и ошибок можно развить навыки интуитивного выбора моделей подходящей сложности для отдельных видов систем, но обычно бывает трудно перенести этот опыт на другие приложения. Существует единственно надежный способ создания модели с оптимальным уровнем неточности, а именно метод постепенного совершенствования модели и методов оптимизации. Начав с самой простой модели, ее последовательно доводят до такого уровня, когда точность полученного значения оптимума соответствует точности используемой в модели информации. Однако этот трудоемкий процесс иногда требует больших затрат времени, чем возможно в условиях конкуренции. Для того чтобы получать результаты в заданные сроки и не проводить постепенного совершенствования модели, обычно подгоняют модель под оптимизационные методы, наиболее развитые к данному времени или освоенные специалистом, проводящим эту работу, или же использованные в предыдущем исследовании. Например, часто возникает желание формулировать все задачи как задачи линейного или геометрического программирования просто потому, что специалисту удобно работать с задачами такой структуры.
Взаимосвязь управляющих воздействий
С ростом интенсивности движения возникают ситуации (заторы), когда только средствами светофорной сигнализации невозможно обеспечить удовлетворительный уровень обслуживания участников движения. Ниже даны условия появления таких ситуаций. Проблема управления ТП большой интенсивности осложняется трудностью локализации заторов в границах их первоначального возникновения.
Под затором понимается такая ситуация на участке УДС со светофором, при которой средняя длительность задержки ТС превышает цикл. В этом случае возрастает длина очереди, достигающая длины перегона. При дальнейшем развитии подобного процесса парализуются большие участки сети и дезорганизуется процесс управления.
Заторы подразделяются на систематические (устойчивые) и случайные. Причиной случайных заторов являются различные случайные факторы, например, аварийные ситуации. Систематические заторы характеризуются периодической повторяемостью во времени и устойчивостью в пространстве. Такие заторы возникают на определенных направлениях движения на одних и тех же участках УДС в определенные интервалы времени, чаще всего - в "пиковые".
При оптимизации управления дорожным движением, как правило, ставятся задачи предсказания, распознавания и ликвидации предзаторовых ситуаций, не допуская возникновения заторов, что требует устранить причины, вызывающие перегрузки, путем перераспределения потоков по альтернативным маршрутам. Система управления ТП должна своевременно информировать водителей о возможности попадания в затор и рекомендовать объездные маршруты следования.
Методы управления ТП при заторе можно подразделить на методы реального масштаба времени и методы, в основе которых лежат исходные данные о параметрах потоков, относящиеся к моменту времени, предшествующему тому, для которого рассчитываются воздействия. Исходные данные в последнем случае могут относиться и к каким-либо "типовым" ситуациям. Примером может служить метод управления, основанный на использовании аналога "библиотеки" программ для ненасыщенных потоков. В результате натурных наблюдений выявлено, например, М типовых ситуаций для объекта. Для каждой из них рассчитываются соответствующие воздействия. В процессе функционирования системы измеряются параметры потоков и, если эти параметры приближаются к параметрам некоторого типового набора из М возможных, то системой отрабатываются соответствующие воздействия.
Рассмотрим на примере простейшего пересечения с двухсторонним движением и многофазным управлением взаимосвязь управляющих воздействий и характеристик ТП. Пусть qjk - интенсивность / -го потока в к-й фазе; Cik - поток насыщения, соответствующий і -му потоку; g; -длительность і-го разрешающего движение сигнала; lik - потери времени в цикле, относящиеся к потоку с интенсивностью qik; п - число фаз управления (рис. 1).
Формализация оптимизационной задачи
Чередование периодов запрета и разрешения движения транспортных средств через перекресток приводит к образованию групп. Эти группы «распадаются» по мере движения по перегону (из-за различия в скоростях отдельных транспортных средств), что математически описывается изменением временной зависимости интенсивности потока.
Задача нахождения взаимосвязи интенсивностей на выходе и входе перегона по существу является задачей построения модели, обеспечивающей возможность на основе значений интенсивности в дискретные моменты времени в прошлом (на входе перегона) ql,...,q„ предсказать значения ql+„,...,q„+r в будущем (на выходе перегона). Наличие лишь статистических данных не позволяет получить достоверный прогноз -необходима модель, удовлетворяющая ряду требований, обусловленных спецификой объекта: она не должна меняться с изменением масштаба; должен учитываться временной фактор, т.е. данные, относящиеся к намного более поздним моментам времени по сравнению с моментом, определяемым разностью момента наблюдения и среднего времени движения до рассматриваемой точки, практически не должны существенно влиять на результат.
Основываясь на методах статистического прогнозирования и зная временную зависимость q(t) интенсивности потока на выходе перекрестка (входе перегона), можно построить модель, позволяющую определить величину интенсивности #,(/) в точке, в которой оказываются транспортные средства спустя время t.
Базируясь на упомянутых методах, значение интенсивности ТП в прогнозируемый момент времени t можно представить в виде суммы: где p{t) - в некотором смысле трендовая составляющая; v(t)- случайная составляющая. При определенных предположениях относительно p(t)n v(0 (математическое ожидание v равно 0, дисперсия конечна и др.) экстраполяция для различных моментов (t + m) может быть связана рекуррентной формулой, в состав которой входит конечное число значений q(t) и ее экстраполяции qx(t) [10]: - параметры. В Великобритании проводилось специальное исследование, в результате которого был разработан метод предсказания среднего «распада» группы транспортных средств по известным в дискретные моменты времени і Т/50 (і=1,..., 50; Т - длительность цикла) значениям интенсивности ТП, убывающего от перекрестка. Предложено следующее рекуррентное выражение (частный случай приведенной выше формулы) где t — среднее время движения по перегону; q (i)- интенсивность ТП на входе перегона в интервале времени і (периодическая, с периодом, равным 50, функция); q(i)— интенсивность ТП на выходе перегона в интервале времени і; /- сглаживающий коэффициент. Экспериментально установлено Модель описывает преобразование интенсивности ТП на перегоне магистрали. Более простая модель приводится в п.. На рис. 5, 6 представлены типичные временные зависимости интенсивности потока на входе и выходе перегона (данные относятся к ул. Герцена г. Омска). Рассмотрим перекресток, к которому прибывает транспортный поток. Экспериментальные исследования показывают, что при большой загрузке дорожной сети интенсивность потока может быть аппроксимирована кусочно-постоянной функцией [9] так, как это изображено на рис. 7, на котором через т обозначен интервал времени от начала (момента включения.
Особенности проведения моделирования
Чтобы воспользоваться моделью, ее надо сначала построить. А объект сложен. На помощь приходят такие приемы моделирования, которые позволяют представлять модель не в аналитическом виде, а в виде машинной программы.
Когда модель задана аналитически, ее исследование - дело математика. А если у него возникают технические трудности, то на помощь можно призвать ЭВМ и численные методы анализа. Для моделей, заданных программно, первый путь невозможен. Их приходится исследовать эмпирически, «проигрывать» на ЭВМ различные варианты. Но такое «проигрывание» вариантов должно быть целенаправленным, организованным и оптимальным (хотя бы в смысле экономии машинного времени).
Инструментом исследования служит ЭВМ. Поначалу развитие ЭВМ связывали лишь с революцией чисто количественной. Но постепенно стали понимать, что открылась возможность качественно новой постановки задач. Одним из первых примеров такого рода явился метод Монте-Карло, позволивший экспериментировать на математических моделях с помощью ЭВМ. Метод Монте-Карло в широком смысле - любой способ решения задачи, в котором используются случайные или псевдослучайные числа.
Случайные числа — это случайные величины, которые равномерно распределены на интервале (0, 1) и стохастически независимы. Псевдослучайные числа генерируются с помощью детерминированной алгебраической формулы; порождаемые числа для практических целей можно считать случайными, равномерно распределенными в интервале (0,1) и независимыми. В основе реализации метода - процедура получения случайных чисел или случайных последовательностей. Из генерированных случайных чисел можно строить случайные величины с требуемыми законами распределения. Идея всякого моделирования, в том числе имитационного, предполагает наличие модели, заданной в том или ином виде. Причем речь идет о моделях далеко не тривиальных систем. Среди частных моделей, широко применяемых в имитационном моделировании, следует назвать модели теории массового обслуживания. Их выдающаяся роль объясняется просто тем, что многие моделируемые системы удобно рассматривать как системы, обслуживающие случайный поток клиентов.
Следует отметить, что многие имитационные исследования используют последовательности случайных чисел и, следовательно, являются формой метода Монте-Карло. Моделирование предполагает экспериментирование, но экспериментирование не с реальным объектом, а с его моделью. Поведение объекта ра сматривается во времени.
Моделирование не обязательно требует случайных чисел. Детерминистическое моделирование очень широко применяется в экономике. Экономические модели состоят из регрессионных уравнений, которые содержат стохастические возмущения (или ошибки).
Стохастическое моделирование предполагает экспериментирование с абстрактными моделями во времени с использованием выборок случайных величин из их распределений.
Поскольку моделирование - это эксперимент во времени, то его методы можно использовать для изучения динамического поведения систем. Особенно если модель содержит случайные величины, тогда даже простая модель может стать непреодолимой для аналитического исследования. Может случиться, что интерес представляет не динамическое поведение системы, а какие-то установившиеся режимы. Но даже в этом случае моделирование может оказаться необходимым, если переменные взаимодействуют сложным образом.
Моделирование используется для сложных систем. Часто больше известно о поведении компонент такой системы, чем о поведении в целом. Блок-схема показывает сами элементы системы, их реакции и взаимное влияние. Математические описания для каждого элемента обычно очень просты; не обязательно это линейные уравнения, могут быть и нелинейные уравнения или неравенства. Каждый элемент воздействует на другие элементы; взаимодействия и делают сложной модель. Если модель основана на знании поведения компонент системы, а не всей системы в целом, говорят о модульной или блочной конструкции или методе декомпозиции.
Имитационное моделирование имеет свои трудности и проблемы. Даже на современной вычислительной машине может потребоваться слишком много времени для выполнения одного «прогона», т.е. одного прохождения системы от начала до конца моделируемого периода времени. Кроме того, этот эксперимент дает значение выхода только для некоторых частных значений параметров и независимых переменных системы, установленных именно в этом опыте (параметры системы - это те характеристики, которые остаются постоянными в течение одного опыта-прогона). Моделирование не дает функциональной связи выхода с независимыми переменными и параметрами. Поэтому требуются новые прогоны с одним или несколькими наборами новых значений параметров.
Изложенное означает, что оптимальное решение для системы можно попробовать получить только экспериментально, т.е. требуется «попробовать» различные наборы параметров для приближения к оптимальному набору.
