| Title |
Modified local search heuristics for the symmetric traveling salesman problem |
| Another Title |
Modifikuoti euristiniai lokaliosios paieškos algoritmai sprendžiant simetrinio tipo komivojažieriaus uždavinį. |
| Authors |
Misevičius, Alfonsas ; Blažinskas, Andrius ; Lenkevičius, Antanas |
| DOI |
10.5755/j01.itc.42.3.1301 |
| Full Text |
|
| Is Part of |
Informacinės technologijos ir valdymas = Information technology and control.. Kaunas : KTU. 2013, t. 42, Nr. 3, p. 217-230.. ISSN 1392-124X. eISSN 2335-884X |
| Keywords [eng] |
Artificial intelligence ; Heuristics ; Local search ; Combinatorial optimization ; Traveling salesman problem |
| Abstract [eng] |
In this paper, we investigate some modified local search (LS) heuristics for the solution of symmetric traveling salesman problem (TSP). These modifications are mainly due to the use of extended neighborhood structures. In addition, we are concerned with several new sets of the moves (transitions of solutions) based on the extended configurations of edge exchanges. We are also examining the performance of these extensions being used in an iterated local search (ILS) paradigm. The results from the experiments with the benchmark TSP instances from the TSP library (TSPLIB) demonstrate that the introduced improvements enable to seek solutions of higher quality without substantially increasing computational complexity. |
| Published |
Kaunas : KTU |
| Type |
Journal article |
| Language |
English |
| Publication date |
2013 |
| CC license |
|
