«Оптимизация перевозок пассажиров автобусным транспортом в районе Медведково с помощью теории графов»



Дата09.03.2019
өлшемі147.25 Kb.


Министерство образования Российской Федерации

Департамент образования города Москвы

Государственное бюджетное общеобразовательное учреждение

города Москвы «Лицей № 1568 имени Пабло Неруды»



Проектная работа на тему:

«Оптимизация перевозок пассажиров автобусным транспортом в районе Медведково с помощью теории графов»

Выполнил:

Бирюков Владислав Павлович,

ученик 10 класса «В» ГБОУ города Москвы

«Лицей 1568 имени Пабло Неруды»
Руководитель:

Синькова Ольга Владимировна,

учитель математики ГБОУ города Москвы

«Лицей 1568 имени Пабло Неруды»

Москва

2016
Оглавление




Введение………………………………………………………..

3

Глава 1. Теория графов – раздел дискретной математики…..

4

    1. Теория графов от задачи Л. Эйлера до наших дней

4

    1. Основные понятия теории графов……………….

5

Выводы по главе 1……………………………………………...

6

Глава 2. Оптимизация движения автобусов в районе

Медведково ……………………………………….….


7


2.1. Теория графов и транспортные задачи ……...….

7

2.2. Анализ пассажирского автобусного транспорта в районе Медведково ………………………………….

8


2.3. Предложения по оптимизации перевозок пассажиров автобусным транспортом по маршрутам №№ 61, 174……………………………………………….

9


Выводы по главе 2………..……………………………………

11

Заключение……………………………………………………….

12

Список литературы………………………………………………

13

Приложения………………………………………………………

14

Введение

Пользуясь транспортной сетью Москвы и, в частности, передвигаясь по районам Южное и Северное Медведково, я подумал, что транспортная сеть на данный момент реализована не совсем оптимально для пассажиров. Стоя на остановках в ожидании своего автобуса, я часто слышал разговоры пассажиров о том, что люди вынуждены ехать с маленьким заболевшим ребенком в поликлинику, при этом им приходилось делать пересадку и дополнительно ожидать автобуса, иногда в не простых погодных условиях. А инвалиды? Для них делается много, но пересадки из автобуса в автобус явно усложняют и без того не легкое их передвижение. Мне захотелось помочь таким людям. Время всегда было важным фактором в жизни человека. С введением онлайн записи на услуги, когда, можно удаленно записаться к специалисту на определенные часы, приобрела большее значение необходимость точно рассчитать время, исключить опоздания и вовремя получить услугу. И здесь встаёт вопрос о поиске маршрута, который позволит снизить финансовые затраты, сократить время на пересадки.



Цель работы: выяснить, возможно, ли улучшить перевозки населения пассажирским автобусным транспортом в районе Медведково.

Задачи: изучить основные положения теории графов и особенности применения графов в транспортных системах; проанализировать маршруты пассажирского автобусного транспорта в Медведково; сделать выводы о возможности оптимизации перевозок пассажиров в районе Медведково.

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

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

В процессе работы над проектом, мною изучены статьи и книги отечественных [2, 3, 7] и зарубежных авторов [8], интернет – ресурсы [1,4,5,6], различные энциклопедические источники.

Глава 1.

Теория графов – раздел дискретной математики


    1. Теория графов от задачи Л. Эйлера до наших дней

В 1736 году в Санкт-Петербурге вышла в свет статья математика Леонарда Эйлера с его знаменитыми рассуждениями о Кенигсбергских мостах, которая положила начало новой математической теории – теории графов. Затем около 100 лет эта статья оставалась единственной, а методы теории графов невостребованными практикой.

Интерес к графам появился только в середине 19 века. В 1847 году немецкий физик Густав Кирхгоф использовал схемы, подобные графам, при изучении электрических цепей. В 1857 году английский математик Артур Кэли изучал число изомеров органического соединения с помощью графов, в которых точки соединялись линиями по числу химических связей. В 1869 г. анализом абстрактных древовидных структур занимался французский математик Мари Энмон Камиль Жордан. В 1859 г. ирландский математик Уильям Роуэн Гамильтон придумал игру, на основе которой были созданы гамильтоновы цепи, имеющие интересное применение. Множеству новых исследований в теории графов положила начало «проблема четырёх красок» - задача, которую сформулировал Фрэнсис Гутри в 1852 году. Теорема о четырёх красках была доказана в 1976 г. математиками Кеннетом Аппелем и Вольфгангом Хакеном  из Иллинойского университета. Схемы из точек и линий использовали известный психолог Курт Левин – для изображения отношений между людьми; физики Уленбек, Ли и Янг для изображения структур молекул и взаимодействия между ними 8, с.16.

