Volume 17 , Issue 2 , PP: 144 - 157, 2021 | Cite this article as | XML | Html | PDF | Full Length Article
Souhail Dhouib 1 * , Said Broumi 2 , M. Lathamaheswari 3
Doi: https://doi.org/10.54216/IJNS.170205
Travelling salesman problem (TSP) is a prominent computational problem where trail technique is used to calculate all the possible travel and choose the best one. Since there is no branching or back tracking in greedy algorithms, determining the run time is much easier than the existing methods and hence, in this paper, a novel greedy method called Dhouib-Matrix-TSP1 is proposed as the first resolution of TSP to get the optimal solution using single valued trapezoidal neutrosophic numbers with several numerical examples. Also, results have been analyzed with graphical solutions.
Neutrosophic Optimization, Neutrosophic graphs, Travelling Salesman Problem, Operational Research, Combinatorial Problems, Heuristic, Dhouib-Matrix, Dhouib-Matrix-TSP1
[1] F. Smarandache, A Unifying Field in Logics: Neutrosophic Logic. Neutrosophy, Neutrosophic Set, Neutrosophic Probability and Statistics, InfoLearnQuest, Philadelphia, PA, USA, 6th edition, 2007.
[2] M.R. Bonyadi, M.R. Azghadi, H.S. Hosseini, Solving Travelling Salesman Problem Using Combinational Evolutionary Algorithm. In: Conference-Artificial Intelligence and Innovations 2007: from theory to Applications, Proceedings of the 4th IFIP International Conference on Artificial Applications and Innovations (AIAI 2007),19-21 September, Peania, Athens, Greece. 2007, doi: 10.1007/978-0-387-74161-1_5
[3] Arindam Chaudhuri, Kajal De, A Study of the Traveling Salesman Problem Using Fuzzy Self Organizing Map. In: The third international conference on Industrial and Information Systems, 2008, ICIIS 2008, doi:10.1109/ICIINFS.2008.4798469
[4] S. M. Abdel-Moetty, Traveling salesman problem using neural network techniques, In: 2010 the 7 th International Conference on Informatics and Systems, 2010, pp. 1-6.
[5] A. Garai, T.K. Roy, Intuitionistic Fuzzy Modeling to Travelling Salesman Problem. Internatonal Journal of Computers & Technology, 2012, 11(9), 3015-3024.
[6] H. Wang, F. Smarandache, Y. Q. Zhang, and R. Sunderraman, Single valued neutrosophic sets, Multispace and Multistructure, vol. 4, pp. 410–413, 2010.
[7] Broumi, A. Bakali, M. Talea and F. Samarandache and L. Vladareanu, Computation of Shortest Path Problem in a Network, with SV-Trapezoidal Neutrosophic Numbers, Proceedings of the 2016 International Conference on Advanced Mechatronic Systems, Melbourne, Australia, 2016, pp. 417-422.
[8] A. Agarwal, Rajendra Singh, Comparative analysis of travelling salesman problem using metaheuristic algorithms. In: The International Conference on Communication and Computing Systems (ICCCS-2016)doi: 10.1201/9781315364094-153 .
[9] S. Broumi, A. Bakali, M. Talea, F. Smarandache, and L. Vladareanu, “Shortest path problem under triangular fuzzy neutrosophic information,” in Proceedings of the 2016 10th International Conference on Software, Knowledge, Information Management & Applications (SKIMA), Chengdu, China, December 2016.
[10] A. Dalia, B. Hafida, Y. Gningue, P. M. L. Takouda, H. Zhu, Improving The Nna For The Travelling Salesman Problem Using The Mvm, International Journal of Latest Research in Science and Technology, 2016, 5(2):106-109.
[11] Z. Zhao, Y. Chen, A Study on the Traveling Salesman Problem Using Genetic Algorithms. International Journal of Simulation: Systems, Science & Technology, 2016, 17(36):40.1-40.
[12] A. Hatamlou, Solving Travelling Salesman Problem Using Heart Algorithm. International Journal of Applied Evolutionary Computation, vol.8, no.4 2017: pp.32-42. http://doi.org/10.4018/IJAEC.2017100103
[13] S. Broumi, A. Bakali, M. Talea and F. Samarandache, Shortest Path problem under Trapezoidal Neutrosophic Information, Computing Conference, 2017, pp.142-148.
[14] S. Rana, S.R. Srivastava, Solving Travelling Salesman Problem Using Improved Genetic Algorithm. Indian Journal of Science and Technology, 2017, 10(30), 1-6.
[15] I.B.K. Widiartha, S.E. Anjarwani, F. Bimantoro, Traveling salesman problem using multi-element genetic algorithm. In: 11 th International Conference on Telecommunication Systems Services and Applications (TSSA), doi: 10.1109/TSSA.2017.8272917
[16] L. Ruxia, W. Jianqiang and Z. Hongyu, Evaluation of e-commerce websites: An integrated approach under a single-valued trapezoidal neutrosophic environment. Knowledge-Based Systems, 2017, v. 135, no. 1, 44-59.
[17] I. Deli, Operations on Single Valued Trapezoidal Neutrosophic Numbers and SVTN-Group Decision Making. Neutrosophic Sets and Systems, 2018, vol. 22, 131-150.
[18] K. Prabakaran, K. Ganesan, Fuzzy Hungarian Method for Solving Intuitionistic Fuzzy Travelling Salesman Problem, Journal of Physics Conference Series, 2018, 1000(1):012008.
[19] A. Yadav, D. Garg, K. Singh, Kamleshwar, M.F. Alam, Traveling Salesman Problem Using Metaheuristic. International Journal for Research in Applied Science & Engineering Technology (IJRASET), 2018, 6(IV), 1135-1138.
[20] N. Anitha, C. Vijayalakshmi, Implementation of Fuzzy Intuitionistic Algorithm for Traveling Salesman Problem, EAI Endorsed Transactions on Energy Web, 2018, 5(18):154817.
[21] W. Fawaz, Solving traveling salesman problem using Kidney-Inspired algorithm. In Conference: Conference: 2nd International Conference on Mathematics, Statistics & Information Technology (2nd ICMSIT 2018), At: Tanta, Egypt, doi: 10.5281/zenodo.4587898.
[22] P. H. Yelmewad, B. Talawar, Near Optimal Solution for Traveling Salesman Problem using GPU. In: Conference: 2018 IEEE International Conference on Electronics, Computing and Communication Technologies (CONECCT), 2018, doi: 10.1109/CONECCT.2018.8482363.
[23] Broumi, S., Talea, M., Bakali, A., Smarandache, F., Lathamaheswari, M. and Nagarajan, D. (2019). Shortest Path Problem in Fuzzy, Intuitionistic Fuzzy and Neutrosophic Environment: An Overview. Complex and Intelligent Systems., Springer, https://doi.org/10.1007/s40747-019-0098-z
[24] A. Si, S. Das, Solving Travelling Salesman Problem Using Intuitionistic Fuzzy Set Based Genetic Algorithm, In: Conference proceedings of National Conference on Device Modeling and Soft Computing for real time applications (DMSC-2019), 20-26.
[25] M. Luo, S. Gu, Solve traveling salesman problem using EMF-CE algorithm, doi: 10.36227/techrxiv.13139042.v2, 2020.
[26] P. Rajeswari P, D. Maheswari, Travelling Salesman Problem Using Branch And Bound Technique. International Journal of Mathematics Trends and Technology, 2020, 66(5), 202-206.
[27] R. Almahasne, B.T. Szabo, Quasi-Optimization of the Time Dependent Traveling Salesman Problem by Intuitionistic Fuzzy Model and Memetic Algorithm. In Book: Computational Intelligence in Emerging Technologies for Engineering Applications, 2020, doi:10.1007/978-3-030-34409-2_14.
[28] K. Murugesan, S. Dhanasekar, N. Mohana, Solving Fuzzy Assignment and Fuzzy Travelling Salesman Problems Using R Software, 2020, doi: 10.37418/amsj.9.11.101
[29] V. Traneva, S. Tranev, An Intuitionistic Fuzzy Approach to the Travelling Salesman Problem, In book: Large-Scale Scientific Computing, doi: 10.1007/978-3-030-41032-2_61, 2020
[30] A. Ruba, B. Szabo, L.T. Koczy, P. Foldesi, Optimization of the Time-Dependent Traveling Salesman Problem Using Interval-Valued Intuitionistic Fuzzy Sets, 2020, doi: 10.3390/axioms9020053.
[31] T. Zhang, Q. Tao, J. Han, Solving Traveling Salesman Problems Using Ising Models with Simulated Bifurcation. In: Conference: 2021 18th International SoC Design Conference (ISOCC), doi: 10.1109/ISOCC53507.2021.9613918.
[32] S. Dhouib, A New Column-Row Method for Traveling Salesman Problem: The Dhouib-Matrix-TSP1. International Journal of Recent Engineering Science, 2021, v. 8, no. 1, 6-10, 10.14445/23497157/IJRES-V8I1P102.
[33] S. Dhouib, Stochastic Column-Row Method for Travelling Salesman Problem: the Dhouib-Matrix-TSP2. International Journal of Engineering Research & Technology, 2021,v. 10, no. 3, 524-527.
[34] Dhouib S. Minimizing the Total Distance for the Supply Chain Problem Using Dhouib-Matrix-TSP2 Method. International Journal of Advanced Research in Engineering and Technology, 2021, v. 12, no. 5, 1-12, DOI: 10.34218/IJARET.12.5.2021.001.
[35] S. Dhouib, Haar Dhouib-Matrix-TSP1 Method to Solve Triangular Fuzzy Travelling Salesman Problem. Research Journal of Recent Sciences, 2021, v. 10,no, 3, 18-20.
[36] M. Miledi, S. Dhouib and T. Loukil, Dhouib-Matrix-TSP1 Method to Optimize Octagonal Fuzzy Travelling Salesman Problem Using α-Cut Technique, International Journal of Computer and Information Technology, 2021, v. 10, no. 3, 130-133, DOI: 10.24203/ijcit.v10i3.105.
[37] Sa. Dhouib and S. Dhouib, Optimizing the Trapezoidal Fuzzy Travelling Salesman Problem Through Dhouib-Matrix-TSP1 Method Based on Magnitude Technique. International Journal of Scientific Research in Mathematical and Statistical Sciences, 2021, v. 8, no. 2, 1-4, DOI: 10.26438/ijsrmss/v8i2.14.
[38] S. Dhouib, Neutrosophic Triangular Fuzzy Travelling Salesman Problem Based on Dhouib-Matrix-TSP1 Heuristic. International Journal of Computer and Information Technology, 2021, v. 10, no. 5, 180-183, DOI: 10.24203/ijcit.v10i5.154.
[39] S. Dhouib, Optimization of Travelling Salesman Problem on Single Valued Triangular Neutrosophic Number using Dhouib-Matrix-TSP1 Heuristic. International Journal of Engineering, 2021, v. 34, no. 12, 2642-2647, DOI: 10.5829/IJE.2021.34.12C.09.
[40] K. P. Sikkannan and V. Shanmugavel, Sorting out fuzzy transportation problems via ECCT and standard deviation, 10 Mathematical Problems in Engineering International Journal of Operations Research and Information Systems, vol. 12, no. 2, 2021.
[41] S. Dhouib, Solving the Single-valued Trapezoidal Neutrosophic Transportation Problmes through the Novel Dhouib-Matrix-TP1-Heuristic. Mathematical Problems in Engineering, 2021, 1-11.
[42] Boualem S.M, BoudjelalMeftah, Debbat F, Solving Travelling Salesman Problem Using a Modified Grey Wolf Optimizer. In Book: Artificial Intelligence and Heuristic for Smart Efficiency in Smart Cities, 2022, doi: 10.1007/978-3-030-92038-8_71
[43] S. A. M. Boualem, B. Meftah, D. Fatima, Solving Travelling Salesman Problem Using a Modified Grey Wolf Optimizer. In Book: Artificial Intelligence and Heuristics for Smart Energy Efficiency in Smart Cities, doi: 10.1007/978-3-030-92038-8_71, 2022.
[44] Ankita, Travelling Salesman Problem Using GA-ACO Hybrid Approach: A Review. In: Kumar A., Senatore S., Gunjan V.K. (eds) ICDSMLA 2020. Lecture Notes in Electrical Engineering, 2022, vol 783. Springer, Singapore. https://doi.org/10.1007/978-981-16-3690-5_11.
[45] S. Dhouib, Novel Metaheuristic based on Iterated Constructive Stochastic Heuristic: Dhouib-Matrix-3 (DM3). Applied Computational Intelligence and Soft Computing, In Press.
[46] S. Dhouib, Multi-Start Constructive Method Through Descriptive Statistics Metrics to Solve Travelling Salesman Problem: The Dhouib-Matrix-TSP4 Metaheuristic.International Journal of Operational Research, In Press.
