Разработка веб-приложения моделирования потоков на транспортных сетях на базе Яндекс. Карты

Целью данной дипломной работы является создание web-приложения для определения оптимального автобусного маршрута с точки зрения его длительности. Разрабатываемое приложение будет включать в себя возможности отслеживания и вычисления времени ожидания автобуса, нахождения его в пути, реализованные посредством моделирования транспортных потоков на ТС с использованием методов теории графов. Web-приложение обеспечит работу с мобильных устройств и со стационарных ПК в онлайн режиме.
Для достижения поставленной цели были поставлены следующие задачи:
• анализ состояния проблемы в области потоков транспортных сетей;
• анализ современных методов и алгоритмов моделирования транспортных сетей;
• обзор и сравнительный анализ существующих методов теории графов для задач моделирования транспортных пото ...

ВВЕДЕНИЕ 2
1 АНАЛИЗ МЕТОДОВ И АЛГОРИТМОВ РЕШЕНИЯ ЗАДАЧ МОДЕЛИРОВАНИЯ ПОТОКОВ ТРАНСПОРТНЫХ СЕТЕЙ 5
1.1 Анализ состояния проблемы в области потоков транспортных сетей 5
1.2 Современные методы, модели и алгоритмы, используемые для задач моделирования потоков транспортных сетей 8
1.2.1 Методы моделирования потоков транспортных сетей 8
1.2.2 Существующие модели транспортных потоков 11
1.2.3 Используемые алгоритмы моделирования потоков транспортных сетей 14
1.3 Специфика алгоритмов теории графов для задач моделирования потоков транспортных сетей 17
1.4 Существующие программные решения для задач моделирования транспортных потоков 24
1.4.1 Анализ функциональных возможностей системы VisSim 24
1.4.2 Анализ функциональных возможностей системы VISUM 26
1.4.3 Анализ функциональных возможностей системыTransNet 29
1.4.4 Анализ функциональных возможностей системы «ДОРОЖНЫЙ МЕНЕДЖЕР» 32
1.5 Выводы по разделу 36
2 ТЕХНИЧЕСКИЕ СРЕДСТВ РЕАЛИЗАЦИИ ПОСТАВЛЕННЫХ ЗАДАЧ И И ИХ ФУНЦИОНАЛЬНЫЕ ВОЗМОЖНОСТИ 38
2.1 Обоснование фреймворков и выбора языков программирования 38
2.2 Обоснование выбора СУБД MySql и языка SQL 43
2.3 Обоснование использования IDE phpDesigner и API Яндекс.Карты 45
3 РАЗРАБОТКА WEB-ПРИЛОЖЕНИЯ ДЛЯ МОДЕЛИРОВАНИЯ ПОТОКОВ НА ТРАНСПОРТНЫХ СЕТЯХ С ИСПОЛЬЗОВАНИЕМ ТЕОРИИ ГРАФОВ 50
3.1 Описание алгоритма работы web-приложения 50
3.2 Описание разработанных функциональностей web-приложения 51
ВЫВОДЫ 62
ЛИТЕРАТУРА 64
ПРИЛОЖЕНИЕ 67

