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

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

УДК 51:330.115

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

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

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

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

Гаращенко Ірина Володимирівна

Харків 2009

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

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

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

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

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

Захист відбудеться «14» квітня 2009 р. о 14.30 годині на засіданні спеціалізованої вченої ради Д 64.052.02 у Харківському національному університеті радіоелектроніки (61166, м. Харків, пр. Леніна, 14).

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

Автореферат розісланий «13» березня 2009 р.

Вчений секретар

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

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

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

ГЗК, СЗК, їх версії, окремі випадки та узагальнення знаходять застосування в проектуванні мереж комунікацій, при оптимізації маршрутів перевезення пасажирів і вантажів, у будівництві і реконструкції інфраструктури міста і регіону, в розробці автоматизованих систем розкрою на верстатах з ЧПУ, в генній інженерії тощо.

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

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

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

1. Аналіз сучасного стану проблеми комівояжера і характеристика методів розв'язання її двох базових задач: ГЗК і СЗК.

2. Дослідження структурних особливостей математичних моделей транспортних мереж.

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

4. Розробка методу пошуку розв'язку ГЗК з меншими потребами в обчислювальних ресурсах, ніж у відомих методів.

5. Побудова оптимізаційної моделі проектування і реконструкції комунікаційних мереж, яка узагальнює ГЗК і розширює область її застосування.

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

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

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

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

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

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

2. Вперше отримано нові достатні умови негамільтоновості графа, які встановлюються за поліноміальний час. Для прискорення процесу пошуку розв'язку ГЗК вперше використано метод, що поєднує алгоритм типу гілок та меж і процедуру перевірки відомих і отриманих умов, що дає змогу відразу встановлювати факт негамільтоновості (нерозв'язності) задачі.

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

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

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

Створені програмні модулі дозволяють розв'язати низку прикладних задач проблеми комівояжера в умовах, визначених вимогами практики. Розроблений програмний продукт використовується на Броварській експериментальній виробничій базі.

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

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

Апробація результатів дисертації. Основні результати дисертаційної роботи доповідалися й обговорювалися на 1-й міжнародній конференції „Глобальні інформаційні системи. Проблеми та тенденції розвитку” (Харків, 2006 р.); 10-му ювілейному міжнародному молодіжному форумі „Радиоэлектроника и молодежь в ХХІ веке” (Харків, 2006 р.); ХХХІ науково-практичній міжвузівській конференції, присвяченій Дню університету (Житомир, 2006 р.); 7-й, 8-й і 9-й міжнародних науково-практичних конференціях „Современные информационные и электронные технологии” (Одеса, 2006, 2007, 2008 рр.); міжнародній науковій конференції „Современные проблемы математики и её приложения в естественных науках и информационных технологиях” (Харків, 2007 р.); міждержавній науково-методичній конференції „Проблеми математичного моделювання” (Дніпродзержинськ, 2008 р.); 7-й, 8-й і 9-й міжнародних науково-технічних конференціях „Штучний інтелект-2006, 2007, 2008. Інтелектуальні системи”; міжнародній науковій конференції ITA 2008, Second part, (Ужгород, вересень-жовтень 2008 р.).

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

Структура та обсяг роботи. Дисертація складається зі вступу, чотирьох розділів, висновків, двох додатків. Загальний обсяг роботи складає 149 сторінок, в тому числі 134 сторінки основного тексту, додатків - 2 сторінки. Дисертація містить 46 ілюстрацій (17 стор.), 14 таблиць (10 стор.), список використаних джерел, що містить 101 найменування на 10 сторінках.

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

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

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

Кожну задачу класу комівояжера можна подати як оптимізаційну задачу про перестановки, що визначається трійкою (P, X, f), елементи якої позначають наступні об'єкти.

1. Р - простір розв'язків: множина всіх циклічних перестановок (обходів) = , , …, множини {1, 2,…, n}. Обходу відповідає маршрут комівояжера або гамільтонів цикл у вигляді послідовності, , …, , різних номерів, ,…, елементів 1, 2,…, n.

