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

ПЕРЕЧЕНЬ УСЛОВНЫХ СОКРАЩЕНИЙ

ВВЕДЕНИЕ

ГЛАВА 1. СИСТЕМАТИЗАЦИЯ ПОНЯТИЙ И МЕТОДОВ ИССЛЕДОВАНИЯ

1.1. Классификация транспортных систем

1.2. Основные понятия области исследования

1.2.1. Транспортная сеть

1.2.2. Транспортный поток

1.2.3. Технические средства организации движения по сети

1.2.4. Управление транспортной сетью •

1.3. Обзор поисковых алгоритмов

1.4. Способы описания транспортных сетей

1.5. Проблемы решения задач исследования транспортных маршрутов

1.6. Задачи исследования транспортных маршрутов

1.6.1. Выбор критерия оценки эффективности построения маршрута

1.6.2. Постановка задачи построения оптимальных маршрутов

1.6.3. Постановка задачи построения маршрута перевозки опасных грузов

1.6.4. Постановка задачи объезда различных объектов

1.6.5. Постановка задачи построения маршрута проезда специального транспорта

1.6.6. Постановка задачи проведения вычислительного эксперимента

Выводы и основные результаты

ГЛАВА 2. МОДЕЛЬ РЕШЕНИЯ ЗАДАЧ ИССЛЕДОВАНИЯ ТРАНСПОРТНЫХ

МАРШРУТОВ

2.1. Графовые модели транспортной сети 4 3 2.1.1. Основные определения

2.2. Расширенная графовая модель

2.2.1. Управление транспортным потоком

2.2.2. Событийное управление на графах

2.2.3. Предикаты состояния расширенной графовой модели УДС

2.3. Способы представления графа

2.4. Методы преобразования графа

2.4.1. Кластеризация графа

2.4.2. Клеточное сжатие графа

2.4.3. Линейное сжатие графа

2.5. Унифицированная модель автотранспортной сети

2.5.1. Модель предметной области

2.5.2. Модель улично-дорожной сети

2.5.3. Модель транспортного маршрута

2.6. Граф улично-дорожной сети города и его свойства 77 Выводы и основные результаты

ГЛАВА 3. МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ИССЛЕДОВАНИЯ ТРАНСПОРТНЫХ

МАРШРУТОВ

3.1. Критерии оценки эффективности маршрутов

3.2. Методы расчета оценки эффективности построения маршрута

3.2.1. Статистический метод

3.2.2. Вероятностный метод

3.2.3. Метод анализа скоростного режима

3.2.4. Метод конфликтных точек

3.2.5. Метод экспертных оценок

3.3. Методы решения задач построения простых МАРШРУТОВ

3.4. Сравнительный анализ алгоритмов

3.5. Методы решения задач построения составных маршрутов 104 Выводы и основные результаты

ГЛАВА 4. ПРОГРАММНЫЙ КОМПЛЕКС ИССЛЕДОВАНИЯ ТРАНСПОРТНЫХ

МАРШРУТОВ

4.1. Назначение, возможности и структура системы

4.1.1. Организация и функционирование системы исследования

4.1.2. Программная инфраструктура системы

4.1.3. Система управления базами данных

4.2. Инструментальные средства исследования транспортных маршрутов

4.2.1. Система моделирования транспортной сети

4.2.2. Геоинформационная система построения и визуализации транспортных маршрутов

4.2.3. Подсистема учета маршрутов перевозки опасных грузов

4.2.4. Экспертная система определения коэффициента безопасности

4.2.5. Подсистема исследования алгоритмов

4.2.6. Разработка и реализация методики исследований 138 4.3. Характеристики инструментального и программного обеспечения

Выводы и основные результаты

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

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

На современном этапе развития транспортной инфраструктуры большое внимание уделяется решению частных задач оптимизации транспортных процессов [10, 29, 51]. Однако создание транспортно-логистической системы на уровне региона требует комплексного рассмотрения всех аспектов указанных процессов. Приоритетной становится задача построения оптимальных маршрутов перевозки на территории России для обработки транзитных и внешнеторговых грузопотоков [53, 86] . Как показывает практика, оптимальность маршрутов может обеспечиваться не только сокращением сроков перевозок или транспортных затрат, но и безопасностью маршрута.

Транспортную систему можно рассматривать в виде совокупности двух множеств элементов: «узлы» системы и «потоки» между узлами. Связями в данной трактовке системы будут отношения инциденции узлов и потоков. Такое представление позволяет применить концепции и методы теории графов, как к построению моделей транспортной системы и составляющих ее элементов (транспортная сеть, поток), так и к решению задач маршрутизации [55].

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

Множество критериев оптимальности построения маршрутов, а также тенденция к маршрутизации в режиме реального времени, например, с применением GPS-навигации, накладывает ограничения на специализацию и выбор наилучшего алгоритма нахождения оптимального решения [63, 64]. Актуальным становится проведение сравнительного анализа производительности различных алгоритмов и выдача рекомендаций пользователю по их применению [51].

