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

Öz

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 of the proposed problem was adapted accordingly, and a metaheuristic method was developed to produce high-quality solutions in shorter computation times. This method is a Variable Neighbourhood Descent algorithm, which uses four different neighbourhood structures and allows for more efficient searching of the solution space by adding a tabu list in some neighbourhood movements. A perturbation operator was also applied, diversifying the search by making huge modifications on the current solution. The proposed algorithm was compared with the results of the mathematical model and demonstrated better performance on the sample sets used.

Anahtar Kelimeler

• 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ı dâhil 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 bozulma 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, 320(1), 1-19, 2025.
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". IFIP international Conference on Advances in Production Management Systems. Austin, USA, 1-5 September 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 İntelligence. 2nd ed. Massachusetts, USA, 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] Taillard Éric D, Stefan Voss. POPMUSIC-Partial Optimization Metaheuristic Under Special Intensification Conditions. Editors: Ribeiro C, Hansen EP. Essays and surveys in metaheuristics, 613-629, New York, USA, Kluwer Academic Publishers, 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, 2331-2338.
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”. International Conference on Principles and Practice of Constraint Programming, Berlin, Heidelberg, 26-30 October 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, 193, 110263, 2024.
32. [32] Hansen P, Mladenović N. An İntroduction To Variable Neighborhood Search. Editors: Stefan V, Silvano M, Ibrahim H. O., Catherine R. Meta-heuristics: Advances and Trends in Local Search Paradigms for Optimization, 433-458. Boston, USA, 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.