2. Х - простір параметрів, кожний елемент якого х є квадратною матрицею вартостей порядку n, , - множина дійсних невід'ємних чисел, , = ,.

3. f - функціонал вартості: f:, де - вартість розв'язку при значенні параметра х.

Оптимальним розв'язком для значення параметра х є розв'язок, такий, що для всіх у випадку мінімізації функціонала і у випадку його максимізації.

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

ГЗК на транспортній мережі, що моделюється повним зваженим графом, з цільовим функціоналом виду

(1)

називається симетричною задачею комівояжера (СЗК).

Незважаючи на численні досягнення в дослідженні проблеми комівояжера, вона безперервно поповнюється новими прикладними задачами і новими, більш сучасними методами комбінаторної оптимізації. До переліку таких задач належать задачі, яким притаманні особливості ГЗК і СЗК. ГЗК, що є NP-трудною, може не мати розв'язку. Звідси випливає, що на теперішній час не існує інших методів знаходження її мінімуму, крім алгоритму організованого відсіву всіх негамільтонових циклів графа Н. СЗК також NP-трудна, але завжди розв'язна. Тому основні зусилля в дослідженні задач типу СЗК на поточному етапі направлені на розробку швидкодіючих наближених алгоритмів розв'язання з оцінками точності і трудомісткості, які залежать від розміру вхідних даних. Виявляється, що час розв'язання СЗК залежить не тільки від порядку матриці вартостей. Для значень, які належать проміжку [a, b], у випадку матриця містить декілька елементів однакової ваги,. Вона породжує тим більше оптимальних і субоптимальних розв'язків, чим вужчий проміжок [a, b]. Для матриць вартостей СЗК фіксованого розміру спостерігається характерна тенденція зростання часу роботи і похибки наближеного алгоритму зі зростанням кількості близьких значень. Цей факт є причиною, яка стимулює подальше вивчення алгоритмічних властивостей СЗК.

Другий розділ містить приклади застосувань СЗК в системі підготовки програм, які керують процесом теплового різання металу, і в системах планування автомобільних перевезень.

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

Основна частина розділу містить опис і аналіз наближеного методу розв'язання СЗК. Метод знаходить за поліноміальний час точний розв'язок релаксації й ефективно перетворює його в гамільтонів цикл. Як релаксацію обрано задачу побудови в повному зваженому графі i- дерева мінімальної ваги.

i- деревом називається підграф повного графа, який містить дерево, що охоплює множину вершин і два ребра, інцидентні вершині {1, 2,..., n},. Введене поняття узагальнює відоме визначення 1-дерева і дозволяє отримати такий результат.

Лема. У будь-якому i- дереві, , кількість висячих вершин

, (2)

де - степінь вершини k.

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

Кожне ребро i- дерева подамо впорядкованою парою, де, - степені вершин k, l в Т, , {1, 2,..., n}. У Т виділимо лівий і правий ланцюги, що починаються у вершині i. Кожний ланцюг закінчується першою вершиною, степінь якої більший за 2. Останні ребра лівого та правого ланцюга позначимо відповідно, , = 2, (рис. 1).

Наступна процедура перетворює i-дерево Т в гамільтонів цикл повного графа.

S0. В i-дереві, , знайти останнє ребро лівого ланцюга або останнє ребро правого ланцюга. Побудувати послідовність із всіх ребер, у яких, , в такий спосіб: в першим є ребро або, а інші компоненти послідовності розташовуються в довільному порядку.- список з n ребер i-дерева Т,.

S1. Поки виконувати

видалити з компоненту;

покласти- 1 в кожній компоненті множини, що містить;

знайти ребро, для якого;

покласти, , =;

розташувати компоненту на місце вилученої пари;

визначити ланцюг, у якому = = … = ,;

