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

На правах рукописи

ТИМЕРЯЕВ Тимофей Валерьевич

МЕТОДЫ И АЛГОРИТМЫ УПРАВЛЕНИЯ МАРШРУТИЗАЦИЕЙ В ТРАНСПОРТНЫХ СЕТЯХ НА ОСНОВЕ ОПЕРАТИВНОЙ ОБРАБОТКИ ИНФОРМАЦИИ В РАЗРЕЖЕННЫХ ГРАФАХ

Специальность 05.13.01 - Системный анализ, управление и обработка информации (в промышленности)

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

Уфа-2015 005568506

005568506

Работа выполнена на кафедре высокопроизводительных вычислительных технологий и систем Федерального государственного бюджетного образовательного учреждения высшего профессионального образования «Уфимский государственный авиационный технический университет»

Научный руководитель

д-р техн. наук, доцент Шерыхалипа Наталия Михайловпа

Официальные оппоненты

д-р техн. наук, доцент Михеепа Татьяна Ивановна

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

канд. физ.-мат. наук, доцент Макаровских Татьяна Анатольевна

Южно-Уральский государственный университет (национальный исследовательский университет), доцент кафедры экономико-математических методов и статистики

Ведущая организация

ФГБОУ ВПО «Санкгг-Петербургский государственный университет гражданской авиации», г. Санкт-Петербург

Защита состоится 3 июня 2015 г. в 1000 часов на заседании диссертационного совета Д 212.288.03 на базе ФГБОУ ВПО «Уфимский государственный авиационный технический университет» по адресу: 450000, г. Уфа, ул. К. Маркса, 12

С диссертацией можно ознакомиться в библиотеке ФГБОУ ВПО «Уфимский государственный авиационный технический университет» и на сайте www.ugatu.su

Автореферат разослан «? 1 » АИРСА $_2015 г.

в кг

Ученый секретарь диссертационного совета

д-р техп. наук, проф. / ^ //¿^ ? В. В. Миропов

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы исследования

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

Как правило, ТС моделируется нагруженными графовыми структурами. При этом для многих из решаемых на практике графовых задач известные алгоритмы имеют полиномиальную по входным параметрам сложность. Ряд часто возникающих на нагруженных графах задач транспортного характера относится к ЫР-трудным. С целью получения их решения за приемлемое время используются эвристические методы, не дающие оптимального решения.

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

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

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

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

Степень разработанности темы. Задачами оптимизации транспортных сетей и разработки алгоритмов поиска кратчайших путей занимались А. О. Алексеев, С. И. Сергеев, И. И. Меламед, Ю.И. Палагин, Т.Н. Михеева, У. Цвик, М.Торуп, A.B. Голдберг, Х.Н. Габов.

Методы поиска метрических характеристик графов изложены в работах отечественных и зарубежных ученных A.M. Раппопорта, Р. Юстера, П. Кре-шензи, Ф.В. Тейкса, Ф.Ф. Драгана.

Задачам аппроксимации графов в различной постановке посвящены работы российских ученных В.П. Ильева, A.A. Агеева, Г.Ш. Фридмана, а также зарубежных ученных П. Сандерса, Д. Шпилмана, Д. Добкина, Дж. Лесковеца, Дж. Капириса.

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

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

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

Задачи исследования:

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

2. Разработать метод и алгоритмы эффективного определения метрических характеристик транспортных сетей.

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

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

Результаты, выносимые па защиту:

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

2. Метод и алгоритмы эффективного определения метрических характеристик транспортных сетей.

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

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

Научпяя новизна полученных результатов заключается в следующем:

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

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

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

Методы исследования

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

Достоверность результатов

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

Теоретическая и практическая значимость

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

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

ративном управлении маршрутизацией транспортных средств в среднем на 15% по сравнению с известными методами.

Результаты работы внедрены в ООО «Эксперт» (г. Уфа), что подтверждается актом о внедрении.

