A variable neighbourhood descent algorithm with tabu mechanism for the time-constrained family travelling salesman problem

Abstract

In this study, the Family Travelling Salesman Problem is considered and time constraints are included in the model to better represent real-life applications. The mathematical model for the proposed problem has been adjusted as necessary and a metaheuristic method has been developed in order to achieve good solutions in shorter times. The method is a Variable Neighbour Descent algorithm using four different neighbourhood structures and a tabu list is added to the algorithm to be used in some neighbourhood movements to make the solution space search more efficient. The perturbation operator also diversifies the search by making large changes on the solution. The proposed algorithm was compared with the mathematical model results and performed better on the sample sets used.

Keywords

• Family travelling salesman problem
• variable neighbourhood descent
• travelling salesman problem

Süre kısıtlı aile gezgin satıcı problemi için tabu mekanizmalı değişken komşu iniş algoritması

Öz

Bu çalışmada, Aile Gezgin Satıcı Problemi ele alınmış ve gerçek yaşam uygulamalarını daha doğru yansıtabilmek için modele zaman kısıtları dahil edilmiştir. Önerilen problemin matematiksel modeli gerektiği şekilde uyarlanmış ve daha kısa sürelerde iyi çözümler elde edebilmek amacıyla bir meta-sezgisel yöntem geliştirilmiştir. Bu yöntem, dört farklı komşuluk yapısı kullanan ve bazı komşuluk hareketlerinde tabu listesi eklenerek çözüm uzayının daha verimli taranmasını sağlayan Değişken Komşu İniş algoritmasıdır. Ayrıca, çözüm üzerinde büyük değişiklikler yaparak aramayı çeşitlendiren bir pertürbasyon operatörü de uygulanmıştır. Önerilen algoritma, matematiksel modelin sonuçlarıyla karşılaştırılmış ve kullanılan örnek setlerinde daha iyi performans göstermiştir.

Anahtar Kelimeler

• Aile gezgin satıcı problemi
• değişken komşu iniş
• gezgin satıcı problemi

Kaynakça

1. [1] Dursunoglu CF, Arslan O, Demir SM, Kara BY, Laporte G. “A unifying framework for selective routing problems”. European Journal of Operational Research, 2024.
2. [2] Dantzig G, Fulkerson R, Johnson S. “Solution of a large-scale traveling-salesman problem”. Journal of the Operations Research Society of America, 2(4), 393-410, 1954.
3. [3] Fischetti M, Salazar González J J, Toth P. “A branch-and-cut algorithm for the symmetric generalized traveling salesman problem”. Operations Research, 45(3), 378-394, 1997.
4. [4] Golden B, Naji-Azimi Z, Raghavan S, Salari M, Toth P. “The generalized covering salesman problem”. INFORMS Journal on Computing, 24(4), 534-553, 2012.
5. [5] Shaelaie MH, Salari M, Naji-Azimi Z. “The generalized covering traveling salesman problem”. Applied Soft Computing, 24, 867-878, 2014.
6. [6] Pop PC, Cosma O, Sabo C, Sitar CP. “A comprehensive survey on the generalized traveling salesman problem”. European Journal of Operational Research, 314(3), 819-835, 2024.
7. [7] Morán-Mirabal L F, González-Velarde JL, Resende MG. “Randomized heuristics for the family traveling salesperson problem”. International Transactions in Operational Research, 21(1), 41-57, 2014.
8. [8] Papcun P, Cabadaj J, Kajati E, Romero D, Landryova L, Vascak J, Zolotova I. “Augmented reality for humans-robots interaction in dynamic slotting 'chaotic storage' smart warehouses”. In Advances in Production Management Systems. Production Management for the Factory of the Future: IFIP WG 5.7 International Conference, APMS 2019, Austin, TX, USA, September 1–5, 2019, Proceedings, Part I, pp. 633-641, Springer International Publishing, 2019.

