Моделі та ефективні методи організації циклічних процесів в класі задач типу комівояжера

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

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

УДК 519.12.176

Автореферат

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

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

Моделі та ефективні методи організації циклічних процесів в класі задач типу комівояжера

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

Плечистий Дмитро Дмитрович

Харків - 2005

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

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

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

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

кандидат технічних наук, доцент Ребезюк Леонід Миколайович, Харківський національний універ-ситет радіоелектроніки, доцент кафедри системо-техніки.

Провідна установа - Національний технічний університет України „Київський політехнічний інститут” (кафедра прикладної математики) Міністерства освіти і науки, м. Київ.

Захист відбудеться „30” червня 2005 р. о 14:00 годині на засіданні спеціалізованої вченої ради Д 64.052.02 Харківського національного університету радіоелектроніки за адресою: 61166, м. Харків, просп. Леніна, 14.

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

Автореферат розісланий „27” травня 2005 р.

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

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

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

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

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

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

Зв'язок роботи з науковими програмами, планами, темами. Дослідження виконувались у відповідності з координаційним планом Міністерства освіти і науки України за науковим напрямком „Технічна кібернетика” і в рамках держбюджетних тем: №0197U015183 „Розвиток математичних методів і алгоритмів скорочення перебору рішень в задачах створення інтелектуальних систем обробки інформації”, №0199U002692 „Моделювання послідовно-паралельних процесів функціонування технічних і виробничих систем на основі методів комбінаторної оптимізації і перспективних інформаційних технологій” на період з 2002 по 2004 роки. Здобувач брав участь у виконанні робіт за вищевказаними темами як виконавець.

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

Для досягнення поставленої мети потрібно вирішити наступні задачі:

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

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

- розробити методи розв'язання неметричної ЗК з вбудованими процедурами підвищення точності отримуваних розв'язків;

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

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

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

Предмет дослідження - швидкодіючі методи розв'язання класу задач типа комівояжера.

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

Наукова новизна одержаних результатів.

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

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

3. На основі вивчення властивостей ЗК вперше знайдено ефективно-розв'язуваний частковий випадок задачі складання конвеєрного розкладу для безперервно виконуваних робіт.

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

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

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

Запропонований пакет комбінованих алгоритмів використовується в системах автоматизованого проектування та системах керування вироб-ництвом в Житомирському спеціальному конструкторсько-технологічному бюро засобів моделювання в енергетиці НАН України та в товаристві з обмеженою відповідальністю радіокомпанії REC для знаходження послідовності обходу точок на друкованих платах, що підтверджується актами впровадження (відповідно від 30.07.2003 та від 25.07.03).

Зміст дисертації знайшов застосування при викладанні таких курсів, як „Дослідження операцій”, „Теорія складності екстремальних задач” в Житомирському державному технологічному університеті.

Особистий внесок здобувача. В усіх перелічених публікаціях автор приймав участь у розробці математичних моделей, методів і алгоритмів розв'язання задач та їх реалізації на ПЕОМ: в [1] автором остаточно сформульовано спосіб побудови допустимого розв'язку для загальної ЗК, оцінено його часову складність; в [2] автором виконано обчислювальний експеримент, зроблено висновки щодо його результатів; в [3] запропоновано спосіб поліпшення отримуваних допустимих розв'язків загальної ЗК; в оглядових роботах [4] та [5] автором зроблено класифікацію існуючих методів розв'язання ЗК та проведено їх порівняння; в [12] автором виведено нові властивості часткового випадку задачі складання розкладу конвеєрної системи, завдяки яким стало можливим утворювати оптимальний розв'язок; в [6] автором показано, як результати роботи [12] можна використовувати на практиці при проектуванні інформаційно-вимірювальних систем.

Апробація результатів дисертації. Результати досліджень доповідались і обговорювались на наукових конференціях: V міжнародна науково-практична конференція „Наука і освіта - 2002” (Дніпропетровськ, 2002 р.); міжнародна конференція з індуктивного моделювання „МКІМ-2002” (Львів, 2002 р.); міжнародна науково-практична конференція „Искусствен-ный интеллект - 2002” (Кацивелі, Крим, 2002 р.); міжнародная конференція „Проблеми математичного моделювання сучасних технологій - 2002” (Хмельницький, 2002 р.); 7-й міжнародний молодіжний форум „Радио-электроника и молодежь в ХХІ веке” (Харків, 2003 р.); міжнародна науково-практична конференція „Штучний інтелект - 2003” (Дивноморськ, Росія, 2003 р.); четверта міжнародна науково-практична конференція „Современные информационные и электронные технологии” (Одеса, 2003 р.); п'ята міжнародна науково-практична конференція „Современные информа-ционные и электронные технологии” (Одеса, 2004 р.); міжнародна науково-практична конференція „Искусственный интеллект - 2004” (Кацивелі, Крим, 2004 р.).

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