Апробация работы

По основным результатам работы были сделаны доклады на следующих конференциях: Всероссийская зимняя ппсола-семинар аспирантов и молодых ученых «Актуальные проблемы науки и техники» (Уфа, 2010, 2012, 2014); XXXVI Международная молодежная научная конференция «Гагаринские чтения» (Москва, 2010); Всероссийская научная конференция молодых ученых «Наука. Технологии. Инновации» (Новосибирск, 2010); V Всероссийская конференция «Проблемы оптимизации и экономические приложения» (Омск, 2012); Всероссийская молодежная научная конференция «Мавлютовские чтения» (Уфа, 2009, 2011, 2012); Вторая международная научная конференция «Информационные технологии и системы» (Челябинск, 2013); Международная конференция «Информационные технологии интеллектуальной поддержки принятия решений». Российско-немецкий семинар «Модели и алгоритмы прикладной оптимизации» (Уфа, 2013), Всероссийская научно-практическая конференция «Механика: современное состояние, проблемы, перспективы» (Чебоксары, 2014), а также на научных семинарах кафедры высокопроизводительных вычислительных технологий и систем Уфимского государственного авиационного технического университета.

Публикации. Основные результаты диссертации отражены в 17 научных трудах, в том числе в 8 статьях в изданиях, рекомендованных ВАК, 9 - в других изданиях.

Структура и объем работы. Диссертация (203 с.) состоит из введения, четырех глав, заключения, списка литературы (243 наимен.) и приложений.

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ

Во введении обоснована актуальность работы; сформулирована цель и задачи исследования; приведены результаты, выносимые на защиту; отмечена их практическая значимость и научная новизна.

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

В главе 2 проводится разработка алгоритма «разборки-сборки графа» для решения задачи поиска кратчайших путей между всеми вершинами. На этапе декомпозиции (разборки) из графа последовательно удаляются вершины, при этом сохраняется информация об удаленной вершине, если путь через нее меж-

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

Пусть дан связный ориентированный или неориентированный простой нагруженный граф 0 = (К,£,С) с неотрицательной вещественной весовой функцией на ребрах С/: Е —> [о,+оо). Необходимо для всех пар вершин графа найти кратчайший путь между вершинами в паре, т. е. найти матрицу расстояний М размерности их и с элементами т{у1,Уу) и матрицу последователей Р

размерности их и, элемент р(},/) которой представляет собой идентификатор вершины, которая следует за вершиной V,- в кратчайшем пути от V; и V.-.

Рисунок 1. Блок-схема алгоритма «разборки-сборки графа»

Этап декомпозиции графа является многоступенчатым и состоит в последовательном приближении исходного графа С0 =(У0,Е0,и0) графами сжимающей последовательности 5(С0) = (С1,02,...,0Г). Начальные значения матриц М и Р соответствуют состоянию исходного графа - расстояния соответ-

ствуют весам ребер графа, последователи оптимальных путей соответствуют существующим ребрам. При удалении вершины vp необходимо гарантировать

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

быть увеличена, пересчитываются по формуле m(v,-,v/)= m(v;-,vp)+ m{vp ,v,).

В результате декомпозиции остается подграф с двумя вершинами. До начала работы сборки графа определена последовательность графов S={Go,G\,...,G„.2}, соответствующие множества вершин Vp и последовательность удаленных вершин vp. Здесь Go - исходный граф, Gn-г — наименьший

граф последовательности, у которого на этапе микрорешения найдены кратчайшие пути между двумя вершинами. На этапе сборки производится обратный ход от Gn-2 к Go с расчетом кратчайших путей от и до восстанавливаемой вершины vp. В графе Gp вычислены кратчайшие пути, т. е. известны элементы матриц Ми Р, позволяющие определить длины путей и сами пути. Поэтому при добавлении вершины vp необходимо определить кратчайшие пути между восстанавливаемой вершиной и восстановленными, причем минимум выбирается между путями, состоящими не более чем из двух шагов. Пути, состоящие из большего числа шагов, проходящие через другие вершины графа, не рассматриваются, так как они не минимальны.