В настоящей диссертационной работе полученные научные и практические результаты при решении частных задач построения маршрутов обобщены на основе методологии системного анализа, численных методов в единую методику анализа транспортной инфраструктуры региона и синтеза транспортной сети. Данная методика апробирована на полигоне г. Самара и Самарской области, в первую очередь в интересах предприятий ОАО «Куйбышевский нефтеперерабатывающий завод», ООО «ЦПУ-Самара», отдела ГИБДД УВД г. Самара и др.

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

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

Задачи исследования обусловлены поставленной целью и включают в себя:

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

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

Внедрение результатов работы . Разработанные в диссертации методы, алгоритмы, программный комплекс внедрены и используются в информационном центре отдела ГИБДД УВД г. Самара, на транспортных предприятиях Самарской области, в ОАО «Куйбышевский нефтеперерабатывающий завод», в учебном процессе специальности 230102 Самарского государственного аэрокосмического университета .

Апробация работы. Результаты диссертационной работы докладывались и обсуждались на II Международной молодежной школе-семинаре «БИКАМП-99» (Санкт-Петербург, 1999 г.); Второй Международной конференции «Интернет. Общество. Личность. ИОЛ-2000» (Санкт-Петербург, 2000 г.); VII, VIII, X, XI, XII Международных научных конференциях «Математика. Компьютер. Образование» (Дубна, 2000 г., 2004 г., Пущино, 2001 г., 2003 г., 2005 г.); XXV, XXVI, XXX Международных молодежных научных конференциях «Гагаринские чтения» (Москва, 1999 г., 2000 г., 2004 г.); VI Всероссийской научной конференции студентов и аспирантов «Техническая кибернетика, радиоэлектроника и системы управления» (Таганрог, 2002 г.); V, VI Всероссийских научных конференциях молодых ученых и аспирантов «Новые информационные технологии. Разработка и аспекты применения» (Таганрог, 2003 г., 2004 г.); Всероссийской научно-методической конференции «Управление качеством инженерного образования» (Казань, 2002 г.); Всероссийской студенческой научной конференции «V Королевские чтения» (Самара, 1999 г.); XXVI, XXVII Самарских областных студенческих научных конференциях (Самара, 2000 г., 2001 г.); 50-й студенческой научно-технической конференции (Самара, 2000 г.).

Публикации. По теме диссертации опубликовано 21 печатная работа, в том числе 6 статей, 15 тезисов докладов.

Структура и объем диссертации. Диссертация состоит из введения, четырех глав, заключения и приложения. Объем работы 156 страниц основного текста, включая 64 рисунка и 11 таблиц. Список литературы содержит 131 наименование.

ЗАКЛЮЧЕНИЕ

В работе ставилась цель: разработать методы и инструментальные средства построения оптимальных транспортных маршрутов по различным критериям оптимальности с использованием алгоритмов, применимость которых определяется в результате сравнительного анализа выполнения алгоритмов. Разработаны модели, наполняющие предметную область «Исследование автотранспортных маршрутов», определены критерии эффективности построения маршрутов, разработаны методы расчета показателей эффективности (в том числе, "безопасности) транспортных маршрутов. Построена графовая модель улично-дорожной сети г. Самара, имеющая более 100000 узлов и ребер. Решены задачи построения оптимальных маршрутов перевозки опасных грузов и проезда спецтранспорта. Разработанные алгоритмы позволяют повысить эффективность построения маршрутов, за счет их адаптации под особенности предметной области и минимизации использования вычислительных ресурсов (время, память).

1. EE Transactions on Evolutionary Computation. №1 (1), 1997.P.p 53-66. Dowsland K. Simulated annealing // Modern Heuristic Techniques for Combinatorial Problems. - N.Y.: McGraw-Hill, 1995. P.p. 34-47.

2. Floyd R.W. Algorithm 97: Shortest path // Comm. Assoc. Cornput. Mach. - 1962. - Vol. 5, N 6. P. 345.

3. Frederieksen G.N. Shortest path problem in planar graphs //24th Ann. Symp. Found. Comput. Sci., Tucson, Ariz, 7-9 November, 1983. - N.Y.: Silver Spring, Md, 1983. P. 242-247.

4. Fredman M.L. New bounds on the complexity of the shortestpath problem // SIAM J. Comput. - 1976. - Vol. 6. P. 83-89.

5. Galil Z. Efficient algorithms for finding maximal matchingon graphs // Lect. Notes Comput. Sci. - 1983.- Vol. 159. P. 90-113.

6. Goldberg D.E. Genetic Algorithms in Search, Optimization,and Machine learning. Addison-Wesley, 1989. P.15-44.

7. Johnson D.B. Efficient algorithms for shortest paths insparse networks // J. ACM. - 1977. - Vol. 24, N 1. P. 1-13.

8. Karlsson R.G., Poblete P.V. An О {m log log D) algorithm forshortest path//Discrete Appl. Math.-1983. - Vol. 6, N l.-P. 91-93.

9. Katon N., Ibaraki Т., Mine H. An 0{Kn2) algorithm for Кshortest simple paths in an undirected graph with nonnegative arc length // Trans. Inst. Electron, and Commun. Eng. Jap. - 1978. - A61, N 12. P. 1199-1206.

10. Shier D.R. Iterative methods for determining the К shortestpaths in a network // Networks. - 1976. - Vol. 6, N 3