Application of shortest path algorithms in dynamic estimation and planning for route optimization

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.