海洋運輸為目前國際物流的主要運輸方式，其中，貨櫃運輸因為空間利用效率高，使其成為主流海運模式之一。然而，貨櫃運輸必須耗費大量時間、人力在港口進行貨櫃的裝卸作業。近年來越來越多港口引進自動化軌道式門式起重機(RMGC)，藉由電腦優化翻櫃作業，使貨櫃依取出順序預先排列好，減少船隻靠港時間，以此作為港口優勢吸引更多船務公司停靠。而決定RMGC翻櫃順序以解決壓櫃情形的問題我們通稱為整櫃問題，依照整櫃期間是否有貨櫃取出可分為取櫃問題(CRP)與預先整櫃問題(CPMP)。本研究所要探討的是無貨櫃取出之CPMP問題。
現存關於CPMP的研究，考量問題龐大難以求解，多半將問題簡化成單一列，並假設各儲區僅有一座RMGC進行作業。然而，現實中貨櫃在列與列之間移動有機會能簡化整櫃作業，且各儲區中通常配有多座RMGC，導致這些假設使問題與現實情況脫節。因此，本研究欲建立數學模型，將問題規模擴大至多列，並考量有兩座RMGC進行作業的情形。在模型中，我們假設整櫃作業總期數T為已知參數，然而在求解之前其實T為未知的，因此我們對T進行上界之估計，以便代入模型中求解。
求解後發現模型只能求解小規模問題，而T上界估計之演算法所得之解又與模型解相差過多，本研究改良過去文獻之演算法，讓貨櫃可以跨列進行翻櫃作業，並區分兩座RMGC的整櫃範圍，使啟發式演算法符合「多列」、「雙RMGC」之情境。數據顯示以啟發式演算法進行求解，在小規模問題中能求出與模型解誤差不大的結果，而針對規模過大使模型難以求解的問題，也能在合理的時間內給出可行解。數據也證實本研究因為考量貨櫃可以跨列進行移動，平均而言相較只考量單一列的文獻可以用更少的翻櫃次數完成預先整櫃作業；在數據分析中我們發現使用兩座RMGC不一定比使用一座RMGC更節省總機器作業時間，但比起只使用一座RMGC能在更短的時間內完成預先整櫃作業。

It is possible to reduce the container ship’s docking time by making good use of time to pre-arrange containers when there is no ship stopping by the quay. In order to determine the order of pre-marshalling operations, we built an integer programming model to solve it. Our research is different from current literatures since we expand the scale of the problem from a single bay to multiple bays and add corresponding restrictions to meet the situation where two RMGCs operate simultaneously. However, results showed that we can only solve small-scale problems by using Gurobi to solve the model due to the complexity of pre-marshalling problem. For medium-to-large-scale problems, we proposed a heuristic algorithm to solve it. For small-scale problems, the heuristic algorithm can obtain result that is almost the same as the model’s solution. Moreover, when it comes to the large-scale problems that model can hardly solve with, the heuristic algorithm can acquire solution within reasonable time. Our research also showed that due to considering moving containers between different bays, the pre-marshalling operations would be more efficient based on our data. Moreover, if the objective is to minimize the workload of RMGCs, using one RMGC sometimes is better than using two. However, if the objective is to minimize the finish time, almost all results suggest that using two RMGCs is better.

