A hybrid metaheuristic method to traveling salesman problem with drone - Sezer, Noyan Sebla (My University, 2023)
İnsansız Hava Araçları (İHA) teknolojisinin son yıllardaki hızla gelişimi ve lojistik süreçlerde kullanımının önerilmesi ile İHA’ lı Gezgin Satıcı Problemi (GSP-İHA) önemli bir araştırma alanı olarak ortaya çıkmıştır. Bu tezde ele alınan GSP-İHA, bir yer aracı ile bir hava aracının dağıtım sistemlerinde entegre kullanılmasıyla geleneksel gezgin satıcı probleminin bir uzantısı olan, İHA destekli teslimat rotasını optimize etmeyi amaçlayan yeni bir kombinatoryal optimizasyon problemidir. Tez kapsamında, bu problemin çözümü için metasezgisel bir yöntem geliştirilerek optimizasyon alanına katkı sağlamak ve İHA destekli teslimat süreçlerinde benzer problemlerin çözümü için de görüş oluşturabilmek amaçlanmıştır. Bu amaç ile hibrit bir metasezgisel algoritma olan Karınca Araması Temelli Genetik Algoritma (KA-GA) çözüm yöntemi önerilmiştir. KA-GA algoritması, mevcut gelişmiş metasezgisel yöntemlerden Genetik Algoritma (GA) ve Karınca Kolonisi Optimizasyonu (KKO) algoritmasının, GSP-İHA için uyarlanmış hibrit bir uygulamasıdır. KA-GA algoritması, GA’ nın standart optimizasyon adımlarına, geleneksel KKO algoritmasından esinlenilen bir arama prosedürü olan Karınca Araması (KA)’ nı dahil etmektedir. KA-GA algoritması, rota kurma sürecini problem özgü özellikleriyle birleştirerek, GA ile üretilen bir çözümün KA prosedürü aracılığıyla tam bir GSP-İHA turu olarak tamamlanmasına olanak sağlamaktadır. KA, karıncaların davranış metaforunu taklit ederek, müşteri noktalarını GSP-İHA turu olarak sıralama işlevini yerine getiren stokastik süreçli bir algoritmadır. Ayrıca, önerilen algoritma, klasik KKO 'nun feromon yapısından farklı bir prosedür kullanmaktadır. Bir GSP-İHA çözümünde iki araç tipi için, farklı feromon yapıları gerektiren iki tür alt rota ortaya çıktığı gözlendiğinden, KA-GA algoritması için ikili-feromon yapısı geliştirilmiştir. Gerçekleştirilen deneyler, GSP-İHA formülasyonunun geleneksel araç rotalamasına göre avantajlarını ve önerilen KA-GA algoritmasının GSP-İHA’ yı etkili bir şekilde çözebilme yeteneğini destekleyen kanıtlar sunmaktadır. Sayısal sonuçlar, önerilen algoritmanın test problemlerinin optimum çözümlerini tutarlı olarak elde ettiğini, belirli rakip algoritmalardan daha iyi performans gösterdiğini ortaya koymuştur ve geleneksel rotalama problemine İHA entegre etmenin faydalarını göstermiştir. Bu tez, yeni hibrit bir metasezgisel algoritma önererek GSP-İHA alanına katkı sağlamaktadır.

The Traveling Salesman Problem with Drone (TSP-D) has emerged as a prominent research area in recent years, driven by the rapid advancements in drone technology and by the idea of utilizing drones in delivery. This thesis addresses the TSP-D, a relatively new combinatorial optimization problem that extends the traditional traveling salesman problem by introducing a drone that can delivery parcels to customers in addition to a ground vehicle and which seeks to optimize that drone-aided delivery route. This thesis aims to contribute to the field of optimization and provide insights for solving similar problems in domains of drone aided delivery processes. For this contribution, the thesis proposes a novel hybrid metaheuristic algorithm, the Genetic Algorithm with Ant Search-Based Solution Method (GA-AS). The GA-AS algorithm is based on the implementation of the current state-of-the-art metaheuristic algorithms, Genetic Algorithm (GA) and Ant Colony Optimization (ACO), by hybridizing and customized them for TSP-D features. The GA-AS framework follows the standard optimization steps of the GA and incorporates a new solution searching procedure, Ant Search, which draws inspiration from the traditional ACO algorithm. The GA-AS algorithm modifies the route construction process by incorporating problem-specific features, allowing a solution generated in the GA stage to be transformed into a complete TSP-D tour through the AS stage. The AS algorithm is a stochastic process imitates the ant behavior metaphor to construct tours which responsible for selecting customer nodes to be sequenced in the TSP-D tour. Besides, the proposed algorithm employs a unique procedure on the pheromone formulation, distinct from the pheromone structure of ACO. Binary-pheromone framework is discussed to be introduced in the GA-AS algorithm, since a TSP-D solution involves two types of sub-routes emerged with requiring separate pheromone frameworks for both truck and drone. The computational experiments conducted in this thesis provide substantial evidence supporting the advantages of the TSP-D formulation and the capability of the GA-AS algorithm to effectively tackle the TSP-D. The algorithm consistently produced optimal solutions of benchmarking problems, outperformed certain rival algorithms, and demonstrated the benefits of integrating a drone into traditional truck travel. This research contributes to the field of TSP-D by introducing a novel hybrid metaheuristic algorithm.
İHA’lı gezgin satıcı problemi için bir melez metasezgisel yöntem
Keywords: ant colony optimization; drone delivery; drone'lu teslimat; Endüstri mühendisliği; genetic algorithm; genetik algoritma; GSP-İHA; Industrial engineering; karınca kolonisi optimizasyonu; TSP-D