Кратчайшие расстояния от восстанавливаемой вершины vp до любой вершины vt е Vp графа Gp можно рассчитать с помощью формулы

m{yp,v;)= min [m(v-p,vJ-)+w(vy,v,)] .

Vj£AP

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

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

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

Метрические характеристики являются существенными свойствами графов и дают важную информацию о структурах, представляемых ими. Например, в задачах размещения (facility location problem) центр и радиус могут соответ-

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

Рассматриваются задачи двух типов: 1) нахождение центра, радиуса и диаметра графа, заданного лишь множествами вершин V и ребер Е; 2) нахождение центра, радиуса и диаметра графа при наличии дополнительной информации в виде вычисленной в главе 2 матрицы кратчайших расстояний М между всеми парами вершин графа. Заметим, что задача 2) имеет существенно меньшую вычислительную сложность, чем расчет матрицы минимальных расстояний М. Поэтому далее рассматривается задача 1).

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

Будем называть множеством опорных вершин Р= {р\,Р2>--->Рд} данного

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

В начале алгоритма поиска центра и радиуса графа выбирается некоторое количество опорных вершин, и вычисляются расстояния от них до всех остальных вершин. Находятся нижняя п и верхняя ги оценки для радиуса и вершина-претендент на центр с,- на данной итерации. После этого из рассмотрения выбрасываются вершины, расстояния от которых не входят в найденные границы. Если в рассмотрении остались вершины, число опорных вершин увеличивается, и снова определяются оценки для радиуса и диаметра. Процесс продолжается до тех пор, пока нижние и верхние оценки не совпадут rj=ru (или совпадут с заданной погрешностью). При этом получают искомые значения радиуса и центра.

Нижнюю границу радиуса п можно определить с помощью множества

опорных вершин Р: ц = mm maxm(v,-,v„). С другой стороны, радиус графа г

п реР

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

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

тахЦс,- ,Vpj=r; = min maxm(v;, v„) (1)

реР i=\,...ji ре?

и с как можно меньшим эксцентриситетом е(с, ) .

С этой целью в графе ищутся самые удаленные друг от друга вершины р\ и

рг. Для этого выбирается любая вершина графа d\, последующие вершины в

данной «последовательности» определяются соотношением

dj+\ '■ ]= J,j=2, 3, ...

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

Найденные вершины р\ и рг включаются в пустое до этого множество опорных вершин Р. Претенденты на центр ct определяются по формуле (1). Ее-

ли для первого претендента на центр й выполняется равенство оценок радиуса, данная вершина является одним из центров графа и радиус определен. Если же ги>гь самая удаленная от с\ вершина р3 : Цс[, v;,3 )= ) добавляется во множество опорных вершин Р и выполняется поиск с2 по формуле (1). Процесс продолжается до тех пор, пока для какого-то из претендентов не будет выполнено равенство оценок радиуса.

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

При поиске диаметра графа можно считать, что хорошим приближением периферийных вершин являются вершины, часть которых максимально удалена от центра графа. Имея вычисленную центральную вершину с и некоторую нижнюю оценку диаметра графа (равную, например, максимальному из уже найденных эксцентриситетов вершин) можно проверять на периферийность только пары вершин (V,-, V,), расстояние до хотя бы одной из которых от центра больше с//2: т(с,у^> ¿¡/2 V т(с,м2. Использование в неравенствах в

качестве точки отсчета центральной вершины позволяет уменьшить число просматриваемых пар вершин V,- с расстоянием удовлетворяющим т(с,у,)>с/,</2.

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

Алгоритм поиска диаметра состоит из двух частей: 1) находится одна из центральных вершин графа с использованием описанного выше алгоритма; 2) производится непосредственный поиск диаметра.

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

