Задача про складанні маршруту комівояжера. Метод гілок і меж

Задача про складання маршруту комівояжера. Метод гілок і меж

Введення

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

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

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

Метою даної роботи буде:

1. Познайомити читача з основними поняттями теорії графів.

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

3. Описати метод гілок і меж.

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

1. Постановка завдання

Комівояжер (Бродячий торговець) повинен вийти з першого міста, відвідати по разу в невідомому порядку міста 2,3,4 ... n і повернутися в перший місто. Відстані між усіма містами відомі. У якому порядку слід обходити міста, щоб замкнутий шлях комівояжера був найкоротшим? У термінах теорії графів: знайти гамільтонів цикл в графі мінімальної довжини.

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

Одним з підходів до її рішенням є скорочення перебору методом гілок і меж. Цей метод дозволяє пізнати безперспективні часткові рішення, в результаті чого від дерева пошуку на одному кроці відсікається ціла гілка. Тим не менш, задовільних оцінок швидкодії алгоритму Літтла, заснованого на цьому методі, і родинних алгоритмів немає, хоча практика показує, що на сучасних ЕОМ вони іноді дозволяють вирішити задачу комівояжера для графів з кількістю вершин, меншим 100.

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

2. Огляд інших методів рішення задачі комівояжера

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

3. Теорія графів

3.1 Основні поняття теорії графів. Визначення

Граф G задається безліччю точок або вершин x 1 , x 2 , ... x n (яке позначається через X) і безліччю ліній або ребер a 1 , a 2 , ... a m (яке позначається символом А), що з'єднують між собою всі або частину цих точок. Таким чином, граф G повністю задається парою (X, A).

Якщо ребра з множини А орієнтірованни, що зазвичай показується стрілкою, то вони називаються дугами, і граф з такими ребрами називають орієнтованим графом. Інше, вживане частіше опис орієнтованого графа G полягає у завданні безлічі вершин Х і відповідності Г, яке показує, як між собою пов'язані вершини. Граф в цьому випадку позначається парою G = (X, Г).

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

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

Іноді дугам графа G зіставляються (приписуються) числа - дузі (x i , x j ) ставиться у відповідність деяке число c i j , зване вагою, або довгою. Тоді граф G називається графом зі зваженими дугами. Іноді ваги приписуються вершин x i графа, і тоді виходить граф зі зваженими вершинами. Якщо в графі ваги приписані і дуг, і вершин, то він називається просто виваженим. При розгляді шляху, представленого послідовністю дуг, за його вага (або довжину) приймається число, рівне сумі ваг всіх дуг, що входять в, тобто .

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

комівояжер граф завдання метод

