Повна версія

Головна arrow Логістика arrow Проектування логістичних систем

  • Увеличить шрифт
  • Уменьшить шрифт


<<   ЗМІСТ   >>

Моделі маршрутизації при плануванні потоків

Постановка завдання маршрутизації без урахування обмежуючих параметрів

Задані: матриця , т відстаней пробігів без вантажів між Bj-пунктами розвантаження (j = 1: п) і Ai.-пунктами навантаження ( i = I: т) (без порушення спільності завдання можна припустити, що , де -відстань пробігів з вантажем ), план перевезень вантажів , який може бути отриманий попереднім рішенням L транспортних завдань закріплення споживачів за постачальниками різних видів вантажу, число яких дорівнює L.

При цьому необхідно знайти таку послідовність поїздок з вантажем і їздець без вантажу [1] , що чергуються між собою , щоб холостий пробіг рухомого складу був би мінімальним і при цьому виконувалися наступні обмеження:

• число їздець без вантажу в Аi-пункт навантаження дорівнює числу поїздок з вантажем з Ai-пункту в В j-пункти ( ):

(4.34)

• число їздець без вантажу з В j-пункту розвантаження дорівнює

числу поїздок з вантажем в В j-пункт з пунктів :

(4.35)

(4.36)

пробіг без вантажу повинен бути мінімальний:

(4.37)

При цьому виконуються наступні умови:

У рівняннях (4.34) і (4.35) умовно вважаємо, що одна їздку здійснюється в пункт з автотранспортного підприємства (інші з пунктів ) і одна їздку виконується з пунктів в автотранспортне підприємство (решта в пункти ).

Завдання маршрутизації в такій постановці може бути вирішена двома методами: методом таблиць зв'язків [10] і методом суміщених матриць [4]. Рішення і тим і іншим методом складається з двох етапів: перший етап - вирішення завдання на мінімум пробігів без вантажу; другий етап - побудова маршрутних ланцюжків.

Перший етап - завдання (4.34) - (4.37) вирішується як транспортна задача лінійного програмування будь-яким з відомих способів. Відмінності в методах таблиць зв'язків і суміщених матриць з'являються на другому етапі рішення.

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

  • 1) таблицю зв'язків (ТС № 1), в якій записуємо заданий план перевезень вантажу ( ) на підставі пунктів в пункти ;
  • 2) таблицю зв'язків (ТС №2), в якій записуємо отриманий в результаті рішення на першому етапі план ( ) їздець без вантажу з пунктів в пункти .

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

Їздку з вантажем будемо називати пов'язаної з поїздки без вантажу, якщо індекси пункту розвантаження збігаються (g = t).

Однозвенной назвемо маршрут, в якому поїздку з вантажем вважатимемо пов'язаної з поїздки без вантажу, якщо (число ланок в маршруті позначимо через В).

Однозвенной s-маршрут назвемо замкнутим, якщо в

, I = р (рис. 4.10). На першому кроці такі маршрути назвемо маятниковими.

Послідовність формування маршрутних ланцюжків така: спочатку виписуємо плани з ТЗ № 1 і з ТС №2; формуємо всі можливі однозвенной (В = 1) пов'язані маршрути; вибираємо з них замкнуті і визначаємо величину вантажу, що перевозиться на маятникових (В = 1) s-маршрутах

; величину викреслюємо з ТЗ № 1 і ТС №2, що включають поїздки і . Одна з цих величин (або обидві) звертається в нуль:

Перший крок закінчуємо на виборі всіх можливих замкнутих однозвенной маршрутів і на відповідних змінах величин планів і в ТС №1 і ТС №2.

Замкнуте s-маршрут

Мал. 4.10. Замкнуте s-маршрут

Кільцевій s-маршрут

Мал. 4.11. Кільцевій s-маршрут

