跳到主要內容

臺灣博碩士論文加值系統

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

詳目顯示

: 
twitterline
研究生:歐陽昆
研究生(外文):Ou Yang Kun
論文名稱:線上型派車系統應用於路線貨運業車輛派遣作業之研究
論文名稱(外文):The Development of A On-Line System in Solving the Vehicle spatching problem of Fixed-Route Trucking Carriers
指導教授:施武榮施武榮引用關係
學位類別:碩士
校院名稱:南台科技大學
系所名稱:工業管理研究所
學門:商業及管理學門
學類:其他商業及管理學類
論文種類:學術論文
論文出版年:2007
畢業學年度:95
語文別:中文
論文頁數:108
中文關鍵詞:車輛途程問題具時窗限制多場站車輛途程基因演算法時間導向最鄰近搜尋法
外文關鍵詞:Vehicle Routing ProblemMulti-Depot Vehicle Routing Problem with Time WindowsGenetic AlgorithmNearest-Neighbor Search Heuristic
相關次數:
  • 被引用被引用:7
  • 點閱點閱:536
  • 評分評分:
  • 下載下載:152
  • 收藏至我的研究室書目清單書目收藏:0
隨著企業國際化之趨勢,許多商品的行銷通路產生改革,有別於傳統的行銷通路需透過層層轉運,目前的商品配送已經逐漸走向「少量、多樣化、高效率」的趨勢,故路線貨運業如何提升競爭力、降低運輸成本,遂成為重要目標之一。本研究針對個案公司實際狀況考量,探討多場站車輛途程問題,其特性包含車輛的承載、派車數量、路線的規劃、時窗限制等。由於此類問題是具有多重限制的NP-hard問題,若要求取最佳解,其計算時間會隨著場站數的增加呈現指數的成長,因此問題規模大時求取最佳解往往相當費時,故通常要求盡可能接近最佳解就可行。為兼顧實務上之求解速度與品質,本研究採用啟發式解法求解近似最佳解。本研究運用混合基因演算法來求解多場站車輛途程問題,協助個案公司能快速地處理派車問題。此演算法先探討如何以先分群再指派場站,然後利用時間導向最鄰近搜尋法建構初始解以快速求得可行解,接續運用基因演算法的尋優特性來改善求解品質,並讓求得之可行解能跳脫區域最佳解的限制,以增加全域最佳解的機會。本研究並依此建構一線上型車輛派遣運作系統,期望在此系統下能提高求解效率及較佳搜尋路線,並以傳統啟發使演算法比較,經測試結果證明,本研究所提出之混合基因演算法,確實具有較佳求解能力,使整體配送成本降低、效益增大。
With the business trends toward the globalization, the marketing channels, differed from the traditional ways, have reformed. Today, the way of product delivery has been toward the trend of wide variety, few amount and high efficiency. In this research, an empirical vehicle routing case is addressed for a transportation company. In the case, the research considers the characteristics of vehicle routing, quantity dispatch, routes arrangement, and Time-window constraints in order to reduce the transportation cost. A hybrid heuristic algorithm was used in solving this practical problem. The developed algorithm firstly employed the Nearest-Neighbor search heuristic to search the feasible solution based on the constraints of Time-window and loading capacity. By the virtue of Genetic Algorithm to improve the quality of the initial solutions, the developed algorithm then enables the solutions to jump out the local optimization and gain a better performance in product delivering. A web-based vehicle routing system which is integrated with the developed algorithm is also developed to assist engineering in configuring the appropriate vehicle routing and dispatching operations. The result has shown that the developed hybrid genetic algorithm method can actually achieve a better solution capability and reduce the transportation cost for the company.
摘要 i
Abstract ii
致謝 iii
目錄 iv
表目錄 vi
圖目錄 vii
第一章 緒論 1
1.1研究背景與動機 1
1.2研究目的 2
1.3 研究範圍 2
1.4研究步驟與流程 6
第二章 文獻回顧 9
2.1車輛途程問題(Vehicle Routing Problem, VRP) 9
2.1.1多場站車輛途程之介紹 12
2.1.2具時窗限制車輛途程之介紹 14
2.1.3具時窗限制之多場站車輛途程之介紹 15
2.2車輛途程求解策略演進 15
2.3簡單啟發式演算法 18
2.4基因演算法 20
2.5小結 28
第三章 研究方法 30
3.1基本假設及限制條件 30
3.2問題模式 31
3.2.1符號與參數說明 31
3.2.2數學模式建構及說明 32
3.3演算法之建構 33
3.3.1場站指派之建構 34
3.3.2時間導向最鄰近搜尋法之建構 35
3.3.3基因演算法之建構 39
第四章 系統建構及實證 45
4.1系統架構 45
4.1.1使用者需求分析 46
4.1.2系統參數設定 46
4.1.3資料輸入 47
4.1.4細部模組設定 49
4.1.5系統實證說明 50
4.2執行結果分析 59
第五章結論與建議 62
5.1結論 62
5.2研究貢獻 63
5.3未來研究方向及建議 64
參考文獻 66
附錄 70
參考文獻
郎茂祥,2006,「多配送中心車輛調度問題的模型與算法研究」,交通運輸系統工程與訊息,第六卷,第五期,65-69。
張靖、卓裕仁、藍宜祥,2005,「改良型巢狀分割法應用於旅行推銷員問題之研究」,運輸計畫季刊,第三十四卷,第四期,549-574。
莊貿凱,2005,「派車專家-車輛途程分析系統應用於零擔貨運業」,南台科技大學工業管理所碩士論文。
陳建甫,2006,「以基因搜尋法求解多桶格車輛途程問題」,南台科技大學工業管理研究所碩士論文。
陳春益、林正章、陳麗紅、胡學彥、林志明與劉昭榮,1997,「國內零擔貨運業設置場站之探討」,第五屆海峽兩岸都市交通術研討會論文集,59-68。
陳春益、林志鴻與邱明琦,2001,「公路貨物運輸產業發展趨勢與因應策略」,國家貨運發展政策研討會論文集,交通部運輸研究所。
劉金維、王隆昌,2004,「線上型單一車輛調派問題研究」,商管科技季刊,第五卷,第一期,95-108。
韓復華、楊智凱、卓裕仁,1996,「門檻接受法、噪音擾動法與搜尋空間平滑法在車輛路線問題之應用研究與比較分析」,運輸計劃季刊,第九卷,第三期,113-144。
簡世釗,2001,「時窗與容量限制下車輛途程問題之研究」,國立成功大學工業管理科學所碩士論文。
顏成佑,2000,「基因演算法解算軟性時窗車輛途程問題之研究」,元智大學工業工程研究所碩士論文。
蘇木春、張孝德,1997,「機器學習:類神經網路、模糊系統以及基因演算法則」,華科技圖書股份有限公司,台北。
蘇志峰,2001,「具時窗限制之多場站車輛路線問題之研究」,國立成功大學工業管理科學系碩士論文。
蘇純繪、翁瑞聰,2003,「以蟻群群聚最佳化整合噪音擾動法求解TSP問題」,商管科技季刊,第四卷,第四期,359-375。
Barrie, M. B. and Ayechew, M. A. (2003). “A Genetic Algorithm or The Vehicle Routing Problem”, Computers and Operations Research, Vol.30, 787-800.
Bodin, L., Golden, B., Assad, A. and Ball, M. (1983). “Routing and Scheduling of Vehicles and Crews”, Computers and Operations Research, Vol. 10, No. 2, 63-211.
Chao, I. M., Golden, B. L. and Wasil, E. (1993). “A New Heuristic for The Multi-Depot Vehicle Routing Problem That Improves Upon Best-Known Solutions”, American Journal of Mathematical and Management Science, Vol. 13, No. 2, 371-406.
Charles, J. M. (1995). “A Genetic Algorithm for Service Level Based Vehicle Scheduling”, European Journal of Operational Research, Vol. 93, 121-134.
Chin, A. J., Kit. H. W. and Lim. A. (1999). “A New GA Approach for Vehicle Routing Problem”, Proceedings of IEEE International Conference on Tools with Artificial Intelligence, 307-310.
Clark, G. and Wright, J. W. (1964). “Scheduling of Vehicles from a Central Depot to a Number of Delivery Points”, Operations Research, Vol. 12, No. 4, 568-581.
Cordeau, J. F., Gendreau, M. and Laporte, G. (1997). “A Tabu Search Heuristic for Periodic and Multi-Depot Vehicle Routing Problems”, Networks, Vol. 30, No. 2, 105-119.
Cordeau, J. F., Laporte, G. and Mercier, A. (2001). “A Unified Tabu Search Heuristic for Vehicle Routing Problems with Time Windows”, Journal of the Operational Research Society, Vol. 52, No. 8, 928-936.
Dantzig, G. B. and Ramser, R. H. (1959). “The Truck Dispatching Problem”, Management Science, Vol. 10, No. 6, 80-91.
Fisher, M. L. (1995). “Vehicle Routing”, In M. O. Ball, T. Magnanti, C. Monma, and G. Nemhauser (Eds.), Handbook in Operations Research and Management Science, Vol. 8, 1-33.
Fisher, M. L. and Jaikumar, R. (1981). “A Generalized Assignment Heuristic for Vehicle Routing Problems”, Network, Vol. 11, 109-124.
Gillett, E. B. and Miller, L. R. (1974). “A Heuristic Algorithm for the Vehicle Dispatch Problem”, Operations Research, Vol. 22, No. 2, 340-349.
Golden, B. L., Magnanti, T. L. and Nguyen, H. Q. (1977). “Implementing Vehicle Routing Algorithms”, Networks, Vol. 7, No. 2, 113-148.
Golden, B., Assad, A., Levy, L. and Gheysens, F. (1984). “The Fleet Size and Mix Vehicle Routing Problem”, Computer and Operations Research, Vol. 11, No.1, 49-66.
Holland, J. H. (1975). “Adaptive in Natural and Artificial Systems”, Ann Arbor: The University of Michigan Press.
Hwang, H. S. (2002). “An Improved Model for Vehicle Routing Problem with Time Constraint Based on Genetic Algorithm”, Computers and Industrial Engineering, Vol. 42, 361-369.
Jin, W. R. and Hsu, J. Y. (1999). “Dynamic Vehicle Routing Using Hybrid Genetic Algorithms”, IEEE Proceedings of International Conference on Robotics and Automation, Vol. 1, 453-458.
Laporte, G., Nobert, Y. and Arpin, D. (1984). “Optimal Solutions to Capacitated Multi-depot VRPs”, Congressus Numerantium, Vol. 44, 283-292.
Laporte, G., Nobert, Y. and Taillefer, S. (1988). “Solving a Family of Multi-Depot Vehicle Routing an Location Routing Problems”, Transportation Science, Vol. 22, No. 3, 161-172.
Lau, H. C., Sim, M. and Teo, K. M. (2003). “Vehicle routing problem with time windows and a limited number of vehicles”, European Journal of Operational Research,Vol. 148, No. 3, 559-569.
Lim, A. and Wang, F. (2005). “Multi-Depot Vehicle Routing Problem: A One-Stage Approach”, IEEE Transactions on Automation Science and Engineering, Vol. 2, No. 4, 397-402.
Lin, S. (1965). “Computer Solutions of the Traveling Salesman Problem”, Bell System Technical Journal, Vol. 44, No. 10, 2245-2269.
Lin, S. and Kernighan, B. W. (1973). “An Effective Heuristic Algorithm for the Traveling Salesman Problem”, Operations Research, Vol. 21, 498-516.
Louis, S. J., Yin, X. and Yuan, Z. Y. (1999). “Multiple Vehicle Routing with Time Windows Using Genetic Algorithms”, IEEE Proceedings of the 1999 Congress on Evolutionary Computation, Vol. 3, 1804-1808.
Mole, R. H. and Jameson, S. R. (1976). “A Sequential Route-Building Algorithm Employing Generalized Savings Criterion”, Operation Research Quarterly, Vol. 27, 503-511.
Potvin, J., Duhamel, C. and Guertin, F. (1996). “A Genetic Algorithms for Vehicle Routing Problem with Backhauling”, Applied Intelligence, Vol. 6, 345-355.
Raft, M. (1982). “A Modular Algorithm for an Extended Vehicle Scheduling Problem”, European Journal of Operational Research, Vol. 11, 67-76.
Renaud, J., Laporte, G. and Boctor, F. F. (1996). “A Tabu Search Heuristic for the Multi-Depot Vehicle Routing Problem”, Computers and Operations Research, Vol. 23, No. 3, 229-235.
Salhi, S. and Sari, M. (1997). “A Multi-Level Heuristic for the Multi-Depot Vehicle Fleet Mix Problem”, European Journal of Operational Research, Vol. 103, No. 1, 95-112.
Solomon, M. M. (1987). “Algorithms for the Vehicle Routing and Scheduling Problems with Time Window Constraints”, Operations Research, Vol. 35, No. 2, 254-265.
Tan, K. C., Lee, L. H. and Ou, K. (2001). “Artificial Intelligence Heuristics in Solving Vehicle Routing Problems with Time Window Constraints”, Engineering Applications of Artificial Intelligence, Vol. 14, 825-837.
Tillman, F. A. (1969). “The Multiple Terminal Delivery Problem with Probabilistic Demand”, Transportation Science, Vol. 3, 192-204.
Yingjie, Z. and Michael, H. C. (2004). “A Vehicle Routing Problem with Backhauls and Time Windows: a Guided Local Search Solution”, Transportation Research Part E, Vol. 41, 131–144.
連結至畢業學校之論文網頁點我開啟連結
註: 此連結為研究生畢業學校所提供,不一定有電子全文可供下載,若連結有誤,請點選上方之〝勘誤回報〞功能,我們會盡快修正,謝謝!
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top