Теорія оптимізації кільцевого маршруту

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

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

Маршрут руху - це шлях прямування транспорту при виконанні перевезень. Виділяють митників і кільцеві маршрути руху.

При маятниковому маршруті шлях прямування транспорту між пунктами неодноразово повторюється.

Кільцевий маршрут - це маршрут руху транспорту по замкнутому контуру, що з'єднує кілька споживачів або постачальників. Різновидами кільцевого маршруту є развозочно маршрути, збірні і збірно-развозочно.

Развозочно кільцевий маршрут - це маршрут, при якому продукція завантажується у одного постачальника і розвозить декільком споживачам.

Збірний кільцевий маршрут - це маршрут руху, при якому продукція виходить у кількох постачальників і доставляється одному споживачеві.

Збірно-развозочно кільцевий маршрут - це поєднання развозочно і збірного кільцевих маршрутів.

Організація развозочно кільцевого маршруту є однією з найбільш складних завдань транспортної логістики. При його організації з одного відправного пункту (наприклад, з оптової бази) відправляються різні товари в кілька пунктів призначення (наприклад, магазини роздрібної торгівлі) з послідовним їх відвідуванням. Метою завдання є пошук замкнутого маршруту з мінімальною транспортної роботою.

При розрахунку кільцевого маршруту вихідними даними є: 1) схема розміщення пункту відправлення та пунктів призначення, 2) відстані між ними, 3) обсяг (маса) вантажу, що поставляється в кожен з пунктів призначення, 4) місткість та вантажопідйомність виділяється для перевезення транспорту. Зазвичай вибір простий маршрут проводиться шляхом перебору всіх можливих варіантів і вибору з них оптимального. Так якщо до розрахунку приймається чотири пункти (одна база і три пункти отримання), то кількість можливих транспортних маршрутів дорівнюватиме шести.

Наприклад, якщо позначити пункт відправки А, а пункти отримання Б1. Б2. Б3. то можна вибрати один з наступних шести маршрутів:

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

Однак для 20 пунктів кількість можливих маршрутів складає вже близько 6 млн. Тому на практиці застосовуються наближені алгоритми і допускається можлива неоптимальність одержуваних рішень.

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

Порядок виконання роботи:

1. Увійти в операційну систему Windows, відкрити диск з програмами Programs Jailer Р. відкрити папку «ЛОГІСТИКА для студентів». відкрити папку «Лаб. робота 2 ». відкрити папку своєї підгрупи, скопіювати вказаний викладачем файл «ЛР2-1 Лист Microsoft Excel». Відкрити диск з програмами Programs Jailer S. відкрити папку своєї групи, відкрити свою папку і зберегти в ній скопійований файл під своїм прізвищем.

2. Робота виконується в файлі, який є книгою Excel і містить два листа:

1-й лист називається «Таблиця-матриця»;

2-й лист - «Розрахунок оптимального маршруту».

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

Контрольний варіант вихідних даних для апробування методики розрахунку представлений на 1-му аркуші (рис. 1). Наступний варіант даних для розрахунку представлений на аркуші «Вихідні дані» допомоги - його призначає керівник.

Теорія оптимізації кільцевого маршруту

Мал. 1. Схема розміщення пунктів споживання і відстані між ними

Розрахунки на 1-му аркуші «Таблиця-матриця»

На 1-му аркуші представлена ​​схема розміщення транспортних пунктів: пунктів споживання і відстаней між ними. На даному листі необхідно рассНовомосковскть три таблиці і визначити початковий базовий маршрут (три перші пункти, що мають max суму по стовпцю).

1. У відповідні комірки таблиці №1 необхідно внести основні можливі варіанти «маршрутів» у вигляді відстаней між пунктами, використовуючи функцію Excel «Підсумовування».

Таблиця, яка визначає всі можливі прилеглі відстані між пунктами кільцевого маршруту

Для цього необхідно визначити можливі варіанти проїзду з одного пункту в інший і рассНовомосковскть сумарне відстань кожного варіанту за формулою суми, використовуючи осередки з даними відстаней в схемі розміщення транспортних пунктів. При цьому варіанти проїзду вибираються тільки ті, у яких маршрути руху від пункту до пункту проходять не більше ніж через два проміжні пункти. В осередку таблиці 1 ставиться «=» і за даними схеми формується маршрут.

2. На підставі даннихтабліци №1 в таблицю №2 заносяться мінімальні відстані між пунктами схеми, використовуючи стандартну функцію визначення мінімального значення з шпальти даних (МІН): = МІН (число 1; число 2 ;.), обирається з усіх занесених в стовпці таблиці №1 варіантів маршрутів. Так якщо з пункту А в пункт Е можна доїхати трьома варіантами. З них за допомогою функції (МІН) вибирається той, який має мінімальну відстань.

