Zamana bağlı oryantiring probleminin genetik algoritma kullanılarak çözümü
A genetic algorithm for solving time-dependent orienteering problem
Yazar: MAHSA BEHDADNIA
Danışman: PROF. DR. İMAN ASKERBEYLİ
Ankara Üniversitesi / Fen Bilimleri Enstitüsü / Bilgisayar Mühendisliği Ana Bilim Dalı
Derece: Yüksek Lisans, 2016
Konu: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol = Computer Engineering and Computer Science and Control

Özet:
Günümüzde turizm dünyada giderek gelişen bir endüstri haline gelmiştir Dünya turizminde önemli bir yere sahip olan ve her yıl milyonlarca turist çeken İstanbul, bu pazarda büyük bir paya sahiptir Bu turistlerin çoğu kentin tarihi ve kültürel yerlerini ziyaret etmek amacıyla gelmektedirler Bir yandan yüksek ilgi puanı (POI) diğer yandan yoğun trafik problemi göz önünde bulundurulursa şehrin bu cazibe merkezlerini ziyaret etmek için kısıtlı zamanda uygulanabilir bir gezi planı yapmayı zorlaştırmaktadır. Bu tez bahsi geçen problemi özellikle sabah ve akşam saatlerindeki şehrin yoğun trafik sorununu dikkate alarak bu kısıtlı zaman süresince en iyi (optimal) tur programını veren Zamana Bağlı Yön Bulma (Orienteering) ile çözmeyi hedeflemektedir Yön Bulma Problemi (OP) ve Zamana Bağlı Yön Bulma Problemi (TDOP) birçok makalede ele alınmış olmasına rağmen, değişken başlangıç noktalı TDOP daha önce ele alınmamıştır ve bildiğimiz kadarıyla literatürde başlangıç noktalarını değişken olarak kabul ederek maksimum skoru bulmaya çalışan TDOP metoduyla yaklaşılan ilk problemi teşkil etmektedir Model girdileri toplanan dataya göre türetilmiştir ve bu veri gerçek yaşam problemi olan İstanbul şehrine uyarlanarak ve farklı ilgi puanları ve oteller göz önüne alınarak bir çözüm algoritması geliştirilmiştir Problem matematiksel olarak modellendikten sonra, meta sezgisel yöntemini kullanmak suretiyle bir genetik algoritmayla çözülmüştür Elde edilen tüm sonuçlar sıralanmıştır ve farklı zaman bütçeleri, ayrılma zamanı ve başlangıç noktaları dikkate alınarak hassasiyet analizi yapılmıştır.

Abstract:
Tourism is actually deemed as a growing sector all over the world. Istanbul, just as an undoubtedly one of the most notable metropolis in world tourism with millions of visitors annually, offers wonderful quota as a part of this particular sector. Numerous of tourists come to the city with the purpose to visit historical as well as cultural places. Great number of Points of Interest (POIs) in one hand and the crowded traffic of the city on the other hand, cause a manageable plan to visit the regarding tourist attractions in the available time period a challenging task. This paper resolved the mentioned problem through the use of a metaheuristic method in Time Dependent Orienteering Problem (TDOP), which not just offers near optimal tour plan during the limited time budget, but additionally considers traffic of the city, specifically in the morning and evening hours. Even though the Orienteering Problem (OP) have been researched in numerous papers, the TDOP with a dynamic starting point has not been assumed previously, and this TDOP problem concerns initial points changeable and aims to find out the highest of scores relating to that with metaheuristic methods. Due to the fact that OP is NPhard, i.e. no polynomial time algorithm could be designed to solve this problem to optimality. Genetic algorithm is employed to solve this case for the city of Istanbul. A variety of POIs as visiting points and Hotels as initials points are considered to deal with this problem. After mathematically modeling the problem, it is solved near optimally with a modified genetic algorithm. All results are achieved and sensitivity analysis was done by considering different time budget and initial points.