Реферат за темою випускної роботи

Зміст

Вступ

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

Оптимізувати можна практично будь-який елемент транспортно-логістичної системи, тому, спектр робіт в рамках даного напрямку дуже широкий [1]

Далі наведено не повний перелік можливих оптимізацій:

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

1. Актуальність теми

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

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

2. Мета, задачі дослідження та заплановані результати

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

Основні задачі дослідження:

  1. формалізація задачі поставок з розширеним функціоналом, за рахунок різних груп вимог;
  2. проаналізувати існуючі методи вирішення подібних задачі;
  3. розробити або вдосконалити існуючі методи розв'язання задачі і адаптувати їх до потрібних умов;
  4. реалізація розробки у вигляді алгоритму на програмному мовою;
  5. аналіз результатів з проведенням оцінки складності алгоритму.

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

Предмет дослідження: швидкодія і функціональність підсумкового програмного продукту.

3. Огляд досліджень та розробок

Кількість робіт за темами досліджуваної області зростає як в національних, так і зарубіжних журналах та інтернет-ресурсах.

3.1 Огляд зарубіжних джерел

Залежно від умов утримання і складного графіка роботи клієнтів можуть виникати додаткові проблеми. Так, в своїй роботі Метод розшифровки із застосуванням алгоритму ройового інтелекту для вирішення проблеми маршрутизації в логістиці транспортних засобів холодного ланцюга [2] Сяолі Лян, разом зі співавторами, розглянув алгоритм ройового інтелекту для оптимізації розподілу транспортних засобів в логістиці холодного ланцюга. Так само, в статті був описаний авторський підхід до визначення послідовності обслуговування клієнтів з подальшою оцінкою його продуктивності.

Залежно від завантаженості транспортних умов виникає необхідність в особливих підходах до дистрибуції товарів. У своїй статті Оптимізація міської логістичної транспортної системи зі змішаними пасажирами і вантажами [3] Рено Массон і його співавтори розробили модель, в якій транспортування вантажу поєднується з перевезенням пасажирів на автобусах із заданим маршрутом. Автори розглянули можливі проблеми і розробили рішення для них. Слід зазначити, що в статті розглянуті чисто детерміновані дані.

3.2 Огляд національних джерел

Під час вивчення національних джерел знайдено безліч статей, спрямованих на зменшення витрат за рахунок розробки моделей і методів вирішують певні транспортні задачі. Так, наприклад, Костюк Ю.Л. і Пожидаєв М.С. в своїй статті Збалансована евристика для вирішення завдання маршрутизації транспорту з урахуванням вантажопідйомності [4] запропонували евристичний алгоритм для вирішення завдання маршрутизації транспорту. Борхані І.Ф. і Фазилов Б.Р. модифікували метод Літтла, який вирішував завдання комівояжера, для більш складного завдання про розвезення, надавши результати в роботі Метод Літтла зі штрафами для вирішення завдання про розвезення [5].

3.3 Огляд локальних джерел

У Донецькому національному технічному університеті так само розглядали теми, пов'язані з оптимізацією логістики вантажних перевезень.

У статті Розробка програмного забезпечення для формування оптимальних маршрутів швидкої доставки товарів [6] Макогон С.А. і Ситнікова О.Д. розглянули завдання побудови оптимального маршруту швидкої доставки товарів. Так само, вони представили розроблене програмне забезпечення, призначене для формування оптимальних маршрутів із забезпеченням швидкої доставки товарів.

Александрова О.А., разом зі своїм науковим керівником Секірін О.І., описала запропонований нею алгоритм і провела адекватність еволюційної моделі. У статті Оптимізація вантажних перевезень з використанням генетичних алгоритмів, на основі програмної реалізації, ними були проведені експериментальні дослідження з метою виявлення раціональних значень параметрів генетичного алгоритму та оцінки ефективності оптимізації вантажних перевезень [7].

Бражник А.В., науковим керівником якого також був Секірін О.І., проаналізував особливості завдання про транспортування вантажу, а також, привів її математичну постановку. У своїй статті Аналіз ефективності методів вирішення задачі про транспортування вантажу [8] він провів докладний порівняння генетичних і мурашиних алгоритмів за якісними і часовим характеристикам.

