Оптимизация транзитных маршрутов транспорта через выбранные точки в населенных пунктах

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

Оптимизация транзитных маршрутов транспорта через выбранные точки в населенных пунктах

Е.К. Акинов

Аннотации

Берілген ж?мыста К?кшетау ?аласы ар?ылы ?тетін транзиттік автотранспортты? е? ?ыс?а маршрутын Дейкстра алгоритмі ар?ылы аны?тау оптимизациялы? есебі к?рсетілген.

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

This article is devoted to the solution of the optimization task on the determining of the transit vehicle shortest ways through Kokshetau using the Deykstra algorithm.

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

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

В связи с этим необходимо более четко решать вопросы разделения пассажирского и грузового движения, а также рациональной организации транзитного движения [1]. От выбора рациональной организации транзитного движения, рассеивания потока транспорта и ликвидации заторов на улицах больших городов зависит сокращение времени пребывание в городе транспортных средств, следствием которого является сокращения вредных влиянии транспорта на воздушную среду города. Немалую нагрузку на магистральную сеть создает транзитный пассажирский и легковой индивидуальный транспорт. Она сосредоточена в центральных районах города. Именно эта нагрузка формирует основные требования к магистральной сети города. Разработки программных продуктов, позволяющих выбрать оптимальный маршрут движения транзитных транспортных средств в больших городах с интенсивным потоком движения, на сегодня достаточно не изучены. Определение кратчайших маршрутов, с учетом интенсивности потоков движения, качества дорог и перекрестков с помощью алгоритмических программ позволяют принимать научно-обоснованные решения по сокращению расстояния маршрутов через определенные точки городов. маршрут транзитный автотранспорт

Наиболее известным и популярным способом решения задач оптимизации маршрутов является применение графов маршрутов. При численном решении задач на компьютерах граф должен быть представлен дискретным способом. Существует довольно много способов такого рода представления графов. Однако простота использования представления графа, как и эффективность алгоритма, в основе которого он лежит, в полной мере зависит от конкретного выбора этого представления. Одно из направлений теории графов связано с их матричным представлением. Существуют различные виды матриц, ассоциированные с графами. Эти алгебраические формы используются для решения многих задач теории графов. Один из известных динамических алгоритмов - алгоритм Дейкстры, где все данные удобно задать в виде матрицы весов [1]. В матрице весов легко учитывать следующие величины влияющие на движения транспорта: влияние качества дорог на скорость с определенной степенью точности; количество перекрестков; время задержки на светофорах; среднюю скорость передвижения транспорта в определенных отрезках дорог и другие факторы. Матрица весов позволяет менять маршруты передвижения при временном отсутствии движения в определенных отрезках дорог, например во время ремонтных работ. С учетом определенного количества факторов можно моделировать передвижения любого транспорта через заданные точки городов и выбрать оптимальный маршрут передвижения. С помощью бортовых компьютеров автомобилей можно находить трассу кратчайшего пути алгоритмом Дейкстры в любом городе, при этом точность решения зависит от степени моделирования входных данных, т.е. от матрицы весов. Следует отметить высокую эффективность алгоритма Дейкстры и его широкую применимость в окружающем нас мире. Не только транспортные, но и другие производственные и экономические задачи можно решить с его помощью [2].

Ниже рассматривается задача определения кратчайшего маршрута транзитного пассажирского транспорта по маршруту Петропавловск - Астана через автовокзал города Кокшетау, где наиболее интенсивный поток транспорта. Новизна исследования состоит в том, что в условиях города Кокшетау моделируется задача сокращения маршрутов транзитных пассажирских транспортных средств. Для моделирования задачи были изучены УДС города Кокшетау. В матрице весов учтены следующие факторы: влияние на скорость передвижения транспорта состояния дорог, влияние количества конфликтных точек, влияния регулируемых и нерегулируемых перекрестков. С учетом всех этих факторов был создан граф маршрута и назначены расстояния между вершинами в графе [1]. На рис.1 и рис 2. показаны граф транзитного маршрута и схема возможного передвижения транспорта на карте города. Вершины графа: 0 - въезд в город, 8- автовокзал, 19- выезд из города, выбраны на карте города всего 20 вершин графа. Обратные стрелки на графе показывают что движение в обратном направлении разрешено, в матрице весов они должны быть учтены. Алгоритм Дейкстры был реализован на языке Паскаль, составлена программа и его результаты приведены ниже.

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

Рис.1. Граф маршрута Петропавловск-Астана через Кокшетау

Рис. 2. Схема возможного передвижения транспорта по городу

Матрица весов приведена в таблице 1. Для облегчения ввода данных расстояния между узлами умножены на 10, т.е. в км х 10.

Таблица 1 - Матрица весов

Результаты вычисления по программе, реализованной по алгоритму Дейкстры:

1. маршрут передвижения от въезда до вокзала через вершины: 0 1 2 13 14 5 6 9 18 7 8 (длина маршрута 8,1 км) и от вокзала до выезда: 8 7 18 15 16 17 11 19 (длина маршрута 6,7 км). Следовательно кратчайший маршрут имеет длину 14,8 км.

2. В случае прямого проезда через город (не заезжая на автовокзал) маршрут проходит через вершины: 0 1 2 13 14 5 6 9 10 11 19 (длина 12,6 км)

По сравнению с другими маршрутами, например 0 1 2 3 12 4 6 9 18 7 8 до вокзала и 8 7 18 15 16 17 11 19 от вокзала оптимальный маршрут короче на 2,4 км. Если техническая скорость движения внутри города составляет в среднем 20 км/час [5] то для преодоления расстояния 2,4 км автобус затрачивает в среднем 8-9 минут времени или сжигает в среднем в городском цикле 1,5 литра дизельного топлива. За один месяц в данном маршруте, в среднем, проходит 1100 автобусов (по статистике УДП города за 2008-2009гг.), тогда экономия от сокращения маршрута позволяет не сжигать в городе 1,65 тысяч, а в год около 20 тысяч литров топлива, что существенно облегчает экологическую обстановку в районе маршрута.

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

Литература

1. Смехов А.А. Основы транспортной логистики. Учебник для вузов. - М.: Транспорт, 2001. 454 с.

2. Берж К. Теория графов и ее применения. -М.: ИЛ. 2002. 300 с.

3. Грин Д., Кнут Д. Математические методы анализа алгоритмов. - М.: Мир, 1997. С 122-134.

4. Оре О. Теория графов. - М.: Наука, 2005. 200 с.

5. Форд Л.Р., Фалкерсон Д.Р. Потоки в сетях. -М.: Мир, 2007. С 224-245.

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