港口集装箱空箱调度的遗传算法优化

杨 扬，王 迪

（1.厦门海洋职业技术学院，福建 厦门 361012；2.大连海事大学 交通运输管理学院，辽宁 大连 116026）

随着经济全球化、贸易国际化的深入发展，国际海运业得到迅猛发展，集装箱运输具有运量大、装卸及疏运快、节约包装材料、安全便捷等优点，越来越多的散杂货选择集装箱运输，所以，集装箱运输已成为全球国际贸易中最重要的运输方式之一。然而集装箱海运业的繁荣对其自身的经营管理模式及网络结构提出了更高要求，高效、有序的港口集装箱运输网络有待完善与优化。由于地区间经济贸易的不平衡性以及船运公司集装箱管理水平存在差异，空箱调运在整个集装箱运输系统中占据了大量比重。研究如何减少集装箱空箱调运，对于促进集装箱运输快速发展、协调多式联运、提高企业经济效益具有重要意义。

由于空箱调运产生的成本对船公司的运营收益产生了很大影响，船公司对该问题非常重视，并引发了学术界的研究兴趣。集装箱调运问题主要研究的是何时从何地将多少数量的空箱通过何种运输方式调运到有需求的指定地点。空箱调运问题具有随时间推移供需地发生变化的动态性，箱种、节点、运输工具众多的复杂性，以及空箱需求与供给的随机性和运输能力及供应时间的限制性等多方面特性。由于空箱调运问题中过程参数、不确定因素众多使问题相当复杂。当前国内相关专家、学者对此问题进行了较多的研究，取得了相当的成果，并对实际运营过程做出有益的参考。其中，施欣对海上空箱调运的过程进行分析，并建立了系统优化模型[1]；刘恒江等以航线经营人为主体，建立了空箱调运的Petri网模型[2]；周红梅等借鉴了铁路空车调度优化模型，建立了海运空箱调运优化模型[3]；Florez等建立利润优化模型来研究远洋航运企业空箱租赁和重新配置问题[4]；Shen等构建了海运空箱调运决策支持系统[5]。

然而这些研究在建立模型时都进行了大量假设，考虑因素较少，与实际系统相差较远，大大降低了模型的实用性。本文拟在考虑多箱种的情况下，建立合理的空箱调运动态优化模型，并运用遗传算法进行优化求解，并用某港口实例数据对模型进行了验证，证明了模型的正确性和遗传算法的有效性。

1 空箱调运模型

本文将建立多箱种情况下的空箱调运模型，目标函数为在满足重箱运输的前提下，使空箱调运的总费用最少。总费用由以下几种费用组成：空箱的运输费用、在各节点的储存费用以及租箱费用。

1.1 模型假设

（1）每一期每个节点的空箱数量已知、每个节点的空箱需求量已知；（2）不考虑集装箱的维修、报废情况，即所有集装箱均是可用的；（3）不存在转运现象，空箱是直接由供应地向需求地的直达运输；（4）各航线的集装箱运输不允许不同箱型相互替换；（5）考虑两种箱型：20英尺和40英尺；（6）空箱调运决策期为1周（5天计算），决策间隔以天计算；（7）需求客户的需求必须得到满足，不存在弃货问题；（8）只有到时段末还未运送的集装箱发生堆存费用。

1.2 模型建立

根据以上假设及其空箱调运实际情况，可以建立如下空箱调运模型，相关参数和变量规定如下：

1.2.1 参数

T：为计划周期；Dt：t时段时所有需求点的集合；St：t时段是所有供给点的集合；：t时段节点i缺k种箱型的数量；：t时段节点j能供应k种箱型的数量；M：所有供给点和需求点的集合；K：各种箱型的集合，包括20英尺和40英尺两种；：在时段t从i到j运输第k种箱型的单位运输费用；：在时段t从i到j运输第k种箱型的箱量；：在时段t节点i的第k种箱型的存储量；：节点i的存储能力限制；：在时段t节点i的k种箱的单位存储费用；：在时段t节点i和j之间由k种箱运输的调运量；τij：从节点i到j得运输时间；：运输能力限制；：系统外调箱的单位费用；：系统外调箱量；：t时段m点本地产生的空箱。

1.2.2 目标函数

目标函数考虑各期在需求客户和供给客户之间的空箱调运费用最少。

1.2.3 约束条件

约束条件（2）表示客户的集装箱需求量必须满足。

约束条件（3）表示各时段末各节点处的空箱库存。

约束条件（4）表示各时段供应节点的供应量。

约束条件（5）表示在各个时段，节点之间的运输量不能超过该种运输方式的运输能力。

约束条件（6）表示各节点的存箱量不能超过该点的容量。

2 遗传算法原理

遗传算法（Genetic Algorithms，GA）是由美国Michigan大学的John H.Holland教授创建的，它模拟了自然选择和进化过程中的繁殖、杂交和突变现象。其基本思想为：按照“适者生存”和“优胜劣汰”的原理，从优化问题一个种群（即一组可行解）开始，逐代进化产生出越来越好的一个新的种群（一组的可行解）。在每一代，根据个体（可行解）适应度（目标函数值）的优劣挑选一分优良个体复制（繁殖）到下一代，被选择的个体经过交叉和变异算子的作用生成新的一代，新的个体由于继承了上一代的一些优良性状，因而在性能上优于上一代，这个过程将导致种群类似自然进化一样，子代种群比父代种群更加适于环境，也就是生成新的可行解优于旧的可行解，最后，将整个进化过程中最优个体作为问题的最终解。

