A Decision-Making Model for the Travelling Salesman Problem Based on Neutrosophic Edge Connectivity

Neutrosophic Sets and Systems, Vol. 93, 2025 University of New Mexico Aparna Tripathy, Amaresh Chandra Panda, Siva Prasad Behera, Prasanta Kumar Raut, A Decision -Making Model for the Travelling Salesman Problem Based on Neutrosophic Edge Connectivity A Decision-Making Model for the Travelling Salesman Problem Based on Neutrosophic Edge Connectivity Aparna Tripathy1, Amaresh Chandra Panda1*, Siva Prasad Behera1, Prasanta Kumar Raut2 1Department of Mathematics, C.V. Raman Global University, Bhubaneswar, Odisha, India. 1Email: [email protected], [email protected], [email protected] 2Department of Mathematics, Trident Academy of Technology, Bhubaneswar, Odisha, India 2Email: [email protected] Correspondence: [email protected] Abstract Neutrosophic edge connectivity is a new idea in graph theory that adds indeterminacy and uncertainty to traditional edge connectivity. It is especially useful for challenging optimization problems that happen in the real world. The use of neutrosophic edge connectivity in solving the well-known NP-hard issue in combinatorial optimization, the Travelling Salesman issue (TSP), is examined in this work. We make a new framework by combining neutrosophic logic, which makes TSP solutions more flexible and realistic, especially in environments that are uncertain and changing quickly, where traditional deterministic models don't work. By taking into account the levels of truth, indeterminacy, and falsity in edge connectivity, the suggested method helps people make better route Neutrosophic Sets and Systems, Vol. 93, 2025 427 Aparna Tripathy, Amaresh Chandra Panda, Siva Prasad Behera, Prasanta Kumar Raut, A Decision -Making Model for the Travelling Salesman Problem Based on Neutrosophic Edge Connectivity optimization decisions. Here in this research paper, we provide a thorough theoretical study along with mathematical examples of TSP (Traveling Salesman Problem) situations to verify the method's efficiency. Furthermore, we proposed a problem statement. A logistics business must choose the best delivery path among different cities. It turns out that our neutrosophicbased approach makes solutions more stable and opens up a beneficial path for more research in real-world logistics and uncertainty-based optimization. Keywords: Edge Connectivity; Neutrosophic Graph Theory; Optimization, Indeterminacy; Travelling Salesman Problem. 1. Introduction Graph theory has great use in many fields, including system analysis, computer science, networking, and transportation systems. Acting as a basic relational model, it shows links among actual objects. In a graph, vertices represent entities, and edges show their relationships. However, challenges such as missing data, lack of supporting evidence, and insufficient knowledge often plague real-world optimization issues, leading to errors in decision-making. Zadeh [1] developed the idea of fuzzy sets, where every element has a membership degree between 0 and 1 and it also to help mathematical modeling overcome ambiguity. Examining fuzzy graphs in excellent detail, Sitara [2] highlighted their main features and their capacity to more successfully control ambiguity in complicated networks. Although fuzzy sets help to handle imprecision, Atanassov [3] noted a drawback in their method as they only control uncertainty in one direction, therefore neglecting the whole complexity of human thinking. Atanassov developed intuitionistic fuzzy sets, an extension of fuzzy sets including both membership and non-membership functions, to get over this disadvantage. Later, Smarandache [4] developed this idea by suggesting neutrosophic sets, a more generic framework able to manage inconsistent and uncertain information, which is usually found in practical situations. Wang [5] improved this idea even further by adding single-valued neutrosophic sets (S-VNS) to increase its useful relevance. Broumi [6] and associates then expanded on this concept, assisting in the development of single-valued neutrosophic graphs for use in decision-making and optimization. More recently, Raut, P. K., investigated the use of neutrosophic sets in many applications, including shortest-path problems [8–17]. Understanding the dependability and resilience of networks depends in large part on edge connections. Edge connectivity in classical graph theory is the least number of edges required to disconnect a graph. In real-world applications, however, networks often consist of ambiguous and unclear characteristics that make conventional models insufficient to correctly Neutrosophic Sets and Systems, Vol. 93, 2025 428 depict system behaviour. Introduced by Smarandache, neutrosophic logic stretches classical and fuzzy logic by adding three basic components: truth, falsehood, and indeterminacy, thereby addressing this restriction. Including neutrosophic logic in edge connectivity analysis helps provide a more flexible and realistic framework to handle actual uncertainty Among such useful applications is the well-known combinatorial optimization problem in computer science and mathematics, the Travelling Salesman Problem (TSP). Originally brought up in the 1930s, the issue became well-known during the 1950s [18–20]. The TSP calls for a salesperson to visit a series of cities and return to the beginning point, therefore optimizing the overall distance travelled. With its NP-hard character [21, 22], the TSP remains a benchmark issue for assessing methods of optimization. Real-world circumstances alter route traversal by dynamic elements like traffic congestion, road conditions, transportation prices, and weather variations, thereby making it challenging to estimate precise trip expenditures and time durations. Decision-makers have to consider these uncertainties if they are to create sensible routing plans. The computational complexity increases exponentially as the number of cities in a TSP instance rises; hence, accurate solutions are useless for large-scale issues. Over the years, many heuristic and metaheuristic approaches have developed to solve the TSP [23–29]. Because precise algorithms must evaluate all potential combinations, their efficiency declines for big networks even as they can rapidly identify effective solutions for small examples. Within an acceptable computing period, heuristic and metaheuristic algorithms, such as harmony search, artificial bee colony algorithms, and genetic algorithms, provide nearly ideal answers. For example, genetic algorithms use selection, mutation, and crossover processes to create better answers while chromosomes reflect possible solutions. This work aims to enhance TSP optimization through the use of neutrosophic edge connectivity, which expresses arc lengths as neutrosophic numbers to account for uncertainty. We use neutrosophic reasoning in the optimization process since conventional evolutionary approaches are not sufficient for unknown surroundings. Our suggested structure allows more flexible and reasonable decision-making by representing arc lengths in the TSP using neutrosophic integers. A mathematical model that was made for the TSP with neutrosophic number arc lengths shows how useful neutrosophic sets can be in uncertain situations. We also show the success of our method with a numerical example. This paper is structured as follows generally: In Section-2 introduces the fundamental concepts of neutrosophic sets, neutrosophic edge connectivity, and their mathematical characteristics. In Section-3 offers the suggested method for neutrosophic edge connection along with its TSP solving application. In Section -4 shows a numerical case to support the Aparna Tripathy, Amaresh Chandra Panda, Siva Prasad Behera, Prasanta Kumar Raut, A Decision -Making Model for the Travelling Salesman Problem Based on Neutrosophic Edge Connectivity Neutrosophic Sets and Systems, Vol. 93, 2025 429 suggested approach. In Section-5 offers a comparative study of the suggested method using models of classical and fuzzy edge connectivity. In Section6 finishes the work and addresses future avenues of investigation. This work suggests a novel method to solve the TSP under uncertainty, thereby advancing neutrosophic graph theory. Our approach provides a more flexible and useful answer to real-world routing and transportation issues by including neutrosophic edge connection. 2. Preliminaries: 2.1 Neutrosophic Sets: Florentin Smarandache presented a mathematical framework called a neutrosophic set to address uncertainty, imprecision, ambiguity, and partial knowledge. Including three independent membership functions, it expands classical, fuzzy, and intuitionistic fuzzy set theories. and three membership values, i.e., truth, indeterminacy, and falsity, lie in [0,1]. Every component of a neutrosophic set is expressed as 𝐴 = {(𝑥,𝑇(𝑥),𝐼(𝑥),𝐹(𝑥)) ∣ 𝑥 ∈ 𝑈} And the condition satisfies three membership values: 0 ≤ 𝑇(𝑥)+ 𝐼(𝑥)+ 𝐹(𝑥)≤ 3 1 2.2 Neutrosophic Edge Connectivity: Definition and Properties Neutrosophic edge connection expands the conventional idea of edge connectivity by including uncertainty, doubt, and ambiguity in network architectures. Each edge of a neutrosophic graph has three components: truth (T), indeterminacy (I), and falsity (F), which, taken together, describe the dependability and stability of an edge. Taking these neutrosophic traits into account, the neutrosophic edge connectivity of a graph is the smallest number of edges that, when taken away, split a graph into two or more disconnected parts. Aparna Tripathy, Amaresh Chandra Panda, Siva Prasad Behera, Prasanta Kumar Raut, A Decision -Making Model for the Travelling Salesman Problem Based on Neutrosophic Edge Connectivity Neutrosophic Sets and Systems, Vol. 93, 2025 430 2.3 Neutrosophic Graph Mathematical Representation Consider a Graph 𝐺 = (𝑉,𝐸,𝑁) • A set of vertices V. • A set of edges E connecting these vertices. • A neutrosophic function 𝑁: 𝐸 → [𝑇,𝐼,𝐹], where each edge has an associated truth, indeterminacy, and falsity value within the range [0,1]. The neutrosophic edge connectivity 𝜆𝑁(𝐺) is defined as the minimum number of edges whose removal increases the number of connected components in G, taking into account the indeterminacy component. 2.4 Properties and Characteristics • Unlike traditional edge connectivity, the neutrosophic model allows uncertainty to be accommodated, therefore enabling a more realistic evaluation of network resilience. • Dynamic Behaviour: The connection strength changes dynamically to fit the shifting edge parameter character. • Flexibility in Optimization: This method is very helpful in decisions when edges show varying degrees of dependability. • Neutrosophic edge connection offers a wider view of network resiliency than conventional and fuzzy models. 3. Proposed Algorithm for Neutrosophic Edge Connectivity and Its Application in the Travelling Salesman Problem Step 1: Representation of the Graph in Neutrosophic Environment 1. Define a weighted graph where is the set of vertices (cities) and is the set of edges (routes between cities). 2. Assign a neutrosophic weight to each edge, represented as, where: • (Truth) represents the degree of certainty that the edge exists. • (Indeterminacy) represents the uncertainty in edge existence. Aparna Tripathy, Amaresh Chandra Panda, Siva Prasad Behera, Prasanta Kumar Raut, A Decision -Making Model for the Travelling Salesman Problem Based on Neutrosophic Edge Connectivity Neutrosophic Sets and Systems, Vol. 93, 2025 431 • (Falsity) represents the degree of nonexistence of the edge. Step 2: Computation of Neutrosophic Edge Connectivity 1. Compute the edge connectivity of the graph under the neutrosophic setting by: • Finding the minimum cut-set using neutrosophic weights. • Identifying critical edges based on their neutrosophic strength. • Using a modified max-flow algorithm incorporating neutrosophic values. 2. Normalize the edge connectivity values to obtain a crisp equivalent measure for comparison. Step 3: Formulating the Travelling Salesman Problem (TSP) under Neutrosophic Constraints 1. Construct the distance matrix using neutrosophic edge weights. 2. Define the objective function: • Minimize the total cost considering neutrosophic uncertainty factors. • Ensure every vertex is visited exactly once and returns to the starting point. Step 4: Solving Neutrosophic TSP using an Optimization Algorithm 1. Apply a heuristic or metaheuristic approach such as Genetic Algorithm (GA), Ant Colony Optimization (ACO), or Particle Swarm Optimization (PSO) adapted to handle neutrosophic numbers. 2. Modify the cost function to incorporate neutrosophic weights. 3. Use a selection mechanism based on the certainty level while considering and Perform optimization iterations to find the optimal route under neutrosophic uncertainty. Step 5: Defuzzification and Decision Making 1. Convert the final neutrosophic solution into a crisp value by applying a defuzzification technique (e.g., score function, centroid method). 2. Compare the results with classical TSP solutions to analyze improvements in route efficiency. Aparna Tripathy, Amaresh Chandra Panda, Siva Prasad Behera, Prasanta Kumar Raut, A Decision -Making Model for the Travelling Salesman Problem Based on Neutrosophic Edge Connectivity Neutrosophic Sets and Systems, Vol. 93, 2025 432 3. Evaluate the robustness of the proposed model by testing different levels of uncertainty. Step 6: Application and Case Study Analysis 1. Implement the proposed model on real-world transportation data. 2. Compare results with classical edge connectivity and TSP solutions. 3. Validate efficiency improvements in decision-making under uncertainty conditions. 4. Mathematical Example Using the Proposed Algorithm 4.1 Problem Statement: A logistics company needs to find the optimal delivery route among four cities A,B,C,D. The roads between these cities are represented as a neutrosophic weighted graph G = (V,E). The objective is to determine the neutrosophic edge connectivity and solve the Travelling Salesman Problem (TSP) considering uncertainty. Aparna Tripathy, Amaresh Chandra Panda, Siva Prasad Behera, Prasanta Kumar Raut, A Decision -Making Model for the Travelling Salesman Problem Based on Neutrosophic Edge Connectivity Neutrosophic Sets and Systems, Vol. 93, 2025 433 Step 1: Representation of the Graph in Neutrosophic Environment We define the graph with four cities: 𝑉 = {𝐴,𝐵,𝐶,𝐷} The roads (edges) between the cities have neutrosophic weights in the form: 𝑤𝑖𝑗 = (𝑇𝑖𝑗,𝐼𝑖𝑗,𝐹𝑖𝑗) where: • 𝑇𝑖𝑗 (Truth): Certainty of the edge's existence. • 𝐼𝑖𝑗 (Indeterminacy): Uncertainty due to weather, traffic, etc. • 𝐹𝑖𝑗 (Falsity): Probability that the edge does not exist. The neutrosophic adjacency matrix for the weighted graph is: 𝐖=[ −−−−− (0.9,0.1,0.0) (0.7,0.2,0.1) (0.8,0.1,0.1) (0.9,0.1,0.0) −−−−− (0.85,0.1,0.05) (0.75,0.15,0.1) (0.85,0.1,0.05) (0.7,0.2,0.1) − − − − − (0.9,0.05,0.05) (0.8,0.1,0.1) (0.75,0.15,0.1) (0.9,0.05,0.05) −−−−− ] Step 2: Computation of Neutrosophic Edge Connectivity Step 2.1: Defuzzification of Neutrosophic Weights To convert the neutrosophic weights into crisp values, we use the defuzzification formula: 𝑊′𝑖𝑗 = (𝑇𝑖𝑗 − 𝐼𝑖𝑗 − 𝐹𝑖𝑗) Applying this formula: 𝐖′=[− 0.8 0.4 0.6 0.8 − 0.7 0.5 0.4 0.7 − 0.8 0.6 0.5 0.8 −] Aparna Tripathy, Amaresh Chandra Panda, Siva Prasad Behera, Prasanta Kumar Raut, A Decision -Making Model for the Travelling Salesman Problem Based on Neutrosophic Edge Connectivity Neutrosophic Sets and Systems, Vol. 93, 2025 434 Step 2.2: Compute Edge Connectivity The edge connectivity 𝜆𝑁(𝐺) is the minimum number of edges that need to be removed to disconnect the graph: 1. The smallest weight is 0.4 (between A and C). 2. Removing this edge does not disconnect the graph. 3. Removing two edges: (A, C) and (B, D) (0.4 and 0.5) disconnects the graph. 4. Thus, the neutrosophic edge connectivity is 𝜆𝑁(𝐺)= 2. Step 3: Formulating the Travelling Salesman Problem (TSP) under Neutrosophic Constraints The goal is to minimize the total cost while considering uncertainty. The distance matrix is: 𝐖′=[− 0.8 0.4 0.6 0.8 − 0.7 0.5 0.4 0.7 − 0.8 0.6 0.5 0.8 −] We need to find the shortest route that visits all cities exactly once and returns to the starting city. Step 4: Solving Neutrosophic TSP using Optimization Using the Nearest Neighbour Algorithm (NNA): 1. Start at A. 2. Visit the nearest unvisited city: • A → C (cost: 0.4) • C→B (cost: 0.7) Aparna Tripathy, Amaresh Chandra Panda, Siva Prasad Behera, Prasanta Kumar Raut, A Decision -Making Model for the Travelling Salesman Problem Based on Neutrosophic Edge Connectivity