Повна версія

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

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


<<   ЗМІСТ   >>

Економіко-математичні моделі задачі маршрутизації

Розглянемо три постановки маршрутизації, що формулюються як спільне завдання лінійного програмування.

Перша постановка [18]. Вона розглянута в попередньому параграфі і являє собою отримання допустимих комбінацій маршрутів без прив'язки їх до автотранспортним підприємствам. Умовно назвемо цю постановку "кільцева маршрутизація" (умовність пояснюється тим, що маршрути в загальному випадку можуть бути і не кільцевими, але це не впливає ні на постановку, ні на модель, ні на методи її вирішення).

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

  • по протяжності маршрутів L s: вона може бути виражена і через час перебування автомобіля в наряді Тн; при цьому враховується час перебування рухомого складу в пунктах А i і В i під навантаженням і розвантаженням
  • по звенности маршрутів У s, іноді це залежить від конкретних умов, в яких вирішується завдання; тоді перше обмеження є більш загальним і виключає другої;
  • за кількістю вантажу, потребному до перевезення з пунктів вантаження до пунктів розвантаження, ;
  • за наявністю автомобілів в місцях їх розміщення;

Модель рухомого складу

Вид вантажу, що перевозиться

1

2, 4,5

2

1,3,5

R

1, 2, L

• щодо відповідності l-видів вантажів, що r-моделі рухомо складу: ця залежність може бути виражена двояко: або таблично, наприклад другий, четвертий і п'ятий види вантажів перевозяться на першій моделі рухомого складу, або матрично у вигляді матриці відповідності з елементами , де одиниця показує, що l -Грузія може бути перевезений на r -моделі рухомого складу, нуль - l -Грузія на r-моделі перевозитися не може;

  • по пропускній спроможності пунктів навантаження, розвантаження і розміщення рухомого складу: пропускна здатність залежить як від виду вантажу та моделей рухомого складу, так і від конкретних умов, в яких здійснюється перевізний процес (наприклад, оснащеність в механізмах пунктів навантаження і розвантаження);
  • за часом доставки вантажів в пункти розвантаження і відправлення вантажів в пунктах навантаження: іноді це обмеження можна виразити через величини пропускних спроможностей у споживачів і постачальників.

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

Повернемося до першої постановці. Повинні бути задані обсяги потрібних до перевезення вантажів від -пункт навантаження в -пункт розвантаження, , число ліній одно ; позначимо вантажопотоки індексом t, . Відома матриця відстаней пробігів без вантажу від В j-пунктів розвантаження до -пункт навантаження,; значить, можуть бути розраховані витрати, доходи, прибуток, коефіцієнт використання пробігу на маршрутах, тобто будь-який необхідний коефіцієнт (як у вартісній, так і в натуральній формах) лінійного рівняння цільової функції.

Вважаємо, що відомі технічні швидкості руху автомобілів з вантажем і без вантажу, час простою рухомого складу під навантаженням-розвантаженням; задані і такі обмеження, як час перебування автомобіля на лінії та деякі інші. Нехай {s = l: N} - безліч номерів допустимих комбінацій маршрутів. Процес формування і способи отримання цього безлічі будуть показані в подальшому. Необхідно, досягаючи оптимального значення заданої цільової функції, перевезти за маршрутами пред'явлений до постачання план

У загальному вигляді маршрут руху транспорту запишемо як послідовність певним чином з'єднаних один з одним вантажопотоків (ліній) :

або

Нехай - шукана інтенсивність на 5-маршруті або вантажопотік на s-маршруті, або кількість автомобілів, що працюють на s-маршруті; - коефіцієнти випуску, що показують, яка кількість t-вантажу перевозиться (або випускається), якщо s-маршрут має одиничну інтенсивність ; - критерії оптимальності використання з одиничною інтенсивністю s-маршруту. Тоді запишемо постановку задачі кільцевої маршрутизації:

(4.38)

де N - безліч допустимих маршрутів.

Рівності показують, що будь-який з пред'явлених до перевезення вантажів буде доставлений з пунктів в пункти в необхідному обсязі.

Якщо вимога постановки вантажів в обсязі не є строго обов'язковим, то рівності (4.38) можуть бути замінені наступними формулами:

(4.39)

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

Граничні умови:

(4.40)

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

В результаті рішення задачі (4.38) - (4.40) отримуємо оптимальні (щодо обраного для конкретного завдання критерію ) маршрути транспортування вантажів .

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

