A hybrid metaheuristic solution method to traveling salesman problem with drone - BULKAN, SEROL (My University, 2023)
The challenging idea of using drones in last-mile delivery systems of logistics addresses a new routing problem referred to as the traveling salesman problem with drone (TSP-D). TSP-D aims to construct a route to deliver parcels to a set of customers by either a truck or a drone, thereby minimizing operational costs. Since TSP-D is considered NP-hard, using metaheuristics is one of the most promising solutions. This paper presents a hybrid metaheuristic solution method of TSP-D based on two state-of-the-art algorithms: the genetic algorithm and ant colony optimization algorithm. Heuristics in TSP-D literature are based on two consequent decisions: truck routing and drone assignment. Unlike those in the existing literature, the proposed metaheuristic constructs both truck and drone routes simultaneously. Additionally, to the best of our knowledge, we introduce for the first time a solution method on the basis of an ant colony optimization approach to TSP-D. Additionally, we propose a binary pheromone framework for both drone and truck, diverging from the traditional pheromone structure. Computational experiments indicate that the proposed hybrid metaheuristic algorithm is able to generate optimal routes for provided instances of TSP-D benchmarking. In addition, the algorithm improves the best-known solutions of some instances found by rival heuristics.
Keywords: Sosyal ve Beşeri Bilimler; Sosyoloji; Kütüphanecilik; Bilgi Sistemleri, Haberleşme ve Kontrol Mühendisliği; Kontrol ve Sistem Mühendisliği; Bilgisayar Bilimleri; Veritabanı ve Veri Yapıları; Matematik; Temel Bilimler; Mühendislik ve Teknoloji; Social Sciences and Humanities; Sociology; Library Sciences; Information Systems, Communication and Control Engineering; Control and System Engineering; Computer Sciences; Database and Data Structures; Mathematics; Computer Science; Natural Sciences; Engineering and Technology; Mühendislik, Bilişim ve Teknoloji (ENG); Temel Bilimler (SCI); Sosyal Bilimler (SOC); Bilgisayar Bilimi; Mühendislik; Sosyal Bilimler Genel; OTOMASYON & KONTROL SİSTEMLERİ; BİLGİSAYAR BİLİMİ, YAZILIM MÜHENDİSLİĞİ; TELEKOMÜNİKASYON; MATEMATİK, UYGULAMALI; BİLGİ BİLİMİ VE KÜTÜPHANE BİLİMİ; Engineering, Computing & Technology (ENG); Natural Sciences (SCI); Social Sciences (SOC); COMPUTER SCIENCE; ENGINEERING; MATHEMATICS; SOCIAL SCIENCES, GENERAL; AUTOMATION & CONTROL SYSTEMS; COMPUTER SCIENCE, SOFTWARE ENGINEERING; TELECOMMUNICATIONS; MATHEMATICS, APPLIED; INFORMATION SCIENCE & LIBRARY SCIENCE; Fizik Bilimleri; Yazılım; Modelleme ve Simülasyon; Bilgisayar Ağları ve İletişim; Bilgi Sistemleri ve Yönetimi; Sosyal Bilimler ve Beşeri Bilimler; Control and Systems Engineering; Physical Sciences; Software; Modeling and Simulation; Computer Networks and Communications; Information Systems and Management; Social Sciences & Humanities; ant colony optimization; genetic algorithm; last-mile delivery; traveling salesman problem with drone; traveling salesman problem with drone; last-mile delivery; genetic algorithm; ant colony optimization