Akademik Veri Yönetim Sistemi
Tezin Türü: Doktora
Tezin Yürütüldüğü Kurum: Marmara Üniversitesi, Mühendislik Fakültesi, Endüstri Mühendisliği Bölümü, Türkiye
Tezin Onay Tarihi: 2008
Tezin Dili: İngilizce
Öğrenci: KUBİLAY A. ALPDOĞAN
Danışman: SEROL BULKAN
Özet:GEZGİN SATICI PROBLEMİNE YENİ BİR SEZGİSEL YAKLAŞIM Bu çalışmada, NP-Hard olarak bilinen ve çözümüne ulaşılması imkansız olan veya henüz ulaşılamamış olan Gezgin Satıcı Problemlerine optimum veya yakın-optimum sonuç bulduracak yeni bir sezgisel metot geliştirilmiştir. Söz konusu metot, işletme alanında geçen “memnun müşteri 2 kişiye; mutsuz müşteri ise 20 kişiye söyler” sözünden yola çıkılarak geliştirilmiştir. Toplumsal yapıdan model alınarak yaratılan algoritma, belirli sayıda insanların rassal olarak kat ettikleri güzergahlar üzerine yaptıkları yorum ve “dedikodulardan” etkilenen sonraki neslin olumsuz yorumların aksini tercih etmeleri veya yepyeni güzergah deneme ihtiyacı duymaları üzerine kuruludur. Yeni yaklaşım, TSPLIB olarak bilinen elektronik Gezgin Satıcı Problemi kütüphanesindeki problemlemlere uygulanmıştır. Farklı ölçekteki problemlerin çözümleri; hesaplama süreleri, bilinen en iyi sonuca yüzde olarak yakınlık oranları not edilerek karşılaştırılmıştır. Sonuç itibari ile 20 şehire kadar olan asimetrik problemlerde optimum sonuç alındığı ve 20 ile 50 şehre kadar olan problemlerde %15. yakınlık oranıyla sonuç bulunduğu görülmüştür. Test sonuçlarının istatistiki güven aralığı, yaklaşık %100 güven seviyesinde optimal değerleri içermektedir. Son olarak, algoritmanın, En-kötü-vaka analizine göre opt-2 algoritmalarından daha iyi sonuç verdiği ispatlanmıştır. Yeni geliştirilen bu algoritmanın, ilk haliyle umut veren sonuçlar sağladığı sonucuna varılmıştır. Bu yeni algoritma, ileri aşamalarda daha çabuk evrimleşmeye ve literatürdeki diğer evrimleşmiş algoritmalardan daha iyi sonuçlar vermeye açıktır. ABSTRACT A NEW HEURISTIC APPROACH TO TSP In this study, a new heuristic method has been developed in order to find optimal or near-optimal solutions to unsolved or impracticaly NP Hard Travelling Salesman Problems. This new algorithm has been developed by inspiring from the word “Satisfied customer tells it to 2 people; dissatisfied customer tells to 20 people” in marketing field. By modelling this social structure, given number of human beings make various routes and after completing their routes they start commenting and “rumoring”. The next generation, affected by these rumors, tend to eliminate the routes of negative rumor concern or sometimes choose to try a new route. The new Algorithm has been applied to the problems from e-library called TSPLIB. The results are compared by means of excess over optimal percentages, interval estimates, and worst case analyses. As a result, it has been seen that the Algorithm provided with optimal solutions to at most 20-city problems; and had 15% excess over optimal ratio for the 20 to 50-city problems. Confidence interval of the test results include optimal values at a confidence level very close to 100%. Lastly, it is prooved that the Algorithm gives better results than opt-2 algorithm by worst case analysis. The new developed algorithm is a prospective heuristic while the technique is in its early stage. In this sense, Rumor Model is a nominator for easy and speedy revolution and having better results than of evoluted algorithms in the literature after retunings.