Generalize A* Algorithms to Solve Travel Salesman Problem

Authors

  • Maha Sabah Saeed Network Department, Computer Science Institute, Sulaimani Polytechnic University, Sulaimani, Iraq
  • Shilan Abdullah Hassan Network Department, Computer Science Institute, Sulaimani Polytechnic University, Sulaimani, Iraq
  • Manal Ali Atiyah

DOI:

https://doi.org/10.25098/8.1.31

Keywords:

A* algorithm, Dijkstra’s algorithm, travelling salesman problem (TSP), heuristic function (HF)

Abstract

Generalize A* is a search algorithm that has widely been used in the pathfinding research group. Its efficiency, simplicity, and modularity are often highlighted as its strengths compared to other algorithms. Dijkstra algorithm is another type of A* but without using of heuristic function. These algorithms were used previously to find the shortest path between two states (start and goal).

Travelling Salesman Problem (TSP) is one of the most common combinatorial optimization problems. It comes in the categorization of NP-Hard problems. The solutions of TSP are not possible using traditional algorithms. It is having many application branches like mathematics, computer science, and engineering. TSP is designed to find the shortest path by visiting all instances of the problem.  This study makes an adaptation to the A* algorithm to work on TSP with the heuristic function that tries to look for a better path which gives priority to nodes that are supposed to be better than others and Dijkstra’s algorithm just explores all possible ways and compare between the two algorithms for the same problem. The study result will help for future studies.

References

A. Rafiq, T. Asmawaty Abdul Kadir, and S. Normaziah Ihsan, "Pathfinding Algorithms in Game Development," IOP Conference Series: Materials Science and Engineering, vol. 769, p. 012021, 2020/02/01 2020.

H. A. Abdulkarim and I. F. Alshammari, "Comparison of algorithms for solving traveling salesman problem," International Journal of Engineering and Advanced Technology, vol. 4, pp. 76-79, 2015.

E. Alkafaween and A.B.A. Hassanat, "Improving TSP Solutions Using GA with a New Hybrid Mutation Based on Knowledge and Randomness," Communications - Scientific letters of the University of Zilina, vol. 22, no. 3, pp. 128-39, 2020.

S. Sharma and V. Jain, "A Novel Approach for Solving TSP Problem Using Genetic Algorithm Problem," in IOP Conference Series: Materials Science and Engineering, 2021, p. 012194.

H. Jiang, "Artificial bee colony algorithm for traveling salesman problem," in 2015 4th International Conference on Mechatronics, Materials, Chemistry and Computer Engineering, 2015, pp. 468-472.

D. Karaboga and B. Gorkemli, "A combinatorial Artificial Bee Colony algorithm for traveling salesman problem," 2011 International Symposium on Innovations in Intelligent Systems and Applications, 2011, pp. 50-53, doi: 10.1109/INISTA.2011.5946125.

B. Gorkemli and D. Karaboga, "Quick combinatorial artificial bee colony-qCABC-optimization algorithm for TSP," in 2nd International Symposium on Computing in Informatics and Mathematics, 2013, pp. 97-101.

J. B. Odili and M. N. Mohmad Kahar, “Solving the Traveling Salesman’s Problem Using the African Buffalo Optimization,” Computational Intelligence and Neuroscience, vol. 2016, pp. 1–12, 2016, doi: 10.1155/2016/1510256.

C. Liu, Q. Mao, X. Chu, and S. Xie, "An Improved A-Star Algorithm Considering Water Current, Traffic Separation and Berthing for Vessel Path Planning," Applied Sciences, vol. 9, p. 1057, 2019.

R. Yang and L. Cheng, "Path Planning of Restaurant Service Robot Based on A-star Algorithms with Updated Weights," 2019 12th International Symposium on Computational Intelligence and Design (ISCID), Hangzhou, China, 2019, pp. 292-295, doi: 10.1109/ISCID.2019.00074.

A. Ghaffari, "An energy efficient routing protocol for wireless sensor networks using A-star algorithm," Journal of applied research and technology, vol. 12, pp. 815-822, 2014.

M. Nosrati, R. Karimi, and H. A. Hasanvand, "Investigation of the*(star) search algorithms: Characteristics, methods and approaches," World Applied Programming, vol. 2, pp. 251-256, 2012.

S. Rabin and N. R. Sturtevant, "Pathfinding architecture optimizations," in Game AI Pro 360, ed: CRC Press, 2019, pp. 1-12.

A. Botea, M. Müller, and J. Schaeffer, "Near optimal hierarchical path-finding," J. Game Dev., vol. 1, pp. 1-30, 2004.

D. Foead, A. Ghifari, M. B. Kusuma, N. Hanafiah, and E. Gunawan, "A systematic literature review of A* pathfinding," Procedia Computer Science, vol. 179, pp. 507-514, 2021.

D. Rachmawati and L. Gustin, "Analysis of Dijkstra’s algorithm and A* algorithm in shortest path problem," in Journal of Physics: Conference Series, 2020, p. 012061.

Published

2024-07-12

How to Cite

Sabah Saeed, M. ., Abdullah Hassan, S. ., & Ali Atiyah, M. . (2024). Generalize A* Algorithms to Solve Travel Salesman Problem. The Scientific Journal of Cihan University– Sulaimaniya, 8(1), 210-218. https://doi.org/10.25098/8.1.31