A Real-Time Dynamic Route Control Approach on Google Maps using Integer Programming Methods

Abstract

The Travelling Salesman Problem (TSP), defined as returning to the starting point after visiting all the points with the least cost, is the modeling framework for many engineering problems. In this study, a real-world application that draws the real time route of the TSP using the current traffic intensity information taken from Google Maps is proposed. In developing the GUI application, different integer programming methods such as Exhaustive Search, Heuristic A-Star Search, BitMask Dynamic Programming, Branch-and-Bound Algorithm, and Greedy Search have been implemented with the help of Google APIs. All these methods, sometimes even Greedy Search, have given the same TSP route for any of test cases. Additionally, a dynamic route update mechanism with Hamiltonian Circuit function is adopted to enhance the conventional TSP system. Sometimes the TSP route list changes according to some sudden reasons or when the traffic intensity changes while travelling the nodes. In this case, the proposed system updates its current route for the rest of the nodes by using the enhanced system to keep the total travel-cost minimum. A user-friendly and dynamic interface, displaying visually the shortest route in distance or duration on Google Maps, has been developed by adding different features such as travelling mode options, remaining route distance and time. This proposed study, which is powered by different algorithms with visual artifacts, might be accepted as a unique blueprint in its field.