Lee, Seung Ho (2005-05). Greedy randomized adaptive search procedure for traveling salesman problem. Master's Thesis. Thesis uri icon

abstract

  • In this thesis we use greedy randomize adaptive search procedure (GRASP) to solve the traveling salesman problem (TSP). Starting with nearest neighbor method to construct the initial TSP tour, we apply the 2-opt and the path-relinking method for the initial tour improvement. To increase 2-opt search speed, fixed-radius near neighbor search and don0t − look bit techniques are introduced. For the same reason a new efficient data structure, the reverse array, is proposed to represent the TSP tour. Computational results show that GRASP gives fairly good solutions in a short time.
  • In this thesis we use greedy randomize adaptive search procedure (GRASP) to solve
    the traveling salesman problem (TSP). Starting with nearest neighbor method to
    construct the initial TSP tour, we apply the 2-opt and the path-relinking method
    for the initial tour improvement. To increase 2-opt search speed, fixed-radius near
    neighbor search and don0t − look bit techniques are introduced. For the same reason
    a new efficient data structure, the reverse array, is proposed to represent the TSP
    tour. Computational results show that GRASP gives fairly good solutions in a short
    time.

publication date

  • May 2005