以門檻接受法改善TSP及VRP路網成本之研究

Abstract

門檻接受法（Threshold Accepting, TA）是 Dueck 與 Scheuer 在1990年發表的一個新的啟發式解題架構。TA基本上是改善起始解的交換 法，傳統的交換型啟發式解法只侷限於區域搜尋，而TA則具有避免陷入區 域解(Local optimum)的特性。 TA新方法國內外的研究尚不多見，在排程 問題( Routing Problem)只有一題，初步結果發現有優於模擬降溫法( Simulated Annealing, SA)的跡象。本研究除詳細探討如何將TA應用於求 解 TSP之外，並首度嘗試將該方法延伸應用於求解VRP。本研究測試的TSP 例題有13題，取自國際網路(Internet)公開之題庫TSPLIB，節點數自42 至442點；VRP測試例題有11題，節點數自 51至200 點。測試例題是在 SUN SPARC 10工作站上進行。測試結果發現，TA架構的啟發式解法精確度 優於大部分傳統的交換型啟發式解法。在TSP方面，以最遠插入法求得起 始解，以起始路線成本的0.5％作為起始門檻、用長度 30的線性遞減門檻 數列、採用2-opt加上Or-opt作為核心方法改善起始解，結果13題測試例 題與國際題庫現有最佳解之平均誤差僅為1.80％，平均CPU時間每題9.842 秒。 在VRP方面，以循序解省法求得起始解，以起始路線成本的0.2％作 為起始門檻、 用長度為30的梯狀遞減門檻數列、採用 2-opt加上一對一 及一對二節點交換法改善起始解，結果11題測試例題與國際題庫現有最佳 解之平均誤差為2.796％，平均CPU時間每題115.17秒。另在 11題VRP測試 例題之中，有 4題經由本研究之TA法求得優於國際題庫現有最佳解之突破 性結果。 Threshold accepting(TA) is a new general purpose algorithm presented by Dueck and Scheuer in 1990 for the solution of combinatorial optimization problems. This new method is even simpler structures than the well-known simulated annealing (SA) approach. While traditional exchange heuristic methods that were limit to local search, TA method can avoid caving into local optimum. We have studied the threshold sequence of TA on TSP, and we have generalized TA to VRP. While the earlier Dueck and Scheuer study reported only one test problem result of Grotschel's 442-cities TSP , this research attempts to apply TA more comprehensively to a set of TSP and VRP test problems. TSP has 13 test problems with 42 to 442 nodes selected from TSPLIB. VRP has 11 test problems with 51 to 200 nodes selected from literature. The average deviation from the best available solutions of 13 TSP test problem is only 1.80%; the average CPU time is 9.842 seconds. For VRP, the average deviation from the best available solutions of the 11 test problems is 2.796%, and the average CPU time is 115.17 seconds. Most of all, amount the 11 VRP test problems, this research using TA has updated the best available solutions of 4 test problems.