貨櫃船舶排艙問題之研究─限制規劃法之應用

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：9

、訪客IP：18.216.227.76

姓名

徐胤埕(Yin-cheng Hsu) 查詢紙本館藏

畢業系所

土木工程學系

論文名稱

貨櫃船舶排艙問題之研究─限制規劃法之應用
(The study of container ship stowage plan – application of constraint programming method)

相關論文

★ 圖書館系統通閱移送書籍之車輛途程問題	★ 起迄對旅行時間目標下高速公路匝道儀控之研究
★ 結合限制規劃法與螞蟻演算法求解運動排程問題	★ 共同邊界資料包絡分析法在運輸業之應用-以國內航線之經營效率為例
★ 雙北市公車乘客知覺服務品質、知覺價值、滿意度、行為意向路線與乘客之跨層次中介效果與調節式中介效果	★ Investigating the influential factors of public bicycle system and cyclist heterogeneity
★ A Mixed Integer Programming Formulation for the Three-Dimensional Unit Load Device Packing Problem	★ 高速公路旅行時間預測之研究--函數資料分析之應用
★ Behavior Intention and its Influential Factors for Motorcycle Express Service	★ Inferring transportation modes (bus or vehicle) from mobile phone data using support vector machine and deep neural network.
★ 混合羅吉特模型於運具選擇之應用-以中央大學到桃園高鐵站為例	★ Preprocessing of mobile phone signal data for vehicle mode identification using map-matching technique
★ 含額外限制式動態用路人均衡模型之研究	★ 動態起迄旅次矩陣推估模型之研究
★ 動態號誌時制控制模型求解演算法之研究	★ 不同決策變數下動態用路人均衡路徑選擇模型之研究

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

[檢視]

[下載]

本電子論文使用權限為同意立即開放。
已達開放權限電子全文僅授權使用者為學術研究之目的，進行個人非營利性質之檢索、閱讀、列印。
請遵守中華民國著作權法之相關規定，切勿任意重製、散佈、改作、轉貼、播送，以免觸法。

摘要(中)

貨櫃船舶之貨櫃排艙問題為定期航商重要的管理課題之一，於滿足船舶穩度安全限制下，最小化壓櫃情形，以降低貨櫃船舶滯港時間，進而使航商之碼頭作業成本下降。近年來，受貨櫃船舶大型化之影響，人工貨櫃排艙作業日漸複雜，故航商需要一套兼具安全與效率之輔助決策排艙系統，貨櫃排艙研究也因此應運而生。
以往貨櫃排艙問題研究多使用數學規劃方法配合啟發式演算法或巨集式啟發演算法，但其無法考量艙內之貨櫃擺放規則限制、貨櫃堆疊高度、重量等細部貨艙內限制式，故Delgado et al. (2012) 將貨櫃排艙問題分為兩階段子問題，分別為主積載規劃問題 (master planning)及艙位規劃問題(slot planning)，主積載規劃問題使用數學規劃方法求解全船之貨艙貨櫃分配數量，於艙位規劃階段使用限制規劃法處理貨艙內細部限制式，但未探討貨艙內船舶橫向穩度問題以及甲版以上艙位規劃問題。
本研究延續其第二階段之艙位規劃問題，並利用限制規劃法能快速搜尋可行解之特性，建構及求解貨艙內之艙位規劃問題，包含貨櫃堆疊高度及重量、貨艙結構、20呎貨櫃無法堆疊於40呎貨櫃上方等限制，同時增加考量貨艙內平衡問題及甲板以上艙位規劃問題，並以航商A所提供之實際船舶資料進行測試，共9個貨艙範例，所有範例均能在1秒內尋找到可行解，且與實務人工排艙比較後，發現本研究所得到之可行解甚佳。

摘要(英)

The container stowage problem is one of the important problem in liner shipping company, in order to decrease the port operating costs , this problem has to satisfy the ship’s stability and also has to minimize the number of over-stowage. Recently, due to the enlargement of containership, the manual operation of stowage plan is getting harder than before, so the liner shipping company is desperate for a container stowage decision making system that can reach both safety and efficiency.
It is our knowledge that the most research in the past are using mathematical programming method to solve the container stowage problem, but they can not considering the detail constraint in a bay, such as the limit of stack height and weight, 20’ containers cannot be stacked on top of 40’ containers and ship structure limit. Delgado et al. (2012) separated the container stowage problem into two phases, the master planning phase and the slot planning phase respectively, they use mathematical programming method to solve the master bay planning problem by distributing containers into bays without specific slot information, then use the constraint programming method to solve the slot planning problem, however, they didn’t mentioned the stability problem in a bay.
Our research is based on slot planning phase, by using the constraint programming method to build and solved the slot planning problem, including the limit of stack height and weight, 20’ containers cannot be stacked on top of 40’ containers and ship structure limit, in addition to considering the balance in a bay and solved the bay above deck. Without loss of generality, our test instances are all provided by the liner shipping company A, and able to solve all of the instances in less than 1 second, after compared with the manual stowage plan, we found that our feasible solution is quite good.

