Solving a modified TSP problem by a greedy heuristic for cost minimization

Büyük bir alanı anında fotoğraflayabilmek yalnızca uydular tarafından mümkündür. Uydular, fotoğraf/izleme süreci için gerekli zamanı azaltmaya yardımcı olabilir, ancak uydu görüntüleri her zaman mevcut değildir ve bu görüntüler mevcut olsa dahi karar vericiler için değerlendirilmesi kolay değildir. Bu sebeple karar vericiler, önceden tanımlanmış bölgenin fotoğraflarını çekmek için insansız hava araçları da denilen gözetim uçakları kullanmaktadır. Bir alanı tanımlayan bir düğüm kümesi (ağ) göz önüne alındığında, her düğüm izlenmeli ve analiz edilmelidir. Bu anlamda sorun, Gezgin Satıcı Problemi olarak tanımlanabilir. Bununla birlikte, her düğüme gitmek ve fotoğraf çekmek pratik değildir. Bunun yerine göreceli yükseklik kavramından yararlanılabilir, yani başka bir düğümden daha yüksek ya da daha uygun bir konumda bir düğüm varsa, dronlar daha yüksek konumlandırılmış düğüme gidebilir, bir fotoğraf çekebilir ve mevcut düğüm tarafından görülen diğer düğümleri otomatik olarak izlemiş olur. Bu çalışmada, yukarıdaki gibi modifiye edilmiş Gezgin Satıcı Problemi (MGSP) için, hepsi ziyaret edilmeksizin tüm düğümleri kapsayan ve toplam seyahat masrafı ile fotoğraf çekme maliyetini minimize eden bir matematiksel model sunulmaktadır. Ardından, çözüm bulmak için sezgisel bir yöntem önerilmekte ve performansı değerlendirmek için sezgisel tarafından bulunan değerler optimum çözümlerle ve alt sınır çözümleri ile karşılaştırılmaktadır. Düşük fotoğraf maliyeti olan durumlarda algoritmanın optimum çözümün ve alt sınır değerlerinin %1 fazlasına kadar iyi sonuçlar verdiği, yüksek maliyetli durumlarda ise nodlar arası görsel erişime bağlı olarak optimum çözümün veya alt sınır değerlerinin %5-10 fazlasına kadar sonuçlar üretebildiği görülmektedir.