Размещено на http://www.allbest.ru/

Харківський національний університет радіоелектроніки

УДК 519.161

01.05.02 - математичне моделювання та обчислювальні методи

Автореферат

дисертації на здобуття наукового ступеня

кандидата технічних наук

Вдосконалення методів оптимізації кільцевих маршрутів на транспортній мережі

Морозов Андрій Васильович

Харків - 2010

Дисертацією є рукопис.

Робота виконана в Житомирському державному технологічному університеті Міністерства освіти і науки України.

Науковий керівник доктор технічних наук, професор Панішев Анатолій Васильович, Житомирський державний технологічний університет, завідувач кафедри програмного забезпечення обчислювальної техніки.

Офіційні опоненти:

- доктор фізико-математичних наук, професор Ємець Олег Олексійович, вищий навчальний заклад УКООП спілки "Полтавський університет економіки і торгівлі", завідувач кафедри математичного моделювання та соціальної інформатики;

- доктор технічних наук, професор Гребеннік Ігор Валерійович, Харківський національний університет радіоелектроніки, професор кафедри системотехніки.

Захист відбудеться "11" січня 2011 р. о 14.30 на засіданні спеціалізованої вченої ради Д 64.052.02 у Харківському національному університеті радіоелектроніки за адресою: 61166, м. Харків, пр. Леніна, 14.

З дисертацією можна ознайомитись у бібліотеці Харківського національного університету радіоелектроніки за адресою: 61166, м. Харків, пр. Леніна, 14.

Автореферат розісланий "9" грудня 2010 р.

Вчений секретар спеціалізованої вченої ради В.В. Безкоровайний

Анотації

Морозов А.В. Вдосконалення методів оптимізації кільцевих маршрутів на транспортній мережі. - Рукопис.

Дисертація на здобуття наукового ступеня кандидата технічних наук за спеціальністю 01.05.02 - математичне моделювання та обчислювальні методи. - Харківський національний університет радіоелектроніки, Харків, 2010.

У дисертаційній роботі сформульовано нові прикладні задачі оптимізації замкнених маршрутів - гамільтонову задачу про сільського листоношу (ГЗСЛ) та кільцеву задачу про сільського листоношу (КЗСЛ).

Запропоновано двоетапний метод типу гілок та меж, який знаходить оптимальний розв'язок ГСЗЛ чи КЗСЛ, або встановлює факт нерозв'язності задачі. Перший етап методу включає перевірку достатніх умов нерозв'язності задачі та процедуру вершинно-реберного перетворення, яка приводить до одного з трьох можливих результатів: побудовано оптимальний кільцевий маршрут; задача не має розв'язку; пошук потрібно продовжити на перетвореному графі зі степенями вершин, більшими за 2, і з множиною фіксованих ребер, яка утворює паросполучення. Це дає можливість скоротити час знаходження розв'язку на другому етапі методу за допомогою запропонованих модифікацій методу Літтла.

Розроблено програмний продукт, проведено обчислювальний експеримент та проаналізовано отримані дані.

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

Морозов А.В. Совершенствование методов оптимизации кольцевых маршрутов на транспортной сети. - Рукопись.

Диссертация на соискание ученой степени кандидата технических наук по специальности 01.05.02 - математическое моделирование и вычислительные методы. - Харьковский национальный университет радиоэлектроники, Харьков, 2010.

Главной целью диссертационной работы является разработка методов решения двух задач построения кратчайших замкнутых маршрутов на транспортной сети: гамильтоновой задачи о сельском почтальоне (ГЗСП) и кольцевой задачи о сельском почтальоне (КЗСП). ГЗСП состоит в поиске гамильтонова цикла минимальной стоимости, содержащего фиксированное подмножество рёбер R связного взвешенного графа. В отличие от ГЗСП, в КЗСП требуется найти простой цикл с такими же свойствами.

ГЗСП и КЗСП NP-полны и не всегда разрешимы. Поэтому для них применимы только точные методы, среди которых наименее трудоёмким является метод ветвей и границ. В работе выдвинуты требования к методу ветвей и границ, обеспечивающие практическое применение решений поставленных задач.

Для решения ГЗСП и КЗСП получила дальнейшее развитие двухстадийная схема границ и ветвлений, корректно строящая кратчайший кольцевой маршрут, если он существует, или устанавливающая, что задача не имеет решения. На первой стадии, исходя из структурных свойств графа транспортной сети и условий, определяющих множество допустимых маршрутов, за полиномиальное время выполняется проверка всех известных достаточных условий неразрешимости задачи. Проверка включает процедуру вершинно-реберного преобразования (ВРП) исходного графа ГЗСП или КЗСП, которая выдает один из трех возможных результатов: построено оптимальное решение; задача не имеет решения; поиск оптимума следует продолжить на преобразованном графе со степенями вершин, большими 2, и с подмножеством фиксированных рёбер, образующих паросочетание. Сложность ВРП оценивается величиной . Вторая стадия метода предполагает решение задачи методом ветвей и границ.

Разработана модификация классического метода ветвей и границ (метода Литтла) для поиска решения ГЗСП на графе, полученном в результате ВРП исходного графа. В ней впервые применён способ разбиения множества всех решений на непересекающиеся подмножества с помощью двух правил ветвления, развивающих бинарное дерево перебора. Модификация без каких либо изменений применима для поиска решения гамильтоновой задачи коммивояжера (ГЗК). Для разреженных графов использование модификации позволяет достичь выигрыша в скорости решения ГЗК по сравнению с классическим методом Литтла приблизительно в 1,6 раз.