關鍵字(中)

★ 貨櫃排艙問題
★ 艙位規劃問題
★ 限制規劃

關鍵字(英)

★ Container stowage problem
★ Slot planning
★ Constraint programming

論文目次

摘要 i
Abstract ii
目錄 iii
圖目錄 vi
表目錄 vii
第一章緒論 1
1.1 研究背景與動機 1
1.2 研究目的與範圍 2
1.3 研究方法與流程 3
第二章文獻回顧 5
2.1 貨櫃排艙問題 5
2.1.1 蒙地卡羅模擬 8
2.1.2 0-1整數規劃模型 9
2.1.3 巨集式啟發解法 12
2.1.4 啟發式規則 18
2.1.5 限制規劃法 18
2.2 實務排艙作業 23
2.3 小結 24
第三章方法建構 25
3.1 貨櫃排艙問題描述 25
3.1.1 名詞描述 25
3.1.2 研究假設 30
3.1.3 參數設定 30
3.1.4 限制式說明 31
3.2 全域限制式建構 34
3.3 模式搜尋 36
3.4 艙位規劃問題求解架構 36
3.5 Gecode軟體 41
第四章範例測試與分析 44
4.1 範例測試資料與實驗環境說明 44
4.1.1 航線之港口資料 45
4.1.2 船舶資料 46
4.1.3 貨櫃資料 48
4.1.4 實驗環境說明 48
4.2 範例測試 48
4.2.1 簡例測試與結果分析 49
4.2.2 全船範例測試 53
4.3 小結 58
第五章結論與建議 59
5.1 結論 59
5.2 建議 60
參考文獻 61
附錄一限制規劃法介紹 64

參考文獻

