跳到主要內容

臺灣博碩士論文加值系統

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

詳目顯示

我願授權國圖
: 
twitterline
研究生:柯芳伸
研究生(外文):Fang-Shen Ko
論文名稱:具裝卸設備限制之離散型動態船席指派問題研究
論文名稱(外文):Modeling and Solving the Discrete and Dynamic Berth Allocation Problem with Limited Quay Cranes
指導教授:申生元申生元引用關係
學位類別:碩士
校院名稱:元智大學
系所名稱:資訊管理學系
學門:電算機學門
學類:電算機一般學類
論文種類:學術論文
論文出版年:2009
畢業學年度:97
語文別:中文
論文頁數:57
中文關鍵詞:禁忌搜尋法船席指派問題裝卸設備指派問題
外文關鍵詞:Tabu SearchBerth allocation problemCrane allocation problem
相關次數:
  • 被引用被引用:2
  • 點閱點閱:283
  • 評分評分:
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
臺灣四周環海,對外貿易仰賴海運,且位居亞洲經貿樞紐,是國際貨櫃運輸往來的交會點,不僅臺灣港口在國際貨櫃運輸的轉口貿易上扮演重要的角色,臺灣港口的競爭力更是影響臺灣國際經貿地位的重要關鍵之一。本研究主要針對考量碼頭裝卸設備調度的船席規劃進行混合整數規劃模式(Mixed Integer Programming Model)構建與利用禁忌搜尋法(Tabu Search)之移步(move)的概念進行啟發式演算法設計,首先我們在不考慮裝卸設備限制條件下,針對離散型動態船席指派問題(Dynamic Berth Allocation Problem)求解,然後根據此船席指派結果,構建出裝卸設備之可行調度路徑,再利用本研究構建之求解裝卸設備指派問題的最佳化子模式求解。最後,求解結果若為不可行解(碼頭所有裝卸設備即使經過調度仍無法滿足所有船舶之需求),便針對部份船舶進行重新排程,再以重新排程後之指派結果構建裝卸設備之可行調度路徑及利用最佳化子模式求解,重覆上述步驟至設定之停止條件。本研究設計之演算法與最佳化混合整數規劃模式的結果比較來看,平均差距在1.5%左右,而最佳化於求解大型例題時,需花費較長的時間才能求得一可行解,測試結果顯示本論文設計之演算法可提供符合實務需求的良好規劃品質。
Because of lacking natural resources, Taiwan deeply relies on international trade for economy development. However, Taiwan has excellent advantages for developing international trade due to its geographic location as the junction of international container transit. From the marine transportation viewpoint, Taiwan should fully take this geographic advantage to enhance operational effectiveness and efficiency at each international harbor. This study focuses on developing a heuristic algorithm to solve the dynamic berth allocation problem (DBAP) with limited number of quay cranes. Initially, ignoring the quay crane constraints we heuristically construct several trial solutions to the DBAP, and maintain a pool of some high quality solutions in terms of total flow time as inputs for the following procedure. Thereafter, for each high quality solution recorded, we repeat the following two steps until a stopping criterion is reached. At step 1, we build the feasible transfer arcs of cranes for each pair of ships at different berths and solve the crane allocation problem using a variant of minimum cost network flow model. If feasibility is obtained with respect to the cranes needed, we got a feasible solution; otherwise, we enter into step 2. At the second step, for those infeasible solutions (i.e. the cranes available at the container terminal can not satisfy the demand of cranes for all the ships even through transferring cranes) obtained, we try to reschedule the service start times for certain ships using information revealed in solving the optimization submodel. Based on the experimental results on small size problems, our algorithm yielded solution quality about an average of 1.5% inferior to the optimal solutions. However, the giant single optimization model took a lot of time to obtain the first feasible solution as the problem size was getting bigger. By contrast, the algorithm we developed spent much less time in producing near optimal solutions. Generally speaking, the algorithm we developed seems to provide practical but high quality solutions.
書名頁 i
論文口試委員審定書 ii
授權書 iii
中文摘要 iv
英文摘要 v
誌謝 vii
目錄 viii
表目錄 x
圖目錄 xi
第一章 緒論 1
1.1 研究背景及動機 1
1.2 研究範圍 2
1.3 研究目的 3
第二章 文獻探討 5
2.1 船席指派問題架構 5
2.2 船席指派問題之相關研究 6
第三章 混合整數規劃模式構建 13
3.1 模式建構說明 13
模式之決策變數 14
3.2 混合整數規劃模式 14
第四章 啟發式演算法 18
4.1 演算步驟 18
4.2初始解構建 20
4.3 可行性初步分析 21
4.4裝卸設備可行性分析-初始解 22
4.5 改善流程 26
4.6船舶重排程 30
第五章 實驗結果 32
5.1 測試例題產生 32
5.2 實驗一 34
5.3 實驗二 38
第六章 結論與未來研究方向 41
6.1 研究結論 41
6.2 未來研究方向 41
參考文獻 43
附錄A 46
附錄B 52
[1]Cordeau, J. -., Laporte, G., Legato, P., & Moccia, L. (2005). Models and tabu search heuristics for the berth-allocation problem. Transportation Science, 39(4), 526-538.
[2]Dai, J., Lin, W., Moorthy, R., & Teo, C. P. (2004). Berth allocation planning optimization in container terminal, Working paper. Georgia Institute of Technology, Atlanta; National University of Singapore.
[3]Hansen, P., & Oǧuz, C. (2003). A Note on Formulations of Static and Dynamic Berth Allocation Problems. ISSN: 0711-2440.
[4]Hansen, P., Oǧuz, C., & Mladenović, N. (2008). Variable neighborhood search for minimum cost berth allocation. European Journal of Operational Research, 191(3), 636-649.
[5]Imai, A., Nagaiwa, K., & Tat, C. W. (1997). Efficient planning of berth allocation for container terminals in asia. Journal of Advanced Transportation, 31(1), 75-94.
[6]Imai, A., Nishimura, E., & Papadimitriou, S. (2001). The dynamic berth allocation problem for a container port. Transportation Research Part B: Methodological, 35(4), 401-417.
[7]Imai, A., Nishimura, E., & Papadimitriou, S. (2005). Erratum: " the dynamic berth allocation problem for a container port" (transportation research part B (2001) vol. 35 (401-417) 10.1016/S0191-261599000570). Transportation Research Part B: Methodological, 39(3), 197.
[8]Imai, A., Sun, X., Nishimura, E., & Papadimitriou, S. (2005). Berth allocation in a container port: Using a continuous location space approach. Transportation Research Part B: Methodological, 39(3), 199-221.
[9]Imai, A., Nishimura, E., Hattori, M., & Papadimitriou, S. (2007). Berth allocation at indented berths for mega-containerships. European Journal of Operational Research, 179(2), 579-593.
[10]Imai, A., Chen, H. C., Nishimura, E., & Papadimitriou, S. (2008). The simultaneous berth and quay crane allocation problem. Transportation Research Part E: Logistics and Transportation Review, 44(5), 900-920.
[11]Imai, A., Nishimura, E., & Papadimitriou, S. (2008). Berthing ships at a multi-user container terminal with a limited quay capacity. Transportation Research Part E: Logistics and Transportation Review, 44(1), 136-151.
[12]Krčum, K., Gudelj, A., & Vlahinić, S. (2007). Genetic Algorithm for Solving Berth and Quay Cranes Assignment problems. 2nd International Conference on Ports and Waterways-POWA 2007,
[13]Liang, C., Huang, Y., & Yang, Y. (2009). A quay crane dynamic scheduling problem by hybrid evolutionary algorithm for berth allocation planning. Computers and Industrial Engineering, 56(3), 1021-1028.
[14]Meisel, F., & Bierwirth, C. (2008). Heuristics for the integration of crane productivity in the berth allocation problem. Transportation Research Part E,
[15]Nishimura, E., Imai, A., & Papadimitriou, S. (2001). Berth allocation planning in the public berth system by genetic algorithms. European Journal of Operational Research, 131(2), 282-292.
[16]Steenken, D., Voß, S., & Stahlbock, R. (2004). Container terminal operation and operations research - A classification and literature review. OR Spectrum, 26(1), 3-49.
[17]Theofanis, S., Boile, M., & Golias, M. (2008). An optimization based genetic algorithm heuristic for the berth allocation problem. Paper presented at the 4439-4445.
[18]Zhu, Y., & Lim, A. (2006). Crane scheduling with non-crossing constraint. Journal of the Operational Research Society, 57(12), 1464-1471.
[19]張徐錫、劉宏道,由國際貨櫃海運發展看臺灣發展轉口貨櫃運輸之契機,中華技術專題報導,九十五年。
電子全文 電子全文(本篇電子全文限研究生所屬學校校內系統及IP範圍內開放)
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top