An evolutionary approach to TSP: Crossover with convertional heuristics

---

Tezin Türü: Yüksek Lisans

Tezin Yürütüldüğü Kurum: Orta Doğu Teknik Üniversitesi, Mühendislik Fakültesi, Endüstri Mühendisliği Bölümü, Türkiye

Tezin Onay Tarihi: 2003

Tezin Dili: İngilizce

Öğrenci: MELTEM SÖNMEZ

Eş Danışman: NUR EVİN ÖZDEMİREL, HALDUN SÜRAL

Özet:

Gezgin satıcı probleminde (GSP), N adet şehri dolaşmak üzere yola çıkan bir satıcı, her şehri sadece bir kez dolaşır ve başladığı noktaya geri döner. Şehir sayısı artığında makul bir sürede en kısa rotayı bulmak güçleşir ve bu nedenle literatürde birçok sezgisel yöntem geliştirilmiştir. Bu çalışmada, GSP 'ne doğal evrimsel süreçleri model olarak kullanan evrimsel algoritmalar ile bilinen geleneksel sezgisel yöntemleri birleştiren bir çözüm yöntemi önerilmektedir. Geleneksel sezgisel yöntemlerden, "en yakın komşu önce", "en kısa mesafe önce" ve "araya girme", çaprazlama yöntemi olarak kullanılmış ve bu yöntemler GSP'nin yapıtaşları olan kenarları koruyabilmek için ebeveyn turların birleşhrıinden oluşan çizelgeye kısıtlanmıştır. Literatürden alman, şehir sayıları 52 ve 3038 arasında değişen bir problem kümesiyle çaprazlama yöntemlerinin performansı test edilmiştir. Hem çözüm kalitesi, hem de süresi bakımından ümit verici sonuçlar elde edilmiştir. Anahtar Kelimeler: Gezgin Satıcı Problemi, Evrimsel Algoritmalar, Geleneksel Sezgisel Yöntemler.