包容性啟發式解法在VRPTW問題上之應用

Abstract

門檻接受法(Threshold Accepting, TA)與大洪水法(Great Deluge Algorithm, GDA)為90年代初新發展之巨集啟發式法(Metaheuristics)，皆具有跳離局部最佳解(Local Optimum)機制。目前在國內外皆尚未應用於求解時間窗車輛路線問題(Vehicle Routing Problem with Time Windows, VRPTW)，本研究首度應用TA及GDA，結合傳統交換法，設計多套解題模組以求解VRPTW之問題，並選擇Solomon之56題標竿題庫測試例題進行測試與績效比較。 本研究之巨集啟發式解法包括局部解構建程序與包容性改善程序兩部分。局部解構建程序包括起始解模組與鄰域搜尋模組，起始解模組包括循序節省插入法(SSI)、循序構建法(SC)以及綜合構建法(MC)；鄰域搜尋模組包括Reduction模組、路線內2-exch節線交換模組、路線間1-0及1-1節點交換模組。在包容性改善程序方面，本研究設計兩種架構G1及G2，配合兩種搜尋方法TA及GDA，提出四種包容性搜尋模組G1(TA)、G1(GDA)、G2(TA)及G2(GDA)。測試結果發現以SC為起始解經過G2(GDA)模組改善後所得結果最佳，平均車輛數誤差及距離誤差為(0.53, 7.79%)。測試結果顯示，局部解構建程序之結果經過包容性改善程序之後能夠明顯降低車輛數誤差及距離誤差，提高解題精確度。本研究發現採用GDA包容性演算解法之解題精確度比TA包容性演算法高，但相對其執行時間也明顯較長。 本研究整理各解題模組所得之最佳結果，56題例題中有一題(r210)突破文獻已知最佳解，車輛數3輛與文獻最佳解相同，距離成本為950.86較文獻已知最佳解966.25改善1.59%；有八題與文獻已知最佳結果相同；另有八題之車輛數誤差多1輛，但距離成本低於文獻已知最佳解。平均而言，56題例題之個案最佳結果之車輛數誤差為0.20輛，距離誤差為2.10%。本論文為國內外首次應用TA與GDA求解VRPTW問題之研究，現有結果與國際文獻其他方法比較，僅略遜於Chiang and Russell[14]與Taillard et al.[38]之Tabu Search法，但優於Potvin and Bengio[31]之Tabu Search法與Chiang and Russell[13]之Simulated Annealing法；本研究限於時間尚未及深入探討參數與組合細節，後續應仍有改善空間。

The Threshold Accepting (TA) and Great Deluge Algorithm (GDA) metaheuristics which were developed in early 90's have not been applied to the Vehicle Routing Problem with Time Windows (VRPTW). This research integrated the implementation techniques of traditional local search algorithms with the search strategies of TA and GDA to solve the VRPTW. A bank of Solomon's 56 benchmark instances was utilized for analyzing the efficiency and the accuracy of our developed methods. The main framework of our generic heuristics consists of local solution constructor and generic search for intensification. In the local solution constructor, we design two implementation modules: initial solution and neighborhood search. In the generic search for intensification, generic search one (G1) and generic search two (G2) were designed to combine with generic search heuristics such as TA and GDA. All of the implementation modules were coded in UNIX C language and executed at a Pentium-pro 180 PC. We have updated the best known solutions for 1 of the 56 benchmark instances. The average deviation of vehicles required is 0.20, and the average deviation of distance is 2.10%. This thesis represents a first-time application of TA and GDA to solve VRPTW in the world. While the current results are encouraging, there should be more room for further improvement of our application framework. Discussions of future research are discussed.