Для решения КЗСП предложен теоретически обоснованный метод нахождения кратчайшего маршрута, развивающий алгоритм Литтла. Главная особенность КЗСП, значительно усложняющая поиск её решения, заключается в неопределённом заранее подмножестве вершин графа, по которым пройдёт искомый цикл. Простой цикл минимальной стоимости следует искать в компоненте связности исходного графа, включающей совокупность вершинно-непе-ресекающихся путей из фиксированных рёбер, не содержащих мостов и точек сочленения. Для нахождения точек сочленения и мостов используется модификация поиска в глубину, имеющая сложность .

В основу метода положен алгоритм Литтла в комбинации с механизмом последовательного сужения области всех простых циклов. Чтобы исключить потерю оптимального решения КЗСП, для каждой вершины ветвления дерева перебора с помощью модифицированного алгоритма Флойда-Уоршелла вычисляются матрица кратчайших путей и матрица маршрутизации, определяющие все вершины и ребра графа, из которых может быть построен искомый цикл. В предложенном методе впервые выполнен способ разбиения множества решений КЗСП на непересекающиеся подмножества с применением трех правил ветвления и вычислением соответствующих им нижних оценок стоимости оптимального решения. Разработанный метод без каких-либо изменений корректно выполняет поиск оптимального решения ГЗСП, замкнутой и незамкнутой задач коммивояжера, а также ГЗК ? задачи нахождения в неполном взвешенном графе кратчайшего гамильтонова цикла.

Предложенные методы реализованы в виде программного продукта, который позволяет: случайным образом генерировать наборы входных данных; сохранять и загружать данные и результаты в базе данных и 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.

Загальна характеристика роботи

Актуальність теми. Суттєві зміни, які відбуваються в економічному механізмі країни, гостро ставлять питання підвищення ефективності управління перевезеннями пасажирів та вантажів. Зниження вартості транспортних робіт і прискорення їх виконання потребує не тільки модернізації рухомого складу і застосування сучасних інформаційних технологій, але і впровадження результатів розв'язання оптимізаційних задач маршрутизації. Задачі оптимального вибору замкнених маршрутів, які виникають у реальних умовах управління транспортними потоками мають комбінаторний характер, розширюючи межі застосування проблеми комівояжера, яка залишається актуальною. Одна з практично важливих задач проблеми, відома як задача про сільського листоношу (ЗСЛ), полягає у побудові найкоротшого замкненого маршруту, який містить певну частину автомобільно-дорожньої мережі. Формально в ЗСЛ потрібно знайти у зв'язному зваженому графі цикл, що має мінімальну вартість і містить задану підмножину ребер.

Дисертаційна робота присвячена дослідженню алгоритмічних властивостей і розробці на їх основі методів розв'язання двох нових версій ЗСЛ. В одній з них потрібно, щоб шуканий цикл був гамільтоновим, а в іншій розв'язком є найкоротший простий цикл. Обидві задачі є NP-повними і не завжди мають розв'язок. Точні методи їх розв'язання потребують значних обчислювальних ресурсів. Потреби в обчислювальних ресурсах та часові витрати на пошук точних розв'язків можуть бути зменшені шляхом вдосконалення існуючих та розробки нових перебірних методів та їх реалізації на багатопроцесорних системах.

Зв'язок роботи з науковими програмами, планами, темами. Робота проводилася відповідно до тематики та загального плану науково-дослідних робіт кафедри інформатики та комп'ютерного моделювання Житомирського державного технологічного університету, у рамках держбюджетної теми № 0106U008579 "Розробка і вдосконалення методів теорії розкладів і дослідження транспортних операцій на основі сучасних комп'ютерних технологій" (2006 - 2008 рр. виконання), в якій здобувач брав участь як виконавець. Автор був розробником математичних моделей, точних методів розв'язання комбінаторних задач та програмних реалізацій методів.

Мета і завдання дослідження. Метою роботи є побудова математичних моделей для розв'язання нових задач оптимізації кільцевих маршрутів на транспортній мережі, що підвищить ефективність транспортних перевезень пасажирів та вантажів. Для досягнення поставленої мети у роботі вирішуються такі завдання:

- дослідження сучасних досягнень у розв'язанні відомих задач побудови найкоротших кільцевих маршрутів;

- розробка математичних моделей двох нових варіантів ЗСЛ, які розширюють область її застосування;

- побудова модифікацій класичного методу Літтла для розв'язання сформульованих задач;

- програмна реалізація запропонованих методів з можливістю їх виконання на багатопроцесорних системах та обчислювальних кластерах;

- виконання обчислювального експерименту та аналіз його результатів.

Об'єкт дослідження - замкнені процеси, які забезпечують ефективне функціонування транспортних засобів та мереж.

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

Методи дослідження. У дисертаційній роботі використовуються результати теорії графів для знаходження найкоротших шляхів, точок зчленування та мостів; теорія паросполучень для визначення випадків нерозв'язності задач; елементи теорії складності комбінаторних задач - для оцінювання трудомісткості алгоритмічних процедур; математичні методи дослідження операції - для аналізу існуючих та розробки нових методів розв'язання NP-повних задач.

Наукова новизна результатів дисертаційної роботи полягає у такому:

1. Вперше розроблено математичні моделі для розв'язання ГЗСЛ та КЗСЛ ? гамільтонової та кільцевої задач про сільського листоношу, які розширюють клас задач про листоношу.

2. Набув подальшого розвитку двоетапний точний перебірний метод типу гілок та меж, який знаходить оптимальний розв'язок ГСЗЛ чи КЗСЛ, або встановлює факт нерозв'язності задачі; перший етап методу включає перевірку достатніх умов нерозв'язності задачі та процедуру вершинно-реберного перетворення, яка приводить до одного з трьох можливих результатів: побудовано оптимальний розв'язок; задача не має розв'язку; пошук оптимального розв'язку потрібно продовжити на перетвореному графі зі степенями вершин, більшими 2, що дає можливість скоротити час пошуку точного розв'язку задачі.