Первая часть алгоритма — поиск одной из центральных вершин графа с с помощью алгоритма, описанного выше. В процессе поиска с для некоторого множества вершин графа ^{г;} решается задача ЭвБР, то есть Для всех вершин этого множества известны кратчайшие расстояния, в том числе эксцентриситеты е(^,).

Начальные значения нижней и верхней границ диаметра полагаются равными: ¿/=0, с1и=оо. Используя вычисленные эксцентриситеты е(5,) вершин множества б1, по формулам ¿1 =тах{<//,е(5,)}, с1и = тт{^и,2-е(5,-)} изменяются зна-

чения верхней и нижней границ. Верхняя оценка du — максимально возможное расстояние между парой вершин графа. По правилу треугольника кратчайшее расстояние между двумя произвольными вершинами графа не больше, чем длина пути между ними, проходящего через какую-либо вершину s¡, каждый из подпутей которого в свою очередь не больше эксцентриситета вершины í¡. Далее производится сокращение числа вершин-претендентов на периферийные. Во время работы алгоритма для каждой вершины v, хранятся значения нижней 8íiy¡) и верхней e„(v,) границ эксцентриситета. В начале для всех вершин они полагаются равными: £/(v¿)=0, £„(v,)=ao, Vv; eF. Каждый эксцентриситет e(í,-) вершин множества S позволяет уточнить значения этих границ по формулам E/(v,) = max{e;(v,), e(si)-m(vi,s¡), m(ví,5,)},Eu(v;) = min{su(v/), е(s¡) +m(v¡,s¡)}

Из рассмотрения исключаются вершины v¡, значения нижней и верхней границ эксцентриситета которых не входят в отрезок, ограниченный текущими оценками диаметра d¡ и du. Также исключаются из рассмотрения вершины с вычисленным эксцентриситетом - вершины, у которых нижняя и верхняя границы эксцентриситета равны. Формально правила исключения вершин описываются следующими формулами £i(v¡)>du/2 v Eu(v¡)<d¡,b¡(v¡) = eu(v¡).

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

После нахождения всех опорных вершин создается t множеств-кластеров С,,С2,...,С,-по числу найденных опорных вершин. Первыми в кластеры добавляются найденные опорные вершины. Каждая из оставшихся вершин присоединяется к тому кластеру, чья опорная вершина находится ближе, чем опорные вершины остальных кластеров.

На основе алгоритмов определения метрических характеристик графа решается задача аппроксимации нагруженного графа большой размерности графом меньшей размерности (декомпозиции графа) с целью минимизации разностей расстояний между вершинами исходного графа и соответствующими им вершинами полученного малого графа. Рассматривается простой связный неориентированный нагруженный граф G={VJ¡,U), где мощность множества вершин | V\=n. Задачи аппроксимации состоят в сопоставлении исходному графу G аппроксимирующего графа Ga=(VaJia,Ua) меньшей размерности: па, где 1 < па < п. Будем называть вершины аппроксимирующего графа метавершина-

ми и обозначать vf. Метавершины могут быть подмножеством исходного множества вершин или не содержаться в V. Вес ребра между метавершинами vf и Vj графа Ga будем обозначать ua(v¡,vj), расстояние между этими же метавершинами ma(y¡,Vj). Обозначим v^ метавершину графа Ga, аппроксимирующую вершину v, графа G.

Погрешностью аппроксимации будем называть величину

Ае = maxjm(v;,vmo(vc(0,vcU)]j.

Рассмотрим две задачи аппроксимации: 1) уменьшение размерности Оа так, чтобы Ае не превосходила заданной величины; 2) уменьшение Ае при заданной размерности Са. Обе задачи являются ЛТ-трудными. При некоторых допущениях они могут быть сформулированы в терминах задачи разбиения графа.