Якщо G = (X, A) - неорієнтований граф з n вершинами, то Остовним деревом (або, коротше, остовом) графа G називається всякий остовного підграф G, що є деревом (тобто графом які не мають циклів, в якому кожна пара вершин з'єднана однією і тільки однією простою ланцюгом). Наприклад, якщо G - Граф, показаний на мал. 1а, то графи на мал. 1.б, в є остовом цього графа.

3.2 Завдання комівояжера

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

Постановка завдання. Комівояжер (бродячий торговець) повинен вийти з першого міста, відвідати по разу в невідомому порядку міста 2,3,4 ... n і повернутися в перший місто. Відстані між усіма містами відомі. У якому порядку слід обходити міста, щоб замкнутий шлях комівояжера був найкоротшим? У термінах теорії графів: знайти гамільтонів цикл в графі мінімальної довжини.

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

Рішення узагальнено...ї задачі комівояжера

Нехай кожній дузі (i, j) графа (I, U) поставлено в відповідність число зване довжиною дуги.

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

Визначимо функцію: покладемо для довільного шляху. Отже, значеннями функції будуть безлічі номерів підмножин розбиття, які перетинає шлях. Нехай кожне безліч Ф i ,, складається з усіляких підмножин множини {1, 2, ..., p}, a. Застосуємо для вирішення цієї задачі наступний алгоритм.

Достатньою системою функцій в даному випадку будуть функції

Позначимо через число елементів довільного кінцевого безлічі А.

Крок 0. Покладемо. Пометим вершини ознаками. Для помічених вершин збільшимо на 1. Розглянемо одну з позначок і перейдемо до кроку 1.

Крок 1. Нехай - розглянута позначка. Пометим ознаками всі ті вершини, для яких. Для знову помічених вершин збільшимо на 1.

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

Крок 2. Будуємо найкоротший допустимий шлях від вершини. Нехай - позначка вершини, для якої. Перейдемо до вершини і розглянемо позначку вершини,

для якої. Далі перейдемо до вершини, з позначкою, для якої. Послідовність і є найкоротшим допустимим шляхом.

Крок 3. Нехай - множина помічених вершин. Розглянемо всі можливі числа при . Визначимо серед цих чисел найменше і візьмемо його за нове наближення до довжині шуканого шляху. Потім перейдемо до кроку 1.

Цей алгоритм можна змінити. Якщо для деякої позначки при всіх j, для яких або, то шлях відповідний цій позначці, вже продовжено у всі суміжні з вершини. Отже, для таких позначок ознаки можна прати.

3.3 Метод гілок і меж (МВГ)

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

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

Опис методу гілок і меж

Нехай х 1 - Центр куба Х. Обчислюємо та присвоюємо це значення рекорду. Розбиваємо куб Х 1i зі стороною ВЅ і обчислюємо значення цільової функції в їх центрах:, i = 1, ... 2 n , оновлюючи по ходу обчислень значення рекорду. Перевіряємо виконання умови для i = 1, ..., 2 n і відкидаємо відповідні подкуби. Кожен з решти розбиваємо на 2 n однакових подкубов Х 2 ij зі стороною Вј і поступаємо як раніше. На будь-якому кроці у нас формується безліч До В«кубиківВ» зі сторонами 2 - l , l> = 2, ціле. Правило вибору чергового кубика для розбиття називається правилом розгалуження - можливі варіанти наводяться нижче. Кубики із стороною не більше виключаються з безлічі К - дроблення кубика закінчується. Також виключаються кубики, потрапили в безліч (з індексом k - номером кубика) для поточного значення рекорду, - правило відсікання гілок. Рекорд оновлюється при отриманні меншого значення цільової функції (правило отримання кордонів, тобто оцінок). Значення цільової функції обчислюються в центрі кожного нового подкубіка, що включається до До після розбиття обраного для цього кубика. Алгоритм зупиняється, коли До порожньо.

Рис. 2. Граф-дерево

Зазначена термінологія і назва методу визначаються тим, що візуально дана схема перебору представляється у вигляді графа-дерева, коренева вершина якого відповідає кубу Х, вершини першого ярусу - подкубам X li , вершини другого ярусу - кубикам X 2 li , приєднаним до своїх породжує вершин X li -го ярусу, і т.д. (Див. рис. 2). Якщо кубик виключається з К, його вершина закривається - з неї не будуть йти гілки на наступний ярус. Порядок закриття вершини визначається правилом відсікання (своїм для кожної масової завдання), порядок розкриття - правилом розгалуження (своїм для кожної індивідуальної задачі). Розрізняють два види правил розгалуження за типом побудови дерева рішень (вибору вершин для розкриття): В«в ширину В», коли спочатку розкриваються всі вершини одного ярусу до переходу до наступного, і в В«глибинуВ» - щоразу розкривається лише одна (звичайно з кращим значенням рекорду) вершина на ярусі до кінця гілки. На практиці реалізують деяку суміш, наприклад, перше правило поки вистачає машинної пам'яті (в К не надто багато елементів), потім перемикаються на друге. Перевагу тієї чи іншої стратегії розгалуження оцінюється кожним обчислювачем по-своєму, виходячи з головного завдання методу гілок і меж - швидше отримати кращий рекорд, щоб відсікти більше гілок. Вдалий вибір стратегії розгалуження в МВГ (наприклад, на основі наявної в обчислювача додаткової інформації або евристичних міркувань про об'єкт) дозволяє (хоча і не гарантовано) вирішувати задачі великої розмірності.

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

4. Вибір об'єкта управління. аналіз аспектів його роботи

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

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

5. Постановка і рішення оптимізаційної задачі

5.1 Вибір критерію оптимальності

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

Перерахуємо основні економічні показники, пов'язані з роботою робота:

1. Прямі витрати

1.1 Одноразові - По доставці машин.

1.2 Амортизаційні суми.

2. Накладні витрати. Заробітна плата робітників.

3. Умовно-постійні витрати.

Зміст службових приміщень.

Пожежної і сторожової охорони.

Побутове благоустрій цеху і підсобних приміщень.

Витрати, пов'язані з технікою безпеки.

4. Непрямі витрати.

Витрати на утримання обслуговуючого персоналу.

Ремонтних майстерень. Витрати на ремонт.

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

Таким чином, слід по можливості скоротити шлях, прохідний роботом.

Отже, задачу зменшення грошових витрат ми звели до задачі пошуку шляху мінімальної довжини. Маємо задачу комівояжера.

5.2 Виявлення основних особливостей розглянутого об'єкта

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

Таблиця 1.

1 2 3 4 5 1 * 4 2 5 2 * 1 9 3 * 3 4 4 * 11 5 *

5.3 Приклад рішення задачі комівояжера

Маємо В«чистоВ» математичну задачу, яку вирішимо, використовуючи метод гілок і меж.

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

Крок 0. Значення. Пометим вершину 1 ознакою

Крок 1. Пометим вершину 3 ознаками

Рис. 3. Крок З. Маємо.

Крок 1. Пометим наступні вершини: вершину 4 - ознаками вершину 5 - ознаками

Крок 3. Маємо.

Крок 1. Пометим вершину 5 ознаками

Крок 3. Маємо.

Крок 1. Пометим вершину 3 ознаками

Крок 3. Маємо.

Крок 1. Пометим вершину 4 ознаками

Крок 1. Пометим вершину 2 - ознаками так як, то шуканий шлях побудований.

Крок 2. Шуканий шлях складає послідовність вершин 1, 5, 3, 4, 2.

Загальне витрачається час в дорозі складе 13.

Висновки

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

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

Список літератури

1. М. 1998.

2.

3. М. 1969.

4. ім.

5.