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

詳目顯示:::

我願授權國圖
: 
twitterline
研究生:張時豪
研究生(外文):Shih-Hao,Chang
論文名稱:貨櫃陸地轉運問題之演算法發展
論文名稱(外文):A Heuristic Algorithm for In-land Container Trnasshipment Problem
指導教授:申生元申生元引用關係
指導教授(外文):Sheng-Yuan,Shen
學位類別:碩士
校院名稱:元智大學
系所名稱:資訊管理研究所
學門:電算機學門
學類:電算機一般學類
論文種類:學術論文
論文出版年:2005
畢業學年度:93
語文別:中文
論文頁數:65
中文關鍵詞:貨櫃運輸車輛途程問題啟發式演算法
外文關鍵詞:Container transshipmentVehicle routingHeuristic
相關次數:
  • 被引用被引用:3
  • 點閱點閱:156
  • 評分評分:
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:1
隨著全球海運業的成長,國際貨櫃運輸量也持續增加,然貨運市場競爭卻也愈趨激烈,因此,各貨櫃運輸業者莫不絞盡腦汁的思考如何節省成本及創造更多收入來源,以為企業帶來更高的利潤。傳統貨運業者大多都倚賴派車人員之直覺及經驗的方式調派轉運車輛。但由於人腦的處理能力有其極限,無法同時考量太多因素,以至於未能以最佳的方式進行作業派遣,也使得業者在擴編車隊時,增加其難度。因此,利用電腦高速的運算能力,來輔助派車人員進行車輛任務排程的工作,對於貨櫃運輸業者而言,將會為其帶來相當的效益。

本研究首先將貨櫃運輸問題構建為一混合整數規劃數學模式,然因其具有NP-hard的特性,其求解時間會隨著問題規模變大而呈指數倍數成長。本論文利用OPL Studio以求解所構建之數學模式,當給予的節點數量不多時,其求解時間尚在可接受的程度,但是隨著節點數量之増加,其求解時間即明顯快速增加。因此,本研究發展一啟發式演算法,希望能在合理的時間內,求得一個品質不錯的解。實驗結果證明此演算法的求解速度相當迅速,且求得解之品質也相當不錯,顯示出此演算法用於求解本問題,無論在時間及求解品質上,均有相當不錯的表現。
With the growth of the global marine, the volume of containers are growing up constantly every year. However, the competition of freight transportation market also becomes increasingly more fierce than ever before. In order to earn more profit, every container transportation company does need to work hard to save cost and create more sources of revenue. Traditionally, most freight transportation companies do their vehicle scheduling tasks manually that rely on the intuition and experience of employees. Because the human brain capability in delaing with complex situations has its limit, it is unable to easily consider too many factors at the same time, so that it can’t utilize vehecles with the best way. Therefore, for freight transportation companies, it is helpful to use the powerful computation capability of computer to assist people in assigning vehicles.

