Solving the profitable tour problem using ant colony system
Karlı tur probleminin karınca kolonisi algoritmasıyla çözümü
- Tez No: 232508
- Danışmanlar: DOÇ. NECATİ ARAS
- Tez Türü: Yüksek Lisans
- Konular: Endüstri ve Endüstri Mühendisliği, Industrial and Industrial Engineering
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2008
- Dil: İngilizce
- Üniversite: Boğaziçi Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Endüstri Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: Belirtilmemiş.
Ö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.
Özet (Çeviri)
The Traveling Salesman Problem (TSP) is one of the most widely studied combinatorialoptimization problems. Many heuristic algorithms such as tabu search, geneticalgorithm, and simulated annealing are applicable to this problem. There are some extensionsof the TSP such as the Profitable Tour Problem (PTP), the OrienteeringProblem (OP) and the Prize-Collecting TSP (PCTSP). The PTP includes a differentobjective function than the TSP where the objective is to maximize the profit whileminimizing the traveling cost. Hence, it is not an obligation to visit all of the cities.In this thesis, a hybrid version of the ACS is used to solve the PTP for the firsttime in the literature. A local search model which includes inversion, insertion, doubleinsertion, extraction and double extraction procedures is proposed. The ACS algorithmis adjusted to be used in the PTP. Four different strategies are presented in the paperand their results are compared with the optimal solutions found by using the Cplexsolver. Results show that the PTP can efficiently be solved by the ACS algorithm.
Benzer Tezler
- Küçük ölçekli bir kimya sanayi işletmesinde kalite güvence sisteminin incelenmesi ve değerlendirilmesi
The examination and evolution of a quality assurance system from a small-scale chemical industry plant
ZEKİ YÖRÜR
Yüksek Lisans
Türkçe
1997
İşletmeİstanbul Teknik Üniversitesiİşletme Mühendisliği Ana Bilim Dalı
DOÇ. DR. SEMRA DURMUŞOĞLU
- Yatırım fonlarından oluşan portföyün bulanık hedef programlama yaklaşımı ile optimizasyonu
The optimization of a mutual fund portfolio with fuzzy goal programming approach
CAN HİÇBEZMEZ
Yüksek Lisans
Türkçe
2014
Ekonomiİstanbul Teknik ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
DOÇ. DR. ALP ÜSTÜNDAĞ
- Türk sigorta sektörünün piyasa yapısı ve analizi
Market structure and anaysis of Turkish insurance sector
LÜTFİ AYKAÇ