Solving the Traveling Salesman Problem by k-opt based Branch and Cut
| Autor: | Wen-YiLiu, 劉文義 |
|---|---|
| Rok vydání: | 2010 |
| Druh dokumentu: | 學位論文 ; thesis |
| Popis: | 98 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. |
| Databáze: | Networked Digital Library of Theses & Dissertations |
| Externí odkaz: |
|