Travelling Salesmen Problem Solution with Ant-Colony optimization Tabu Search Algorithm

Sikandar Hanif*
School of Information Technology and Engineering, Tianjin University of Technology and Education, Tianjin, China.
Periodicity:October - December'2019
DOI : https://doi.org/10.26634/jse.14.2.17019

Abstract

This paper presents an innovative technique for solving the Traveling Salesman Problem (TSP) using Ant Colony Optimization (ACO) and Tabu Search (TS). This paper focuses on the variation of Euclidean Traveling Salesman Problem (TSP) and Generalized Traveling Salesman Problem (GTSP), extending the Ant Colony Optimization method from TSP to the region. The goal of the algorithm is to find the shortest route from source to destination and the total number of cities is 25. The technique of graphs is used to find the shortest path to the problem in the literature. The main goal is to reduce the travel costs and time. First of all, most researchers try to solve this problem by using different algorithms to get efficient results. Our proposed algorithm has optimized the implementation of our algorithm faster and more efficient to solve the well-known TSP problem. Our algorithm using ASO and TS has made significant improvements in accuracy compared to the sophisticated TS algorithm to solve the same TSP. An efficient MATLAB implementation system prepares our code for deployment in an environment with limitations in memory and speed. The results confirm the efficiency of the proposed algorithm. The performance obtained is better than the genetic algorithm and the Tabu Search algorithm.

Keywords

TSP Problem (TSPP); Ant-Colony Tabu Search Algorithm; Tabu search.

How to Cite this Article?

Hanif, S. (2019). Travelling Salesmen Problem Solution with Ant-Colony optimization Tabu Search Algorithm, i-manager's Journal on Software Engineering, 14(2), 1-9. https://doi.org/10.26634/jse.14.2.17019

References

