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

---

Tezin Türü: Yüksek Lisans

Tezin Yürütüldüğü Kurum: Marmara Üniversitesi, Fen Bilimleri Enstitüsü, Türkiye

Tezin Onay Tarihi: 2021

Tezin Dili: İngilizce

Öğrenci: ONUR DOĞAN

Danışman: Ali Fuat Alkaya

Açık Arşiv Koleksiyonu: AVESİS Açık Erişim Koleksiyonu

Özet:

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.