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

• Автор: Тимеряев, Тимофей Валерьевич
• Шифр специальности: 05.13.01
• Научная степень: Кандидатская
• Год защиты: 2015
• Место защиты: Уфа
• Количество страниц: 203 с. : ил.

СОДЕРЖАНИЕ
Введение
Глава 1. Анализ современного состояния в области оперативного управления маршрутизацией транспортных средств
1.1. Техническая постановка задачи оптимизации оперативных
транспортных перевозок
1.2. Обзор задач поиска оптимальных путей в транспортных сетях и алгоритмов их решения
1.3. Обзор задач уменьшения размерности графа транспортной сети
Выводы по 1-й главе
Глава 2. Задача поиска оптимальных путей между всеми парами узлов транспортной сети
2.1. Алгоритм разборки-сборки графа транспортной сети
2.2. Доказательство получения точного оптимального решения с помощью алгоритма разборки-сборки графа транспортной сети
2.3. Примеры решения задачи поиска оптимальных путей с помощью
алгоритма разборки-сборки графа транспортной сети
Выводы по 2-й главе
Глава 3. Поиск метрических характеристик и уменьшение размерности графа транспортной сети
3.1. Задача поиска метрических характеристик транспортной сети
3.2. Метод и алгоритм поиска центра и радиуса транспортной сети
3.3. Метод и алгоритм поиска диаметра транспортной сети
3.4. Уменьшение размерности графа транспортной сети
Выводы по 3-й главе
Глава 4. Программная реализация разработанных алгоритмов и анализ

полученных результатов
4.1. Данные и методика тестирования
4.2. Поиск оптимальных путей между всеми парами узлов транспортной сети
4.3. Поиск метрических характеристик транспортной сети
4.4. Уменьшение размерности графа транспортной сети
4.5. Внедрение разработанного программного обеспечения
Выводы по 4-й главе
Заключение
Список литературы
Приложение 1. Среднее время решения задач уменьшения размерности графа транспортной сети разными алгоритмами
Приложение 2. Акт о внедрении

ВВЕДЕНИЕ
Актуальность темы исследования
Транспорт — одна из основных отраслей материального производства. На транспорте, как в добывающей и обрабатывающей промышленности и в сельском хозяйстве, создается стоимость. Однако транспорт имеет ряд своеобразных черт. Его продукция — изменение местоположения, перемещение грузов и людей. Эта продукция создается и потребляется одновременно, в самом процессе работы транспорта [36].
Многие современные области промышленности в различном объеме содержат транспортную систему (ТС). В зависимости от типа предприятия ТС может представлять собой: локальную транспортную сеть предприятия,
дорожную сеть территориального образования, в пределах которого расположены цеха/филиалы предприятия, совокупность авиалиний между пунктами производства и доставки т.д. В тех случаях, когда ТС имеет значительное влияние на характер работы промышленного предприятия, некоторыми из способов повышения эффективности работы предприятия и сокращения издержек являются оперативный мониторинг и оптимизация процессов связанных с ТС.
Как правило, ТС моделируется нагруженными графовыми структурами. При этом для многих из решаемых на практике графовых задач известные алгоритмы имеют полиномиальную по входным параметрам сложность. Ряд часто возникающих на нагруженных графах задач транспортного характера относится к ЫР-трудным. С целью получения их решения за приемлемое время используются эвристические методы, не дающие оптимального решения.
События последних десятилетий в транспортной промышленности связаны со становлением и бурным развитием ее компьютеризации. Сопутствующее массовое распространение навигационных систем на основе цифровой картографии привело к появлению большого числа картографических сервисов (как коммерческих, так и бесплатных) с большим объемом накопленных данных и различными интерфейсами доступа к ним. Таким образом, при решении

2. Граф, для которого вычисляются характеристики, является полным;
3. Требуется вычислять метрические характеристики не для всего графа G, а для некоторых его подграфов GX,G2,
Во всех этих случаях возможно периодическое изменение связей между вершинами графа и весов ребер, а при поиске характеристик для подграфов GX,G2,... изменение их состава. Все это при использовании методов решения задач SSSP и DSP для поддержания актуальности матрицы М требует периодического пересчета метрических характеристик.
Тривиальным методом решения является просмотр всех элементов матрицы расстояний М. Для нахождения диаметра в случае неориентированного графа в силу симметричности М необходимо просмотреть (п1-п}12 элементов
матрицы, для нахождения радиуса все п2 элементов. То есть сложность решения тривиальным методом 0[п2). Время поиска характеристик может быть
уменьшено, если вычисленные расстояния между вершинами графа хранятся не в виде матрицы, а в специальной структуре данных, например, в очереди с приоритетом [81]. Однако временная сложность построения таких структур данных превосходит 0(п2), например, 0(”4) [81, с. 198] для сортированного
связного списка, О (п2 log и2) для двоичной кучи [81, с. 151].
Задачи о поиске метрических характеристик могут ставиться на специального вида графах, в этом случае дополнительной информацией, используемой при поиске характеристик, является знание о структуре графа. Для неориентированных ненагруженных деревьев диаметр и радиус могут быть найдены за 0(т) [136]. Для поиска диаметра в этом случае используется так называемый 2-sweep алгоритм: выбирается случайная вершина у, для которой ищется максимально удаленная вершина vj} d - ^(v,) = w(v,-,vy). Центр графа определяется как вершина в середине пути П(