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

詳目顯示:::

: 
twitterline
研究生:趙庭
研究生(外文):Ting Chao
論文名稱:貨櫃裝填問題之研究
論文名稱(外文):A Study on the Container Loading Problem
指導教授:朱經武博士
指導教授(外文):Dr. Chu Ching -Wu
學位類別:碩士
校院名稱:國立臺灣海洋大學
系所名稱:航運管理學系
學門:運輸服務學門
學類:運輸管理學類
論文種類:學術論文
論文出版年:2012
畢業學年度:100
語文別:中文
論文頁數:76
中文關鍵詞:貨櫃裝填問題遺傳基因演算法啟發式演算法
外文關鍵詞:container loading problemgenetic algorithmheuristic algorithm
相關次數:
  • 被引用被引用:2
  • 點閱點閱:387
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:44
  • 收藏至我的研究室書目清單書目收藏:1
摘要
貨櫃裝載問題在海、空、製造業,均非常重要,因為採取何種方式裝填併櫃,會直接影響供應鏈的運費及成本計算,所以如何能得到最大利益,了解如何裝填貨物,使得剩餘使用空間最少,就是一個非常有研究價值的課題。

本研究以多尺寸長方體貨物與單一貨櫃裝載為探討對象,目的是要解決貨櫃裝載問題並在合理的時間內求取最小不可裝載空間。

我們提出了以遺傳基因演算法做為堆疊機制,對於如何在三維空間內裝載最大量的長方體貨物,演算法分成建構與改良二階段,在建構階段採取以建牆的方式去計算剩餘空間,並且決定最先優先放入之順序和停止條件標準,在該層牆貨物堆疊完成後,就進行下一層的建牆步驟,同時為避免建牆時空間過多之浪費,也將建牆方法加以改良。採取決定層貨物的概念,設定每層寬度等於決定層 (Layer Determine Box, LDB) 貨物之寬度。

改良階段以建構階段之結果為輸入運用遺傳基因法來進行貨物堆疊。運用染色體編碼、產生初始母體、計算母體的合適度再進一步的複製、交配、運用突變的概念以產生不同的基因,進而產生新的母體原則來進行計算研究中以15題的國際例題和實務情形來進行計算驗證後,證明確能提供一精確及有效率的方法求解貨櫃裝載問題。

關鍵詞:貨櫃裝填問題、遺傳基因演算法、啟發式演算法

Abstract
Container loading problems are important for sea transportation, air transportation and manufacturing. The way adopted to load cargoes into a container has direct impacts on the freight of a supply chain and cost calculation. In order to maximize profit, how to load cargoes into a container by minimizing the unused capacity is worthy of a study.

In this thesis, we study a container loading problem with multiple types of cargoes. The objective of this thesis is solving the container loading problem within a reasonable time by minimizing the unused capacity.

This thesis presents a genetic algorithm for a three dimensional container loading problem. The algorithm can be divided into two stages, construction and improvement stages. In the construction stage, a wall building method is used to calculate the unused space and to decide the loading priority of cargoes and stopping criterion. We keep building a layer within the current wall until no more space available. In order to mi-nimize the wasted space, we modified the wall building method by incorporating the concept of layer determine box. It is achieved by setting the width of each layer equal to layer determine box’s width.

In improvement stage, the genetic algorithm is used to load the container by taking the results of the construction stage as an input. Based on chromosome coding, we gen-erate the initial population and there calculate the fitness for further replication, cros-sover, and mutation. 15 test questions from Operations Research Library and a real world data are tested. Computational results show that our algorithm provides and ac-curate and efficient method for solving the container loading problem.

Keywords: container loading problem; genetic algorithm; heuristic algorithm

目錄
謝辭 I
摘要 III
Abstract IV
表目錄 VII
圖目錄 VIII
第一章緒論 1
1.1研究動機 1
1.2研究目的 5
1.3研究範圍與假設 6
1.4研究內容與流程 7
第二章文獻回顧 9
2.1貨櫃 (容器) 裝填研究 9
2.1.1單一尺寸的貨物與單一貨櫃(矩型容器) 9
2.1.2多尺寸的貨物與單一貨櫃/矩型容器 13
2.1.3多尺寸的貨物與貨櫃/矩型容器 19
2.2具有重量與穩定度考量之貨櫃裝填研究 22
2.3求解貨櫃(容器)裝填之啟發式演算法 25
2.3.1模擬退火演算法 26
2.3.2禁忌搜尋演算法 26
2.3.3基因演算法 31
2.3.4蟻群演算法 34
2.3.5蜜蜂演算法 37
2.4小結 39
第三章貨櫃裝載問題 40
3.1貨櫃裝載問題 40
3.2問題定義 46
3.4問題限制 50
第四章演算法建構與範例測試 51
4.1啟發式演算法建構 51
4.1.1建構階段 51
4.1.2改善階段 54
4.2範例測試 60
第五章結論與建議 70
5.1結論 70
5.2建議 70
參考文獻 72


