求解車輛途程問題的仿水流演算法

Abstract

仿水流演算法是一新興啟發式演算法，仿效水流在地理空間逐步流向最低點的特性，將代理人模擬成水流在解空間中搜尋最佳解。仿水流演算法模仿水流的分流和匯流特性，動態調整代理人數量，有效集中或分散搜尋。亦模仿水流蒸發和降水特性使搜尋能有機會從區域最佳解中跳脫。本研究承襲求解連續優化問題的仿水流演算法架構，提出求解車輛途程問題的仿水流演算法。在仿水流演算法的演算程序規範下，規劃符合車輛途程問題的解編碼法。在此編碼格式下，設計初始解產生法作為演算初始，並依循分流移步、匯流、蒸發、和降水等作業進行演化。為驗證本研究所提的初始解產生法和仿水流演算法成效，以THE VRP WEB內的標竿問題為測試對象。本研究所提的初始解產生法與節省演算法、掃描演算法、和樹狀搜尋法等傳統啟發式演算法比較，結果不相上下。本研究所提的初始解產生法搭配2-opt區域搜尋法後，和輔以2-opt區域搜尋的貪婪搜尋法比較，在大多數問題的求解結果均明顯較佳。本研究研擬的求解車輛途程問題的仿水流演算法和粒子群演算法比較，在相同目標函數呼叫次數下，仿水流演算法在小規模問題的求解表現較佳，但整體而言在不同規模問題的表現不如粒子群演算法穩定。

Water Flow-like Algorithm, WFA, is a newly developed heuristic algorithm, which simulates a solution searching agent as a water flow traversing the lowest point of a terrain. The number of water flows is dynamically changed while water flows split into subflows against rough terrain and merge several flows into single flow. Flow splitting and merging are mimicked by the WFA to conduct efficient optimum search in the solution space. In addition, evaporation and precipitation are simulated in WFA to search outside the local optima or to broaden searching area. This thesis presents a WFA for solving capacitated vehicle routing problems, WFA4VRP, based on WFA for solving continuous optimization problems. Under the WFA computation structure, this thesis presents two solution representations and designs initialization method followed by flow-splitting, merging, evaporation, and precipitation. Several benchmark problems from THE VRPWEB are used to test proposed initialization method and WFA4VRP. The performance of proposed initialization method is about the same as those of savings algorithm, sweep algorithm, and tree search. And the performance of proposed initialization method with 2-opt local search performs better than that of greedy search with 2-opt local search in most benchmark problems. As to the result of WFA4VRP, numerical tests show that WFA4VRP performs better than Particle Swarm Optimization, PSO, in small-scaled benchmark problems under the same call-objective-function times. However, PSO performs steadier than WFA in all benchmark problems.