встановити,.

S2. У побудованій множині визначити гамільтонів цикл.

Теорема. Підграф повного графа, поданий i- деревом Т = , {1, 2,..., n}, коректно перетворюється на гамільтонів цикл за час, де- кількість висячих вершин в Т.

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

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

{1, 2,..., n}.

Оцінкою трудомісткості знаходження служить часова оцінка складності будь-якого градієнтного алгоритму побудови КМВ, наприклад, алгоритму Прима. Відомо, що КМВ графа з множиною ребер Е можна отримати за час.

На другій стадії виконується процедура перетворення дерева = на гамільтонів цикл повного зваженого графа. Вартість отриманого розв'язку СЗК

,

де - множина ребер, видалених з, - множина ребер графа, доданих до;, - кількість висячих вершин дерева, яке визначається із співвідношення (2).

Оскільки в будь-якому градієнтному алгоритмі побудови КМВ ребро з найменшою вагою додається до, а внаслідок виконання другої стадії воно може бути замінене на ребро з найбільшою вагою в, то в найгіршому випадку

. (3)

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

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

Для графа, , алгоритм будує КМВ, утворюючи розбиття множини його ребер на m підмножин,. Кожна підмножина містить всі ребра однієї ваги. Нехай підмножини, , занумеровані так, що якщо, , , то. Підмножині поставимо у відповідність множину всіх ребер такої ж ваги в. Тоді будь-який КМВ в містить точно ребер множини, , і, відповідно,

.

Таким чином, область пошуку КМВ J з найменшою кількістю висячих вершин обмежена множиною тільки тих кістяків, які належать підграфу, що заданий множиною вершин і множиною ребер. Потужність множини кістяків у підграфі визначається з відомої матричної теореми про дерева.

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

Очевидно, на першому етапі потрібно визначити, чи містить граф хоча б одну висячу вершину або точку з'єднання. Для їх розпізнавання потрібен час.

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

S0. H = (V, U) - граф, який не містить висячих вершин і точок з'єднання, але містить вершини степеня 2.

S1. Кожний ланцюг (p, q,…, t, w), зі степенями вершин, = 2, замінити на ребро з вагою, що дорівнює сумі ваг його ребер; визначити, чи існує інше ребро, яке з'єднує вершини p та w, і, якщо існує, видалити його.

S2. Якщо ребра, які отримані на кроці S1, утворюють вершинонепересічні ланцюги (p, s,…, r, v), то для кожного з них видалити з множини ребер, що залишилися, всі ребра, інцидентні вершинам s, …, r, замінити ланцюг на ребро з вагою, яка дорівнює сумі ваг його ребер, і перейти до кроку S1. Інакше кінець: граф H = (V, U) негамільтонів.

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

Степінь будь-якої вершини графа, який побудовано внаслідок ВРП графа H = (V, U), більший за 2, а множина містить підмножину невидалених ребер з U і множину доданих ребер R.

Твердження. Якщо в графі множина ребер R не є паросполученням, то граф H = (V, U) негамільтонів.

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

Для обчислення нижніх оцінок величини алгоритм викликає процедуру розв'язання задачі про призначення (ЗП), що містить матрицю вартостей ГЗК. Оскільки в такій матриці є елементи, , то ЗП може виявитись нерозв'язною. Тоді не має розв'язку і ГЗК. Нижня оцінка вартості шуканого циклу визначається за допомогою модифікації алгоритму Кана-Мункреса, що запропонована для розв'язку ЗП з матрицею, в якій не тільки елементи головної діагоналі дорівнюють.

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

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

Для ЗП, , модифікацією алгоритму Кана-Мункреса будується перестановка, якщо розв'язна, або з'ясовується, що вона не має розв'язків. Нехай із k задач розв'язні задач, {1, 2,..., k}, , тобто побудовані оптимальні перестановки й обчислені значення, що доставляються ними. Очевидно, вартість шуканого гамільтонового циклу обмежена величиною

