旅行銷售員問題(Traveling Salesman Problem, TSP)乃路線問題中最典型的一種，亦是計算機科學、管理科學以及作業研究等領域長期探討之議題。由於旅行銷售員問題屬於NP-Complete問題，因此依求解速度與其精確度所發展出的演算法可分為最佳解求解法(Exact Algorithm)與啟發式演算法(Heuristic Algorithm)。最佳解求解法能求得誤差值極小的解，但是在求解速度上，隨著問題的複雜度增加，求解所需時間也會呈指數的成長；另外，啟發式演算法在求解精確度雖不及最佳解求解法，但其時間複雜度(Time Complexity)卻屬多項式時間(Polynomial Time)複雜度，因此可以較短的時間獲致不錯的解。
本研究先以小型問題作為研究目標，結合k-節線交換法(k-opt)與分支切面法(Branch and Cut)，以k-opt為概念、分支切面法為主體，求解旅行銷售員問題，用已知最好的解作為交換目標，將不同之路徑交換數量化為不同之子問題求解。求解過程先計算替換較少路徑之子問題，當確定無法找到更好的解時才改計算替換的路徑數量更多之子問題。
本研究所提出之演算法，可較快找到新的上界(較好的可行解)，進而改善分支切面法的求解速度，因此有機會可以大幅度的改善演算法之完成時間。從時間成本的角度來看，若能較快得到較好的可行解，企業也能在較早的時間點減少成本上的損失。但由於分支切面法的初始解是由啟發式演算法求得，若其初始解恰為最佳解時，則不會有更好的解存在，因此造成本研究之演算法無法以較快速度來更新上界，因此本研究之演算法不適合運用在容易藉由啟發式演算法求出最佳解之問題。

Traveling Salesman Problem (TSP) is typical in Routing Problems. The TSP has usually been discussed in literature about computer science, management science and operation research. Since the TSP is NP-Complete problem, it can be solved by Exact Algorithm or Heuristic Algorithm. The optimal solution can be found by Exact Algorithm, but it is not a Polynomial time algorithm. Heuristic Algorithm is a Polynomial time algorithm, but cannot assure an optimal solution.
The thesis solves the TSP by combing k-opt and the branch and cut algorithm. The branching process splits original problem into a number of different sub-problems by k-opt based and a sub-problem constructed by smaller k-opt, will have a higher priority to solve. The solution of sub-problem may provide a better upper bound or fathom.
This study proposed algorithm can quickly find a new upper bound(better feasible solution), then the new upper bound can improve the computing time of the Branch and Cut. If the algorithm can quickly find a better feasible solution, enterprises can reduce costs early. However if the initial solution is an optimal solution, the algorithm in this paper has a worse computing time because it can’t find a better upper bound and spend a lot of time to conclude optimality.

