Abstract
This thesis presents a heuristic algorithm for solving traveling salesman problem by utilizing dynamic programming and divide-and-conquer methods. In our algorithm, a complete, whole tour is divided into several sub-tours, and refined by dynamics programming respectively to get the better solution. In order to escape from local optimal, we modify the refinement algorithm to city group version that refine solution in city group unit. This algorithm does work under many instances with the size of thousand of cities, showed in chapter 4 experimental results).