В течение ХХ века развитию теории графов способствовали труды таких выдающихся учёных, как Уильям Томас Татт, Фрэнк Харари, Эдсгер Вибе Дейкстра и Пол Эрдёш. Непрерывно расширялась сфера применений теории графов в самых разных областях – в социологии, архитектуре, урбанистике, особенно в информатике и телекоммуникациях.


    1. Основные понятия теории графов

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

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

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

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

Если на рёбра графа нанести стрелки, обозначающие направления, то они будут называться ориентированными рёбрами или дугами 8, с.19.

Граф, у которого все рёбра являются ориентированными, называется ориентированным или орграфом 8, с.19. Дуга такого графа представима в виде упорядоченной пары вершин (v, w), где вершина v называется началом, а w — концом дуги.

Маршрут графа — это конечная последовательность, в которой чередуются вершины и ребра. Эта последовательность начинается и кончается вершиной, в которой каждое ребро инцидентно двум вершинам.

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

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

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

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

Выводы по главе 1

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

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

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


Глава 2. Оптимизация движения автобусов в районе Медведково

2.1. Теория графов и транспортные задачи

В теории графов транспортная сеть — ориентированный граф, в котором каждое ребро имеет неотрицательную пропускную способность и поток. Выделяются две вершины: источник и сток такие, что любая другая вершина сети лежит на пути из источника в сток. Транспортная сеть может быть использована для моделирования, например, дорожного трафика.

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

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

Если вам необходимо спланировать поездку, вы можете использовать граф, отметив на нём не только промежуточные пункты пути, а так же время движения и ожидания, финансовые расходы и многое другое.

«Количество автомобилей, которые могут проехать по каждому отрезку дороги за единицу времени, не безгранично: оно определяется такими факторами, как ширина проезжей части, качество дорожного покрытия, действующие ограничения скорости движения и т.д. (обычно это называют пропускной способностью дороги)» 7, с.52.



2.2. Анализ пассажирского автобусного транспорта

в районе Медведково

Автобус  – массовый безрельсовый уличный вид транспорта. Характеризуется высокой маневренностью. Не требует специальных путевых устройств. Движение осуществляется по городским дорогам, поэтому капитальные вложения в обустройство автобусных линий включают только строительство остановочных пунктов и разворотных площадок. Провозная способность может достигать 9000 пассажиров/час в одном направлении [6]

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

Согласно СНиП среднее время передвижения пассажиров для крупных городов не должно превышать 40 минут, для средних городов – 30 минут.

На Северо-Востоке Москвы в районе Медведково находится одноимённая станция метро, открытая в 1978 году. Один троллейбусный (№ 80) и один трамвайный (№ 17) маршрут. Автобусные маршруты: 31, 50, 61, 71, 93, 124, 136, 174, 181, 238, 278, 601, 605, 606, 618, 628, 649, 696, 771, 774, 838, 880. Маршрут № 823 связывает Медведково с «Северной ТЭЦ».

По информации ГУП «Мосгортранс» самым востребованным жителями маршрутом в Южном Медведково является автобус №61. Этот автобус пересекает сразу три района: Ростокино, Свиблово и Южное Медведково. Интервал движения — 5 минут в час пик.

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

17-й трамвай между Останкино и Северное Медведково — самый популярный маршрут Мосгортранса. Он перевозит 61 тысячу пассажиров в сутки.
2.3. Предложения по оптимизации перевозок пассажиров автобусным транспортом по маршрутам №№ 61, 174

Я предлагаю на уже существующих остановочных пунктах добавить новые остановки для автобуса №174 (Полярная улица; Проезд Дежнева,32; Проезд Дежнева; Спорткомплекс «Медведково»; Заповедная улица) и изменить маршрут [Приложение №2].

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

Несмотря на то, что район Бибирево соседствует с районом Южное Медведково транспортная инфраструктура между этими районами достаточно сложная. Чтобы добраться из района в район необходимо использовать, как минимум, два разных маршрута транспорта. По моим наблюдениям и, по отзывам знакомых, много людей используют трамвай №17 и от остановки «Кожгалантерейная фабрика» автобусы чтобы добраться из района в район. Это вызывает неудобство населения, связанное с двойной оплатой проезда и ожиданием транспорта. Я предлагаю продлить маршрут автобуса №61 [Приложение №1].

Транспортной подвижностью называется количество поездок в расчете на одного жителя в год.

Транспортная подвижность населения является основной исходной величиной в расчетах при проектировании работы транспорта. Зная транспортную подвижность населения и число жителей населенного пункта, можно определить плановый объем перевозок пассажиров [Приложение №3].



