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
- Tez No: 233566
- Danışmanlar: DOÇ.DR. HALDUN SÜRAL, PROF. DR. NUR EVİN ÖZDEMİREL
- Tez Türü: Yüksek Lisans
- Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Endüstri ve Endüstri Mühendisliği, Computer Engineering and Computer Science and Control, Industrial and Industrial Engineering
- Anahtar Kelimeler: Genetik Algoritmalar, Çaprazlama Yöntemleri, Dagıtım ve Toplama Güzergâhı Bulma Problemi (DTGBP), Sezgisel Yöntemler, Genetic Algorithms, Crossover operator, Mutation Operator, TSP with Backhauls, Conventional Heuristics
- Yıl: 2007
- Dil: İngilizce
- Üniversite: Orta Doğu Teknik Üniversitesi
- Enstitü: Enformatik Enstitüsü
- Ana Bilim Dalı: Bilişim Sistemleri Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 123
Özet
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.
Özet (Çeviri)
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.
Benzer Tezler
- A genetic algorithm for the biobjective traveling salesman problem with profits
Çok amaçlı kar getiren gezgin satıcı problemi için genetik bir algoritma
SERDAR KARADEMİR
Yüksek Lisans
İngilizce
2008
Endüstri ve Endüstri MühendisliğiOrta Doğu Teknik ÜniversitesiEndüstri Mühendisliği Bölümü
DOÇ. DR. ESRA KARASAKAL
DOÇ. DR. HALDUN SÜRAL
- Karga ve yarasa tabanlı algoritmaların yeni versiyonlarının geliştirilmesi ve performanslarının değerlendirilmesi
Development of new versions of crow and bat based algorithms and evaluation of their performance
ZAHER AKHDIR
Yüksek Lisans
Türkçe
2020
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolErciyes ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
DR. ÖĞR. ÜYESİ MUSTAFA DANACI
- Data-driven prediction and emergency control of transient stability in power systems towards a risk-based optimal power flow operation
Güç sistemlerinde risk tabanlı optimal güç akışı işletimineyönelik geçici hal kararlılığın veri güdümlü tahmini veacil durum kontrolü
SEVDA JAFARZADEH
Doktora
İngilizce
2022
Elektrik ve Elektronik Mühendisliğiİstanbul Teknik ÜniversitesiElektrik Mühendisliği Ana Bilim Dalı
PROF. VEYSEL MURAT İSTEMİHAN GENÇ
- Swarm intelligence algorithms for prize collecting traveling salesman problem with time windows
Sürü zekası algorimaları ile zaman pencereli ödül toplayan gezgin satıcı probleminin çözümü
ONUR DOĞAN
Yüksek Lisans
İngilizce
2021
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolMarmara ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
DOÇ. DR. ALİ FUAT ALKAYA
- Genetik algoritma ile araç rotalama problemlerinin çözümü için görsel rotalama yazılımı geliştirme
Development a visual routing software for the solution of vehicle routing problems with genetic algorithm
NOYAN SEBLA GÜNAY
Yüksek Lisans
Türkçe
2013
Endüstri ve Endüstri Mühendisliğiİstanbul ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
YRD. DOÇ. DR. MURAT AKAD