İnsansız hava aracıyla araç rotalama problemine genetik algoritma yaklaşımı
Genetic algorithm approach for drone routing problem
Yazar: AHMET MACİT AYTEKİN
Danışman: PROF. NİHAN ÇETİN DEMİREL
Yıldız Teknik Üniversitesi / Fen Bilimleri Enstitüsü / Endüstri Mühendisliği Ana Bilim Dalı / Endüstri Mühendisliği Bilim Dalı
Derece: Yüksek Lisans, 2023
Konu: Endüstri ve Endüstri Mühendisliği = Industrial and Industrial Engineering

Özet:
Araç Rotalama Problemi (ARP) bir veya birden çok sayıdaki depodan tüm müşterilerin taleplerini karşılayacak ürün dağıtım rotasını en optimal biçimde belirlemeyi hedefler. Müşteriler için ürün tedariği başta karayolu yani kamyonlar ve deniz yolu kullanılırken gelişen teknolojiler, artan tedarik masrafları ve trafik nedenleri ile birlikte  yavaş yavaş yerini insansız hava araçlarına bırakmaya başlamıştır. Başta askeriye tarafından kullanılan bu ulaştırma yöntemi günümüzde Amazon ve Google gibi büyük şirketler tarafından kullanılmaya başlanmıştır. Lojistikte kullanılan insasız hava araçlarının (İHA) belirlenen hedeflere paketleri en uygun maaliyet ve kısa sürede iletmeleri için bir rota planlamasına ihtiyaç duyulmuştur. ARP'nin çözümü için geleneksel yöntemler ve sezgisel yöntemler günümüzde kullanılmaktadır. Bu tür problemler N.P olarak tanımlandığı için geleneksel algoritmalarla kesin çözüme ulaşmak maaliyetli ve büyük zaman istediği için yerini kısa zamanda iyi sonuçlar elde edilebilen sezgisel çözüm yöntemlerine bırakmıştır.
Bu çalışmada optimum rotanın belirlenmesi için Genetik Algoritma (GA) kullanılmıştır. Genetik Algoritma ARP çözümü için en yaygın kullanılan sezgisel yöntemlerden birisidir. Çalışmada Python programlama dili kullanılarak İHA için en uygun rota belirlenmiştir. Çalışmada özel bir şirketin 3 büyük il (İstanbul-Ankara-İzmir) için olan verileri kullanılmıştır. Problemin çözümlenmesi için ilk aşamada İHA'nın gitmesi gereken noktaların koordinatları belirlenerek haritadaki dağılımları tespit edilmişir.  Ardından tedarik noktaları arasında İHA'nın sevkiyata başlayacağı ve pili bittiğinde dönüp şarj olabileceği depo noktasının yeri tespit edilmiştir. İkinci aşamada GA sezgisel yöntemi kullanılarak İHA için optimum veya optimuma yakın rota belirlenmiştir. Son aşamada İHA'nın uçuş menzili genetik algoritma ile bulunan gen dizimine entegre edilerek İHA'nın gerçek sevkiyat rotası hesaplanmıştır.

Abstract:
Vehicle Routing Problem (ARP) aims to determine the product distribution route in the most optimal way that will meet the demands of all customers from one or more warehouses. Unmanned Aerial Devices (UAV) have been replacing once common conventional ones of trucks and seaways pursuant to the increasing supply cost and traffic issues. This transportation method, which was used primarily by the military, has now been used by large companies such as Amazon and Google. A route planning was needed for the unmanned aerial vehicles (UAV) used in logistics to deliver packages to the determined destinations at the most appropriate cost and in a short time. Today traditional methods and heuristic methods are used to solve ARP problems. Since such problems are defined as n.p., reaching the exact solution with traditional algorithms is costly and takes a lot of time consuming, so it has been replaced by heuristic solution methods that can get good results in a short time.
In this study, Genetic Algorithm (GA) was used to determine the optimum route. The Genetic Algorithm is one of the most widely used heuristics for solving ARP problems. In this context, the most suitable route for the UAV was determined using the Python programming language. In the study, data of a private company for 3 big cities (Istanbul-Ankara-Izmir) were used. In order to solve the problem, in the first stage, the coordinates of the points where the UAV needs to go were determined and their distribution on the map was determined. Then, the location of the storage point where the UAV will start shipping and return to charge when its battery runs out was determined among the supply points. In the second stage, the optimum route for the UAV was determined using the GA heuristic method. In the final stage, the flight range of the UAV was integrated into the optimum gene sequence found by the genetic algorithm, and the actual delivery route of the UAV was calculated.