一個結合貪婪法與二元優化法之創新技術用以解決旅行銷售

Solving Traveling Salesman Problem by Hybridization of Greedy and 2-OPT Techniques

江耀(Chiang, Yao)

指導教授 ： 蔡正發

國立屏東科技大學/管理學院/資訊管理系所/碩士(2016年)

摘要

本論文提出一個結合了貪婪法與二元優化法的創新性啟發式演算法用以解決旅行銷售者問題。本技術首先運用二元優化演算法產生一組不錯的初始路徑，再透過隨機選取與貪婪選取兩個改良策略，用以不斷的改善舊有路徑直到完成所設定之終止條件。
本論文之實驗結果顯示，所提之GR-2OPT啟發式演算法在求解旅行銷售者問題方面的表現，比其他知名演算法更具效能與效率，並可能是目前現有之同性質演算法中表現最好的一個。

關鍵字

組合優化問題 ； 旅行銷售者問題 ； 啓發式演算法 ； 二元優化演算法

並列摘要

This thesis presents a new metaheuristic algorithm called GR-2opt, that hybridizes the greedy algorithm and the 2-opt method for solving the traveling salesman problem (TSP). The proposed algorithm integrates an excellent strategy for interactively improving the candidate solution. To validate the proposed approach, various simulations are conducted to compare the proposed algorithm with numerous well-known approaches, utilizing a range of TSP benchmark problems. Based on the results of the simulations, GR-2opt solves the traveling salesman problem significantly more effectively than other schemes. Notably, the proposed method yields an excellent solution within a very short time. As our best knowledge, the proposed TSP technique may be one of the best methods in the world currently.

並列關鍵字

Combinatorial optimization problem ； Traveling salesman problem ； Metaheuristic algorithm ； 2-opt

參考文獻

[1] M. Dorigo, “Ant system: optimization by a colony of cooperating agents,” IEEE Transactions on Systems, Man, and Cybernetics, Vol. 26, No. 1, pp. 29-41, 1996.

[2] Z. A. Aziz, “Ant Colony Hyper-heuristics for Travelling Salesman Problem,” Procedia Computer Science, Vol. 76, pp. 534-538, 2015.

[3] F. Glover, “Applications of Integer ProgrammingFuture paths for integer programming and links to artificial intelligence,” Computers & Operations Research, Vol. 13, No. 5, pp. 533-549, 1986.

[4] D. S. W. Lai, O. Caliskan Demirag, J. M. Y. Leung, “A tabu search heuristic for the heterogeneous vehicle routing problem on a multigraph,” Transportation Research Part E: Logistics and Transportation Review, Vol. 86, pp. 32-52, 2016.

[5] S. Kirkpatrick, “Optimization by Simulated Annealing,” Science, Vol. 220, No. 4598, pp. 671-680, 1983.