集装箱船全航线预配优化模型与算法研究

Optimum model and algorithm of containership′s pre-stowage planning in full routes

集装箱船全航线配载问题属于NP-hard问题.为降低问题求解难度,提出了解决全航线配载问题的分解算法,即将配载问题分解为Bay位选择和Bay位中集装箱排序两个子问题.将Bay位选择看成是"装箱问题",以不同属性集装箱作为待装"物品",以船舶上的Bay位为箱子,以最优装箱(即使用箱子的数量最少)及集装箱在每个港口的倒箱数量最少为目标进行总布置配载;Bay位中集装箱排序是将Bay位选择阶段分配到不同Bay位的集装箱按某些规则进行排序,确定其在Bay位中的具体箱位.主要研究了Bay位选择阶段的模型及算法.实例模拟结果表明该方法可行,为集装箱船全航线配载优化提供了一个实用的模型.

Containership stowage plan problem is an NP-hard problem. The problem is decomposed into two sub-problems, namely, pre-stowage plan and arranging containers of bays in order to reduce the computational complexity. Firstly, pre-stowage problem is regarded as packing problem, ship-bays on the board of vessel are regarded as bins, and the number of cells at each bay is taken as capacities of bins, containers with different characteristics （homogeneous containers group） are treated as items packed. At this stage, there are two objective functions： one is minimizing the number of bays packed by containers and the other is minimizing the number of rehandles. Secondly, containers assigned to each bays at first stage are allocated to special slot, and the objective functions are to minimize the metacentric height, heel and rehandles. The taboo search heuristics algorithm is used to solve the sub-problem. The main focus is on the first sub-problem. A practical case certifies the feasibility of the model and the algorithm.