Будем аппроксимировать вершины подмножеств разбиения V, центрами этих подмножеств. Веса ребер в графе йа между этими центрами будем полагать равными расстояниям между центрами в исходном графе О, Дополнительно будем требовать связность всех подграфов разбиения в,{Уд- При выполнении всех этих условий для погрешности аппроксимации справедливо с/тах/2 < Ае < Гщ +гтг . Здесь <1тях - максимальный диаметр, гщ - максимальный, а г„2 - второй по величине радиусы множеств разбиения. При такой

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

Задача 1. Дан простой связный неориентированный нагруженный граф 0—(У^,Ц) с неотрицательной вещественной весовой функцией на ребрах и: Е —> [0,оо) и вещественное число ешах>0. Найти разбиение множества вершин графа на попарно непересекающиеся подмножества {РьКг,.такое, что все подграфы б^Р}), порожденные этими множествами, связны, гщ +гт2 <етах и

ишп.

Задача 2. Отличается от задачи 1 тем, что вместо етах задано число к 0<к<п и гщ + гт2 ->• тш.

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

Удаление вершины V,- влечет необходимость изменения весов ребер только между смежными с ней вершинами После пересчета весов погрешность аппроксимации между всеми неудаленными вершинами останется нулевой. Поэтому для минимизации общей погрешности аппроксимации надо поставить в соответствие удаленной вершине V,- такую метавершину у^, для которой тах|т(у,-,уу)-т(ус(,-),уу]|-^1гш1. В качестве ус(Г) будем выбирать ближайшую

смежную с v¡ вершину, тогда погрешность аппроксимации увеличится не более чем на вес ребра между вершинами.

В задаче 1 требуется, чтобы погрешность аппроксимации не превосходила некоторого заданного числа. Для достижения этого необходимо хранить информацию о погрешности А1е, вносимой каждой из оставшихся вершин V/. Удаление вершины V,- изменяет погрешность аппроксимирующей ее вершины у^о по правилу А^ = + А'е +и(у,-,ус^). В силу сохранения расстояний между оставшимися вершинами, для выполнения Ае < етах необходимо, чтобы

л/ <етах /2,У/. Согласно этому, вершину V,- можно удалять, когда для аппроксимирующей ее вершины ус(|) выполняется А^ + А'е + u{v¡,vc^)< егоах/2.