Якщо розв'язок задачі, для якої, є гамільтоновим циклом, то він буде і розв'язком ГЗК. Інакше перестановка утворює декілька непересічних циклів, а вершина дерева перебору оголошується вершиною розгалуження. Задача розбивається на задачі, розв'язки яких не містять циклу мінімальної довжини з розкладання перестановки. Внаслідок виконання модифікації алгоритму Кана-Мункреса для кожної отриманої задачі визначаються розв'язних задач, , , і поточна нижня границя циклу

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

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

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

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

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

(4)

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

Якщо, то розв'язком задачі (4) є КМВ графа H = (V, U) з мінімальною кількістю висячих вершин.

У загальному випадку транспортна мережа містить як транзитні, так і тупікові пункти, тобто моделюється графом H = (V, U), що містить висячі вершини. Для такої мережі поставлена задача полягає в мінімізації (4) на деякому підграфі графа Н. Дійсно, в будь-якому розв'язку задачі, що поданий кістяковим деревом графа Н, кожна висяча вершина j отримує вагу. У графі Н множина всіх висячих вершин утворює підграф у вигляді лісу. Кожному дереву лісу взаємно-однозначно відповідає коренева вершина, що зв'язує його з частиною графа Н, яка не є лісом. Оскільки всі ребра містяться в будь-якому кістяковому дереві графа Н, то степені кореневих вершин у припустимому розв'язку більші за 1, а степені інших вершин лісу не змінюють своїх значень.

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

Поклавши в для кожної кореневої вершини , отримаємо функціонал, що мінімізується, який збігається з точністю до позначень з функціоналом (4):

(5)

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

У четвертому розділі описано програмний продукт, що призначений для експериментального дослідження отриманих теоретичних результатів. Розроблений засіб дозволяє:

- реалізувати три алгоритми типу гілок та меж для розв'язку СЗК;

- отримати наближений розв'язок відомими алгоритмами NN, NT, NC, MST, MM;

- реалізувати наближений метод розв'язку СЗК, викладений у розділі 2 у двох варіантах: за допомогою побудови а) єдиного дерева ("1-дерево"); б) n дерев, n - число вершин повного графа ("i*-tree");

- виконати пошук розв'язку ГЗК методом, викладеним у розділі 3.

Операційною системою (ОС) програмного засобу є Microsoft Windows, а мовою програмування - Microsoft Visual C#.

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

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

Досліджено точність наближених алгоритмів метричної СЗК в залежності від порядку матриць вартостей, що згенеровані випадковим способом, та матриць, заповнених на 20%, 50%, 80% однаковими значеннями. Для матриць порядку 50 - 400, в яких 20%, 50%, 80% елементи набувають одного й того самого значення, точність наближеного методу оцінювалась відношенням вартості побудованого розв'язку до нижньої границі оптимального, за яку обрана вага i-дерева. Результати проведеного експерименту дозволяють зробити такі висновки.

1. Для задач з матрицями вартостей порядку 50-400, згенерованими без обмежень на значення елементів, найточнішим є алгоритм ММ. Проте задачі такої ж розмірності з матрицями, заповненими на 20% - 80% однаковими значеннями, розв'язуються методом "i*-tree" з меншою похибкою.

2. Для метричної СЗК розмірністю 3-50 метод "i*-tree" будує більш точні розв'язки, ніж алгоритми NN, NT, NC, MST, MM.

Досліджено поведінку наближених алгоритмів неметричної СЗК, для якої порядок матриці вартостей варіюється в проміжку 3 - 250.

Із результатів експерименту, поданих на рис. 2, випливає: а) ефективні алгоритми розв'язку СЗК, що не задовольняють умові трикутника, характеризуються залежністю похибки від розміру входу, близькою до лінійної; б) алгоритм ММ, що розв'язує метричну СЗК із теоретично неперевершеною точністю, дає досить велику помилку розв'язку СЗК з довільними значеннями матриці вартостей; в) методи "1-tree" і "i-tree" забезпечують найбільшу точність розв'язку неметричної СЗК.

