New Genetic Operator (Jump Crossover) for the Traveling Salesman Problem

2.1. Traveling Salesman Problem

The TSP is a classic combinatorial optimization problem, simple in its formulation but very difficult to solve. This problem is known to be NP-hard, in other words it cannot be solved exactly in polynomial time. Many exact and heuristic algorithms have been developed in the field of Operations Research (OR) to solve it. The problem is to find the shortest possible tour through a set of n vertices in such a way that each vertex is visited once and only once.

This problem can be divided into two categories depending on the form of the costs matrix: symmetric and asymmetric. If the equality C(i, j) = C(j, i) is satisfied, the TSP is symmetric, otherwise it is called an asymmetric TSP, i and j being any vertex. In a symmetric TSP of n cities, there are (n-1)!/2 possible solutions and their inverses cyclic permutations with the same total cost. The purpose is then to find a Hamiltonian cycle with minimum total cost (Cicirello & Smith, 2000).

2.2. Mathematic Formulation

The TSP is formulated as a cost matrix in n dimensions of d_ij values Figure 1, where the purpose is to obtain a permutation of these values, as the sum of costs d_ij is minimal, for all i and j, where i is a node and j his next in a sequence.

Figure 1.

Distance matrix of symmetric TSP of 8 cities

More formally, we have:

We consider d_ij = d_ji, ∀ i, j to work on the symmetric TSP (STSP);