Drone ayrıt rotalama problemleri ve metasezgisel çözüm yaklaşımı

Abstract

Kapasiteli Ayrıt Rotalama Problemi (KARP), bağlı bir serimdeki zorunlu ayrıtlara hizmet verecek araçların kapasiteleri aşılmaksızın toplam tur mesafesini enküçükleyecek rotaların elde edilmesi olarak tanımlanır. KARP'ta araç kapasitesi sadece zorunlu ayrıtlara hizmet verilirken kullanılmaktadır. Literatürde KARP için geliştirilen çözüm yaklaşımları araştırılmış ve KARP'ın çözümü için metasezgisel yöntem olan Tavlama Benzetimi kullanılmıştır. Tavlama benzetimi algoritmasının bileşenleri KARP'a uygun olarak tasarlanmıştır. Önerilen algoritma literatürdeki test problemlerinin çözümünde kullanılmış ve önerilen algoritmanın KARP için kaliteli çözümleri makul çözüm sürelerinde elde edebilme yeteneğinin olduğu gösterilmiştir. Çalışmanın devamında çeşitli alanlarda uygulaması olan gözetleme drone'ları ele alınmış ve bağlı olmayan serimler üzerinde tariflenen, yeni bir ayrıt rotalama problemi olan Drone Ayrıt Rotalama Problemi araştırılmıştır. Bu çalışmada kullanılan gözetleme drone'larının enerji kapasiteleri mevcuttur ve bu kapasitelerin aşılmaması gerekmektedir. Gözetleme drone'ları ayrıtlardan boş geçiş yaparken sadece katedilen mesafeden kaynaklı olarak bir enerji harcamakta, hizmet verirken hem katedilen mesafeden kaynaklı hem de gözetleme esnasında aktif hale getirilen sensörler, görüntüleme ve haberleşme aygıtları sebebiyle enerji harcamaktadır. Dolayısıyla drone kapasiteleri hem ayrıtlara hizmet verirken hem de ayrıtlardan boş geçiş yaparken kullanılmaktadır. Söz konusu problem Boş Geçiş Talepli Drone Ayrıt Rotalama Problemi (BGT-DARP) olarak isimlendirilmiştir. Yapılan çalışma kapsamında BGT-DARP'ta karşılaşılabilecek özel durumlar araştırılmış ve toplamda 7 yeni problem literatüre kazandırılmıştır. KARP'ta başarılı sonuçların elde edilmesini sağlayan tavlama benzetimi algoritması bileşenlerinde bazı değişiklikler yapılarak ilgili problemlerin çözümünde kullanılmıştır. Geliştirilen algoritmanın performansı türetilen test problemleri kullanılarak test edilmiş ve elde edilen sonuçlar detaylı olarak tartışılmıştır. Önerilen algoritma ve bileşenlerinin BGT-DARP ve çeşitlerini çözmede etkin ve kullanışlı olduğu gösterilmiştir.

Capacitated Arc Routing Problem (CARP) is defined as obtaining routes that minimize the total tour distance without exceeding the capacities of the vehicles serving the required edges in a connected graph. Simulated Annealing algorithm is used to solve the CARP. The components of the Simulated Annealing algorithm are designed in accordance with the CARP. It is shown that the proposed algorithm is capable of obtaining high quality solutions for the CARP in reasonable computation times. After that, surveillance drones which have applications in various fields are discussed and Drone Arc Routing Problem, a new arc routing problem in a disconnected graph, is investigated. When surveillance drones do not serve the edges, they only consume as much energy as the traveled distance, and when serving the edges, they consume as much as energy demanded by both the traveled distance and the sensors, imaging, communication devices activated during surveillance. That is to say, drone capacities are used both when serving the edges and when deadheading the edges. The related problem is called as Drone Arc Routing Problem with Deadheading Demand (DARP-DD). Within the scope of this study, special cases of DARP-DD are investigated and 7 new problems are introduced to the literature. The Simulated Annealing algorithm, which provides obtaining high quality solutions for the CARP, is used to solve the DARP-DD and its variants. It is shown that the proposed algorithm and its components are effective and useful in solving the DARP-DD and its variants.