2-OPT ALGORİTMASI VE BAŞLANGIÇ ÇÖZÜMÜNÜN ALGORİTMA SONUÇLARI ÜZERİNDEKİ ETKİSİ

Timur KESKİNTÜRK; Barış KİREMİTCİ; Serap KİREMİTCİ

Makale detayları

2-OPT ALGORİTMASI VE BAŞLANGIÇ ÇÖZÜMÜNÜN ALGORİTMA SONUÇLARI ÜZERİNDEKİ ETKİSİ

Yazarlar:

Timur KESKİNTÜRK | Barış KİREMİTCİ | Serap KİREMİTCİ

Yayıncı:

TMMOB Makina Mühendisleri Odası

Dergi:

Journal of Industrial Engineering 2016 Vol.27 Issue 3, pp.2-12

Belge Tipi:

Makale

Yayın Tarihi:

9/2016

Belge Dili:

Türkçe

Document ID (Org No.):

2000409374

eISSN:

2667-7539

pISSN:

1300-3410

Özet:

 


In this study the 2-opt heuristic algorithm which was proposed by Croes (1958) for the travelling salesman problem is presented and the effect of the initial solutions produced by constructive heuristics on the performance of the algorithm is analyzed. The algorithm is based on a local search that works with the logic of removing two edges from the current solution and merging the two parts in a different way. After trying all possible changes the result is considered a 2-optimal solution. The initial tour could be either a randomly created tour or a result of any other heuristics. In this work the best initial tour by the heuristics has also been studied. The algorithm has been tested on different benchmark problems and these results have been analyzed. Since this algorithm has not yet been studied in the Turkish literature this study will fill a gap on this topic.

.

 

Bu çalışmada, gezgin satıcı problemlerinin çözümü için Croes (1958) tarafından önerilen 2-opt algoritması tanıtılmış ve tur oluşturan sezgisellerle üretilen başlangıç çözümlerinin, algoritmanın performansı üzerindeki etkileri incelenmiştir. Yerel arama mantığı ile çalışan algoritma, turdaki iki kenarın turdan çıkarılması ve kalan kısımların farklı şekilde birbirlerine bağlanması şeklinde iyileştirmeler yapmaktadır. Tüm mümkün değişikliklerin yapılmasından sonra elde edilen çözüm, 2-optimal olarak adlandırılmaktadır. Başlangıç çözümü tesadüfi olarak üretilen bir tur olabileceği gibi, farklı sezgisellerin ürettiği turlar da kullanılabilir. Çalışmada ayrıca, hangi başlangıç çözümünün 2-opt algoritmasının sonuçlarını iyileştirdiği de araştırılmıştır. Algoritma, farklı problemler üzerinde denenmiş, elde edilen sonuçlar da karşılaştırmalı olarak raporlanmıştır. Türkçe literatürde daha önce ele alınmamış olan algoritmanın detaylı anlatımıyla, anadili Türkçe olan araştırmacılar için bir boşluğu doldurması umulmuştur.

Makale detayları

2-OPT ALGORİTMASI VE BAŞLANGIÇ ÇÖZÜMÜNÜN ALGORİTMA SONUÇLARI ÜZERİNDEKİ ETKİSİ

Yazarlar: Timur KESKİNTÜRK | Barış KİREMİTCİ | Serap KİREMİTCİ

Yayıncı: TMMOB Makina Mühendisleri Odası

Dergi: Journal of Industrial Engineering 2016 Vol.27 Issue 3, pp.2-12

Belge Tipi: Makale

Yayın Tarihi: 9/2016

Belge Dili: Türkçe

Document ID (Org No.): 2000409374

eISSN: 2667-7539

pISSN: 1300-3410

Sayı

Yazarlar:

Timur KESKİNTÜRK | Barış KİREMİTCİ | Serap KİREMİTCİ

Yayıncı:

TMMOB Makina Mühendisleri Odası

Dergi:

Journal of Industrial Engineering 2016 Vol.27 Issue 3, pp.2-12

Belge Tipi:

Makale

Yayın Tarihi:

9/2016

Belge Dili:

Türkçe

Document ID (Org No.):

2000409374

eISSN:

2667-7539

pISSN:

1300-3410