參考文獻
1.田邦廷 (2003),「長方體物件堆疊問題解法之研究」,私立大葉大學碩士論文。
2.李其憲 (2005) ,「應用基因演算法求解長方體物件堆疊問題」,私立大葉大學碩士論文。
3.李起毓 (2007) ,「以混合啟發式演算法求解空間裝載利用率的最佳化問題」,私立朝陽科技大學碩士論文。
4.林光、李選士、王昱傑 (1995),「配櫃決策支援系統之研究」,航運季刊第四卷,第四期,頁84-106。
5.柯宜伶(2008) ,「以基因演算法求解限重與平穩度考量下之貨物配櫃問題」,國立臺灣海洋大學碩士論文。
6.徐誠佑 (2002) ,「螞蟻演算法求解零壹多限制式背包問題」,國立清華大學碩士論文。
7.徐徳興 (2000) ,「利用模擬退火演算法求解不規則物件排列及切割問題」,私立大葉大學碩士論文。
8.張美忠 (1992) ,「貨物運輸棧板裝載問題啟發式解法之應用」,國立交通大學碩士論文。
9.楊佳燕 (2005) ,「多重限制多容器裝填問題最佳化之研究」,私立華梵大學碩士論文。
10.謝宜和 (2011) ,「改良螞蟻演算法為基礎之法則探勘」,國立高雄第一科技大學碩士論文。
11.劉復華、蕭智仁 (1996) ,「單一尺寸箱體棧板堆疊方法」,國立交通大學博士論文。
12.鍾正豪(2003) ,「多重限制容器裝填問題最佳化之研究」,私立華梵大學碩士論文。
13.Abdou, G. and Yang, M.(1994), “A Systematic Approach for the Three-dimensional Palletization Problem,”International Journal of Production Research, Vol. 32, No. 10, pp. 2381-2394.
14.Belev, G. and Scheithauer, G. (2002),“A Cutting Plane Algorithm for the One-dimensional Cutting Stock Problem with Multiple Stock Lengths,” Euro-pean Journal of Operational Research, Vol. No.141, pp. 274-294.
15.Bischoff, E. E. and Marriott, M. D. (1990), “A Comparative Evaluation of Heu-ristics for Container Loading,” European Journal of Operational Research, Vol. 44, No. 2, pp. 267-266.
16.Bischoff, E. E. and Ratcliff, M. S. W. (1995a),“Loading Multiple Pallets,”The Journal for the Operational Research Society, Vol. 46, No. 11, pp. 1322-1336.
17.Bischoff, E. E., Janetz, F. and Ratcliff, M. S. W. (1995b), “Loading Pallets with Non-identical Items,”European Journal of Operational Research, Vol. 84, No. 3, pp. 681-692.
18.Bischoff, E. E. and Ratcliff, M. S. W. (1995),“Issues in the Development of Ap-proaches to Container Loading,”Omega, Vol. 23, No. 8, pp. 377-390.
19.Bischoff, E. E. (2006), “Three-dimensional Packing of Items with Limited Load Bearing Strength,” European Journal of Operational Research, Vol. 168, No. 3, pp. 952-966.
20.Bortfeldt, A. and Gehring, H.(2001), “A Hybrid Genetic Algorithm for the Con-tainer Loading Problem,” European Journal of Operational Research, Vol. 131,No. 1, pp. 143-161.
21.Bortfeldt, A., Gehring, H. and Mack, D. (2003), “A Parallel Tabu Search Algo-rithm for Solving the Container Loading Problem,” Parallel Computing, Vol. 29, No. 5, pp. 641-662.
22.Chen, C., Sarin, C. and Ram, B. (1991),“The Pallet Packing Problem for Non-uniform Box Sizes,” International Journal of Production Research, Vol. 29, No. 10, pp. 1963-1968.
23.Chien, C. F. and Deng, J. F. (2004),“A Container Packing Support System for Determining and Visualizing Container Packing Patterns,”Decision Support Systems, Vol. 37, No, 1, pp. 22-34.
24.Chen, C. S., Lee, S. M. and Shen, Q. S., (1995),“An Analytical Model for The Container Loading Problem,” European Journal of Operational Research, Vol. 80, No. 1,pp. 68-76.
25.Davies, A. P. and Bischoff, E. E. (1999), “Weight Distribution Consideration in Container Loading,” European Journal of Operational Research, Vol. 114, No. 3, pp. 509-527.
26.Dereli, T. and Das, G. S. (2011), “A Hybrid ‘Bee(s) Algorithm’ for Solving Container Loading Problems,”Applied Soft Computing, Vol. 11, No. 2, pp. 2854-2862.
27.Dorigo, M. and Gambardella, L. M. (1997), “Ant Colonies for the Travelling Salesman Problem,” Bio Systems, Vol. 43, pp. 73-81.
28.Dorigo, M. and Caro, Gianni Di (1999), Ant Colony Optimization: A New Me-ta-heuristic, Evolutionary Computation, 1999. CEC 99. Proceedings of the 1999 Congress on, IEEE, Washington, DC., Vol. 2, pp. 1470-1477.
29.Dowsland, K. A. (1987), “An Exact Algorithm for the Pallet Loading Problem,” European Journal ofOperational Research, Vol. 31, No. 1, pp. 78-84.
30.Dowsland, K. A. (1987), “A Combined Data-base and Algorithmic Approach to the Pallet Loading Problem,” Journal of the Operational Research Society, Vol. 38, No. 4, pp. 341-345.
31.Dowsland, W. B. (1991), “Three Dimensional Packing-solution Approaches and Heuristic Development,” International Journal of Production Research,Vol. 29, No. 8, pp. 1673-1685.
32.Csirik, J., Johnson, D. S., Kenyon, C., Orlin, J. B., Shor, P. W. and Weber, R. R. (2006),“On the Sum-of-Squares Algorithm for Bin Packing,”Journal of the ACM, Vol. 53, No. 1, pp. 1-65.
33.Eley, M. V. (2002),“Solving Container Loading Problems by Block
Arrangement,”European Journal of Operational Research, Vol. 141, No. 2, pp. 393-409.
34.Garey, M. R. and Johnson, D. S. (1979), Computers and Intractability A Guide to the Theory of NP Completeness, Freeman, San Francisco, U. S. A.
35.Gehring, H., Menschner, K. and Meyer, M. (1990), “A Computer-based Heuristic for Packing Pooled Shipment Containers,” European Journal of Operational Research, Vol. 44, pp. 277-288.
36.George, J. A. and Robinsion, D. F. (1980), “A Heuristic for Packing Boxes into Container,”Computers and Operations Research, Vol. 7, No. 3, pp. 147-156.
37.George, J. A. (1992), “A Method for Solving Container Packing for a Single Size of Box,” The Journal of the Operational Research Society,Vol. 43, No. 4, pp. 307-312.
38.Gilmore, P. C. and Gomory, R. E . (1965), “Multistage Cutting Stock Problems of Two and More Dimensions,” Operations Research, Vol. 13, No. 1, pp. 94-120.
39.Scheithaurer, G. (1999), “LP-based Bounds for the Container and Mul-ti-container Loading Problem,”International Transactions In Operational Re-search, Vol. 6, No. 2, pp. 199-213.
40.Haessler, R. W. (1980), “A Note on Computational Modifications to the Gil-more-Gomory Cutting Stock Algorithm,” Operations Research, Vol. 28, No. 4, pp. 1001-1005.
41.Haessler, R. W. and Talbot, F. B. (1990), “Loading Planning for Shipments of Low Density Products,” European Journal of Operational Research, Vol. 44, No. 2, pp. 287-299.
42.Herz, J. C. (1972),“A Recursive Computing Procedure for Two Dimensional Stock Cutting,” IBMJournal of Research Society, Vol. 16, No. 5, pp. 462-469.
43.Hochba, D. S. (1997), Approximation Algorithms for NP-hard Problems, USA:ACM Sigact News.
44.Holland, J. H. (1975), Adaptation in Natural and Artificial Systems, The MIT Press.
45.Lin, J. L., Foote, B., Pulat, S., Chang, C. H. and Cheung, J. Y. (1993), “Hybrid Genetic Algorithm for Container Packing in Three Dimensions,” Proceeding of the 9th Conference on AI Appliance, OrlandoIEEE, pp.353-359.
46.Liu, F. F. and Hsiao, C. J. (1997), “A Three-dimensional Pallet Loading Method for Single-size Boxes,” Journal of the Operational Research Society, Vol. 48, pp. 726-735.
47.Liu, N. C. and Chen, L. C. (1981), “A New Algorithm for Container Loading, ” Compsac 81-5th International Computer Software and Applications Conference Proceedings, IEEE, pp. 292-299.
48.Loh, H. T. and Nee, A. Y. (1992),”Packing Algorithm for Fexahedral Boxes,” Proceeding of the Industrial Automation 2 Conference of Singapore, pp. 115-126.
49.Morabito, R. and Pureza, V. (2010), “A Heuristic Approach Based on Dynamic Programming and and/or-Graph Search for the Constrained Two-Dimensional Guillotine Cutting Problem,” Annals of Operations Research, Vol.169, pp. 117-130.
50.Ngoi, B. K. A., Tay, M. L. and Chua, E. S. (1994), “Applying SpatialRepresen-tation Techniques to the Container Packing Problem,”International Journal of Production Research, Vol. 32, No. 1, pp. 111-123.
51.Parreño, F., Alvarez-Valdes, R., Oliveira, J. F. and Tamarit, J. M.:Amaximal-space Algorithm for the Container Loading Problem. INFORMS Journal on Computing, Vol. 20, No.3, pp. 412-422.
52.Parreño, F., Alvarez-Valdes, R., Oliverira, J. F. and Tamarit, J. M. (2010), “Neighborhood Structures for the Loading Problem a VNS Implementation,” Journal of Heuristics, Vol. 16, No. 1, pp. 1-16.
53.Davies, A. P., Eberhard, E. and Bischoff E. E. (1999),“Weight Distribution Con-siderations in Container Loading,”European Journal of Operational Research, Vol. 114, No. 3, pp. 509-527.
54.Ratcliff, M. S. W. and Bischoff, E. E. (1998),“Allowing for Weight Considera-tions in Container Loading,” OR Spektrum, Vol. 20, No. 1, pp.65-71.
55.Reves, C. R. and Yamada, T. (1998), “Genetic Algorithms, Path
Relinking and the Flowshop Sequencing Problem,”Evolutionary Computation, Vol. 6, No. 1, pp. 45-60.
56.Pureza, V. and Morabito, R. (2006), “Some Experiments with a Simple Tabu Search Algotithm for the Manufacturer’s Pallet Loading Problem,”Computers and Operations Research, Vol. 33, pp. 804-819.
57.Scheithauer, G. (1999), “LP-based bounds for the Container and Multi-container Loading Problem,”International Journal of Production Research, Vol. 6, pp. 199-213.
58.Socha, K. and Dorigo, M. (2008), “Ant Colony Optimization for Continuous Domains,”European Journal of Operational Research, Vol. 185, No. 3, pp. 1155-1173.
59.Srinivas, M. and Patnaik, L. M. (1994), “Genetic Algorithm: A Survey,”IEEE, Vol. 27, No. 6, pp. 17-26.
60.Steudel, H. J.(1979), “Generating Pallet Loading Patterns: A Special Cases of the Two-Dimensional Cutting Stock Problem,”Management science, Vol. 25, No.10, pp. 997-1004.
61.Steudel, H. J.(1984),“Generating Pallet Loading Patterns with Considerations of Item Stacking on End and Side Surface,”Journal of Manufacturing Systems, Vol. 3, No. 2, pp. 135-143.
62.Terno, J., Scheithauer, G. and Jan Riehme, U. S., (2000), “An Efficient Approach for the Multi-pallet Loading Problem,”European Journal of Operational Research, Vol. 123, No. 2, pp. 372-381.
63.Wang, P.(1983),“Two Algorithms for Constrained Two Dimensional Cutting Stock problems,” Operations Research, Vol. 31, No. 3, pp. 573-586.
64.Valdes, R. A., Parreňo, F. and Tamarit, J. M. (2005a), “A Branch-and-cut Algo-rithm for the Pallet Loading Problem,”Computers and Operations Research, Vol. 32, pp. 3007-3029.
65.Valdes, R. A., Parreňo, F. and Tamarit, J. M. (2005b), “A Tabu Search Algorithm for the Pallet Loading Problem,”OR Spectrum, Vol. 27, No. 1, pp. 43-61.

連結至畢業學校之論文網頁點我開啟連結
註: 此連結為研究生畢業學校所提供,不一定有電子全文可供下載,若連結有誤,請點選上方之〝勘誤回報〞功能,我們會盡快修正,謝謝!
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
系統版面圖檔 系統版面圖檔