李衍儒. (2011). 出口儲區取櫃問題. (碩士), 國立成功大學, 台南市.
Bortfeldt, A., & Forster, F. (2012). A tree search procedure for the container pre-marshalling problem. European Journal of Operational Research, 217(3), 531-540.
Carlo, H. J., & Martínez-Acevedo, F. L. (2015). Priority rules for twin automated stacking cranes that collaborate. Computers & Industrial Engineering, 89, 23-33.
Caserta, M., Schwarze, S., & Voß, S. (2012). A mathematical formulation and complexity considerations for the blocks relocation problem. European Journal of Operational Research, 219(1), 96-104.
Caserta, M., & Voß, S. (2009). A Corridor Method-Based Algorithm for the Pre-marshalling Problem, Berlin, Heidelberg.
de Melo da Silva, M., Toulouse, S., & Wolfler Calvo, R. (2018). A new effective unified model for solving the Pre-marshalling and Block Relocation Problems. European Journal of Operational Research, 271(1), 40-56.
Expósito-Izquierdo, C., Melián-Batista, B., & Moreno-Vega, M. (2012). Pre-Marshalling Problem: Heuristic solution method and instances generator. Expert Systems with Applications, 39(9), 8337-8349.
Expósito-Izquierdo, C., Melián-Batista, B., & Moreno-Vega, J. M. (2015). An exact approach for the Blocks Relocation Problem. Expert Systems with Applications, 42(17), 6408-6422.
Expósito-Izquierdo, C., Melián-Batista, B., & Marcos Moreno-Vega, J. (2014). A domain-specific knowledge-based heuristic for the Blocks Relocation Problem. Advanced Engineering Informatics, 28(4), 327-343.
Hottung, A., & Tierney, K. (2016). A biased random-key genetic algorithm for the container pre-marshalling problem. Computers & Operations Research, 75, 83-102.
Huang, S.-H., & Lin, T.-H. (2012). Heuristic algorithms for container pre-marshalling problems. Computers & Industrial Engineering, 62(1), 13-20.
Jin, B., Zhu, W., & Lim, A. (2015). Solving the container relocation problem by an improved greedy look-ahead heuristic. European Journal of Operational Research, 240(3), 837-847.
Jovanovic, R., Tuba, M., & Voß, S. (2017). A multi-heuristic approach for solving the pre-marshalling problem. Central European Journal of Operations Research, 25(1), 1-28.
Kemme, N. (2012). Design and Operation of Automated Container Storage Systems: Physica-Verlag.
Kim, K. H., & Hong, G.-P. (2006). A heuristic rule for relocating blocks. Computers & Operations Research, 33(4), 940-954.
Lee, Y., & Chao, S.-L. (2009). A neighborhood search heuristic for pre-marshalling export containers. European Journal of Operational Research, 196(2), 468-475.
Lee, Y., & Hsu, N.-Y. (2007). An optimization model for the container pre-marshalling problem. Computers & Operations Research, 34(11), 3295-3313.
Liang, C., Fan, L., Xu, D., Ding, Y., & Gen, M. (2018). Research on coupling scheduling of quay crane dispatch and configuration in the container terminal. Computers & Industrial Engineering.
Tanaka, S., & Tierney, K. (2018). Solving real-world sized container pre-marshalling problems with an iterative deepening branch-and-bound algorithm. European Journal of Operational Research, 264(1), 165-180.
Tierney, K., Pacino, D., & Voß, S. (2017). Solving the pre-marshalling problem to optimality with A* and IDA*. Flexible Services and Manufacturing Journal, 29(2), 223-259.
Ünlüyurt, T., & Aydın, C. (2012). Improved rehandling strategies for the container retrieval process. Journal of Advanced Transportation, 46(4), 378-393.
van Brink, M., & van der Zwaan, R. (2014). A Branch and Price Procedure for the Container Premarshalling Problem, Berlin, Heidelberg.
Wang, N., Jin, B., Zhang, Z., & Lim, A. (2017). A feasibility-based heuristic for the container pre-marshalling problem. European Journal of Operational Research, 256(1), 90-101.
Wu, K.-C., Ting, C.-J., Hern, Aacute, & Ndez, R. (2010). Appling tabu search for minimizing reshuffle operations at container yards. Journal of the Eastern Asia Society for Transportation Studies, 8, 2379-2393.
Zehendner, E., Caserta, M., Feillet, D., Schwarze, S., & Voß, S. (2015). An improved mathematical formulation for the blocks relocation problem. European Journal of Operational Research, 245(2), 415-422.
Zheng, S., Wang, A., Mehmood, F., & Mohmand, Y. T. (2018). An Improved Path Optimum Algorithm for Container Relocation Problems in Port Terminals Worldwide. Journal of Coastal Research, 752-765.
Zhu, W., Qin, H., Lim, A., & Zhang, H. (2012). Iterative Deepening A* Algorithms for the Container Relocation Problem. IEEE Transactions on Automation Science and Engineering, 9(4), 710-722.