Gerçek Türkiye Verileri Kullanılarak Yol Bulma Algoritmalarının Simülasyonu ve Karşılaştırılması

Abstract

Yol bulma algoritmaları, sayısal olarak elde edilen konum bilgilerini kullanarak, istenen kaynak noktasından varış noktasına olası rotaları bulmayı sağlamaktadır. Bir kaynak noktasından hedefe olan en kısa yolun belirlenmesi ve özellikle dinamik olarak değişen ortamlarda hızlı bir şekilde hesaplanması önemli bir araştırma alanıdır. Yol bulma algoritmaları farklı araştırma alanlarındaki farklı problemlerin çözümünde kullanılmaktadır. Bu alanlardan bazıları; oyun programlama, yapay zekâ, mobil robotlar ve uygulamaları, insansız araçlar ve uygulamaları olarak örneklendirilebilir. Bu çalışmada 9 faklı yol bulma algoritması test edilmiş ve elde edilen sonuçlar karşılaştırılmıştır. Çalışmada kullanılan algoritmalar şu şekilde listelenmiştir; Dijkstra, Bellman-Ford, Floyd-Warshall, Johnson, Martin, Bidirectional Dijkstra, A* Algoritması, K Shortest Simple Path ve BHandari K-Disjoint algoritmasıdır. Her algoritma Türkiye’nin illeri arasındaki mesafe bilgisi ile oluşturulan graf kullanılarak test edilmiştir. İller arasındaki mesafe cetveli Karayolları Genel Müdürlüğünden edinilmiştir. Oluşturulan graf illerin komşuluklarını göstermektedir ve 81x81 boyutlarında bir komşuluk matrisi olarak programlanmıştır. Tüm algoritmalar Java programlama dili kullanılarak programlanmıştır ve test edilmiştir. Her algoritma birden fazla konum için test edilmiştir ve sonuçlar gösterilmiştir. Bu çalışma kapsamında, Türkiye merkezlerine (illerine) ait, gerçek uzaklık bilgilerini içeren programlanabilir komşuluk matrisi oluşturulup literatüre kazandırılmıştır. Gelecek çalışmalarda il merkezlerinin yanında ilçe merkezlerinin de uzaklık ve komşuluk bilgilerinin bulunduğu yüksek boyutlu komşuluk matrisinin oluşturulması ve farklı algoritmalar ile farklı kısıtlar eklenerek test edilmesi planlanmaktadır.

Path finding algorithms allow to find possible routes from the desired source point to the destination point using numerical obtained location information. It is an important research challenge to determine the optimal shortest path from a source point to the destination in a fast and precise manner, and especially in dynamically changing environments. Path finding algorithms are used to solve different problems in different areas. As an illustration, some of the most important areas are game development, artificial intelligence, mobile robots and unmanned vehicles. In this study, 9 different path finding algorithms were tested with same graph data and, the obtained results were compared. The algorithms we use in our study are as follows; Dijkstra, Bellman-Ford, Floyd-Warshall, Johnson, Martin, Bidirectional Dijkstra, A* algorithm, K Shortest Simple Path and BHandari K-Disjoint algorithm. Each path finding algorithm was tested using graph created from distance information from the provinces of Turkey. Data from the distance between the provinces is taken from the Republic of Turkey General Directorate of Highways. The graph used for the test is constructed from real distance data and contains information about the neighborhoods of the provinces. All algorithms were tested using the Java programming language. The open source JFX map library developed for java has been used to show the path between start and end points. Each algorithm was tested for more than one location and performance results were presented. In future studies, it is planned to using high dimensional graph data. Besides, graph data of province centers and district centers will be created together and tested with each algorithm.