臺灣博碩士論文加值系統

本研究之核心為策略性的中期船席規劃問題，其目的為使有大量船舶停靠需求的擁擠港口能藉由此模式提供的指派資訊，決定是否接受該船停泊需求，並給予接受指派的船舶相應的指派船席。不同於過去短期的船席指派問題，本研究考慮之模式引入了循環週期長度，目的為安排船席模板(Berth Template)，使該模板能套用在中期的碼頭船席決策，做港口資源最佳化的利用。同時，本研究在模式考量航商偏好之時間窗，使船席配置規劃能深入顧客服務層面，此結果也能提供航商未來長期的船期排程參考。本研究嘗試將中期船席規劃問題建構出數學模式，並考量問題規模與求解時間和求解品質，將該類中期船席規劃問題轉換成常見的集合涵蓋問題，並參考圖形最大權重匹配之演算方式進行求解演算法之構建。在數值例題測試部分，該演算方式能在可接受時間內完成可行解之搜尋，並有良好的求解績效。本研究期藉由數學模式與演算方式能增進中期船席規劃問題之發展與應用，提升中期船席規劃問題的可行性與求解效率。

Under the context of a congested container terminal, solving the congested problem has become the most important issue to port operators. The study developed two mixed integer programming (MIP) models for the tactical berth template design problem. With the objective of cost minimization, the terminal operator determines the berth assignment and the service starting time of the potential calling ships on a cyclical basis with respect to a fixed length of planning horizon. The operator has the flexibility of denying a ship at the price of losing a ship-dependent revenue or berthing it within a specific time window. In particular, an early or late penalty cost is incurred, if the ship service starting time is deviated from the preferred target time. This study compared the performances of the two IP formulations, one directly using the binary variable to represent the decision of berth assignment and service sequencing and the other indirectly making use of the generalized set-partitioning model. It was found that the performance of the latter is much better. This study further designed a heuristic solution algorithm based on the classic maximum weighted matching problem with respect to the generalized set-partitioning formulation. Based on the numerical experiments, the model and the solution algorithm developed in this study are promising in enhancing the literature of the tactical planning of container terminals

中文摘要 i
英文摘要 ii
誌謝 iii
目錄 iv
表目錄 vi
圖目錄 vii
第一章 緒論 1
1.1研究背景與動機 1
1.2研究範圍與目的 2
1.3研究方法與流程 3
第二章 文獻回顧 5
2.1船席規劃問題 5
2.1.1動態且離散之船席指派問題文獻回顧 6
2.1.2中期船席配置規劃問題之文獻回顧 7
2.2船席規劃問題模式與求解技術回顧 10
2.2.1船席指派問題求解方式探討 10
2.2.2基本動態且離散船席指派問題數學模式 10
2.2.3集合分割模型應用於船席指派問題 12
2.3文獻小結 13
第三章 模式建立與求解方法 15
3.1整數規劃模式一-以船席順序指派變數為基礎 15
3.2整數規劃模式二-以集合分割模式為基礎 19
3.3求解演算法設計 21
3.3.1最大權重匹配問題 21
3.3.2運用路徑生成法於船席規劃問題 23
第四章 數值測試 30
4.1測試題目設計 30
4.2數值測試結果 31
4.2.1小型測試例題結果分析 31
4.2.1大型測試例題結果分析 33
第五章 結論與建議 36
參考文獻 37
簡歷 40

