摘要：随着经济的发展，集装箱发展迅速，而这对集装箱码头的运作效率提出了巨大 的挑战。本文针对我国集装箱码头工作机制，探讨了基于贪婪算法的物流堆场策略建模，希望可以为集装箱码头提高运作效率提供支持。

　　关键词：物流堆场;贪婪算法;集装箱

　　1. 研究背景

　　在我国外贸货物中，适箱货已达90%，出口适箱货比重更大，集装箱化率不断提高。同时，“一带一路”集装箱班轮航线陆续增设，通过发展联运业务、延伸物流产业链、拓展经济腹地等，有力促进了物流降本增效、集运业稳健发展。国内外大宗货物运输是经济全球化重要的一环，集装箱码头作为大宗货物主要运输中转站，其运作效率的高低直接影响着整个行业的发展,受到社会大众广泛关注。

　　基于此我们对国内集装箱码头工作机制展开了研究，发现其发展仍然面临着诸多亟待解决的问题。

　　集装箱码头的运作效率主要取决于堆场的堆放规则以及码头内货物运输规则。在堆场内，场桥是集装箱堆场进行集装箱装卸的重要设备,场桥装卸进出口货物的效率是影响集装箱码头整体效率的其中一个主要因素。但是场桥体积较大, 移动速度缓慢,其作业效率极大地限制了整个港口集装箱码头的货物运输作业效率,因此如何提高场桥的作业效率是值得高度关注和研究的问题。为进一步研究如何优化集卡运输进出口货物的作业成本，本文从仅考虑堆场内运输效率入手，探讨在集卡运输时间最短的前提下出场翻箱率最小的集装箱堆放规则。

　　2. 问题描述与假设

　　2.1 问题描述

　　图1：堆场构造

　　上图为典型的集装箱码头堆场构造，堆场区内箱位使用排、贝、层唯一表示，本文中规定同一区段内箱位用三元组(row，bay，tier)表示，其中row 表示排，bay 表示贝，tier 表示层，具有相同排和贝的箱位称为一个堆栈。本文第一部通过改进堆场出口箱堆放规则优化出场箱提货效率。在深入研究限制堆场工作效率的因素后发现其中影响效率的最大两个因素为出场和进场时翻箱率总和和场桥工作横向移动距离。其中的影响因子大于 a 因素。为了缩短场桥工作横向移动距离，规定同组集装箱尽可能集中堆放;为了减小堆场翻箱率，规定出口箱进场堆放时出场时间早的集装箱放在出场时间晚于该集装箱的上层。因此问题可转换为集装箱堆放规划问题，其优化目标为出场箱组进场及出场时场桥横向行走距离总和最小的前提下堆场翻箱率达到最小值。

　　国内典型集装箱码头堆场堆放规则如下：

　　1)场桥提箱及下箱过程为手动控制，场桥运输集装箱过程为机械自动控制，单次工作花费时间长。

　　2)堆场规划基本规则要求对内、外贸箱，空、重箱，进、出口箱分区，韦恩图如下：

　　图2：集装箱分区韦恩图

　　其中特殊箱堆区未画出。

　　3)通用安全堆放规则：在同一贝位选择箱位时，孤立排不能出现堆放后，层高差大于3，提箱后产生的孤立排需要就近减层高(如果同贝内有相同提单号的箱可以优先放)，进场箱补齐旁边的排位后，原来的减高的箱子需要还回去;

　　4)翻箱仅在同一贝中进行;

　　经过对堆场现有运行方式的研究发现存在以下影响集装箱在堆场内运输效率的问题：a)进场时集装箱堆放规则未考虑集装箱未来出场时的时间顺序，将翻箱量最小的目标完全依靠出场时船舶智能配载调度的环节完成，造成翻箱率高;b)未考虑同一目的地的箱组堆放的位置应该尽量集中，降低了外集卡运输效率。

　　2.2 规则优化

　　在原有堆放规则之上，拟定优化出场和进场时翻箱率总和和场桥工作横向移动距离的堆场全局基本堆放规则如下：

　　1)安全规则：相邻堆栈层高差不得大于ΔHmax，底面积较大的集装箱不得堆放在底面积较小的集装箱之上。

　　2)堆放规则：出场时间较早的集装箱堆放在出场时间较晚的集装箱上层。

　　3)同一目的港的集装箱分为一组。

　　2.3 基本假设

　　1. 相邻贝位之间距离为1。

　　2.有足够数量的箱位支持翻箱。3.只考虑20GP、20HQ、40GP、40HQ 的集装箱，不考虑此类型的空想。

　　4. 所有场桥、中控系统支持同尺寸不同箱型的集装箱(支持同尺寸不同箱型的混堆)。

　　5. 集装箱重量不超过场桥限定标准和国家标准。

