In this work, the iterated tabu search (ITS) algorithm for the traveling salesman problem (TSP) is discussed. The TSP is a well-known combinatorial optimization problem. Thus, solving the TSP means searching for the shortest closed tour in which every city is visited exactly once. Various heuristic algorithms can be used for solving the TSP, among them, tour construction heuristics, simulated annealing, genetic algorithms, etc. One of the promising heuristic techniques is the iterated tabu search approach. ITS consists of two main parts: standard tabu search (TS) and mutation of solutions. The goal of TS is finding a locally optimal solution in the neighbourhood of the current solution, while the mutation operators are responsible for escaping from the current local optimum and moving towards new regions in the solution space. Several mutation procedures have been analyzed in this work, in particular, exchange mutation, insert mutation, inversion mutation, and others. In order to investigated the performance of the mutation operators, computational experiments with the test instances from the TSP instances library TSPLIB were carried out. The results obtained from these experiments show that the mutation operators play the important role and influence the solution quality significantly.

Šiame darbe nagrinėjamas patobulintas tabu paieškos metodas, žinomas kaip iteratyvioji tabu paieška (ITP). Pasiūlytos kai kurios ITP metodo modifikacijos, besiremiančios tam tikromis sprendinių mutavimo (pertvarkymo) procedūromis (inversijos, įterpimai ir kt.), kurios įgalina pagerinti gaunamų sprendinių kokybę. Atlikti išsamūs sudaryto ITP algoritmo ir kitų pasiūlytų modifikacijų eksperimentiniai tyrimai, panaudojant testinius KU pavyzdžius iš KU testinių pavyzdžių bibliotekos TSPLIB. Gauti rezultatai patvirtina pasiūlytų modifikacijų pranašumą kitų ITP variantų atžvilgiu. / In this work, one of the heuristic algorithm – the iterated tabu search and its modifications are discussed. The work is organized as follows. Firstly, some basic definitions and preliminaries are given. Then, the iterated tabu search algoritm and its variants based on special type mutations are considered in more details. The ITS algorithms modifications were tested on the TSP instances from the TSP library TSPLIB. The results of this tests (experiments) are presented as well. The work is completed with the conclusions.

In this work, the Traveling Salesman Problem (TSP) is discussed. The Hybrid Genetic Algorithm for solving the TSP is presented. The traveling salesman problem is formulated as follows: given matrix D=(dij)nxn of distances between n objects and the set P of permutations of the integers from 1 to n, find a permutation p=(p(1), p(2), ..., p(n)) P that minimizes. Many heuristic algorithms can be applied for the TSP. Recently, genetic algorithms (GAs) are among the advanced heuristic techniques for the combinatorial problems, like the TSP. genetic algorithms are based on the biological process of natural selection. The original concepts of GAs were developed in 1970s. Many simulations have demonstrated the efficiency of GAs on different optimization problems, among them, bin–packing, generalized assignment problem, graph partitioning, job–shop scheduling problem, set covering problem, vehicle routing. One of the main operators in GAs is the crossover (i.e. solution recombination). This operator plays a very important role by constructing competitive GAs. In this work, we investigate several crossover operators for the TSP, among them, CX (cycle crossover), PMX (partialy mapped crossover), POS (position based crossover), ER (edge recombination crossover), edge-NN (edge recombination crossover, nearest neighbour) and AP (alternating-positions crossover). Comparison of these crossover operators was performed. The results show high efficiency of the edge-NN, ER and PMX crossovers.