Содержание к диссертации
Введение
ГЛАВА 1. Анализ проблем построения распределенных информационых систем для решения задач на транспорте .
1.1. Анализ проблем проектирования баз данных для решения задач на транспорте . 17
1.2. Анализ построения распределенных информационных систем. 24
1.3. Обзор средств разметки документов. 32
1.4. Анализ принципов функционирования и применения ГИС. 44
1.5. Анализ современных информационных систем для решения задач на транспорте, представленных на рынке. 52
Выводы по главе 1. 56
ГЛАВА 2. Структура данных информационной системы "транспортная сеть города"
2.1. Описание предметной области информационной системы . 57
2.2. Разработка концептуальной и реляционной схемы предметной области. 63
2.3. Создание графа транспортной сети. 73
2.4. Разработка системы параметризации объектов на транспортной сети. 77
Выводы по главе 2. 81
ГЛАВА 3. Поиск кратчайших маршрутов транспортных сетях .
3.1. Разработка алгоритмов нахождения кратчайших путей из одной вершины к другой вершине графа. 82
3.2. Разработка алгоритмов нахождения кратчайших путей из одной вершины ко всем другим вершинам графа . 83
3.3. Разработка алгоритмов поиска кратчайших путей по всем точкам графа. 88
3.4. Разработка алгоритмов нахождения нескольких кратчайших путей между двумя точками. 91
3.5. Разработка методов построения маршрутных планов. 92
3.6. Анализ зависимости времени выполнения алгоритмов от объемов и степени параметризации транспортной сети. 94
Выводы по главе 3. 99
ГЛАВА 4. Разработка реализации информационной системы .
4.1. Схема реализации работы информационной системы . 100
4.2. Разработка методов представления информации для пользователя. 107
4.3. Схема взаимодействия компонентов информационной системы. 110
4.4. Методы сбора, распределения и обновления информации. 114
Выводы по главе 4. 117
Заключение. 118
Литература. 120
Приложение. 134
- Анализ проблем проектирования баз данных для решения задач на транспорте
- Описание предметной области информационной системы
- Разработка алгоритмов нахождения кратчайших путей из одной вершины ко всем другим вершинам графа
- Схема реализации работы информационной системы
Введение к работе
Актуальноть темы. С проблемами экспедирования и транспортировки грузов сталкиваются не только специалисты, основным направлением деятельности которых является транспортная логистика, но и огромная масса людей, чей интерес к задачам перевозок может быть как разовым, так и практически постоянным. Например, одним из обязательных условий проведения любой торговой операции является регулярное и своевременное перемещение товара. Любая организация, действующая в сфере производства, не может обойтись без обращения к услугам перевозчика или экспедитора. [15]
Сложность автоматизации деятельности транспортной организации с учетом распределенной структуры и географической удаленности отдельных ее компонентов делает актуальной задачу разработки программного обеспечения с ориентацией на сетевую обработку информации. Необходимо обеспечить информационное обслуживание массовых и разнообразных запросов со стороны предприятий-перевозчиков, экспедиторов и частных лиц, заинтересованных в получении оперативной транспортной информации. [25]
Указанные обстоятельства предопределяют актуальность темы настоящей диссертационной работы, ориентированной на комплексное решение проблемы построения распределенной информационной системы, необходимой для обработки сложно структурированной информации о транспортной сети города.
Целью диссертационной работы является разработка моделей, алгоритмов и средств создания распределенной информационной системы, позволяющей автоматизировать работу по созданию и поддержанию оперативно обновляемой информационной модели транспортной сети города, решению задач по поиску кратчайших и оптимальных путей на транспортной сети.
Объектом исследования является деятельность транспортного предприятия, связанная с обработкой информации о транспортной сети города.
Основным научным результатом является разработка распределенной информационной системы, решающей задачи поиска кратчайших и оптимальных путей на оперативно обновляемой параметрической модели транспортной сети города.
Для достижения поставленной цели в работе решены следующие основные задачи:
• проведен анализ информационных требований пользователей по предметной области "Транспортная сеть города";
• разработаны концептуальная и реляционная схемы предметной области [6];
• формализовано представление данных о транспортной сети в виде параметрических направленных сетевых графов [11];
• на основании существующих алгоритмов нахождения кратчайших путей в графах разработаны алгоритмы поиска кратчайших и оптимальных путей на транспортной сети, учитывающие особенности распределенной информационной системы, а также разработаны принципы построения отчетов в виде транспортных планов и путевых маршрутов;
• разработана архитектура построения распределенной информационной системы для решения задач на транспорте [5,7];
• разработана реализация информационной системы "Транспортная сеть города" в виде интернет-проекта [4].
Методы исследования. Результаты диссертационной работы получены на основе комплексного использования методов теории графов, теории множеств, теории баз данных, методов исследования операций и теории вычислительных сетей.
Научная новизна диссертации состоит в разработке принципов, моделей, алгоритмов и средств построения распределенной информационной системы, ориентированной на решение пользовательских задач по нахождению кратчайших и оптимальных путей на транспортной сети города. Разработанные научные принципы, методы и средства позволяют автоматизировать работу по созданию и поддержанию информационной модели транспортной сети города, поиску кратчайших и оптимальных путей на ней, дают возможность информационной системе работать в условиях распределения рабочей нагрузки и одновременного доступа множества удаленных пользователей. Положения, выносимые на защиту:
• результаты анализа предметной области "Транспортная сеть города";
• разработанная семантическая модель и реляционная схема базы данных предметной области;
• методы представления базы данных информационной системы в виде параметризированных однородных сетевых графов;
• алгоритмы поиска кратчайших и оптимальных путей на транспортной сети, учитывающие особенности распределенной информационной системы, разработанные на основе существующих алгоритмов нахождения кратчайших путей в графах, а также принципы построения отчетов в виде транспортных планов и путевых маршрутов;
• архитектура построения распределенной информационной системы для решения задач на транспорте;
• реализация информационной системы в виде интернет-проекта, использующего методы и алгоритмы решения задач на транспортной сети.
Достоверность научных положений, рекомендаций и выводов. Обоснованность научных положений, рекомендаций и выводов, изложенных в работе, обеспечивается корректным использованием в работе современных математических методов при анализе и оптимизации разрабатываемых алгоритмов. Достоверность положений и выводов диссертации подтверждена результатами экспериментальных исследований и положительными результатами внедрения разработок в ряде промышленных организаций.
Практическая ценность и реализация результатов работы. Результаты работы имеют реальный практический выход в виде разработанного и отлаженного программного обеспечения с методикой его использования в организациях и на предприятиях. Разработанные методы и алгоритмы прошли апробацию и внедрены для практического применения в ООО "Яндекс", ТК "Стройтехника ТМ". Значимость выполненных исследований подтверждается их использованием на этих предприятиях. Практическое использование результатов подтверждено соответствующими актами о внедрении, приводимыми в приложении к диссертации.
Реализация информационной системы была внедрена в ООО "Яндекс", где предложенные методы и решения реализованы в виде распределенной информационной системы, способной автоматизировать разработку сетевых решений и обрабатывать запросы пользователей. Информационная система была использована для разработки
геоинформационных проектов "Яндекс.Атлас" и "Яндекс.WAP".
Также реализация информационной системы была внедрена в ТК "Стройтехника ТМ", что позволило компании сократить транспортные расходы и улучшить обслуживание клиентов за счет увеличения оперативности и повышения качества доставки.
Результаты диссертационной работы использованы в учебном процессе кафедры "Автоматизированные системы управления" МАДИ (ГТУ) по дисциплинам "Базы данных" и "Проектирование ИС".
Апробация результатов. Основные положения и результаты диссертации докладывались и обсуждались на заседаниях кафедры "Автоматизированные системы управления" МАДИ (ГТУ) в 2000-2003 годах, на научно-методических конференциях МАДИ (ТУ) (Москва 1999 2003 гг.), на республиканских межрегиональных и международных научно-технических конференциях, симпозиумах и семинарах (1998-2003 гг.).
Публикации. Отдельные положения диссертации отражены в 11 печатных работах.
Объем работы и структура диссертации. Диссертационная работа состоит из введения, 4 глав основного текста, заключения, списка использованной литературы и приложения.
Во введении приводится краткая характеристика диссертационной работы. Обоснована актуальность выбранной темы, сформулированы цель и основные задачи исследования, научная новизна, практическая ценность и положения, выносимые на защиту. Излагается краткое содержание глав диссертации.
В первой главе приведен подробный анализ проблем проектирования распределенных информационных систем для решения задач на транспорте.
В рамках анализа существующих СУБД были рассмотрены современные концепции хранения и анализа данных, основные аспекты и особенности сопровождения реляционных баз данных, необходимость и перспективы повышения автоматизации обработки данных при выполнении ряда задач [21]. Анализ современных технологий хранения и доступа к информации показал необходимость использования таких средств управления реляционными базами данных, как Oracle, Microsoft SQL Server, MySQL. [38, 39]
Также проведен анализ существующих технологий распределенной работы информационной системы. Была показана необходимость применения компонентной структуры информационной системы на основе архитектуры распределенного взаимодействия элементов (технология CORBA). [93]
Проведен анализ принципов обмена информацией, как между компонентами системы, так и для ввода и вывода данных, также выполнен анализ средств преобразования информации и форматов ее разметки для обеспечения основных видов запросов пользователей информационной системы. Анализ современных технологий представления данных показал, что в качестве формата передаваемых данных для вышеуказанных целей наилучшим является использование языка разметки XML, а для представления результатов работы в виде различных отчетов следует использовать язык преобразований XSLT. [45, 91, 115, 123]
Проведенный анализ основных принципов функционирования ГИС и вопросов их применения позволил сделать выводы о необходимости построения собственной информационной системы для наиболее адекватного решения поставленных задач. Анализ существующих пакетов ГИС привел к выводу о невозможности использования их в полном объеме при построении основы для данной информационной системы, однако было определено, что механизм сбора информации может быть осуществлен при помощи ГИС, а информационная система может экспортировать свои данные для использования в ГИС. [110]
Были рассмотрены существующие аналогичные интернет-проекты, и информационные системы. После анализа их возможностей и недостатков был сделан вывод, что для достижения поставленной задачи построения распределенной информационной системы "Транспортная сеть города" необходимо, ориентируясь на анализ существующих технологий, разработать оригинальную архитектуру, методы и механизмы реализации параметрической модели транспортной сети.
Во второй главе подробно описывается предметная область информационной системы, рассматриваются ее основные объекты и их характеристики, а также производится анализ методов построения однородного направленного графа сети на основе реляционной схемы информационной системы. Кроме того, рассматриваются разработанные методы параметризации объектов на транспортной сети с любой необходимой пользователю точностью детализации.
Для этого параметры узлов транспортной сети представлены в виде иерархии параметров, заполненной уточняющими значениями.
В процессе проектирования информационной системы была разработана концептуальная схема предметной области, созданы локальные представления объектов и глобальное представление предметной области в виде диаграммы объект-связь.
Показана реляционная схема информационной системы, описываются ее объекты и их атрибуты. [6]
Так как структура данных модели транспортной сети города напрямую не предусматривает каких-либо связей между узлами, за исключением связи от узла к ближайшему узлу, необходимо было разработать основные принципы преобразования подобной неоднородной системы к сетевому графу, а также методы хранения этой информации в
базе данных информационной системы.
В третьей главе описываются основные алгоритмы нахождения кратчайших и оптимальных путей на транспортной сети, такие как:
• алгоритмы нахождения кратчайших путей из одной вершины к другой вершине,
• алгоритмы нахождения кратчайших путей из одной вершины ко всем другим вершинам графа,
• алгоритмы нахождения кратчайших путей между всеми точками транспортной сети.
Также в диссертации приводятся разработанные способы применения вышеуказанных алгоритмов для построений транспортных схем и маршрутов. [7]
Для решения задачи поиска кратчайших и оптимальных путей были выделены следующие методы:
1. Метод нахождения кратчайших путей из начальной точки S к конечной точке F графа, который позволяет находить кратчайший путь между двумя любыми узлами транспортной сети по текущим данным. Для решения этой задачи реализован алгоритм Ли, известный как волновой алгоритм. [30]
2. Метод нахождения кратчайших путей из данной точки S ко всем другим вершинам графа, позволяющий создавать маршруты между точками и реализованный алгоритмами Дейкстры и Форда-Беллмана. [58, 80]
Метод нахождения кратчайших путей между всеми точками транспортной сети, позволяющий построить план проезда по сети, который не зависит от данных информационной системы и показывает состояние сети в момент создания плана. Для решения этой задачи существует алгоритм Флойда [63].
3. Метод нахождения нескольких кратчайших путей между двумя точками для выбора оптимальных путей, для чего применим алгоритм Йена [88].
4. Метод построения маршрутных планов путем приведения списка точек посещения в граф и решения на нем задачи коммивояжера. Данная задача решена N-разовым применением алгоритма Дейкстры. [71]
Проведенные исследования эффективности работы алгоритмов показали их характерные особенности, такие как зависимость времени выполнения алгоритмов от размеров транспортной сети или зависимость времени выполнения алгоритмов от степени параметризации транспортной сети и других ограничений.
На основании существующих алгоритмов нахождения кратчайших путей в графах и оценках их быстродействия были разработаны алгоритмы поиска кратчайших и оптимальных путей на транспортной сети, учитывающие особенности распределенной информационной системы.
Также в диссертации описаны методы построения временных срезов и планов сети, сохранения их во вспомогательной базе данных и подстановки сохраненных данных при повторяемости запросов пользователей.
В четвертой главе описываются основные особенности реализации распределенной информационной системы, приведены разработанные методы представления информации для пользователя, схема построения маршрутов в текстовом и графическом вариантах, а также показан механизм обмена данных между компонентами информационной системы. [4, 52]
Особое внимание уделяется описанию информационной системы, как связной многокомпонентной структуры. Для обеспечения устойчивой и непрерывной работы информационной системы была разработана методика обеспечения распределенности его на отдельные и независимые группы компонентов.
Такими группами в данной реализации являются:
• сервера системы управления основной базой данных,
• сервера системы управления дополнительными базами данных,
• сервера обработки и преобразования информации,
• веб-сервера.
В диссертации показаны механизмы и принципы взаимодействия распределенных компонентов информационной системы, описана экспериментальная транспортная сеть, которая легла в основу реализации информационной системы.
Анализ проблем проектирования баз данных для решения задач на транспорте
С развитием информационных технологий человечеству приходится иметь дело с постоянно возрастающими объемами информации. Огромные объемы информации порождают две проблемы: как ее хранить и как обрабатывать. Не исключение и такая область человеческой деятельности как транспорт и логистика. Все возрастающие объемы перевозок требуют анализа и обработки все больших объемов информации.
На данный момент оптимальным средством работы с массивами данных являются СУБД (Системы Управления Базами Данных). [16, 21, 39]
В ходе проектирования и разработки ИС необходимо создать БД, которая будет обеспечивать хранение данных, доступ к ним, наполнение данными, и выполнение некоторых сервисных операций. [57]
К ИС может предъявляться требование непрерывного функционирования в течение длительного времени. В этом случае БД должна характеризоваться высокой отказоустойчивостью. В ИС может одновременно выполняться множество процессов (задач), осуществляющих обращение к БД, при этом одновременные запросы по возможности должны обрабатываться параллельно. ИС может быть распределенной, то есть ее различные составляющие задачи, БД могут быть размещены на различных компьютерах, связанных в сеть, в подобной системе БД должна поддерживать возможность приема удаленных запросов (по сети). [2]
Возможна реализация СУБД, которая принимает и обрабатывает как запросы в масштабах локальной сети, так и в масштабах Internet. Это зависит от возможностей операционной системы и от того, какие стандартные интерфейсы приема запросов СУБД поддерживает. Например, возможна реализация СУБД в виде SQL-сервера, FTP-сервера, Web-сервера, WAP-сервера. [28]
Перечисленные в постановке задачи требования к БД должны и могут выполняться одновременно. В зависимости от объемов информации и требований к ее обработке и представлению используются различные СУБД. С целью оптимального использования ресурсов и повышения рабочих характеристик разработчикам самих баз данных (БД) и приложений к ним необходимо в первую очередь определиться с архитектурой СУБД..[41, 73]
Когда необходимо хранить очень большие объемы данных (от нескольких сотен Мб до нескольких Тб) и обеспечивать доступ к ним сотен клиентов, применяются большие корпоративные базы данных. В основе реализации таких СУБД лежит архитектура «клиент-сервер». Обычно для реализации такой архитектуры применяется две СУБД: клиентская и серверная. Сервер БД реализует все основные функции по обработке, хранению и оптимизации данных, разграничению доступа к серверным функциям и данным, получению и реализации запросов клиента, выдаче клиенту результатов запросов и другие масштабные и административные функции. [42] Клиент БД выполняет функции по отображению полученных с сервера данных пользователю, организации взаимодействия с пользователем, отправке на сервер запросов на получение или модификацию данных, обработке сообщений полученных с сервера. [18, 49]
Таким образом, на клиентской машине располагается небольшая программа, выполняющая простые операции и не слишком требовательная к ресурсам, а все основные операции выполняются мощным сервером. К тому же различные программные комплексы, расположенные на ЭВМ клиентов могут выполнять различные функции, используя общие данные. При данной технологии критичными для быстродействия являются операции чтения диска сервером и пропускная способность сети. Операции чтения диска минимизируются с помощью оптимального использования оперативной памяти и организации временных областей быстрого доступа с оперативными, часто используемыми данными. [61]
Основная нагрузка на сеть происходит во время передачи запросов от клиента и результатов с сервера. Снизить нагрузку на сеть можно, оптимизируя работу программы по количеству отправляемых серверу запросов, а, также размещая большие, часто используемые несколькими клиентами, функции на сервере (так называемые хранимые процедуры). [60] Это позволяет, не передавая процедуру по сети, выполнить часть обработки данных непосредственно на сервере, используя оптимизацию процедуры сервером, а клиенту послать только короткий результат этих операция. При архитектуре «клиент-сервер» реализуется максимальная безопасность и надежность хранения данных, а также достигается максимальная скорость обработки больших объемов данных. [54]
При построении таких систем перед разработчиками всегда стоит задача оптимального выбора и правильной оценки, как аппаратных, так и программных средств, которые могли бы в полном объеме удовлетворить специфические потребности заказчика (конечного пользователя). [32]
На российском рынке, который зарубежные компьютерные фирмы считают неплохим полигоном для предлагаемых ими новых технологий, сегодня представлены разнообразные СУБД ведущих компаний -разработчиков программных средств, таких как IBM, Informix, Microsoft, Oracle, Progress, Sybase и др., в продукции которых в ответ на текущие и перспективные потребности реальных и потенциальных пользователей воплощены самые современные решения. Развитие СУБД на современном этапе - процесс динамичный и характеризующийся наличием различных идей и концепций, порой весьма спорных и неоднозначных. Наиболее интересны вопросы, с которыми в своей повседневной жизни сталкиваются разработчики и пользователи БД. [23]
Описание предметной области информационной системы
Построение прикладной информационной системы (ИС), позволяющей решать нетривиальные запросы и задачи по перевозке грузов, предполагает, наряду с разработкой метода представления собственно графа транспортной сети города, также разработку и привязку некоторого множества фактографических ограничений и параметров, представляющих дополнительную информацию о дорожной обстановке в определенных точках и на ребрах графа.
Именно вопросам разработки комплексной структуры данных и посвящена данная глава. В соответствии с общепринятым подходом особое внимание уделяется вопросам концептуального логического проектирования информационных систем, базирующихся на концепции систем баз данных.
В виду того, что семантика представления данных зависит от процессов, имеющих место в предметной области (ПО) системы, то, прежде всего, целесообразно описать саму ПО ИС "Транспортная сеть города". Транспортная сеть города, т.е. дороги и проезды, бульвары и проспекты, шоссе и переулки, улицы и тупики, перекрестки и развороты, площади и набережные, представляет собой единый ориентированный граф. Дугами этого графа являются участки дороги (элементы пути, для которых все характеристики движения в начале участка равны характеристикам конца участка). Вершинами графа являются узлы, т.е. объекты, являющиеся абстрактными точками на проезжей части и изменяющие характеристики движения. Такими объектами являются дорожные знаки, линии разметки, пешеходные переходы в одном уровне, светофоры, искусственные сооружения, ограничивающие проезд по весу, высоте, длине, ширине транспортных средств, а также в зависимости от временных ограничений и других характеристик. При необходимости существования в одной городской системе нескольких транспортных сетей одновременно следует саму сеть определить как объект для внесения в систему. Подобный случай может возникнуть при существовании нескольких слабосвязанных транспортных сетей (Москва и города-спутники, такие, как Химки, Мытищи, Зеленоград и другие) или при необходимости объединения транспортных систем нескольких городов. Сама по себе транспортная сеть города может иметь следующие характеристики: идентификационный номер транспортной сети, название транспортной сети, ее описание, список улиц и перекрестков, входящих в транспортную сеть, номер начального перекрестка (перекрестка, с которого началось построение транспортной сети). [6] Каждая улица, состоит из нескольких узлов, связанных между собой участками дороги. Улицы, как правило, имеют следующие характеристики: идентификационный номер улицы, название улицы, старые названия улицы (в Москве, например, 30% улиц когда-нибудь переименовывались), тип улицы, номер транспортной сети, которой принадлежит улица, список узлов, входящих в состав улицы, список домов, расположенных на улице, номера перекрестков, пересекающих улицу. Основные типы улиц это: автомагистрали и бульвары, дороги и набережные, переулки и площади, проезды и проспекты, тупики и улицы, шоссе и т.д. Перекресток состоит из нескольких входящих и нескольких исходящих узлов, связанных друг с другом определенной схемой проезда по перекрестку. Перекрестки могут иметь следующие характеристики: идентификационный номер перекрестка, номер транспортной сети, которой принадлежит перекресток, номера улиц, пересекающихся на перекрестке, список входящих и исходящих узлов, схема возможных путей проезда по перекрестку (схема представляет собой список возможных проездов от каждого входящего узла к исходящим). Участок дороги это направленный элемент транспортной сети, на котором характеристики в начале движения равны характеристикам конца движения при сохранении заданного направления. Каждый участок дороги связан с двумя узлами (в начале и в конце). Параметры узла, в котором начинается участок дороги, характеризуют весь участок. Узлы это объекты, в которых соединяются два участка дороги, либо участок дороги и перекресток. В любом случае узел описывает изменение характеристик движения. В узел входят описывающие его параметры. В информационное описание узла включается: идентификационный номер узла, связь со следующим узлом с помощью участка дороги или перекрестка, наличие параметров, координаты узла, номер улицы, которой принадлежит узел. Параметр имеет: идентификационный номер параметра, тип параметра, номер типа параметра. Основные типы параметров это: элементы дороги, характеристики дороги, ограничения. Основными элементами дороги являются: предупреждающие дорожные знаки, информационно-указательные дорожные знаки, запрещающие дорожные знаки, налагающие ограничения на транспортные средства, направление и скорость движения, предписывающие знаки, знаки приоритета, линии дорожной разметки, изменяющие характеристики участка дороги, искусственные инженерные сооружения, контактная трамвайно-троллейбусная или железнодорожная сеть и другие ограничители проезда на участке дороги, пешеходные переходы, светофоры и т.д.
Разработка алгоритмов нахождения кратчайших путей из одной вершины ко всем другим вершинам графа
Эффективность волнового алгоритма оказалась зависима от расстояния между начальной и конечной точками. На транспортной сети из 168 точек скорость поиска составляла при расстоянии между точками в 1 -0.1 сек, 5 - 0.3 сек, 10-0.7 сек, 15-1.3 сек, 20-3.0 сек, 25-5.6 сек, 30 -10,3 сек, 35 - 17,8 сек.
Алгоритм Дейкстры был реализован для информационной системы «Транспортная сеть города» и показал следующее быстродействие: для транспортной сети из 464 узлов скорость поиска кратчайшего маршрута между двумя точками составила 6.5 секунды, для транспортной сети из 168 узлов - 1.5 секунды, для транспортной сети из 112 узлов - 1.0 секунды, для транспортной сети из 52 узлов - 0.6 секунды, для транспортной сети из 10 узлов - 0.2 секунды.
Алгоритм Флойда был также реализован для информационной системы «Транспортная сеть города» и показал следующее быстродействие: для транспортной сети из 464 узлов скорость поиска кратчайшего маршрута между двумя точками составила 0.8 секунды, построение плана 1324 секунды, для транспортной сети из 168 узлов - 0.3 секунды, построение плана 360 секунд, для транспортной сети из 112 узлов - 0.2 секунды, построение плана 245 секунд, для транспортной сети из 52 узлов - 0.15 секунды, построение плана 150 секунд, для транспортной сети из 10 узлов -0.1 секунды, построение плана 45 секунд.
Таким образом, мы видим, что волновой алгоритм может быть применим при расчетах кратчайших путей, при условии, что расстояние между начальной и конечной точками невелико. А также, что для выполнения расчетов на постоянно изменяющейся транспортной сети, то есть в случаях, когда есть необходимость пересчитывать всю сеть, наиболее выгоден алгоритм Дейкстры, а в случаях, когда транспортная сеть неизменна, то есть перерасчет не нужен, достаточно получить один раз план сети и в дальнейшем считать кратчайшие маршруты по нему, с гораздо большей скоростью. [64]
Кроме расчетов быстродействия алгоритмов от объема транспортной сети были проведены расчеты зависимости быстродействия алгоритмов от количества ограничений на узлах транспортной сети. [90] Были получены следующие результаты: Для транспортной сети объемом 168 узлов с одним ограничением -длиной участков дороги результаты следующие: построение кратчайшего маршрута 1.5 секунды, плана 360 секунд. Для транспортной сети с двумя ограничениями - длиной участков дороги, и коэффициентом замедления в зависимости от количества полос в одну сторону результаты следующие: построение кратчайшего маршрута 3.5 секунды, плана 454 секунд. Для транспортной сети с четырьмя ограничениями - длиной участков дороги, коэффициентом замедления в зависимости от количества полос в одну сторону, коэффициентом замедления в зависимости от ширины полосы, коэффициентом замедления в зависимости от наличия светофоров результаты следующие: построение кратчайшего маршрута 8.5 секунды, плана 760 секунд. Для транспортной сети с шестью ограничениями - длиной участков дороги, коэффициентом замедления в зависимости от количества полос в одну сторону, коэффициентом замедления в зависимости от ширины полосы, коэффициентом замедления в зависимости от наличия светофоров, коэффициентом замедления в зависимости от наличия дорожных знаков ограничения скорости, коэффициентом замедления в зависимости от времени суток результаты следующие: построение кратчайшего маршрута 14 секунд, плана 1270 секунд.
Схема реализации работы информационной системы
На замещенный XML накладывается XSL и формируется XHTML передаваемый пользователю. В основном страницы формирует компонент Publisher, хранящий статические тексты в базе данных, формирующий соответствующий XML и кэширующих их. [65] Однако для показа динамических компонентов, таких как карта, маршруты поиска и формы выбора используются другие компоненты. Практически при любом вызове функций происходит аутентификация пользователя и проверка его прав компонентом Auth. Когда пользователь открывает страницу, на которой показывается карта, ему показывается картинка в формате PNG, сформированная компонентой Atlas. Когда пользователь хочет увидеть маршрут, наложенный на карту, Atlas обращается к компоненту Ratling за данными по маршруту. Если подобный запрос есть в кэше XML компонента HyperXML, то возвращается этот XML, если их там нет, то производится поиск в кэше экспорта Wraith и если подобный запрос там есть, то данные просто передаются оттуда, если нет, то проверяется, существует ли план соответствующий заданным ограничениям и если существует, то он берется из кэша компонента Pathy, иначе Ratling производит расчет самостоятельно, записывает его в кэш Wraith, делает пометку о данном пользовательском запросе в Pathy, передает данные в HyperXML и на там основе дополнительных справочных данных формируется XML, кэшируется и возвращается в Ratling, который в свою очередь возвращает его в Atlas, где XML преобразуется в команды построения графического маршрута на соответствующую карту. Карта преобразуется в растровую картинку и в виде картинки в формате PNG отдается пользователю. В свою очередь, на странице с картой проезда находится еще и блок показа текстового маршрута-схемы проезда, поэтому точно такой же запрос приходит от самого Ratling, и т.к. данный запрос только что уже был выполнен, данные поступают из кэша HyperXML, на них накладывается соответствующий XSL, и в результате получается текстовый список необходимых для проезда по маршруту действий. Система авторизации и аутентификации пользователей осуществлена тремя способами: Через сертификат SSL и протокол HTTPS. Через авторизацию HTTP и ограничение доступа по IP адресу. Через собственную систему авторизации сайта (компонент Auth). Протокол HTTPS и сертификат SSL используется при экспорте информации, для того, что бы получатель информации мог быть уверен, что получает информацию именно от данной информационной системы. [31] Авторизация HTTP представляет собой просто список пользователей и паролей, хранящихся в файле паролей веб-сервера, и фактически закрывает от неуполномоченных пользователей административную часть проекта. Также в данном случае используется ограничение доступа по IP адресу, для того, что бы, даже если один или несколько паролей будут известны, предотвратить попадание в закрытую зону посторонних людей из мест, отсутствующих в списке разрешенных. Собственная система авторизации используется на открытой части проекта, и представляет собой следующий набор действий. При вводе пользователем своей пары логин/пароль ему выставляется сессионная кука (cookie), запоминаемая браузером пользователя до закрытия сессии работы. Она представляет собой набор бессмысленных символов, но в базе данных компонента Auth записывается строка соответствия этого набора и id пользователя. Через определенное время устаревшие авторизации удаляются. При любом заходе пользователя на страницу, требующую авторизации, проверяется его сессионная кука, если она выставлена и ей есть соответствие в базе, то пользователь считается авторизованным и пропускается в систему, данные о нем передаются при запросах другим компонентам системы. Иначе пользователю показывается только форма введения логина и пароля, и ссылки для регистрации. Для подержания актуального состояния информационной системы необходимо постоянно обновлять информацию, содержащуюся в ней, внося все возникающие изменения в дорожной и транспортной обстановке, и, вслед за этим обновляя генерируемые схемы и планы транспортной сети. Для обновления информации в информационной системе предусмотрено два основных механизма. Первым из них является административный интерфейс, к информационной системе позволяющий произвести любые изменения в данных. Фактически с помощью данного инструмента следует вносить лишь разовые изменения или изменения являющиеся исправлениями возможных ошибок.
Для постоянного, срочного обновления данных информационной системы предусмотрен механизм импорта в систему файлов XML. Формат данных файлов точно такой же, как и формат файлов генерируемых самой системой. Входящие файлы проходят обязательную проверку на правильность формата при помощи схем XSD.
Для правильного принятия XML в любом формате из любого возможного источника данных предусмотрено предварительное наложение на файл преобразующего в нужный формат XSL. [105]