3. Модифіковано класичний метод Літтла; запропоновані два правила розгалуження та спосіб пошуку нижньої оцінки дають можливість застосовувати метод для розв'язання ГЗСЛ та гамільтонової задачі комівояжера.

4. Вперше запропоновано метод розв'язання КЗСЛ, який розвиває класичний метод Літтла. Для розбиття множини розв'язків на підмножини застосовано три правила розгалуження і отримано нижні оцінки вартості оптимального розв'язку, що дає можливість застосовувати метод для розв'язання КЗСЛ та інших задач маршрутизації.

Практичне значення отриманих результатів. Розроблені математичні моделі задач і методи їх розв'язання спрямовані на економічно обґрунтований пошук кільцевих маршрутів. Вони можуть бути використані для ефективної організації транспортного процесу в оперативному управлінні пасажирськими та вантажними перевезеннями. Оптимізація кільцевих маршрутів дозволяє зменшувати витрати на пальне та часові витрати при виконанні транспортних перевезень, доставці кореспонденції, прибиранні, патрулюванні вулиць району та виконанні інших кур'єрських завдань.

Створена здобувачем програмна система дозволяє розв'язувати прикладні задачі управління транспортними перевезеннями пасажирів і вантажів у реальному масштабі часу. Запропоновані методи та їх програмна реалізація впроваджені на ЗАТ "Агротонпром" та Броварській експериментально-виробничій базі ВАТ УкрНДІПСК ім. В.М. Шимановського.

Результати досліджень використовуються у навчальному процесі за напрямком "Програмна інженерія" при викладанні дисциплін "Математичні методи дослідження операцій", "Дискретна математика", "Алгоритми і структури даних", у лабораторному практикумі, при курсовому і дипломному проектуванні. замкнений маршрут межа оптимізація

Особистий внесок здобувача. Основні результати досліджень опубліковано у роботах [1?14]. У роботах, які опубліковані в співавторстві, здобувачеві належить: у [1] ? точний двоетапний метод розв'язання гамільтонової задачі комівояжера, який має менші потреби в обчислювальних ресурсах, ніж відомі методи; у [2] ? результати обчислювального експерименту, показано, що на матрицях спеціального виду запропоновані методи перевершують існуючі; у [4] ? алгоритм вершинно-реберного перетворення, який виконується на першому етапі розв'язання ГЗСЛ і дає можливість скоротити час пошуку оптимального розв'язку; у [5] ? математична модель КЗСЛ, яка є новою прикладною задачею класу задач про листоношу, і запропоновано модифікацію методу Літтла для її розв'язання; у [6] ? метод гілок та меж, який включає два способи розгалуження і може бути застосований для розв'язання ГЗСЛ; у [7] ? наближений метод розв'язання симетричної задачі комівояжера; у [8] ? новий спосіб обчислення нижньої оцінки вартості обходів для загальної задачі комівояжера, що дозволяє прискорити процес розв'язання задачі; у [9] ? модифікація методу Літтла для розв'язання загальної задачі комівояжера, яка дозволяє зменшити потреби в обчислювальних ресурсах; у [10] - формулювання і аналіз алгоритмічних властивостей КЗСЛ; у [11] - загальний двоетапний підхід до розв'язання КЗСЛ, який суттєво скорочує перебір варіантів у методі гілок та меж; у [13] - задача оперативного управління транспортним процесом, яка є новою прикладною задачею; у [14] - класифікація ключових задач пошуку замкнених маршрутів на транспортній мережі, яка дає можливість виділити задачі зі схожими алгоритмічними властивостями.

Апробація результатів дисертації. Основні результати дисертаційної роботи доповідалися та обговорювалися на 2-й Міжнародній науковій конференції "Современные информационные системы. Проблемы и тенденции развития" (Харків-Туапсе, 2007 р.); 9-й, 10-й, 11-й Міжнародних науково-практичних конференціях "Штучний інтелект-2008, 2009, 2010. Інтелектуальні системи" (с. Кацівелі, 2008 р., 2010 р.; с. Дивноморське, Росія, 2009 р.); 17-й, 18-й Міжнародних науково-технічних конференціях "Прикладные задачи математики и механики", (Севастополь, 2009 р., 2010 р.); Міждержавній науково-методичній конференції "Проблеми математичного моделювання", (Дніпродзержинськ, 2009 р.); Всеукраїнській науково-практичній конференції "Інформатика та системні науки", (Полтава, 2010 р.); 11-й Міжнародній науково-практичній конференції "Современные информационные и электронные технологии", (Одеса, 2010 р.); 35-й науково-практичній міжвузівській конференції, присвяченій Дню Житомирського державного технологічного університету, (Житомир, 2010 р.); Міжнародній науково-технічній конференції "Автоматизация: проблемы, идеи, решения 2010" (Севастополь, 2010 р.); 17-й Міжнародній конференції "Knowledge Dialogue - Solution" (Київ, 2010 р.).

Публікації. За темою дисертації видано 14 друкованих робіт, з яких 5 робіт у наукових журналах та збірниках наукових праць, що увійшли до переліків, затверджених ВАК України, 9 - у матеріалах конференцій.

Структура та обсяг роботи. Дисертація складається зі вступу, чотирьох розділів, висновків, двох додатків. Загальний обсяг роботи складає 154 сторінки, в тому числі 114 сторінок основного тексту, одного додатку на 3 сторінках. Дисертація містить 33 ілюстрації (16 стор.), 9 таблиць (8 стор.), список використаних джерел, що містить 126 найменування на 13 сторінках.

Основний зміст роботи

У вступі обґрунтовано актуальність обраної теми, сформульовано мету та основні завдання дослідження, викладено наукову новизну і практичне значення отриманих результатів, наведено відомості про апробацію і напрямки застосування роботи.

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

