| 摘要: | 組合最佳化問題中，旅行銷售員問題(Traveling Salesman Problem, TSP)是最基本且典型的例子，許多問題都可以轉變成TSP的形式求解，又由於TSP是屬於NP-Complete問題，在資料量龐大的情況之下無法找出最佳解，所以又有將大型TSP變換成數個小型TSP的分群旅行銷售員問題(Clustered Traveling Salesman Problem, CTSP)的研究提出。所以，如何設計一個良好的演算法，使得我們能夠能找出近似最佳解變得相當重要。因此，本研究提出以基因演算法及塔布搜尋法為核心的演算架構，並將TSP問題轉為CTSP問題型式，以期能找出近似最佳解。
本研究所提出的演算架構分為二個部分，第一部分為分群及群路建立，第二部分為全域最佳路徑搜尋。分群為階層式，由上而下分群，首先將頂點做初步分群，完成後再將每一群分為若干子群並建立群路路徑。第二部分的全域最佳路徑，搜尋方法採用塔布搜尋法，首先使用雙點式塔布搜尋做大範圍的路徑搜尋，接著使用單點式塔布搜尋做細部改善，最後使用MNIO演算法將解收斂。在TSPLIB國際範例korA100中，基因演算法所得的路徑長度比最佳解長5.27%，本研究只多出2.46%；在d198中，基因演算法的路徑長度比最佳解多出5.96%，本研究只多出3.44%；而在rat783中，基因演算法的路徑長度比最佳解多出10.52%，本研究只多出8.72%。因此可以看出，本研究所提出的演算法能比單純使用基因演算法有更好的路徑搜尋結果。
In the combinatorial optimization problem, Traveling Salesman Problem is the most basic and typical example, lots of problems could transfer to TSP as solution. Meanwhile, as the TSP belongs to NP-Complete problem, it is quite hard to find out the best solution in case of huge data, the CTSP, Clustered Traveling Salesman Problem, transferred from a big TSP into several smaller ones, came up. Therefore, it becomes highly important to define a good algorithm in order to find the best similar solution. In consequence, this research proposes an algorithm; the cadre is based on genetic algorithm and tabu search, and transfer the TSP problem into CTSP to find out the best similar solution.
In this research, the algorithm is divided into two parts: the first one on the cluster path, second on the global best path search. The cluster is top- down; at the beginning making the preliminary cluster on the top, then set up the path. The second part, adopting the tabu search: firstly by using the two-points tabu search as large boundary, then by one point tabu search for detail, finally by using MNIO algorithm for the final solution. In TSPLIB international exemplification linkorA100, the path of genetic algorithm is 5.27% longer than the best solution, in this research only 2.46% longer; in the d198, the path of genetic algorithm is 5.96% longer than the best solution, in this research 3.44% only; as for the rat783, the path of genetic algorithm is 10.52% longer than the best solution, here only longer than 8.72%. Therefore, the algorithm of this research can get a better path research result than by using uniquely the genetic algorithm. |
