Tez Arşivi

Tez aramanızı kolaylaştıracak arama motoru. Yazar, danışman, başlık ve özete göre tezleri arayabilirsiniz.


Orta Doğu Teknik Üniversitesi / Enformatik Enstitüsü / Bilişim Sistemleri Anabilim Dalı

A genetic algorithm for TSP with backhauls based on conventional heuristics

Dağıtım ve toplamalı güzergahı bulma problemi için bilinen sezgisellere dayalı bir genetik algoritma

Teze Git (tez.yok.gov.tr)

Bu tezin tam metni bu sitede bulunmamaktadır. Teze erişmek için tıklayın. Eğer tez bulunamazsa, YÖK Tez Merkezi tarama bölümünde 233566 tez numarasıyla arayabilirsiniz.

Özet:

A genetic algorithm using conventional heuristics as operators is considered in this study for the traveling salesman problem with backhauls (TSPB). Properties of a crossover operator (Nearest Neighbor Crossover, NNX) based on the nearest neighbor heuristic and using more than two parents are investigated in a series of experiments. Different parent selection and replacement strategies and generation of multiple children are also tried as well. Conventional improvement heuristics are also used as mutation operators. It has been observed that 2-edge exchange and node insertion heuristics work well with NNX using only two parents. The best settings among different alternatives experimented are applied on traveling salesman problem with backhauls (TSPB). TSPB is a problem in which there are two groups of customers. The aim is to minimize the distance traveled visiting all the cities, where the second group can be visited only after all cities in the first group are already visited. The approach we propose shows very good performance on randomly generated TSPB instances. Keywords: Genetic Algorithms, Crossover operator, Mutation Operator, TSP with Backhauls, Conventional Heuristics

Summary:

Bu çalısmada toplamalı gezgin satıcı problemi için bilinen sezgisel yöntemleri operatör olarak kullanan bir genetik algoritma incelenmistir. En yakın komsu sezgiseline dayalı bir çaprazlama yönteminin (En yakın komsu çaprazlaması, EYKÇ) özellikleri ve ikiden fazla ebeveyn kullanılması bir dizi deneyle incelenmistir. Farklı ebeveyn seçilimi ve birden fazla çocuk yaratma stratejileri de kıyaslanmıstır. Bilinen sezgisel yöntemler mutasyon operatörü olarak kullanılmıstır. 2-kenar degisimi ve dügüm sokma yöntemlerinin EYKÇ ile iyi sonuçlar verdigi gözlemlenmistir. Farklı alternatifler arasında en iyi sonuçları veren alternatifler Dagıtım ve Toplama Güzergâhı Bulma Problemine uygulanmıstır. DTGBP içinde iki grup sehir bulunan bir problemdir. Amacı, ikinci gruptakiler ancak birinci gruptakilerin tamamı gezildikten sonra gezilebilir sartını saglayacak sekilde, tüm sehirleri gezen en kısa yolu bulmaktır. Kullandıgımız yöntem rasgele üretilmis DTGBP'de etkileyici sonuçlar vermistir. Anahtar Kelimeler: Genetik Algoritmalar, Çaprazlama Yöntemleri, Dagıtım ve Toplama Güzergâhı Bulma Problemi (DTGBP), Sezgisel Yöntemler