Розробка та дослідження алгоритмів розв’язання задачі маршрутизації з поверненням товару
Ключові слова:
задача маршрутизації, повернення товару, табу пошук, евристичні алгоритми, евристики покращення розв’язкуАнотація
Розглядаються існуючі точні та евристичні алгоритми розв’язку задачі маршрутизації з поверненням товару. Більш докладно розкривається задумка евристичного алгоритму табу пошуку. На його основі з певними евристиками знаходження початкового рішення, побудови сусідніх розв’язків та покращення знайденого розв’язку пропонується новий алгоритм. Приводяться результати роботи алгоритму на тестових даних, що були запропоновані авторами, які розглядали цю проблему раніше, та їх порівняння. Запропонований алгоритм може бути використаний для розв’язання подібних задач у системах реального часу, оскільки евристичний алгоритм навіть на великих наборах даних надає результат за прийнятний час.
Посилання
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##
Опубліковано
Номер
Розділ
Ліцензія
Авторське право (c) 2017 Костянтин Анатолійович Кузнєцов, Світлана Валентинівна Антоненко, Тарас Ігорович Данилов, Андрiй Олександрович Скачков
Ця робота ліцензується відповідно до Creative Commons Attribution 4.0 International License.
