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

У задачі комівояжера для формування оптимального маршруту об'їзду n міст необхідно вибрати один кращий з (n-1)! варіантів за критерієм часу, вартості або довжині маршруту. Це завдання пов'язана з визначенням Гамільтона циклу мінімальної довжини. У таких випадках безліч всіх можливих рішень має бути поданий у вигляді дерева - зв'язного графа, що не містить циклів і петель. Корінь дерева об'єднує всі безліч варіантів, а вершини дерева - це підмножини частково впорядкованих варіантів рішень.

Інструкція. Виберіть розмірність матриці (кількість міст). Отримане онлайн рішення зберігається в файлі Word і Excel (див. Приклади рішень задачі комівояжера).

Математична модель задачі комівояжера

Сформульована задача - завдання целочисленная. Нехай хij = 1. якщо мандрівник переїжджає з i -ого міста в j-ий і хij = 0. Якщо це не так.
Формально введемо (n + 1) місто, розташоване там же, де і перше місто, тобто відстані від (n + 1) міста до будь-якого іншого, відмінного від першого, рівні відстаням від першого міста. При цьому, якщо з першого міста можна лише вийти, то в (n + 1) місто можна лише прийти.
Введемо додаткові цілі змінні, рівні номеру відвідування цього міста на шляху. u1 = 0, un + 1 = n. Для того, щоб уникнути замкнутих шляхів, вийти з першого міста і повернутися в (n + 1) введемо додаткові обмеження, що зв'язують змінні xij і змінні ui. (Ui цілі невід'ємні числа).


ui -uj + nxij ≤ n-1, j = 2..n + 1, i = 1..n, i ≠ j, при i = 1 j ≠ n + 1
0≤ ui ≤ n, xin + 1 = xi1. i = 2..n

Методи розв'язання задачі комівояжера

1. метод гілок і меж (алгоритм Літтла або виключення підциклів). Приклад рішення методом гілок і меж;
2. угорський метод. Приклад рішення угорським методом.

Приклад. В якості початкового маршруту вибирається будь-який, наприклад, X0 = (1,2); (2,3); (3,4); (4,5); (5,6); (6,1). Оцінка для цього маршруту дорівнює F (X0) = 43 + 65 + 73 + 22 + 8 + 80 = 291. Для визначення нижньої межі безлічі використовують операцію редукції. для чого в кожному рядку матриці D знаходять мінімальний елемент: di = min (j) dij

Сума констант приведення визначає нижню межу H = Σdi + Σdj = 9 + 52 + 13 + 17 + 8 + 10 + 0 + 20 + 0 + 5 + 0 + 0 = 134. Елементи матриці dij відповідають відстані від пункту i до пункту j. Довжина маршруту визначається виразом: F (Mk) = Σdij. Причому кожен рядок і стовпець входять в маршрут тільки один раз з елементом dij.

Потім в ході подальших ітерацій, визначається ребро розгалужень. Всі безліч маршрутів щодо цього ребра розбивається на дві підмножини (i, j) і (i *, j *).