9. [9] Gonçalves JF, Resende MG. “Biased random-key genetic algorithms for combinatorial optimization”. Journal of Heuristics, 17(5), 487-525, 2011.
10. [10] Festa P, Pardalos PM, Resende MG, Ribeiro CC. “Randomized heuristics for the MAX-CUT problem”. Optimization Methods and Software, 17(6), 1033-1058, 2002.
11. [11] Reinelt G. “TSPLIB—a traveling salesman problem library”. ORSA Journal on Computing, 3, 376–384, 1991.
12. [12] Bernardino R, Paias A. “Solving the family traveling salesman problem”. European Journal of Operational Research, 267(2), 453-466, 2018.
13. [13] Bernardino R, Paias A. “Heuristic approaches for the family traveling salesman problem”. International Transactions in Operational Research, 28(1), 262-295, 2021.
14. [14] Holland JH. “Adaptation in natural and artificial systems: an introductory analysis with applications to biology, control, and artificial intelligence”. MIT Press, 1992.
15. [15] Bernardino R, Paias A. “The family traveling salesman problem with incompatibility constraints”. Networks, 79(1), 47-82, 2022.
16. [16] Dorigo M, Birattari M, Stutzle T. “Ant colony optimization”. IEEE Computational Intelligence Magazine, 1(4), 28-39, 2006.
17. [17] Bernardino R, Gouveia L, Paias A, Santos D. “The multi-depot family traveling salesman problem and clustered variants: Mathematical formulations and branch-&-cut based methods”. Networks, 80(4), 502-571, 2022.
18. [18] Wu X, Wang Z, Wu T, Bao X. “Solving the family traveling salesperson problem in the Adleman–Lipton model based on DNA computing”. IEEE Transactions on NanoBioscience, 21(1), 75-85, 2021.
19. [19] Adleman LM. “Molecular computation of solutions to combinatorial problems”. Science, 266(5187), 1021-1024, 1994.
20. [20] Lipton RJ. “DNA solution of hard computational problems”. Science, 268(5210), 542-545, 1995.
21. [21] Nourmohammadzadeh A, Sarhani M, Voß S. “A matheuristic approach for the family traveling salesman problem”. Journal of Heuristics, 29(4), 435-460, 2023.
22. [22] Kirkpatrick S, Gelatt Jr CD, Vecchi MP. “Optimization by simulated annealing”. Science, 220(4598), 671-680, 1983.
23. [23] Ribeiro CC, Hansen P, Taillard ED, Voss S. “POPMUSIC-Partial optimization metaheuristic under special intensification conditions”. Essays and Surveys in Metaheuristics, 613-629, 2002.
24. [24] Domínguez-Casasola S, González-Velarde JL, Ríos-Solís YÁ, Reyes-Vega KA. “The capacitated family traveling salesperson problem”. International Transactions in Operational Research, 31(4), 2123-2153, 2024.
25. [25] Chaves AA, Vianna BL, da Silva TT, Schenekemberg CM. “A parallel branch-and-cut and an adaptive metaheuristic to solve the Family Traveling Salesman Problem”. Expert Systems with Applications, 238, 121735, 2024.
26. [26] Chaves AA, Lorena LHN. "An adaptive and near parameter-free BRKGA using Q-learning method". 2021 IEEE Congress on Evolutionary Computation (CEC), Kraków, Poland, 2021, June 28.
27. [27] Pandiri V, Singh A. “Solution of the family traveling salesman problem using a hyper-heuristic approach”. Engineering Applications of Artificial Intelligence, 133, 108193, 2024.
28. [28] Shaw P. “Using constraint programming and local search methods to solve vehicle routing problems”. In International Conference on Principles and Practice of Constraint Programming, pp. 417-431, Berlin, Heidelberg, 1998.
29. [29] Miller CE, Tucker AW, Zemlin RA. “Integer programming formulation of traveling salesman problems”. Journal of the ACM, 7(4), 326-329, 1960.
30. [30] Şahin Y, Karagül K. “Gezgin satıcı probleminin melez akışkan genetik algoritma (MAGA) kullanarak çözümü”. Pamukkale Üniversitesi Mühendislik Bilimleri Dergisi, 25(1), 106-114, 2019.
31. [31] Wen X, Zhang X, Xing H, Ye G, Li H, Zhang Y, Wang H. “An improved genetic algorithm based on reinforcement learning for aircraft assembly scheduling problem”. Computers & Industrial Engineering, 110263, 2024.
32. [32] Hansen P, Mladenović N. “An introduction to variable neighborhood search”. Meta-heuristics: Advances and Trends in Local Search Paradigms for Optimization, pp. 433-458. Boston, MA: Springer US, 1999.
33. [33] Crispim J, Brandão J. “Metaheuristics applied to mixed and simultaneous extensions of vehicle routing problems with backhauls”. Journal of the Operational Research Society, 56(11), 1296-1302, 2005.
34. [34] Glover F. “Tabu search—part I”. ORSA Journal on Computing, 1(3), 190-206, 1989.