In this research, we first transform the container transshipment problem into a mix interger mathematical model. Since it is an NP-hard problem, the corresponding computational time tends to grow exponentially as the problem size increases. Therefore, we develop a heuristic to meet the real world needs. We hope that we can get acceptable solutions in a resonable time. After testing the heuristic through several examples, we find the solution time of the heuristic is quiet efficient, and the quality of the answer is pretty good in contrast to the optimal solutions for small size problems. It shows that the heuristic is effective in solving this problem.
書頁名…………………………………………………………………………………i
教育部授權書…………………………………………………………………………ii
國科會授權書…………………………………………………………………………iii
論文口試委員審定書…………………………………………………………………iv
中文摘要………………………………………………………………………………vi
英文摘要………………………………………………………………………………vii
誌 謝…………………………………………………………………………………viii
目錄……………………………………………………………………………………ix
表目錄…………………………………………………………………………………xi
圖目錄…………………………………………………………………………………xii
第一章 緒論…………………………………………………………………………1 1.1 研究背景與動機………………………………………………………1
1.2 研究目的……………………………………………………………………3
1.3 研究範圍……………………………………………………………………4
1.4 研究流程……………………………………………………………………5
第二章 陸地貨櫃運輸現況之問題特性……………………………………………6
2.1 貨櫃的定義與分類…………………………………………………………6
2.1.1 貨櫃的定義…………………………………………………………………6
2.1.2 貨櫃的分類…………………………………………………………………7
2.1.3 貨物裝載方式………………………………………………………………9
2.2.1 貨櫃集散站之定義與功能…………………………………………………11
2.2.2 貨櫃集散站之分類…………………………………………………………11
2.3 貨櫃轉運產業之特性………………………………………………………12
第三章 文獻探討……………………………………………………………………14
3.1 運具調度問題………………………………………………………………14
3.2 車輛排班模式之探討………………………………………………………15
3.2.1 旅行推銷員問題(Traveling Salesman Problem,TSP)…………16
3.2.2 車輛途程問題(Vehicle Routing Problem,VRP)…………………16
3.3 車輛排班之求解模式………………………………………………………17
3.3.1 最佳解的解法………………………………………………………………17
3.3.2 啟發式求解法………………………………………………………………19
3.3.3 智慧型啟發式求解法………………………………………………………21
第四章 問題描述與模式構建………………………………………………………27
4.1 問題描述……………………………………………………………………27
4.2 模式構建說明………………………………………………………………28
4.3 數學規劃模式一 ─ 各貨櫃同屬性之情形………………………………29
4.3.1 模式概觀……………………………………………………………………29
4.3.2 模式介紹……………………………………………………………………31
4.3.3 數學模式說明………………………………………………………………33
4.4 數學規劃模式二 ─ 作業含有時窗之情形………………………………34
4.4.1 模式概觀……………………………………………………………………34
4.4.2 模式介紹……………………………………………………………………36
4.4.3 數學模式說明………………………………………………………………38
4.5 數學規劃模式三 ─ 作業含有CY作業之情形……………………………39
4.5.1 模式概觀……………………………………………………………………39
4.5.2 模式介紹……………………………………………………………………40
4.5.3 數學模式說明………………………………………………………………42
第五章 啟發式演算法………………………………………………………………43
5.1 發展緣由……………………………………………………………………43
5.2 演算法之背景介紹…………………………………………………………43
5.3 演算法精神…………………………………………………………………44
5.4 演算法模組介紹……………………………………………………………47
第六章 實驗結果與分析……………………………………………………………49
6.1 測試環境與題目說明………………………………………………………49
6.1.1 測試環境……………………………………………………………………49
6.1.2 測試題目說明………………………………………………………………49
6.2 實驗一之測試結果與分析…………………………………………………54
6.2 實驗二之測試結果與分析…………………………………………………57
第七章 結論與建議…………………………………………………………………60
7.1 結論…………………………………………………………………………60
7.2 後續研究建議………………………………………………………………61
參考文獻………………………………………………………………………………62
附錄 A…………………………………………………………………………………65
英文部分:

[1]Algorithms for the Vehicle Routing Problem," Annals of Operations Research, Vol. 41, pp.421-451.
[2]Balas E., “Intersection cuts —A new type of cutting plane for integerprogramming,” Operations Research, 19,19-39, 1971.
[3]Bard, J. F., L. Huang, M. Dror, and P. Jaillet, “A branch and cutalgorithm for the VRP with satellite facilities”, IIE Transaction, 30,pp.821- 834, 1998
[4]Bellman,R., “Dynamic Programming Treatment of the Traveling SalesmanProblem”,Vol.119,pp61-63,1962
[5]Bodin, L.D., Golden, B.L., Assad, A.A., and Ball, M.O., Routing andScheduling of Vehicle and Crews-The State of the Art,” Computer &Operations Research 10, pp.69-211, 1983.
[6]Brandao, J. and Mercer, A., "A Tabu Search Algorithm for the Multi-Trip Vehicle Routing and Scheduling Problem," European Journal of Operational Research, Vol.100, No.1, pp.180-191, 1997.
[7]Chiang, W.C. and Russel, R.A., “A Reactive Tabu Search Metaheuristic for the Vehicle Routing Problem with Time Windows,” Informs Journal of Computing, Vol.9, No.4, pp.417-430, 1997
[8]Glover, F., and M. Laguna, Tabu Search, Kluwer Academic Publishers,1997
[9]Glover, F., Tabu Search Fundamentals and Uses,E-mail:glover-f@cubldr.Colordo.edu,1994
[10]Golden, B. L. and C. C. Skiscim,“Optimization by Simulated Annealing :A Preliminary Computational Study for the TSP” Proceedings of the 1983 winter Simulated Annealing Conference,Washington,D.C.
[11]Held,M.and R.Karp,“A Dynamic Programming Approach to Scheduling Problem”,SIAM Journal Applied Mathematics,Vol.10,pp.192-210
[12]Holland, J. H., Adaptation in Natural and Artificial Systems,University of Michigan Press. Ann Arbor, MI, 1975
[13]http://userwww.sfsu.edu/%7Ekroll/CLASSES/510/syllabus.html.Intro.to algorithms by Cormen, Leiserson and Rivest
[14]J.E Beasley,B.Cao,”A tree search algorithm for the crew scheduling problem”。European Journal of Operation research ,pp.517-526,1996
[15]Katta G. Murty, 1985, Linear and Combinatorial programming, Robert E. Krieger Publishing Company
[16]Kirpatrick, S., C. D. Gelatt, Jr., and M. P. Vecchi, Optimization Simulated Annealing”,Science, Vol. 220, No.4598,pp.671-680,1983
[17]Lin, S. (1965), "Computer Solutions of the Traveling Salesman Problem," The Bell System Technical Journal, Dec., pp.2245-2269
[18]M.Padberg.,G.Rinaldi., “Optimization of a city symmetric Traveling Salesman Problem by Branch and Cut ”,Operations Research Letters,Vol.6,No.1,pp1-7,1987
[19]Or, I. (1976), "Traveling Salesman-type Combinatorial Problems and Their Relation to the Logistics of Regional Blood Banking," Ph.D. Dissertation, Northwestern University. 19.Osman, I.H. (1993), "Metastrategy Simulated Annealing and Tabu Search
[20]Pyung H. K., Woon S. L, and Dong W. Jang, 2004. “Fleet Sizing and Vehicle Routing for container transportation in a static environment”
[21]Stephen E. Bechtold、Michael J. Brusco and Michael J. Showalter, A comparative Evaluation of Labor Tour Scheduling Methods, Decision Sciences, 22, 1991, pp. 683-699
[22]Tibrewala, R.,D. Philippe, and J. Browne.(1972). “Optimal Secheduling of Two Consecutive Idle Periods,” Management Science,19(1),71-75.
[23]Warren B. Powell. “A Comparative Review of Alternative Algorithms for the Dynamic Vehicle Problem”. In:B.L Golden and A.A.Assad,Vehicle Routing:Methods and Studies(1988).pp249-291
[24]XU. J. and J.P. Kelly, 1996. “A Network Flow-Based Tabu Search Heuristic for the Vehicle Routing Problem,” Transportation Science, 30, 379-395
[25]XU. J. and J.P. Kelly,1999. “A Set-Partitioning-Based Heuristic for the Vehicle Routing Problem,” Journal on Computing, 11 , 161-172

中文部份

[26]中華民國交通統計月報,民國九十二年十二月
[27]王文貞,圖書配送車輛排程問題之研究,成功大學交通管理學系,民國八十六年。
[28]王志賢,公路車輛調度問題之研究-以新竹客運為例,國立交通大學,交通運輸研究所碩士論文,民國八十五年。
[29]王勇華,人員排班問題啟發式解法之應用”,交通大學土木工程研究所,民國82 年。
[30]吳宗憲,結合模擬技術與專家系統應用於公車之排班作業,國立台灣大學,土木工程學研究所碩士論文,民國八十三年。
[31]吳淵民,物流中心運輸成本及短缺罰金之最佳化模式,國立雲林技術學院,工業工程與管理研究所,民國八十三年。
[32]曹家瑞,物流業配送系統之車輛指派與路徑規劃,國立台北科技學,生產系統工程與管理研究所,民國八十九年。
[33]陳坤賓,模擬退火法應用於車輛途程問題之研究,元智大學,工業工程研究所,民國八十七年。
[34]黃木才,”貨櫃運輸公司車輛排程問題之研究-模糊多目標遺傳演算法之應用”國立交通大學,交通運輸研究所碩士論文,民國八十五年。
[35]廖學昌,公車客運業人員排班問題之研究,國立交通大學,交通運輸研究所碩士論文,民國八十七年。
[36]駱景堯,吳泰熙,張俊仁 結合模糊理論與遺傳基因演算法於多目標彈性製造系統排程問題研究,工業工程學刊 1999 年,pp391~404
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top