До переваг постановки кільцевої маршрутизації слід віднести можливість обліку виникають на практиці обмежень при отриманні маршрутів. В якості критерію оптимальності при формуванні маршрутів можуть бути використані будь-які показники, як натуральні, так і вартісні (наприклад, мінімізація пробігів без вантажу, максимізація прибутку і т.д.).

Недоліками даної постановки є:

  • • можливість отримання нецілочисельне рішення, тобто інтенсивності технологічних способів можуть набувати значень, нерівні цілих чисел; в разі, якщо змінні виражаються, наприклад, в автомобілях, отримання не цілих чисел рівносильно неможливості використовувати оптимальне рішення на практиці. Так, число свідчить про те, що на s-маршруті необхідно мати 2,43 автомобіля. Очевидно, що в подібних випадках округлення чисел до цілих буде приводити до погрішностей в розрахунках [1] і значних відхилень від оптимального варіанту; в подальшому буде розроблений метод досягнення цілочисельного рішення;
  • • істотно більше число змінних завдань, тобто кількість маршрутів в загальному випадку може бути досить значним: для даної постановки можливе число комбінацій маршрутів одно

де k - задане число ліній або співвідношень матеріального балансу; В - звенность s-маршрутів; область допустимих маршрутів N, як правило, дещо менше, ніж область можливих комбінацій, при цьому чим більше обмежень, висунутих практикою, тим менше число N, але все одно висловлювати матрицю коефіцієнтів "витрат-випуску" в явному вигляді не представляється можливим, тому потрібно розробка методів, що враховують матричну структуру завдання: її розрідженість (число позитивних вкрай мало) і витягнутість (число стовпців матриці значно більше, ніж кількість рядків: N> k ); в подальшому будуть описані деякі з методів вирішення завдань саме з такою структурою;

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

Друга постановка [1]. Назвемо її маршрутизацією з урахуванням обмеження рухомого складу на автотранспортних підприємствах або маршрутизацією з прикріпленням до автотранспортним підприємствам.

Вважаємо заданими вантажопотоки (t = 1: к). Вони, як і в попередній постановці, можуть бути або задані, або отримані попереднім рішенням ряду транспортних завдань: закріплення споживачів за постачальниками; матриця відстаней пробігів без вантажу від -пункт розвантаження до -пункт навантаження, ; пункти розміщення рухомого складу (k = 1: р) з наявними транспортними засобами, кількість яких може бути виражено через (в разі, якщо в -автотранспортном підприємстві є R-типів рухомого складу, то такий -пункт умовно розбиваємо на R -пункт, в кожному з яких буде знаходитися тільки один певний тип рухомого складу); матриці відстаней від -автотранспортних підприємств до -пункт навантаження, - перший нульовий пробіг від -пункт розвантаження до -автотранспортних підприємств, - другий нульовий пробіг; крім того, вважаємо відомими технічні швидкості руху рухомого складу з вантажем і без вантажу, час простою автомобілів під завантаженням і розвантаженням в пунктах і , час перебування рухомого складу на лінії та ряд інших параметрів.

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

Нехай необхідно знайти невід'ємні інтенсивності маршрутів транспортування вантажів:

(4.41)

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

(4.42)

Якщо заявлений до перевезення вантаж з пунктів і доставлений в необхідній кількості , то

і досягається оптимальне значення лінійної цільової функції

(4.43)

де - кількісний показник використання s-маршруту з шуканої інтенсивністю .

Необхідно пам'ятати, що при визначенні коефіцієнтів лінійної форми можливі різні шляхи об'їзду пунктів (а звідти і різні розміри витрат), що входять в s-маршрут, для випадку, коли . Тоді знаходимо мінімальний шлях проходження автомобіля по s-маршруту (це необхідно і для випадків, коли в якості показника приймаємо і вартісні показники). Нехай маємо маршрут, що складається з трьох ліній (В = 3) і початком в пункті навантаження , в який автомобіль подається з автотранспортного підприємства .

Можливі два шляхи прямування (рух автомобіля показано стрілками):

• перший (ріс. 4.12), де величина порожнього пробігу дорівнює

• другий (рис. 4.13), де порожній пробіг дорівнює

Тепер для визначення остаточного варіанту руху автомобіля по даному маршруту вибираємо min Очевидно, що для випадку В = 4 [2] необхідно вибирати вже з шести можливих шляхів об'їзду.

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

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

Шлях проходження 1

Мал. 4.12. Маршрут 1

Шлях проходження 2