由于遗传算法对适应度函数没有连续可微的要求，具有高效的全局优化能力，并且其操作对象是编码个体，可以处理诸如矩阵、树和图等结构形式的对象，因此在解决高维复杂优化问题上显示出很强的生命力，在实际中得到了广泛的应用。基于遗传算法的特点和空箱调运问题的特征，本文采用了遗传算法对该问题进行优化。

3 算法描述及其实例

3.1 算法设计

（1）编码方案：根据本文模型决策变量的特征，本文采用多维的实数编码形式。例如，用实数集合M=｛1, 2 ,…,n｝表示港口集合，K=｛1,2｝表示箱型（20英尺和40英尺），则t时段的一个可行解表示为：

这个解直观的表达就是：港口1向港口2调运x1个集装箱（箱型是20英尺），港口5向港口3调运x2个集装箱（箱型是40英尺），……。

（2）选择：采用轮盘赌选择算子，这虽然增大了遗传算法的随机性，但保证群体的多样性，使算法不至于过早收敛。

（3）交叉：交叉运算是遗传算法区别于其他进化算法的重要特征，它在遗传算法中起关键作用。由于基本交叉算子单点交叉、多点交叉不能满足本文空箱调运问题的特殊性要求（它们都会产生大量不可行解），所以本文采用的交叉算子为循环交叉算子，该算子能修正交叉过程中生成的不可行解。

（4）变异：变异是指将个体编码串中的某些基因值用其它基因值来替换，从而形成一个新的个体。遗传算法中的变异运算是产生新个体的辅助方法，它是必不可少的一个运算步骤。变异本身是一种全局随机搜索，与选择算子结合在一起，保证了遗传算法的有效性，使遗传算法具有全局的随机搜索能力，同时使得遗传算法保持种群的多样性，以防止出现非成熟收敛。本文在考虑编码设计及问题实际的情况下采用均匀变异算子对种群进行变异操作。

算法流程图如图1所示。

图1 算法流程图

3.2 实例

本文考虑六个港口的空箱调运问题，算例中假设运输能力和堆存能力无限制，只考虑一种箱型（40英尺），在一个计划期内，航线挂靠顺序不变。这六个港口的运输网络模型如图2所示。港口运输时间、费用如表1所示。港口初始库存和各时段需求状况分别如表2、表3所示。

图2 运输网络图

表1 港口间的运输时间、费用表 单位：天、$/TEU

表2 港口空箱基本数据

表3 港口需求表 单位：TEU

该算法利用matlabR2009程序实现，取最大迭代数G=500，本文针对不同种群规模进行了大量测试，结果表明当种群规模N=100左右时效率最高；对交叉概pc为0.7、0.8、0.9分别进行了10次试验发现交叉概率的变化对算法的效率影响并不是很大，所以取交叉概率pc=0.8。最后，我们进行了三组实验，分别取变异概率pm为0.001、0.01、0.1，由实验结果分析得出当变异概率时pm=0.01，效果最好。最终得出最优解，第一期调运结果：由港口B至A调运空箱80个，由E至C调运空箱163个，由F至E调运空箱10个，总费用为6 119美元，其中库存费用为2 158美元；第二期调运结果：由B至A调运空箱75个，由E至A调运空箱9个，由C至E调运空箱13个，总费用为5 051美元，其中库存费用为3 014美元；第三期调运结果：由B至A调运空箱119个，由E至C调运空箱110个，总费用为6 734美元，其中库存费用为3 065美元；第四期调运结果：由B至C调运空箱24个，由A至E调运空箱23个，由D至E调运空箱200个，总费用为8 738美元，其中库存费用为2 065美元；第五期调运结果：由B至A调运空箱76个，由E至C调运空箱125个，由D至E调运空箱46个，总费用为6 938美元，其中库存费用为3 075美元，租箱费用为315美元。这一周期的总费用为33 580美元。

4 结 论

本文力求与实际情况接近，充分考虑了空箱调运问题中多箱型的现实情况，应用动态规划的思想，建立了多箱型的集装箱空箱调运优化模型。最后，本文运用遗传算法对所建立的模型在matlab平台下进行了编程仿真，为港口间空箱调运提供了具体的方案。本文模型的目的在于提高航运企业的空箱调运管理水平和调运效率，节省不必要的运输费用。

[1]施欣.集装箱海运空箱调运优化分析[J].系统工程理论与实践，2003(23):70-75.

[2]刘恒江，施欣.基于Petri网的集装箱空箱调运方针分析[J].交通运输工程报，2002,2(3):97-102.

[3]周红梅，方芳.航运集装箱空箱调运优化模型的研究[J].武汉理工大学学报，2003,2(7):384-387.

[4]Florez.H.Empty container Repositioning and Leas2ing:An Optimization Model[R].Ph.D Dissertation,Polytechnic Institute of New York,New York,1986.

[5]W.S.Shen,C.M.Khoong.A DSS for empty container distribution planning[J].Decision Support Systems,1995(15):75-82.

[6]王斌.海运空箱调运模糊优化研究[J].港工技术，2007,8(4):11-13.

[7]王小平，曹立明.遗传算法—理论、应用与软件实现[M].西安：西安交通大学出版社，2002.

[8]赵道致，黄健.基于海陆运整体成本的集装箱空箱调运优化研究[J].北京交通大学学报，2008,7(4):48-52.