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.
| Identifer | oai:union.ndltd.org:LABT_ETD/oai:elaba.lt:LT-eLABa-0001:E.02~2006~D_20060602_173228-37727 |
| Date | 02 June 2006 |
| Creators | Simaitis, Rokas |
| Contributors | Maciulevičius, Stasys, Pranevičius, Henrikas, Barauskas, Rimantas, Mockus, Jonas, Misevičius, Alfonsas, Telksnys, Laimutis, Jasinevičius, Raimundas, Jusas, Vacius, Plėštys, Rimantas, Kaunas University of Technology |
| Publisher | Lithuanian Academic Libraries Network (LABT), Kaunas University of Technology |
| Source Sets | Lithuanian ETD submission system |
| Language | Lithuanian |
| Detected Language | English |
| Type | Master thesis |
| Format | application/pdf |
| Source | http://vddb.library.lt/obj/LT-eLABa-0001:E.02~2006~D_20060602_173228-37727 |
| Rights | Unrestricted |
Page generated in 0.0023 seconds