藉由改進旅途片段來尋找旅行推銷員問題的近似解

旅行推銷員問題由來已久，一直是各界熱衷的研究項目，但也因為屬於NP-Hard的問題，當節點數量過多時，程式通常無法有效率地完成。本篇論文提出一種解決旅行推銷員問題的啟發式演算法。在此演算法中，我們先藉由貪婪演算法找出一個合法的路徑，並使用2-opt與3-opt的方法初步改進此路徑；接著將此路徑分割成數個子路徑，再對各個子路徑做動態規劃，找出各子路徑之局部最佳解，並重新連接成一條新的完整路徑。最後新得之路徑分成數個群組，根據這些群組分割做動態規劃，以縮短路徑長度。

關鍵字

旅行推銷員問題

並列摘要

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).

並列關鍵字

TSP

參考文獻

[1] Bellman, R. (1960), "Combinatorial Processes and Dynamic Programming", in Bellman, R., Hall, M., Jr. (eds.), Combinatorial Analysis, Proceedings of Symposia in Applied Mathematics 10,, American Mathematical Society, pp. 217–249.

[2] Bellman, R. (1962), "Dynamic Programming Treatment of the Travelling Salesman Problem", J. Assoc. Comput. Mach., 9, pp. 61–63

[4] G.B. Dantzig, R. Fulkerson, and S. M. Johnson, “Solution of a large-scale traveling salesman problem,” Operations Research 2 (1954), pp. 393-410

[5] S. Lin and B. W. Kernighan, (197 3) “An Effective Heuristic Algorithm for the Traveling Salesman Problem,” Operations Research, vol. 21, pp. 498-516. .

[6] W. Cook, D. Applegate, A. Rohe. (1999) “Chained Lin-Kernighan for large traveling salesman problems.” Research Institute for Discrete Mathematics Report 99887,

國際替代計量

藉由改進旅途片段來尋找旅行推銷員問題的近似解

全文下載

主題瀏覽