月旦知識庫
 
  1. 熱門:
 
首頁 臺灣期刊   法律   公行政治   醫事相關   財經   社會學   教育   其他 大陸期刊   核心   重要期刊 DOI文章
運輸學刊 本站僅提供期刊文獻檢索。
  【月旦知識庫】是否收錄該篇全文,敬請【登入】查詢為準。
最新【購點活動】


篇名
門檻接受法、噪音擾動法與搜尋空間平滑法在車輛路線問題之應用研究與比較分析
並列篇名
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.
起訖頁 113-143
關鍵詞 車輛路線問題門檻接受法噪音擾動法搜尋空間平滑法Vehicle Routing Problem(VRP)Threshold Accepting(TA)Noising Method(NM)Search Space Smoothing(SSS)
刊名 運輸學刊  
期數 199609 (9:3期)
出版單位 中華民國運輸學會
該期刊-上一篇 模糊型動態用路人最佳化變動需求/出發時間/路徑選擇模型暨演算法
 

新書閱讀



最新影音


優惠活動




讀者服務專線:+886-2-23756688 傳真:+886-2-23318496
地址:臺北市館前路28 號 7 樓 客服信箱
Copyright © 元照出版 All rights reserved. 版權所有,禁止轉貼節錄