[1] 李俊德，民國94年，「以限制規劃求解全年無休人員排班問題之研究-以護理排班人員為例」，國立交通大學運輸科技與管理學系，碩士論文，新竹市。
[2] 余彥儒，民國99年，「圖書館書籍通閱移送之車輛途程問題－巨集啟發式演算法之應用」，國立中央大學土木工程學系，碩士論文，中壢市。
[3] 邱俊唐，民國96年，「高雄港在亞太地區轉運競爭力之研究」，國立中央大學土木工程學系，碩士論文，中壢市。
[4] 陳彥宏、叢日春、林榮泰，民國96年，「危險貨物裝載的議題」，台灣海事安全與保安研究會-海安論壇。
[5] 陳彥宏，民國96年，「海事英文」，台灣海事安全與保安研究會。
[6] 陳惠國，民國99年，「研究方法-理論與實務」，滄海書局。
[7] 陳惠國，民國98年，「網路與物流分析」，滄海書局。
[8] 徐國裕，民國96年，「船舶操縱理論與實務」，五南書局。
[9] 張耿宗，民國92年，「變動需求下貨櫃船排艙最佳化研究」，國立中央大學，土木工程學系，碩士論文，中壢市。
[10] 張若怡，民國96年，「運用限制規劃求解氣體配送途程問題」，國立成功大學，交通管理科學系，碩士論文，台南市。
[11] 曾志煌、陳一昌、林美霞、徐順憲、陳素惠、蕭清木、鄭國璘、鄭樂堯、蔡瑞鉉、沈世婷、王世俠、張淑滿，民國100年，「臺灣地區商港整體發展規劃(101~105 年)」，交通部運輸研究所，頁1-1~12-9。
[12] 鄭雅勻，民國96年，「利用限制規劃求解客服中心人員排班問題」，國立清華大學，工業工程與工程管理學系，碩士論文，新竹市。
[13] 廖坤靜，民國77年，「航海力學」，中華民國海事學會。
[14] 廖坤靜，民國80年，「貨物作業」，正合印刷有限公司。
[15] 蔡政諭，民國100年，「結合限制規劃法與螞蟻演算法求解運動排程問題」，國立中央大學，土木工程學系，碩士論文，中壢市。
[16] Ambrosino, D., Sciomachen, A., Tanfani, E., “Stowing a containership: the master bay plan problem”, Transportation Research Part A, Vol. 38, No. 2, pp. 81-99, Genova, Italy, 2004.
[17] Avriel, M., Penn, M., “Exact and approximate solutions of the container ship stowage problem” , Computers and Industrial Engineering, Vol. 25, pp. 271-274, Israel,1993.
[18] Avriel, M., Penn, P. and Shpirer, N., “Container Ship Stowage Problem: Complexity and Connection to the Coloring of Circle Graphs”, Discrete Applied Mathematics, Vol. 103, pp. 271-279, Israel, 2000.
[19] Avriel, M., Penn, P., Shpirer, N., Witteboon, S., “Stowage planning for container ships to reduce the number of shifts”, Annals of Operations Research, Vol. 76, pp. 55-71, Israel, 1998.
[20] Ambrosino, D., Anghinolfi, D., Paolucci, M., Sciomachen, A., “An experimental comparison of different heuristics for the master bay plan problem”, Symposium on Experimental Algorithm, Springer, Vol. 6049, pp. 314-325, Genova, Italy, 2010.
[21] Ayachi, I., Kammarti, R., Ksouri, M., Borne, P., “Harmony search algorithm for the container storage problem”, International Conference on Modeling Optimization and Simulation, Tunisia, 2010.
[22] Brailsford, S. C., Potts, C. N., Smith, B. M., “Constraint satisfaction problems: algorithms and applications”, European Journal of Operation Research, Vol. 119, pp. 557-581, Southampton, United Kingdom, 1999.
[23] Dubrovsky, O., Levitin, G., Penn, M., “A genetic algorithm with a compact solution engine for the container ship stowage problem”, Journal of Heuristics, Vol. 8, pp. 585-599, Genova, Italy, 2002.
[24] Delgado, A., Jensen, R. M., Janstrup, K., Rose, T. H., Andersen, K. H., “A constraint programming model for fast optimal stowage of container vessel bays”, European Journal of Operation Research, Vol. 220, pp. 251-261, Copenhagen , Denmark, 2012.
[25] Delgado, A., Jensen, R. M., Schulte C., “Generating optimal stowage plans for container vessel bays”, Conference on Principles and Practice of Constraint Programming, Vol. 5732, pp. 6-20, Copenhagen, Denmark, 2009.
[26] Hoeve, W. J., Katriel, I., “Handbook of constraint programming”, 2006.
[27] Kang, J. G. and Kim, Y. D., “Stowage planning in maritime container transportation,” Journal of Operational Research Society, Vol. 53, No. 4, pp. 415-426, Korea, 2002
[28] Liu, F., Yoke, M., Huang, S. Y., Hsu W. J., Zeng M., Win, C. A., “Stowage planning of large containership with tradeoff between crane workload balance and ship stability”, International Multi-Conference of Engineers and Computer Scientists, Vol. 3, pp. 1838-1843, Singapore, 2010.
[29] Pacino, D., “Fast generation of container vessel stowage plans” Ph.D. Thesis, Copenhagen, Denmark, 2012
[30] Pacino, D. and Jensen, R. M., “Fast slot planning using constraint-based local search” Transactions on Engineering Technologies, Vol. 186, pp. 49-63, Copenhagen, Denmark, 2013.
[31] Pacino, D., Fast generation of container vessel stowage plans, IT University of Copenhagen, Ph.D. Thesis, Copenhagen, Denmark, 2012.
[32] Schulte, C., Tack, G., Lagerkvist, M. Z., “Modeling and programming with Gecode”, Sweden, 2013.
[33] Shields, J. J., “Container stowage: a computer aided pre-planning system”, Marine Technology, Vol. 24, No. 4, 1984.
[34] Wilson , I. D., Roach, P. A., “Principles of combinatorial optimization applied to container-ship stowage planning”, Journal of Heuristics Vol. 5, pp. 403-418, United Kingdom, 1999.
[35] Wilson , I. D., Roach, P. A., Ware, J. A., “Container stowage pre-planning: using search to generate solutions, a case study”, Knowledge-Based Systems, Vol. 14, pp. 137-145, United Kingdom, 2001.
[36] Xiao, X., Yoke, M., Huang, Y. S., Hsu, W. J., Li, Z., Liu F., “An efficient heuristic method for stowage planning of large containership with crane split consideration”, Maritime and Multimodal Logistics Modelling and Simulation, pp. 93-99, Singapore, 2009.
[37] Yoke, M., Low, H., Xiao, X., Liu, F., Huang, S.Y., Hsu, W.J., Li, Z., “An automated stowage planning system for large containerships”, Intelligent Production Machines and Systems, pp. 1964-1978, Singapore, 2009.
[38] Zeng, M., Yoke, M., Hsu, W. J., Huang, S. Y., Liu, F., Win, C. A., “Automated stowage planning for large containerships with improved safety and stability” Proceeding of the 2010 Winter Simulation Conference, pp. 1976-1989, Singapore, 2010.

指導教授

陳惠國(Huey-kuo Chen)

審核日期

2014-7-22

推文