Giriş:
Otomatik yönlendirmeli araç uygulamalarının birincil amacı, otomatik yönlendirmeli araçların bir depo veya üretim tesisindeki hareketini optimize etmektir. Otomatik yönlendirmeli araçların hareketi, ürünleri bir konumdan diğerine taşımak için gereken süreyi ve maliyeti en aza indirmek için verimli olmalıdır. Bu amaca ulaşmak için seçtiğimiz Dijkstra algoritması sayesinde kaynak düğüm ile grafikteki diğer tüm düğümler arasındaki en kısa yol bulunmaktadır.
Dijkstra algoritması haberleşme, ulaşım, lojistik, robotik ve havacılık alanlarında yaygın olarak kullanılmaktadır. Otomatik yönlendirmeli araçların en kısa yolu seçmesi, ürünleri taşımak için gereken süreyi ve maliyeti azaltmaya yardımcı olmaktadır.
Özetle, otomatik yönlendirmeli araç uygulamalarında Dijkstra algoritmasının kullanılması, bir grafikteki düğümler arasındaki en kısa yolu bularak otomatik yönlendirmeli araçların bir depo veya üretim tesisindeki hareketini optimize etmeye yardımcı olmaktadır.
Literatür:
Dijkstra algoritmasının 1956 yılında bilgisayar bilimcisi Edsger W. Dijkstra tarafından tasarlanmış ve üç yıl sonra yayınlanmış olduğu bilinmektedir. Edsger W. Dijkstra’ nın Rotterdam'dan Groningen'e seyahat etmenin en kısa yolunun ne olduğunu düşünürken yirmi dakika içerisinde tasarladığı bir algoritma olmuştur [1]. Günümüzde en kısa yolu bulma probleminin çözümlerinden biri olarak aktif olarak kullanılmaktadır. Literatürde haberleşme, ulaşım, lojistik, robotik ve havacılık alanlarında yaygın olarak uygulamaları görülmektedir. Demirkol vd. günümüzde internet dünyasındaki ihtiyaçların çoğalması ile birlikte büyüyen ağ yapılarının içerisindeki veri aktarımı sorununa Dijkstra algoritması ile bir çözüm sunmuştur[2]. Makalede Bellman-Ford algoritması ile Dijkstra algoritması karşılaştırılmış olup Dijkstra algoritmasının kesin, Bellman-Ford algoritmasının tahmini bir sonuç verdiği vurgulanmıştır. Bülbül, bilgisayar oyunu tasarımında üç boyutlu bir ortamda en kısa yol problemini Dijkstra ve A star algoritmalarını modifiye ederek uygulamasını sunmuştur [3]. Bayzan, araç rotalama problemininin çözümünü Dijkstra algoritması kullanarak benzetim ortamında sunmuştur [4]. Özdemir, Sacar ve Özcan, Pekin’den Londra’ya ulaşan demir yolu ağı için en kısa yolun hesaplanması amacıyla Dijkstra algoritması uygulamasını kullanmıştır [5]. Koca ve Doğan, Dijkstra algoritmasını çok katlı ve katlar arası geçiş olan bir binada mobil robotların yönlendirilmesine uygulamıştır [6]. Boğar, yol planlama probleminin çözümü için genetik algoritma ve Dijkstra algoritmasını birlikte içeren hibrit bir optimizasyon yöntemi önermiştir [7]. Alkan ve Aydın, Türkiye haritası üzerinde şehirlerarasındaki en kısa yolları farklı yol bulma algoritmalarını uygulayarak karşılaştırmıştır [8]. Sonuçlarda Dijkstra algoritmasının Bellman-Ford algoritmasından sonra en kısa sürede sonuçlandığı görülmektedir. Şahin, insanlı veya insansız gemilere bulanık analitik hiyerarşi süreci ve genişletilmiş Dijkstra algoritması yöntemlerini birlikte kullanarak bir rota optimizasyonu uygulaması sunmuştur [9]. Atay ve Seçgin, kablosuz algılayıcı ağlarda yönlendirme algoritması olarak kullanılan Dijkstra ve Bellman-Ford algoritmalarının karşılaştırmasını yapmıştır [10]. Dhulkefl, Durdu ve Terzioğlu, insansız hava araçlarının engellerden kaçınarak hedef noktasına ulaşılmasını sağlayacak en kısa yolun belirlenmesi uygulamasını sunmuşlardır [11].
Tarihçe:
Leonhard Euler tarafından, 1736 yılında, Königsberg'in yedi köprüsü (Almanca: Die Sieben Brücken von Königsberg) adında günümüzde hâlâ popülerliğini koruyan bir problem ile ilgili olarak yazılan bir makale, çizge kuramının kesin başlangıç tarihidir [12]. Königsberg kentinde Eski ve Yeni Pregel nehirlerinin birleşerek oluşturduğu Pregel nehri Şekil 1’ deki gibi şehri dört bölüme ayırmakta ve bu bölgeleri birleştiren yedi köprü bulunmaktadır. Problem ise “Bütün köprülerden bir ve yalnız bir defa geçmek koşulu ile bir yürüyüş yapılabilir mi?” sorusu ile başlamaktadır[12].
Euler, problemi Şekil 2’ deki gibi kara parçalarına ve yollara bölmüştür. Kara parçalarını harfler, köprüleri ise sayılar ile ifade etmeyi tercih etmiştir. Daha sonra Şekil 2’ de göründüğü gibi kara parçalarını nokta, köprüleri ise çizgiler olarak ifade etmiştir. Bu şekilde ifadesi çizge (graf) olarak isimlendirilmiştir.
Sonuç:
HKTM Ar-Ge birimi projelerinden biri olan otomatik yönlendirmeli araç projesinde rota oluşturulmasına temel olması adına Dijkstra algoritması kullanılmıştır. Başlangıç düğümünden diğer tüm düğümlere olan en kısa mesafeyi ve ziyaret edilen düğümleri sunan bu algoritma projede otomatik yönlendirmeli aracın hedef ve o anki pozisyonu arasındaki tüm düğüm noktalarını bulmak için hazırlanan yazılım içerisinde kullanılmıştır.
Kaynakça:
[1] Frana, Phil (August 2010). "An Interview with Edsger W. Dijkstra". Communications of the ACM. 53 (8): 41–47. doi:10.1145/1787234.1787249.
[2] Ö. E. Demirkol, A. Demirkol, “Dijkstra ve Bellman-Ford En Kısa Yol Algoritmalarının Karşılaştırılması” SAU Fen Bilimleri Enstitüsü Dergisi, 7. Cilt, 3. Sayı, 2003.
[3] E. Bülbül, “Değişen 3b Ortamda En Kısa Yol Algoritmaları”, Yüksek Lisans Tezi, Ankara Üniversitesi Fen Bilimleri Enstitüsü, Ankara, 2015.
[4] Ş. Bayzan, “Araç Rotalarının En Kısa Yol Algoritmaları Kullanılarak Belirlenmesi Ve .Net Ortamında Simülasyonu”, Yüksek Lisans Tezi, Pamukkale Üniversitesi Fen Bilimleri Enstitüsü, Denizli, 2005.
[5] S. Özdemir, Ö. Sacar, E. Özcan, “Dijkstra Algoritması Kullanılarak İpek Yolu Koridorları Arasında En Kısa Ulaştırma Güzergâhının Belirlenmesi Demiryolu Mühendisliği”, Railway Engineering Sayı:13, Sayfa: 97-105, 2021.
[6] G. O. Koca, Ş. Doğan, “Üç boyutlu bir arama yüzeyi için mobil robotların yol planlaması”, Fen Bilimleri Dergisi BEU Journal of Science 8 (1), 298-307, 2019.
[7] E. Boğar, “Tek Ve Çok Amaçlı Robot Yol Planlama Problemi İçin Hibrit Bir Optimizasyon Yöntemi”, Yüksek Lisans Tezi, Pamukkale Üniversitesi Fen Bilimleri Enstitüsü, Denizli, 2016.
[8] M. ALKAN and M. AYDIN, "Simulation and Comparison of Pathfinding Algorithms using Real Turkey Data," 2018 International Conference on Artificial Intelligence and Data Processing (IDAP), 2018, pp. 1-4, doi: 10.1109/IDAP.2018.8620849.
[9] B. Şahin, “Bulanık Analitik Hiyerarşi Süreci ile Genişletilmiş Dijkstra Algoritmasını Kullanarak Rota Önceliklendirme”, Journal of Eta Maritime Science, 2019.
[10] C. Atay, S. Seçgin, “Kablosuz Algılayıcı Ağlarda Yönlendirme Algoritmalarının Performans Analizi”, İzmir,2015.
[11] E. J. Dhulkefl, A. Durdu, H. Terzioğlu, “Dijkstra Algorıthm Usıng Uav Path Planning”, Konya Mühendislik Bilimleri Dergisi, c. 8, Özel Sayı, ss. 92-105, 2020. DOI: 10.36306/konjes.822225.
[12] Çizge teorisi - Vikipedi (wikipedia.org) Erişim Tarihi:25.11.2022
[13] Wilson, Robin J. Introduction to Graph Theory, Harlow, Addison Wesley Longman Limited, 4th edition, 1996.