Мал. 4.13. Маршрут 2

Послідовне, поетапне і ізольоване вирішення завдань оптимізації потоків і маршрутизації, хоча на кожному етапі при цьому і досягається найкращий варіант, як уже зазначалося, не гарантує отримання загального оптимуму при спільному функціонуванні транспортних і обслуговуються організацій. Перша спроба (описана в роботі [20]) вирішення подібної проблеми, зведеної при її формулюванні до постановки транспортної задачі лінійного програмування, дозволяла комплексно вирішувати одне завдання закріплення та маршрутизації. Але в даній постановці неможливо врахувати ряд практичних обмежень, а це є найбільш істотним недоліком. До теперішнього часу не вдалося формалізувати процес формування комбінацій маршрутів, що не дозволяє на всіх стадіях планування використовувати засоби сучасної обчислювальної техніки.

В роботі [15] була запропонована комплексна лінійна модель оптимізації поставок вантажів на автомобільному транспорті, постановка якої і дозволяє вирішувати завдання транспортної логістики. Вважаємо заданими:

  • • обсяги поставок вантажів у -пункт навантаження, позначимо їх через ( i = 1: т), в разі якщо -постачальник відпускає не один, a L видів вантажів, такий пункт умовно розбиваємо на L пунктів таким чином, щоб будь-який -пункт відвантажував тільки один вид продукції;
  • • обсяги споживання вантажів в -пункт розвантаження, позначимо їх через ( j = 1: n ); >
  • • кількість ходового рухомого складу в пунктах їх розміщення , позначимо через (А = 1: р); в разі якщо в -автотранспортном підприємстві є не один, а R-типів рухомого складу, то такий пункт умовно розбиваємо на R-пунктів так, щоб кожне -автотранспортное підприємство випускало на лінію тільки один тип автомобілів;
  • • матриці найкоротших відстаней між пунктами поставок вантажів і пунктами їх споживання - (відстані пробігів з вантажем); між -пункт розвантаження і -пункт навантаження - (відстані пробігів без вантажу); між -пункт розвантаження і -автотранспортнимі підприємствами - (відстані друге нульових пробігів); між -автотранспортнимі підприємствами і -пункт навантаження - (відстані перших нульових пробігів); - час простою під навантаженням і розвантаженням в пунктах і ; при цьому враховується, який вид вантажу і тип рухомого складу з автотранспортного підприємства знаходиться під навантаженням-розвантаженням; час перебування автомобіля на лінії і т.д., тобто практично всі можливі обмеження, що виникають при плануванні транспортно-логістичних систем.

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

(4.44)

щоб задовольнялися співвідношення матеріального балансу:

• на ходової парк рухомого складу в автотранспортних підприємствах

(4.45)

• на заявлений до постачання вантаж в пунктах навантаження

(4.46)

• на реквізит до доставки вантаж в пункти розвантаження

(4.47)

і при цьому досягалося екстремальне значення лінійної цільової функції

(4.48)

де - кількісний показник ефективності s-маршруту з одиничною інтенсивністю.

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

Постановка комплексної задачі планування перевізного процесу дозволяє:

  • • врахувати практично всі обмеження, що виникають при оперативному плануванні роботи автомобільного транспорту;
  • • вирішувати єдину комплексну задачу за єдиним критерієм оптимальності. При цьому можливо використовувати в якості критерію будь-який показник роботи автомобільного транспорту, як вартісний, так і натуральний: прибуток, загальний пробіг автомобіля, витрати, час простою під навантаженням-розвантаженням і др.;
  • • вирішуючи загальну задачу лінійного програмування, знаходити не тільки оптимальне рішення, але і отримувати значний обсяг додаткової об'єктивної інформації (двоїсті оцінки ресурсів в пунктах ), в основному пов'язаної з виявленням вузьких місць виробництва (дефіцит рухомого складу, недостатня пропускна здатність вантажно-розвантажувальних механізмів і пр.). Крім кількісної інформації, рішення дозволяє визначити, з якою величиною втрат пов'язана наявність таких вузьких місць;
  • • вирішити задачу раціонального розподілу рухомого складу (з числа наявних) за маршрутами при оперативному плануванні перевезень вантажів [12].

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

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

  • [1] Для випадку перевезень великих обсягів масових вантажів округлення значень змінних y s до цілих не приводитиме до істотних похибок.
  • [2] У загальному випадку формула визначення числа можливих шляхів слідування дорівнює (В-1)!
 
<<   ЗМІСТ   >>