Якщо в таблицях зв'язків не всі і дорівнюють нулю, то переходимо до другого кроку. На другому кроці формуємо маршрутні ланцюжка з двох ланок (В = 2), які назвемо пов'язаними, якщо індекс пункту навантаження, що належить поїздки без вантажу першої ланки, збігається з індексом пункту навантаження, що належить поїздки з вантажем другої ланки: . Маршрутну ланцюжок з двох ланок назвемо замкнутої, якщо індекс пункту навантаження, що належить поїздки з вантажем першої ланки, збігається з індексом пункту навантаження, що належить поїздки без вантажу другої ланки (g = k ). Такі s-маршрути називають кільцевими (рис. 4.11).

Знову визначаємо величину вантажу, що перевозиться на s-марш рутах з В = 2:

На величину зменшуємо в ТС № 1 і ТС №2 всі беруть участь в отриманому маршруті поїздки.

Якщо не всі і після другого кроку дорівнюють нулю, то переходимо до третього (В = 3) і так далі кроків до тих пір, поки всі елементи в таблиці зв'язків не стануть дорівнюють нулю (очевидно, що число таких кроків не може перевищити число т, де т - кількість пунктів вантаження).

Таким чином, послідовність пар індексів назвемо k -звенним маршрутом, якщо виконані наступні умови:

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

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

Постановка завдання маршрутизації з урахуванням обмежуючих параметрів

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

1. Число В -ездкі з вантажем в одному обороті маршруту. В описаних методах теоретично , де т - число пунктів вантаження, але при перевезеннях масових вантажів у великих містах часто т = 15-20. Виконання маршрутів з таким числом ланок не представляється можливим як через обмеження тривалості перебування автомобіля на лінії, так і через збільшення числа пунктів навантаження і розвантаження на маршруті, що в свою чергу призводить до необхідності пошуків водієм нових адрес цих пунктів. Описані раніше спроби регулювати число В носять неформалізовані характер, в значній мірі суб'єктивні і практично не дозволяють оцінити похибки відхилень від оптимального плану.

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

  • 2. Нижня межа величини коефіцієнта використання пробігу на всіх одержуваних маршрутах повинна бути не нижче заздалегідь заданої . В описаних методах вирішення завдання на загальний мінімум пробігів без вантажу не гарантує в окремих випадках отримання у деяких маршрутів величини , що іноді неприпустимо в практиці планування маршрутизації перевезень деяких видів вантажів.
  • 3. Прив'язка маршрутів до автоекспортним підприємствам, так як в містах питома вага нульових пробігів в загальному пробігу автомобіля досягає 10%. В раніше описаних методах це обмеження не враховується,
  • 4. Тривалість перебування автомобіля в наряді. На внутрішньоміських перевезеннях таке обмеження має велике значення. У викладених методах це обмеження не враховується.
  • 5. Відповідність видів вантажів типам рухомого складу. У згаданих вище методах передбачається, що будь-який з вантажів плану {xij} може перевозитися на будь-якому з типів рухомого складу, що беруть участь в перевезеннях. На практиці це справедливо (в основному) для вантажів, що перевозяться автомобілями самоскидами, і ще для деяких видів вантажів. Але для багатьох вантажів (наприклад, залізобетонні вироби) неврахування даного обмеження неприпустимо і не дозволяє отримувати найкращі результати.
  • 6. Необхідність при оперативному плануванні роботи автотранспорту проводити всі розрахунки за допомогою комп'ютерів. В описаних методах (крім методу таблиць зв'язків) розрахунки на комп'ютерах здійснюються тільки для виконання першого етапу (рішення транспортної задачі на мінімум пробігів без вантажу), а другий етап (побудова маршрутних ланцюжків) через відсутність формалізованих правил виконується вручну, що є трудомістким процесом і ускладнює щоденне планування маршрутизації масових вантажів в умовах великих міст.

В роботі [5] запропонований метод вирішення задачі маршрутизації, що враховує допустимість обмежень по перерахованим вище параметрам.

  • [1] Плани { x ij} і {yij} висловлюємо в одних і тих же одиницях: тонни, автомобілі, автомобйле-їздки та ін. При розрахунках необхідно враховувати клас вантажу і величину коефіцієнта використання вантажопідйомності.
 
<<   ЗМІСТ   >>