본문 바로가기
  • Home

The Extended k-opt Algorithm for Traveling Salesman Problem

  • Journal of The Korea Society of Computer and Information
  • Abbr : JKSCI
  • 2012, 17(10), pp.155-165
  • Publisher : The Korean Society Of Computer And Information
  • Research Area : Engineering > Computer Science

Sang-Un, Lee 1

1강릉원주대학교

Accredited

ABSTRACT

This paper suggests traveling salesman problem algorithm that have been unsolved problem with NP-Hard. The proposed algorithm is a heuristic with edge-swap method. The classical method finds the initial solution starts with first node and visits to mostly adjacent nodes then decides the traveling path. This paper selects minimum weight edge for each nodes, then perform Min-Min method that start from minimum weight edge among the selected edges and Min-Max method that starts from maximum weight edges among it. Then we decide tie initial solution to minimum path length between Min-Min and Min-Max method. To get the final optimal solution, we apply previous two-opt to initial solution. Also, we suggest extended 3-opt and 4-opt additionally. For the 7 actual experimental data, this algorithm can be get the optimal solutions of state-of-the-art with fast and correct.

Citation status

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