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.
Travelling Salesperson Problem hotel selection heuristic algorithms variable neighborhood descent
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.
Gezgin satıcı problemi otel seçimi sezgisel algoritmalar değişken komşu arama
Birincil Dil | Türkçe |
---|---|
Bölüm | Araştırma Makalesi |
Yazarlar | |
Yayımlanma Tarihi | 30 Haziran 2020 |
Gönderilme Tarihi | 10 Eylül 2019 |
Kabul Tarihi | 14 Temmuz 2020 |
Yayımlandığı Sayı | Yıl 2020 Cilt: 4 Sayı: 1 |