GDA與RRT啟發式解法在VRP問題上之應用

Abstract

GDA與RRT啟發式解法在VRP問題上之應用研 究 生 ：陳國清 指導教授：韓復華國立交 通大學交通運輸研究所摘 要大洪水法(Great Deluge Algorithm, GDA) 與記錄更新法(Record to Record Travel, RRT)是Dueck在1993年發表的 新啟發式解題架構。兩種方法主要是由門檻接受法(ThresholdAccepting, TA)演變而來﹐為具有跳離局部最佳解(Local Optimum)機制的演算法。 GDA與RRT方法在國內外皆尚未應用於求解車輛路問題(Vehicle Routing Problem, VRP)上﹐本研究首度應用求解VRP問題﹐探討兩種方法之適用性 及解題績效。本研究根據GDA和RRT方法之解題概念並與傳統啟發式解發結 合後設計了求解之執行架構﹐並對所選擇之11題例題進行初步測試﹐結果 發現以11題平均而言GDA執行架構之解題精度誤差得2%至4%之間﹔而RRT執 行架構則在平均情況下解題精度誤差得12%以下。在追蹤RRT架構時發現﹐ 暫劣解擾動於固定的偏差值間﹐以致難以找到更好的記錄。為此﹐本研究 提出了改良式的RRT執行架構﹐即讓偏差率參數隨執行次數遞減﹐因此稱 之為偏差率遞減RRT－DDR執行架構。並以DDR架構對所選測試例題進行測 試﹐結果發現在沒有增加時間的情況下11題平均誤差可以改善到7%以下﹐ 明顯地改善了RRT之結果。本研究以GDA與DDR作為基本架構﹐策略性地組 合後提出兩階段與多階段組合型執行架構﹐主要目的在於在鄰域搜尋時考 慮其強化性﹐期在目前鄰域裡能更嚴密地找到好的解之外﹐亦考慮跳離目 前鄰域至另一鄰域﹐以避免陷入局部最佳解而預期找到全域最佳解。在兩 階段方面提出RWL-GDA､GDA/DDR與DDR/GDA三種執行架構﹐此部份屬於強 化策略。經初步測試後發現11題平均誤在3%左右﹐而以TSS為起始解所求 得之結果較以SSI之結果佳。在多階段方面本研究提出DG-FF-DG與GD-FF- DG兩種架構﹐包括著具有跳離觀念的兩極跳躍法。經初步測試後發現11題 平均誤在1.8%以下﹐而以TSS為起始解所求得之結果較以SSI之結果佳。本 研究再針對單純架構與兩階段架構所需之參數進行大規模測試﹐並對各種 執行架構提出最適參數範圍建議。本研究針對各階段之測試過程中求解得 各例題最佳個案結果進行比較﹐以十一題例題之個案最佳結果的平均誤差 而言兩階段組合型方法表現最好﹐平均誤差為0.17%﹔其餘依次為GDA､ DDR､多階段組合型方法以及RRT方法。然而若以解題效率與解題精度為指 標進行比較時在六組執行架構參數可併列為非劣解。依據此分析﹐建議在 實際應用時可按不同的要求(解題精度或效率)來選擇何種執行架構﹐如果 是講求解題效率則可考慮GDA和DDR架構﹐而若講求解題精度則可考慮多階 段組合型架構﹐兩階段架構則介於兩種之間。再將本研究所求得之最佳個 案結果與國際文獻之結果比較﹐在十一題例題中本研究有二題優於文獻已 知最佳結果､有三題與文獻已知最佳結果相同﹐得十一題例題平均誤 差0.06%﹐優於其他文獻。 Applications of Great Deluge Algorithm and Record to Record Travel Methods to Vehicle Routing ProblemStudent: Guo-Ching Chen Advisor: Anthony Fu-Wha Han Institute of Traffic and Transportation National Chiao Tung UniversityThe Great Deluge Algorithm (GDA) and Record to Record Travel (RRT) Methods aregeneric search heuristics algorithms presented by Dueck in 1993 for thesolution of the famous 442-citie TSP problem. These methods are similarto Threshold Accepting (TA) which is generally an improvement method forinitial solution and can avoid caving into local optimum. Though GDA andRRT were applied to TSP, they have not been applied to the Vehicle RoutingProblem (VRP). This research attempts to combine the use of GDA andRRT with the traditional exchange methods for solving Vehicle Routing Problem(VRP). A test bank of 11 benchmark VRP test problems from the TSPLIB wasselected for the evaluation of our developed methods. According to the concepts of GDA and RRT, we strategically combined thesemethods and developed eight implementation procedures which involveintensification and diversification strategies. These procedures are pureGDA and RRT; improved RRT method, Descending Deviation RRT (DDR); Reset WaterLevel GDA( RWL-GDA), GDA/DDR and DDR/GDA which are two phases structures andbelong to intensification strategy; DG-FF-DG and GD-FF-DG which aremulti-phase structures and belong to intensification and diversificationstrategies. Results show that the average deviations of 11 test problemsare all lower than 5%, hence these eight procedures are suitable for solvingVRP problem. We find that the average deviations of mulit-phase structuresare lower than 2%. It means that our hybrid strategies are robust. Comparewith the literature, 3 test problems are the same with the best knownresults and we have updated the best known solutions of 2 test problems,and the average deviation is 0.06%.