Разработка и применение инструментального средства для расчета маршрутов транспортных средств в условиях города Краснодара

Размещено на http://www.allbest.ru/

Разработка и применение инструментального средства для расчета маршрутов транспортных средств в условиях городА краснодарА

Лойко Валерий Иванович

Параскевов Александр Владимирович

Бариев Руслан Рафаэльевич

студент факультета прикладной информатики

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

Ключевые слова: ТРАНСПОРТНЫЙ ПОТОК, АВТОМОБИЛЬНАЯ ДОРОГА, ЭКОНОМИЧЕСКАЯ ЭФФЕКТИВНОСТЬ, равновесие транспортной сети, алгоритм Флойда-Уоршалла, ГРАФИК.

ВВЕДЕНИЕ

Отличительной чертой современного мегаполиса являются пробки на дорогах. По данным ГИБДД РФ в стране 30 миллионов автолюбителей. Основная их масса сосредоточена именно в крупных городах. Весенне-летний период отличается увеличением количества автомобилей на дорогах страны и ростом объемов грузоперевозок. Способов борьбы с пробками достаточно много. Один из них - за счет грамотного планирования загрузки транспортных магистралей. Европейские и американские компании активно внедряют различные системы транспортного контроля на развитой сети платных дорог. Это экономически выгодное вложение капитала: современные «умные» дороги - значительная статья дохода экономики страны. Однако у всех решений есть существенный недостаток. Они требуют от владельцев частных дорог вложения огромных средств, которые окупятся лишь через 10-20 лет.

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

Задачи:

1. Обзор существующих методов решения задачи;

2. Разработка инструментального средства для нахождения кратчайших путей на графе микрорайона «Юбилейный» города Краснодара на основании расчетов, произведенных с помощью алгоритма Флойда-Уоршалла.

городской транспортный путь уоршалл

Алгоритм Флойда - Уоршалла

В этом алгоритме используется представление графа в виде матрицы. Предполагается, что вершины пронумерованы как 1,2,…,|V|, и в роли входных данных выступает матрица W размером n*n,представляющая веса ребер ориентированного графа G=(V,E) c n вершинами. Другими словами, W=(w_ij).

Чтобы решить задачу о поиске кратчайших путей между всеми парами вершин с входной матрицей смежности, необходимо вычислить не только веса кратчайших путей, но и матрицу предшествования P(p_ij), где величина p_ij имеет нулевое значение, если j=i или путь из вершины i в вершину j отсутствует; противном случае p_ij - предшественник вершины j на некотором кратчайшем пути из вершины i.

Алгоритм Флойда - Уоршалла основан на применении динамического программирования. Алгоритм итеративно строит матрицу кратчайших расстояний между вершинами графа.

Транзитивное замыкание графа отношения. Алгоритм Флойда - Уоршалла.

Алгоритм умножения матриц требует порядка n4 простых логических операций. Алгоритм Флойда - Уоршалла требует лишь n3 простых операций и не требует дополнительной памяти под промежуточные матрицы.

Пусть матрица G(l) представляет собой граф путей (рис. 1), проходящих через промежуточные вершины с номерами от 0 до l -1 (рис. 2,3), то есть в матрице G(l) единица находится в ячейке (u,v), если в исходном графе существовал путь из u в v, проходящий только через вершины из множества {0,… l -1}, u и v в это множество не входят. Тогда что такое матрица G(l+1)?

Рисунок 1 - Начальный граф путей

G(l+1)[u,v] = G(l)[u,v] || G(l)[u,l] && G(l)[l,v]

Рисунок 2 - Граф путей проходящих через промежуточные вершины

G^(l+1)[u,v] = 1, если G^(l)[u,v] == 1

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

G^(l+1)[u,v] = 1, если G^(l)[u,l] == 1 && G^(l)[l,v] == 1

Применение алгоритма Флойда - Уоршалла для поиска кратчайших путей

Пусть матрица G(l) представляет собой граф кратчайших путей (рис. 6), проходящих через промежуточные вершины с номерами от 0 до l -1. То есть в матрице G(l) в ячейке (u,v) находится длина кратчайшего пути из u в v, если он существовал, проходящий только через вершины из множества {0,… l -1}, u и v в это множество не входят. Если пути из u в v не было, то в соответствующей ячейке матрицы будет значение ?.