Структура і обсяг роботи. Дисертація складається з вступу, чотирьох розділів, висновків, списку використаних джерел та додатків. Основний обсяг дисертації становить 136 сторінок. Робота містить 33 рисунка на 12 сторінках, 13 таблиць на 5 сторінках, список використаних джерел, що містить 91 найменування на 9 сторінках, 2 додатки на 2 сторінках.

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

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

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

Загальна (асиметрична) ЗК може бути сформульована так: задано матрицю вартостей , де - дійсні, невід'ємні, довільні числа, , та потрібно знайти циклічну перестановку на множині , яка мінімізує функцію

.

Циклічну перестановку називають також обходом, а величину - вартістю обходу.

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

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

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

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

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

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

S0. - матриця вартостей порядку в ЗК; , , , , .

S1. ; побудувати з перестановки послідовність ; сформувати з циклічних перестановок : , , ..., , , ..., ; обчислити вартості обходів, що відповідають побудованим перестановкам :

,

,

...

, ,

...

;

знайти такий обхід , що ; встановити , .

S2. Якщо , то кінець: , інакше визначити циклічну перестановку , що відповідає обходу , перейти до кроку S1.

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

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

- множина всіх обходів довжини , і можна отримати видаленням з дуг і заміною їх іншими дугами.

Обхід назвемо локально оптимальним відносно , якщо для всіх .

Для загальної ЗК система околів відносно обходу може бути побудована при . У випадку вона містить контурів з дуг.

Алгоритм пошуку локально-оптимального обходу в -околі можна представити наступним чином:

S0. - вартість початкового обходу; покласти ;

S1. Для кожного обходу знайти його вартість ; покласти , якщо .

Визначив 3-заміну відносно розв'язку, побудованого процедурою знаходження , можна отримати .

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

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

та знайдемо

.

Тоді справедливе наступне твердження.

Твердження 1. Якщо , , де , то виключення з діагоналі, що задає , елементу та додання до неї елементів , утворює локальний оптимальний розв'язок для .

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

Якщо , де - локальний обхід, отриманий з видаленням дуги та доданням дуг , , то -заміна є результативною. Тоді встановлюється , інакше . Вартість дорівнює

,	(2)
.	(3)

Очевидно, на побудову потрібен час, який обмежено величиною .

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

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

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

,	(4)

де , , , , , , .

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

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

Оптимальний розв'язок задачі мінімізації належить класу перестановочних розкладів та при знаходиться за час . При та довільних значеннях пошук мінімуму є NP-складною задачею. В результаті вивчення особливостей моделі (4) встановлено наступний результат.

Твердження 2. Задача знаходження мінімуму при , , є ефективно розв'язуваною за час .

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

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

Твердження 3. Якщо - матриця, впорядкована по рядках, то у відповідній матриці вартостей ЗК виконується нерівність

, , .	(5)

Твердження 4. Елементи матриці пов'язані співвідношенням

, , , , , , .	(6)

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

Четвертий розділ дисертації присвячено розробці програмного забезпечення, де набули алгоритмічної реалізації запропоновані методи розв'язання ЗК та її часткових випадків, і проведенню обчислювального експерименту, в якому дані методи досліджувались. Для дослідження представлених методів розроблено програмний засіб “TS Explorer”.

Функціональне наповнення “TS Explorer” представлено програмними реалізаціями методу побудови локальних послідовностей у вигляді алгоритму знаходження обходу (ЛП), його модифікації - алгоритму з -заміною (ЛП-Мод), а також точного алгоритму мінімізації для випадку, коли матриця упорядкована по рядкам. Окрім того, до “TS Explorer” ввійшла програма побудови точного розв'язання загальної ЗК методом гілок та меж (методом Літла), яка використовується для оцінки похибки наближеного методу, евристична процедура „йди до найближчого”, а також метод „найближчого міста”.

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

1) Для розмірностей вихідної матриці ЗК від 20 до 40 розв'язувалось по 100 екземплярів задачі алгоритмами Літтла, ЛП та ЛП-Мод. Значення елементів матриці генерувалися випадково в межах від 1 до 50. На матрицю не було накладено обмежень. Досліджувались відношення вартостей обходів, утворених ЛП та ЛП-Мод, до вартостей оптимальних маршрутів.

