The traveling salesman problem (TSP) is a classical combinatorial optimization problem that involves finding the shortest or fastest route among a set of citie s. To formalize the uncertainty and imprecision in input data, often caused by subjective evaluations of the travel time intervals, this paper employs fuzzy numbers. The form of these fuzzy numbers is based on a Gaussian-like approach. This work examines the specifics of applying the ant colony optimization (ACO) algorithm and proposes an approach for its optimal use. The impact of the algorithm's parameters on the quality of the approximated best solution is analyzed. The problem is illustrated with numerical examples involving a sufficiently large number of cities in the transportation network. fuzzy traveling salesman problem, ant colony optimization method, trapezoidal fuzzy numbers, defuzzification, performance evaluation DA), bees (Bee Algorithm, BA), termites (Termite Algorithm), fish (Fish Swarm Algorithm, FSO), and wolves (Wolf Pack Algorithm, WSA).
One of the promising directions in scientific and practical research of social and information processes is based on the use of mathematical methods that incorporate the principles of natural decision-making mechanisms. Swarm intelligence is a relatively new technological approach formalized through the analysis of the social behavior of animals and insects. In particular, observations of ants have led to the development of several methods and techniques, the most studied and successful of which is the general optimization method known as Ant Colony Optimization (ACO). The simulation of the self-organization of an ant colony forms the basis of ant optimization algorithms—a new and promising method of natural computation. Other natural prototypes for optimization methods include the behavior of dragonflies (Dragonfly Algorithm, tolerance. Systems based on swarm intelligence allow for the rapid discovery of efficient solutions under conditions of dynamic parameter changes, agent failures, and without requiring centralized control limitations.
Let us consider the application of swarm intelligence for solving optimization problems using
ACO [
An ant colony can be viewed as a multi -agent system in which each agent (ant) operates
autonomously according to defined rules. The behavior of each agent is governed by simple
probabilistic rules. This principle aligns with the behavior of ants in the real world, where they
work together to build nests, forage for food, and protect the colony. Studies [
The idea of the algorithm is based on the behavior of an ant colony, which finds a path to food that is close to optimal. The core of ant behavior is self-organization - a set of dynamic mechanisms by which the system achieves a global goal as a result of interactions at a low level.
Multiple interactions are implemented in the form of sequential iterative route searches conducted simultaneously by several ants. Each ant starts its movement randomly when leaving the nest in search of food. It is assumed that each agent does not follow a predetermined path or direction. This exploratory behavior allows ants to explore a wide area around the nest. A key aspect of ant behavior is their ability to leave chemical traces—pheromones—along their path. These pheromones serve as signals for other ants, indicating that the path has already been explored and is in use. Wh en an ant finds food, it returns to the nest, leaving a pheromone trail that helps other ants find the path to the food. The amount of pheromone deposited by the ant on each segment of the route is inversely proportional to the length of that segment. The shorter the path found by the ant during the search, the more pheromone will be deposited on the corresponding segments (graph edges).
It should be noted that the use of only positive feedback leads to the rapid (premature) convergence of the algorithm, meaning that all ants will follow the same suboptimal route. To prevent oversaturation of the paths, pheromones evaporate over time, which implements negative feedback. This allows ants to adapt to changes in the environment (for example, the appearance of new food sources or obstacles on the paths).
Thanks to the mechanisms of inter-agent interaction, the system self-organizes, allowing individual ants to use optimal paths to food sources while enabling efficient solutions to resource allocation and search problems without centralized control.
From a mathematical perspective, the ACO model is described through the following basic components related to the behavior of both individual ants and the system as a whole: mechanisms for path formation; pheromone deposition to mark the traversed paths; pheromone evaporation; rules for an ant's path selection.
One of the problems for which a solution based on the ant colony algorithm can be proposed is
the traveling salesman problem [
The standard formulation of the traveling salesman problem is to choose the shortest (in length or time) closed path on a network of cities that passes through all cities exactly once. The number of possible options is (n − 1)! , and if the stages of the route are symmetric, the number of unique routes is (n − 1)!/ 2 .
The problem is to find the optimal traveling salesman path, the determination of which requires a very large amount of computational resources, which leads to the need to use approximate algorithms such as ACO.
His In real logistics problems, the concept of the duration or cost of travel between individual points of the transport network cannot be fixed; they are determined approximately, often with the influence of the subjective factor based on estimates of time periods or the cost of movement along the route sections. This leads to the need to take into account uncertainty, its formalization based on different methods. One of the approaches used in this case is to involve fuzzy numbers and implement means of manipulating them.
Let's consider the formulation of the traveling salesman problem with a vaguely specified
duration of movements at the stages of the transport and logistics network. In this case, it is
necessary to find a cyclic permutation of the numbers of the cities to be visited by the traveling
salesman, according to which the time spent will be minimal, taking into account the restriction on
visiting each of the points no more than once. The mathematical formulation of the fuzzy problem
of the traveling salesman can be written as follows: it is necessary to minimize, taking into account
some method of comparing fuzzy numbers, the objective function
where the time costs for moving between points are given in the form of a matrix T = {tij } ,
i ,j = 1,n , with elements in the form of fuzzy numbers [
n ∑j =1x ij = 1 for all i = 1,2,...,n , i −j +nx ij ≤n − 1 , 1 ≤i ≠ j ≤n , x ij = 0 or 1 for all i ,j = 1,2,...,n .
x −a 1 ,if a 1 ≤x ≤a 2 , a 2 −a 1 µA (x ) =1, ifa 2 ≤x ≤a 3 , a 4 −x ,if a 3 ≤x ≤a 4 .
(1) (2) (3)
For the software implementation, the diagonal elements tii of the matrix T should be set to large positive numbers to ensure that the solution provides values x ii = 0 for all i = 1,2,....,n . The fuzzy travel durations tij between arbitrary cities i ,j = 1,n , will be represented as trapezoidal fuzzy numbers.
Definition. A trapezoidal fuzzy number A [
If a Gaussian-based approach with corresponding characteristics is applied to the representation of a trapezoidal fuzzy number, then in the generalized case, the trapezoidal fuzzy number can be represented in a slightly different form:
A =,a2 (a 1 ,a 3 ,a 4 ) =,a ([a 2 3 ] ,α ,β ) =,w,α (m ,β ) , A = (a 1 ,a 2 ,a 3 ,a 4 ) . To operate with fuzzy numbers, it is necessary to define operations based on the description provided above. The midpoint is taken as the simple arithmetic mean of the plateau boundaries, and the left and right distributions are considered according to the lattice rule, where for arbitrary real numbers a ,b we set a ∪b =max{a ,b } and a ∩b =min {a ,b } .
Then, for arbitrary trapezoidal fuzzy numbers
A = (m (A ) ,w (A ) ,α 1 ,β1 ) and B = (m (B ) ,w (B ) ,α 2 ,β2 ) the operations of addition, subtraction, multiplication, and division can (4) (5) (6) (7) be defined, which in the general case are denoted by the symbol :
A B =(A) (m m (B ) ,w (A ) ∪w (B ) ,α 1 ∪α 2 ,β1 ∪ β2 ) = (m (A ) m (B ) , max (w (A ) ,w (B )) , max (α 1 ,α 2 ) , max (β1 ,β2 )) .
Finally, we have:
A +B =(m (A ) +m (B ) ,w (A ) ∪w (B ) ,α 1 ∪α 2 ,β1 ∪ β2 ) =(m (A ) +m (B ) , max (w (A ) ,w (B )) , max (α 1 ,α 2 ) , max (β1 ,β2 )) ,
A −B =(m (A ) −m (B ) ,w (A ) ∪w (B ) ,α 1 ∪α 2 ,β1 ∪ β2 ) =(m (A ) −m (B ) , max (w (A ) ,w (B )) , max (α 1 ,α 2 ) , max (β1 ,β2 )) ,
A ×B =(m (A )×m (B ) ,w (A ) ∪w (B ) ,α 1 ∪α 2 ,β1 ∪ β2 ) =(m (A )×m (B ) , max (w (A ) ,w (B )) , max (α 1 ,α 2 ) , max (β1 ,β2 )) ,
A ÷B =(m (A ) ÷m (B ) ,w (A ) ∪w (B ) ,α 1 ∪α 2 ,β1 ∪ β2 )
The process of handling fuzzy numbers involves a defuzzification stage - converting a fuzzy result into a crisp (numerical) value. This is a crucial step in the methodology of applying fuzzy logic, especially in fuzzy control and fuzzy business logic tasks, where fuzzy solutions need to be transformed into specific events or numerical values. There are various defuzzification methods, the most common of which are the Center of Gravity (CoG) or centroid method, the mean of maxima method, and the maximum method. For comparison of research results, we will use the =(m (A ) ÷m (B ) , max (w (A ) ,w (B )) , max (α 1 ,α 2 ) , max (β1 ,β2 )) .
To perform the operations of comparison and ranking of fuzzy numbers, we will use the method based on the median average value. In other words, if for each A =,a2 (a 1 ,a 3 ,a 4 )∈F (R ) a ranking function R :F (R ) →R with a median average value R (A ) =a2 +a 3 β −α , is defined,
+ 2 4 then for any two trapezoidal fuzzy numbers A = (a 1 ,a 2 ,a 3 ,a 4 ) and B = (b 1 ,b 2 ,b 3 ,b 4 ) we have the following possible comparison options: - A B if and only if R (A ) > R (B ) ; - A B if and only if R (A ) < R (B ) ; - A ≈B if and only if R (A ) = R (B ) .
Center of Gravity method. In this method, the defuzzification point is calculated as the center of gravity of the fuzzy set by the formula:
∫a 4x ⋅µ (x )dx CoG = a1 ∫a 4µ (x )dx a1 where x are the points of fuzzy number support, and point. ,
Path formation in the ASO model is described using a graph. Let G = (V ,E ) represent a graph, where V
– is the set of m vertices, and E is the set of edges. Each edge (i ,j )∈E is associated with two key parameters: the travel time t ij along edge (i ,j ) (typically proportional to the path length Dij ) and the pheromone intensity τij on edge (i ,j ) , i ,j =m . The preservation of pheromone levels is a key process for inter-agent interaction among ants. The pheromone intensity on edge (i ,j ) is updated based on the experience of the ants that have traversed this edge. The pheromone level is often updated using the following formula:
τij (s + 1) = (1 − ρ ) ⋅τij (s ) + ∆τij (s ) , where ρ is the pheromone evaporation coefficient, and 0 < ρ < 1 , а ∆τij (s ) is the amount of pheromone deposited by the ants on edge (i ,j ) during iteration s , s = 0,1,2,...
Pheromone evaporation decreases the intensity of pheromones on all edges, allowing the system to forget previous (possibly suboptimal) paths and adapt to changes. This prevents premature convergence to local optima. The selection of each step in the ant's path is based on probabilistic rules. When, at iteration s ant k is at vertex i , it chooses the next vertex j with a certain probability Pijk (s ) , which depends on the pheromone intensity and visibility ηij , the latter being inversely proportional to the path length ηij = 1 /Dij : µ (x ) is the membership degree of each (8) (9) (10) (11) (12) Pijk (s ) =(τij (s ))α (ηij )
β ∑l ∈J ik (τil (s ))α (ηil )
β ,ifj ∈J ik , Pijk (s ) =0,ifj ∉J ik , where P denotes the set of edges that make up the ant's path. where τij (s ) is the pheromone intensity on edge (i ,j ) , ηij = 1 /Dij is the visibility (inversely proportional to the path length), and α and β that control the influence of pheromone intensity and visibility, respectively. The sum in the denominator is calculated over all available edges (the set of available vertices J ik from vertex i ). If α = 0 , the most likely transition will be to the nearest cities. In classical optimization theory, this corresponds to the so-called greedy algorithm. If β = 0 , only pheromone reinforcement operates, which leads to the rapid termination of the algorithm as all ants converge on the same suboptimal solution. Note that the sum of all transition probabilities from city i over all possible options from the set J ik at iteration s equals 1:
The main objective of the ant algorithm is to minimize the path length L , which is the sum of the lengths of the edges along the ant's path: ∑j ∈J iPijk (s ) = 1 .
L = ∑(i ,j )∈PDij ,
Let us consider the implementation scheme of the four main components of the self-organizing behaviour of ants during the optimization of the traveling salesman route. Sequentially implementing the iterative steps that replicate the procedure of finding the route by each ant, we obtain the functioning scheme of the ant algorithm for solving the fuzzy traveling salesman problem. The transition of an ant from city i to city j at iteration s of the algorithm depends on three components: the tabu list, visibility, and the virtual pheromone trail. The tabu list Aik is a list of cities that ant k has already visited before reaching vertex i , and revisiting them is forbidden. This list grows as the ant progresses along the route and is cleared at the beginning of each iteration of the algorithm. Let J ik denote the list of cities that ant k , currently at city i , still needs to visit. It is clear that the union of the lists traveling salesman problem.
Aik and J ik gives the set of all cities specified in the At the first iteration s = 0 , the amount of pheromones on each path is equal to τij (0) = 0 . At the start of the iteration, a set of ants is generated at each vertex of the graph.
During the iteration, each ant acts independently. In the first city i , the tabu list Aik for ant k consists of the city where the ant is currently located Aik = {i } . Then, each ant probabilistically selects the next city for movement based on the given travel time to the nearest cities using formula (1). For this, a random number generator will be used.
After selecting the next city j , this city is added to the tabu list Ajk = {i ,j } . In the next step, the ant selects the following city to move to, and so on, until the last city in the route. If the route cannot be closed, the ant is considered invalid until the next iteration. After the iteration is completed, pheromone evaporation is calculated for each possible edge. Then, for each ant that successfully completes its route after iteration s , the route duration is calculated, and for each edge used in the route, pheromone is added in an amount inversely proportional to the route duration for each ant ∆τij (s ) =Q, where Lk is the duration of the successful route of each ant
Lk
k , and edge (i ,j )∈Lk belongs to the route of ant k , Q is a tunable parameter, the value of which
is chosen to be on the same order as the length of the optimal route [
Thus, with properly chosen parameter values for α and β , we gradually obtain improved results with each iteration.
Let us proceed to the experimental section. As part of the computational experiment, we will calculate and compare the solution to the usual traveling salesman problem obtained by the enumeration method and the solutions to the corresponding fuzzy problem using the proposed approach.
Let us consider the traveling salesman problem on a transport network with a given travel time
(Fig. 1, the travel time between individual nodes is given by the values placed on the corresponding
edges) [
The optimal solution to the traveling salesman problem (1), (2) with a time criterion for the route duration is determined by the following sequence:
1 → 2 → 6 → 10 → 11 → 8 → 5 → 9 → 7 → 4 → 3 → 1 , (13)
which is 156 units [
In the first stage, the ACO algorithm was adapted to solve the traveling salesman problem with fuzzy travel durations between cities. For this, the problem was fuzzified using trapezoidal fuzzy numbers (Fig.2).
The ranking of routes with fuzzy durations was performed using the CoG method for continuous distribution.
For this problem, numerical calculations of the traveling salesman route were conducted using the ACO algorithm and the exhaustive search method. The application of the ASO algorithm to the traveling salesman problem in the specified configuration is characterized by a high convergence speed and ensures the best result with fairly conservative ASO parameters (see Table 1).
In the “iteration” column, the first iteration that contains the best solution with the highest probability is indicated.
The optimal solution to the problem defines the duration of the traveling salesman route as a fuzzy trapezoidal number (156,156,167,189) , with the result generally being achieved by the 3rd or 4th iteration, and its defuzzified value based on the CoG method is 167.92 units.
Further experiments with ASO were conducted to assess the quality of the obtained result, taking into account various numbers of cities in the transportation network. During the numerical calculations, the genetic algorithm was used to solve the TSP with random placement of n = 16,17,18 cities on a two-dimensional 200x200 plane, where the travel durations between network cities were determined by the average fuzzy time duration, assumed to be proportional to the distance between the corresponding cities. Three series of experiments were conducted, with the number of iterations equal to: four times the number of cities (Table 2), twice the number of cities (Table 3), and the number of cities (Table 4). The number of ants in each case was equal to the number of cities. For each experiment, simulations were conducted to vary the parameters β and α . A comparison of the best result obtained for the specified number of iterations with the best result obtained by exhaustive search is presented as percentages in Tables 2, 3, and 4. As can be seen from the results, when the number of iterations is equal to the number of cities, the algorithm yields results within 5% of the best solution. Increasing the number of iterations improves the results. The variation of the parameter β within the range from -4 to -1 and the parameter α within the range from 0.1 to 0.3 qualitatively impacts the results, bringing them closer to 5% deviation from the best result obtained by exhaustive search.
For comparison with the results obtained by other methods, computational experiments were
conducted using a genetic algorithm (GA) [
The table 5 shows the data of the averaged quality indicators of the obtained results of solving the traveling salesman problem based on the genetic algorithm with modeling of a transport network map consisting of n = 16,17,18 cities (without and with PNP, respectively). The efficiency indicators of calculations using the AСO method were compared with the time indicators of solving the problem using the genetic algorithm (Table 6).
As can be seen from tables 5 and 6, the deviations of the obtained results from the optimal also
do not exceed 5.5%, and the time costs for finding a solution do not differ significantly [
The results of the studies conducted in this paper demonstrate the application of the Ant Colony Optimization (ACO) algorithm to solve the traveling salesman problem with fuzzy travel time along the transport network. Trapezoidal fuzzy numbers are used to formalize the travel time values. A transformation of fuzzy number representation based on a Gaussian-like approach is used, and operations on fuzzy values are defined. The features of the ACO algorithm are considered and an approach for its application is proposed. The effectiveness of using this algorithm for finding locally optimal solutions in traveling salesman problems with a sufficiently large number of cities in the transport network is shown. Estimates of the deviation of the duration of the obtained solutions from the duration of the optimal route are given.
Computational experiments are conducted that show a significant influence of the ant colony algorithm parameters on the accuracy of approximate solutions to the fuzzy traveling salesman problem. The numerical examples provided also demonstrate the influence of the number of iterations on the accuracy of the results obtained.
A conclusion is made about the efficiency of using the ASO algorithm for solving fuzzy traveling salesman problems.
The authors have not employed any Generative AI tools.