Базовою моделлю транспортної мережі міста або району обрано зв'язний граф H = (V, U), де V - множина вершин, |V| = n, U - множина ребер. Вершині , , відповідає перехрестя на карті міста або населений пункт на транспортній мережі регіону. Вершини i та j утворюють ребро {i, j} у графі H, якщо вони представлені сусідніми перехрестями вулиці або населеними пунктами, які безпосередньо зв'язані ділянками дороги. Граф H не містить петель. Кожному ребру приписано вагу що дорівнює відстані між пунктами, - множина невід'ємних дійсних чисел.

Якщо в умовах задачі маршрутизації вказано вартості переміщення і між пунктами i та j, то можливо, що не для всіх пар {i, j}U . У цьому випадку транспортну мережу зручніше представити зваженим орграфом G = (V, E), у якому будь-які дві вершини i та j, {i, j}U, з'єднані парою дуг (i, j) і (j, i). Для ділянки {i, j} дорожнього полотна з одностороннім рухом від i до j (від j до i) можна покласти dji = ? (dij = ?) тобто видалити з E дугу (j, i) (дугу (i, j)). Транспортна мережа, у якій усі пункти зв'язані дорожніми ділянками з одностороннім рухом, моделюється орграфом (V, A), де A - множина дуг, таких, що якщо (i, j) A, то (j, i) A, і якщо (j, i) A, то (i, j) A.

З опису базової моделі транспортної мережі випливають різні постановки важливих практичних задач побудови маршрутів, які задовольняють заданим обмеженням і є оптимальними у розумінні обраного критерію. Одним з обмежень, суттєво ускладнюючим розв'язання цих задач, є вимога замкненості маршрутів, яка висувається у тих випадках, коли транспортний засіб починає і закінчує рух в одному пункті (базі). Інше обмеження полягає у тому, що замкнений маршрут транспортного засобу повинен включати визначені пункти та ділянки транспортної мережі. І, врешті, потрібно, щоб замкнений маршрут проходив кожну вказану ділянку і кожний вказаний пункт рівно один раз.

Замкнений маршрут, який проходить по кожній вказаній ділянці та пункту мережі в точності один раз, а по будь-якому з інших пунктів не більше одного разу, назвемо кільцевим. Будемо вважати оптимальним кільцевим маршрутом той, який має мінімальну вартість (протяжність) серед усіх кільцевих маршрутів мережі.

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

Ключові задачі пошуку замкнених маршрутів представлено на рис. 1.

У другому розділі сформульовано ГЗСЛ і запропоновано метод пошуку її розв'язку.

ГЗСЛ формулюється у такий спосіб. Задано зв'язний зважений граф H = (V, U) з множиною вершин V, |V| = n, і множиною ребер U. Кожному ребру приписано вагу - множина невід'ємних дійсних чисел. Граф H повністю визначається симетричною матрицею вартостей , де якщо і інакше, . На множині U задано непорожню підмножину ребер R. Потрібно знайти у графі H гамільтонів цикл, який містить кожне ребро з R та має мінімальну суму ваг усіх ребер.

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

(1)

Рис. 1. Класифікація основних задач оптимізації замкнених маршрутів на транспортній мережі: ЗЗК - загальна задача комівояжера; ЗКЛ - задача про китайського листоношу; ЗСЛ - задача про сільського листоношу; ГЗСЛ - гамільтонова задача про сільського листоношу; КЗСЛ - кільцева задача про сільського листоношу; ГЗК - гамільтонова задача комівояжера; ЗК - задача комівояжера

ГЗСЛ є NP-повною. Безпосереднє застосування класичного методу гілок та меж (методу Літтла) не дозволяє розв'язувати ГЗСЛ.

Для розв'язання ГЗСЛ пропонується модифікація класичного методу гілок та меж (методу Літтла) ? метод HRPP. Метод забезпечує пошук розв'язків як ГЗСЛ, так і гамільтонової задачі комівояжера (ГЗК).

ГЗК і ГЗСЛ не мають розв'язків, якщо граф містить кінцеві (висячі) вершини. Вони знаходяться тривіальним простим переглядом усіх вершин V за час . Множина вершин зв'язного графа H може містити точки зчленування, а множина ребер U - мости. Зв'язний граф H не є гамільтоновим, якщо містить точки зчленування або мости. Відповідно, ГЗСЛ на графі з точками зчленування або мостами не має розв'язку.

Нехай граф H = (V, U) не має висячих вершин і точок зчленування, а множина його ребер у ГЗСЛ представлена ланцюгами, які не перетинаються по вершинах або ребрах. Виконаємо вершинно-реберне перетворення (ВРП) графа Н, внаслідок якого встановлюються достатні умови нерозв'язності ГЗСЛ. Вони доповнюють перелічені вище умови.

S0. H = (V, U) - граф, який не містить висячих вершин і точок зчленування; непорожня множина ребер утворює сукупність Z ланцюгів, які не перетинаються по вершинах або ребрах.

S1. Якщо кількість ланцюгів сукупності Z дорівнює , то покласти , перейти до кроку S5.

S2. Для кожного ланцюга (a, b, …, c, d) видалити усі ребра з , які а) з'єднують його будь-які дві вершини, б) інцидентні одній вершині з {b,…,c}, і визначити степені усіх вершин множини V. Якщо хоча б одна вершина в отриманому остовному підграфі графа Н є ізольованою або висячою, то ГЗСЛ не має розв'язку.

S3. Замінити кожний ланцюг (a, b, …, c, d) на ребро {a, d}, присвоївши йому вагу, рівну сумі ваг ребер ланцюга.

S4. - граф, побудований після виконання кроку S3, - множина усіх ребер, отриманих з R у результаті побудови .

S5. Покласти .

S6. Якщо граф не містить вершин зі степенем 2, то кінець.

S7. Якщо множина не утворює паросполучення, то кінець: ГЗСЛ не має розв'язку.

S8. Кожний ланцюг зі степенями вершин , замінити на ребро з вагою, рівною сумі ваг її ребер;

