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

Костянтин Анатолійович Кузнєцов, Світлана Валентинівна Антоненко, Тарас Ігорович Данилов, Андрiй Олександрович Скачков

Анотація


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


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


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

Повний текст:

PDF

Посилання


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


Пристатейна бібліографія ГОСТ


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

Glover, F. Tabu Search hauls [Text] / F. Glover, M. Laguna. – Boulder: Springer US, 1997. – 383 p. doi:10.1007/978-1-4615-6089-0

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

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

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

Deif, I. Extension of the Clarke and Wright algorithm for solving the vehicle routing problem with backhauling [Text]: proc. Babson conf. / I. Deif, L. D. Bodin // Proceedings of the Babson Conference on Software Uses in Transportation and Logistic Management. – Babson Park, 1984. – P. 75–96.

Casco, D. Vehicle routing with backhauls: models algorithms and case studies [Text] / D. Casco, B. L. Golden, E. Wasil // Vehicle Routing: Methods and Studies. – 1988. – № 16. – P. 127–147.

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

Golden, B. The vehicle routing problem with backhauling: two approaches. [Text]: Proc. 21st An. Meeting / B. Golden, E. Baker, J. Alfaro, J. Schaaer // Proceedings of the 21st Annual Meeting of SE TIMS. – South Carolina, 1985. – P. 90–92

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


Посилання

  • Поки немає зовнішніх посилань.




Copyright (c) 2017 Костянтин Анатолійович Кузнєцов, Світлана Валентинівна Антоненко, Тарас Ігорович Данилов, Андрiй Олександрович Скачков

Creative Commons License
Ця робота ліцензована Creative Commons Attribution 4.0 International License.

ISSN 2411-2828 (Online), ISSN 2411-2798 (Print)