2) Аналогічні дії виконувались для ЗК з матрицями вартостей, на які після випадкової генерації елементів накладалось обмеження трикутника.

3) Для розмірностей вихідної матриці ЗК від 20 до 100 розв'язувалось по 100 екземплярів задачі алгоритмами ЛП, ЛП-Мод та найближчого міста. Значення елементів матриці генерувалися випадково в межах від 1 до 50. На матрицю не було накладено обмежень. Досліджувались відношення вартостей обходів, утворених алгоритмом найближчого міста до вартостей наближених розв'язків, утворених алгоритмами ЛП та ЛП-Мод.

4) Аналогічні дії виконувались для ЗК з матрицями вартостей, на які після випадкової генерації елементів накладалось обмеження трикутника.

5) Для розмірностей вихідної матриці ЗК від 40 до 100 розв'язувалось по 100 екземплярів задачі алгоритмами ЛП та ЛП-Мод. Значення елементів матриці генерувались випадково в межах від 1 до 50. На матрицю вартостей не було накладено обмежень. Досліджувались середні значення співвідношення розв'язків, що утворювались алгоритмами ЛП та ЛП-Мод на кожній розмірності.

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

Порівняльний аналіз отриманих даних та графіків дозволив зробити наступні висновки.

1) Абсолютна похибка на інтервалі від 20 до 40 зростає практично лінійно. Для визначення характеру подальшої поведінки похибки необхідно проводити додаткове порівняння з точними розв'язками на більших розмірностях.

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

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

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

1) Відношення вартостей розв'язків алгоритму найближчого міста до вартостей розв'язків алгоритмів ЛП та ЛП-Мод на інтервалі від 20 до 100 зростає. Дане відношення зростає значно повільніше у випадку, коли на матрицю вартостей накладено обмеження трикутника.

2) Наближені розв'язки, які утворюються алгоритмами ЛП та ЛП-Мод, є кращими, ніж наближені розв'язки, що утворюються алгоритмом найближчого міста. При цьому алгоритми ЛП та ЛП-Мод утворюють розв'язки швидше, ніж алгоритм найближчого міста. Це говорить про перевагу розроблених алгоритмів над обраним для порівняння наближеним алгоритмом.

Аналіз отриманих даних та наведених графіків дозволив зробити наступні висновки.

1) Для ЗК без обмеження трикутника алгоритм ЛП-Мод із зростанням розмірності задачі є більш ефективним, ніж алгоритм ЛП. Залежність відношення вартостей отримуваних розв'язків від розмірності найбільш точно можна охарактеризувати, як лінійну.

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

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

Висновки

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

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

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

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

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

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

5. Спроектовано та розроблено програмний засіб TS Explorer, в склад якого включено алгоритм Літла, алгоритм „йди до найближчого”, алгоритм „найближчого міста” та розроблені алгоритми з їх модифікаціями.

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

Результати досліджень є внеском у подальший розвиток і удоскона-лення методів розв'язання задач організації циклічних процесів, здебільшого пов'язаних з проблемами ефективної організації транспортного процесу. На практиці їх можна застосовувати у моделюванні і у проектуванні автоматизованих систем управління виробничими підприємствами, в системах управління транспортом, системах штучного інтелекту та інших. Отримані результати набули впровадження в системах автоматизованого проектування та системах керування виробництвом в Житомирському СКТБ засобів моделювання в енергетиці НАН України та в ТзОВ REC, а також застосовуються в навчальному процесі Житомирського державного технологічного університету.

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

1. Панішев А.В., Плечистий Д.Д. До питання побудови маршруту комівояжера // Вісник Житомирського інженерно-технологічного інституту. - 2002. - №20. - С. 120-124.

2. Плечистий Д.Д. Задача комівояжера: застосування, розв'язання, дослідження // Вісник Житомирського інженерно-технологічного інституту. - 2002. - №23. - С. 217-221.

3. Панишев А.В., Плечистый Д.Д., Костикова М.В. Комбинация локального поиска и схемы построения оптимальных подпоследовательностей в задачах выбора и назначения // Штучний Інтелект. - Донецьк: IПШI, 2003. - №4. - С. 25-31.

4. Панішев А.В., Плечистий Д.Д., Скачков В.О. Вузлові питання задачі комівояжера. 1 // Вісник Житомирського державного технологічного університету. - 2004. - №29. - С. 198-204.

5. Костікова М.В., Панішев А.В., Плечистий Д.Д. Вузлові питання задачі комівояжера. 2 // Вісник Житомирського державного технологічного університету. - 2004. - №30. - С. 99-108.