видалити з і усі ребра ланцюга, які належать і ;

покласти ;

якщо існує ще одне ребро , видалити його.

S9. Якщо множина не утворює сукупності ланцюгів, які не перетинаються по вершинах або ребрах, то кінець: ГЗСЛ не має розв'язку.

S10. Якщо степені усіх вершин побудованого графа дорівнюють 2, то кінець: ГЗСЛ має розв'язок, інакше

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

виключити з ребра ланцюга, які належать ;

замінити ланцюг на ребро

Якщо існує ще одно ребро, яке з'єднує p та v, видалити його;

встановити ,

;

перейти до кроку S6.

Часова складність ВРП графа H = (V, E) оцінюється величиною

Твердження 1. Якщо результатом ВРП графа Н є граф, у якому множина ребер не утворює паросполучення, то ГЗСЛ не має розв'язку.

Пошук розв'язку ГЗСЛ за допомогою модифікованого методу гілок та меж починається з перетворення матриці вартостей графа Н у приведену матрицю. Вона у загальному випадку не є симетричною.

У приведеній матриці виберемо ті елементи і , для яких і покладемо

, .

Назвемо отриману матрицю повністю приведеною. Подальші дії будуть виконуватися за допомогою цієї матриці.

Кореню дерева перебору поставимо у відповідність повністю приведену матрицю з оцінкою

і визначимо дугу орграфа , яка ініціює розгалуження. Для цього, як і у класичному методі Літтла, кожний елемент (p, q) у , такий, що , оцінимо величиною

. (2)

і знайдемо елемент (p, q) з найбільшим значенням

. (3)

Елементу (p, q) в орграфі відповідає дуга (p, q), яка ініціює розбиття множини всіх обходів на дві підмножини і породжує два випадки: {k, l} і {k, l} .

У випадку {k, l} множина усіх розв'язків задачі розбивається на підмножини і . Перша підмножина включає усі обходи, які містять дугу (k, l), а друга - всі обходи, які не містять цієї дуги.

Матриця, за якою обчислюється нижня границя вартості усіх обходів множини і визначає цю множину, знаходиться так, як і у методі Літтла, при умові, що виконується таке правило.

Якщо множина R містить ребро {x, k}, то в шуканий обхід разом із дугою (k, l) включається дуга (x, k). Аналогічно, якщо множина R містить ребро {y, l}, то до дуги (k, l) приєднується дуга (l, y). Включення дуги (x, k) або (l, y) у підмножину розв'язків означає, що матриця, яка визначає цю підмножину, не містить не тільки рядка k і стовпця l, але й того рядка і стовпця, номери яких є початком та кінцем приєднаної дуги. У випадку {x, k}, {y, l} до дуги (k, l) приєднуються дуги (x, k) і (l, y), а у матриці, яка визначає множину , вилучаються рядки x, k, l і стовпці k, l, y.

Позначимо нижню границю вершини розгалуження . Для дуги (k, l), яка ініціює розгалуження, покладемо

(4)

Тут - елементи матриці, які відповідають границі . У випадку вони є елементами повністю приведеної матриці . Тоді вартість усіх обходів множини обмежена знизу величиною

, (5)

де і - коефіцієнти приведення матриці, якій відповідає границя , у матрицю, яка визначає множину .

Матриця, що визначає множину і границя знаходяться як і у класичному методі Літтла:

.

Розглянемо випадок, де (k, l). Простір розв'язків ГЗСЛ {z(R)} розбивається на дві підмножини {(k, l)} і {(l, k)}. У першу підмножину включаються усі обходи, які містять дугу (k, l), а в другу - дугу (l, k).

Нехай вершині розгалуження відповідає границя і матриця D, що породжує дугу (k, l) або (l, k), {k, l}, з максимальною оцінкою. Матриця, яка визначає підмножину {(k, l)}, знаходиться у результаті вилучення з матриці D рядка k і стовпця l, присвоєння елементу значення і приведення отриманої скороченої матриці. Аналогічно, для знаходження матриці, яка визначає підмножину {(l, k)}, потрібно в матриці D покласти , видалити рядок l і стовпець k і виконати приведення отриманої скороченої матриці. Нижні границі вартості обходів для підмножини {(k, l)} і {(l, k)} обчислюються за формулами:

(6)

(7)

де - коефіцієнти приведення, отримані внаслідок перетворення матриці D.

Можливою є ситуація, коли у матриці D або , або . Із (6) і (7) випливає, що якщо , то {(k, l)}, якщо , то {(l, k)}.

Твердження 2. Метод HRPP дозволяє знайти розв'язок ГЗСЛ або встановити факт нерозв'язності задачі.

У третьому розділі сформульовано КЗСЛ та запропоновано двоетапний підхід для її розв'язання.

КЗСЛ формулюється у такий спосіб. Задано зв'язний зважений граф H = (V, U) з множиною вершин V, , і множиною ребер U. Кожному ребру {i, j}U приписано вагу , , , - множина невід'ємних дійсних чисел. Граф повністю визначається симетричною матрицею вартостей , де , якщо {i, j}U і інакше, , , , . На множині U задано непорожню підмножину ребер .

Потрібно знайти у графі простий цикл, який містить кожне ребро і має мінімальну суму ваг ребер.

У задачі, яка розглядається, на відміну від ЗСЛ шуканий цикл має бути простим.

Нехай - простий цикл графа H, який містить усі ребра заданої множини ребер R. Тоді КЗСЛ полягає у знаходженні простого циклу , мінімізуючого функціонал

(8)

Для розв'язання КЗСЛ пропонується використовувати двоетапний підхід. На першій стадії виконується ефективна перевірка відомих достатніх умов нерозв'язності КЗСЛ. До неї належить процедура ВРП вихідного графа H у граф зі структурними характеристиками, які дають можливість виконання перебірного методу.

