The Vehicle Routing Problems with Profit are defined on a graph including control points and connections between them. Objective of the problem is to find paths, starting at an origin and ending at a destination that maximizes total profit without violating prescribed cost function (total distance, time and etc.). A path is determined for each vehicle defined by the problem. If there is only one vehicle in the problem, the problem is named as Orienteering Problem (OP), if there are more than one vehicles, it is named as Team Orienteering Problem (TOP).In this thesis, two new models based on Particle Swarm Optimization (PSO) and Variable Neighborhood Search (VNS) are proposed for solving OP and TOP. First model employs Reduced VNS (RVNS) which is a version of VNS. Providing a fast but sketchy exploration through the solution space is the strongest asset of RVNS. By using two nested RVNS, the proposed model accomplishes not only global search but also detailed local search at the same time.The second model is based on PSO. PSO is a population based metaheuristic that takes advantage of individual memory and social cooperation in a swarm. Straightforward application of PSO suffers from premature convergence and lack of intensification around the local best locations. To rectify these problems, a RVNS based local search around the best particle in the swarm is performed and a random moving strategy for this particle is employed. The proposed method is named as Strengthened PSO (StPSO). Partial and full discrete versions of this method are used for OP and TOP. The proposed models are tested aginst 453 OP and TOP benchmark problems in literature. It is observed that they generate competitive and promising results compared to the other similar methods in literature in terms of solutions quality and performance. Furthermore, improvements are achieved for 12 benchmark problems.

En Fazla Kazanç Sağlayan Rota Bulma Problemleri, kontrol noktaları ve bu kontrol noktaları arasındaki bağlantıları içeren bir çizge üzerinde çalışır. Problemin amacı, bir başlangıç noktasından başlayıp, bitiş noktasında sonlanacak ve verilen maliyet kısıtını (mesafe, zaman, vb.) aşmayacak biçimde araç sayısı kadar ve toplamda en fazla kazancı sağlacak rotaları belirlemektir. Literatürde bu problemlerin tek araçlı şekli Oryantiring Problemi (OP), çok araçlı şekli ise Takım Oryantiring Problemi (TOP) olarak adlandırılmıştır.Bu tez çalışmasında, OP ve TOP çözümü için Değişken Komşu Arama (DKA) ve Parçacık Sürü Optimizasyonu (PSO) tabanlı iki yeni model geliştirilmiştir. Birinci model, DKA'nın bir versiyonu olan İndirgenmiş-DKA(İ-DKA) yöntemini kullanır. Geliştirilen modelde, İ-DKA geliştirilme amacı olan küresel aramanın yanında yerel arama için de kullanılır.İkinci model ise PSO tabanlıdır. PSO çözüm uzayını, popülasyonu oluşturan parçacıkların sistematik dolaşmasıyla tarar. PSO'nun doğrudan uygulanmasında iyi yerlerde yeterince detaylı arama yapamama ve erken yakınsama gibi zayıflıklarla karşılaşılır. Bu zayıflıklar sırayla, iyi yerler bulan parçacıklar için İ-DKA yerel aramasının çalıştırılması ve sonrasında o parçacıkların aramaya rasgele bir yerden devam ettirilmesi ile giderilmeye çalışılmıştır. Önerilen bu yeni PSO versiyonu, Güçlendirilmiş-PSO (G-PSO) olarak adlandırılmıştır. G-PSO üzerine, çözüme ihtiyaç duyacağı anda ayrık duruma getirilen ve kullanılan operatörler dahil tüm algoritmanın ayrık olarak ifade edildiği, iki yeni Ayrık G-PSO modeli geliştirilmiştir.Geliştirilen bu yeni modeller OP ve TOP için toplam 453 problemde test edilmiştir. Sonuçlar çözüm kalitesi ve performans açısından literatürdeki sonuçlarla karşılaştırıldığında, 12 problem için literatüre yeni sonuçlar kazandırılmış, diğer problemler için ise aynı yada rekabetçi sonuç üretildiği görülmüştür.