Опис документа

Морозов А. В. Вдосконалення методів оптимізації кільцевих маршрутів на транспортній мережі. - Рукопис. Дисертація на здобуття наукового ступеня кандидата технічних наук за спеціаль- ністю 01.05.02 - математичне моделювання та обчислювальні методи.- Харківсь- кий національний університет радіоелектроніки, Харків, 2010. У дисертаційній роботі сформульовано нові прикладні задачі оптимізації замкне- них маршрутів - гамільтонову задачу про сільського листоношу (ГЗСЛ) та кільцеву задачу про сільського листоношу (КЗСЛ). Запропоновано двоетапний метод типу гілок та меж, який знаходить оптимальний розв'язок ГСЗЛ чи КЗСЛ, або встановлює факт нерозв'язності задачі. Перший етап методу включає перевірку достатніх умов нерозв'язності задачі та процедуру вершинно-реберного перетворення, яка приводить до одного з трьох можливих результатів: побудовано оптимальний кільцевий маршрут; задача не має розв'яз- ку; пошук потрібно продовжити на перетвореному графі зі степенями вершин, більшими за 2, і з множиною фіксованих ребер, яка утворює паросполу-чення. Це дає можливість скоротити час знаходження розв'язку на другому етапі методу за допомогою запропонованих модифікацій методу Літтла. Розроблено програмний продукт, проведено обчислювальний експеримент та проаналізовано отримані дані. Ключові слова: задача про сільського листоношу, задача комівояжера, гамільтонів цикл, транспортна мережа, метод гілок та меж, вершинно-реберне перетворення. Морозов А. В. Совершенствование методов оптимизации кольцевых маршрутов на транспортной сети. - Рукопись. Диссертация на соискание ученой степени кандидата технических наук по специальности 01.05.02 - математическое моделирование и вычислительные методы. - Харьковский национальный университет радиоэлектроники, Харьков, 2010. Главной целью диссертационной работы является разработка методов решения двух задач построения кратчайших замкнутых маршрутов на транспортной сети: гамильтоновой задачи о сельском почтальоне (ГЗСП) и кольцевой задачи о сельском почтальоне (КЗСП). ГЗСП состоит в поиске гамильтонова цикла мини- мальной стоимости, содержащего фиксированное подмножество рёбер R связ- ного взвешенного графа. В отличие от ГЗСП, в КЗСП требуется найти простой цикл с такими же свойствами. ГЗСП и КЗСП NP-полны и не всегда разрешимы. Поэтому для них применимы только точные методы, среди которых наименее трудоёмким является метод ветвей и границ. В работе выдвинуты требования к методу ветвей и границ, обеспечивающие практическое применение решений поставленных задач. Для решения ГЗСП и КЗСП получила дальнейшее развитие двухстадийная схема границ и ветвлений, корректно строящая кратчайший кольцевой маршрут, если он существует, или устанавливающая, что задача не имеет решения. На первой стадии, исходя из структурных свойств графа транспортной сети и условий, определяющих множество допустимых маршрутов, за полиномиальное время выполняется проверка всех известных достаточных условий неразрешимости задачи. Проверка включает процедуру вершинно-реберного преобразования (ВРП) исходного графа ГЗСП или КЗСП, которая выдает один из трех возможных результатов: построено оптимальное решение; задача не имеет решения; поиск оптимума следует продолжить на преобразованном графе со степенями вершин, большими 2, и с подмножеством фиксированных рёбер, образующих паросочета- ние. Сложность вершинно-реберного преобразования оценивается величиной 0( |V2| ). Вторая стадия метода предполагает решение задачи методом ветвей и границ. Разработана модификация классического метода ветвей и границ (метода Литтла) для поиска решения ГЗСП на графе, полученном в результате вершинно-реберного преобразования исходного графа. В ней впервые применён способ разбиения множества всех решений на непересекающиеся подмножества с помощью двух правил ветвления, развивающих бинарное дерево перебора. Модификация без каких либо изменений применима для поиска решения гамиль- тоновой задачи коммивояжера (ГЗК). Для разреженных графов использование модификации позволяет достичь выигрыша в скорости решения гамильтоновой задачи коммивояжера по сравнению с классическим методом Литтла приблизи- теьльно в 1,6 раз. Для решения КЗСП предложен теоретически обоснованный метод нахождения кратчайшего маршрута, развивающий алгоритм Литтла. Главная особенность КЗСП, значительно усложняющая поиск её решения, заключается в неопреде- лённом заранее подмножестве вершин графа, по которым пройдёт искомый цикл. Простой цикл минимальной стоимости следует искать в компоненте связности исходного графа, включающей совокупность вешинно-непересекаю- щихся путей из фиксированных рёбер, не содержащих мостов и точек сочлене- ния. Для нахождения точек сочленения и мостов используется модификация поиска в глубину, имеющая сложность 0( IVI+IUI ). В основу метода положен алгоритм Литтла в комбинации с механизмом последовательного сужения области всех простых циклов. Чтобы исключить потерю оптимального решения КЗСП, для каждой вершины ветвления дерева перебора с помощью модифицированного алгоритма Флойда-Уоршелла вычис- ляются матрица кратчайших путей и матрица маршрутизации, определяющие все вершины и ребра графа, из которых может быть построен искомый цикл. В предложенном методе впервые выполнен способ разбиения множества решений КЗСП на непересекающиеся подмножества с применением трех правил ветвле- ния и вычислением соответствующих им нижних оценок стоимости оптимального решения. Разработанный метод без каких-либо изменений корректно выполняет поиск оптимального решения ГЗСП, замкнутой и незамкнутой задач коммивоя- жера, а также гамильтоновой задачи коммивояжера - задачи нахождения в неполном взвешенном графе кратчайшего гамильтонова цикла. Предложенные методы реализованы в виде программного продукта, который позволяет: случайным образом генерировать наборы входных данных; сохранять и загружать данные и результаты в базе данных и xml-файлах; определять точное решение гамильтоновой задачи коммивояжера при помощи классического метода Литтла; выполнять процедуру вершинно-рёберного преобразования и проверять достаточные условия неразрешимости ГЗСП и КЗСП; находить точное решение ГЗСП для заданной матрицы стоимостей и заданною множества рёбер R; определять точное решение КЗСП для исходной матрицы стоимостей и заданного множества рёбер R; выполнять поиск решения ГЗСП и КЗСП с использованием многопроцессорных систем; генерировать детализированный отчет о процессе решения задачи и экспортировать его в текстовые или html- файлы; проводить вычислительный эксперимент. Проведён вычислительный эксперимент. Его результаты показывают, что время решения ГЗСП и КЗСП зависит как от размерности задачи, так и от количества обязательных для посещения рёбер. При фиксированном значении |R| с ростом размерности задачи время решения возрастает, а при фиксированной размер- ности задачи, с ростом количества фиксированных рёбер, время работы решения ГЗСП уменьшается, а КЗСП - возрастает. Использование параллельных версий предложенных методов позволяет значительно сократить время решения как той, так и другой задачи. Ключевые слова: задача о сельском почтальоне, задача коммивояжера, гамильтонов цикл, транспортная сеть, метод ветвей и границ, вершинно-рёберное преобразование. Morozov A. V. Improvement of methods of circular route optimization in transport network. - Manuscript. Dissertation for Technical Science Candidate Degree in specialty 01.05.02 -mathematical modeling and calculating methods. - Kharkiv National University of Radio Electronics, Kharkiv, 2010. The dissertation research outlines new applied tasks of optimization of closed-circuit route - the Hamilton Rural Postman Problem (HRPP) and the Circular Rural Postman Problem (CRPP). A two-stage exact branch and bound method, which finds an optimal solving of HRPP or CRPP, or states the fact of the task to be impossible for solution is offered. The first stage of the method includes the checking of sufficient conditions for the task not to be solved and the procedure of vertex-edge transformation which leads to either of three possible results: an optimal solution has been reached; the task has no possible solution or the search should be continued on a converted graph with a vertex's degree greater than two and with a set of fixed edges that forms matching. The second stage is qualified to make a research of solution on the basis of the branch-and-bound method which are offered in the dissertation. Keywords: Rural Postman Problem, Travelling Salesman Problem, Hamilton loop, transport network, branch-and-bound method, vertex-edge transformation.