## 3 The Travelling Salesman Problem  
The TSP has given rise to a wide variety of research, due to its simplicity of description but its complexity at the time of obtaining a solution [21]. If the problem is formulated using graph theory terminology, it can be defined as a graph \(G=(V,A)\), where \(V=\{v_{1},\)\(\ldots\)\(v_{n}\}\) consists of a set of \(n\) vertices (nodes) and \(A=\{(v_{i},v_{j})/v_{i},\)\(v_{j}\in V,\)\(i\
eq j\}\) is a set of edges with an associated non-negative cost (distance) matrix \(D=(d_{ij})\). The problem is symmetric if \(d_{ij}=d_{ji}\) for any pair of vertices \((v_{i},v_{j})\in A\), and it is said to be asymmetric (ATSP) otherwise.  
If \(l\):\(\{1,\)\(\ldots,n\}\rightarrow\{1,\)\(\ldots,n\}\) is a bijective function that determines a reordering of vertices \(v_{i}\) in \(V\), the TSP can be defined as obtaining the minimal result for the following calculation:  
\[F_{TSP}=\sum_{j=1}^{n-1}d_{I(j)I(j+1)} \tag{1}\]  
It is easy to establish an analogy or correspondence between the TSP and the problem of managing traffic in smart cities. For example, the set of nodes can be related to the different city locations where a van or truck must deliver its cargo from a depot. As previously explained, the meaning of _distance_ in the case of urban environments is different from the mere concept of geographical distance, because it can also incorporate traffic lights and their crossing times, pedestrian crossings, speed limits, and even dynamic factors, such as temporary traffic jams, road maintenance works, and accidents. In addition, data collected on fuel consumption and pollution related to different roads can be added.  
For a set of \(n\) nodes, obtaining the optimal solution by means of exhaustive search is a problem that implies \((n-1)!\) comparisons. As an example, in the case of ten nodes, the required comparisons between possible solutions would be 9! = 362,880, and 15 nodes would imply comparing 14! = 87,178,291,200 possible solutions to obtain the best solution. The extensive list of research papers related to TSP has produced different methods that try to decrease the aforementioned complexity. Heuristic methods are suitable for managing TSP, and much attention has been paid to these types of methods among researchers on optimization. In [22], a review of swarm intelligence applied to graph search problems is contributed, but the paper focuses almost solely on ant colony optimization (ACO) and bee colony optimization (BCO).  
In [23], two different modifications of the artificial bee colony (ABC) method are applied to TSP: a combinatorial algorithm, called CABC, and an improved version of CABC, called qCABC. Experiments are performed on a benchmark of 15 TSP instances. The performance of these two algorithms and eight different genetic algorithm (GA) versions is compared. Moreover, the performance of ABC is also compared with the ant colony system (ACS) and bee colony optimization methods. Results show the suitability of CBAC and qCABC algorithms to be applied to TSP problems.  
Most of the works related to solving the TSP by means of metaheuristic optimization methods use the ant colony optimization method [24; 25; 26; 27; 28], sometimes in a hybrid version with other methods [29]. This is because the natural behavior of ants in the development of a colony can be easily matched to the problem of finding the shortest path between a series of nodes.