автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.13, диссертация на тему:Методы разработки распределенной информационной системы параметрической транспортной сети города

ВВЕДЕНИЕ.

ГЛАВА 1. АНАЛИЗ ПРОБЛЕМ ПОСТРОЕНИЯ

РАСПРЕДЕЛЕННЫХ ИНФОРМАЦИОНЫХ СИСТЕМ ДЛЯ РЕШЕНИЯ ЗАДАЧ НА ТРАНСПОРТЕ.

1.1. Анализ проблем проектирования баз данных для решения 17 задач на транспорте.

1.2. Анализ построения распределенных информационных 24 систем.

1.3. Обзор средств разметки документов.

1.4. Анализ принципов функционирования и применения ГИС.

1.5. Анализ современных информационных систем для решения 52 задач на транспорте, представленных на рынке.

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

ГЛАВА 2. СТРУКТУРА ДАННЫХ ИНФОРМАЦИОННОЙ

СИСТЕМЫ "ТРАНСПОРТНАЯ СЕТЬ ГОРОДА"

2.1. Описание предметной области информационной системы.

2.2. Разработка концептуальной и реляционной схемы 63 предметной области.

2.3. Создание графа транспортной сети.

2.4. Разработка системы параметризации объектов на 77 транспортной сети.

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

ГЛАВА 3. ПОИСК КРАТЧАЙШИХ МАРШРУТОВ В

ТРАНСПОРТНЫХ СЕТЯХ.

3.1. Разработка алгоритмов нахождения кратчайших путей из 82 одной вершины к другой вершине графа.

3.2. Разработка алгоритмов нахождения кратчайших путей из 83 одной вершины ко всем другим вершинам графа.

3.3. Разработка алгоритмов поиска кратчайших путей по всем 88 точкам графа.

3.4. Разработка алгоритмов нахождения нескольких кратчайших 91 путей между двумя точками.

3.5. Разработка методов построения маршрутных планов.

3.6. Анализ зависимости времени выполнения алгоритмов от 94 объемов и степени параметризации транспортной сети.

Выводы по главе 3.

ГЛАВА 4. РАЗРАБОТКА РЕАЛИЗАЦИИ ИНФОРМАЦИОННОЙ 100 СИСТЕМЫ.

4Л. Схема реализации работы информационной системы.

4.2. Разработка методов представления информации для 107 пользователя.

4.3. Схема взаимодействия компонентов информационной 110 системы.

4.4. Методы сбора, распределения и обновления информации. 114 Выводы по главе 4. 117 ЗАКЛЮЧЕНИЕ.

Актуальность темы. С проблемами экспедирования и транспортировки грузов сталкиваются не только специалисты, основным направлением деятельности которых является транспортная логистика, но и огромная масса людей, чей интерес к задачам перевозок может быть как разовым, так и практически постоянным. Например, одним из обязательных условий проведения любой торговой операции является регулярное и своевременное перемещение товара. Любая организация, действующая в сфере производства, не может обойтись без обращения к услугам перевозчика или экспедитора. [15]

Сложность автоматизации деятельности транспортной организации с учетом распределенной структуры и географической удаленности отдельных ее компонентов делает актуальной задачу разработки программного обеспечения с ориентацией на сетевую обработку информации. Необходимо обеспечить информационное обслуживание массовых и разнообразных запросов со стороны предприятий-перевозчиков, экспедиторов и частных лиц, заинтересованных в получении оперативной транспортной информации. [25]

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

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

Объектом исследования является деятельность транспортного предприятия, связанная с обработкой информации о транспортной сети города.

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

Для достижения поставленной цели в работе решены следующие основные задачи:

• проведен анализ информационных требований пользователей по предметной области "Транспортная сеть города";

• разработаны концептуальная и реляционная схемы предметной области [6];

• формализовано представление данных о транспортной сети в виде параметрических направленных сетевых графов [11];

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

• разработана архитектура построения распределенной информационной системы для решения задач на транспорте [5,7];

• разработана реализация информационной системы "Транспортная сеть города" в виде интернет-проекта [4].

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

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