6. Панишев А.В., Плечистый Д.Д., Скачков В.А. Об эффективно разрешимых случаях задачи коммивояжера и их приложениях // Штучний Інтелект. - Донецьк: IПШI, 2004. - №4. - С. 169-174.

7. Панишев А.В., Плечистый Д.Д., Скакалина Е.В. Схема построения локальных оптимальных последовательностей в решении обобщений задачи о назначениях // Матеріали V Міжнар. наук.-практ. конф. „Наука і освіта - 2002”. - Дніпропетровськ: Наука і освіта, 2002. - Т.20. - С. 54-55.

8. Панишев А.В., Данильченко А.М., Плечистый Д.Д. Эффективное построение решений в задачах оптимального назначения и составления расписаний // “Искусственный интеллект - 2002”, Материалы Междунар. науч.-техн. конф. - Таганрог: Изд-во ТРТУ, 2002. - Т.1. - С. 336-339.

9. Панішев А.В., Плечистий Д.Д. Про один ефективний метод роз-в'язання проблеми комівояжера. // Проблеми математичного моделювання сучасних технологій. Міжнар. конф.: Тези доповідей. - Хмельницький: ТУП, 2002. - С. 103.

10. Плечистый Д.Д. Об одном эвристическом подходе к решению задачи коммивояжера // Материалы 7-го Междунар. молодежного форума “Радиоэлектроника и молодежь в ХХI веке”: Сб. материалов форума. - Харьков: ХНУРЭ, 2003. - С. 572.

11. Панишев А.В., Плечистый Д.Д. Развитие и совершенствование метода локального поиска в задачах оптимизации дискретных процессов // Труды четвертой междунар. науч.-практ. конф. “Современные инфор-мационные и электронные технологии”. - Одесса: ДП “Нептун-Технология”, 2003. - С. 162.

12. Panishev A.V., Plechystyy D.D. An effective exact algorithm for one particular case of the traveling-salesman problem // International Journal “Information Theories & Applications”. - 2003. - Vol.10. - P. 355-359.

13. Панишев А.В., Плечистый Д.Д. Алгоритм 3-кратной замены в методе локального поиска // Труды пятой междунар. науч.-практ. конф. “Современные информационные технологии”. - Одесса: ДП “Нептун-Технология”, 2004. - С. 118.

14. Панишев А.В., Плечистый Д.Д. Актуальные вопросы оптимизации моделей циклических процессов для задач типа коммивояжера // 10-я Юбилейная междунар. науч. конф. “Теория и техника передачи, приема и обработки информации”. Сб. Тезисов докладов. Ч.2. - Харьков: ХНУРЭ, 2004. - С. 22-23.

Анотація

Плечистий Д.Д. Моделі та ефективні методи організації циклічних процесів в класі задач типу комівояжера.

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

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

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

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

Аннотация

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

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

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

Известно, что общая (несимметричная) ЗК является NP-трудной, и не существует полиномиальных приближенных алгоритмов ее решения с ошибкой в виде константы или выражения, асимптотически близкого к . Наибольшие успехи в достижении высокой точности приближенных решений в масштабе реального времени связаны с метрической ЗК.

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

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

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

На основании данного метода предложен алгоритм построения допустимого решения . Временная сложность разработанного алгоритма , где - размерность входа ЗК.

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

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

Результаты работы внедрены в системах автоматического проектирования и системах управления производством в Житомирском СКТБ средств моделирования в энергетике НАН Украины и в ООО REC.

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

Abstract

Plechystyy D.D. Models and effective methods of organization of cyclic processes for the class of traveling salesman-like tasks. - Manuscript.

Dissertation for a candidate of technical sciences (Ph.D.) degree in speciality 01.05.02 - mathematical modeling and computing methods. - Kharkiv national university of radioelectronics, Kharkiv, 2005.

Dissertation studies models of cyclic processes and develops methods of their optimization. Aim of many of such models is to order periodically repeating job sequences in such way that optimum value of the chosen criteria is achieved. Great quantity of these ordering tasks can be transformed into well-known traveling salesman problem. Algorithmical properties of this problem make it nearly impossible to apply exact solution methods for solving tasks with input sizes given by practical demands. That's why it's important to develop effective approximate methods for solution of this problem.

In this work method of building local sequences is applied to solve general traveling-salesman problem and job-shop scheduling problem. It is shown, how achieved results can be applied in practical use.

Keywords: mathematical model, traveling salesman problem, job scheduling, combinatorial optimization, polynomial algorithm, optimal solution, path.

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

...