硬性/軟性時窗限制之車輛途程問題研究

Vehicle Routing Problem with Hard/Soft Time Window Constraints

陳契伸(Chi-Shen Chen)

指導教授 ： 陳建良

中原大學/工學院/工業工程研究所/碩士(2001年)

https://doi.org/10.6840/cycu200100262

摘要

本研究結合禁制搜尋法 (Tabu Search, TS) 與門檻接受法 (Threshold Accepting, TA) ，發展出新的禁制門檻法 (Tabu-Threshold Algorithm, TTA) ，並放寬一般VRP中每個需求點只能經過一次的限制條件，求解硬性 (Hard) / 軟性 (Soft) 時窗限制之車輛途程問題 (Vehicle Routing Problem with Hard/Soft Time Window Constraints, VRPHTW / VRPSTW) 。首要目標求總車輛行走距離最小，次目標為求配送車輛數最少，並以Solomon (1987) 之56題國際題庫測試績效。
車輛途程問題 (Vehicle Routing Problem, VRP) 在學術上已被討論多年，然而因實務上有許多複雜的限制條件，且VRP求解複雜度高，一般動輒數小時的求解時間，在實務上難以實際應用。以半導體業為例，晶圓廠產能昂貴，其時窗要求也相對嚴謹，因此迅速回應 (Quick Response) 顧客需求以提高服務水準(較短的行走距離) 比降低運輸成本 (較少的配送車輛數) 更為重要。
本研究架構主要包含起始解建構、區域改善模組以及TTA改善模組三部分。起始解建構應用節省法、最鄰近法求得；區域改善模組應用車輛縮減模組以及簡單的鄰域交換法；TTA改善模組則應用途程內、途程間兩階段交換改善法。
本研究以Visual Basic 6.0撰寫程式，執行環境為PⅢ550 PC。測試結果顯示TTA求解效果及效率良好。相較於初始解平均總距離改善率為26%，車輛數改善率為14%，平均每題執行時間約300秒。
本研究整理各組合所得之最佳結果，平均距離與收集之目前已知最佳解誤差小於5%，車輛數誤差約為8%，結果並與其他國際知名文獻比較。

關鍵字

門檻接受法 ； 禁制搜尋法 ； 時窗限制 ； 車輛途程問題 ； 禁制門檻法

並列摘要

This research proposes a heuristic, Tabu-Threshold Algorithm (TTA), to efficiently and effectively solve Vehicle Routing Problem with Hard/Soft Time Window Constraints (VRPHTW / VRPSTW). TTA integrates Tabu Search (TS) and Threshold Accepting (TA), two of the most popular generic heuristics in solving VRPHTW in recent years. The first objective is to determine the route that minimizes the total vehicle travel distances. This, in turn, leads to quick response to customer demands. The second objective is to find the minimum required number of vehicles. This, in turn, results in low transportation cost. Solomon’s 56 benchmark instances were tested for TTA.
TTA consists of three phases: initial solution construction, local search improvement, and generic search improvement. In the initial solution construction phase, Enhanced Savings Method and Nearest Neighbor Method are 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 and TA is used to improve the initial solution. TTA is coded in Visual Basic 6.0 and evaluated at a PentiumⅢ550 PC.
TTA results in good solution quality and efficiency. The average deviation of distance is less than 5% and the average deviation of vehicle numbers is about 8%, compared to the known “best” solutions. The average computation time is approximately 5 minutes to solve all the instances.

並列關鍵字

TS ； TA ； TTA ； VRPHTW ； VRPSTW

參考文獻

1. 王木坤，「時間限制條件下配銷系統路徑與途程問題之研究」，中原大學工業工程研究

29. 韓復華、楊智凱、卓裕仁，「應用門檻接受法求解車輛路線問題之研究」，運輸計劃季

11. 林書銘，「禁制搜尋法於含時窗與裝載限制車輛途程問題解算之研究」，元智大學工業

14. 徐明輝，「多部車一般性車輛途程解算法之研究」，元智大學工業工程研究所碩士論

17. 陳功欽，「一般性車輛途程問題之探討」，元智大學工業工程研究所碩士論文，1996