4. Проблема вирішення NP-повних задач

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

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

Завдання, які по своїм моделям є комбінаторними, оптимізаційними або змішаного типу з елементами комбінаторики в основному є NP-повними. Клас NP-повних задач має такі властивості [9]:

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

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

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

5. Відомі методи вирішення NP-повних задач

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

Для скорочення часу, необхідного для знаходження оптимального рішення в задачах цілочислового програмування в 1960 році АІЛС Ленд і Елісон Дойг запропонували метод гілок і меж [10]. Це загальний алгоритмічний метод для знаходження оптимальних рішень різних задач оптимізації, особливо, дискретної і комбінаторної оптимізації. Метод є розвитком методу повного перебору, на відміну від останнього — з відсівом підмножин допустимих рішень, свідомо не містять оптимальних, хоча, в гіршому випадку, його складність дорівнює складності повного перебору. При великої розмірності задачі рішення так само займе дуже багато часу.

Дж. Литтл, К. Мурті, Д. Суїні, К. Керол адаптували метод гілок і меж для вирішення задачі комівояжера в 1963 році [11]. Даний алгоритм використовується для пошуку оптимального гамільтонова контуру в графі.

Ілля scidev в статті Рішення задачі комівояжера алгоритмом Літтла з візуалізацією на площині [12] представив графік порівняння методу гілок і меж з повним перебором і середній час роботи реалізованого їм алгоритму на різній кількості міст (рисунок 1). Тестувалося на матрицях для випадково згенерували точок.

Порівняння повного перебору з методом гілок і меж
Рисунок 1 - Порівняння повного перебору (синій) з методом гілок і меж (помаранчевий)


Також, він надав графік, який зображує час роботи реалізованого методу гілок і меж на різних прикладах (рисунок 2).

Час роботи алгоритму
Рисунок 2 - Час роботи алгоритму
(синім зображено найкращий час, помаранчевим - середнє, а сірим найгірше)


Як видно з рисунку 2, вже на 30 точках алгоритм може працювати близько 180 секунд, а з ростом кількості точок час роботи буде збільшуватися експоненціально. Для отримання рішення за прийнятний час, зазвичай, можна використовувати евристичні алгоритми. Вони включають практичні методи, які не є гарантовано точними або оптимальними, але достатніми для вирішення поставленого завдання [13]. До таких алгоритміф відносяться, наприклад, мурашині, які представляють собою вірогідну жадібну евристику, де ймовірності встановлюються виходячи з інформації про якість рішення, отриманого від попередніх. [14]. Також слід зазначити алгоритми ройового інтелекту, засновані на колективному поведінці децентралізованої самоорганізовується. Вони розглядаються в теорії штучного інтелекту як оптимізаційний метод. Термін був введений Херардо Бені і Ван Цзінь в 1989 році, в контексті системи клітинних роботів [15].

Одним з найпопулярніших методів [18], незважаючи на давність розробки, є метод Кларка-Райта, розроблений двома британськими вченими Г. Кларком і Дж.В. Райтом [16]. Його суть полягає в покроковому переході до оптимальної схемою розвезення з кільцевими маршрутами. На рисунку 3 показані дві схеми доставки.

Схеми доставки
Рисунок 3 - Схеми доставки
(Анімація: 6 кадрів, 6 кб)

На схемі доставки вантажів по радіальних маршрутах в пункти Т1 і Т2 сумарний пробіг автотранспорту дорівнює:


LA = d01 + d10 + d02 + d20
 (1)

На схемі доставки вантажів по кільцевому маршруту в пункти Т1 і Т2 пробіг автотранспорту становить:


LB = d01 + d12 + d20
 (2)

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


S12 = LA − LB = d10 + d02 − d12
 (3)

У статті Розробка ПЗ оптимізації логістики поставок продукції [17] мною був реалізований алгоритм Кларка-Райта з деякими оптимізаціями і протестований на різних розмірах вхідних даних. Виходячи з отриманих даних, був побудований наступна діаграма, на якій зображений зростання часу роботи алгоритму від кількості точок:

Збільшення часу роботи алгоритму від кількості точок
Малюнок 4 - Збільшення часу роботи алгоритму від кількості точок