　　6. 不考虑包括提箱、移箱、拆箱等中控室提出的特殊指令。

　　7. 同时间、同箱位只有一个集装箱待命。

　　3. 堆场箱位三层0-1 规划

　　3.1 符号说明

　　为方便表述，下面称调度时已在堆场的集装箱为“已有箱”，新进场需要调度的集装箱为“新进箱”。

　　T为调度周期内计划进场箱总数;

　　GN 为调度周期内的总出口箱组数;

　　BN、LN、TN分别为堆场区段内的总贝数、总排数和最大堆高;

　　BT为贝中最多可堆存的箱量;

　　Nij为堆栈(i，j)中的已有箱量;

　　Aijg为堆栈(i，j)中箱组g的已有箱量;

　　Bn为出口箱n所属箱组代表数值;

　　Nij=1，进场箱n分配到贝i0，其他

　　Ynj=1，进场箱n分配到贝j0，其他

　　B'ng=1，B'n=g0，其他 为出口箱n所属箱组g的指示变量，若属于箱组g，则取1，否则，取0;

　　BSig=1，■Aijg+■Xni×B'ng>10，其他

　　是堆栈(i，j)中有g组箱的指示变量，若有则取1，否则，取0;

　　tg为出口箱组g的出场时间;

　　t'n为出口箱n的进场时间;

　　tn为出口箱n的出场时间，tn=tBn;

　　Rn为堆放进场箱n引发的翻箱量;

　　STij为堆栈(i，j)最顶层集装箱尺寸;

　　Sn为进场集装箱的尺寸;

　　ΔHmax为堆栈与相邻集装箱允许最大高度差;

　　ΔHmaxij为堆栈(i，j)与相邻集装箱最大高度差;

　　Sni为出口箱n的底面积;

　　Sgi为出口箱组g的体积;

　　θ为堆场已进场TEU与最大TEU 的比值，代表堆场的堆放饱和度。

　　3.2 模型的建立

　　3.2.1 翻箱量的计算

　　n为新进场待分配集装箱，i，j表示规划产生的堆放贝位及排位。首先根据安全规则筛选可堆放的堆栈，在允许堆放的集合中遍历查找符合同组箱占贝位距离最小的贝位，然后在该贝位中遍历查找引起翻箱量最小的栈位。

　　翻箱量Rn的计算是模型的关键之一。集装箱堆栈示意图如下图所示。

　　图3：集装箱堆栈示意图

　　新进箱被分配到该栈，假设堆栈中已有箱数量为Hij若其出场时间晚于箱n =k，则该箱应该插入i = k位置，堆存当前箱的翻箱量为Hij-k。集装箱n分配引起的总翻箱量为：

　　Rn=RT+Rv

　　其中，集装箱出场时间先后引发的翻箱量RT由堆栈已有箱的翻箱率和分配当前箱引发新进箱的翻箱量组成：

　　RT=■Aijg×Ing+■xn,i×yn,j×Inn,

　　Ing=1，P (tn-tg>0)>α0，其他 为在一定机会阈值α下插入位置下的在场箱出场早于当前箱的指示变量，α为人为设定的值。

　　Inn,=1，P (ξ'n-ξ'n>0且ξ''n-ξ''n>0)>α0，其他 为在一定机会阈值α下新进箱出场和进场早于当前箱的指示变量

　　集装箱体积引发的翻箱量Rv由体积堆放规则引发在场箱的翻箱量和引发新进箱的翻箱量：

　　Rv=■Aijg×Ing+■xn,i×yn,j×Inn,

　　I'ng=1，P (sn>sg)>α0，其他

　　表示新进箱进场和出场都早于当前箱的可能性测度大于α时，其值取1，否则，取0。

　　I'nn,=1，P (vn>vn,)>α0，其他

　　表示新进箱体积大于在场箱体积可能性测度大于α时，其值取1，否则，取0。其中P 为事件可能性测度函数。

　　3.2.2三层0-1规划模型根据上述分析，堆场箱位分配问题可分解为第一层决策——选择针对集装箱安全规则可放置的位置，第二层决策——同一箱组优选最小化总的贝间距，第二层决策——优选最小化翻箱量。

　　1)第一层目标函数：选择新进箱的位置时保证其纵向高度差小于安全范围。

　　max{(Hij-HiHj)，(Hij-HijH)}≤ΔHmax

　　2)第二层目标函数：最小化同组箱所占贝的距离之和，以减少装船时龙门吊横向行驶时间和成本，同时有利于降低翻箱率。

　　s.t.■xni=1，n=0，1，2，…，T-1■■Aijg+■xni≤BT，i=0，1，2，…，BTxni∈{0，1}，n=0，1，2，…，T-1，i=0，1，2，…，BN-1