• результаты анализа предметной области "Транспортная сеть города";

• разработанная семантическая модель и реляционная схема базы данных предметной области;

• методы представления базы данных информационной системы в виде параметризированных однородных сетевых графов;

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

• архитектура построения распределенной информационной системы для решения задач на транспорте;

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

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

Практическая ценность и реализация результатов работы. Результаты работы имеют реальный практический выход в виде разработанного и отлаженного программного обеспечения с методикой его использования в организациях и на предприятиях. Разработанные методы и алгоритмы прошли апробацию и внедрены для практического применения в ООО "Яндекс", ТК "Стройтехника ТМ". Значимость выполненных исследований подтверждается их использованием на этих предприятиях. Практическое использование результатов подтверждено соответствующими актами о внедрении, приводимыми в приложении к диссертации.

Реализация информационной системы была внедрена в ООО "Яндекс", где предложенные методы и решения реализованы в виде распределенной информационной системы, способной автоматизировать разработку сетевых решений и обрабатывать запросы пользователей. Информационная система была использована для разработки геоинформационных проектов "Яндекс.Атлас" и "Яндекс.WAP".

Также реализация информационной системы была внедрена в ТК "Стройтехника ТМ", что позволило компании сократить транспортные расходы и улучшить обслуживание клиентов за счет увеличения оперативности и повышения качества доставки.

Результаты диссертационной работы использованы в учебном процессе кафедры "Автоматизированные системы управления" МАДИ (ГТУ) по дисциплинам "Базы данных" и "Проектирование ИС".

Апробация результатов. Основные положения и результаты диссертации докладывались и обсуждались на заседаниях кафедры "Автоматизированные системы управления" МАДИ (ГТУ) в 2000-2003 годах, на научно-методических конференциях МАДИ (ТУ) (Москва 1999и

2003 гг.), на республиканских межрегиональных и международных научно-технических конференциях, симпозиумах и семинарах (1998-2003 гг.).

Публикации. Отдельные положения диссертации отражены в 11 печатных работах.

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

Выводы по главе 4.

1. Вслед за теоретическим решением задач построения информационной системы произведены работы по практической реализации предложенных методов и решений.

2. Описаны механизмы и принципы взаимодействия распределенных компонентов информационной системы, экспериментальная транспортная сеть, которая легла в основу данной реализации, применение методов поиска кратчайших маршрутов для экспериментальной транспортной сети.

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

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

ЗАКЛЮЧЕНИЕ.

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

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

2. На основе приведенных обзоров и анализов, а также описания предметной области разработаны концептуальная и реляционная схемы.

3. Разработаны основные принципы преобразования неоднородной структуры данных информационной системы в однородную структуру в виде сетевых графов и методы их хранения во вторичных базах данных.

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

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

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

1. Атре Ш. Структурный подход к организации баз данных. // М.: Финансы и статистика, 1983. - 320 с.

2. Бойко В.В., Савинков В.М. Проектирование баз данных информационных систем. // М.: Финансы и статистика, 1989. 351 с.

3. Будихин A.B., Гуджоян О.П., Виленц А.Р. Структура данныхинформационной системы «Транспортная сеть города». // Сборник научных трудов "Автоматизированные системы управления в автотранспортном комплексе". М.: МАДИ (ТУ), 1998, с.123-138

4. Будихин A.B., Гуджоян О.П., Виленц А.Р. Поиск кратчайших маршрутов в транспортных сетях. // Сборник научных трудов «Современные информационные технологии в автотранспортном комплексе и дорожном строительстве». М.: МАДИ (ТУ), 1999, с. 30-43

5. Виленц А.Р. Использование информационных технологий для решения задач поиска кратчайших путей на транспортной сети. // Сборник трудов "Международная конференция. Информационные технологии в образовании технике и медицине". ВолгГТУ, 2002 С. 57- 59

6. Виленц А.Р. Методы построения интеллектуальной системы параметризации объектов на транспортной сети города. // Пятый международный симпозиум. Интеллектуальные системы. 2002, Материалы. М.: МИФИ. 2002, С. 110 - 112

