# Adjustable Pheromone Reinforcement Strategies for Problems with Efficient Heuristic Information
## 3 Combinatorial Optimization Problems Relevant to This Study  
Ant colony optimization always uses pheromone trails and, for some problems, heuristic information to guide the ant's construction of a particular solution. For some problems, useful heuristic information was not discovered. For example, in the case of the quadratic assignment problem (QAP) one of the best-performing variants of the ACO algorithm, the MAX-MIN ant system, does not use heuristic information. Other examples of NP-hard problems for which successful ACO algorithms do not use heuristic information are the shortest common supersequence problem (SCSP) [31] and the maximum clique problem (MCP) [32].  
For some problems, researchers discovered heuristic information that can significantly guide and speed up the search process and, thus, improve the performance of ACO algorithms. This includes the traveling salesman problem (TSP), asymmetric traveling salesman problem (ATSP), sequential ordering problem (SOP), vehicle routing problem with time window constraints (VRPTW) [33], car renter salesman problem (CaRS), and many others. For example, by using heuristic information (with parameter \(\beta\) = 4) for TSP problem instance pka379, one ant in ACO can increase the probability of obtaining a particular optimal solution in the first iteration by an enormous 1.03 \(\times\) 10\({}^{719}\) times. Since TSP with 379 nodes has 378!/2 = 3.28 \(\times\) 10\({}^{811}\) solutions, this probability is increased from 3.05 \(\times\) 10\({}^{-812}\) without heuristic information to 3.14 \(\times\) 10\({}^{-93}\) with heuristic information. It is obvious that, when considering those probabilities, we never expect to obtain an optimal solution in the first iteration of the algorithm, but heuristic information can help tremendously in starting iterations of ACO algorithms [34].  
We used TSP and ATSP for experimental investigation in this research as they are often used for testing new techniques or strategies of the swarm and evolutionary computation algorithms and have various interesting extensions like SOP, VRPTW, and CaRS.  
The asymmetric traveling salesman problem can be defined using a weighted directed graph with a set of vertices V and a set of arcs A. The objective is to visit all vertices exactly once and return to the starting vertex while minimizing the total tour weight. All the information needed to solve the problem can be stored in a matrix that specifies the distance between vertices in each direction (e.g., because of one-way streets).  
\[D=\begin{bmatrix}d_{11}&d_{12}&\cdots&d_{1n}\\ d_{21}&d_{22}&\cdots&d_{2n}\\ \vdots&\vdots&\ddots&\vdots\\ d_{n1}&d_{n2}&\cdots&d_{nn}\end{bmatrix}\]  
The symmetric variant of the problem, where \(d_{ij}=d_{ji}\), is traditionally studied separately, is denoted simply as TSP. The symmetric TSP is possibly one of the most researched NP-hard problems with significant achievements for some special variants. After decades of research for the metric variant of TSP and especially Euclidian TSP, there are specialized heuristics that can efficiently solve rather large instances, often to an optimum. In metric TSP, there is a constraint that, for any three nodes labeled as \(i,j\), and \(k\), the following triangle inequality holds:  
\[d_{ij}+d_{jk}\leq d_{ik} \tag{1}\]  
In addition, for Euclidian TSP, it is true that for any two nodes \(i\) and \(j\) with coordinates \((x_{i},y_{i})\), \((x_{j},y_{j})\) the distance \(d_{ij}\) is given by:  
\[d_{ij}=\sqrt{\left(x_{i}-x_{j}\right)^{2}+\left(y_{i}-y_{j}\right)^{2}}. \tag{2}\]In this context, metaheuristics usually use metric and Euclidean TSP instances for testing new techniques and strategies and less commonly to produce the best performing algorithm for such variants.