В осередку відстані між i -м і i -м пунктом ставиться прочерк.

У нижній строкетабліци №2 (Разом) визначається сума відстаней за стовпцями між i -м пунктом і іншими маршрутними пунктами.

Таблиця - матриця з найкоротшими відстанями між пунктами (рассНовомосковскть

за формулою = МІН (число1; [число2] ;.))

Рядок отриманих сум автоматично переходить в таблицю №3, яка призначена для визначення базового маршруту.

Таблиця-матриця для визначення базового маршруту

Сумарні відстані і пункти по спадаючій

Підсумкові результати (з таблиці № 2)

3. Таблиця №3 заповнюється таким чином, щоб в стовпці «Відстань» суми вишикувалися в порядку спадання. А в стовпці «Пункт» навпроти кожної суми був відповідний їй пункт.

Заповнення таблиці №3

- рядок «Разом» таблиці №2 автоматично перейде в таблицю №3 в стовпець «Підсумкові результати». Дані рядка є вихідною інформацією для подальших розрахунків;

- у верхній осередку шпальти «Відстань» за формулою = МАКС (число1; число 2 ;.) визначається максимальна величина в рядку колонки «Підсумкові результати»;

- з використанням функції: = Якщо (лог_вираз; [значеніе_еслі_істіна]; [значеніе_еслі_ложь]), де істина = 0, заповнюється наступна рядок колонки «Підсумкові результати» таким чином, щоб обчислене максимальне значення стало дорівнює 0. а інші значення були перенесені без змін;

- подібним чином заповнити колонку «Відстань» і всю колонку «Підсумкові результати», при цьому в колонці «Відстань» вибудовується ланцюжок відстаней по зменшенню;

- використовуючи результати розрахунків таблиці №2 і таблиці №3, а також функцію: = Якщо (лог_вираз; [значеніе_еслі_істіна]; [значеніе_еслі_ложь]), де істина = шуканий пункт, заповнити колонку «Пункт», в якій вибудовуються пункти маршруту згідно сумарні значення рядка «Разом» таблиці №2.

Базовий маршрут складається з перших трьох пунктів, що мають максимальні сумарні значення величини маршрутів стовпчика «Відстані» (виділені в таблиці №3 жирним шрифтом). Вибрані пункти переносяться в рядок базового маршруту шляхом посилання на відповідні елементи таблиці №3.

Розрахунки на 2-му аркуші «Розрахунок оптимального маршруту»

1. Перенести результати, отримані в таблиці №2, і базовий маршрут на 2-й лист в таблицю-матрицю. визначальну мінімальні відстані між пунктами кільцевого маршруту шляхом посилань. Заповнювати слід ту частину таблиці, осередки якої вільні і не містять нулі.

Таблиця-матриця. визначальна мінімальні відстані між пунктами

Разом по рядках

Разом за стовпцями

2. Розрахункова таблиця №1 заповнюється автоматично.

Розрахункова таблиця №1

Разом з зменшенням

Разом з зменшенням

3. У базовий маршрут складається з трьох пунктів першим включається пункт, який має наступну найбільшу суму відстаней по стовпчику після перших трьох базових (4-й за рангом з таблиці №3). При цьому вирішується завдання, між якими пунктами його слід включити. Для цього визначаємо розмір збільшення маршруту # 916; L для кожної пари пунктів за формулою: # 916; L12 = L1i + Li2 - L12,

де L - відстань між пунктами, км;

i - індекс включається пункту;

1 - індекс першого пункту з пари;

2 - індекс другого пункту з пари.

Розміри збільшень знаходяться в «Таблиці для розрахунку збільшень».

Наприклад, якщо базовими були пункти А, С, В, а четвертим пунктом - пункт D, то формули розрахунку збільшень мають вигляд:

# 916; AC = AD + DC-AC; # 916; CB-CD + DB-CB; # 916; BA = BD + DA-BA.

Пункт D розміщується між пунктами, які мають найменше прирощення.

Для порівняння і вибору з отриманих значень збільшень мінімальне визначається з використанням формули: = МІН (число1; число2 ;.), яке заноситься в відповідному полі:

Мінімальним значенням є:

В результаті отримуємо новий маршрут з 4-х пунктів.

введення 5-го і 6-го пунктів здійснюється тим же способом.

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

Для розрахунку схеми наступного варіанта скопіюйте два розрахункових листа 1-го варіанту і замініть вихідні дані. Якщо все формули вірні, то результат вийде автоматично.

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