門檻接受法、噪音擾動法與搜尋空間平滑法在車輛路線問題之應用研究與比較分析

Applications of Threshold Accepting, Noising Method and Search Space Smoothing on the Vehicle Routing Problem

本研究採用新近發展的門檻接受法(Threshold Accepting,TA)、噪音擾動法制oising Method,NM)與搜尋空間平滑法(Search Space Smoothing,SSS)等AI啟發式演算法，並結合傳統交換型演算法，設計多種解題方法求解車輛路線問題(Vehicle Routing Problem,VRP)。本研究設TA VRP、NM VRP與SSS VRP三種解題程序，並選擇11個國際標竿題庫VRP例題，以C語言撰寫電腦程式，在SUN SPARC 10工作站上進行測試。就各方法在11個測試例題所求得最佳個案的結果與已知最佳解的平均誤差而言:TA.VRP為1.19%NM VRP為3.89%SSS VRP為210%。另與現有文獻方法比較發現，本研究設計方法之精確度雖尚不如禁制搜尋(Tabu Search);去，但執行時間較快;TA_VRP之結果已優於模擬鍛鍊(Simulated Annealing)j去。

This research combined the use of artificial intelligent (AI) algorithms and traditional exchange methods for solving the Vehicle Routing Problem (VRP). We considered three generic AI methods, inc1uding Threshold Accepting (TA), Noising Method (NM) and Search Space Smoothing (SSS) method, as the solution modules in our research. A test bank of 11 benchmark VRP instances from the TSPLffi was selected for the evaluation of our developed methods Considering different parameter settings, we developed three implementation procedures for TA, NM and SSS methods to VRP: TA_ VRP, NM_ VRP and SSS_ VRP. The average accuracy deviation from the best known solutions ofthe 11 tested problems for our developed heuristic methods are: 1.19% for T A _ VRP, 3.89% for NM_ VRP and 2.10% for SSS_ VRP. At this stage, TA seems to yield better average performance than SSS and NM. Among the 11 problems we tested, six problems were also tested by other researchers using different heuristic methods such as TabuSearch (TS) and Simulated Annealing (SA). We also compared TA, NM, and SSS with TS and SA based on the resu1ts ofthose six test problems which provides a common base for comparison. A1though the hybrid heuristics reported in this paper cannot outperform the Tabu Search method, the computation time of our proposed hybrid heuristics is much faster. The implementation efficiency ofthe TA_ VRP, NM_ VRP and SSS_ VRP implies that they could provide useful tools for real-world applications of VRP and other related problems.