以禁忌搜尋法則求解推銷員旅行問題

A Tabu Search Heuristic for the Traveling Salesman Problem

吳泰熙(Tai-Hsi Wu) ； 張欽智(Chin-Chih Chang)

《大葉學報》 6卷1期 (1997/12) Pp. 87-99

https://doi.org/10.7119/JDYU.199712.0087

摘要

推銷員旅行問題（traveling salesman problem；TSP），是組合最佳化問題中最具代表性之一種，通常不易在一合理的時間之內應用傳統之數學規劃法求得最佳解，因此一般皆採行能迅速求得近似最佳解的啟發式（heuristics）解法。禁忌搜尋法（tabu search；TS）是一種高階的萬用啟發式方法（meta-heuristic），專門用來解決組合最佳化的問題。此方法透過彈性記憶體之運用，故常常能跳脫區域最佳解（local optimal），且能在一合理的時間之內求得一近似（或最佳）解。有鑑於此，本研究採用途徑建構法以獲得TSP初始路徑，然後利用禁忌搜尋法進行路徑改善，以獲得一近似（或最佳）巡迴路徑。在禁忌搜尋法中，不同的參數設定將會影響演算法的精度及效度，因此本研究針對禁忌搜尋演算法執行中系統參數進行實驗設計以找出較佳參數組合，冀望能發展一較有效率且更切合實際應用之禁忌搜尋演算法以求解TSP問題。

關鍵字

推銷員旅行問題 ； 禁忌搜尋法則 ； 啟發式解法

並列摘要

This paper proposes a tabu search heuristic for solving the well known traveling salesman problem (TSP). In this research, tabu search is used to improve the initial solutions suggested from literature. A full factorial design is performed to find the best parameters setting for the tabu search heuristic. Computational experience on standard test problems is discussed and comparisons with some published solutions are provided.

並列關鍵字

traveling salesman problem ； tabu search heuristic