Знаходження розв’язку задачі комівояжера методом осереднених коефіцієнтів

Розв’язок задачі комівояжера, за методом осереднених коефіцієнтів, та ксамо, як і за методом редекції рядків і колонок, ділиться на (n-2) етапи (у межах кожного етапу, алгоритм розрахунків однаковий).

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

Рис. 1. Тарифи на переміщення між містами.

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

Метод осереднених коефіцієнтів — Рис. 2. Середні тарифи рядків і колонок.

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

Рис. Таблиця коефіцієнтів обчислених на першому етапі — Рис. 3. Таблиця осереднених коефіцієнтів обчислених на першому етапі.

Серед знайдених осереднених коефіцієнтів вибираємо найменший. В нашому випадку таким є коефіцієнт, який міститься в 5-му рядку і у 3-й колонці і значення якого рівне -81,2. Тобто, в шлях комівояжера заносимо маршрут (5,3) і перехоимо до другого етапу.

Перш ніж приступити до другого етапу, викреслюємо з таблиці тарифів (Рис. 1) п’ятий рядок і третю колонку з розгяляду, а також зробимо комірку (3,5) забороненою. Дану комірку ми зробили забороненою виходячи з того, що у будь-якому рядку і у будь-якій колонці таблиці комівояжера повинна існувати одна заборонена комірка, в нашому випадку, такої комірки немає у рядку i=3 та колонці j=5 .

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

Знову серед знайдених коефіцієнтів вибираємо той, значення якого є найменшим. Тобто, коефіцієнт, який міститься в 2-му рядку і у 5-й колонці (значення якого рівне -59,25). В шлях комівояжера заносимо маршрут (2,5), викреслуємо другий рядок та п’яту колонку з розгляду і перехоимо до етапу під номуром три.

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

Рис. 5 Таблиця коефіцієнтів обчислених на третьому етапі — Рис. 5. Таблиця осереднених коефіцієнтів обчислених на третьому етапі.

Найменше значення коефіцієнтів становить – 47,7. Отже, заносимо в шлях комівояжера маршрут (1,2) після чого викреслюємо з розгляду перший рядок і другу колонку. В результаті ми отримали таблицю, яка містить два рядки і дві колонкт. На цьому алгоритм припиняється, бо дана таблиця вказує завершальний шлях комівояжера (3,4) і (4,1).

Рис. 6 Завершальний маршрут комівояжера — Рис. 6. Завершальний маршрут комівояжера.

Таким чином, оптимальний маршрут комівояжера рівний:

витрати на який становлять 310 умовних одиниць.

Залишити коментар