航运业快速发展,船舶在航运中的集装箱种类越来越多,并且航程规划更加复杂,中途停靠的码头也更多,若集装箱在船舶的放置位置及停靠时的装卸顺序不合理,极易增加停港时的倒箱作业,同时导致港口物流设备使用率低。所以港口集装箱装卸问题成为现代物流重要的研究方向。
港口集装箱装卸顺序可以抽象为一个NP模型,对船舶集装箱的位置规划、港口泊位方向、装卸顺序及配载等都可以利用数学元素进行描述,最终建立其数学模型,且模型的约束条件是减少倒箱作业量及提高港口物流设备利用率[1],最终目标是提高整个船舶物流效率。
现有的解决NP模型的算法有蚁群算法、神经网络算法、遗传算法等,其中遗传算法中的交叉及变异更适用于解决船舶集装箱装卸模型。
最后本文给出了基于遗传算法的船舶港口集装箱装卸模型解决方案,并进行了仿真。
1 船舶集装箱作业系统与传统的码头集装箱装卸不同,其进口与出口中一系列由人工完成的验收、确认、发证、提单、交接流程都可通过计算机自动实现[2]。现代化的船舶集装箱作业流程分为签证模块、泊位申请模块、港口堆场计划模块及集装箱卸载顺序模块。
现代作业流程模块划分如图 1所示。
① 签证模块
通过因特网与港口管理部门连接,进行停靠泊位及集装箱装卸申请。
② 泊位申请模块
港口管理人员根据船舶的申请信息及本港口的泊位空闲数,为船舶分配最优的泊位,并进行指导、监控及收费。
③ 港口堆场计划
根据现有的堆场集装箱堆放及船舶上报的需要卸载的集装箱种类、数量、距离等信息,合理安排堆场计划。
④ 船舶集装箱卸载顺序
船舶根据自身的航行状态,接收到泊位及堆场情况合理安排装卸顺序。
2 基于遗传算法的集装箱装卸顺序 2.1 集装箱装卸顺序模型建立下面从港口码头堆场、船舶位置、港口顺序开始定位,给出了模型的约束条件,最后从经济性及可操作性方面给出了目标函数。
1)码头堆场、船舶放置位置、港口顺序定义[3]
码头按照规定的街区、层次及行列来描述集装箱堆放位置。
船舶方位的集装箱位置同样可用贝号、行号及层数作为放置的集装箱位置描述,且分为甲板上及甲板下,设
港口顺序则以船舶依次停靠的港口为起点,设第一个停靠的为1,最后停靠的为N,则港口用
2)模型约束条件
约束条件主要考虑稳定性,从行高、层重、船舶装卸集装箱倾斜度等进行了限制。出于篇幅限制,下面着重从层重角度给出约束条件。
航运船舶在设计时限制了每个层面的载重,假设层面为ViVk ,其额定重量阀值为Wlimit ,放置集装箱后的载重表达式为:
$ W_{Vj}(k) = \sum\nolimits_{k = 1}^K {W_{ViVkVj}} \text{,} $ | (1) |
其中,WViVkVj 为此层面每个位置放置的集装箱重量,则约束条件为:
$ W_{Vj}(k) < W_{\lim it}\text{。} $ | (2) |
3)目标函数
港口集装箱装卸顺序的合理按照最终需要从经济性及可操作性两方面进行考量[4]。
① 经济型目标
经济型最主要是要介绍船舶停靠港口的倒箱作业,目标函数为:
$ \mathop {\min }\limits_{1 \leqslant j \leqslant t} f = \sum\nolimits_{q = 1}^n {Li_{qj}}\text{,} $ | (3) |
式中,n为港口堆场可放集装箱数;T,J表示停靠港口数及每个港口的装卸数;iqj 为船舶排序为j的集装箱装卸至排序为q堆场位置编号;Liqj 为iqj 装卸中需要的倒箱数。
② 可操作性目标
可操作性目标最终需要考量其吊桥的装卸效率及堆场的堆放效率,目标函数为:
$ \mathop {\min }\limits_{1 \leqslant j \leqslant t} f = \sum\nolimits_{q = 1}^n {|i_{(q + 1)j} - i_{qj} - 1|} \text{。} $ | (4) |
遗传算法是一种利用生物演化规律的自适应全局搜索算法,集合了机器学习及自适应控制原理,整个过程分为种群选择、编码、交叉、变异几大步骤[5],下面进行详细说明。
① 集装箱装卸的初始种群设置
在此对船舶装载的所有集装箱进行排序,排序后的表为S,对每个箱子给一个编号,设集装箱数量为n,编号记为:
$ S = (s_1, s_2, s_3 \cdots s_n) $ | (5) |
随机选择一个装卸顺序设置初始种群,进行周期循环。
② 编码
遗传算法的编码有格雷编码、浮点数编码、交差编码等方式,在此采用Grefenstette编码方式。
假设船舶需要装卸集装箱列表为W,对于一个初始装卸种群
最终找到全部装卸箱子的序号gi :
$ G = (g_1, g_2, g_3 \cdots g_n)\text{。} $ | (6) |
③ 交叉过程
交叉有多点交叉、单点交叉、均匀交叉及算术交叉几种方式,在此选择算术交叉。
算术交叉是一种线性过程,其交叉前及交叉后的个体满足线性分布,假设
$ X_A^{t + 1} = aX_B^t + (1 - a)X_A^t\text{,} $ | (7) |
$ X_B^{t + 1} = aX_A^t + (1 - a)X_B^t\text{。} $ | (8) |
其中,a为线性变换的系数。
④ 变异过程
同样,变异有边界变异、均匀变异、非均匀变异、基本位变异几种方式,结合船舶集装箱装卸问题特点及选择的Grefenstette编码方式的适用范围,在此选择了均匀变异。
船舶每进行一次集装箱装卸后,其变异因子
本文最后对基于遗传算法的船舶集装箱装卸算法进行了仿真,给出了与传统的装卸方法在经济性能提升百分比结果,并与神经网络及蚁群算法进行了比较,如表 1所示。
本文从码头堆场、船舶放置位置、港口顺序对港口集装箱问题进行了定义,给出了约束条件及目标函数,最后给出了基于遗传算法的解决方案。
[1] | 李海民, 吴成柯. 遗传算法性能与所求解问题关系的研究[J]. 西安电子科技大学学报, 1999, 26 (6): 752–757. |
[2] | 丁以中, 费红英, 韩晓龙. 港口集装箱流研究现状与分析[J]. 上海海运学院学报, 2004, 25 (2): 45–54. |
[3] | BOTTER R C, BRINATI M. A. Stowage Container Planning:A Model for Getting an optimal Solution. Computer Applications in the Automation of Shipyard Operation and Ship Design, IFIP Transactions B (Applications in Teeh.), 1992:217-229. |
[4] | CHANG F, DEAN J, GHEMAWAT S, et al. BigTable:A distributed storage system for structured data[J]. ACM Transaction on Computer Systems, 2008, 26 (2): 12–26. |
[5] | WILSON I D, ROACH P A. Principles of combinatorial optimization applied to containership stowage planning[J]. Journal of Heuristie, 1999, 5 : 403–418. DOI: 10.1023/A:1009680305670 |