以巨集啟發式方法求解多車種與週期性車輛路線問題之研究

Abstract

車輛路線相關問題（Vehicle Routing Related Problems, VRRP）在物流運輸之應用與研究領域中扮演相當重要的角色；隨著實務狀況與限制條件之不同，更衍生出許多複雜的應用類型。由於大多數VRRP的解題複雜度屬於NP-Hard，因此實務應用時大多採用能快速求解的啟發式方法，近年來更朝向巨集啟發式方法（Meta-heuristics）之發展。 本論文選擇VRRP當中較為困難的多車種車輛路線問題（Heterogeneous Fleet Vehicle Routing Problem, HVRP）與週期性車輛路線問題（Periodic Vehicle Routing Problem, PVRP）做為研究的對象，並發展一套可有效求解HVRP與PVRP之巨集啟發式方法及工具。本研究結合多種巨集啟發式方法的特性與優點，將接受劣解、變換鄰域、擾動成本與多重起點等巨集策略融合在深度搜尋與廣度搜尋的概念中，發展出一套「包容性深廣度搜尋（Generic Intensification and Diversification Search, GIDS）」的巨集啟發式方法。GIDS法共包含：(1) 多起始解構建（Multiple Initialization Constructor, MIC）、(2)深度化包容搜尋（Generic Search for Intensification, GSI）與(3) 廣度化擾動搜尋（Perturbation Search for Diversification, PSD）三個策略群組。整套GIDS法係以傳統鄰域搜尋為實際執行求解之工具，以深度搜尋之GSI群組為核心，再搭配廣度搜尋之PSD與MIC群組。此外，本研究更設計了五種模組來執行GIDS之策略群組：即在MIC群組構建有加權起始（Weighted Initialization, WI）模組與鄰域搜尋（Neighborhood Search, NS）模組；在GSI群組設計有G1與G2兩種包容搜尋（Generic Search）模組；在PSD群組中則構建有成本擾動（Cost Perturbation, CP）模組。 為檢視新提出之GIDS巨集啟發式方法在HVRP與PVRP應用上的適用性與發展潛力，本研究以實驗設計的理念配合選取若干國際標竿測試例題來進行平均狀況分析，並藉由撰寫電腦執行程式及測試國際標竿例題，與國內外文獻發表之最佳已知解（Best Known Solution）進行比較分析。歸納本論文之具體研究成果如下： 1. 在方法架構方面，GIDS法具有以下三項優點：(1) 不需要記憶結構，因此節省電腦的記憶體空間，可加快運算速度；(2) 控制參數少，參數設定容易；(3) 模組組合與執行方式更具有彈性，應用到不同的VRRP問題時，可以很快地設計出適當的解題架構。 2. 在例題測試方面，GIDS找到六題PVRP例題新的最佳紀錄；無論是HVRP或PVRP，GIDS的最佳解與文獻已知最佳解的平均誤差分別為0.58%與0.26%。 總而言之，GIDS的解題績效並不亞於國際文獻報導的數個績效最佳之方法，而且對控制參數之設定值較不敏感，證明GIDS法不僅適合求解VRRP這類複雜的問題，也是一個有效、穩健（Robust）且具有應用潛力的一個巨集啟發式方法。

The Heterogeneous Fleet Vehicle Routing Problem (HVRP) and Periodic Vehicle Routing Problem (PVRP) are two important variants of the conventional vehicle routing problem (VRP). Due to the NP-hard complexity of HVRP and PVRP, most existing methods for solving HVRP and PVRP are heuristics or metaheuristics. The major contribution of this research is that we have developed a new metaheuristic approach, i.e. the Generic Intensification and Diversification Search (GIDS), for solving HVRP and PVRP. The GIDS integrates the use of some recently developed generic search methods such as Threshold Accepting (TA) and Great Deluge Algorithm (GDA), and the meta-strategies of intensification and diversification for intelligent search. The GIDS includes three components: Multiple Initialization Constructor (MIC), Generic Search for Intensification (GSI), and Perturbation Search for Diversification (PSD). We also designed five modules and proposed several modified algorithms for the implementation of the GIDS to HVRP and PVRP. As compared with the well-known tabu search, GIDS shares some similar ideas in the search strategies of intensification and diversification but does not require complicated memory scheme for computer implementation. Both HVRP and PVRP benchmark instances were selected and tested by several different implementations of GIDS. The numbers of benchmark instances tested for HVRP and PVRP are twenty and thirty-two respectively. All programs were coded in UNIX C and ran on a SUN SPARC 10 workstation. Computational results are very encouraging; GIDS yielded comparable results with recent successful applications using the tabu search. Using GIDS, we have updated the best-known solutions for six of the PVRP instances. Moreover, for PVRP, the average deviation of our best solutions from the published best-known solutions is merely 0.26 %. For HVRP, the average deviation of our best solutions from the published best-known solutions is 0.58%. Such results imply that GIDS may provide an efficient and robust tool for real-world HVRP and PVRP applications.