Висновки

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

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

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

Перелік посилань

  1. Оптимизация логистики — [Электронный ресурс]. — Режим доступа: https://morproekt.ru/articles/materialy-po-tekhnologii/optimizatsiya-logistiki
  2. A Decoding Method for Applying Swarm Intelligence Optimization Algorithm to Solve the Cold Chain Vehicle Logistics Routing Problem / Xiaolei Liang, Yuan Sun, Mengdang Tian, Wenfeng Zhou // IOP Conference Series: Earth and Environmental Science, 2018
  3. Renaud Masson, Anna Trentini, Fabien Lehuédé, Nicolas Malhéné, Olivier Péton / Optimization of a city logistics transportation system with mixed passengers and goods / EURO Journal on Transportation and Logistics, Springer, 2017, 6 (1), pp.81–109.
  4. Ю.Л. Костюк, М.С. Пожидаев / Сбалансированная эвристика для решения задачи маршрутизации транспорта с учетом грузоподъемности / Вестник Томского государственного университета, Управление, вычислительная техника и информатика, 2010
  5. И.Ф. Борханов, В.Р. Фазылов / Метод Литтла со штрафами для решения задачи о развозке. / Учебные записки Казанского государственного университета, Физико-математические науки, 2008
  6. Макогон С.А. Разработка программного обеспечения для формирования оптимальных маршрутов быстрой доставки товаров / Макогон С.А., Ситникова О.Д. // VI Международная научно-техническая конференция «Информатика, управляющие системы, математическое и компьютерное моделирование – 2017» / Информатика и кибернетика. — 2017. — № 2(4). — С. 63–70.
  7. Александрова О.А. Оптимизация грузовых перевозок с использованием генетических алгоритмов / О.А. Александрова, А.И. Секирин // Информатика и компьютерные технологии — 2009 №5, — Донецк: ДонНТУ, с. 237–244.
  8. Бражник А.В. Анализ эффективности методов решения задачи о транспортировке груза / Бражник А.В., Секирин А.И., Валуева О.С. // X Международная научно-техническая конференция «Информатика, управляющие системы, математическое и компьютерное моделирование — 2019» — 2019. — С. 57–61.
  9. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982.
  10. A.H. Land and A.G. Doig. An automatic method of solving discrete programming problems, С. 497–520.
  11. Костевич Л.С. Математическое программирование: Информ. технологии оптимальных решений: Учеб. пособие / Л. С. Костевич. — Мн.: Новое знание, 2003. ил., стр. 150
  12. Решение задачи коммивояжера алгоритмом Литтла с визуализацией на плоскости — [Электронный ресурс]. — Режим доступа: https://habr.com/ru/post/332208/
  13. С. Гудман. Введение в разработку и анализ алгоритмов / С. Гудман, С. Хидетниеми. — М. : Мир, 1981.
  14. Дж. Макконелл Основы современных алгоритмов: учебное пособие / Дж. Макконелл; пер. с англ. С.К. Ландо. — [3-е изд.]. — М.: Техносфера, 2004. — 368 c.
  15. Beni G. Wang, J. Swarm Intelligence in Cellular Robotic Systems, Proceed. NATO Advanced Workshop on Robots and Biological Systems, Tuscany, Italy, June 26–30 (1989)
  16. Clarke G. Scheduling of vehicles from a central depot to a number of delivery points / G. Clarke, J.W. Wright // Journal of Operations Research Society. — 1964. — Vol.12, № 4. — pp. 568–581.
  17. Хубеджев Д.П. Разработка ПО оптимизации логистики поставок продукции / Д.П. Хубеджев, О.Д. Ситникова // II Международная научно-практическая конференции «Программная инженерия: методы и технологии разработки информационно-вычислительных систем — 2018» / Программная инженерия. — 2018. — № 1(4). — С. 123-126.
  18. Л.Н. Шилин. Эвристический алгоритм как средство оптимизации транспортных потоков предприятия / Л.Н. Шилин, А.А. Навроцкий, Р.В. Козарь // Пятая Международная научно-практическая конференция «BIG DATA and Advanced Analytics. BIG DATA и анализ высокого уровня» — 2019.