A genetic algorithm for TSP with backhauls based on conventional heuristics

Abstract

Bu çalısmada toplamalı gezgin satıcı problemi için bilinen sezgisel yöntemlerioperatör olarak kullanan bir genetik algoritma incelenmistir. En yakın komsusezgiseline dayalı bir çaprazlama yönteminin (En yakın komsu çaprazlaması,EYKÇ) özellikleri ve ikiden fazla ebeveyn kullanılması bir dizi deneyleincelenmistir. Farklı ebeveyn seçilimi ve birden fazla çocuk yaratma stratejileri dekı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 verdigigözlemlenmistir. Farklı alternatifler arasında en iyi sonuçları veren alternatiflerDagıtım ve Toplama Güzergâhı Bulma Problemine uygulanmıstır. DTGBP içindeiki grup sehir bulunan bir problemdir. Amacı, ikinci gruptakiler ancak birincigruptakilerin tamamı gezildikten sonra gezilebilir sartını saglayacak sekilde, tümsehirleri gezen en kısa yolu bulmaktır. Kullandıgımız yöntem rasgele üretilmisDTGBP'de etkileyici sonuçlar vermistir.Anahtar Kelimeler: Genetik Algoritmalar, Çaprazlama Yöntemleri, Dagıtım veToplama Güzergâhı Bulma Problemi (DTGBP), Sezgisel Yöntemler

A genetic algorithm using conventional heuristics as operators is considered in thisstudy for the traveling salesman problem with backhauls (TSPB). Properties of acrossover operator (Nearest Neighbor Crossover, NNX) based on the nearestneighbor heuristic and using more than two parents are investigated in a series ofexperiments. Different parent selection and replacement strategies and generation ofmultiple children are also tried as well. Conventional improvement heuristics arealso used as mutation operators. It has been observed that 2-edge exchange and nodeinsertion heuristics work well with NNX using only two parents. The best settingsamong different alternatives experimented are applied on traveling salesmanproblem with backhauls (TSPB). TSPB is a problem in which there are two groupsof 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 arealready visited. The approach we propose shows very good performance onrandomly generated TSPB instances.Keywords: Genetic Algorithms, Crossover operator, Mutation Operator, TSP withBackhauls, Conventional Heuristics