Abstract
旅行推銷員問題是一典型的組合最佳化問題, 由於此問題應用在實際生活中的情形處之可見, 因而使得這方面的研究益發受人重視。然而由於此問題本身的特性, 使得在處理較大問題時, 迄今尚無一種方法能保證在求得近似最佳解的時候, 同時有一合理的計算時間。本文的研究即針對了這方面的問題, 在仍然能獲得一不錯的精確度的情況下, 計算時間卻能大量地減少了。文中, 我們首先利用了圓環插入法如何減少計算時間的觀念, 針對其現有的缺點稍加修正之後, 從而發展出一新的方法- 凸緣法, 亦即利用凸緣的特性及限制, 使得在處理問題的時候, 除了可獲致極佳的精確度之外,同時將計算時間減至最低。從經濟上的觀點來看, 花費在計算機上的成本, 也因而得以大量地降低了。