A variable neighbourhood descent algorithm with tabu mechanism for the time-constrained family travelling salesman problem
Beyza Günesen AkansuEskişehir Osmangazi University, Faculty Of Engineering And Architecture, Department Of Industrial Engineering, Production And Service Systems, EskisehirIn 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 problemSüre kısıtlı aile gezgin satıcı problemi için tabu mekanizmalı değişken komşu iniş algoritması
Beyza Günesen AkansuEskişehir Osmangazi Üniversitesi, Mühendislik Mimarlık Fakültesi, Endüstri Mühendisliği, Üretim Ve Servis Sistemleri Anabilim Dalı, EskişehirBu çalışmada Aile Gezgin Satıcı Problemi ele alınmış ve gerçek hayat uygulamalarını daha iyi temsil etmesi üzerine süre kısıtları da modele dâhil edilmiştir. Önerilen problem için matematiksel model gerekli şekilde düzenlenmiş ve daha kısa zamanlarda iyice çözümlere ulaşabilmek adına bir metasezgisel yöntem geliştirilmiştir. Yöntem dört farklı komşuluk yapısının kullanıldığı Değişken Komşu İniş algoritması olup çözüm uzayı aramasının daha verimli hale getirilmesi için algoritmaya bazı komşuluk hareketlerinde kullanılmak üzere tabu listesi eklenmiştir. Bozulma operatörü de çözüm üzerinde büyük değişiklik yaparak aramayı çeşitlendirmektedir. Önerilen algoritma matematiksel model sonuçları ile karşılaştırılmış ve kullanılan örnek setlerinde daha iyi performans sergilemiştir.
Anahtar Kelimeler: Aile gezgin satıcı problem, değişken komşu iniş, gezgin satıcı problemiManuscript Language: English