Akıllı ulaşım sistemleri için yapay bağışıklık sistemleri ve genetik algoritma ile yeni stokastik en kısa yol algoritmalarının geliştirilmesi

Abstract

Akıllı Ulaşım Sistemlerinin (AUS) gelişmesine bağlı olarak gerçek zamanlı trafik yönetimi ve rota rehber modellerinde en kısa yol (EKY) bilgisine ihtiyaç duyulmaktadır. Klasik EKY algoritmaları kenar verilerini karşılaştırarak EKY bilgisine ulaştığından ağın geneli için ortaya konan stokastik problemlerde yetersiz kalmaktadır. Bu çalışmanın amacı stokastik bir ulaşım ağında EKY problemini Genetik Algoritma (GA) ve Yapay Bağışıklık Sistemi (YBS) yardımıyla çözerek Akıllı Ulaşım Sistemleri için ihtiyaç duyulan EKY bilgisini sağlamaktır.Bu çalışmada farklı büyüklükteki ağlar için üç farklı GA ve YBS algoritması oluşturulmuştur. Ulaşım ağlarında her bir kenarın zaman ve yakıt değerleri için ihtimal dağılımı verilerek çevre şartlarından etkilenen stokastik bir yapı modellenmiştir. Stokastik bir ulaşım ağında EKY problemini çözmek için iki farklı karar kriterine göre modeller oluşturulmuştur. 1. Modelde verilen süre veya yakıtla gitme ihtimali en yüksek yol ve 2. Modelde ise hedef ihtimalle en az süre veya yakıtla gidilen yolu bulmak amaçlanmıştır. Öncelikle GA ve YBS'nin populasyon sayısı, nesil sayısı, çaprazlama olasılığı, mutasyon olasılığı ve klonlama oranı gibi parametrelerinin en uygun seviyelerini belirlemek için Taguchi Metodu kullanılmıştır. Önerilen modellerin etkinliğini göstermek için deterministik ağda EKY problemi GA ve YBS yöntemleriyle çözülerek elde edilen sonuçlar klasik EKY algoritmalarından olan Dijkstra ve Floyd algoritmaları ile karşılaştırılmıştır. Ayrıca her bir ağ, çok amaçlı EKY problemi olarak Pareto tekniği ile çözülmüştür. En az maliyetli yol, Pareto çözümleri arasında maliyet değerlendirilmesi yapılarak, AUS kullanıcılarına önerilmiştir. Sonuç olarak, önerilen GA ve YBS modellerinin stokastik EKY problemlerini çözmede etkili oldukları ve YBS modelinin problemi GA'dan daha kısa hesap süresinde çözdüğü görülmüştür.

Based on the development of the intelligent transportation systems (ITS), the shortest path information is required for the real time traffic management and route guidance models. Classical shortest path algorithms are ineffective in the stochastic problems related to the whole network due to providing shortest path information by comparing the link data. The aim of this study is to provide the shortest path information in the stochastic network by Genetic Algorithm (GA) and Artificial Immune System (AIS) for ITS.In this study, three different GA and AIS algorithms are built for the different size of networks. A stochastic structure affected by the environmental, road and traffic conditions and driver is modeled by giving the probability density functions for the time and fuel data concerning each edge. Models are designed according to two different decision criteria to solve the shortest path problem in a stochastic network. It is aimed to search that in the first model, the path which has highest probability for a given travel time or fuel consumption, in the second model, the path which has the lowest travel time and fuel consumption for a given target probability. First of all, Taguchi method is used to determine the most suitable levels of the factors such as number of population and crossover probability, mutation generation, crossover and mutation probability, and cloning ratio for GA and AIS. The results from GA and AIS models are compared to the ones from classical Dijkstra and Floyd algorithms for a deterministic network. After each network is also solved as multi-objective shortest path problem by Pareto technique, shortest path with minimum cost is recommended to ITS users by making cost evaluation among all pareto solutions. As a result, it is seen that proposed GA and AIS models are effective in solving the stochastic shortest path problems and, AIS model solves the problem in a shorter computing time than the GA model.