A hybrid metaheuristic method to traveling salesman problem with drone
İHA'lı gezgin satıcı problemi için bir melez metasezgisel yöntem
- Tez No: 934800
- Danışmanlar: PROF. DR. SEROL BULKAN, DR. ÖĞR. ÜYESİ EMRE ÇAKMAK
- Tez Türü: Doktora
- Konular: Endüstri ve Endüstri Mühendisliği, Industrial and Industrial Engineering
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2023
- Dil: İngilizce
- Üniversite: Marmara Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Endüstri Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Endüstri Mühendisliği Bilim Dalı
- Sayfa Sayısı: 106
Özet
İ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.
Özet (Çeviri)
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 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 deliver 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 optimization field 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. The 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.
Benzer Tezler
- Gezgin satıcı probleminin çözümü için guguk kuşu arama algoritma tabanlı yeni bir hibrit metasezgisel yöntem
A new hybrid metaheuristic method based on cuckoo search algorithm for solving the traveling salesman problem
MUSTAFA FURKAN BERKAYA
Yüksek Lisans
Türkçe
2021
Endüstri ve Endüstri MühendisliğiKonya Teknik ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
DOÇ. DR. AHMET SARUCAN
- Optimizasyon için metasezgiseller ve makine öğrenmesine dayalı hibrit bir yaklaşım
A hybrid approach based on metaheuristics and machine learning for optimization
KADİR KUTAY ÖZGÜN
Doktora
Türkçe
2025
Endüstri ve Endüstri MühendisliğiEskişehir Teknik ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
PROF. DR. GÜRKAN ÖZTÜRK
- The roaming salesman problem and its application to election logistics
Dolaşım satıcısı problemi ve seçim lojistiğine uygulanması
MASOUD SHAHMANZARİ
Doktora
İngilizce
2019
Mühendislik BilimleriKoç Üniversitesiİşletme (İngilizce) Ana Bilim Dalı
DOÇ. DR. DENİZ AKSEN
- Gezgin satıcı problemlerinin çözümü için karınca kolonisi optimizasyonu tabanlı hibrit bir algoritma geliştirilmesi
Developing a hybrid algorithm based on ant colony optimization to solve travelling salesman problems
BATUHAN SAYGIN ARSLAN
Yüksek Lisans
Türkçe
2018
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolSelçuk ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
DOÇ. DR. MUSTAFA SERVET KIRAN
- Hipersezgisel yöntemlerle lojistik ağ tasarımı ve optimizasyon
Logistic network design and optimization using hyperheuristic methods
VURAL EROL
Doktora
Türkçe
2017
Endüstri ve Endüstri Mühendisliğiİstanbul Teknik ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
DOÇ. DR. MURAT BASKAK
PROF. DR. GÜLGÜN KAYAKUTLU