多目标蚁群算法在集装箱配载问题中的应用

汪圆圆 陈顺怀

(武汉理工大学交通学院高性能船舶技术教育部重点实验室 武汉 430063)

多目标蚁群算法在集装箱配载问题中的应用

汪圆圆 陈顺怀

(武汉理工大学交通学院高性能船舶技术教育部重点实验室 武汉 430063)

针对集装箱配载问题，提出一种基于Pareto解集的蚁群算法以及基于权值分配的蚁群算法，采用分步式方法，将三维集装箱装载问题分解为Bay位优选和二维集装箱装载问题.在保证倒箱量为零的策略下，以船舶中纵剖面弯矩值、重心横向偏移、初稳性高为目标，以船舶吃水差值为约束条件，优化集装箱配载，从而达到提高集装箱船装载效率、节约装载成本和时间并使集装箱船获得稳定航行状态的目的.

多目标；蚁群算法；集装箱；配载优化

0 引 言

集装箱船舶配载问题是一个复杂的NP完全问题[1]，配载的优劣关系到船舶在港口装卸货物时效率的高低、船体强度，以及船舶稳性的合理与否，除此之外，还需考虑如何通过合理配载来使船舶具有较合理的浮态，从而保证船舶的快速性.想要通过整体方法快速有效地解决集装箱配载问题基本不可能，因此，对于大型集装箱船的配载问题，一个较为明显的做法就是对问题进行分解.

Gümü等[2]将集装箱配载问题分解为四步：①为每一目的港分派Bay位；②对Bay位中的每一层进行分配；③进行箱位分配；④当某一个箱子放到某一个箱位后，计算其适应度值.这四步分解能够较好地解决大型集装箱的配载问题，但是其倒箱模型复杂，且目标函数仅有倒箱，而将船舶的横倾作为约束处理，实际上是一个单目标优化问题.Ambrosino 等[3]将配载问题分解为两步，即首先根据目的港确定Bay位，而后对每一Bay位的集装箱进行优化排布.张维英[4]在其博士论文中将此问题分解为Bay位选择和Bay位排箱两个子问题，针对Bay位排箱这一子问题，给出了单一目的港和船舶挂靠多港的求解模型.而其求解模型以加权形式给出所谓多目标的求解形式，或者是以倒箱量最少为目标函数的单目标形式，这样的模型对于多目标问题来说，显然不是很合理.

集装箱船在一个航次中一般都要挂靠多个港口，在配载过程中，就会出现先卸载箱被后卸载箱压在下面的情况，这种情况称为倒箱.倒箱的产生将会使船舶的装载成本提高，船舶的经济效益减小.配载优化的一个关键目标就是尽可能减少倒箱.因此，很多关于配载优化的文章都将减少倒箱量作为目标.

Dubrovsky等[5]提出了以倒箱数最少为目标的基于紧凑编码的遗传算法，算法采用紧凑而高效的编码方式缩小搜索域，在遗传算法中加入局部优化策略，最终可以将倒箱数减少为零.但是，算法仅仅以倒箱数为目标，属于单目标的优化方式，船舶横稳性没有得到有效的保证.张维英针对混合港Bay位排箱优化问题，以倒箱数最少为目标，提出一种基于隐式图启发式搜索技术的Bay位排箱优化算法，并且给出一个挂靠6个港口，含80个箱位的Bay位优化算例.算法依然是基于单目标的优化方式，虽然可以减少倒箱量，但不能保证稳性和左右均衡.

卫家骏[6]提出一种针对集装箱箱位分配问题的混合蚁群算法，算法以装船后所有箱子的合重心距船舶中纵排剖面的距离最小为目标，在蚁群算法中加入禁忌算法，即将已选择的蚂蚁和其所选择的箱位加入禁忌表，以此来避免算法陷入局部最优.很显然，这样的算法依然是针对单目标问题的，其实用性不大.

文中将集装箱船舶配载问题分解为纵向Bay位选择和Bay位排箱优化这样两个子问题，采用控制倒箱量为零的策略，提出多目标蚁群算法进行优化配载，实现了这两步操作的无缝连接.先给出一个模拟Bay位排箱问题的算例，最后给出一个实际集装箱船配载算例.

1 配载问题的数学模型

1.1 问题描述

集装箱船配载问题是一个多目标、多约束的复杂问题，如前所述，问题可以被分解为纵向Bay位选择和Bay位排箱优化这样两个子问题，在纵向Bay位选择问题中，最关心的是船舶的结构强度和船体的浮态.Bay位排箱优化问题的一个最主要目标就是减少倒箱量，倒箱的定义如下：当在港口i卸载的集装箱被在港口j卸载的集装箱所阻碍时，便产生倒箱[7].很显然，船舶将先在港口i港口停泊.在本算法中，采用基于零倒箱规则的方式来处理多港排箱中的倒箱问题，即后卸载箱先装、先卸载箱后装的方式，这样的装箱方式可以确保在装箱过程中不产生倒箱操作，避免了由于倒箱所带来的数学模型的复杂性.第二个目标是最小化重心的垂向高度，以此来提高船舶的初稳性.第三个目标是最小化重心到中线面的距离，以此确保船舶的左右均衡.

