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.
| Identifer | oai:union.ndltd.org:tamu.edu/oai:repository.tamu.edu:1969.1/3735 |
| Date | 16 August 2006 |
| Creators | Lee, Seung Ho |
| Contributors | Butenko, Sergiy |
| Publisher | Texas A&M University |
| Source Sets | Texas A and M University |
| Language | en_US |
| Detected Language | English |
| Type | Book, Thesis, Electronic Thesis, text |
| Format | 371208 bytes, electronic, application/pdf, born digital |
Page generated in 0.0019 seconds