Согласно данным последней переписи населения всего в Москве проживал 11503501 житель, из них в Медведково - 205059 жителей 5.

По данным Мосгорстата в этом году в Москве перевезено общественным транспортом 4127 млн. человек, из них 73,6 млн. человек, проживающих в Медведково 5.

Таким образом, на одного жителя Медведково в год приходится 359 поездок (что соответствует расчетному показателю Научно - исследовательского института автомобильного транспорта) 9.

Плотность транспортной сети – это длина линий магистральных улиц, по которым может осуществляться движение маршрутного пассажирского транспорта, приходящихся на 1км2 заселенной площади населенного пункта. [Приложение №3]

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

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

Рекомендуются следующие значения плотности транспортной сети: [2]

• в центральной зоне плотность сети должна составлять 3,5…4,2 км/км2;

• в средней зоне – 2,2…3,0 км/км2;

• в периферийной зоне – 1,0…1,2 км/км2.

Плотность транспортной сети – 1,7 км/км2, что соответствует рекомендуемому значению в периферийной зоне.



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

Одним из основных показателей, характеризующих качество транспортного обслуживания, является среднее время передвижения пассажиров: [Приложение №3]

tпер = 2×tпод + Кпер×(tож +  )
Предлагаемые мной изменения маршрутов сокращает количество пересадок, таким образом, уменьшается коэффициент пересадочности и соответственно уменьшается среднее время передвижения пассажиров.
Выводы по главе 2

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

Граф, изображающий автобусный маршрут, является помеченным и взвешенным.

Графы, изображающие транспортные сети, должны быть очень чёткими и простыми, понятными для каждого пассажира.

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

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

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

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

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

Своей работой я хотел привлечь внимание жителей моего района и руководителей ГУП «Мосгортранс» к проблеме эффективности перевозок пассажиров автобусным транспортом в районе Медведково.

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

В перспективе мне было бы интересно продолжить изучение теории графов и возможности её применения в современном обществе.

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


Список литературы.
1. https://lisiynos.googlecode.com/git/s2/graphs.html

2. О.Н. Ларин “Организация пассажирских перевозок” учебное пособие Издательство ЮУрГУ 2005

3. М.Р. Якимов Транспортное планирование: создание транспортных моделей городов издательство Логос 2013

4. Сайт Мосгортранса http://www.mosgortrans.ru/

5. Сайт Мосгорстата http://moscow.gks.ru/

6. http://studopedia.ru/7_185430_tema--kratkaya-harakteristika-razlichnih-vidov-gorodskogo-transporta.html



7. Теория графов и сетей при моделировании процессов УВД: учеб. пособие / сост. В.А. Карнаухов. – Ульяновск: УВАУ ГА(И), 2009.

8. Мир математики: в 40 т. Т.11: Клауди Альсина. Карты метро и нейронные сети. Теория графов./ Пер. с исп. – М.: Де Агостини, 2014. – 144 с.

9. Сайт Научно - исследовательского института автомобильного транспорта http://www.niiat.ru/

Приложение 1.

Схема изменённого маршрута автобуса №61




Приложение 2.

Схема изменённого маршрута автобуса №174




Приложение 3.

Расчет транспортной подвижности и плотности транспортной сети.
Транспортная подвижность.


где Птр – количество передвижений на транспорте в течение года; Кж – число жителей населенного пункта; – число пассажиров, перевезенных за год.

Плотность транспортной сети.

где δ – плотность транспортной сети, км/ км2; Lc – протяженность транспортной сети, км; Foc – площадь населенного пункта, км2.


Среднее время передвижения пассажиров.

tпер = 2×tпод + Кпер×(tож + )


где tпод – среднее время подхода к остановочному пункту, ч;

Кпер – коэффициент пересадочности;

tож – среднее время ожидания транспортного средства, ч;

 – средняя дальность маршрутной поездки, км;

Vc – средняя скорость сообщения, км/ч.





Каталог: wp-content -> uploads -> 2016
2016 -> Беттің және ауыз қуысы ағзаларының туа пайда болған ауытқуларының көріністерін анықтай білу
2016 -> Анатомо-физиологические особенности кожи. Кожа это трехмерная пограничная ткань Кожа
2016 -> Аппарат для локальной криотерапии фирмы tur therapietachnik GmbH
2016 -> Анальный полип. Что такое анальный полип?
2016 -> Уметь распознавать проявления врожденной патологии лица и органов полости рта; уметь распознавать проявления врожденной патологии лица и органов полости рта
2016 -> Дентальная имплантация


Достарыңызбен бөлісу:


©stom.tilimen.org 2019
әкімшілігінің қараңыз

    Басты бет