集装箱码头装船计划问题建模与优化研究  

Modeling and Optimizing for the Container Stowage Planning Problem in Container Terminal

作　　者：李坤[1] 唐立新[2] 

机构地区：[1]天津工业大学管理学院,天津300387 [2]东北大学物流优化与控制研究所,沈阳110004

出　　处：《控制工程》2015年第4期683-689,共7页Control Engineering of China

基　　金：国家自然科学基金(61403277);天津市教委项目(20132151)

摘　　要：以集装箱码头物流运作管理为研究背景,研究集装箱的装船计划问题(Container Stowage Planning Problem,CSPP)。在考虑船体结构以及具体的装载要求的基础上来确定集装箱装载计划中每个集装箱在船舶上的具体空间位置。对此问题构建整数规划模型,目标函数考虑总的装载时间以及船舶上bay位之间的装载量。为近似求解此问题,设计禁忌搜索算法。在算法实施中,把该问题分为两阶段问题并依次求解以获得整个问题的初始解,提出大范围搜索和深度搜索的混合搜索策略用于改进算法,并设计基于计算目标函数改进量的加速策略。通过实验表明,提出的禁忌搜索算法与CPLEX所获得的最优解或下界进行比较,平均偏差值为1.95%。Taking the logistics operation management of container terminals as the background, this paper investigates the container stowage planning problem （abbreviated as CSPP）. The main task of CSPP is to determine the stowage location of each container arranged in the loading plan according to the ship structure and specific loading requirements. This problem is formulated as an integer programming model whose optimization objective is to minimize the total loading time and the weight difference between loaded bays. To obtain a near-optimal solution for this problem, a tabu search algorithm is proposed. During the implementation of the algorithm, the CSPP is divided into two stages that are solved successively so as to obtain an initial solution of the CSSP. In the proposed tabu search algorithm, a hybrid search strategy combining the intensification search and diversification search is proposed and a speed-up strategy based on the calculation of the improvement of objective function is developed to further improve the algorithm＇s performance. Computational results show that the average gap between the solutions obtained by the tabu search algorithm and the optimal solutions or lower bounds Obtained by CPLEX is about 1.95%.

关 键 词：集装箱 装船计划 禁忌搜索 CPLEX 

分 类 号：TP181[自动化与计算机技术—控制理论与控制工程]