Перебірний метод, який виконується на другій стадії розв'язання КЗСЛ, являє собою модифікацію класичного методу Літтла, адаптованого для знаходження циклу зв'язного підграфа H = (V, U) вихідного графа, у якому: а) степінь кожної вершини більша 2, б) множина R утворює паросполучення, в) немає точок зчленування.

У запропонованій модифікації (методі CRPP), як і у методі Літтла для розв'язання задачі комівояжера, дерево розгалуження розвивається з представлення матриці вартостей орієнтованим графом G = (V, E), отриманим у даному випадку з графа H шляхом заміни кожного ребра {i, j} парою дуг (i, j) і (j, i). Розв'язком КЗСЛ є простий контур мінімальної вартості. Тому, модифікація методу може бути застосована для розв'язання КЗСЛ, сформульованої у термінах орієнтованих графів.

У методі CRPP кореневій вершині дерева розгалуження ставиться у відповідність матриця вартостей вихідного графа H, матриця довжин найкоротших шляхів M і матриця маршрутизації W. Після їх перетворення знаходяться вершини, які породжуються на кроці розгалуження. Для визначення матриць M і W на кожному кроці розгалуження застосовується модифікація алгоритму Флойда-Уоршелла. У сукупності матриці D, M і W дозволяють виконати в умовах поставленої задачі усі дії класичного методу Літтла. У запропонованій версії методу вибір чергової вершини розгалуження виконується за схемою, яку зображено на рис. 2.

У матрицях M і W, які формуються за допомогою модифікованого алгоритму Флойда-Уоршелла для поточних параметрів матриці D, задля розгалуження, визначається дуга (p, q) або простий шлях з вершини p у вершину q. Для порівняння, у класичному методі розв'язання задачі комівояжера (ЗК) розгалуження відбувається за дугою, яка визначається з приведеної матриці вартостей. У цій же матриці шукається дуга, що запобігає утворенню підконтурів у розв'язку ЗК.

Умови КЗСЛ потребують формування множини Q заборонених дуг, тобто дуг, які викликають появу підконтурів у шуканому розв'язку .

Рис. 2. Схема розгалуження у методі розв'язання КЗСЛ

У множину Q включаються дуги у залежності від способу розбиття множини допустимих розв'язків на підмножини.

Якщо розгалуження ініціює дуга (k, l), яка відповідає ребру {k, l}, то множина допустимих розв'язків задачі розбивається на дві підмножини. Перша підмножина складається з усіх контурів, які містять дугу (k, l), а друга - з усіх контурів, які містять дугу (l, k).

Нехай розгалуження викликає дуга (k, l), {k, l} , або шлях з вершини k у вершину l. При формуванні множини Q він розглядається як дуга (k, l). У цьому випадку множина допустимих розв'язків розбивається на дві підмножини. Перша множина включає усі контури, які містять (k, l), а друга - усі контури, які не містять (k, l), тобто .

При формуванні першої підмножини, як і у методі HRPP, необхідна перевірка таких умов. Якщо множина R містить ребро {x, k}, то у шуканий контур разом з дугою (k, l) включається дуга (x, k). Аналогічно, якщо множина R містить ребро {y, l}, то до дуги (k, l) приєднується дуга (l, y). Включення дуги (x, k) або (l, y) у підмножину розв'язків означає, що відповідна матриця D не містить не тільки рядка k і стовпця l, але й того рядка і стовпця, номери яких є початком та кінцем приєднаної дуги. У випадку {x, k}, {y, l}R до дуги (k, l) приєднуються дуги (x, k) і (l, y), а з відповідної матриці D вилучаються рядки x, k, l і стовпці k, l, y.

Сформулюємо правило визначення множини Q:

- для кореня X0 дерева перебору Q =;

- усі елементи множини Q при вершині розгалуження передаються вершинам, які є її нащадками;

- якщо у будь-який розв'язок при вершині, породженій на етапі розгалуження, включається дуга (k, l), то до множини Q при цій вершині слід додати дугу (l, k);

- вага кожної дуги з Q приймається рівною нескінченності.

Якщо розгалуження викликає шлях з вершини k у вершину l, то для розбиття множини допустимих розв'язків на підмножини, що не перетинаються, використовується інше правило. У цьому випадку результатом розбиття є множина вершин V(L), яка представляє розширення множини вершин дерева перебору, породженої на попередніх кроках розгалуження.

У кореневій вершині і вершині розгалуження, де процес розбиття ініціює дуга, . Множина вершин утворює робочу підматрицю матриці M. Робоча матриця не містить рядків та стовпців, які відповідають вершинам множини . Внаслідок приведення робочої матриці знаходиться робоча приведена матриця .

Нехай розгалуження ініціює шлях, який містить кілька дуг. Тоді початкова та кінцева вершини шляху належать множині , а його проміжні вершини - множині . Початкова вершина відповідає рядку робочої матриці, кінцева вершина - стовпцю, а робоча матриця побудована на вершинах множини . Проміжна вершина , шляху потребує включення відповідного їй рядка та стовпця у робочу матрицю. У дереві перебору вершині відповідає множина розв'язків, які містять цю вершину. Кожна така множина може розглядатися як розбиття на дві підмножини, одна з яких містить дугу а інша не включає її.

Твердження 3. Метод CRPP знаходить розв'язок КЗСЛ або встановлює його відсутність.

У четвертому розділі описано програмний продукт, розроблений для розв'язання ГЗСЛ, КЗСЛ, ГЗК та проведення обчислювального експерименту.

Для розробки програмного продукту використано мову програмування Microsoft Visual C# 4.0 і, відповідно, середовище розробки Microsoft Visual Studio 2010. Для реалізації паралельних версій методів використано бібліотеку.NET Remoting.

Програмний продукт має такі можливості:

- випадковим чином генерувати одиночні умови задач і випадкові набори вхідних даних, вводити умови задач з клавіатури;

- зберігати та завантажувати умови задач з бази даних та xml-файлів;

- знаходити точний розв'язок ГЗК за допомогою класичного методу Літтла;

- виконувати процедуру ВРП і перевіряти достатні умови нерозв'язності ГЗК, ГЗСЛ, КЗСЛ;

- знаходити точний розв'язок ГЗСЛ або встановлювати факт нерозв'язності задачі для заданої матриці вартостей і заданої множини ребер R;

- визначати точний розв'язок КЗСЛ або встановлювати його відсутність для вихідної матриці вартостей і заданої множини ребер R;

- виконувати пошук розв'язків ГЗСЛ, КЗСЛ та ГЗК з використанням багатопроцесорних систем;

- формувати деталізований звіт про процес розв'язання задачі та експортувати його у текстові або html-файли;

- проводити обчислювальний експеримент.

Обчислювальний експеримент проведено на серії випадково згенерованих умов задач.

Досліджено залежність часу розв'язання ГЗСП методом HRPP від розмірності задачі та кількості фіксованих ребер. Для симетричної матриці вартостей з розмірністю від 10 до 50 з кроком 5 генерувалося по 100 тестових задач. Значення |R| варіювалося у діапазоні від 0 до |V|/2. Матриця заповнювалася випадковими числами з діапазону від 10 до 50. Кожна задача розв'язувалася модифікованим методом HRPP.

Аналогічні дії виконано для дослідження однопроцесорної версії методу CRPP. Генерувалося по 100 випадкових симетричних матриць розмірністю від 10 до 40 з кроком 5. Значення |R| змінювалося у діапазоні від 2 до |V|/2. Числа, якими заповнювалася матриця, обиралися з інтервалу від 10 до 50. Отримано залежність часу розв'язання КЗСП від параметрів |V|, |R|.

Результати експерименту дають можливість зробити такі висновки:

1. Час розв'язання задач методами HRPP (рис. 3) і CRPP (рис. 4) залежить як від розмірності вхідної матриці вартостей, так і від значення |R|, тобто представляється у вигляді трьохвимірного графіку залежності.

2. При фіксованому значенні |R| з ростом розмірності матриці вартостей час роботи методу зростає.

3. При фіксованій розмірності задачі, з ростом величини |R|, час роботи методу HRPP зменшується, а CRPP - зростає, а потім спадає.

Обчислювальний експеримент включав стадію, на якій порівнювався час розв'язання ГЗК за допомогою методу HRPP та класичного методу Літтла. Для кожної розмірності задачі від 10 до 50 з кроком 5 випадковим способом генерувалася серія зі 100 тестових задач. Кожна серія задач розв'язувалася методами Літтла і HRPP. Результати показали, що для розріджених графів застосування методу HRPP дозволяє прискорити пошук розв'язку в 1,6 раз.

Побудовано паралельні реалізації методів HRPP і CRPP, які дозволяють для розв'язання ГЗСЛ та КЗСЛ використовувати багатопроцесорні системи. Проведено експеримент на двох, чотирьох та восьми паралельних робочих процесах. Показано, що при використанні паралельних версій методів, досягається виграш у часі від 1,4 до 5,2 раз, у залежності від кількості процесорів (від 2-ох до 8-ми).

Висновки

1. Вперше у термінах проблеми комівояжера надано класифікацію задач знаходження найкоротших замкнених маршрутів, які проходять по заданим ділянкам і пунктам транспортної мережі, що дає можливість виділяти задачі зі схожими алгоритмічними властивостями і розробляти узагальнені методи їх розв'язання. Сформульовано нові прикладні задачі оптимізації замкнених процесів: гамільтонова та кільцева задачі про сільського листоношу (ГЗСЛ і КЗСЛ), пов'язані з відомими моделями маршрутизації. Формально ГЗСЛ полягає у знаходженні гамільтонового циклу мінімальної вартості, який містить фіксовану підмножину ребер зв'язного зваженого графу. На відміну від ГЗСЛ, у КЗСЛ потрібно знайти простий цикл з такими ж властивостями.

2. Показано, що ГЗСЛ і КЗСЛ є NP-повними і не завжди мають розв'язок. Тому для пошуку їх розв'язків можуть бути застосовані тільки точні методи обмеженого перебору, серед яких найменш трудомістким є метод гілок та меж.

3. Отримала подальший розвиток двостадійна схема гілок та меж, яка коректно будує найкоротший кільцевий маршрут, якщо він існує, або встановлює, що задача не має розв'язку. На першій стадії, виходячи зі структурних властивостей графа транспортної мережі та умов, які визначають множину допустимих маршрутів, за поліноміальний час виконується перевірка усіх відомих достатніх умов нерозв'язності задачі. Перевірка включає процедуру ВРП вихідного графа ГЗСЛ або КЗСЛ, яка приводить до одного з трьох можливих результатів: побудовано оптимальний розв'язок; задача не має розв'язку; пошук оптимуму потрібно продовжувати на перетвореному графі зі степенями вершин, більшими за 2, і з підмножиною фіксованих ребер, яка утворює паросполучення. ВРП дозволяє суттєво прискорити виконання точного методу, який виконується на другій стадії.

4. Вперше розроблена модифікація класичного методу гілок та меж для пошуку розв'язку ГЗСЛ на графі, отриманому внаслідок ВРП вихідного графу. Вперше застосовано спосіб розбиття множини усіх розв'язків на підмножини за допомогою двох правил розгалуження та вибору, які розвивають бінарне дерево перебору. Модифікація дозволяє розв'язувати ГЗК на розріджених графах значно швидше, ніж класичний метод Літтла.