Buhrkal, K., Zuglian, S., Ropke, S., Larsen, J., and Lusby, R. (2011).Models for the discrete berth allocation problem: A computational comparison. Transportation Research Part E, 47, 461-473.
Christensen, C.G., Holst, C.T. (2008). Berth Allocation in Container Terminals. Master’s Thesis. Department of Informatics and Mathematical Modelling, Technical University of Denmark.
Cordeau, J.-F., Laporte, G., Legato, P., Moccia, L. (2005). Models and tabu search heuristics for the berth-allocation problem, Transportation Science, 39, 526-538.
D.E. Drake, S. Hougardy, (2003).A simple approximation algorithm for the weighted matching problem. Information Processing Letters, 85, 211–213.
E.Lalla-Ruiz, B.Melián-Batista, J.Marcos Moreno-Vega (2012). Artificial intelligence hybrid heuristic based on tabu search for the dynamic berth allocation problem, Engineering Applications of Artificial Intelligence, 25,1132–1141.
Fisher, M.L., (1985). An applications oriented guide to Lagrangian relaxation. Interfaces, 15, 10-21.
Fisher, M.L. (2004). The Lagrangian relaxation method for solving integer programming problems. Management Science, 50, 1861–1871.
Giallomobardo,G., Moccia, L., Salani, M., Vacca, I. (2010). Modeling and sloving the tactical berth allocation problem. Transportation Research Part B, 44, 232-245.
Golias, M.M., Bolie, M., Theofanis, S. (2009). Berth scheduling by customer service differentiation: a multi-objective approach. Transportation Research Part E, 45, 878-892.
Hansen, P., Oguz, C., Mladenovic, N. (2008). Variable neighborhood search for minimum cost berth allocation. European Journal of Operational Research, 191, 636-649.
Held, M., Karp, R.M. (1970).The traveling salesman problem and minimum spanning trees. Operations Research, 18, 1138-1162.
Imai, A., Nagaiwa, K., Chen, W.T. (1997). Efficient planning of berth allocation for container terminals in Asia. Journal of Advanced Transportation, 31, 75-94.
Imai, A., Nishimura, E., Papadimitriou, S. (2001). The dynamic berth allocation problem for a container port. Transportation Research Part B, 35, 401-417.
Imai, A., Nishimura, E., Papadimitriou, S. (2003). Beth allocation with service priority. Transportation Research Part B, 37, 437-457.
Imai, A., Nishimura, E., Papadimitriou, S. (2005). Corrigendum to “The dynamic berth allocation problem for a container port” [Transportation Research Part B 35(2001) 401-417]. Transportation Research Part B, 39, 197.
Imai, A., Nishimura, E., Hattori, M., Papadimitriou, S. (2007). Berth allocation at indented berths for mega-containerships. European Journal of Operational Research, 179, 579-593.
Imai, A., Nishimura, E., Papadimitriou, S. (2008). Berthing ships at a multi-user container terminal with a limited quay capacity. Transportation Research Part E, 44, 136-151.
Huang, K.C., Imai, A., Chen, Y.A. (2012). An Ant-Based Algorithm for the Dynamic Berth Allocation Problem. Conference Paper, The 4th International Conference on Transportation and Logistics (T-LOG 2012)
Imai, A., Yamakawa, Y., Huang, K.C. (2013). The strategic berth template problem. working paper.
Monaco, M.F., Sammarra, M. (2007). The dynamic berth allocation problem: a strong formulation solved by Lagrangean approach. Transportation Science, 41, 265-280.
Moorthy, R., Teo, C.-P. (2006).Berth management in container terminal: the template design problem. OR Spectrum, 28, 495-518.
Nishimura, E., Imai, A., Papadimitriou, S. (2001) Berth allocation planning in the public berth system by genetic algorithms. European Journal of Operational Research, 131, 282-292.
Saharidis, G.K.D., Golias, M.M., Boile, M., Theofanis, S., Ierapetritou, M.G. (2010). The berth scheduling problem with customer differentiation: a new methodological approach based on hierarchical optimization. International Journal of Advanced Manufacturing Technology. 46, 377-393.
Ting, C.J., Wu, K.C., Chou, H. (2014). Particle swarm optimization algorithm for the berth allocation problem. Expert Systems with Applications. 41(4), Part 1,1543–1550.
Vacca, I., Salani, M., Bierlaire, M., (2013). An exact algorithm for integrated planning of berth allocation and quay crane assignment. Transportation Science, 47, 148-161.
Zhao, X., Luh, P.B., Wang, J. (1999). Surrogate gradient algorithm for lagrangian relaxation. Journal of Optimization Theory and Applications, 100, 699-712.
Zhen, L., Chew, E.P., Lee, L.H. (2011). An integrated model for berth template and yard template planning in transshipment hubs. Transportation Science, 45, 483-504.