Дослідження трудомісткості методу розв'язку ГЗК виконано на компьютері Celeron 1,8 Гц з оперативною пам'яттю 2 Гб.

Експеримент показав, що для матриць вартостей порядку меншого за 40, пошук розв'язку ГЗК виконується практично в режимі реального часу.

Висновки

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

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

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

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

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

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

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

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

1. Гаращенко И. В. Приближенный алгоритм решения симметричной задачи коммивояжера / И. В. Гаращенко, А. В. Панишев, Д. Д. Плечистый // Искусственный интеллект. Донецк, 2006. Вып. 3. С. 371-378.

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

3. Гаращенко И. В. Полиномиальное преобразование в приближенных алгоритмах решения задач типа коммивояжера / И. В. Гаращенко, А. В. Панишев, О. Б. Маций // Радиоэлектроника и информатика. 2007. № 1. С. 45-49.

4. Гаращенко И. В. Об одном классе задач построения остовного дерева в неориентированном взвешенном графе / И. В. Гаращенко, А. В. Панишев. // Искусственный интеллект. Донецк, 2007. Вып. 3. С. 486-493.

5. Гаращенко І. В. Евристичний алгоритм пошуку кістяка мінімальної ваги з мінімальною кількістю висячих вершин / І. В. Гаращенко // Вісник Житомирського державного технологічного університету. 2007. № 4 (43). С. 147-154.

6. Irina Garashchenko. Method of Finding Hamilton Routesin Transport Network / Irina Garashchenko, Anatoliy Panishev // Artificial Intelligence and Decision Making. ITHEA, Sofia, 2008. Number 7. P. 43-48.

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

8. Гаращенко И. В. О решении задачи коммивояжера на транспортной сети / И. В. Гаращенко, А. В. Панишев, В. А. Шевченко // Глобальні інформаційні системи. Проблеми та тенденції развитку: перша між нар. конф, 3-6 жовт. 2006 р.: матеріали конф. Харків, 2006. С. 244-245.

9. Гаращенко И. В. Особенности применения дискретного программирования для решения задач маршрутизации / И. В. Гаращенко // Радіоелектроніка і молодь в ХХІ ст.: 10-й ювілейний між нар. молодіжний форум, 10-12 квіт. 2006 р.: матеріали конф. Харків, 2006. С. 575.

10. Гаращенко І. В. Вдосконалення методу гілок і границь в симетричній задачі комівояжера / І. В. Гаращенко // ХХХІ наук.-практ. міжвузівська конф, 14-16 березня 2006 р.: зб.тез доповідей. Житомир, 2006. С. 25.

11. Гаращенко И. В. Программная реализация методов комбинаторной оптимизации для решения класса задач типа коммивояжера / И. В. Гаращенко, А. В. Панишев, Д. Д. Плечистый // Современные информационные и электронные технологии: 7-я междунар. науч.-практич. конф., 22-26 мая 2006 г.: труды конф. Одесса, 2006. С. 28.

12. Гаращенко И. В. Приближенный метод решения задач типа коммивояжера, заданных матрицей специального вида / И. В. Гаращенко // Современные проблемы математики и ее приложения в естественных науках и информационных технологиях: междунар. науч. конф., 23-25 марта 2007 г.: материалы конф. Харьков, 2007. С. 112 - 115.

13. Гаращенко И. В. Модификация приближенного метода решения задач типа коммивояжера, заданных матрицей специального вида / И. В. Гаращенко, А. В. Панишев, А. Ю. Левченко // Современные информационные и электронные технологии: 9-я междунар. науч.-практич. конф., 19-23 мая 2008 г.: труды конф. Одесса, 2008. Т.1. С. 45.

