Розробка та дослідження алгоритмів розв’язання задачі маршрутизації з поверненням товару

Автор(и)

  • Костянтин Анатолійович Кузнєцов Дніпропетровський національний університет ім. О. Гончара, пр. Гагаріна, 72, м. Дніпро, Україна, 49010, Україна
  • Світлана Валентинівна Антоненко Дніпропетровський національний університет ім. О. Гончара, пр. Гагаріна, 72, м. Дніпро, Україна, 49010;, Україна
  • Тарас Ігорович Данилов Дніпропетровський національний університет ім. О. Гончара, пр. Гагаріна, 72, м. Дніпро, Україна, 49010, Україна
  • Андрiй Олександрович Скачков Дніпропетровський національний університет ім. О. Гончара, пр. Гагаріна, 72, м. Дніпро, Україна, 49010, Україна

Ключові слова:

задача маршрутизації, повернення товару, табу пошук, евристичні алгоритми, евристики покращення розв’язку

Анотація

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

Біографії авторів

Костянтин Анатолійович Кузнєцов, Дніпропетровський національний університет ім. О. Гончара, пр. Гагаріна, 72, м. Дніпро, Україна, 49010

кандидат фізико-математичних наук, доцент, кафедра математичного забезпечення ЕОМ

Світлана Валентинівна Антоненко, Дніпропетровський національний університет ім. О. Гончара, пр. Гагаріна, 72, м. Дніпро, Україна, 49010;

кандидат технічних наук, доцент, кафедра математичного забезпечення ЕОМ,

Тарас Ігорович Данилов, Дніпропетровський національний університет ім. О. Гончара, пр. Гагаріна, 72, м. Дніпро, Україна, 49010

магістрант

кафедра математичного забезпечення ЕОМ

Андрiй Олександрович Скачков, Дніпропетровський національний університет ім. О. Гончара, пр. Гагаріна, 72, м. Дніпро, Україна, 49010

магістрант

кафедра математичного забезпечення ЕОМ

Посилання

Osman, I. H., Wassan, N. A. (2002). A reactive tabu search meta-heuristic for the vehicle routing problem with back-hauls. Journal of Scheduling, 5 (4), 263–285. doi: 10.1002/jos.122

Glover, F., Laguna, M. (1997). Tabu Search. Boulder: Springer US, 383. doi:10.1007/978-1-4615-6089-0

Toth, P., Vigo, D. (1997). An Exact Algorithm for the Vehicle Routing Problem with Backhauls. Transportation Science, 31 (4), 372–385. doi:10.1287/trsc.31.4.372

Mingozzi, A., Giorgi, S., Baldacci, R. (1999). An Exact Method for the Vehicle Routing Problem with Backhauls. Transportation Science, 33 (3), 315–329. doi:10.1287/trsc.33.3.315

Yano, C. A., Chan, T. J., Richter, L. K., Cutler, T., Murty, K. G., McGettigan, D. (1987). Vehicle Routing at Quality Stores. Interfaces, 17 (2), 52–63. doi:10.1287/inte.17.2.52

Deif, I., Bodin, L. (1984). Extension of the Clarke and Wright algorithm for solving the vehicle routing problem with backhauling. Proceedings of the Babson Conference on Software Uses in Transportation and Logistic Management. Babson Park, 75–96.

Casco, D, Golden, B. L., Wasil, E. (1988). Vehicle routing with backhauls: models algorithms and case studies. Vehicle Routing: Methods and Studies, 127–147.

Clarke, G., Wright, J. W. (1964). Scheduling of Vehicles from a Central Depot to a Number of Delivery Points. Operations Research, 12 (4), 568–581. doi:10.1287/opre.12.4.568

Golden, B., Baker, E., Alfaro, J., Schaffer, J. (1985). The vehicle routing problem with backhauling: two approaches. Proceedings of the 21st Annual Meeting of SE TIMS, South Carolina, 90–92.

Toth, P., Vigo, D. (1996). A Heuristic Algorithm for the Vehicle Routing Problem with Backhauls. Transportation Analysis, 585–608. doi:10.1007/978-3-642-85256-5_26

##submission.downloads##

Опубліковано

2017-02-15

Номер

Розділ

Автоматизація та управління механіко-технологічними системами та комплексами