Solving the profitable tour problem using ant colony system

---

Tezin Türü: Yüksek Lisans

Tezin Yürütüldüğü Kurum: Boğaziçi Üniversitesi, FEN BİLİMLERİ ENSTİTÜSÜ, FEN BİLİMLERİ ENSTİTÜSÜ, Türkiye

Tezin Onay Tarihi: 2008

Tezin Dili: İngilizce

Öğrenci: AYKUN AÇIL

Danışman: MUSTAFA NECATİ ARAS

Açık Arşiv Koleksiyonu: AVESİS Açık Erişim Koleksiyonu

Özet:

Gezgin satıcı problemi üzerinde en çok çalışılan kombinatoriyel optimizasyonproblemlerinden biridir. Tabu arama, Genetik Algoritma ve Yapay ısıl işlem algoritmalarıgibi bir çok algoritma bu probleme uygulanabilmektedir. Gezgin satıcı problemininKarlı Tur Problemi, Yön Bulma Problemi ve Ödül Toplayan Gezgin satıcıproblemi gibi uzantıları vardır. Karlı Tur Probleminin Gezgin satıcı problemindenfarklı bir amaç fonksiyonu vardır. Karlı Tur Probleminde amaç karı maksimize ederkenyol maliyetlerini minimize etmektir. Bu sebeple tüm şehirleri gezme zorunluluğuyoktur. Karınca kolonisi algoritmaları Karlı Tur Problemini çözebileceği halde bugünekadar uygulanmamıştır. Bu tezde, Hibrid Karınca Koloni Sistemi algoritması KarlıTur Problemini çözmek için kullanılmıştır. Yerel arama modeli olarak şehir çıkarma,şehir ekleme, çift şehir çıkarma ve çift şehir ekleme prosedürleri önerilmiştir. KarıncaKoloni Sistemi algoritması Karlı Tur Probleminde kullanabilmek için uyarlanmıştır.Bu tezde dört farklı strateji sunulmuş ve sonuçları Cplex çözücüsü tarafından bulunanoptimal çözümlerle kıyaslanmıştır. Sonuçlar Karlı Tur Probleminin Karınca KoloniSistemi algoritmasıyla çözülebildiğini göstermektedir.