[1]. Bontoux, B., & Feillet, D. (2008). Ant colony optimization for the traveling purchaser problem. Computers & Operations Research, 35(2), 628-637. https://doi.org/ 10.1016/j.cor.2006.03.023
[2]. Brucal, S. G. E., & Dadios, E. P. (2017, December). Comparative analysis of solving traveling salesman problem using artificial intelligence algorithms. In 2017, IEEE 9th International Conference on Humanoid, Nanotechnology, Information Technology, Communication and Control, Environment and Management (HNICEM) (pp. 1-6). IEEE. https://doi.org/10.1109/HNICEM.2017.82 69423
[3]. Dorigo, M., & Gambardella, L. M. (1997a). Adaptation In Natural And Artificial Systems: An Introductory Analysis With Applications To Biology, Control, And Artificial Intelligence. MIT Press.
[4]. Dorigo, M., & Gambardella, L. M. (1997b). Ant colony system: A cooperative learning approach to the traveling salesman problem. IEEE Transactions on Evolutionary Computation, 1(1), 53-66. https://doi.org/10.1109/ 4235.585892
[5]. Dorigo, M., Caro, G. D., & Gambardella, L. M. (1999). Ant algorithms for discrete optimization. Artificial Life, 5(2), 137-172. https://doi.org/10.1162/106454699568728
[6]. Dorigo, M., Colorni, A., & Maniezzo, V. (1991). Distributed optimization by ant colonies. In Proceedings of the First European Conference on Artificial Life (pp.134–142).
[7]. Dorigo, M., Maniezzo, V., & Colorni, A. (1996). Ant system: Optimization by a colony of cooperating agents. IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics), 26(1), 29-41.
[8]. Ezugwu, A. E. S., Adewumi, A. O., & Frîncu, M. E. (2017). Simulated annealing based symbiotic organisms search optimization algorithm for traveling salesman problem. Expert Systems with Applications, 77, 189-210. https://doi.org/10.1016/j.eswa.2017.01.053
[9]. Gao, M., & Tian, J. (2007, August). Path planning for mobile robot based on improved simulated annealing artificial neural network. In Third International Conference on Natural Computation (ICNC 2007) (Vol. 3, pp. 8-12). IEEE. https://doi.org/10.1109/ICNC.2007.547
[10]. Halim, A. H., & Ismail, I. (2019). Combinatorial optimization: comparison of heuristic algorithms in travelling salesman problem. Archives of Computational Methods in Engineering, 26(2), 367-380. https://doi.org/ 10.1007/s11831-017-9247-y
[11]. Junqiang, W., & Aijia, O. (2012, August). A hybrid algorithm of ACO and delete-cross method for TSP. In 2012 International Conference on Industrial Control and Electronics Engineering (pp. 1694-1696). IEEE. https://doi.org/10.1109/ICICEE.2012.448
[12]. Kaabi, J., & Harrath, Y. (2019). Permutation rules and genetic algorithm to solve the traveling salesman problem. Arab Journal of Basic and Applied Sciences, 26(1), 283- 291. https://doi.org/10.1080/25765299.2019.1615172
[13]. Karamcheti, V., & Malek, M. (1991, September). A TSP engine for performing tabu search. In Proceedings of the International Conference on Application Specific Array Processors (pp. 309-321). IEEE. https://doi.org/10.1 109/ASAP.1991.238912
[14]. Laporte, G. (1992). The traveling salesman problem: An overview of exact and approximate algorithms. European Journal of Operational Research, 59(2), 231- 247.
[15]. Lim, Y. F., Hong, P. Y., Ramli, R., & Khalid, R. (2011, December). An improved tabu search for solving symmetric traveling salesman problems. In 2011, IEEE Colloquium on Humanities, Science and Engineering (pp. 851-854). IEEE. https://doi.org/10.1109/CHUSER.2011.616 3857
[16]. Luo, W., Lin, D., & Feng, X. (2016, December). An improved ant colony optimization and its application on TSP problem. In 2016, IEEE International Conference on Internet of Things (iThings) and IEEE Green Computing and Communications (GreenCom) and IEEE Cyber, Physical and Social Computing (CPSCom) and IEEE Smart Data (SmartData) (pp. 136-141). IEEE. https://doi.org/10.1109/ iThings-GreenCom-CPSCom-SmartData.2016.48
[17]. McKendall Jr, A. R., & Shang, J. (2006). Hybrid ant systems for the dynamic facility layout problem. Computers & Operations Research, 33(3), 790-803. https://doi.org/10.1016/j.cor.2004.08.008
[18]. Mohammed, M. A., Ahmad, M. S., & Mostafa, S. A. (2012, June). Using genetic algorithm in implementing capacitated vehicle routing problem. In 2012, Conference on Computer & Information Science (ICCIS) (Vol. 1, pp. 257- 262). IEEE. https://doi.org/10.1109/ICCISci. 2012.6297250
[19]. Mohsen, A. M. (2016). Annealing ant colony optimization with mutation operator for solving TSP. Computational Intelligence and Neuroscience, 1-13. https://doi.org/10.1155/2016/8932896
[20]. Nazif, H., & Lee, L. S. (2010). Optimized crossover genetic algorithm for vehicle routing problem with time windows. American Journal of Applied Sciences, 7(1), 95.
[21]. Osaba, E., & Díaz, F. (2012, September). Comparison of a memetic algorithm and a tabu search algorithm for the traveling salesman problem. In 2012, Federated Conference on Computer Science and Information Systems (FedCSIS) (pp. 131-136). IEEE.
[22]. Raff, S. (1983). Routing and scheduling of vehicles and crews: The state of the art. Computers & Operations Research, 10(2), 63-211. https://doi.org/10.1016/0305- 0548(83)90030-8
[23]. Ratanavilisagul, C. (2017, June). Modified ant colony optimization with pheromone mutation for travelling salesman problem. In 2017, 14th International Conference on Electrical Engineering/Electronics, Computer, Telecommunications and Information Technology (ECTICON) (pp. 411-414). IEEE. https://doi.org/10.1109/ ECTICon.2017.8096261
[24]. Reinelt, G. (1994). The Traveling Salesman: Computational Solutions For TSP Applications. Springer- Verlag.
[25]. Yu, S., Ding, C., & Zhu, K. (2011). A hybrid GA–TS algorithm for open vehicle routing optimization of coal mines material. Expert Systems with Applications, 38(8), 10568- 10573. https://doi.org/10.1016/j.ins.2003.11.008
[26]. Wang, J., Ersoy, O. K., He, M., & Wang, F. (2016). Multioffspring genetic algorithm and its application to the traveling salesman problem. Applied Soft Computing, 43, 415-423. https://doi.org/10.1016/j.asoc.2016.02.021
[27]. Yoshikawa, M., & Terai, H. (2009, March). Car navigation system based on hybrid genetic algorithm. In 2009, WRI World Congress on Computer Science and Information Engineering (Vol. 5, pp. 62-65). IEEE. https://doi.org/10.1109/CSIE.2009.558
[28]. Yousefikhoshbakht, M., Malekzadeh, N., & Sedighpour, M. (2016). Solving the traveling salesman problem based on the genetic reactive bone route algorithm whit ant colony system. International Journal of Production Management and Engineering, 4(2), 65-73. https://doi.org/10.4995/ijpme.2016.4618
[29]. Zhang, Z., & Feng, Z. (2009, November). A novel maxmin ant system algorithm for traveling salesman problem. In 2009, IEEE International Conference on Intelligent Computing and Intelligent Systems (Vol. 1, pp. 508-511). IEEE. https://doi.org/10.1109/ICICISYS.2009.5357792
[30]. Zhong, Y., Wu, C., Li, L., & Ning, Z. (2008, October). The study of neighborhood structure of tabu search algorithm for traveling salesman problem. In 2008, Fourth International Conference on Natural Computation (Vol. 1, pp. 491-495). IEEE. https://doi.org/10.1109/ICNC.2008.749
[31]. Zhou, A. H., Zhu, L. P., Hu, B., Deng, S., Song, Y., Qiu, H., & Pan, S. (2019). Traveling-salesman-problem algorithm based on simulated annealing and gene-expression programming. Information, 10(1), 7. l https://doi.org/ 10.3390/info10010007
If you have access to this article please login to view the article or kindly login to purchase the article

Purchase Instant Access

Single Article

North Americas,UK,
Middle East,Europe
India Rest of world
USD EUR INR USD-ROW
Online 15 15

Options for accessing this content:
  • If you would like institutional access to this content, please recommend the title to your librarian.
    Library Recommendation Form
  • If you already have i-manager's user account: Login above and proceed to purchase the article.
  • New Users: Please register, then proceed to purchase the article.