A Decomposition Method for Finding Optimal Container Stowage Plans

作     者：Roberti, R. Pacino, D. 

作者机构：Vrije Univ Amsterdam Dept Informat Logist & Innovat NL-1081 HV Amsterdam Netherlands Tech Univ Denmark Dept Engn Management DK-2800 Lyngby Denmark 

出 版 物：《TRANSPORTATION SCIENCE》 (运输科学)

年 卷 期：2018年第52卷第6期

页      面：1444-1462页

核心收录：

学科分类：1201[管理学-管理科学与工程(可授管理学、工学学位)] 08[工学] 0823[工学-交通运输工程] 

基　　金：Den Danske Maritime Fond 

主　　题：column generation container stowage dynamic programming exact methods maritime logistics mixed-integer programming 

摘      要：In transportation of goods in large container ships, shipping industries need to minimize the time spent at ports to load/unload containers. An optimal stowage of containers on board minimizes unnecessary unloading/reloading movements, while satisfying many operational constraints. We address the basic container stowage planning problem (CSPP). Different heuristics and formulations have been proposed for the CSPP, but finding an optimal stowage plan remains an open problem even for small-sized instances. We introduce a novel formulation that decomposes CSPPs into two sets of decision variables: the first defining how single container stacks evolve over time and the second modeling port-dependent constraints. Its linear relaxation is solved through stabilized column generation and with different heuristic and exact pricing algorithms. The lower bound achieved is then used to find an optimal stowage plan by solving a mixed-integer programming model. The proposed solution method outperforms the methods from the literature and can solve to optimality instances with up to 10 ports and 5,000 containers in a few minutes of computing time.