(3.238.96.184) 您好!臺灣時間:2021/05/08 20:20
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

我願授權國圖
: 
twitterline
研究生:陳契伸
研究生(外文):Chi-Shen Chen
論文名稱:硬性/軟性時窗限制之車輛途程問題研究
論文名稱(外文):Vehicle Routing Problem with Hard/Soft Time Window Constraints
指導教授:陳建良陳建良引用關係
指導教授(外文):James C. Chen
學位類別:碩士
校院名稱:中原大學
系所名稱:工業工程研究所
學門:工程學門
學類:工業工程學類
論文種類:學術論文
論文出版年:2001
畢業學年度:89
語文別:中文
論文頁數:62
中文關鍵詞:門檻接受法禁制搜尋法時窗限制車輛途程問題禁制門檻法
外文關鍵詞:TSTATTAVRPHTWVRPSTW
相關次數:
  • 被引用被引用:33
  • 點閱點閱:408
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:1
本研究結合禁制搜尋法 (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.
英文摘要 ii
誌謝 iii
目錄 iv
表目錄 vi
圖目錄 vii
摘要 1
1.緒論 2
2.文獻探討 4
2.1 VRP與VRPTW求解方法 4
2.1.1 初始解法 5
2.1.2 傳統交換改善方法 5
2.1.3 一般性搜尋法 6
2.2 相關文獻探討 8
2.2.1 國外文獻彙整 8
2.2.2 國內文獻彙整 9
3.研究方法 13
3.1 研究範圍與假設 13
3.2 模式建構 13
3.3 方法架構 16
3.4 VRPHTW 16
3.4.1 初始解建構 16
3.4.2 區域改善模組 18
3.4.3 禁制門檻法 19
3.5 VRPSTW 21
3.5.1 初始解建構 21
3.5.2 區域改善模組與禁制門檻法 22
4.例題測試與實驗設計 23
4.1 測試題庫與最佳解 23
4.2 初始解設計與測試 23
4.2.1 節省法 23
4.2.2 最鄰近法 24
4.3 TTA參數設計 25
4.4 最佳結果比較分析 32
5.結論與建議 36
5.1 結論 36
5.2 未來研究方向 37
參考文獻 38
附錄 43
附錄1 VRP與VRPTW示意圖 43
附錄2 近年國外研究VRPTW相關文獻 44
附錄3 國內研究VRP及VRPTW相關文獻 46
附錄4 節省法流程圖 50
附錄5 最鄰近法流程圖 51
附錄6 TTA流程圖 52
附錄7 文獻分析統計資訊 53
附錄8 Solomon題庫目前已知最佳解 54
附錄9 程式執行畫面 56
附錄10 初始解折線圖 58
附錄11 本研究最佳結果 60
作者簡歷 62
1. 王木坤,「時間限制條件下配銷系統路徑與途程問題之研究」,中原大學工業工程研究 所碩士論文,19972. 申生元,「時窗限制車輛途程問題」,交通大學工業工程與管理研究所博士論文,19993. 杜世文,「多目標與模糊時窗貨物配送啟發式解法之研究」,交通大學交通運輸研究所 碩士論文,19924. 李玉雯,「求解在軟性時窗限制下醫院運輸部門車輛途程問題之研究—以遺傳演算法求 解」,成功大學工業管理研究所碩士論文,20005. 李洪鑫,「含時間窗車輛途程問題各演算法適用範圍之探討」,東海大學工業工程研究 所碩士論文,20006. 吳亮瑩,「單一物流中心配送車輛途程問題之研究—以遺傳演算法求解」,成功大學工 業管理研究所碩士論文,19997. 吳致昀,「多車次車輛路線問題之研究」,成功大學工業管理研究所碩士論文,20008. 吳泰熙、黃金智、楊懿淑,「以禁忌搜尋演算法求解確定型及隨機型多車種車輛途程問 題」,工業工程學刊,第18卷,第2期,20019. 林宏勳,「節線排程問題路線改善方法之研究」,交通大學土木工程研究所碩士論文, 199510. 林修竹,「包容性啟發式解法在VRPTW問題上之應用」,交通大學交通運輸研究所碩士 論文,199911. 林書銘,「禁制搜尋法於含時窗與裝載限制車輛途程問題解算之研究」,元智大學工業 工程研究所碩士論文,199812. 林崑隆,「交通擁塞與時間窗口限制下車輛派送問題之啟發式解法」,中央大學工業管 理研究所碩士論文,199613. 易德華,「軟時窗車輛巡迴問題之研究」,中央大學土木工程研究所碩士論文,199814. 徐明輝,「多部車一般性車輛途程解算法之研究」,元智大學工業工程研究所碩士論 文,199715. 莊志諒,「配送網路之設計研究」,交通大學交通運輸研究所碩士論文,198816. 陳正元,「節省法與路線間交換改善法在車輛路線問題 (VRP) 上之應用」,交通大學 土木工程研究所碩士論文,199217. 陳功欽,「一般性車輛途程問題之探討」,元智大學工業工程研究所碩士論文,199618. 陳志騰,「多車型具時間窗限制之車輛途程演算法介紹」,機械工業雜誌,199919. 陳坤賓,「模擬退火演算法應用於車輛途程規問題之研究」,元智大學工業工程研究所 碩士論文,199820. 陳國清,「GDA與RRT啟發式解法在VRP問題上之應用」,交通大學交通運輸研究所碩士 論文,199821. 敖君瑋,「禁制搜尋法於軟性時窗限制之車輛途程問題研究」,元智大學工業工程研究 所碩士論文,199922. 張有恆,「儲運管理」,華泰書局出版,199523. 黃珈昇,「物流體系中貨櫃運送車輛途程規劃問題之探討」,中原大學工業工程研究所 碩士論文,199624. 黃冠華,「遺傳演算法於時窗限制下多車種車輛途程問題之應用」,東海大學工業工程 研究所碩士論文,199925. 曾維豪,「軟性時窗與回程撿收之車輛途程問題研究」,元智大學工業工程研究所碩士 論文,200026. 楊智凱,「以門檻接受法改善TSP及VRP路網成本之研究」,交通大學土木工程研究所碩 士論文,199527. 廖亮富,「含時窗限制多部車車輛途程問題解算之研究」,元智大學工業工程研究所碩 士論文,199828. 廖韋翔,「應用門檻值接受法之多目標車輛路徑規劃」,雲林科技大學工業工程與管理 技術研究所碩士論文,199829. 韓復華、楊智凱、卓裕仁,「應用門檻接受法求解車輛路線問題之研究」,運輸計劃季 刊,第26卷,第二期,253-280,199730. 顏成佑,「基因演算法解算軟性時窗車輛途程問題之研究」,元智大學工業工程研究所 碩士論文,200031. P. Badeau, F. Guertin, M. Gendreau, J. Y. Potvin, E. Taillard, “A Parallel Tabu Serach Heuristic for the Vehicle Routing Problem with Time Windows”, Transportation Research 5:2, 109-122, 199732. M. Baker, J. Sheasby, “Extensions to the Generalised Assignment Heuristic for Vehicle Routing”, European Journal of Operational Research 119, 147- 157, 199933. L. Bodin, B. L. Golden, A. Assad, M. Ball, “Routing and Scheduling of Vehicle and Crew: The State of Art”, Special Issue of Computers and Operations Research 10:2, 63-211, 198334. J. Brandao, A. Mercer, “A Tabu Search Algorithm for the Multi-Trip Vehicle Routing and Scheduling Problem”, European Journal of Operational Research 100, 180-191, 199735. X. Chen, W. Wan, X. Xu, “Modeling Rolling Batch Planning as Vehicle Routing Problem with Time Windows”, Computers and Operations Research 25, 390-400, 199836. W. C. Chiang, R. A. Russell, “Simulated Annealing Metaheuristics for the Vehicle Routing Problem with Time Windows”, Annals of Operations Research 63, 3-27, 199637. W. C. Chiang, R. A. Russell, “A Reactive Tabu Search Metaheuristic for the Vehicle Routing Problem with Time Windows”, Informs Journal on Computing 9:4, 417-430, 199738. A. J. Chin, H. W. Kit, A. Lim, “A New GA Approach for Vehicle Routing Problem”, Proceedings of IEEE International Conference on Tools with Artificial Intelligence, 307-310, 199939. G. Clerk, J. W. Wright, “Scheduling of Vehicles from a Central Depot to a Number of Delivery Points”, Operations Research 12:4, 568-581, 196440. G. Desaulniers, J. Lavigne, F. Soumis, “Multi-Depot vehicle Scheduling Problems with Time Windows and Waiting Costs”, European Journal of Operational Research 111, 479-494, 199841. G. Dueck, T. Scheuer, “Threshold Accepting: A General Purpose Optimization Algorithm Appearing Superior to Simulated Annealing”, Journal of Computational Physics 90, 161-175, 199042. C. Duhamel, J. V. Potvin, J. M. Rousseau, “A Tabu Search Heuristic for the Vehicle Routing Problem with Backhauls and Time Windows”, Transportation Science 31:1, 49-59, 199743. M. Filipec, D. Skrlec, S. Krajcar, “An Efficient Implementation of Genetic Algorithms for Constrained Vehicle Routing Problem”, IEEE International Conference on Systems, Man, and Cybernetics 3, 2231-2236, 199844. F. Glover, “Tabu Search-Part I”, ORSA Journal on Computing 13, 190-206, 198945. F. Glover, “Tabu Thresholding: Improved Search by Nonmonotonic Trajectories”, ORSA Journal on Computing 7:4, 426-442, 199546. B. L. Golden, G. Laporte, E. D. Taillard, “An Adaptive Memory Heuristic for a Class of Vehicle Routing Problems with MinMax Objective”, Computers and Operations Research 24, 445-452, 199747. S. C. Hong, Y. B. Park, “A Heuristic for Bi-Objective Vehicle Routing with Time Window Constraints”, International Journal of Production Economics 62, 249-258, 199948. W. R. Jin, J. Y. Hsu, “Dynamic Vehicle Routing Using Hybrid Genetic Algorithms”, IEEE Proceedings of International Conference on Robotics & Automation 1, 453-458, 199949. H. Kim, Y. Hayashi, K. Nara, “An Algorithm for Thermal Unit Maintenance Scheduling Through Combined Use of GA SA and TS”, IEEE Transactions on Power Systems 12:1, 199750. F. H. F. Liu, S. Y. Shen, “A Route-Neighborhood-Based Metaheuristic for Vehicle Routing Problem with Time Windows”, European Journal of Operational Research 118, 485-504, 199951. S. J. Louis, X. Yin, Z. Y. Yuan,”Multiple Vehicle Routing with Time Windows Using Genetic Algorithms”, IEEE Proceedings of the 1999 Congress on Evolutionary Computation 3, 199952. A. H. Mantawy, L. Abdel-Magid, Z. Selim, “A New Simulated Annealing-Based Tabu Search Algorithm for Unit Commitment”, IEEE International Conference on Computational Cybernetics and Simulation 3, 2432-2437, 199753. W. P. Nanry, J. W. Barnes, “Solving the Pickup and Delivery Problem with Time Windows Using Reactive Tabu Search”, Transportation Research Part B 34, 107-121, 200054. I. H. Osman, “Metastrategy Simulated Annealing and Tabu Search Algorithms for the Vehicle Routing Problem”, Annals of Operations Research 41, 421- 451, 199355. J. S. Pan, Z. M. Lu, S. C. Chu, S. H. Sun, “Non-redundant VQ Channel Coding Using Modified Tabu Search Approach with Simulated Annealing”, IEEE Third International Conference on Knowledge-Based Intelligent Information Engineering Systems, 242-245, 199956. J. Y. Potvin, S. Bengio, “The Vehicle Routing Problem with Time Windows PartⅡ: Genetic Search”, Informs Journal on Computing 8:2, 165-172, 199657. J. Y. Potvin, T. Kervahut, B. L. Garcia, J. M. Rousseau, “The Vehicle Routing Problem with Time Windows Part I: Tabu Search”, Informs Journal on Computing 8:2, 158-164, 199658. J. Y. Potvin, J. M. Rousseau, “A Parallel Route Building Algorithm for the Vehicle Routing and Scheduling Problem with Time Windows”, European Journal of Operational Research 66, 331-340, 199359. S. Salhi, G. K. Rand, “Incorporating Vehicle Routing into the Vehicle Fleet Composition Problem”, European Journal of Operational Research 66, 313-330, 199360. M. M. Solomon, “Algorithms for The Vehicle Routing and Scheduling Problems with Time Window Constraints”, Operation Research 35:2, 254-265, 198761. E. Taillard, P. Badeau, M. Gendreau, F. Guertin, J. Y. Potvin, “A Tabu Search Heuristic for the Vehicle Routing Problem with Soft Time Windows”, Transportation Science 31:2, 170-186, 199762. P. M. Thompson, H. Psaraftis, “Cyclic Transfer Algorithms for Multi- Vehicle Routing and Scheduling Problems”, Operations Research 41, 935-946, 199363. P. Toth, D. Vigo, “A Heuristic Algorithm for the Symmetric and Asymmetric Vehicle Routing Problems with Backhauls”, European Journal of Operational Research 113, 528-543, 199964. V. Valls, R. Marti, P. Lino, “A Tabu Thresholding Algorithm for Arc Crossing Minimization in Bipartite Graphs”, Annals of Operations Research 63, 233-251, 199665. N. Yoshiike, Y. Takefuji, “Vehicle Routing Problem Using Clustering Algorithm by Maximum Neural Networks”, IEEE Proceedings of the Second International Conference on Intelligent Proceeing and Manufacturing of Materials 2, 1109-1113, 1999
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
系統版面圖檔 系統版面圖檔