Sezgisel algoritma kullanılarak en iyi yol rotalanması ve bir uygulama

Abstract

Bu çalışmada çözülmesi zor problemlerden biri olan Gezgin Satıcı Problemi ele alınmıştır. GSP sezgisel yöntemlere yol göstermesi amacıyla en iyi sonuçların elde edilebilmesi için çözümüne yönelik karınca kolonisi algoritması kullanılmıştır. Amaç GSP üzerinde karınca kolonisi algoritması kullanılarak İstanbul Halk Ekmek şirketinin ekmek dağıtım araçlarının rotalama probleminin çözülmesidir. Karıncaların aralarındaki iletişimi sağlamaları için salgıladıkları feromon adlı sıvı haberleşmeleri açısından en temel madde olarak bilinmektedir. Bu algoritmada bulundukları alanda en kısa yolu bulma mantığıyla çalışan yapay karıncalardan faydalanılmıştır. Programımızdaki amaç, dağıtım araçlarının büfelere en kısa yoldan rota hesaplaması yapılmasıdır. Programda oluşturulan rota Google maps ile harita üzerinden görüntülenmektedir. Yapılan uygulamanın etkinliğini ve performansını ölçmek için aynı rotalar Excel- Solver (Evolutionary) çözülüp karşılaştırılmıştır.

In this study, Travelling Salesman Problem (TSP), an NP-hard problem, is addressed. In order to get the best results with a view to directing TSP heuristics, the ant colony algorithm was used for solution purposes. The purpose was to solve the problem of setting a course for the bread distribution trucks of Istanbul Halk Ekmek (Public Bread) Company using the ant colony algorithm on TSP. A liquid called Pheromone, which ants release in order to establish communication among them, is known as the most fundamental matter to provide this communication. In this research, artificial ants, which function with the logic of finding the shortest path in the area where they are located, were utilized. The purpose of our programme is to determine the shortest route for the arrival of the distribution trucks to the kiosks where bread is sold to the public. The route developed by the programme is displayed over Google maps. In order to measure the efficiency and performance of the implemented application, the same roots Excel-Solver (Evolutionary) were solved and compared.