7. Грабер М., SQL Справочное руководство. // Издательство: Лори, 2001 -304 с.

8. Грабер М., Введение в SQL. // Издательство: Лори, 2000 4001. С.

9. Данилова Т.Ю., Панов С.А. Пример создания информационных ресурсов территорий // Информационные ресурсы России. 1997. - N2. -С. 17-20.

10. Дейт К. Введение в системы баз данных.// М.: Наука. 1980.- 463с.

11. Дейт К. Руководство по реляционной СУБД DB2. // М.: Финансы и статистика, 1988. 320 с.

12. Джексон Г. Проектирование реляционных баз данных для использования с микроЭВМ. // М.: Мир, 1991. 252 с.

13. Джонсон Э., Потоки в сетях. // Сборник «Исследование операций», т. 1, «Мир», Москва 1981 712 с.

14. Елманова Н.З., Трепалин С.В. Delphi 4: технология COM. OLE, ActiveX, Автоматизация, MIDAS, Microsoft Transaction Server // M.: Диалог-МИФИ, 1999.-320 с.

15. Замулин А. В. Системы программирования баз данных и знаний // Новосибирск: Наука, 1990,- 352 с.

16. Карабин П., Язык программирования Java: Создание интерактивных приложений для Internet // Познавательная книга плюс, 2001,-224 С.

17. Кириллов В.В. Основы проектирования реляционных баз данных. Учебное пособие. // СПб.: ИТМО, 1994. 90 с.

18. Кириллов В.В. Структуризованный язык запросов (SQL). // СПб.: ИТМО, 1994.-80 с.

19. Кофман А., Крюон Р. Массовое обслуживание. Теория и приложения. // Издательство "Мир", Москва, 1965. 229 с.

20. Кошкарев A.B. Толковый мини-словарь основных терминов по геоинформатике (с английскими эквивалентами). // ГИС обозрение, весна 1994, No 0. С.56-59, ГИС-обозрение, осень 1994, No 1. - С.59-62. ГИС обозрение, зима 1994, No 2. - С.50-51.

21. Кузнецов С.Д. Развитие идей и приложений реляционной СУБД System R. // "Вычислительные науки. Т.2 (Итоги науки и техники ВИНИТИ АН СССР)". М„ ВИНИТИ АН СССР, 1989.- 94-120 с.

22. Липаев В.В., Филинов E.H., "Мобильность программ и данных в открытых информационных системах.", // РФФИ, 1997 351 с.

23. Липатов Е. П. Теория графов и её применения. // М., Знание, 1986,-32 с.

24. М. Свами, К. Тхуласираман. Графы, сети и алгоритмы. // Москва «Мир» 1984, 455 с.

25. Мартин Дж. Планирование развития автоматизированных систем. // М.: Финансы и статистика, 1984. 196 с.

26. Мейер М. Теория реляционных баз данных. // М.: Мир, 1987.608 с.

27. Орлик С. В ожидании CORBA 3 // Открытые системы, 1999, №2, с. 17

28. Орфали Р., Харки Д. Java и Corba в приложениях клиент -сервер. // Изд. 2-е, Лори-пресс, 2001, 716 С.

29. Орфали Р., Харки Д., Эдварде Дж., Основы CORBA. //. М:. МАЛИП 1999,- 317 с.

30. Осипов М.В., Мачульский О.Л., Калиниченко Л.А. Отображение модели данных XML в объектную модель языка СИНТЕЗ // Электронные библиотеки, Санкт-Петербург, 1999, с. 23 - 30

31. Питтс Н. XML за рекордное время // Пер. с англ. М.: Мир,2000. 444 с.

32. Риккарди Г., Системы баз данных. Теория и практика использования в Internet и среде Java // М.: Издательский дом "Вильяме",2001. -480 с.

33. Тиори Т., Фрай Дж. Проектирование структур баз данных. // В 2 кн., М.: Мир, 1985. Кн. 1. - 287 е.: Кн. 2. - 320 с.

34. Ульман Дж. Базы данных на Паскале. // М.: Машиностроение, 1990. 386 с.

35. Ульман Дж. Основы систем баз данных. // М.: Финансы и статистика, 1983. 334 с.