Рисунок 4 - Граф кратчайших путей.

G(l+1)[u,v] = min(G(l )[u,l] + G(l )[l,v], G(l )[u,v])

На рисунке 5 представлен алгоритм инициализации матрицы предшествования, который является неотъемлемой частью разрабатываемого программного комплекса.

Рисунок 5 - Алгоритм инициализации матрицы предшествования.

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

Рисунок 6 - Алгоритм итеративного вычисления расстояния.

Данный программный продукт предназначен для поиска оптимального маршрута, где в качестве критерия выбрана загруженность улицы. То есть стоит задача минимизации времени проезда к заданной точке в реальных городских дорожных условиях. На рисунке 7 представлен граф микрорайона «Юбилейный», на котором с помощью алгоритма Флойда - Уоршалла будем прокладывать кратчайшие пути между двумя произвольно взятыми вершинами.

Рисунок 7 - Граф Юбилейного района.

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

Исходя из этого, в качестве весов будут использоваться параметры загруженности улицы, рассчитанные по итогам выполнения студенческой научной работы Чемеркиной А.А. и опубликованные в Политематическом Сетевом Электронном Научном Журнале Кубанского Государственного Аграрного Университета в ноябре. Эти данные приведены в таблице 1.

Таблица1 - Статистические параметры загруженности улиц.

Сама же архитектура программного комплекса, реализующего вышеприведенные алгоритмы, приведена на рисунке 8.

Рисунок 8 - Архитектура программного комплекса.

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

Язык C# заслужил большое уважение и популярность среди разработчиков самых разных программных продуктов. Последнюю пару лет C# играл важную роль в производстве устойчивых к сбоям продуктов -- от настольных приложений до Web сервисов, от высокоуровневых решений в автоматизации бизнес-процессов до программ системного уровня и от однопользовательских продуктов до корпоративных решений в сетевых распределенных средах. Зная о мощных средствах этого языка, можно задаться вопросом: нельзя ли использовать C# и Microsoft.NET Framework не только для GUI- и Web-компонентов? Готово ли научное сообщество воспринимать их всерьез при разработке кода для высокопроизводительных вычислений?

Ответ не вполне очевиден, поскольку сначала надо ответить на многие другие вопросы. Например, что такое научные вычисления? Чем они отличаются от обычных вычислений? Действительно ли у языков есть характеристики, по которым можно решить, насколько они соответствуют требованиям научных программ?

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

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

Описание процесса работы программы

При запуске исполняемого файла navigator.exe на экране появится главное окно программы, представленное на рисунке 9.

Рисунок 9 - Главное окно программы

В данном окне показана карта микрорайона «Юбилейный». Для указания маршрута необходимо выбрать начало пути и его конец. Это делается путем выделения первого checkbox и конечного однократным нажатием левой кнопки мыши.

В основе данной карты лежит граф микрорайона представленный на рисунке 7.

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

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

Мы выбрали начало пути, в данном случае будем считать, что этой точкой является перекресток улиц 2-я Линия с улицей Калинина. Далее мы должны выбрать конец пути. Для этого установим флажок на перекрестке улиц Кожевенная - Брюсова.

Рисунок 11 - Окно после выбора точки прибытия.

Как видно программа проложила минимальный маршрут на основе загруженности дорог.

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

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

Рисунок 12 - Окно о программе.

На рисунке 12 показано окно «About» с информацией об авторах данного программного продукта, реализующего алгоритм Флойда - Уоршалла для поиска кратчайших путей на ориентированном графе, построенном на основании карты микрорайона «Юбилейный» города Краснодара.

ЗАКЛЮЧЕНИЕ

В ходе изучения проблемы связанной с пробками на дорогах в крупных городах, был адаптирован алгоритм нахождения кратчайших путей на основе графа, построенного по карте микрорайона «Юбилейный» города Краснодара.

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

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

Результаты работы были внедрены в деятельность ООО «РенКапСтрой» и используются при проектировании прокладки городской автодороги, при составлении плана застройки городского микрорайона (жилого комплекса), при строительстве многоквартирных жилых домов и проектировании гаражей и подземных или надземных парковок при них.

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

СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ

1. Автомобильные дороги. Строительные нормы и правила. СНиП 2.05.02-85. М.: Государственный комитет СССР по делам строительства, 1986. - 62 с.

2. Автодороги промышленных предприятий. Строительные нормы и правила. СНиП 2.05.07-85. М.: Государственный комитет СССР по делам строительства, 1989. - 82 с.

3. Бабков В.Ф., Андреев О.В. Проектирование автомобильных дорог. Т.1. 2-е изд. - М.: Транспорт, 1987.- 368 с.

4. Бабков В.Ф., Андреев О.В. Проектирование автомобильных дорог. Т.2. 2-е изд. - М.: Транспорт, 1987.- 415 с.

5. Бируля А.К. Проектирование автомобильных дорог. Ч. 1. 4-е изд. - М.: Научно-техническое издательство министерства автомобильного транспорта и шоссейных дорог РСФСР, 1961. - 199 с.

6. Внутрихозяйственные дороги сельхозпредприятий и организаций. Строительные нормы и правила. СНиП 2.05.11-83. М.: Государственный комитет СССР по делам строительства, 1984. - 26 с.

7. Лавриненко Л.Л. Изыскания и проектирование автомобильных дорог. - М.: Транспорт, 1991. - 296 с.

8. В.И. Лойко, А.В. Параскевов, А.А. Чемеркина Разработка и применение инструментального средства расчета характеристик городских автомобильных дорог (на примере г. Краснодара) // Научный журнал КубГАУ [Электронный ресурс]. - Краснодар: КубГАУ, 2008. - №09(43). - http://ej.kubagro.ru/2008/09/pdf/08.pdf

9. В.И. Лойко, А.В. Параскевов, А.А. Чемеркина Математическая модель расчета экономических параметров управления транспортными потоками // Научный журнал КубГАУ [Электронный ресурс]. - Краснодар: КубГАУ, 2008. - №10(44). - http://ej.kubagro.ru/2008/10/pdf/06.pdf

10. Параскевов А.В. Совершенствование управления дорожным движением (обзор), Научный журнал КубГАУ, №37(3), 2008 года, http://www.ej.kubagro.ru/

11. Параскевов А.В., Чемеркина А.А. Совершенствование модели управления транспортными потоками, Научный журнал КубГАУ, №42(8), 2008 года, http://www.ej.kubagro.ru/

12. Параскевов А.В. «Инструментальное средство организации городского дорожного движения», 2-я Всероссийская научно-практическая конференция молодых ученых «Научное обеспечения агропромышленного комплекса», Кубанский государственный аграрный университет, 2008.

13. Параскевов А.В. «Предпосылки совершенствования управления дорожным движением» Информационные технологии в экономике и образовании: Материалы международной научно-практической конференции студентов и аспирантов «Информационные технологии в экономике и образовании», посвященной 95-летию Российского университета кооперации. - М.: Российский университет кооперации, 2008. - 190с. (стр. 81-83).

14. Проектирование автомобильных дорог. Справочник инженера дорожника/ под ред. Г.А. Федотова. - М.: Транспорт, 1989. - 437 с.

15. "Руководство по прогнозированию интенсивности движения на автомобильных дорогах" (для опытного применения), распоряжение министерства транспорта РФ 19 июня 2003 г. № ОС-555-р (д).

16. Указания по обеспечению безопасности движения на автомобильных дорогах. ВСН 25-86. МИНАВТОДОР РСФСР. М.: ТРАНСПОРТ, 1988.

17. Федеральный закон Российской Федерации от 8 ноября 2007 г. N 257-ФЗ "Об автомобильных дорогах и о дорожной деятельности в Российской Федерации и о внесении изменений в отдельные законодательные акты Российской Федерации".

18. Sheffi, Y. Городские транспортные сети: Анализ устойчивости с помощью методов математического программирования, Prentice-Hall, Englewood Cliffs, 1985, New Jersey.

19. «Ferrari» Цена на проезд и равновесие транспортной сети. Транспортное исследование Б, 1995 №29, 357-372.

20. Evans A. W.Цены за проезд в пробках: когда это хорошая политика? Journal of Transport Economics and Policy 1992 №26, 213-243.

Размещено на Allbest.ru