1.Applegate, D., Bixby, R., Chvátal, V., and Cook, W. “The Traveling Salesman Problem.” Princeton University Press, 41 WilLiam Street, 2006.
2.Applegate, D., Bixby, R., Chvátal, V., Cook, W., Espinoza, D. G., Goycoolea M.,and Helsgaun K. “Certification of an optimal TSP tour through 85,900 cities” Operations Research Letters 37, 11-15, 2009
3.Bellmore, M., and Nemhauser, G. L. "The traveling salesman problem: A survey." Operations Research, 538-558, 1968.
4.Chvátal, V. “Edmonds polytopes and weakly hamiltonian graphs.” Mathematical Programming, 29-40, 1973.
5.Croes, G. A. "A method for solving traveling-salesman problems." Operations Research, 791-812, 1958.
6.Dantzig, G., Fulkerson, R., and Johnson, S. "Solution of a Large-Scale Traveling-Salesman Problem." Journal of the Operations Research Society of America, 393-410, 1954.
7.Dorigo, M., and Gambardella, L. M. "Ant Colony System: A Cooperative Learning Approach to the Traveling Salesman Problem." IEEE Transactions on Evolutionary Computation, 53-66, 1997.
8.Dorigo, M., and Gambardella, L. M. "Ant Colonies for the Traveling Salesman Problem." BioSystems, Vol. 43, 73-81, 1997.
9.Dorigo, M., Maniezzo, V., and Colomi, A. "Positive feedback as a search." Technical Report No. 91-016 Revised, Politecnico di Milano, Italy, 1991.
10.Eastman W. L. Linear Programming with Pattern Canstraints.” Ph.D. Thesis. Department of Economics, Harvard University, Cambridge,MAAxhusetts, USA., 1958.
11.Edmonds, J. “Maximum matching and a polyhedron with 0,1-vertices.” Journal of Research of the National Bureau of Standards 69B, 125-130, 1965.
12.Glover, F. "Future Path for Integer Programming and Links to Articial Intelligence." Computer and operation research, 533-549, 1986.
13.Golde, B. "A Statistical Approach to the TSP." Networks 7, 209-225, 1977.
14.Golden, B., Bodin, L., Doyle, T., and Jr, W. S. "Approximate Traveling Salesman Algorithms." Operations Research, 694-711, 1980.
15.Held, M., and Karp, R. M. "A Dynamic Programming Approach to Sequencing Problems." Journal of the Society for Industrial and Applied Mathematics, 196-210, 1962.
16.Held, M., and Karp, R. M. "The traveling-salesman problem and minimum spanning trees." Operations Research, 6-25, 1970.
17.Holland, J. H. "Adaption in Natural and Artificial System." The University Michigan Press, Ann Arbor, 1975.
18.Johnson, D. S. "Local optimization and the traveling salesman problem." Lecture Notes in Computer Science 443. Springer, Berlin, Germany, 446-461, 1990.
19.Karp, R. M. "Reducibility among combinatorialproblem." Complexity of Computer Computations, Plenum Press, 85-104, 1972.
20.Kirkpatrick, S., Gelatt, C. D., Jr., and Vecchi, M. P. "Optimization by simulated annealing." Science 13 May, 671-680, 1983.
21.Lin, S. “Computer solutions of the traveling salesman problem.” The Bell System Technical Journal, 2245-2269, 1965.
22.Little, J. D. C., Murty, K. G., Sweeney, D. W., and Karel, C. "An algorithm for the traveling salesman problem. " Operations Research, 972-989, 1963.
23.MacGregor, J. N., and Ormerod, T. "Human performance on the traveling salesman problem." Perception & Psychophysics, 527-539, 1996.
24.Martin, O. Otto S. W., Felten E. W. “Large-step Markov chains for the traveling salesman problem.” Coplex Systems 5, 299-326, 1991.
25.Miller, D. L., Pekny J. F. “Exact solution of large asymmetric traveling salesman problems.” Science 251, 754-761, 1991.
26.Padberg, M. W., and Hong, S. “On the symmetric traveling salesman problem: A computational study.” Mathematical Programming Study 12, 78-107, 1980.
27.Padberg, M., and Rinaldi, G. “A branch and cut algorithm for the resolution of large-scale symmetric traveling salesman problem” SIAM Review, 60-100, 1991.
28.Sakakibara, K. "New edges not used in shortest tours of TSP." European journal of operational research, 129-138, 1998.
29.Schrijver, A., Aardal, K., Nemhauser, G. L., and Weismantel, R. "On the History of Combinatorial Optimization (till 1960)," Handbook of Discrete Optimization, 2005.
30.Woeginger, G. "Exact Algorithms for NP-Hard Problems:A Survey." Lecture Notes in Computer Science, 185-207, 2003.
31.Takenaka, Y. and Funabiki, N. "An Improved Genetic Algorithm Using the Convex Hull for Traveling Salesman Problem." Transactions on Systems, Man, and Cybernetics, 2279-2284, 1998.