Single Valued Trapezoidal Neutrosophic Travelling Salesman Problem with Novel Greedy Method: The Dhouib-Matrix-TSP1 (DM-TSP1)
1 Laboratory OLID, Higher Institute of Industrial Management, University of Sfax, Tunisia; souhail.dhouib@gmail.com
2Regional Center for the Professions of Education and Training,Casablanca-Settat, Morocco
3Laboratory of Information Processing, Faculty of Science Ben M’Sik, University Hassan II, Casablanca, Morocco
4Department of Mathematics, Hindustan Institute of Technology & Science, Chennai-603 103, India; lathamax@gmail.com
* Correspondence: dhouib.matrix@gmail.com
Abstract
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.
Keywords: Neutrosophic Optimization, Neutrosophic graphs, Travelling Salesman Problem, Operational Research, Combinatorial Problems, Heuristic, Dhouib-Matrix, Dhouib-Matrix-TSP1.
1.Introduction
The Travelling Salesman Problem (TSP) portrays the salesman who is travelling between n cities where the salesman knows the transmits and cost of the cities. This helps the salesman to identify the possible shortest route that visits each city exactly once and returns to the starting city. TSP is an NP-hard problem and the aim of this problem is to calculate a shortest possible tour that visits every city exactly once. TSP is related with daily activities in uncertain and indeterminate parameters namely distance, cost and time. These parameters are unstable and not exactly known and hence, neutrosophic concept has been widely used in TSP.
Fuzzy set deals with only membership function and intuitionistic fuzzy set handles both membership and non-membership function. But real-world problems have indeterminacy too in nature and hence Smrandache introduced the neutrosophic concept in 1995 concerning the chance of reflecting the human thinking using the three membership functions namely Truth (T), Indeterminacy (I) and Falsity (F) which belongs to neutrosophic set. These three components are independent and hence neutrosophic set plays a vital role and has been a major focus of the research field. This field a new branch of philosophy called Neutrosophy as a generalization of intuitionistic, inconsistent, and fuzzy logic. It deals with not only ambiguity; also analyze the relation and absolute truth [1].
Shortest path problems have been studied and made an overview by the researchers under single valued and trapezoidal neutrosophic information [6-7, 13, 23]. TSP has been solved using various methods under different set environments as follows. TSP is solved using combinational Evolutionary Algorithm [2], a study was carried out on TSP using fuzzy self-organizing map [3], two methods have been proposed to solve TSP namely Ant Colony Systems to understand the operations and applied Hopfield Neural Network to TSP as it has fully connected neurons generally used in optimization tasks [4], intuitionistic fuzzy modeling [5], metaheuristic algorithm [8]. Also, shortest path problem is solved under triangular fuzzy neutrosophic environment by considering the edge weight as the triangular fuzzy neutrosophic numbers. Here, the length of the shortest path has been calculated using ranking function [9], using the first iteration of modified Vogel method to calculate the best starting city for the nearest neighbor algorithm [10].
Also, TSP is examined using Genetic Algorithm which supports the growth of life [11], using Heart Algorithm which handles the action of the heart and circulatory setup in human beings [12], improved Genetic Algorithm [14], Multi-element Genetic Algorithm [15], E-commerce website evaluation is done under single valued neutrosophic environment using a novel integrated decision system which contain three modules namely, information acquisition, SVTN-DEMATEL module and the integration module [16], operations on single valued trapezoidal neutrosophic numbers have been proposed and applied in a group decision making problem [17], using Hungarian method under intuitionistic fuzzy environment [18].
In [19], metaheuristic method is used to solve TSP by finding the near optimal solution, implemented fuzzy intuitionistic algorithm is used to solve TSP [20], Kidney inspired algorithm in which the Kidney process in the human body is used [21], the method of Graphical Processing Units is applied [22], using Genetic Algorithm under intuitionistic fuzzy environment [24]. Moreover, EMF-CE algorithm which uses a negative exponent function to achieve critical value as the feedback regulation of the implementation of algorithm [25], using Branch and Bound method [26], Quasi optimization with time dependent [27], fuzzy environment [28], using intuitionistic fuzzy approach [29], time dependent TSP where edge costs depend on their position in the tour is solve under interval valued intuitionistic fuzzy environment [30].
TSP has been solved using Ising model where the data given by ISING solver as text in matrix market format with simulated bifurcation where the nearly optimal solution can be obtain quickly [31], solved transportation problem using ECCT and standard deviation under fuzzy environment [40], modified grey wolf optimizer [42], using modified Grey Wolf optimizer where the leadership ranking and hunting mechanism of grey wolves in nature is simulated [43], and review has been done with TSP using GA-ACO hybrid approach.
Though, there are various types of neutrosophic numbers, we used trapezoidal neutrosophic numbers as it is the combination of trapezoidal fuzzy numbers and neutrosophic set. According to the literature survey, so far, TSP is not yet been studied under single valued trapezoidal neutrosophic numbers. Hence the motivation of this present work is to enhance the novel greedy method called Dhouib-Matrix-TSP1 (DM-TSP1) to solve this kind of indeterminant TSP.
The rest of the paper is presented as follows. In section 2, basic concepts are described related to the present work. In section 3, the novel greedy method entitled DM-TSP1 is proposed under trapezoidal neutrosophic environment. In section 4, the first resolution of the TSP are carried out with step-wise application to test the validity. Also, graphical representation is given. In section 5, conclusion and future direction of the present work are given.
2. Mathematical definition for trapezoidal and neutrosophic numbers
Definition 1[23]. Let us consider a space X composed of universal elements denoted by x. The neutrosophic set A is a phenomenon having the following construction where the three grades of memberships are from X to ]−0,1+[ of the element x X to the set N, with the criterion:
. The functions and are the truth, indeterminate and falsity grades lies in ] −0, 1+ [.
Definition 2 [6]. For the space X of objects contains a global elements x. A single valued neutrosophic number represented by three degrees of membership grades , [0, 1]. A single valued neutrosophic set is defined by
Definition 3[41].The three independent membership functions Truth (T), Indeterminacy (I), Falsity (F) for the single valued trapezoidal neutrosophic number (SVTpNN) are defined by:
Definition 4 [30].Let and be two SVTpNNs and be any real number. Then
3. Novel greedy method: The Dhouib-Matrix-TSP1 (DM-TSP1)
The Travelling Salesman Problem (TSP) is one of the most important combinatorial problems. It deals with generating a minimal cycle between all cities (see Equation 1) where dij represents the distance between city i and city j and xij denotes a binary decision variable (xij= 1 if city i is related to city j otherwise xij = 0).
Minimize:
(1)
Subject to:
(2)
In order to obtain an initial basic feasible solution for the TSP, [32] designed a novel greedy method named Dhouib-Matrix-TSP1 (DM-TSP1). Then, this method is enhanced to be a stochastic technique entitled Dhouib-Matrix-TSP2 (DM-TSP2) in [33]. Hence, DM-TSP1 and DM-TSP2 are applied on several instances in [34]. Then, an application of DM-TSP1 on TSP under fuzzy environment is depicted in [35, 36, 37] and its application on neutrosophic domain is illustrated in [38,39]. Two new metaheuristics are recently developed and inspired from DM-TSP1 and DM-TSP2: the iterated DM3 in [45] and the multi-start DM4 in [46].
The greedy heuristic DM-TSP1 is subdivized into four steps (see Figure 1). DM-TSP1 is independent to the statistical metrics (Min, Max, Average, … etc.). In this paper, we will use the range function.
Figure 1 Flow chart of the proposed new heuristic DM-TSP1
The score function developed in [11] is applied to transform the single value trapezoidal neutrosophic number to crisp number (see Equation 1). Let be a neutrosophic number so its score function will be calculated as:
(1)
4. Application of DM-TSP1 on the neutrosophic Travelling Salesman Problem
This section aims to carry out the first optimization of the TSP under single valued trapezoidal neutrosophic domain. The greedy method DM-TSP1 is proposed to generate the initial basic feasible solution. Moreover, a step-wise application was conducted to test its validity. However, there are no instances for this variant of TSP, so we create three numerical examples (presented in the next subsection).
4.1. Example 1
Let us consider an example of 5 cities where the distances are denoted by single valued trapezoidal neutrosophic numbers (see Figure 2).
Figure 2 Neutrosophic matrix
By applying the score function described by Equation 1, the crisp matrix is presented as follows (see Figure 3).
Figure 3 Crisp matrix
Now, compute the sum of each row and find the smallest which is equal to 25.34 at row 3 (see Figure 4).
Figure 4 Select the smallest element in row 3
Then, select the smallest value in row 3 which is equal to 4.60 at position d32, insert the corresponding city 3 and city 2 into List-cities {3-2} and remove their corresponding columns (see Figure 5).
Figure 5 Discard columns 3 and 2
Hence, choose the smallest element between row 2 and row 3 (equal to 5.60) at position d34.Then, add city 4 to List-cities {4-3-2} just before city 3 and discard its column (see Figure 6).
Figure 6 Discard column 4
Similarly, find the smallest element between rows 2 and 4 that is equal to 6.50 is at position d21. Thus, add city 1 to the List-cities {4-3-2-1} just after city 2 and discard its column (see Figure 7).
Figure 7 Discard column 1
Next select the smallest element between row 1 and row 4 that is equal to 7.23 at position d15. So, add city 5 to List-cities {4-3-2-1-5} and remove its coresponding column (see Figure 8).
Figure 8 Discard column 5
To finish, generate a cycle from List-cities {4-3-2-1-5} by translating all cities before city 1 to the last position and adding city 1 at the end {1-5-4-3-2-1}.
The crisp optimal solution for this problem is equal to 31.53 in which the neutrosophic optimal solution is equal to (see Figure 9).
Figure 9 Graphical representation of the single valued trapezoidal neutrosophic optimal solution
4.2. Example 2
The second example deals with 5x5 TSP matrix with single valued trapezoidal neutrosophic TSP (see Figure 10).
Figure 10 Neutrosophic matrix
By applying the score function described by Equation 1, the crisp matrix is presented as follows (see Figure 11).
Figure 11 Crisp matrix
Figure 12, depicts the stepwise application of DM-TSP1 on 5x5 distance matrix. DM-TSP1 needs only n (n=5) iterations to solve this problem.
Figure 12 Step by step application of the heuristic DM-TSP1 on 5x5 matrix
The crisp optimal solution for this problem is equal to 26.50 in which the neutrosophic optimal solution is equal to (See Figure 13).
Figure 13 Graphical representation of the single valued trapezoidal neutrosophic optimal solution
4.3. Example 3
The third example presents a 6*6 TSP matrix with single valued trapezoidal neutrosophic numbers (see Figure 14).
Figure 14 Neutrosophic matrix
By applying the score function described by Equation 1, the crisp matrix is presented as follows (see Figure 15).
Figure 15 Crisp matrix
Figure 16, depicts the stepwise application of DM-TSP1 on 6x6 distance matrix. DM-TSP1 needs only n (n=6) iterations to solve this problem.
Figure 16 Step by step application of the heuristic DM-TSP1 on 6x6 matrix
The crisp optimal solution for this problem is equal to 41.02 in which the neutrosophic optimal solution is equal to (See Figure 17).
Figure 17 Graphical representation of the single valued trapezoidal neutrosophic optimal solution
5. Conclusions
This article presents the first optimization of the Travelling Salesman Problem (TSP) under single valued trapezoidal neutrosophic number. Several numerical examples are generated and the novel greedy method Dhouib-Matrix-TSP1 (DM-TSP1) is applied in order to find an initial basic feasible solution after only n iterations (n is the number of nodes). Acquired results are analyzed and graphical solutions are presented. As an extension of this research work, we look to solve other combinatorial problems under neutrosophic domain.
Funding: “This research received no external funding”
Conflicts of Interest: “The authors declare no conflict of interest.”
References
[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.