36. Хаббард Дж. Автоматизированное проектирование баз данных. //М.: Мир, 1984.-294 с.

37. Цикритизис Д., Лоховски Ф. Модели данных. // М.: Финансы и статистика, 1985. 344 с.

38. Цимбал Александр. "Технология CORBA для профессионалов". // СПб.; М.; Харьков; Минск: Питер, 2001. 624 с.

39. Эдди С. XML: Справочник /Пер. с англ. // СПб: Питер, 1999.480 с.

40. Яворски Д., Перроун П., Система безопасности Java. // Руководство разработчика, Вильяме, 2001 528 с.

41. Яргер Р., Риз Д., Кинг Т., MySQL и mSQL. Базы данных для небольших предприятий и Интернета // М:. Символ Плюс, 2000 - 560 с.

42. Abiteboul S., Hull R. IFO: A Formal Semantic Database Model // ACM Trans. Database Syst.- 12, N 4.- 1987,- P. 525-565

43. Bell D.A. Issues in Relational Database Performance // Data and Knowledge Eng.- 1988.- 3, N 1.- P. 46-61

44. Blasgen M.W., Eswaran K.P. Storage and Access in Relational Data Bases // IBM Syst. J.- 1977,- 16, N 4,- P. 363-377

45. Clohessy K., "Using object-oriented programming tools to build real-time embedded systems" // Real-time engineering, 1996/Fall

46. Codd E. F. A Relational Model of Data for Large Shared Data Banks // Commun. ACM.- 26, N 1,- 1970.- p. 377-387

47. Cravotta N. "Real-time operating systems" // Embedded system programming, 1997/march

48. Cuny J., Forman G., Hough A., Kundu J., Lin C., Snyder L., Stemple D., "The Ariadne debugger: scalable application of event-based abstraction", // ACM, 1993-P. 85-95

49. Date C.J. An Introduction to Database Systems. V.l. 4th ed. // Reading, Mass.: Addison-Wesley.- 1984.- 639 c.

50. Dijkstra E.W. A Note on Two Problems in Connection with Graphs, //Numerical Mathematics, 1959, 1:269-271.

51. Elmasri R. The category concept: An Extension to the entity-relationship model. // Data & Knowledge Engineering, 1985, v. 1, #1, p. 75-116.

52. Encontre V., "How to use modeling to implement verifiable, scalable, and efficient real-time application programs", Real-time engineering, 1997/Fall

53. Finkelstein S., Schkolnick M., Tiberio P. Physical Database Design for Relational Databases // ACM Trans. Database Syst.- 1988,- 13, N 1.- C. 91128

54. Florescu D., Kossmann D., A Performance Evaluation of Alternative Mapping Schemes for Storing XML Data in a Relational Database Rapport de Recherche No. // 3680 INRIA, Rocquencourt, France, May 1999, P 27-34

55. Floyd R.W. Algorithm 97: Shortest Path, Comm. ACM, 1962, 5:6,p.345

56. Fritzson P., Gyimothy T., Kamkar M., Shahmehri N., "Generalized algorithmic debugging and testing" // ACM, 1991, 317 326

57. Goldman R., McHugh J., Widom J. From Semistructured Data to XML: Migrating the Lore Data Model and Query Language // WebDB Workshop, Philadelphia, USA, 1999

58. Held M., Karp R. M., The Traveling Salesman Problem and Minimum Spanning Trees // Operations Res. Vol 18, 1138-1162 (1970).

59. ISO 8879:1986. "Information Processing Text and Office Systems - Standard Generalized Markup Language (SGML)", Amd 1:1988, P 15.

60. Johnson D.B. A Note on Dijkstra's Shortest Path Algorithm, // Journal of the ACM (JACM), v.20 n.3, p.385-388, July 1973.

61. Krzanovski R.M., Palylyk C.L., Crown P.H. GIS Lexicon. 19911992 International GIS Sourcebook. Geographic information system technology in 1991. // Fort Collins: GIS World, Inc., 1991. - P.552-568

