Solution for the Travelling Salesman Problem with a Microcontroller-based Instantaneous System

Abstract

The travelling salesman problem (TSP) is one of the most frequently researched combinational optimization problems. Despite its trivial definition, the problem is very difficult to solve. Therefore, it is categorized as an NP-hard problem in research literature. It is used for the solution of many real-life problems like route planning, transportation and logistics applications. In this study, a microcontroller-based system was proposed for the solution of the TSP. In the proposed system, location information was imported instantaneously via a GPS module. The Ant Colony Optimization (ACO) algorithm was coded inside the microcontroller for the solution of the TSP. Various tests were performed on two different datasets using different parameter values. Tests showed that the only difference between the results for the microcontroller-based and the computer-based systems were the run-times. Therefore, it was concluded that population-based algorithms like ACO could easily be used in current microcontrollers for various purposes in different areas.

Keywords

• Ant Colony Optimization,GPS Module; Microcontroller; Travelling Salesman Problem

Kaynakça

1. K. Menger, "Das botenproblem", In Ergebnisse eines Mathematischen Kolloquiums 2 (K. Menger, editor), Teubner, Leipzig, 1932.
2. M. R. Garey and D. S. Johnson, “Computers and Intractability: A Guide to the Theory of NP-Completeness”, W. H. Freeman and co., New York, 1979.
3. D. S. Johnson, "Local optimization and the traveling salesman problem." Automata, Languages and Programming, Springer Berlin Heidelberg, pp. 446-461, 1990.
4. M. Held and R. M. Karp, "A dynamic programming approach to sequencing problems," Journal of the Society for Industrial and Applied Mathematics vol. 10, pp. 196-210, 1992.
5. N. Ascheuer, F. Matteo and G. Martin, "Solving the asymmetric travelling salesman problem with time windows by branch-and-cut," Mathematical Programming, vol. 90, pp. 475-506, 2001.
6. T. Volgenant and R. Jonker, “A branch and bound algorithm for the symmetric traveling salesman problem based on the 1-tree relaxation,” European Journal of Operational Research, vol. 9, pp. 83-89, 1982.
7. D. L. Applegate, R. E Bixby, V. Chvata and W. J Cook, “The traveling salesman problem: A computational study,” Princeton University Press, 2011.
8. Z. C. Hlaing and M. A. Khine, "Solving traveling salesman problem by using improved ant colony optimization algorithm," International Journal of Information and Education Technology, vol. 1, pp. 404, 2011.

9. B. Li, W. Lipo and W. Song. "Ant colony optimization for the traveling salesman problem based on ants with memory," Natural Computation, ICNC'08. Fourth International Conference on. vol. 7, 2008.
10. K. H. Hingrajiya, K. G. Ravindra and G. S. Chandel, "An ant colony optimization algorithm for solving travelling salesman problem," International Journal of Scientific and Research Publications, vol. 2, pp. 1-6, 2012.
11. C. A. Silva and A. R. Thomas, "Ant Colony Optimization for dynamic Traveling Salesman Problems," ARCS Workshops. 2004.
12. J. T. Fajardo and M. O. Carlos, "A mobile disaster management system using the android technology," WSEAS Transactions on Communications, vol. 9, pp. 343-353, 2010.
13. A. Aydın and S. Telceken, "Artificial intelligence aided recommendation based mobile trip planner for Eskisehir city," Industrial Electronics and Applications (ICIEA), IEEE 10th Conference on, 2015.
14. İ. İlhan, “Mobile Device Based Test Tool For Optimization Algorithms,” Computer Applications In Engineering Education, DOI: 10.1002/cae.21747, 2016.
15. G. Dantzig, R. Fulkerson and S. Johnson, "Solution of a large-scale traveling-salesman problem," Journal of The Operations Research Society of America, vol. 2, pp. 393-410, 1954.
16. İ. İlhan, “An Application On Mobile Devices With Android And IOS Operating Systems Using Google Maps APIs For The Traveling Salesman Problem,” Ciencia E Tecnica Vitivinicola, vol. 31, pp. 47-67, 2016.
17. G. V. Glen, “Heavenly mathematics: The forgotten art of spherical trigonometry,” Princeton University Press, 2013.
18. M. Dorigo, “Optimization, learning and natural algorithms,” Ph. D. Thesis, Politecnico di Milano, Italy, 1992.
19. www.st.com/resource/en/datasheet/stm32f407vg.pdf (accessed 01.08.2016).
20. www.st.com/resource/en/user_manual/dm00039084.pdf (accessed 01.08.2016).
21. https://www.openimpulse.com/blog/products-page/product-category/gy-neo6mv2-gps-module/ (accessed 01.08.2016).