1.2 数学模型的建立

集装箱船箱位排布俯视和侧视图见图1～图2.

图1 箱位排布俯视图

图2 箱位排布侧视图

在图1中，以L1，L2，…，Lm表示箱位的纵向排布顺序，按自船首至船尾增序排列.其所包含的集装箱数量分别为n1，n2，…，nm，重量分别为M1，M2，…，Mm，距船中的位置分别为x1，x2，…，xm，图中显示了TEU和FEU集装箱的排布示意.

在图2所示的Bay位图中，最大列数为R，最大层数为T，由最底层往最上层依次装载将于第Q，Q-1，…，k港卸载的集装箱，每港占据若干Bay位，如果第i港有冗余箱，则冗余箱按由轻到重选择，将冗余箱加至第i-1港的集装箱中进行排位.将坐标原点取在船舶中纵剖面处，沿船宽方向为Y轴，垂向为Z轴，以Cij(y,z)代表Bay位中第i(i=k,k+1,…,Q)港第j(j=1,2,…,Ni)箱位的坐标，其重量以w(y,z)表示.图中数字表示箱位顺序，即按从左到右、自下而上增序编号.

假定某集装箱船计划挂靠P个港口，该船舶的某一Bay位共混装Q个港口的集装箱，其中，Q≤P， 并假定该Bay位共有N个箱位，Q个港口的集装箱要装满这N个箱位.设每一港口集装箱数目分别为N1，N2，…，NQ，以wi(i=1,2,…,N)代表每一集装箱的重量.设该Bay位中在最前港卸载集装箱的港口为k(k=1,2,…,Q)，所需装载的集装箱数目为Nk.

在一次优化过程中，一个集装箱只能占据一个箱位，一个箱位也只能被一个集装箱占据，其数学表达形式为

(1)

对于某一个Bay位来说，其重心的横向和垂向位置为

(2)

(3)

式中：yj，zj为每一箱子的重心坐标.

对于每一港口及整个Bay位的集装箱重心位置的表示与其类似，限于篇幅，这里直接给出全船集装箱重心横向和垂向位置为

(4)

(5)

(6)

f2=YG

(7)

f3=ZG

(8)

(9)

p(r,c)≥p(r+1,c)

(10)

(11)

(12)

(13)

(14)

式(9)为变量值只能为0或1；式(10)为在某一列中，上层集装箱的卸载港要在下层集装箱的卸载港前；式(11)为所装载的集装箱总数要不超过船舶的箱位数；式(12)为每一列的集装箱数目不能大于该列的箱位总数；式(13)为船舶最好有一定的尾倾；式(14)为船舶的纵向强度约束，其中s为一与船长和排水量相关的常数.

2 多目标蚁群算法

2.1 多目标蚁群算法的数学模型

蚁群算法(ant colony optimization, ACO)最早成功应用于TSP(travelling salesmen problem)问题，集装箱配载问题与TSP问题类似，故应用蚁群算法求解集装箱配载问题.

石榴采摘后能有多种用途。个头大，汁多味甜的石榴用于出售给消费者食用。外观不好，但是酸甜可口的石榴被送到工厂进行产品加工，制成石榴汁进行售卖。而味道酸涩的石榴将被用作制作石榴酒，石榴醋等产品。而剩余的石榴皮可以晒干后进行卖入中药店用作药材。而剩下的石榴籽可以加工精油进行出售，或者卖入化妆品生产公司进行深加工。而老了的果树进行加工后，可以制作成为观赏价值较高的盆景。由于石榴的多种用途，给石榴种植产业化发展提供了有利的条件。

进行蚁群算法的前提是要构建距离函数，在多目标蚁群算法中，针对每一个目标，都需要定义合适的距离函数，距离函数的定义依据的是目标函数，因此，将距离函数定义为

(15)

式中：c为箱位坐标，包括x,y与z轴坐标；w为箱重.

蚁群算法的另一个关键点是蚂蚁选择某一路径的概率函数的定义，文中概率函数的定义与基本蚁群算法一致.

在每一只蚂蚁遍历完所有城市后，要对残留信息素进行更新，按照蚁周模型对信息素进行更新.

2.2 多目标蚁群算法

在对多目标蚁群算法中的一些要素进行定义以后，就可以进行算法的具体实现，实现步骤如下：

步骤1 设置初始参数，循环次数Tc=0，初始化各路径下的信息素量τij=常数，Δτij=0，建立禁忌表Tabu.

步骤2 对将在第Q港卸载的NQ个集装箱进行Bay位优化，将mQ只蚂蚁随机放在NQ个箱位上循环次数TQ,C=1，针对不同目标函数，计算蚂蚁选择城市j的概率，按轮盘赌规则选择蚂蚁将要移动到的箱位，并将之加入到禁忌表中，直到访问完所有箱位.存储mQ只蚂蚁的路径.

步骤3 对信息素量进行更新.

步骤4 如果TQ,C=TQ,max，则循环结束，将所有mQ×TQ,max条路径暂存；否则，TQ,C=TQ,C+1，禁忌表清空，返回步骤2.

步骤5 根据步骤4存储的mQ×TQ,max条路径计算YgQi，ZgQi，并两两进行比较，保留其中的非劣路径.

步骤6 对其他港进行相同操作.

步骤7 根据将在第k～Q港卸载的集装箱箱位优化选择结果计算Yg，Zg，得到一个Pareto前沿.

以上是一种基于Pareto前沿的多目标蚁群算法的基本步骤，这种算法可求得多组解，提供多种可选方案.除此之外，还可以以加权方式来求解多目标问题，这里不再赘述.加权方式算法简洁，但所得结果与权值选取有很大关联，且所能提供的可选方案少，而上述算法结果多样，所能提供的方案较多，且比较快速.

3 结果与分析

3.1 算例1

假定船舶某一Bay位共有30个箱位[8]，装载将在4个港口卸载的集装箱，每一个集装箱都为标准箱，将宽计为两个单位长度，则高为2.125 5个单位长度.港口排序按由近到远的增序排列，在第4港卸载的集装箱数目为6，第3港为8，第2港为12，第1港为4，起点港为第0港.箱子的初始重量(单位：104N)排布见图3.

图3 重量初始排布图

Bay位重心坐标：Yg=6.125 m，Zg=7.117 m.取α=1，β=2，ρ=0.2，Q=50，计算50代，优化后，结果见图4.

图4 优化排布结果

由非劣解所组成的Pareto前沿见图5，由图5可知，Bay位的重心纵向和垂向距离都能够得到优化解集.而倒箱量可严格控制为0.

图5 Bay位排箱优化后的Pareto前沿

3.2 算例2

对文献[4]中的“冰河”号在起始港进行Bay位优化，取α=1，β=2，ρ=0.2，Q=50，采用分步策略，重心垂向坐标权值取为0.5，横向偏移权值取为0.5.结果见表1(限于篇幅，仅给出部分结果)，其中a为该Bay位所有集装箱总重量之和，优化前与优化后的比较见表2.

优化后，中纵剖面弯矩减少了2.44%，吃水差绝对值下降14.2%，初稳性高增加43.5%，重心横向基本无偏移.

表1 部分“冰河”号配载优化结果图(Bay27)

表2 优化前后结果比较

4 结 束 语

文中提出一种基于Pareto解集的蚁群算法，采用不倒箱策略，对集装箱配载问题进行了优化求解，利用基于权值分步的蚁群算法，给出一个全船集装箱配载实例，并进行了比较，结果表明，这两种蚁群算法都大大节约了优化求解时间，能够将配载问题中最为重要的倒箱量指标严格控制为0，对集装箱船的重心、吃水差以及结构强度也有较大程度的优化.

[1]AVRIEL M, PENN M, SHPIRER N. Container ship stowage problem: complexity and connection to the coloring of circle graphs[J]. Discrete Applied Mathematics,2000,103(1):271-279.

[2]GÜMÜ M, KAMINSKY P, TIEMROTH E, et al. A multi-stage decomposition heuristic for the container stowage problem[J]. Journal of Heuristics,2008(1):55-58.

[3]AMBROSINO D, SCIOMACHEN A, TANFANI E. A decomposition heuristics for the container ship stowage problem[J]. Journal of Heuristics,2006,12(3):211-233.

[4]张维英.集装箱船全航线配载智能优化研究[D].大连：大连理工大学,2005.

[5]DUBROVSKY O, LEVITIN G, PENN M. A genetic algorithm with a compact solution encoding for the container ship stowage problem[J]. Journal of Heuristics,2002(8):585-599.

[6]卫家骏.集装箱船智能配载研究[D].大连：大连海事大学,2012.

[7]BENEDITO M, SANTOS A. Evolutionary algorithm and ant colony optimization for a container stowage problem[J]. Discrete Applied Mathematics,2015(2):356-363.

[8]张维英,林焰,纪卓尚,等.基于指派问题的Bay位排箱优化模型与算法[J].大连理工大学学报,2011,51(1):61-67.

Multi-objective Ant Colony Algorithms for Solving Container Loading Plan Problem

WANG Yuanyuan CHEN Shunhuai

(Key Laboratory of High Performance Ship Technology, Ministry of Education, School of Transportation, Wuhan University of Technology, Wuhan 430063, China)

In order to solve the three-dimensional container loading plan problem (3D CLPP), the ant colony algorithm based on the Pareto solution set and ant colony algorithm based on weight distribution are put forward. Using the method of step by step, the three-dimensional container loading problem is decomposed into the bay optimization and a two-dimensional container loading plan problem (2D CLPP). In a strategy of controlling the number of shift to be zero, the ship longitudinal bending moment value, center of gravity in the lateral displacement and height of initial stability are set as the goal and the ship draft difference between fore and aft is set as the constraint. In this way, the container loading plan is optimized such that the efficiency of containership loading can be improved, the cost and time of loading could be saved and the container ship state could have a stable state for sailing.

multiple objective; ant colony algorithm; container; loading optimization

2017-01-24

U695.22

10.3963/j.issn.2095-3844.2017.03.024

汪圆圆(1992—)：男，硕士生，主要研究领域为智能船舶