Складання маршрутів руху автомобільного транспорту
Правильна маршрутизація руху транспорту справляє суттєвий вплив на загальну величину транспортних витрат. Складність складання раціональних маршрутів залежить від взаємного співвідношення місткості транспортного засобу і середньої величини обсягу однієї відправки вантажу. Чим менше середній обсяг однієї відправки вантажу щодо місткості використовуваного транспортного засобу, тим складніше пошук раціонального маршруту розвезення. В даному параграфі розглянемо один з методів маршрутизації перевезень у разі, коли середній обсягу однієї відправки вантажу істотно менше місткості транспортного засобу. У даному випадку застосовуються, так звані кільцеві маршрути руху транспорту.
Складання кільцевих маршрутів в першому наближенні може здійснюватися методом, відомим як алгоритм Свира або алгоритм двірника-склоочисника (рис. 60). Задамо становище споживача матеріального потоку в полярній системі координат. Полюс системи - точку 0, розмістимо в місці дислокації розподільчого складу. Виберемо початкове, нульове положення полярної осі φ=0. Становище споживача визначається відстанню від центру і кутом φ, який утворений полярною віссю, тобто променем, що виходить з точки 0 і спрямованим на споживача.
Примітка: Цифрами на малюнку зображені споживачі матеріального потоку
Рис. 60. Декомпозиція транспортної мережі при складанні маршрутів розвезення (метод Свира)
Суть алгоритму Свира полягає в тому, що полярна вісь, подібно щітці двірника-склоочисника, починає поступово обертатися проти (або) годинникової стрілки, "стираючи" при цьому з координатного поля зображені на ньому магазини - споживачі матеріального потоку. Як тільки сума замовлень "стертих" магазинів досягне місткості транспортного засобу, фіксується сектор, що обслуговується одним кільцевим маршрутом, і намічається шлях об'їзду споживачів.
Слід зазначити, що даний метод дає хороші результати на евклідової транспортної мережі, тобто в тому випадку, коли відстань між вузлами транспортної мережі по існуючих дорогах прямо пропорційно відстані по прямій.
На кільцеві маршрути крім обмежень по місткості можуть накладатися додаткові вимоги, наприклад, обмеження по часу. Якщо виявиться, що час руху за певним кільцевому маршруту більше допустимого, необхідно цей сектор зменшити, збільшивши відповідно сусідній сектор. Необхідні зменшення сектору виконуються і при наявності інших обмежень.
Побудова наступного сектора починається лише після того, як в цьому секторі буде отримано допустимий кільцевий маршрут. Формування кільцевих маршрутів завершується при повному обороті "стираючого магнітного" променя.
Алгоритм Свира дозволяє розділити всю зону, що обслуговується, на кілька секторів. У межах кожного сектору складання кільцевого маршруту може здійснюватися за допомогою вирішення різних оптимізаційних задач, в тому числі і задачі комівояжера.