跳到主要內容

臺灣博碩士論文加值系統

(44.210.132.31) 您好!臺灣時間:2022/08/19 18:42
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

: 
twitterline
研究生:鄭超元
研究生(外文):Chau Yuan Jeng
論文名稱:考慮時窗限制之多車種零擔貨運車輛途程問題
指導教授:朱經武朱經武引用關係
指導教授(外文):Ching-Wu Chu
學位類別:碩士
校院名稱:國立海洋大學
系所名稱:航運管理學系碩士在職專班
學門:運輸服務學門
學類:運輸管理學類
論文種類:學術論文
論文出版年:2002
畢業學年度:90
語文別:中文
論文頁數:95
中文關鍵詞:車輛途程問題時窗限制硬性時窗軟性時窗減少車輛
外文關鍵詞:Vehicle Routing ProblemTime Window ConstraintsVehicle Routing Problem with Hard Time Window ConstraintsVehicle Routing Problem with Soft Time Window ConstraintsReduction
相關次數:
  • 被引用被引用:20
  • 點閱點閱:712
  • 評分評分:
  • 下載下載:171
  • 收藏至我的研究室書目清單書目收藏:2
摘 要
車輛途程問題(Vehicle Routing Problem, VRP)研究在學術上已被討論多年,但大多假設只擁有單一車種,然而在現實生活中有許多複雜的限制條件,如道路狀況、車流狀況、貨品特性、顧客需求等因素,配送所使用的車輛卻不只一種,因此如何決定車輛大小是否符合客戶之需求將是一個相當複雜的問題。
本研究之主要研究目的為探討硬性時窗限制之多車種車輛途程問題,構建一有效率之啟發式演算法,協助管理者規劃路線、降低運輸成本。
本研究之啟發式演算法,包含三部份:首先採用修正節省法,建構起初解;其次再以減少車輛模組,縮減起初解之車輛數目;最後再以鄰域改善模組求解,以期使總路線距離縮短。鄰域改善模組中所採用的方法為傳統的路線內及路線間節點交換。
本研究以C++語言撰寫程式,執行環境為Pentium Ⅲ 800MHz PC。由求解過程,本研究發現在少數測試題目中,鄰域改善模組確實發揮其改善總行駛距離之功能。本研究之最佳結果與國際著名之文獻比較,除C1類題在總車輛數方面表現最佳,均求得最佳車數,其餘表現並不突出。與目前已知最佳車數與行駛距離誤差約維持在20%以
內。雖然本研究所構建之演算法,主要構想為處理多車種之問題,並非針對同一車種設計,但執行結果並不理想為事實。
探究其原因,由於使用傳統之啟發式方法易陷入局部最佳解而無法跳離。建議未來宜結合人工智慧搜尋法 ,如禁制搜尋法(Tabu Search, TS)以便找出更好的解答。
Abstract
The Vehicle Routing problem has been an intensive research area during the past several decades, but typically it has been assumed that there is only one type of vehicle involved. In fact, there are many complicated factors to be considered, such as whether highways or downtown streets are employed, the traffic flow, the characteristic of the goods, customer demand, and many others. How to select an appropriate type of vehicle to meet customer needs is a rather complicated problem.
The main purpose of this study is to discuss the vehicle routing problem with hard time windows (VRPHTW), and to develop an efficient algorithm to assist managers with route planning and to reduce transportation costs. The heuristic algorithm developed in this study includes three parts: first, a revised savings algorithm is used to build up an initial solution; second, a reduction modular is implemented to reduce the total number of vehicles; third, the classical route improvement heuristic is used to shorten the distance of all routes.
Our algorithm was programmed in C++ language, and run on a Pentium Ⅲ 800MHz PC. Computational testing on 56 benchmark problems by Solomon has shown that the overall solution quality of our algorithm is not competitive with all existing heuristics. In general, the percent of error possible between the optimum number of vehicles and the distance is within about 20%.
Due to the use of the traditional heuristic algorithm, the results cannot avoid being only a local optimum. It is suggested that the future research be combined with artificial intelligence, such as TS (Tabu Search) and, TA (Threshold Accepting), in order to achieve better results.
目 錄
謝詞
摘要‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧ Ⅰ
目錄‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧ Ⅴ
圖目錄‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧ Ⅶ
表目錄‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧ Ⅷ
第一章 緒論
1.1研究動機與目的‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧ 1
1.2問題敘述與研究範圍假設‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧ 2
1.3研究方法與流程‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧ 3
1.4研究內容與項目‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧ 4
第二章 文獻回顧
2.1緒論‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧ 6
2.2多車種車輛途程問題‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧ 7
2.3具時窗限制車輛途程問題‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧ 11
2.3.1國外文獻彙整‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧ 12
2.3.2國內文獻彙整‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧ 17
第三章 模式建構
3.1最佳解-整數規劃模式‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧ 23
3.2 啟發式解-修正節省法‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧ 26
3.2.1起初解構建‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧ 27
3.2.2減少車輛模組‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧ 28
3.2.3鄰域改善模組‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧ 29
第四章 範例測試
4.1 範例產生與測試題庫‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧ 34
4.2 測試結果‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧ 45
第五章 結論與建議
5.1結論‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧ 50
5.2建議‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧ 50
參考文獻‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧ 52
附錄‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧ 59
一、中文部份
1. 王木坤(1997),「時間限制條件下配銷系統路徑與途程問題之研究」,中原大學工業工程研究所碩士論文。
2. 申生元(1999),「時窗限制車輛途程問題」,交通大學工業工程與管理研究所博士論文。
3. 李玉雯(2000),「求解在軟性時窗限制下醫院運輸部門車輛途程問題之研究-以遺傳演算法求解」,成功大學工業管理研究所碩士論文。
4. 李洪鑫(2000),「含時窗車輛途程問題各演算法適用範圍之探討」,東海大學工業工程研究所碩士論文。
5. 杜世文(1992),「多目標與模糊時窗貨物配送啟發式解法之研究」,交通大學交通運輸研究所碩士論文。
6. 林修竹(1999),「包容性啟發式解法在VRPTW問題上之應用」,交通大學交通運輸研究所碩士論文。
7. 林崑隆(1996),「交通擁塞與時間窗口限制下車輛派送問題之啟發式解法」,中央大學工業管理研究所碩士論文。
8. 林書銘(1998),「禁制搜尋法於含時窗與裝載限制車輛途成問題解算之研究」,元智大學工業工程研究所碩士論文。
9. 周蘇江(2001),「含時窗限制的動態車輛途程問題之研究」,中原大學工業工程研究所碩士論文。
10. 吳致昀(2000),「多車次車輛路線問題之研究」,成功大學工業管理研究所碩士論文。
11. 易德華(1998),「軟時窗車輛巡迴問題之研究」,中央大學土木工程研究所碩士論文。
12. 敖君璋(1999),「禁制搜尋法於軟性時窗限制之車輛途程問題研究」,元智大學工業工程研究所碩士論文。
13. 梅明德 (1994),「地理資訊系統輔助物流中心即時配送系統之研究」, 中央大學土木工程研究所運工組碩士論文。
14. 黃冠華(1999),「遺傳演算法於時窗限制下多車種車輛途程問題之應用」,東海大學工業工程研究所碩士論文。
15. 陳正元(1992),「節省法與路線間交換改善法在車輛路線問題(VRP)上之應用」,國立交通大學土木工程研究所碩士論文。
16. 陳春益 (1993),「兩階式分解演算法應用於隨機動態多型式運具調度模式之研究」,運輸計劃季刊,第22卷,第1期,頁1-33。
17. 陳春益 (1996),「國內物流中心配送系統之探討」,運輸學刊,第九卷,第一期,頁65-80。
18. 陳煌儒 (1996),「企業運輸配送問題暨模式探討」,黎明學報,第10卷,第1期,頁117-123。
19. 陳契伸(2001),「硬性/軟性時窗限制之車輛途程問題研究」,中原大學工業工程研究所碩士論文。
20. 陳國清(1998),「GDA與RRT啟發式解法在VRP問題上之應用」,交通大學交通運輸研究所碩士論文。
21. 陳志騰(1999),「多車型具時間窗限制之車輛途程演算法介紹」,機械工業雜誌。
22. 陳坤賓(1998),「模擬退火演算法應用於車輛途程規問題之研究」,元智大學工業工程研究所碩士論文。
23. 莊志諒(1988),「配送網路之設計研究」,交通大學交通運輸研究所碩士論文。
24. 張學孔 (1994),「先進大眾運輸使用者即時資訊系統技術評估之研究」,國立台灣大學土木工程研究所執行。
25. 張祖明 (1994),「多車種車輛路線問題啟發式解法之研究」,國立交通大學土木工程研究所碩士論文。
26. 張志榮(2000),「整合自有車隊或選擇貨運公司服務與車輛運送路線問題」,國立台灣海洋大學航運管理研究所碩士論文。
27. 曾維豪(2000),「軟性時窗與回程撿收之車輛途程問題研究」,元智大學工業工程研究所碩士論文。
28. 楊智凱(1995),「以門檻接受法改善TSP及VRP路網成本之研究」,交通大學土木工程研究所碩士論文。
29. 廖韋翔(1998),「應用門檻值接受法之多目標車輛路徑規劃」,雲林科技大學工業工程與管理技術研究所碩士論文。
30. 廖亮富(1998),「含時窗限制多部車車輛途程問題解算之研究」,元智大學工業工程研究所碩士論文。
31. 韓復華、楊智凱、卓裕仁(1997),「應用門檻值接受法求解車輛路線問題之研究」,運輸計畫季刊,第26卷,第二期,253-280。
32. 顏成佑(2000),「基因演算法解算軟性時窗車輛途程問題之研究」,元智大學工業工程研究所碩士論文。
二、英文部份
1. Ballou, R. H., (1990), “A continued comparison of several popular algorithm for vehicle routing and scheduling”, Journal of Business logistics, Vol. 11, No. 1, pp. 111-126.
2. Bodin, L. and Golden, B. and Assad, A. and Ball, M., (1983), “Routing and Scheduling of Vehicles and Crews, the state of the art”, Computers & Operations Research, special issue, Vol. 10, No. 2, pp. 63-211.
3. Ball, M. O. and Magnanti, T. L. and Monma, C. L. and Nemhauser, G. L., (1995), “Network Routing”, Handbooks in Operations Research and Management Science, Vol. 8, Elsevier Science B. V., The Netherlands.
4. Ballou, R. H. and Agarwal, Y. K., (1988), “A performance comparison of several popular algorithms for vehicle routing and scheduling”, Journal of Business logistics, Vol. 9, No. 1, pp. 51-65.
5. Bodin, L. D., (1990), “Twenty years of routing and scheduling, Operations Research”, Vol. 38, No. 4, pp. 571-579.
6. Brandao, J. and Mercer, A., (1997), “A Tabu Search Algorithm for the Multi-Trip Vehicle Routing and Scheduling Problem”, European Journal of Operational Research,Vol. 100, pp. 180-191.
7. Badeau, P. and Guertin, F. and Gendreau, M. and Potivn, J. Y. and Taillard, E., (1997), “A Parallel Tabu Serach Heuristic for the Vehicle Routing Problem with Time Windows”, Transportation Reserch, Vol. 5, No. 2, pp. 109-122.
8. Baker, M. and Sheasby, J., (1999), “Extensions to the Generalised Assignment Heuristic for Vehicle Routing”, European Journal of Operational Research, Vol. 119, pp. 147-157.
9. Chin, A. J. and Kit, H. W. and Lim, A., (1999), “A New GA Approach for Vehicle Routing Problem”, Proceedings of IEEEE Interational Conference on Tools with Artificial Intellingence, pp. 307-310.
10. Chiang, W. C. and Russell, R. A., (1997), “A Reactive Tabu Search Metaheuristic for the Vehicle Routing Problem with Time Windows”, Informs Journal on Computing, Vol. 9, No. 4, pp. 417-430.
11. Chiang, W. C. and Russel, R. A., (1996), “Simulated Annealing Metaheuristics for the Vehicle Routing Problem with Time Windows”, Annals of Operations Research Vol. 63, pp. 3-27.
12. Chen, X. and Wan, W. and Xu, X., (1998), “Modeling Rolling Batch Planning as Vehicle Routing Problem with Time Windows”, Computers and Operations Research Vol.25, pp.390-400.
13. Clarke, G. and Wright, J. W., (1964), “Scheduling of Vehicles form a Central Depot to a Number of Delivery Points”, Operations Research, Vol. 12, No. 4, pp. 568-581.
14. Desrochers, M. and Verhoog, T. W., (1991), “A New Heuristic For The Fleet Size And MixVehicle Routimg Problem”, Comput. & Ops Res, Vol. 18, No. 3, pp. 263-274.
15. Desaulniers, G. and Lavigne, J. and Soumis, F., (1998), “Multi-Deopt vehicle Scheduling Probiem with Time Windows and Waiting Costs”, European Journal of Operational Research, Vol. 111, pp. 479-494.
16. Duhamel, C. and Potvin, J. V. and Rousseau, J. M., (1997), “A Tabu Search Heuristic for the Vehicle Routing Problem with Backhauls and Time Windows”, Transportation Science, Vol.31, No.1, pp. 49-59.
17. Filipec, M. and Skrlec, D. and Krajcar, S., (1998), “An Effcient Implementation of Genetic Algorithms for Constrained Vehicle Routing Problem”, IEEEE International Conference on Systems, Man, and Cybernetics, Vol.3, pp.2231-2236.
18. Glover, F., (1995), “Tabu Thresholding: Improved Search by Nonmonotonic Trajectories”, ORSA Journal on Computing, Vol.7, No.4, pp.426-442.
19. Golden, B. and Assad, A. L. and Levy, and Gheysens, F. , (1984), “The Fleet Size And Mix Vehicle Routing Problem”, Comput. & Ops Res, Vol 11, No 1, pp. 49-66.
20. Golden, B. L. and Assad, A. A., (1988), “Elsevier Science Publishers, North-Holland”, Vehicle Routing: Methods and Studies.
21. Golden, B. and Bodin, L. and Aassd, A. and Ball, M., (1983). “Routung and Scheduling of Vehicle and Crew: The State of Art”, Special Issue of Computers and Operations Research, Vol. 10, No. 2, pp. 63-211.
22. Gheysens, F. and Golen, B. and Assad, A., (1984), “A Comparison Of Techniques For Solving The Fleet Size And Mix Vehicle Routing Problem”, OR Spektrum, Vol. 6, pp. 207-216.
23. Golden, B. L. and Laporte, G. and Taillard, E. D., (1997), “An Adaptive Memory Heuristic for a Class of Vehicle Routing Problems with MinMax Objective”, Computers and Operations Research, Vol. 24, pp. 445-452.
24. Hong, S. C. and Park, Y. B., (1999), “A Heuristic for Bi-Objective Vehicle Routing with Time Window Constraints”, Interational Journal of Production Economics, Vol. 62, pp. 249-258.
25. Jin, W. R. and Hsu, J. Y., (1999), “Dynamic Vehicle Routing Using Hybrid Genetic Algorithms”, IEEEE Proceedings of International Conference on Robotics&Automation, Vol. 1, pp.453-458.
26. Liu, F. H. F. and Shen, S. Y., (1999,) “A Route-Neighborhood-Based Metaheuristic for Vehicle Routing Problem with Time Windows”, European Journal of Operational Research, Vol.118, pp.485-504.
27. Laporte, G., (1992), “The vehicle routing problem: an overview of exact and approximate algorithms”, European Journal of Operational Research, Vol. 59, pp. 345-358.
28. Laporte, G. and Osman, I. H., (Eds.), (1996), “Baltzer Science Publications, The Netherlands” , Metaheuristics in Combinatorial Optimization, Annals of Operations Research, Vol. 63, pp.233-251.
29. Laporte, G. and Osman, I. H., (1995), “Routing problems: A bibliography”, Annals of Operations Research, Vol. 61, pp. 227-262.
30. Liu, F. H. F. and Shen, S. Y., (1999), “A Route-Neighborhood-Based Metaheuristic for Vehicle Routing Problem with Time Windows”, European Journal of Operational Research, Vol.18, pp.485-504.
31. Louis, S. J. and Yin, X. and Yuan, Z. Y., (1999), “Multiple Vehicle Routing with Time Windows Using Genetic Algorithms”, IEEEE Proceedings of the 1999 Congress on Evolutionary Computation 3.
32. Nanry, W. P. and Barnes, J. W., (2000), “Solving the Pickup and Delivery Problem with Time Windows Using Reactive Tabu Search”, Transportation Research Part, Vol.B 34, pp. 107-121.
33. Or, I. (1976), “Traveling Salesman-type Combinatorial Problems and Their Relation to the Logistics of Regional Blood Banking”, Ph.D. Dissertation, Northwestern University.
34. Osman, I. H. (1993), “Metastrategy Simulated Annealing and Tabu Search Algorithms for the Vehicle Routing Problem”, Annals of Operations Research, Vol. 41, pp. 421-451.
35. Potvin, J. Y. and Bengio, S., (1996), “The Vehicle Routing Problem with Time Windows Part :Genetic Search”, Informs Journal on Computing Vol. 8, No. 2, pp. 165-172.
36. Potvin, J. Y. and Kervahut, T. and Garcia, B. L. and Rousseau, J. M., (1996), “The Vehicle Routing Problem with Time Windows Part I:Tabu Search”, Informs Journal on Computing, Vol. 8, No. 2, pp. 158-164.
37. Salhi, S. and Rand, G. K., (1993), “Incorporating Vehicle Routing Into The Vehicle Fleet Composition Problem”, European Journal of Operational Ressearch, Vol. 66, pp. 313-330.
38. Solomon, M. M., (1987), “Algorithms for The Vehicle Routing and Scheduling Problems with Time Window Constraints”, Operation Researsch Vol. 35, No. 2, pp. 254-265.
39. Taillard, E. and Badeau, P. and Gendreau, M. and Guertin, F. and Potvin, J. Y., (1997), “ A Tabu Search Heuristic for the Vehicle Routing Problem with Soft Time Windows”, Transportation Science Vol. 31, No. 2, pp. 170-186.
40. Thompson, P. M. and Psaraftis, H., (1993), “Cyclic Transfer Algorithms for Multi-Vehicle Routing and Scheduling Problems”, Operations Research, Vol. 41, pp. 935-946.
41. Toth, P. and Vigo, D., (1999), “A Heuristic Algorithm for the Symmetric and Asymmetric Vehicle Routing Problems with Backhauls”, European Lournal of Operational Research, Vol. 113, pp. 528-543.
42. Valls, V. and Marti, R. and Lino, P., (1996), “A Tabu Thresholding Algorithm for Arc Crossing Minimization in Bipartite Graphs”, Annals of Operations Research, Vol. 63, pp. 233-251.
43. Yoshiike, N. and Takefuji, Y., (1999), “Vehicle Routing Problem Using Clustering Algorithm by Maximum Neural Networks”, IEEE Proceedings of the Second International Conference on Intelligent Proceeing and Manufacturing of Materials, Vol. 2, pp. 1109-1113.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top