5. Запропоновано новий теоретично обґрунтований метод знаходження найкоротшого замкненого маршруту для ВРП графа КЗСЛ. В основу метода покладено класичний алгоритм Літтла у комбінації з механізмом послідовного звуження області усіх простих циклів. Щоб виключити втрату оптимального розв'язку КЗСЛ, для кожної вершини розгалуження у дереві перебору за допомогою модифікованого алгоритму Флойда-Уоршелла обчислюється матриця найкоротших шляхів і матриця маршрутизації. Вони визначають усі вершини і ребра графа, з яких може бути побудовано шуканий цикл. У запропонованому методі вперше виконано спосіб розгалуження множини усіх розв'язків КЗСЛ на підмножини, які не перетинаються, із застосуванням трьох правил розгалуження і обчисленням відповідних нижніх оцінок вартості оптимального розв'язку. Розроблений метод без будь-яких змін коректно виконує пошук оптимального розв'язку ГЗСЛ, замкненої і незамкненої задач комівояжера (ЗК), а також ГЗК ? задачі пошуку в неповному зваженому графі найкоротшого гамільтонового циклу.

6. Розв'язання ГЗСЛ і КЗСЛ дозволяє зменшити витрати на пальне та часові витрати при виконанні транспортних перевезень, розвезенні вантажів, виконанні кур'єрських завдань за рахунок оптимального вибору кільцевих маршрутів руху транспортних засобів.

7. Розроблено програмний засіб для побудови і оптимізації кільцевих маршрутів на транспортній мережі, що включає паралельну реалізацію запропонованих методів. З результатів обчислювального експерименту випливає, що часові витрати на розв'язання ГЗСЛ і КЗСЛ значно зменшуються з ростом кількості процесорів.

Список опублікованих праць за темою дисертації

1. Гаращенко И.В. Метод решения гамильтоновой задачи коммивояжера. / И.В. Гаращенко, А.В. Морозов, А.В. Панишев // Искусственный интеллект. ? 2008. ? Вып. 3. ? С. 630?637.

2. Гаращенко І. В. Наближений метод розв'язання задач типу комівояжера, що задані матрицею спеціального вигляду / І. В. Гаращенко, А.В. Морозов, А.В. Панішев // Вісник Житомирського державного технологічного університету. ? 2007. ? №1(40). ? С. 147?154.

3. Морозов А.В. Про одне узагальнення задачі комівояжера /

А.В. Морозов // Вісник ЖДТУ. Технічні науки - 2009. - № 3 (50) . ? С. 161-171.

4. Морозов А.В. Вершинно-рёберное преобразование в гамильтоновой задаче о сельском почтальоне / А.В. Морозов, А.В. Панишев // Искусственный интеллект. - 2009. - Вып. 4. ?

С. 138-143.

5. Морозов А.В. Модификация метода Литтла для решения кольцевой задачи о сельском почтальоне / А.В. Морозов, А.В. Панишев, В.А. Скачков // Искусственный интеллект. - 2010. - Вып. 3. - С. 103-115.

6. Morozov A. Modified branch and bound algorithm for solving the Hamiltonian Rural Postman Problem / A. Morozov, A. Panishev // Information Models of Knowledge. - Kiev-Sofia. - 2010. -

P. 442-450.

7. Морозов А.В. Поліноміальні перетворення в задачі комівояжера /

А.В. Морозов, А.В. Панішев // Сучасні інформаційні системи. Проблеми та тенденції розвитку: матер. 2-ї міжнар. конф., 2?5 жовтня 2007 р.: тези доп. - Харків: ХНУРЕ, 2007. ? С. 188?189.

8. Левченко А.Ю. Поиск цикла минимальной стоимости, проходящего по всем вершинам связного графа / А.Ю. Левченко, А.В. Морозов, А.В. Панишев // Проблеми математичного моделювання: міжнар. наук.-метод. конф., 27?29 травня 2009 р.: тези доп. ? Дніпродзержинськ. - 2009. - С. 150-152.

9. Левченко А.Ю. Точный метод решения симметричной задачи коммивояжера / А.Ю. Левченко, А.В. Морозов, А.В. Панишев // Прикладные задачи математики и механики: матер. XVII межд. науч.-техн. конф., 14-18 сентября 2009 г.: тезисы докл. - Севастополь. - 2009. - С. 238-241.

10. Панишев А.В. О кольцевой задаче о сельском почтальоне /

А.В. Панишев, А.В. Морозов // Современные информационные и электронные технологии: 11-я межд. науч.-практ. конф., 24-28 мая 2010 г.: тезисы докл. - Одесса. - 2010. - Т.1. - С. 45.

11. Морозов А.В. Кільцева задача про сільського листоношу та підхід до її розв'язання / А.В. Морозов, А.В. Панішев // XXXV наук.-практ. міжвуз. конф., 25-28 травня 2010 р.: тези доп. - Житомир: ЖДТУ. - 2010. - Т. 1 - С. 66-67.

12. Морозов А.В. Метод гілок та меж для розв'язання кільцевої задачі про сільського листоношу / А.В. Морозов // Інформатика та системні науки: матер. всеукр. наук.-практ. конф.,

18-20 березня 2010р.: тези доп. - Полтава: РВВ ПУСКУ. - 2010. - С. 138-140.

13. Морозов А.В. О задаче оперативного управления транспортным процессом / А.В. Морозов, А.В. Панишев // Автоматизация: проблемы, идеи, решения: матер. межд. науч.-техн. конф., 6-10 сентября 2010 г.: тезисы докл. -Севастополь. - 2010. - Т. 2. - С. 98-101.

14. Морозов А.В. О задачах нахождения замкнутых маршрутов на транспортной сети / А.В. Морозов, А.В. Панишев // Прикладные задачи математики и механики: матер. XVІII межд. науч.-техн. конф., 13-17 сентября 2010 г.: тезисы докл. - Севастополь. - 2010. - С. 166-169.

Размещено на Allbest.ru