Современные транспортные сети (ТС) различного типа испытывают критические нагрузки, некоторые из них практически исчерпали свои технические возможности. Нагрузки на ТС имеют динамический характер, что обуславливает подверженность различным колебаниям, вызываемым сезонными и социально-политическими явлениями. Центры диспетчерского управления транспортными потоками, оснащенные компьютерной техникой и программными средствами, не всегда в состоянии эффективно противодействовать подобным явлениям.
Транспортная инфраструктура - одна из важнейших инфраструктур, обеспечивающих жизнь городов и регионов. В последние десятилетия во многих крупных городах исчерпаны или близки к исчерпанию возможности экстенсивного развития транспортных сетей. Поэтому особую важность приобретает оптимальное планировани е сетей, улучшение организации движения, оптимизация системы маршрутов общественного транспорта. Решение таких задач невозможно без математического моделирования транспортных сетей.
Развитие ТС может происходить благодаря активному использованию математически имитационных моделей теории графов для исследования специфики и оптимизации движения транспортных потоков. Для построения математических моделей необходимо формальное описание указанных факторов. В качестве такого описания может быть использован транспортный граф, узлы которого соответствуют перекресткам и станциям внеуличного транспорта, дуги — сегментам улиц и линий внеуличного транспорта. Содержание топологии ТС может быть представлено в виде матрицы межузловых загрузок (ММЗ). В совокупности значения элементов матрицы отражает общее состояние всей сети, что позволяет получить ряд очень важных для практических расчетов технико-экономических показателей (объем перевозок, их среднюю дальность, загрузку коммуникационных трактов, среднее время пребывания груза в пути и т.д.).
Анализ существующих программных продуктов моделирования потоков на транспортных сетях показал, что большая часть существующих решений нацелена на решение узко специализированных задач, что связано с предназначением их использования лишь в рамках организаций, осуществляющих перевозки. Кроме этого, часто используются устаревшие статистические данные, что снижает адекватность и точность прогнозируемые характеристики ТС. Для более адекватных решений необходимо применение динамических имитационных моделей, с возможностью «на лету» изменять модели событий, что позволяет адекватно оценивать события ТС в реальном времени.