　　第一个约束方程为箱流约束，表示每个进场箱仅分配一个贝位;第二个约束方程要求贝中箱量不超过最大堆存量;第三个约束方程是0-1 决策变量约束。

　　3)第三层目标函数：最小化翻箱总量。

　　第一个约束方程为箱流约束，表示进场箱都要分配且只能分配一个栈位;第二个约束方程要求堆栈堆存集装箱高度不超过最高安全个数;第三个约束方程是0-1决策变量约束; 最后两个函数代表翻箱量约束。

　　4. 算法建立与分析

　　4.1 算法初始状态设置

　　设置单个堆场内贝数BN 为17，排数LN 为9，层高TN 为3。

　　即堆场内理论容纳箱的数量为459，规定场内最大饱和率θ为0.8，即可堆放箱的数量为367 个。

　　4.2 算法分析

　　在单个进场周期内进场箱量T。在最坏的情况下，为每一个进场箱寻求一个最佳的堆放堆栈位置，遍历搜索的空间大小为2 的T*(17 + 9)次方。且其中影响每个集装箱进场、出场时间的分布是与实际相关的非线性关系，具有很大的不确定因素，由此可见问题是NP-HARD 问题。

　　为了求解算法，采取了基于经验选择的贪婪思想，并针对单一作业周期内箱量T，按同一箱组的出场时间期望由大到小排序和各个箱组内进场时间期望由小到大排序，编号1-T。

　　之后按照1-T 顺序选择堆栈位置，在选择的每一步过程中，都是基于经验的当前的局部最优解。

　　基于贪心策略的启发式算法的基本流程为，在第一层选择符合安全规则堆栈位置，并作为第二层目标函数的当前堆场状态。在第二层搜索中为集中堆放同组箱选择最优贝位，并作为第三层的条件。在第三层搜索中为最小化翻箱量进行排位搜索。

　　堆栈分配的算法步骤具体如图。

　　图4：基于贪心策略的启发式算法流程图

　　5. 实验结果与分析

　　5.1 算例选取

　　以重庆市果园港的运营数据为基础，生成随机时间分布的算例数据：首先处理果园港运营原始数据，获取港口吞吐量、各类集装箱运载比例等必要数据;然后，按分布模拟生成集装箱进场时间、出场时间及目的港数据。最后，利用以上所述方法模拟生成一个月的数据，利用前10 天的进出口箱量数。设置码头规模为堆场区段20 个，一个堆场内贝位17 个，理论最大堆存集装箱数量459 个。

　　图5：2018 年集装箱船到达码头相关数据

　　图6：2018 年集装箱船运出码头相关数据

　　对原始数据进行分析发现后半年果园港的吞吐量高于上半年，为了体现改进后堆放规则处理的高效性，选取吞吐量大的六个月的集装箱吞吐量平均值作为算例中一个月的数量。20 尺箱和40尺箱的数量基本稳定在2.5:1 的比例上，因此设置30天内集装箱吞吐量为8767个，目的港数量设置为10 个，机会阈值α设置为0.95。

　　算法利用python 编程实现，对8767 组算例进行实验分析。

　　5.2 结果分析

　　在算例设置的条件下，对比利用果园港原始堆放规则和改进后规则一个月内产生的总翻箱量及同箱组贝位距离总和可得。

　　表1：两种规则下同箱组贝位距离

　　表2：两种规则下翻箱总量

　　改进后的堆场堆放规则算法与原有规则所得同组箱所占贝间距离的比较结果可知，改进后的堆放规则计算得到同组箱所占贝间距离大部分均得到了20%以上的缩小。改进后的堆放规则计算得到翻箱率大部分得到了13%以上的减少。

　　6. 结论

　　针对出场时间不确定条件下的集装箱堆场堆栈分配问题做了深入研究，考虑到场桥横向行走效率的低下，设计了基于贪心策略的启发式算法策划方案。采用蒙特卡罗方法生产对方案进行算例验证，结果表明与原有堆场规划方案相比，在同样的堆场条件下，优化后的堆场堆放规则在同箱组贝位距离降低20%的前提下降低了约13%的翻箱量。由此可见优化后的堆场规划方案能更好地处理集装箱码头吞吐量加大的情况，提升了堆场工作效率。C

　　(作者单位：重庆巴蜀常春藤学校)

　　参考文献

　　[1]郑斐峰, 蒋娟, 梅启煌. 最小化集装箱运输成本的配载优化[J]. 计算机科学, 2019,46(06):239-245.

　　[2]郑建鹏. 基于Markov链的集装箱码头设备资源协同作业研究[D].浙江工业大学，2020.

　　[3]陆书翔, 吕长虹, 秦涛. 集装箱码头桥机调度问题基于完工时间下界的算法[J]. 运筹学学报, 2020(3):67-76.