본문 바로가기
  • Home

Greedy-based Neighbor Generation Methods of Local Search for the Traveling Salesman Problem

  • Journal of The Korea Society of Computer and Information
  • Abbr : JKSCI
  • 2022, 27(9), pp.69-76
  • DOI : 10.9708/jksci.2022.27.09.069
  • Publisher : The Korean Society Of Computer And Information
  • Research Area : Engineering > Computer Science
  • Received : August 23, 2022
  • Accepted : September 16, 2022
  • Published : September 30, 2022

Junha Hwang ORD ID 1 Yongho Kim 1

1금오공과대학교

Accredited

ABSTRACT

The traveling salesman problem(TSP) is one of the most famous combinatorial optimization problem. So far, many metaheuristic search algorithms have been proposed to solve the problem, and one of them is local search. One of the very important factors in local search is neighbor generation method, and random-based neighbor generation methods such as inversion have been mainly used. This paper proposes 4 new greedy-based neighbor generation methods. Three of them are based on greedy insertion heuristic which insert selected cities one by one into the current best position. The other one is based on greedy rotation. The proposed methods are applied to first-choice hill-climbing search and simulated annealing which are representative local search algorithms. Through the experiment, we confirmed that the proposed greedy-based methods outperform the existing random-based methods. In addition, we confirmed that some greedy-based methods are superior to the existing local search methods.

Citation status

* References for papers published after 2022 are currently being built.

This paper was written with support from the National Research Foundation of Korea.