Работа с программой не вынуждает получение глубоких профессиональных знаний в области моделирования поток транспортных сетей.
Программа имеет современный, легко осваиваемый гибкий пользовательский интерфейс
Недостатки: отсутствие гибких настроек детального моделирования отдельных потоков транспортной сети, высокая цена, повышенная требовательность к ресурсам ПК.
1.5 Выводы по разделу
Анализ существующих программных решений показал, что использование присутствующих а рынке систем в рамках дипломной работы не позволяет в полной мере выполнить все поставленные задачи. Большая часть существующих ситем моделирования транспортных потоков не могут быть интегрированы в онлайн режим, а также являются дорогостоящими и ресурсоемкими. В связи с этим, актуальность дипломного проекта заключается в разработке собственного кроссплатформенного программного решения в виде web-приложения для определения оптимального транспортного маршрута с точки зрения его длительности.
В качестве алгоритма поиса оптимального маршрута в рамках дипломной работы выбран алгоритм Беллмана-Форда в силу быстродействия и возможности применения для решения задач моделирования транспортных потоков.
Для реализации web-приложения моделирования потоков на транспортных сетях используется алгоритм Беллмана-Форда, в частности, при расчете равновесных значений потоков на дугах, являющихся траекториями маршрутов транспортных средств, соединящими остановки, которые представлены в приложении узлами графа. Для каждого номера маршрута транспортного средства производиться построение отдельного графа, на основании чего производиться поиск оптимального, с точки зрения временных затрат, маршрута.
2 ТЕХНИЧЕСКИЕ СРЕДСТВ РЕАЛИЗАЦИИ ПОСТАВЛЕННЫХ ЗАДАЧ И И ИХ ФУНЦИОНАЛЬНЫЕ ВОЗМОЖНОСТИ
Для реализации поставленных задач необходимо провести сравнительный обзор существующих технических средств и инструментов. На основании этого проводиться обоснование выбора конретных языков программирования, фреймворков, технилогий, среды разработки, используемых сторонних API. В данном разделе приведен краткий анализ и осуществлен выбор наиболее подходящих технических инструментов и средств реализации, поставленных в рамках дипломной работы, задач.
2.1 Обоснование фреймворков и выбора языков программирования
PHP (Hypertext PreProcessor, препроцессор гипертекста) – язык программирования, исполняемый на стороне веб-сервера.
Согласно литературным источникам [3, 8, 19, 25] в сравнении с другими языками программирования web-приложений данный язык является гибким, приобрёл массовую популярность и используется в проектах различного уровня и масштаба, для разработки блогов, интернет-магазинов, сайтов-визиток и т.д.
Существует удобная реализация PHP для .NET/Mono — Phalanger и для JVM — JPHP. При компиляции PHP-кода в Phalanger можно получить практически любое .NET-приложение, в то же время JPHP поддерживает расширение Swing, которое портированно из среды Java.
PHP является языком программирования с динамической типизацией, т.е. он не требует указания типа при объявлении переменных. Преобразования между скалярными типами осуществляются неявно, однако такой функционал также заложен в возможности языка.
Выявленные преимущества PHP:
развитая поддержку СУБД;
свободный язык, распространяемым под лицензией- PHP license;
низкий порог вхождения, легок в освоении;
наличие большого количества библиотек и расширений;
может быть внедрен для решения задач в изолированной среде;
содержит нативные средства организации веб-сессий и программного интерфейса расширений;
является полной заменой проприетарной среды ASP от Microsoft;
оперативно разворачивается практически на любом сервере;
крупная поддержка авторитетными сообществами разработчиков;
портирован под большое количество аппаратных платформ и операционных систем.
Выявленные недостатки PHP:
слабые средства для обработки исключений;
не применим для создания крупных и требовательныъ десктопных приложений, системных компонентов;
объекты передаются по значению, а не по ссылке, как в большинстве других современных языков;
глобальные параметры конфигурации сильно отражаются и влияют на синтаксис языка, что часто затрудняет настройку сервера и разворачивание приложений;
не высокая степень безопасности и устойчивости к веб-угрозам.
Преимущества использования php-фреймворков:
могут использоваться параллельно с сайтом, который разработанн на существующих CMS;
оперативно разрабатывается сайт любой сложности и функционала, в силу большого колличества заложенного в них потенциала;
разработка дополнительных компонентов дешевле и быстрее, по сравнению с разработкой в запутанных CMS;
высокая скорость работы в сравнении с CMS.
Недостатки:
малое колличество полностью готовых модулей и компонентов, для быстрой установки клиентов.
необходимость в дополнительных доработках функционала, которые прийдется заказывать у разработчиков;
разработка дополнительного функционала обойдется дороже и займет больше времени, чем использование некоторых CMS.
JavaScript —сценарный, ориентированный на прототипную разработку язык программирования. Представляет собой реализацию языка ECMAScript.
Согласно проведенному анализу источников [22, 28, 29], в сравнении с другими решениями, JavaScript в большей степени приспособлен для программного доступа к объектам приложений в качестве встраиваемого языка. Широкое применение язык нашел в современных браузерах для придания интерактивности веб-страницам, как язык сценариев.
Архитектурные черты: слабая типизация, прототипное программирование, динамическая типизация, автоматическое управление памятью, объекты первого класса в виде функции.
Набор основных объектов ядро JavaScript: Math, Array и другие. Основным набором элементов языка являются управляющие структуры, операции, операторы. Ядро JavaScript является расширяемым.
JavaScript похож на Си синтаксически, однако по сравнению с Си обладает коренными отличиями:
возможность интроспекции объектов;
объекты первого класса - функции;
сборка мусора в в автоматическом режиме;
анонимные функции;
приведение типов в автоматическом режиме.
К сожалению, в данном языке отсутствуют такие функциональности, как:
модульная система. Язык не предоставляет возможностей по изоляции областей видимости и управлению зависимостями;
стандартная библиотека: отсутствуют интерфейсы управления потоками ввода-вывода, программирования приложений работы с файловой системой, базовых типов бинарных данных;
отслеживающая зависимости и автоматически устанавливающая их система управления пакетами;
стандартные интерфейсы к базам данных и веб-серверам.
Выявленные недостатки.
Потенциальные хакеры и авторы вредоносного кода на JavaScript могут запускать его позволяет на любом компьютере сети, т.к. для этого достаточно открытия веб-страницы.
Выполнение JavaScript-программ происходит в песочнице, в которой они могут выполнять ограниченный круг действий, но далеко не все задачи программирования общего назначения;
Для JavaScript используется политика общего происхождения, согласно которой скрипт, который встроен в страницу, не получает доступ к ряду свойств объектов другой страницы, при отличии этих страниц в номере порта, протоколе, хосте.
Главная проблема, касающаяся JavaScript это нарушение политики общего происхождения, т.е. межсайтовый скриптинг. Уязвимости XSS имеют место в ситуациях, когда злоумышленник имеет размещает JavaScript на страницу, которая демонстрируется пользователю. Тогда скрипт с правами этого пользователя получает доступ к сайту, что открывает возможность осуществления нежелательных транзакций, отсылки конфиденциальной информации и др.
Подделка межсайтовых запросов или CSRF является другим типом межсайтовой уязвимости. Она заключается в том, что злоумышленник заставляет браузер пользователя осуществлять нежелательные действия на выбранном сайте, при переводе безналичных денег, например. Это может произойти, если целевой сайт полагается на запросы авторизации или HTTP cookie. В таком случае инициализированные кодом сайта запросы злоумышленника выполняются аналогично запросам пользователя, когда он авторизован на целевом сайте.
При всем этом, JavaScript предоставляет интерфейс к широкому спектру возможностей браузера, часть которых может содержать ошибки. Это приводит к тому, что злоумышленики пишут скрипты,которые исполняют произвольный кода на системе пользователя.
JQuery представляет собой библиотеку JavaScript, которая фокусируется на взаимодействии HTML и JavaScript.
При манипулировании необходимыми элементами страницы в Javascript предусмотрено несколько способов их поиска на странице среди существующего множества объектов. Данные способы требуют использования большого количества информации, а при поиске элемента с помощью jQuery необходимо знать только ID элемента, с которым производяться операции. В общем случае, код обращения будет выглядеть так: $('путь к элементу(элементам)'). Важной функцией jQuery является функция $()– она вызывается всеми методами jQuery.
Выявленные преимущества использования JQuery.
Объем кода очень не высок. Посредством того, что объем программного кода jQuery меньше, чем объем обычного Javascript кода, происходит сокращение временных затраты, направленных на разработку различных элементов веб-страницы. Сам программный код гораздо более понятен, в отличии от JavaScript конструкций.
Простота и наглядность.  Функции и код JQuery гораздо более удобны для понимания и чтения. При создании простого Ajax-запроса требуется всего около трех-пяти строк кода, что существенно упрощает использование данной технологии.
Кроссплатформенность. Написанное с помощью использования JQuery с высокой вероятностью будет работать во всех существующих браузерах.
Легкость тестирования и отладки. Наличие большого количества плагинов позволяет реализовать практически любое действие или эффект. Использование JQuery позволяет подключать большое колличество стандартных компонентов (плагинов). Данные плагины можно оформлять и конфигурировать согласно требованиям, они будут работать во поддерживаемых JavaScript браузерах.
Широкая поддержка на форумах и образовательных ресурсах. Над JQuery трудятся тысячи программистов, для того, чтобы разные версии были совместимы друг с другом.
Конкурентоспособность. Высокая оценка специалистов по работе с JQuery на рынке труда.
2.2 Обоснование выбора СУБД MySql и языка SQL
MySQL представляет собой широко используемую в Интернет систему управления базами данных (СУБД), как правило применяемую в связке с PHP [1, 13, 16, 23].
MySQL, в стравнении с существующими аналогами, ориентирована на управление реляционными БД. В реляционной БД данные хранятся в отдельных таблицах, благодаря чему обеспечивается выигрыш в гибкости и скорости. С помощью отношений таблицы связываются между собой, что обеспечивает возможность сочетания данных из нескольких таблиц, при выполнении запросов. SQL, как часть системы MySQL, может быть охарактеризована в качестве языка структурированных запросов, и наиболее распространенный стандартный язык, который используется для доступа к БД.
СУБД MySQL состоит из двух частей: серверной и клиентской. Сервер MySQL работает на компьютере постоянно. Клиентские программы посылают sql-запросы серверу MySQL через механизмы сокетов, сервер их обрабатывает и фиксирует результаты.
Структура СУБД MySQL имеет трехуровневый вид: базы данных - таблицы - записи. Базы данных и таблицы MYSQL физически представляются в виде файлов с расширениями MYD, MYI, frm. Записи - это совокупность разного типа полей. Имя БД MySQL в рамках системы уникально, а таблицы уникальны в пределах базы данных, поля в пределах таблицы также уникальны.
SQL является информационно-логическим языком, предназначенным для задач описания, удаления и изменения данных, которые хранятся в реляционных БД. SQL может быть назван языком программирования, ноэтом он не является Тьюринг-полным, вместе с тем стандарт языка спецификаций SQL / PSM предусматривает его расширение процедурных возможностей.
SQL является основным способом работы пользователя с БД и позволяет выполнять такие операции:
добавление новых записей в таблицу;
создание новой таблицы в базе данных;
выборка записей из нескольких таблиц или из одной (согласно условию);
удаление записей;
изменение структур таблиц;
изменение записей.
Преимущества SQL.
1. Независимость от конкретной СУБД
Несмотря на наличие диалектов тексты SQL-запросов, содержащих DML и DDL, могут быть легко перенесены из одной СУБД в другую. Существуют системы, разработчики которых ориентировались на применение нескольких СУБД . При применении некоторых специфичных для реализации возможностей такой переносимости добиться очень трудно.
2. Наличие проверенных временем стандартов
Способствует «стабилизации» языка и наличие стандартов, набора тестов для выявления совместимости и соответствия конкретной реализации SQL общепринятому стандарту. Однако, сам по себе стандарт слишком формализован и очень емок в размерах (базовая часть стандарта включает более 1300 страниц текста).
3. Декларативность
С помощью SQL программист описывает методику извлечения конкретных данных или их модифиции. Специфика реализации выбирается непосредственно СУБД при обработке SQL-запроса. При этом, это не является полностью универсальным принципом - программист описывает набор данных для модификации или выборки, однако ему необходимо знать как СУБД будет разбирать текст его запроса. Чем сложнее структура запроса, тем больше он допускает вариантов написания, которые могут отличаться по скорости выполнения, но одинаковых по результирующему набору.
Недостатки SQL.
1. Несоответствие реляционной модели данных
2. Дефекты SQL с точки зрения реляционной теории:
колонки без имени и дублируются имена колонок;
строки-дубликаты;
использование порядке колонок;
неопределенные значения (nulls);
использование указателей;
неспособность правильно поддерживать операцию «=»;
высокая избыточность.
2.3 Обоснование использования IDE phpDesigner и API Яндекс.Карты
phpDesigner – интегрированная среда разработки(IDE), в сравнении с существующими аналогами, такими как NetBeans, Eclipse, Subline, обладает более полным и удобных функционалом для реализации web-приложений. С использованием данного редактора можно создавать веб-проекты на CSS, HTML, PHP, JS. Реализована поддержка всех актуальных на сегодняшний день PHP Фреймворков (CodeIgniter, Zend, Yii, Prado, Symfony), а также Фреймворков JavaScript (Ext JS, MooTools, jQuery, Prototype, Dojo и других).
Выявленные преимущества
Присутствуют пакеты локализации для украинского и русского языков.
Поддержка работы с файлами по FTP напрямую. 
Наличие встроенной библиотеки phpDesigner, которая имеет более 3000 функций, посредством чего процесс разработки сопровождается подсказками по работе с функциями
Для роботы с БД предусмотрен специальный вьювер, использующий PHPMyAdmin.
Программа phpDesigner позволяет создавать и использовать сниппеты. Для большего удобства, предусмотрена возможность их сортировки по заданным директориям. Для поддерживаемых языков присутствует готовый набор сниппетов для оперативного использования.
Встроенный мануал по CSS, Perl, PHP, SQL, HTML, JavaScript.
Очень удобное комментирование кода. Достаточно выделить нужный фрагмент кода и нажать одну кнопку. Нет необходимости в комментировании каждую отдельной строки. Предусмотрена возможность быстрого удаления комментария.
Недостатки phpDesigner.
Отсутствие выделения кода в вертикальном режиме, в отличие существующих аналогов, например Sublime Text 2.
Отсутствие кроссплатформенности. Данная IDE может быть установлена только на операционные системы Windows.
Нет возможности изменения размера шрифта масштабированием
Высокая цена.
Яндекс.Карты – это поисково-информационный сервис, который дает возможность пользователям получать информацию о картах городов, схемы метро, данные о пробках, и другую гео-информацию
Карты, кроме справочной информации, открывают обширные функциональные и рекламные возможности. С их помощью легко размещать и просматривать данные о местных компаниях, в том числе контактную информацию, адрес, маршруты проезда. Благодаря использованию открытого API, инструмента, который позволяет разработчикам получать доступ к частям сервиса карт, появляется возможность интеграции такого функционала на целевые сайты.
Весомым аргументом в сторону выбора карт Яндекса – их ориентация на Россию и Украину. Поддерживается функция геортаргетинга, т.е. определения местонахождения пользователя по ip-адресу, причем с оптимизацией под русскоязычный Интернет. Некоторые российские мобильные операторы предоставляют пользователям бесплатный трафик своим на мобильную версию Яндекс.карт. Яндекс позволяет пользователям создавать собственные электронные интерактивные карты используя свою платформу в качестве базы.
Основными модулями API Яндекс.Карт являются:
1. ObjectManager
Преимущества.
Производится отрисовка только тех объектов, которые попадают в область видимости карты.
Кластеризация объектов на клиенте.
Отсутствие необходимости реализации серверной части, т.к. вся обработка данных производится на клиентской стороне.
Фильтрация объектов при их отображении.
Недостатки.
Загрузка данных для всех объектов одновременно, без оптимизации;
Поддержка работы с метками.
Проведение кластеризации объектов на стороне клиента.
2. LoadingObjectManager
Преимущества.
Фильтрация объектов при их отображении.
Кластеризация объектов на клиенте.
Сохранение загруженных данных. Данные загружаются только один раз для каждого объекта.
Загрузка данных только для видимой области карты.
Недостатки.
Поддержка работы только с метками.
Кластеризация объектов производится на стороне клиента.
Необходимость реализации серверной части.
3. RemoteObjectManager
Преимущества.
Использование серверной кластеризации данных.
Хранение на сервере данных по объектам. Подгрузка данные только для объектов, которые попадают в видимую область карты.
Недостатки.
Необходимость реализации серверной части.
Изменение коэффициента масштабирования влечет загрузку данных заново.
Поддерживает работу только с метками.
Необходимость реализации собственной кластеризациюи.
Выявленные достоинства API Яндекс.Карт:
1. С большим количеством объектов карты удобно использовать ObjectManager, т.к. он позволяет оптимально кластеризовать, отображать и управлять видимостью объектов.
2. Поддержка мультимаршрутностей. В случае, когда есть возможность построения более одного маршрута с похожими характеристикам они могут быть построены, а пользователь может выбрать сам наиболее подходящий.
3. Маршруты могут строиться без учёта пробок и с учетом. Для каждого маршрута доступен маршрутный лист и рассчитывается время в пути.
4. Возможнсть вывода данных из файла на карту с помощью функции JQuery.getJSON(). Формат загруженных данных - GeoJSON.
5. Поддержка геокодирования. Геокодирование данных организовано на стороне сервера. На серверной стороне разработан Node.js-модуль который использует HTTP-сервис геокодирования. Данный модуль позволяет осуществляет по географическим названиям поиск множества объектов. С помощью встроенных функций API полученный результат может быть добавлен на карту. Недостатки:
1. Сложность серверной части. 
2. Отсутствие динамической гибкости в управлении. 
3. Невозможность перемещения метки при наведении на нее курсора.
4. Невозможность оперативного изменения на клиенте внешнего вида меток.
3 РАЗРАБОТКА WEB-ПРИЛОЖЕНИЯ ДЛЯ МОДЕЛИРОВАНИЯ ПОТОКОВ НА ТРАНСПОРТНЫХ СЕТЯХ С ИСПОЛЬЗОВАНИЕМ ТЕОРИИ ГРАФОВ
3.1 Описание алгоритма работы web-приложения
Для реализации web-приложения моделирования потоков на транспортных сетях используется алгоритм Беллмана-Форда, в частности, при расчете равновесных значений потоков на дугах, являющихся траекториями маршрутов транспортных средств, соединящими остановки, которые представлены в приложении узлами графа. Поиск оптимального маршрута реализуется на основании использования критериев оптимальности затрат времени и длины маршрута. Для этого, в программном коде, реализован метод построения матрицы транпортных потоков. На базе использования данного метода для каждого номера маршрута транспортного средства производиться построение отдельного графа, на основании чего производиться поиск оптимального, с точки зрения временных затрат, маршрута.