Geri Dön

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

PDF İndir

  1. Tez No: 233566
  2. Yazar: İLTER ÖNDER
  3. Danışmanlar: DOÇ.DR. HALDUN SÜRAL, PROF. DR. NUR EVİN ÖZDEMİREL
  4. Tez Türü: Yüksek Lisans
  5. 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
  6. Anahtar Kelimeler: Genetik Algoritmalar, Çaprazlama Yöntemleri, Dagıtım ve Toplama Güzergâhı Bulma Problemi (DTGBP), Sezgisel Yöntemler, Mutasyon, Genetic Algorithms, Crossover operator, Mutation Operator, TSP with Backhauls, Conventional Heuristics, Mutation
  7. Yıl: 2007
  8. Dil: İngilizce
  9. Üniversite: Orta Doğu Teknik Üniversitesi
  10. Enstitü: Enformatik Enstitüsü
  11. Ana Bilim Dalı: Bilişim Sistemleri Ana Bilim Dalı
  12. Bilim Dalı: Belirtilmemiş.
  13. Sayfa Sayısı: Belirtilmemiş.

Ö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

  1. Tez No

    224019

    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

    İngilizce

    2008

    Endüstri ve Endüstri MühendisliğiOrta Doğu Teknik Üniversitesi

    Endüstri Mühendisliği Bölümü

    DOÇ. DR. ESRA KARASAKAL

    DOÇ. DR. HALDUN SÜRAL

  2. Tez No

    337103

    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

    Türkçe

    2013

    Endüstri ve Endüstri Mühendisliğiİstanbul Üniversitesi

    Endüstri Mühendisliği Ana Bilim Dalı

    YRD. DOÇ. DR. MURAT AKAD

  3. Tez No

    667368

    SEYAHAT SATIŞI SORUNUNUN ÇÖZÜMÜ İÇİN FARKLI TEKNİĞİN KARŞILAŞTIRILMASI İÇİN DEĞİŞTİRİLMİŞ BALİNA OPTİMİZASYON ALGORİTMASININ KULLANILMASI

    USING MODIFIED WHALE OPTIMIZATION ALGORITHM WITH A COMPARATIVE ANALYSIS OF DIFFERENT TECHNIQUE FOR SOLVING TRAVELING SALESMAN PROBLEM

    MOHAMMED ISAM DHAHIR IMARAH

    Yüksek Lisans

    İngilizce

    İngilizce

    2020

    Elektrik ve Elektronik MühendisliğiAltınbaş Üniversitesi

    Elektrik ve Bilgisayar Mühendisliği Ana Bilim Dalı

    Prof. Dr. OSMAN NURİ UÇAN

  4. Tez No

    805082

    Using modified whale optimization algorithm with a comparative analysis of different technique for solving traveling salesman problem

    Seyahat satışı sorununun çözümü için değiştirilmiş toptan optimizasyon algoritmasının kullanılması

    ALI ABDULLAH SALEH SALEH

    Yüksek Lisans

    İngilizce

    İngilizce

    2022

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolAltınbaş Üniversitesi

    Elektrik ve Bilgisayar Mühendisliği Ana Bilim Dalı

    PROF. DR. MESUT ÇEVİK

  5. Tez No

    651213

    Determining the best settings for the operators and parameters of genetic algorithms: A methodology and its application to traveling salesperson problem

    Genetik algoritmaların operatörleri ve parametreleri için en iyi ayarları belirleme: Bir metodoloji ve gezgin satıcı probleminde uygulaması

    YAVUZHAN AKDURAN

    Yüksek Lisans

    İngilizce

    İngilizce

    2020

    Endüstri ve Endüstri MühendisliğiHacettepe Üniversitesi

    Endüstri Mühendisliği Ana Bilim Dalı

    PROF. DR. MURAT CANER TESTİK

Geri Dön