Experimental Analisy of Variants of the Lin and Kernighan’s heuristic for the Multi-objective Traveling
Salesman Problem
Traveling Salesman Problem, MTSP, Lin and Kernighan, Multiobjective
The Lin and Kernighan’s heuristic (LK) is one of the most effective methods for the Traveling Salesman Problem (TSP). Due to this fact, different implementations for the LK were proposed in literature and this heuristic is also used as part of various meta-heuristic algorithms. LK has been used in the context of the multi-objective TSP (MTSP) as originally proposed by its authors, i.e., with a single objective focus. This study investigates variants of the LK heuristic in the multi-objective context. We investigate the potential of LK extensions combined with other metaheuristic techniques. Results of a computational
experimental are reported for MTSP instances with 2, 3 and 4 objectives.