№63-13

Вирішення задачі маршрутизації транспорту на підприємстві

Т.В. Хом’як1, Н.С. Коханчик1, А.В. Малієнко1

1 Національний технічний університет «Дніпровська політехніка», Дніпро, Україна

Coll.res.pap.nat.min.univ. 2020, 63:145-155

https://doi.org/10.33271/crpnmu/63.145

Full text (PDF)

АНОТАЦІЯ

Мета дослідження полягає в вирішенні задачі маршрутизації на підприємстві ТОВ «Лайт» з метою знаходження оптимальних маршрутів для перевезення товарів замовникам.

Методика дослідження. Для вирішення поставленої задачі застосовано алгоритм Кларка-Райта, який дозволяє ефективно знаходити рішення в задачі маршрутизації транспорту. Він відноситься до числа наближених, ітераційних методів і може використовуватися для комп'ютерного розв'язання задачі перевезення, похибка рішення не перевищує в середньому 5-10 %. Перевагами методу є його простота, надійність і гнучкість, що дозволяє враховувати цілий ряд додаткових факторів, які впливають на кінцеве рішення задачі. Цей алгоритм заснований на ранжуванні відрізків шляху за “кілометровими виграшами” та наступним додаванням цих відрізків до кінцевого маршруту. Це дозволяє мінімізувати кінцеву відстань маршруту та, відповідно, час на доставку товарів.

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

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

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

Ключові слова: системний аналіз, задача маршрутизації транспорту, метод Кларка-Райта.

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

  1. Алесинская, T.В. (2005).Основы логистики. Общие вопросы логистического управления: Учебное пособие. Изд-во ТРТУ.
  2. Golden,B.,Raghavan,S.,& Wasil,E. (2008).The vehicle routing problem: latest advances and new challenges.Springer.
  3. Lonnie, D.(2007).Systems Analysis and Design for the Global Enterprise 7th Edition.McGraw-Hill.
  4. Хом’як, Т. В., Малієнко, А. В., & Симонець, Г. В. (2019). Застосування методів згладжування для прогнозування обсягу виробництва. Вісник Національного Технічного Університету «ХПІ». Збірник Наукових Праць, Серія: Системний Аналіз, Управління Та Інформаційні Технології, 1, 8–12.
    https://doi.org/10.20998/2079-0023.2019.01.02
  5. Хом’як, Т. В., Малієнко, А. В., & Фішбах, К. К. (2019). Розробка системи підтримки прийняття рішень для вибору виду діяльності підприємст-ва. Збірник Наукових Праць Національного Гірничого Університету, 59, 132–142.
    https://doi.org/10.33271/crpnmu/59.132
  6. Shankar, R. B. S., Reddy, K. D., & Venkataramaiah, P. (2018). Solution to a capacitated vehicle routing problem using heuristics and firefly algorithm. International Journal of Applied Engineering Research, 13(21), 15247-15254.
  7. Altınel, İ. K., & Öncan, T. (2005). A new enhancement of the Clarke and Wright savings heuristic for the capacitated vehicle routing problem. Journal of the Operational Research Society, 56(8), 954–961.
    https://doi.org/10.1057/palgrave.jors.2601916