查詢結果分析
來源資料
頁籤選單縮合
題 名 | 應用門檻接受法求解車輛路線問題之研究=Applications of Threshold Accepting Method to Vehicle Routing Problem |
---|---|
作 者 | 韓復華; 楊智凱; 卓裕仁; | 書刊名 | 運輸計劃 |
卷 期 | 26:2 1997.06[民86.06] |
頁 次 | 頁253-280 |
分類號 | 557.81 |
關鍵詞 | 車輛路線問題; 門檻接受法; 啟發式解法; Vehicle routing problem; VRP; Threshold accepting algorithm; Heuristics; |
語 文 | 中文(Chinese) |
中文摘要 | 門檻接受法(threshold accepting, TA)源於模擬降溫法(simulated annealing, SA),TA與SA均具有避免陷入局部解的特性,其不同處主要在TA改變SA機率性接受暫劣解的方 式為確定性的遞減門檻數列。國內外研究TA新方法的文獻尚不多見,目前僅見應用於旅行推 銷員問題(TSP)與若干工作排程的問題方面,本文係國內外文獻上首次將TA延伸應用於車輛路 線問題(VRP)上之研究。本文除詳細探討TA解題架構之設計與相關參數之選擇,並自國際電腦 網路題庫中選取11題標竿測試例題(節點數自51至200點),在SUN SPARC 10工作站上 以C語言撰寫程式進行測試。測試結果發現,以修正之循序節省法求得起始解,採整合式執行 組合方式(2-exchange節線交換法加上1-1及1-2節點交換法)改善起始解,用長度為30的梯狀 遞減門檻數列,在起始門檻值為0.2%時,11個測試例題與文獻已知最佳結果之平均誤差 百分比為4.64%,平均運算時間為115.17CPU秒。測試過程中,經由TA法對1 1個測試例題找到最好結果的平均誤差僅1.71%,另對測試例題中最大規模的200個節 點之例題(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. |
本系統中英文摘要資訊取自各篇刊載內容。