Полученная таким образом аппроксимация не гарантирует связности подграфов сДКу): Ку = {у,- е V | с(;') = _/'} исходного графа, вершины которых аппроксимируются одной метавершиной. В диссертации предложено правило переопределения функции с, которое позволяет гарантировать связность подграфов, не увеличив при этом погрешность аппроксимации. В худшем случае, для полного графа при «удалении» и—2 вершин, сложность алгоритма составляет

Для решения задачи 2 предлагается алгоритм (рис. 2) на основе предыдущего: итеративно ищется такое значение величины етзх, при котором решение задачи 1 позволит получить аппроксимирующий граф с числом вершин Уа\ < к, где к - ограничение из задачи 2. Для поиска такого етах используется предположение о зависимости етах = /(¡^¡) и метод последовательных приближений.

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

Рисунок 2. Блок-схема алгоритма решения задачи 2

Глава 4 посвящена проведению вычислительных экспериментов для оценки эффективности разработанных алгоритмов поиска кратчайших путей, нахождения метрических характеристик и аппроксимации графов. В качестве тестовых данных используется несколько наборов графов: графы дорожных сетей крупнейших городов России и других стран, сгенерированные полные графы со случайными весами ребер. Разработанный алгоритм поиска кратчайших путей графа («разборки-сборки графа», PC«) сравнивается с различными реализациями эффективного на практике алгоритма Дейкстры из библиотеки Boost Graph Library, обладающими кубической сложностью. В качестве очереди с приоритетом в алгоритме Дейкстры используются: д-кучи (д=2,3,4, Д2-Д4), ре-лакс-куча (ДИ.) и фибоначчиева куча (ДФ). Проведенные эксперименты демонстрируют преимущество разработанного алгоритма в скорости решения в 3-10 раз по сравнению с Д2-Д4, что изображено на рис. 3.

Рисунок 3. Сравнительная характеристика времени определения расстояний в

транспортных сетях

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

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

Разработанный алгоритм аппроксимации графа (А2) сравнивается с аппроксимацией, получаемой ¿-разбиением графа. Анализ результатов вычислительных экспериментов показал, что погрешностью аппроксимации не превос-

11?тер6\рг

I " — ДФТСп

-—-¿г-Москва -"-дитсп

' ~ " у -ш-ДЗ/PCn

—Д1РСП

30%.

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

Среднее число транспортных узлов, пгг.

Рисунок 4. Среднее число решений задачи об оптимальных путях при определении радиуса транспортной сети

Ксхотаи дднпью

Знхо.тякс данзь»

Рисунок 5. Структура разработанного программного обеспечения

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

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

Груши графов Число вершин гранспортной сети Уменьшение графа сети в 10 раз Уменьшение графа сета в 10г раз Сокращение стоимости транспортньи перевозок

степень вершин Относительная погрешность Ср. квадр. отио с ягельной погрешности Относительная погрешность Ср. квадр. относительной погрешности

1 ~Ю5 2,16 0,013 0,004 0,218 0,069 15%

■> К1СР 2.61 0,026 0.007 0,407 0,093 9%

3 ~2Т05 2,2 0,011 0.007 0,182 0,098 18%

4 ~2-103 2.6 0,018 0,004 0,284 0,061 13%

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ И ВЫВОДЫ

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

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

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

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

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

СПИСОК ПУБЛИКАЦИЙ ПО ТЕМЕ ДИССЕРТАЦИИ

В рецензируемых журналах из списка ВАК

1. Разбиение графа с минимизацией средних перемещений / А. Р. Ураков, Т. В. Тимеряев // Научно-технические ведомости СПбГТТУ. Информатика. Телекоммуникации. Управление. 2011. № 5 (133). С. 96-99.

2. Многоуровпевый алгоритм разбиения графов по критерию средней длины / А. Р. Ураков, Т. В. Тимеряев // Информационные технологии. 2012. № 4. С. 22-25.

3. Использование особенностей взвешенных графов для более быстрого определения их характеристик / А. Р. Ураков, Т. В. Тимеряев // Прикладная дискретная математика. 2012. № 2 (16). С. 95-99.

4. Быстрый поиск характеристик взвешенного графа по матрице кратчайших расстояний / А. Р. Ураков, А. А. Михташок, Т. В. Тимеряев // Вестник УГАТУ. 2012. Т. 15, №6 (51). С. 164-166.

5. Оценка достоверности и аппроксимация информации, представленной взвешенным графом / В. П. Житников, А. Р. Ураков, Т. В. Тимеряев // Вестник УГАТУ. 2013. Т. 17, № 2 (55). С. 50-52.

6. Алгоритм поиска кратчайших путей для разреженных графов большой размерности / А. Р. Ураков, Т. В. Тимеряев // Прикладная дискретная математика. 2013. №1 (19). С. 84-92.

7. Алгоритмы быстрого поиска для двух задач о метрических характеристиках взвешенных графов / А. Р. Ураков, Т. В. Тимеряев // Управление большими системами. 2013. Вып. 42. С.153-172.

8. О двух задачах аппроксимации взвешенных графов и алгоритмах их решения / А. Р. Ураков, Т. В. Тимеряев // Прикладная дискретная математика. 2013. №3(21). С. 86-92.

Свидетельство о государственной регистрации программы для ЭВМ:

9. Св-во гос. рег. прогр. для ЭВМ №2013660815 (20.11.13). Программа выборки подграфов с заданными характеристиками. / Т. В. Тимеряев. № 2013660815. Заявл. 01.10.2013.

В других изданиях

10. Сбор информации и автоматизация построения графов для задач на макроуровне / Т. В. Тимеряев // XXXVI Гагаринские чтения: науч. тр. Межд. молодежи, науч. копф. (Москва, 6-10 апреля 2010). М.: МАТИ, 2010. Т. 5. С. 151-153.

11. Точные алгоритмы быстрого поиска метрических характеристик графов дорожных сетей / А. Р. Ураков, Т. В. Тимеряев // Проблемы оптимизации и экономические приложения: матер. V Всерос. конф. (Омск, 2-6 июля 2012). Омск: Изд-во Омск. гос. ун-та, 2012. С. 214.

12.06 особенностях одного типа взвешенных графов и их использовании для эффективного решения задач / Т. В. Тимеряев // Мавлютовские чтения: Всерос. молодежи, научн. конф. (Уфа, 7-9 ноября 2012): сб. тр. Уфа: УГАТУ,

2012. Т. 5(4. 1). С. 73-74.

13.Алгоритм разборки и сборки для поиска кратчайших путей графа / Т. В. Тимеряев // Актуальные проблемы науки и техники: сб. тр. 8-й Всерос. зимн. шк.-сем. аспир. и молод, уч. (Уфа, 19-20 февраля 2013). Уфа: УГАТУ,

2013. Т. 3. С. 295-298.

14. Алгоритм поиска кратчайших путей между всеми парами вершин разреженных графов большой размерности (статья на англ. яз.)/ А. Р. Ураков, Т. В. Тимеряев // Computer Science and Information Technology. Horizon Research Publishing. USA, 2013. Vol. 1 (3). P. 233-237.

15.Быстрый поиск кратчайших путей разреженных графов / Т. В. Тимеряев // Информационные технологии интеллектуальной поддержки принятия решений: тр. Междунар. конф. (Уфа, 21-25 мая 2013). Уфа: УГАТУ, 2013. Т. 2. С. 201-203.

16.Оперативное определение оптимальных путей транспортных сетей (статья на англ. яз.) / Т. В. Тимеряев, H. М. Шерьгхалина. // Proceedings of 16-th Workshop on Computer Science and Information Technologies (CSIT'2014). (Sheffield, September 17-22, 2014). Vol. 2. P. 102-106.

17. Определение оптимальных путей транспортной сети на базе графовой декомпозиции / Т. В. Тимеряев, H. М. Шерыхалина // Proceedings of the 2nd International Conference "Intelligent Technologies for Information Processing and Management" (Ufa, Russia, November 10-12, 2014). Vol. 2. P. 71-75.

18.Задачи аппроксимации и разбиения графов / Т. В. Тимеряев, Н.М. Шерыхалина // Актуальные проблемы науки и техники: сб. тр. 9-й Всерос. зимн. шк.-сем. аспир. и молод, уч. (Уфа, 25-27 февраля 2014). Уфа: УГАТУ, 2014. Т. 2. С. 337-339.

Диссертант

Т. В. Тимеряев

ТИМЕРЯЕВ Тимофей Валерьевич

МЕТОДЫ И АЛГОРИТМЫ УПРАВЛЕНИЯ МАРШРУТИЗАЦИЕЙ В ТРАНСПОРТНЫХ СЕТЯХ НА ОСНОВЕ ОПЕРАТИВНОЙ ОБРАБОТКИ ИНФОРМАЦИИ В РАЗРЕЖЕННЫХ ГРАФАХ

Специальность: 05.13.01 - Системный анализ, управление и обработка информации (в промышленности)

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

Подписано в печать 03.04.2015 Формат 60x84 1/16. Бумага офсетная. Печать плоская. Гарнитура Тайме. Усл. печ. л. 1,0. Уч.-изд. л. 0,9. Тираж 100 экз. Заказ № 222.

ФБГОУ ВПО «Уфимский государственный авиационный технический университет» Центр оперативной полиграфии 450000, Уфа-центр, ул. К. Маркса, 12