門檻接受法(threshold accepting, TA)源於模擬降溫法(simulated annealing, SA)，TA與SA均具有避免陷入局部解的特性，其不同處主要在TA改變SA機率性接受暫劣解的方 式為確定性的遞減門檻數列。國內外研究TA新方法的文獻尚不多見，目前僅見應用於旅行推 銷員問題(TSP)與若干工作排程的問題方面，本文係國內外文獻上首次將TA延伸應用於車輛路 線問題(VRP)上之研究。本文除詳細探討TA解題架構之設計與相關參數之選擇，並自國際電腦 網路題庫中選取１１題標竿測試例題（節點數自５１至２００點），在SUN SPARC 10工作站上 以Ｃ語言撰寫程式進行測試。測試結果發現，以修正之循序節省法求得起始解，採整合式執行 組合方式(2-exchange節線交換法加上1-1及1-2節點交換法)改善起始解，用長度為３０的梯狀 遞減門檻數列，在起始門檻值為０．２％時，１１個測試例題與文獻已知最佳結果之平均誤差 百分比為４．６４％，平均運算時間為１１５．１７ＣＰＵ秒。測試過程中，經由ＴＡ法對１ １個測試例題找到最好結果的平均誤差僅１．７１％，另對測試例題中最大規模的２００個節 點之例題(M-n200-k17.vrp)，更求得優於文獻已知最佳結果之突破性發現。

　　　　　Originating from the simulated annedling(SA)approach, threshold accapting (TA)is a new general purpose algorithm presented by Dueck and Scheuer in 1990 for the solution of combinatorial optimization problems. Threshold accepting is generally an improvement method for initial solution. While traditional exchange heuristic methods are limited to local search, TA can avoid caving into local optimum. For routing problems, Dueck and Scheuer had applied the TA method to the famous 442-cities TSP of Grotschel and reported better results than that obtained by SA. Recently, Han et al. has accomplished a comprehensive application analysis of TA over a test bank of 15 TSP problems from the TSPLIB. This research extends the applications of TA to VRP. There are 11 benchmark test problems with 51 to 200 nodes were selected from literature for our test. Results found that the overall average cost of the best results obtained by TA is even lower than that reported in existing literature. Moreover, among the 11 VRP test problems, this research using TA has updated the best known solution for the test problem M-n200-k17.vrp with 200 nodes.