Алгоритм Свіра

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

Цифрами на рисунку зображені споживачі матеріального потоку

Рис. 1 – Декомпозиція транспортної мережі при складанні маршрутів розвезення (метод Свіра)

Суть алгоритму Свіра полягає в тому, що полярна вісь, подібно щітці двірника-склоочисника, починає поступово обертатися проти (чи за) годинною стрілкою, "стираючи" при цьому з координатного полю зображені на ньому магазини — споживачі матеріального потоку. Як тільки сума замовлень "стертих" магазинів досягне місткості транспортного засобу, фіксується сектор, що обслуговується одним кільцевим маршрутом, і намічається шлях об’їзду споживачів.

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

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

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