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

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

Hicham El Hassani (Hassan II University, Morocco), Said Benkachcha (Hassan II University, Morocco) and Jamal Benhra (Hassan II University, Morocco)
DOI: 10.4018/978-1-5225-0788-8.ch069


Inspired by nature, genetic algorithms (GA) are among the greatest meta-heuristics optimization methods that have proved their effectiveness to conventional NP-hard problems, especially the traveling salesman problem (TSP) which is one of the most studied supply chain management problems. This paper proposes a new crossover operator called Jump Crossover (JMPX) for solving the travelling salesmen problem using a genetic algorithm (GA) for near-optimal solutions, to conclude on its efficiency compared to solutions quality given by other conventional operators to the same problem, namely, Partially matched crossover (PMX), Edge recombination Crossover (ERX) and r-opt heuristic with consideration of computational overload. The authors adopt a low mutation rate to isolate the search space exploration ability of each crossover. The experimental results show that in most cases JMPX can remarkably improve the solution quality of the GA compared to the two existing classic crossover approaches and the r-opt heuristic.
Chapter Preview

2. Genetic Algorithms 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 dij values Figure 1, where the purpose is to obtain a permutation of these values, as the sum of costs dij 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:

(1) with,

(3) Xij is the decision matrix (connection). S is a vertex Set from the global set V.

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

Complete Chapter List

Search this Book: