0 引言

随着经济的发展，大宗货物运输量不断地增加，集装箱作为一种最为经济实惠的运输方式得到广泛的使用。集装箱装船顺序是保证货物运输安全、快捷的重要组成部分。在集装箱运输过程中按照一定的顺序将其装载，能够使得船舶装载的货物量增大，并且使得船舶的稳定性增高，降低货场的翻箱情况。

装船顺序问题是近年来的研究热点，Chen等^[1]在单个装船问题的0-1顺序模型的基础上研究了特殊集装箱的装船问题。Ambrosino等^[2]构建了集装箱装船的约束条件，对特殊集装箱装船算法进行求解。Bortfeldt等^[3]通过定点禁忌长度解决了局部最优解的问题。

1 建立模型

在装船问题上是将港口货场的集装箱按照一定的顺序搬运到船舶上，在货场中集装箱是按照行、列、层的顺序摆放的，其中重量大、运输路程远的集装箱会放在船舶的最下方，这样可以避免多次翻箱，以此降低运输成本，在这个运输过程尽量减少翻箱，保持处于船舶稳定状态。

为了更好的研究装船问题，本文对所研究的集装箱作出一些假设：

1）集装箱的尺寸都是20尺的箱子。

2）不适用吊桥和集卡进行船舶操作。

3）在装船的集装箱中没有生鲜箱等特殊箱体。

4）在堆场中进对同一行或同一列的集装箱进行翻箱。

在装船模型中令各个变量参数为：

1）堆场中集装箱的数量为n，设I_n ={1，2，…，n}是指标集。

2）第i个集装箱的质量是m_i ，且已知，i∈I_n 。

3）第i个集装箱到达目的港的时间标号是u_i ，且已知，i∈I_n

4）第i个集装箱在堆场的行列层分别是b_i ，l_i ，h_i ，为已知，i∈I_n 。

5）B，L，H为船舶上所有集装箱的总的行、列和层。

6）第i个集装箱在船上的位置可以表示为B_i ，H_i ，L_i ，i∈I_n 。

7）第i个集装箱的装船时间是t_i ，i∈I_n 。

船舶在没有装船时的中心为船舶的几何中心表示为： $\left( {\frac{B}{2},\frac{L}{2},\frac{H}{2}} \right)$ ，船舶在装了集装箱后，重心变为 $\left( {\frac{{\sum\limits_{n = 1}^n {{B_i}{m_i}} }}{{\sum\limits_{n = 1}^n {{m_i}} }},\frac{{\sum\limits_{n = 1}^n {{L_i}{m_i}} }}{{\sum\limits_{n = 1}^n {{m_i}} }},\frac{{\sum\limits_{n = 1}^n {{H_i}{m_i}} }}{{\sum\limits_{n = 1}^n {{m_i}} }}} \right)$ 。为了保持船舶的稳定状态，应该尽可能的使得二者的重心吻合，即

$ \!\min z = {\left( {\frac{{\sum\limits_{n = 1}^n {{B_i}{m_i}} }}{{\sum\limits_{n = 1}^n {{m_i}} }} - \frac{B}{2}} \right)^2} \!\!+\! {\left( {\frac{{\sum\limits_{n = 1}^n {{L_i}{m_i}} }}{{\sum\limits_{n = 1}^n {{m_i}} }} - \frac{L}{2}} \right)^2} \!\!+\! \frac{{\sum\limits_{n = 1}^n {{H_i}{m_i}} }}{{\sum\limits_{n = 1}^n {{m_i}} }}\text{，} $

(1)

通常情况下堆场的集装箱不能摆放的均匀，并且还有重量和航程的原因，所以应减少翻箱，当处于同行、同列、不同层的集装箱，低层的集装箱要先于高层的，那么就会产生翻箱的问题，即

$ \zeta _{ij}^1 = \left\{ \begin{array}{l} 1 \text{，} ({b_i} = {b_j}) \wedge ({h_i} = {h_j}) \wedge ({t_i} = {t_j})\text{，}\\ 0\text{，} else\text{，} \end{array} \right. $

(2)

式中：i ≠j；i，j∈I_n 。

由此可以得到整个堆场中装船中总的翻箱率为：

$ {\rho _1} = \frac{{\sum\limits_{i < j} {\zeta _{ij}^1} }}{n}\text{，} $

(3)

2个集装箱不能摆放在船舱的同一个位置上，因此：

$ {({B_i} - {B_j})^2} + {({L_i} - {L_j})^2} + {({H_i} - {H_j})^2} > 0\text{，} $

(4)

2个集装箱在装船时要有先后顺序，则：

$ {t_i} \ne {t_j},i \ne j,\;\;\;\;i,j \in {I_n}\text{，} $

(5)

在同一行同一列，不同层的集装箱，会先让下层的集装箱装船，因此：

$ {t_i} > {t_j} if ({B_i} = {B_j}) \wedge ({L_i} = {L_j}) \wedge ({H_i} = {H_j})\text{，} $

(6)

集装箱在装船时，会使重量大的箱体放在下面，于是可得：

$ {H_i} > {H_j} if ({B_i} = {B_j}) \wedge ({L_i} = {L_j}) \wedge ({m_i} = {m_j})\text{。} $

(7)

式中：i ≠j；i，j∈I_n 。

在卸载的过程中，同行同列，低层的集装箱先到达港口，则需要进行翻箱，因此：

$ \zeta _{ij}^2 = \left\{ \begin{array}{l} 1 \text{，} ({B_i} = {B_j}) \wedge ({L_i} = {L_j}) \wedge ({H_i} = {H_j}) \wedge ({u_i} = {u_j})\text{，}\\ 0 \text{，} else\text{，} \end{array} \right. $

(8)

产生总的翻箱率是：

$ {\rho _2} = \frac{{\sum\limits_{i < j} {\zeta _{ij}^2} }}{n}\text{，} $

(9)

由上述描述可以建立装船顺序整数规划模型为：

$\begin{split}\\[-12pt] \min \left\{ \begin{array}{l} {f_1} = {\rho _1} + {\rho _2}\\ {f_2} = \min z = {\left( {\frac{{\sum\limits_{n = 1}^n {{B_i}{m_i}} }}{{\sum\limits_{n = 1}^n {{m_i}} }} - \frac{B}{2}} \right)^2} \!+\! {\left( {\frac{{\sum\limits_{n = 1}^n {{L_i}{m_i}} }}{{\sum\limits_{n = 1}^n {{m_i}} }} - \frac{L}{2}} \right)^2}\! +\! \\ \frac{{\sum\limits_{n = 1}^n {{H_i}{m_i}} }}{{\sum\limits_{n = 1}^n {{m_i}} }}\text{。} \end{array} \right. \end{split}$

(10)

$ {\rm {s.t}}. {({B_i} - {B_j})^2} + {({L_i} - {L_j})^2} + {({H_i} - {H_j})^2} > 0\text{，} $

(11)

$ {({t_i} = {t_j})^2} > 0\text{，} $

(12)

$ {t_i} > {t_j} if ({B_i} = {B_j}) \wedge ({L_i} = {L_j}) \wedge ({H_i} > {H_j})\text{，} $

(13)

$ {H_i} > {H_j} if ({B_i} = {B_j}) \wedge ({L_i} = {L_j}) \wedge ({m_i} \le {m_j})\text{，} $

(14)

其中：1≤B_i ≤B，1≤L_i ≤L，1≤H_i ≤H，1≤t_i ≤n；B_i ，L_i ，H_i ，t_i ∈I_n 。

2 利用粒子群算法进行集装箱装船顺序

本文利用粒子群算法对上述装船顺序整体规划模型进行求解，利用二次平方和加权将原目标函数转化为：

$ f = {\lambda _1}{({f_1} - 0.3)^2} + {\lambda _2}{({f_2} - 3)^2}\text{。} $

(15)

式中：λ₁，λ₂ > 0，λ₁ +λ₂=1。翻箱率和稳定性是影响装船顺序的两大因素，本文令λ₁=λ₂=0.5。

利用粒子算法进行装船顺序求解可以描述为^[4]：

1）设定初值b_i ，l_i ，h_i ，m_i ，u_i （i=1，2，…，n）和B，L，H，以及最大迭代次数是N_max，种群大小是M，粒子的边界和最小最大速度为 $x_q^{\min }$ ， $x_q^{\max }$ ， $v_q^{\min }$ ， $v_q^{\max }$ ，q=1，2，…，4n， $\bar M$ 无穷大，获取收缩因子χ。

2）种群中M个粒子的初始位置和速度分别是 $x_p^0$ 和 $v_q^0$ 。且 $x_p^0 = (x_{p1}^0,x_{p2}^0,...,x_{pn}^0)$ ， $x_{pi}^0 = (B_{pi}^0,L_{pi}^0,H_{pi}^0,t_{pi}^0)$ 。设 $w_{pi}^0: = (B_{pi}^0,L_{pi}^0,H_{pi}^0)$ ， $bes{t_p}: + \infty $ ， $gbes{t_p}: + \infty $ ，i=1，2，…，n，p=1，2，…，M，q=1，2，…，4n，设置k：=0。

3）令p:=1， $S\!\!\!:=\! \{ 1,2,...,B\} \times \{ 1,2,...,L\} \times \{ 1,2,...,H\} $ ，则：1）令 $\Omega _p^k:S$ ；2） $D_p^k:(d_{p1}^k,d_{p2}^k,...,d_{pn}^k)\;\Omega _p^k:\Omega _p^k\backslash D_p^k$ ；3）如果 $\exists i,j \in [1,n]$ ， $d_{pi}^k = d_{pj}^k$ 。那么对任意的 $\mathop d\limits^ - \in \Omega _p^k$ ，令 $d_{pj}^k = \mathop d\limits^ - $ ，则执行步骤2，否则继续执行下一步。

4）通过b_i ，l_i ，h_i ，m_i ，可以得到第p个粒子的适应值 $z_p^k$ ，不然令 ${z_p}: = \bar M$ ，继续执行。

5）如果 ${z_p} < bes{t_p}$ ，则 $bes{t_p}: = z_p^k$ ， $x_{best}^p: = x_p^k$ 。

6）如果p < M，则p：p + 1，执行步骤1。

7）令 $tmp: = \mathop {\min }\limits_p bes{t_p}$ ， ${x_{tmp}}: = \mathop {\arg \min }\limits_p bes{t_p}$ ，如果tmp < gbest，则gbest：=tmp， ${x_{gbest}}: = {x_{tmp}}$ 。

8）通过 $v_p^k$ 和 $x_p^k$ 可以得到 $v_p^{k + 1}$ 和 $x_p^{k + 1}$ ，如果 $v_{pq}^{k + 1} < v_q^{\min }$ ， $v_{pq}^{k + 1}: = v_q^{\min }$ ，如果 $v_{pq}^{k + 1} > v_q^{\min }$ ， $v_{pq}^{k + 1}: = v_q^{\max }$ 。令 $v_{pq}^{k + 1} = \left\lfloor {v_{pq}^{k + 1}} \right\rfloor $ 。如果 $v_{pq}^k < v_q^{\min }$ ， $v_{pq}^k: = v_q^{\min }$ ；如果 $v_{pq}^k > v_q^{\max }$ ， $v_{pq}^k: = v_q^{\max }$ ；p=1，2，…，M。

9）如果k < N_max，则k：=k + 1，转到步骤3。

将粒子算法应用于本文所建立的装船模型，设定的迭代次数是200次，学习因子都是1.494，粒子数为48，求得的最优适度值是0.368，其粒子最优适度值曲线如图 1所示。

本文的实验结果可以看出，通过粒子群算法进行装船顺序整体规模，收敛速度快，并且在不断更新粒子位置和速度的过程中，扩大了搜索空间，具有很好的应用效果。