OTEL SEÇİMLİ GEZGİN SATICI PROBLEMİ İÇİN DEĞİŞKEN KOMŞU İNİŞ SEZGİSELİ

VARIABLE NEIGHBORHOOD DESCENT FOR TRAVELLING SALESPERSON PROBLEM WITH HOTEL SELECTION

Özet

Otel Seçimli Gezgin Satıcı Problemi (OSGSP) Gezgin Satıcı Probleminin (GSP) bir çeşididir. OSGSP'nde çalışma süresi/mesafesi kısıtından dolayı tüm noktalar tek bir günde ziyaret edilememektedir. Bu problem NP-zor problem sınıfına girdiği için sezgisel yöntem kullanılması çözüm zamanı açısından avantaj sağlamıştır. İlk olarak En Yakın Komşu Prensibi (EYKP) kullanılarak başlangıç çözüm elde edilmiştir. Sonrasında bulunan bu çözümü iyileştirmek amacıyla Değişken Komşu İniş Algoritması (DKİA)'ndan faydalanılmıştır. Algoritmalar Python dili ile kodlanmıştır. Literatürde var olan test problemleri üzerinde çeşitli ölçütler kullanılarak denemeler yapılmıştır ve elde edilen sonuçlar var olan en iyi çözümler ile karşılaştırılarak algoritmanın performansı değerlendirilmiştir.

Abstract

The Travelling Salesperson Problem with Hotel Selection (TSPHS) is a variant of The Travelling Salesperson Problem (TSP). In case of TSPHS problem, all points cannot be visited in a single day due to the restriction of working time / distance. Since this problem belongs to the NP-hard problem class, the use of heuristic method has an advantage in terms of the solution time. The initial solution is obtained using The Nearest Neighbor Algorithm (NN). In order to improve this solution, the Variable Neighborhood Descent (VND) is used. Python language is used for coding. The algorithms experiments are made on the test problems in the literature using various criteria and the results obtained are compared with the best available solutions and the performance of algorithm is evaluated.

Anahtar kelimeler: Gezgin satıcı problemi, otel seçimi, sezgisel algoritmalar, değişken komşu arama