14. Гаращенко І. В. Про один метод побудови оптимального обходу / І. В. Гаращенко, А. В. Панішев // Проблеми математичного моделювання: міждерж. наук.-методич. конф., 28-30 травня 2008 р.: тези доповідей. Дніпродзержинськ, 2008. С. 34-36.

Анотація

Гаращенко І. В. Моделювання і розробка методів оптимізації циклічних процесів на транспортних мережах. - Рукопис.

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

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

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

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

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

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

Аннотация

Гаращенко И.В. Моделирование и разработка методов оптимизации циклических процессов на транспортных сетях. - Рукопись.

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

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

Для решения СЗК предложен метод, состоящий из двух этапов. На первом этапе находится решение вспомогательной задачи (релаксации), в качестве которого выбрано i-дерево минимальной стоимости. i-деревом называется подграф полного графа = (V, E), который содержит дерево, стягивающее множество вершин, и два ребра, инцидентные вершине i, {1, 2,…, n}, |V| = n. На втором этапе выполняется полиномиальное преобразование в гамильтонов цикл. Аналитически установлено, что точность предложенного метода зависит от числа концевых (висячих) вершин i-дерева минимальной стоимости, построенного на первом этапе, и от разности между максимальным и минимальным элементами матрицы стоимостей СЗК. Чем ближе значения этих элементов, тем меньше отклонение стоимости построенного решения от стоимости оптимального.

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

Для решения ГЗК разработан точный двуэтапный метод, который строит гамильтонов цикл минимальной стоимости, если ГЗК разрешима, или корректно определяет, что граф негамильтонов. На первом этапе за полиномиальное время проверяются все известные достаточные условия негамильтоновости графа. Если ни одно из них не выполняется, то выполняется второй этап, построенный в соответствии со схемой ветвей и границ. Для вычисления оценок снизу значения целевого функционала ГЗК в схеме ветвления применяется эффективная процедура решения задачи о назначениях (ЗН), представляющая модификацию известного алгоритма Кана-Мункреса. Процедура либо строит решение ЗН, если оно существует, либо строго устанавливает, что задача не имеет решений. Предлагаемый метод решения ГЗК легко адаптируется для решения классической задачи поиска гамильтонова цикла в связном графе.

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

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

Прикладной характер построенной модели становится очевидным из формулировки следующей задачи оптимального планирования: необходимо найти такую часть транспортной сети H = (V, U), связывающую все её пункты, реконструкция которой требует минимума затрат на дорожное полотно и терминалы.

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

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

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

Abstract

Garashchenko I.V. Modeling and development of methods of cyclic processes optimization on transport networks. - Manuscript.

Dissertation for achieving scientific degree of Candidate of Technical Sciences with specialization "01.05.02 - mathematical modeling and computing methods". - Zhitomir State Technological University, Zhitomir, 2009.

This dissertation shows algorithmic features of Symmetric Traveling Salesman Problem (STSP) and Hamilton's Traveling Salesman Problem (HTSP) which need further study: the property of symmetry essentially impacts the time and precision of approximate solution of STSP, while HTSP is not solvable every time.

High precision of STSP solution is provided by algorithm structure which consists of two phases. Laboriousness of the approximate solution of STSP depends on algorithmic properties of relaxation and the method of transformation of it.

There is proposed two-stage algorithm of HTSP solution, which starts with checking conditions of transport network being not-Hamiltonian, based upon it's structural characteristics. If none of them are positive then branch-and-bound-like algorithm cuts off non-Hamiltonian cycles. For lower estimations calculation there is proposed modified method of assignment problem solution, which determines non-solvability of HTSP at vertexes of tree of branching.

Developed software complex was used for computing experiment and analysis of it's received data.

Keywords: Symmetric Traveling Salesman Problem, STSP, Hamiltonian cycle, approximate solution, transport networks, optimization, minimal spanning tree, MST, accuracy rankings.

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

...