Swarm intelligence algorithms for prize collecting traveling salesman problem with time windows

Abstract

Gezgin satıcı problemi, uzun süredir üzerinde çalışılan bilindik bir problemdir. Zaman pencereli ödül toplayan gezgin satıcı problemi her ziyaret edilen müşteri için zaman penceresi kısıtları içeren ve her müşteri için ödül değerleri içeren gezgin satıcı problemi türevidir. Bu tezde farklı parçacık zekası algoritmalarının zaman pencereli ödül toplayan gezgin satıcı probleminin çözümü için implemente edilmesi anlatılmıştır. Önerilen metod iki bölümden oluşur. İlk bölüm üç boyutlu zaman pencereli uzaklık matrisi kullanarak çözüm bulan yeni bir sezgisel yapıcı algoritmadır. Uzaklık matrisinin üçüncü boyutu, düğümler üzerinde tanımlanan zaman penceresi kısıtlarından dinamik olarak oluşturulur. Sezgisel yapıcı algoritmada, en iyi bulunan çözüme uzaklığı belirli bir aralık içerisinde olan çözümlerden oluşan bir başlangıç popülasyonu oluşturulur. İkinci bölüm olarak parçacık sürüsü optimizasyonu, göçmen kuşlar optimizasyonu ve genetik algoritmadan oluşan üç farklı parçacık zekası algoritması, üretilen çözümler üzerinde optimizasyon yapmak için uygulanmıştır. Hesaplamalara dayanan sonuçlar önerdiğimiz algoritmanın literatürde verilen algoritmaya göre daha iyi sonuçlar verdiğini göstermiştir.

Traveling salesman problem (TSP) is a well-known problem that has been studied for a long time. Prize Collecting Traveling Salesman Problem with Time Windows (PCTSPTW) is a variant of TSP that includes time windows constraints for each customer to be visited and prize for the visited nodes. This thesis presents a method that implements different swarm intelligence algorithms for solving the PCTSPTW. There are two stages in the proposed method. First stage is a novel constructive heuristic for finding solutions by using a three dimensional distance matrix with time windows. Third dimension of the distance matrix is generated dynamically by the time window constraints defined on the nodes. In the constructive heuristic phase, an initial population of solutions is generated which contains solutions that are close to the best generated solution within a threshold value. Then, in the second stage, three different swarm intelligence algorithms (particle swarm optimization algorithm, migrating birds optimization algorithm and a genetic algorithm) are implemented for making improvements on generated solutions. Results of computational experiments present that our approach outperforms the ones given in the literature.