Rota optimizasyonu için dinamik tahminleme ve planlamada en kısa yol algoritmalarının uygulanması
Application of shortest path algorithms in dynamic estimation and planning for route optimization
Yazar: KHALED MILOD KHALIFA HUDOUD
Danışman: DR. ÖĞR. ÜYESİ YASEMİN GÜLTEPE
Kastamonu Üniversitesi / Fen Bilimleri Enstitüsü / Malzeme Bilimi ve Mühendisliği Ana Bilim Dalı
Derece: Yüksek Lisans, 2021
Konu: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol = Computer Engineering and Computer Science and Control

Özet:
Araç yönlendirme problemi, ulaşım, dağıtım ve lojistik endüstrisindeki optimizasyon problemlerine atıfta bulunan genel bir isimdir. Esas olarak bir dizi müşteriye bir dizi araçla hizmet vermeye odaklanırlar. Rota planlama teknikleri, bir yol haritasında bir başlangıç noktasından bir varış noktasına en uygun rota ve en uygun maliyeti amaçlayan araç yönlendirme probleminin ana görevlerinden biridir. Araba yolculuğu sırasında karayolu trafik koşulları değişebileceğinden (örneğin, trafik sıkışıklığının artması/azalması, yol olayları vb.) trafik koşullarında bir güncelleme mevcut olur olmaz en uygun rota yeniden değerlendirilmelidir. Literatürdeki mevcut algoritmalar arasından uygun bir rota planlama algoritmasının seçilmesi, bunu gerçek karayolu ağlarında uygulamak, herhangi bir ulaşım uygulaması için önemli bir görevdir. Bu tez çalışmasında, önce farklı rota planlama algoritmalarının bir sınıflandırması sunulmuştur ve ardından gerçek yol ağlarında uyguladıklarında performanslarının karşılaştırılması analiz edilmiştir. Karşılaştırma amacıyla, geliştirilen bilgisayar yazılımı kullanılarak çalışma zamanı sırasında bu algoritmaların davranışları, benzetim yoluyla test edilmiştir. En çok bilinen en kısa yol algoritması olan A*(yıldız), yazılımda uygulanan ilk algoritma olarak seçilmiştir. Bir arabanın mevcut en uygun rota ve en uygun maliyeti etkileyen herhangi bir trafik durumu güncellemesinin alınması üzerine, algoritmayı yeniden uygulamak ve bu araba rotasını buna göre değiştirmek için geliştirilen yazılım kullanılır. Tez çalışmasında diğer en kısa yol algoritmalarından Floyd-Warshall ve Dijkstra algoritmaları da test edilmiştir ve elde edilen en iyi rotanın kalitesine göre performansları karşılaştırılmıştır. Geliştirilen sistem, popüler bir programlama dili olan Java dili ile yazılmış olup, algoritmaların ve sistemin düzgün çalışması için gerekli tüm veriler JavaDB veri tabanında depolanmış olup modüler bir yapıya sahiptir. Sonuç olarak sistemde kullanılabilirlik testi uygulanmıştır. Sistem değerlendirmesi başarıyla gerçekleştirilmiştir. Tez çalışması, otomatik ve manuel tur planlaması arasındaki farklı uygulama beklentilerini çözmemizi sağlayacaktır.

Abstract:
The vehicle routing problem is a generic name referring to optimization problems in the transportation, distribution and logistics industry. They mainly focus on serving a range of customers with a range of vehicles. Route planning techniques are one of the main tasks of the vehicle orientation problem aiming at the most appropriate route and the most cost-effective from a starting point to a destination in a road map. Since road traffic conditions may change during car travel (e.g. increase / decrease in traffic congestion, road events, etc.), the most suitable route should be re-evaluated as soon as an update of traffic conditions is available. Selecting an appropriate route planning algorithm from among the algorithms available in the literature and applying it in real road networks is an important task for any transportation application. In this thesis, first a classification of different route planning algorithms is presented and then the comparison of their performance when applied in real road networks is analyzed. For comparison, the behavior of these algorithms during runtime is tested by simulating using the developed computer software. The best known shortest path algorithm A * (star) was chosen as the first algorithm implemented in the software. Upon receiving any traffic condition updates that affect a car's current best route and the most cost-effective, the software developed to re-apply the algorithm and change this car route accordingly. In the thesis study, Floyd-Warshall and Dijkstra algorithms, which are among the other shortest path algorithms, were also tested and their performances were compared according to the quality of the best route obtained. The developed system is written in Java, which is a popular programming language, and all the data required for the proper operation of the algorithms and the system are stored in the JavaDB database and has a modular structure. As a result, usability test was applied on the system. System evaluation has been carried out successfully. The thesis work will enable us to resolve the different application expectations between automatic and manual tour scheduling.