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


Hamza Mehmet EROL


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.


How to Cite
Faruk BULUT, & Hamza Mehmet EROL. (2018). A Real-Time Dynamic Route Control Approach on Google Maps using Integer Programming Methods. International Journal of Next-Generation Computing, 9(3), 189–202. https://doi.org/10.47164/ijngc.v9i3.148


  1. Aygn, S. and Akay, M. 2015. Matlab paralel hesaplama arac ile a* algoritmasnn rota planlama in analizi. Gen Mhendisler Sempozyumu, Trk Mhendisler Birlii, Mays, Ankara.
  2. Bulut, F. and Amasyali, M. F. Locally adaptive k parameter selection for nearest neighbor classi er. one nearest cluster 20(2), 415-425. Pattern Analysis and Applications.
  3. Changdar, Chiranjit, Pal, R. K., and Mahapatra, G. S. 2017. A genetic ant colony optimization based algorithm for solid multiple travelling salesmen problem in fuzzy rough environment. International Soft Computing 21.16, 4661-4675.
  4. Chen, M. H., Yu, C. W., and Chang, P. C. 2014. Block based imperial competitive algorithm with greedy search for traveling salesman problem. International Scholarly and Scienti c Research Innovation 8, 793-799.
  5. Choong, S. S., Wong, L.-P., and Lim, C. P. 2017. An arti cial bee colony algo- rithm with a modi ed choice function for the traveling salesman problem. In Interna- tional IEEE International Conference on Systems, Man, and Cybernetics (SMC). DOI: 10.1109/SMC.2017.8122629.
  6. Dorigo, Marco, and Gambardella, L. M. 2016. Ant-q: A reinforcement learning approach to the traveling salesman problem. Proceedings of ML-95, Twelfth Intern. Conf. on Machine Learning.
  7. Erol, M. H. and Bulut, F. 2017. Real-time application of travelling salesman problem using google maps api. In Electric Electronics, Computer Science, Biomedical Engineerings' Meeting (EBBT), 1-5. IEEE.
  8. Goerigk, Marc, and Schbel, A. 2016. Algorithm engineering in robust optimization. Springer International Publishing, 245-279.
  9. Hoffman, L., K., Padberg, M., and Rinaldi, G. 2013. Traveling sales-man problem. In International Encyclopedia of operations research and management science. Springer US, 1573-1578.
  10. Kaplan, Haim, and Tarjan, R. E. 1999. New heap data structures. Department of Computer Science, Princeton University. Technical Report TR-597-99.
  11. Kullmann, O. 2017. The science of brute force. Communications of the ACM.
  12. Lancia, Giuseppe, and Serafini, P. 2018. Traveling salesman problems. compact extended linear programming models. Springer, Cham, 155-164.
  13. MUTLU, M. 2010. Kaynak dengeleme problemi iin bir dal ve snr algoritmas (a branch and bound algorithm for resource leveling problem). Doktora Tezi, Orta Dou Teknik niversitesi Fen Bilimleri Enstits, Ankara.
  14. OLAK, S. 2010. Genetik algoritmalar yardm ile gezgin satc probleminin zm zerine bir uygulama. ukurova niversitesi Sosyal Bilimler Enstits Dergisi 19, 3.
  15. Onder, Gozde, Kara, I., and Derya, T. 2017. New integer programming formulation for multiple traveling repairmen problem. Transportation Research Procedia 22, 355-361.
  16. Rao, A. and Hedge, S. K. 2015. Literature survey on travelling salesman problem using genetic algorithms. International Journal of Advanced Research in Education Technology (IJARET) 2, 42-45.
  17. Rao, A. and Hegde, S. K. 2015. Literature survey on travelling salesman problem using genetic algorithms. International Journal of Advanced Research in Education Technology (IJARET) 2.1, 42.
  18. Urrutia, S., Milans, A., and Lkketangen, A. 2015. A dynamic programming based local search approach for the double traveling salesman problem with multiple stacks. Interna- tional Transactions in Operational Research 22, 1, 61-75.
  19. Voudouris, Christos, and Tsang, E. 1999. Guided local search and its application to the traveling salesman problem. European journal of operational research 113.2, 469-499.
  20. Wong, Li-Pei, Low, M. Y. H., and Chong, C. S. 2008. A bee colony optimization algorithm for traveling salesman problem. In International Modeling and Simulation. Second Asia International Conference on. IEEE 2008. AICMS 08.