透過您的圖書館登入
IP:44.210.107.64
  • 學位論文

以複合啟發式演算法求解硬式時窗限制下車輛途程問題

A Meta-Heuristic Method for Vehicle Routing Problem with Hard Time Window Constraints

指導教授 : 陳建良
若您是本文的作者,可授權文章由華藝線上圖書館中協助推廣。

摘要


車輛途程問題(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.

參考文獻


Chen, J. C., Chen, C. S., Chen, B. J., Lay, M., Liu, L., Lee, B., Huang, S., Chang, W., Huang, D. (2001), “Application of Vehicle Routing Problem with Hard Time Window Constraints”, Proceedings of the 29th International Conference on Computers & Industrial Engineering, Montreal, Canada, pp. 533-538.
Ao, C. W. (1999), “A Tabu Search Heuristic for the Vehicle Routing Problem with Soft Time Window Constraints”, Master Thesis of Department of Industrial Engiveering and Management, Yuan Ze University, Taiwan.
Badeau, P., Guertin, F., Gendreau, M. J., Potvin, Y., Taillard, E. (1997), “A Parallel Tabu Serach Heuristic for the Vehicle Routing Problem with Time Windows”, Transportation Research 5 (2), pp. 109-122.
Bent, R. and Hentenryck, P. V. (2001), “A Two-Stage Hybrid Local Search for the Vehicle Routing Problem with Time Windows”, Technical Report CS-01-06, Department of Computer Science, Brown University.
Berger, J., Barkaoui, M. and Bräysy, O. (2001), “A Parallel Hybrid Genetic Algorithm for the Vehicle Routing Problem with Time Windows”, Working paper, Defense Research Establishment Valcartier, Canada.

被引用紀錄


李美儀(2015)。車輛路線相關問題之回顧與國內發展之分析〔碩士論文,國立交通大學〕。華藝線上圖書館。https://doi.org/10.6842%2fNCTU.2015.00488

延伸閱讀