62. Kuznetsov S.D. OODBMS's Query and Programming Languages: What Do They Provide and What Do We Need (Extended Abstract). // Submitted to the Second East-West Workshop on Advanced Databases. 1994: 138-146.

63. Lin S. Computer Solutions of the Traveling Salesman Problem, // Bell Syst. Tech. J., Vol. 44, 2245-2269 (1965).

64. Locke C.D., "Fundamentals of Real-Time" // Lockhead Martin, White Paper -Issue 1.0, 1998

65. Lorie Raymond A., Daudenarde Jean-Jacques P. On Extending the Realm of Application of Relational Systems // In Information Processing 86, ed. H.-J. Kugler, Elsevir Science Publishers, 1986.- 889-894

66. McDonell R., Kemp K. International GIS Dictionary. // Geoinformation International, 1995. 111 p.

67. McGoogan J., Realtime CORBA A White Paper- Issue 1.0, OMG Realtime Platform SIG, Initial Review Draft, Nov 1996.

68. McHugh Jason, Abiteboul Serge, Goldman Roy, Quass Dalian, Widom Lore Jennifer: A Database Management System for Semistructured Data. // SIGMOD Record 26(3): 54-66 (1997)

69. Mittag L. "Multitasking design and implementation", Embedded system programming, 1998/march

70. Offutt A.J., Hayes J.H. "A semantic model of program faults" // ACM, 1996, P 195-200

71. Peckham Joan, Maryanski Fred. Semantic Data Models // ACM Comp. Surv.- 20, N 3.- 1988.- 153-189

72. Pierce A.R., Bibliography on Algorithms for Shortest Path, Shortest Spanning Tree and Related Circuit Routing Problems (1956 1974) // Networks, 1975, vol. 5, pp. 129-149.

73. Schmidt D.C., Vinoski S., CORBA and XML, Part 2: XML as CORBA Data (of UC Irvine) // C/C++ Users Journal, July 2001

74. Schmidt D.C., Vinoski S. "Introduction to CORBA Messaging" // SIGS C++ Report, 1998, Vol. 10, No. 10.

75. Schmidt D.C., Vinoski S. "Portable Object Adapter" // SIGS С++ Report, 1998, Vol. 10, No. 7.

76. Stonebraker M., Jeff A., Hanson E. Extending a Database System with Procedures // ACM Trans. Database Syst.- 12, N 3.- 1987.- 350-376

77. Stonebraker M. Future Trends in Database Systems // IEEE Trans. Knowledge and Data Eng.- 1, N 1,- 1989,- 33-44

78. Stroustrup B. The С++ Programming Language // Addison-Wesley, Professional, Mass., 1997, P. 1040

79. Tabourier Y., All Shortest Distances in a Graph: An Improvement to Dantzig's Inductive Algorithm // Discrete Mathematics, vol. 4, 1973, pp. 83-87

80. Tsai J., Bi Y., Yang S., Smith R. "Distributed real-time systems. Monitoring, visualization, debugging, and analysis", Wiley-Interscience Publication, 1996, p 317

81. Vinoski S. "New Features for CORBA 3.0" // С ACM, 1998, vol 41, p 44 52

82. Whang K.-Y. Constructing Cost Formulas for Relational Database Query Optimizers: A Tutorial // TENCON'87: IEEE Reg. 10th Conf., Seoul, Aug. 25-28, 1987. Proc. Vol. 1. New York, 1987,- C. 132-1411. Публикации в интернете:

83. Пауэре Ш. Чего мы ждем от XML // Мир ПК. 1998. - N3. -http: //www. osp. ru/pc world/1998/03/180 .htm

84. Beckett D., Miller E., Brickley D. An XML Encoding of Simple Dublin Core Metadata, http://dublincore.org/documents/2001/04/ll/dcmes- xml /. Proposed Recommendation.

85. Brickley D., Guha R.V. Resource description framework (RDF) schema specification. http://www.w3.org/TR/PR-rdf-schema. W3C Proposed Recommendation. Technical report, W3C, 1999.

86. Cover R. Astronomical Instrument Markup Language (AIML). http://www.oasis-open.org/cover/aiml.html.