車輛途程問題(Vehicle Routing Problem)於學術研究上已被探討多年,在物流運輸應用領域亦扮演非常重要的角色。近年來,物流宅配業激烈的競爭與半導體、TFT-LCD製造廠對設備備份零件配送之時效性要求,促使具時窗限制之車輛途程問題(Vehicle Routing Problem with Time Window Constraints, VRPTW)在研究與應用上更趨重要。本研究首要目標為總車輛行走距離最小,以迅速回應 (Quick Response)顧客需求,次目標為配送車輛數最少以降低運輸成本,並以Solomon(1987)提出之56題國際題庫測試演算法績效。 VRP與VRPTW目前以啟發式演算法求解相關議題居多。啟發式搜尋法雖不能保證求得最佳解,但其具有求解快速且能求得最佳解之近似解的優點。本研究結合禁制搜尋法(Tabu Search, TS)、門檻接受法(Threshold Accepting, TA)與基因演算法(Genetic Algorithms, GAs),發展出新的複合型啟發式演算法,禁制門檻基因演算法(Tabu-Threshold Genetic Algorithm, TTGA),求解硬式時窗限制下車輛途程問題(Vehicle Routing Problem with Hard Time Window Constraints, VRPHTW)。本研究共分三階段,包含第一階段為起始解建構模組,應用時間導向最鄰近法快速求得初始解。第二階段為區域改善模組,應用車輛縮減模組以及傳統交換型演算法對初始解做粗略改善。第三階段為TTGA改善模組,針對求解品質做深度及廣度搜尋,以達到途程最佳化之目的。 本研究整理所得之最佳結果,與公布於Solomon網頁上的之已知最佳解比較,總平均行走距離誤差小於3.6%,車輛數誤差約為11.5%。
This research proposes a heuristic, Tabu-Threshold Genetic Algorithm (TTGA), to efficiently and effectively solve Vehicle Routing Problem with Hard Time Window Constraints (VRPHTW). TTGA integrates Tabu Search (TS), Threshold Accepting (TA) and Genetic Algorithms (GAs) that are the most popular generic heuristic in solving VRPHTW in recent years. The first objective is to determine the routes that minimize the total vehicle travel distances, and the second objective is to find the minimum required number of vehicles. Both objectives lead to quick response to satisfy customer demands and reduce the transportation cost. TTGA consists of three phases: initial solution construction, local search improvement, and generic search improvement. In the initial solution construction phase, enhanced Nearest Neighbor Method is used. In the local search improvement phase, vehicles reduction and Neighborhood Search modules are proposed. In the generic search improvement phase, a hybrid algorithm of TS, TA and GA is used to improve the current solution. TTGA results in good solution quality and efficiency. The average deviation of distance is less than 3.6% and the average deviation of the number of vehicles is about 11.5%, compared to the best known solutions of Solomon’s 56 benchmark instances.
為了持續優化網站功能與使用者體驗,本網站將Cookies分析技術用於網站營運、分析和個人化服務之目的。
若您繼續瀏覽本網站,即表示您同意本網站使用Cookies。