Методика розрахунку збірних, розвізних і збірно-розвізних маршрутів методом найкоротшої зв’язуючої мережі
При перевезенні вантажів дрібними партіями транспортні машини (або поїзди), прийнявши вантаж у одного відправника, повинні розвезти його кільком одержувачам, рухаючись послідовно від одного до іншого і залишаючи певну кількість вантажу у кожного одержувача. В інших випадках транспортні машини об’їжджають кілька вантажних пунктів, збирають в кожному з них певну кількість вантажів і завозять весь цей вантаж конкретному одержувачу. Іноді одночасно виконується розвезення і збирання вантажів. Задача полягає у визначенні таких маршрутів об’їзду заданих вантажних пунктів, які забезпечують мінімум пробігу рухомого складу за цими маршрутами.
Приклад. Зі складу А (рис. А.1) доставляють вантажі в дев'ять цехів (Б-К), з яких в свою чергу необхідно повертати в цій самій тарі продукцію або порожню тару на склад. Кількість вантажних місць (ящикових піддонів), що доставляються зі складу А кожному одержувачу і вивозяться від них, надані в табл. А.1.
Рисунок А. 1 – Схема розміщення вантажних пунктів і час руху між ними (транспортна мережа)
Таблиця А.1 – Завезення і вивезення по вантажним пунктам підприємства
| Вантажний пункт | Ввезення вантажних місць | Вивезення вантажних місць |
| Б | ||
| В | ||
| Г | ||
| Д | ||
| Е | ||
| Ж | ||
| К | ||
| І | ||
| З |
Місткість однієї транспортної одиниці не більш як 30 вантажних місць. Необхідно організувати перевезення між всіма вантажними пунктами з найменшим пробігом рухомого складу. Задачу розв'язують в декілька етапів.
Етап І. Знаходять найкоротшу зв’язуючу мережу, яка об’єднує всі вантажні пункти, між якими виконуються перевезення вантажів дрібними партіями. Вводять такі поняття: всі вантажні пункти (рис. А.1)- вершини транспортної мережі; лінії, що з’єднують дві сусідні вершини - ланки; незамкнута мережа, що зв’язує дві і більше вершини з мінімальною сумарною довжиною всіх з’єднуючих ланок - найкоротша з’єднуюча мережа, яку визначають так.
На транспортній мережі знаходять найменшу ланку. У даному прикладі – це ланка І-3 = 4 хв. Потім розглядають всі ланки, зв’язані однією зі своїх вершин з вибраною ланкою, тобто ланки К-І = 5; А-І = 15; Е-І = 6; Е-З = 8; Ж-3 = 6; К-3 = 6. З них вибирають ланку з найменшим часом руху. Такою ланкою є К-І = 5. Далі розглядають ланки, зв'язані з вершинами отриманої лінії (К-І-3), і з них вибирають найменшу. При цьому не можна вибирати ланку, що з’єднає дві, раніше включені в мережу вершини. Така ланка в даному прикладі – ланка З-К. Іншими ланками, зв’язаними своїми вершинами з раніше вибраною мережею, є ланки А-К = 15; А-І = 15; Е-І = 6; Е-3 = 8; Ж-3 = 6, при цьому ланки Е-І та Ж-3 мають однакові найменші значення. З них можна вибрати будь-яке. Як найменшу вибираємо ланку Е-І і отримуємо мережу, яка включає в себе пункти К-І-З-Е. Далі знову розглядають всі ланки, зв’язані з вершинами отриманої гілки, і з них вибирають найменшу. Таким чином вибирають всі вершини мережі. Найкоротша зв’язуюча мережа даного прикладу показана на рис. А. 2. На схемі найкоротшої зв’язуючої мережі рекомендується проставляти біля кожного вантажного пункту кількість завезених (чисельник) і вивезених (знаменник) вантажних місць.
Рисунок А. 2 – Схема найкоротшої зв’язуючої мережі
Етап ІІ. Виконують набір вантажних пунктів у маршрути. Виділяють гілку у мережі, в якій найбільша кількість ланок і, починаючи з дальньої ланки, групують пункти в маршрут з урахуванням кількості ввезених та вивезених вантажних місць та місткості одиниці транспортного засобу.
Якщо всі пункти розглянутої гілки не можуть бути включені в один маршрут, найближчі до другої гілки пункти групують разом з її пунктами. Виходячи з умов даного прикладу, пункти зазначені на рис. А.2, можна згрупувати так, як показано в табл. А.2. Пункт Ж не ввійшов у маршрут, оскільки транспортна одиниця не могла б прийняти його вантажні місця, оскільки він розміщений поряд з другою гілкою мережі.
Етап ІІІ. Визначають черговість об’їзду пунктів маршруту. На цьому етапі зв’язують всі пункти маршруту (табл. А.2.) починаючи зі складу А, замкнутою лінією, який відповідає найкоротший час об’їзду цих пунктів. Рекомендується застосовувати метод сум. При розрахунку за цим методом спочатку будують таблицю, яку називають симетричною матрицею (для маршруту №1 вона наведена в табл. А.3). По головній діагоналі в таблиці розміщені пункти, що включаються у маршрут. Числа показують найменший час прямування рухомого складу між цими пунктами. В матриці є підсумковий рядок “Рядок сум”, в якому проставляють суму часу по кожному стовпцю.
Таблиця А.2 – Групування вантажних пунктів у маршрути
| Вантажний пункт | Ввезення вантажних місць | Вивезення вантажних місць |
| Маршрут № 1 | ||
| К | ||
| І | ||
| З | ||
| Е | ||
| Разом | ||
| Маршрут №2 | ||
| Ж | ||
| Д | ||
| Г | ||
| В | ||
| Б | ||
| Разом |
Таблиця А.3 – Симетрична матриця для маршруту №1
| А | ||||
| К | ||||
| З | ||||
| І | ||||
| Е | ||||
Після будови симетричної матриці будують початковий маршрут трьох пунктів, що мають максимальну суму по своїх стовпцях. Якщо існує кілька пунктів з однаковими максимальними сумами, для першого початкового маршруту вибирають будь-який з них. Для даного прикладу (див. табл. А.3) максимальні суми мають стовпці пунктів А,К,З. Приймають як початковий маршрут АКЗА. Потім в нього включають наступний пункт з максимальною сумою. В даному прикладі – пункт Е. Цей пункт слід вставити між такою парою сусідніх пунктів початкового маршруту, де приріст часу Dt руху рухомого складу буде мінімальним. Значення цього приросту знаходять за формулою
Dt кр = tki + tip - tkp® min,
де t – час, хв.;
k, p, і – пункт відповідно перший сусідній, другий сусідній та включений.
Для сусідніх пунктів АК
Dt AK = tAE + tEK - tAK
Існуючі відстані будемо брати з табл. А.3:
Dt AK = 10 + 11 – 15 = 6
Для сусідніх пунктів КЗ
Dt KЗ = 11 + 8 - 6 =13
Для сусідніх пунктів ЗА
Dt ЗА =8 + 10 - 18 = 0.
В даному прикладі мінімальним приростом є Dt ЗА, тому отримуємо маршрут АКЗЕА. Далі за табл. А.3 знаходять наступний, що не беруть до уваги, пункт з максимальною сумою часу по стовпцю (пункт 1). Подальші розрахунки виконують аналогічно:
Dt AK = 15 + 5 – 15 = 5;
Dt ЗА = 5 + 4 – 6 = 3;
Dt ЗЕ = 4 + 6 – 8 = 2;
Dt ЕА = 6 + 15 – 10 = 11.
Найменший час - Dt ЗЕ , тому пункт І включають між ЗЕ і отримують маршрут АКЗІЕА. Не включених пунктів більше немає, отже маршрут АКЗІЕА остаточний. Час руху за маршрутом за оборот
tpо = 15 + 6 + 4 + 6 + 10 = 41 хв.
Можна твердити, що знайдена черговість об’їзду вантажних пунктів маршруту дає мінімальний або досить близький до мінімального час руху.
Далі виконують розрахунки за маршрутом № 2. Будують симетричну матрицю (табл. А.4).
Таблиця А.4 – Симетрична матриця для маршруту № 2
| А | |||||
| Б | |||||
| В | |||||
| Г | |||||
| Д | |||||
| Ж | |||||
В матриці максимальні суми мають стовпці пунктів А, Ж і Б. Беруть за початковий маршрут АЖБА. Наступний маршрут з максимальною сумою по стовпцю – це В. Визначають, між якими пунктами початкового маршруту слід встановити пункт В:
Dt AЖ = 20 + 13 – 16 = 17;
Dt ЖБ = 13+ 5 – 17 = 1;
Dt БA = 5 + 20 – 14 = 11.
Розрахунок показав, що пункт В слід вставити в маршрут між пунктами ЖБ. В результаті отримаємо маршрут АЖВБА. Наступним пунктом з максимальною сумою по стовпцю в табл. А.4 буде пункт Д. Визначають, між якими пунктами його вставити:
Dt AЖ = 14 + 7 – 16 = 5;
Dt ЖВ = 7 + 6 – 13 = 0;
Dt ВБ = 6 + 11 – 5 = 12;
Dt БA = 11 + 14 – 14 = 11.
Мінімальний приріст часу /нуль/ буде, якщо в маршруті пункт Д вставити між пунктами ЖВ. Отже, отримаємо маршрут АЖДВБА.
Залишається визначити, куди вставити пункт Г:
Dt AЖ = 8 + 8 - 16 = 0;
Dt ЖД = 8 + 6 – 7 = 7;
Dt ДВ = 6 + 6 – 6 = 6;
Dt ВБ = 6 + 9 – 5 = 10;
Dt БA = 9 + 8 – 14 = 3.
Розрахунок показав, що пункт Г слід вставити між пунктами А і Ж.
Таким чином, отриманий остаточний маршрут об’їзду: АГЖДВБА. Час руху по маршруту за оборот
Dt РО = 8 + 8 + 7 + 6 + 5 + 14 = 48 хв.
Схеми рухомого складу за розрахованими маршрутами показані на рис. А.3.
У тих випадках, коли маршрути тільки складені або тільки розвізні, на цьому розрахунки закінчуються. Якщо ж маршрути складено-розвізні (як в даному випадку), слід виконати четвертий етап розрахунку.
Етап IV. Визначити можливість одночасного розвезення і складання вантажних місць на маршруті. Ця перевірка викликана тим,
Рисунок А. 3 – Схема маршрутів №1 і №2
що місткість рухомого складу обмежена. За отриманим розв’язком маршрут №1 має таку послідовність об’їзду вантажних пунктів: АКЗІЕ-А.
Перевіряють, яка кількість вантажних місць буде на одиниці рухомого складу протягом всього маршруту, за допомогою таблиці, в якій вантажні пункти маршруту перебувають у послідовності, отриманій за розрахунком, і дається розрахунок наявності вантажних місць на одиниці рухомого складу після навантаження і розвантаження в кожному пункті (табл. А.5). Береться, що з початкового пункту рухомий склад завантажений повністю ( в даному прикладі 30 вантажних місць).
Таблиця А.5 – Наявність вантажних місць на одиниці рухомого складу за маршрутом № 1
| Вантажний пункт | Кількість вантажних місць | ||
| Прибуло | Відправлено | Всього | |
| А | - | ||
| К | |||
| З | |||
| І | |||
| Е |
При заповненні табл. А.5 видно, що починаючи з вантажного пункту З, рухомий склад не вміщує всі вантажні місця. Одним з виходів із такого становища є зміна напрямку руху на маршруті.
Змінюючи напрям руху на маршруті № 1, отримаємо послідовність об’їзду АЕІЗК-А. При заповненні табл. А.6 видно, що зміна напрямку дозволяє виконати весь обсяг перевезень за маршрутом № 1, не перевищуючи місткість рухомого складу.
Таблиця А.6 – Наявність вантажних місць на одиниці рухомого складу після зміни напрямку руху
| Вантажний пункт | Кількість вантажних місць | ||
| Прибуло | Відправлено | Всього | |
| А | - | ||
| Е | |||
| І | |||
| З | |||
| К |
Перевіряють маршрут № 2, заповнюючи табл. А.7, з якої видно, що на протязі всього маршруту рухомий склад перевантажений не буде.
При організації збірно-розвізних маршрутів виникають ускладнення та спеціальні вимоги, наприклад:
1) існують випадки, коли для запобігання перевантажень рухомого складу змінюють напрям руху на маршруті, однак позитивного результату не досягають;
2) іноді в деяких вантажних пунктах складально-розвізного маршруту виникає необхідність спочатку тільки вивантажити вантажні місця, а потім на зворотному шляху вантажити їх. Цей захід звичайно дуже спрощує навантажувально-розвантажувальні роботи й скорочує нераціональний пробіг рухомого складу під навантаженням.
Таблиця А.7 – Наявність вантажних місць на одиниці рухомого складу за маршрутом № 2
| Вантажний пункт | Кількість вантажних місць | ||
| Прибуло | Відправлено | Всього | |
| А | - | ||
| Г | |||
| Ж | |||
| Д | |||
| В | |||
| Б |
Для усунення перелічених ускладнень й дотримання певної черговості навантажувально-розвантажувальних робіт змінюють початок маршруту: за найкоротшою зв’язуючої мережею (див. рис. А.2) вибирають один або кілька вантажних пунктів для повторного заїзду, які повинні лежати на одному маршруті, на одній гілці і до них повинен бути мінімальним час руху від базового пункту (складу) А. Найвіддаленіший із вибраних пунктів беруть за початок маршруту. Для розрахунку маршруту в симетричну матрицю не включають пункт А і всі пункти, вибрані для повторного заїзду. В матрицю включають останні пункти маршруту і пункт, вибраний за початок маршруту.
Порядок складання симетричної матриці і розрахунків залишається таким самим, як описувалося раніше. Покажемо це на прикладі маршруту № 1.
Припустимо, що при об’їзді маршруту № 1 треба повторно заїхати в пункти Е і І. За рис. А.2 і А.3 можна впевнитися, що вони лежать на одній гілці і до них мінімальний час руху від базового пункті А. Найвіддаленіший з них пункт І береться за початок маршруту. Будують симетричну матрицю (табл. А.8), в яку включають пункти І і Е.
Таблиця А.8 – Симетрична матриця при зміні маршруту
| І | ||
| З | ||
| К | ||
Після побудови матриці слід побудувати початковий маршрут з трьох пунктів (див. Етап ІІІ розрахунків). В матриці їх залишилося всього тільки три, отже, додаткових розрахунків не потрібно. Маршрут ІЗКІ буде і початковим і остаточним.
Тепер можна записати маршрут з урахуванням повторного заїзду в пункті: з обох сторін шифру остаточного маршруту (ІЗКІ)підставляють найменування (букви) на початку вантажного пункті, що лежить між пунктами базовим і початку маршруту, а потім – базового. Для даного випадку маршрут запишеться у вигляді шифру: АЕІЗКІЕ-А (рис.А.4). Час руху на маршруті за оборот становить 47 хв.
Перевіряють отриманий маршрут за завантаженням рухомого складу (табл. А.9). Перевантаження не спостерігаються, отже, маршрут АЕІЗКІЕ-А підходить.
Рисунок А. 4 – Схема маршруту №1 із повторним заїздом
у пункти Є і І
Таблиця А.9 – Наявність вантажних місць на одиниці рухомого складу при повторному заїзді в пункти ЕІ
| Вантажний пункт | Кількість вантажних місць | ||
| Прибуло | Відправлено | Всього | |
| А | - | ||
| Е | - | ||
| І | - | ||
| З | |||
| К | |||
| І | - | ||
| Е | - |
Додаток Б