易应强 金丹 余丹炯 韦燚
（天津港股份有限公司 300461、上海振华重工（集团）股份有限公司 200125）
摘要：集装箱堆场箱位分配策略对作业效率和空间利用影响较大，将堆场装卸作业时间成本和堆场空间成本作为优化目标，建立箱位分配的数学模型，分别采用贪心算法、遗传算法进行求解，并与三种传统堆垛方式对比。计算结果表明，贪心算法与遗传算法生成的相对传统堆垛方式优势显著，模型中双优化目标权重系数随堆场拥挤程度变化会有更好的效果。
关键词：集装箱；箱位分配；贪心算法；遗传算法
0 引言
目前港口已经可以实现自动化作业，而自动化港口集装箱堆场中箱位如何分配是一个较为重要的问题，高效的分配策略能大大提高作业效率。集装箱进入堆场的箱位分配策略对作业中的搬运距离、翻箱次数以及堆场空间利用影响较大。随着集装箱堆场的规模增大，人工分配箱位计划性差、堆场利用率低、翻箱次数高等缺陷愈发显著，而通过计算机来自动分配可有效改善这些问题。
对于箱位分配策略的研究，主要集中于作业成本的最小化，而不同的研究中采用了不同的目标函数来表征作业成本。在不同的堆码模型中，分别定义了堆场的叠压度、自由度、翻箱量等概念，用于权衡堆垛作业中的作业成本。江南等 [1]通过划分堆场集装箱集合，建立了静态码垛模型；关于集装箱的对方顺序定义了全序关系，建立了动态的码垛模型，并设计了对应判定、码箱、取箱算法；再考虑取箱时暂扣空箱，建立了循环箱码垛模型，设计了对应码箱、取箱算法。王金红 [2]首先根据运输货物性质划分箱大区，根据物流情况和常见货主划分箱小区；其次，提出大宗货物自由度与零散货物叠压度的定义；在之前基础上，建立了大宗货物集装箱码垛模型和零散货物集装箱码垛模型，设计了堆垛算法，并验证了算法的可行度。谢颖 [3]考虑了翻箱的原因、对作业成本和效率的影响，归纳了降低翻箱量的策略，建立了以码箱取箱成本最低为目标的码箱箱位优化模型，并通过模拟仿真验证了模型的可行性。
1 问题描述
1.1 码头作业方式
图1.1 自动化码头示意图
如图1.1所示，为一个码头的简易示意图，港口衔接了海运与陆运两种运输方式。来自海运的集装箱通过岸桥从船舶上卸下后，通过港口内部集卡、AGV等水平搬运设备与堆场门吊进入堆场，等待下一步作业；来自陆运的集装箱直接通过堆场门吊直接进入堆场，等待下一步作业；而在堆场内的集装箱，通过陆运离开则直接由门吊装载至外部集卡、列车等运输工具上，通过海运离开则通过岸桥装载至船舶上。
在如今通信技术较为发达的时代，船舶、列车等运输方式均具备一定的计划性，可以根据计划、天气等因素，对其到达港口的时间进行预测，即可以由此来预测对应集装箱离开堆场的时间，计算出压箱情况下发生翻箱作业的可能性。
1.2 传统堆垛方式
人工作业传统堆垛方式主要有垂直式、平铺式、阶梯式三种。
（1）垂直式堆放：集装箱由离列车轨道较远的一侧堆往靠近列车轨道一侧，堆满一栈才队下一栈。这种堆码方式的优点是堆垛较为紧凑，空间利用率高；缺点是容易导致压箱，取箱时需要进行翻箱作业，增加作业成本。
（2）平铺式堆放：集装箱由最下面一层往上堆，堆满一层才开始堆上面一层。这种堆码方式优点是在集装箱不多时取箱方便，不易产生压箱现象；缺点是堆垛不紧凑，空间利用率低，所需面积大。
（3）阶梯式堆放：集装箱以阶梯的方式堆垛，特点介于垂直式与平铺式之间。
2 箱位分配模型
2.1 模型假设
（1）待分配箱位的集装箱均为普通集装箱，不考虑特种箱；
（2）引入集装箱属性概念，属性根据集装箱离场情况划分，同批次离开堆场的集装箱属性相同。同属性的集装箱会一起离开堆场或者在上方的优先离开，即同属性箱之间不会发生翻箱作业；
（3）不同属性的集装箱堆叠在同一栈一起称为压箱。产生压箱时，若下面的集装箱先离开堆场，则须进行翻箱作业。
（4）集装箱离开堆场关于时间的概率密度函数可以由统计得知；
（5）待分配集装箱只有40英尺标准集装箱堆垛；
（6）不考虑作业目标箱位的堆垛高度，都视为需要相同时间的堆垛过程；
2.2 符号说明
.png)
2.4 目标函数
（1）减少搬运距离
发送箱、中转箱需要考虑与将要装载列车车厢的距离，因为列车采用脱钩甩尾的方式，越靠近最终目的地的集装箱越应放在列车靠前部分，所以考虑减少起重机搬运距离的情况下，集装箱应尽量靠近预计装车位置。
.png)
3 模型求解
3.1 求解算法
（1）贪心算法——单箱局部最优
由以上模型描述可知，每个集装箱将要堆放的位置为因变量，目标函数的值受到多个因变量的影响。同时，因变量之间也会互相影响。此外，因变量——集装箱箱位分配策略的变化与目标函数大小变化的之间的数学关系较为复杂，并不直观，即无法通过因变量的变化大致判断目标函数的变化趋势。对于此类数学模型，因变量越多，则求解难度越大，计算复杂度越大。因此将一组多个集装箱的箱位分配问题转化为多组单个集装箱的分配问题，对每个集装箱分配当前根据模型判断出的最优箱位，由此生成一组集装箱的箱位分配策略。该策略不一定是全局最优解，但一般为相对较优解。
（2）针对箱位优化的遗传算法
本模型的优化对象为集装箱的分配箱位，直接将优化对象作为染色体进行优化，以数学模型中对箱位分配策略的优化目标函数（优劣评估函数）的倒数作为适应度，设计一种遗传算法对模型进行求解。
染色体编码规则：对于个集装箱的堆码问题，染色体分为段，其中每一段为对应集装箱分配的垛位，具体数值由贝号和列号计算得到：(贝号－1)×6+列号，例如：4对应1贝4列，15对应3贝3列，36对应6贝6列。染色体则由个这样的数值组成，如对10个集装箱的堆码问题，染色体{4，15，36，11，25，15，14，36，8，2}，代表着堆码策略{1贝4列，3贝3列，6贝6列，2贝5列，5贝1列，3贝3列，3贝2列，6贝6列，2贝2列，1贝2列}。
（3）针对贪心算法求解顺序优化的遗传算法
上一个算法主要存在两个问题：第一，堆场箱位数量较大，解空间过大，找到最优解难度较大；第二，初始化、交叉、变异过程中可能会生成不合格的染色体，需要剔除后重新生成合格的染色体，由此在特定条件下可能导致计算量过大或者死循环。因此，设计对贪心算法求解顺序进行优化的遗传算法，寻找最优顺序来进行贪心算法，获得较优解。
染色体编码规则：对于个集装箱的堆码问题，染色体分为段，其中每一段为对应集装箱进行箱位分配的优先度值，优先度值较小的集装箱先分配箱位，如对10个集装箱的堆码问题，染色体{ 0.4912 ，0.4122，0.7346 ，0.9985 ，0.2822 ，0.2395 ，0.6673 ，0.9282 ，0.8333 ，0.5543 }，代表着求解顺序{ 6→5→2→1→10→7→3→9→8→4 }，按该顺序采用贪心算法进行计算即可得对应箱位分配策略。
3.2 计算结果对比
将三种传统堆码方式：垂直式堆码、平铺式堆码和阶梯式堆码和上文中描述的两种算法：贪心算法和通过遗传算法优化计算顺序的贪心算法进行模拟仿真对比堆码效果。因为在具体计算中发现采用遗传算法直接对箱位进行优化，优化效果一般且计算时间很长，在算例中并没有分析直接对箱位进行优化的遗传算法，故下文中的遗传算法指的是针对贪心算法计算顺序优化的遗传算法。
（1）五种箱位分配策略对比
如图3.1所示，垂直式堆码预计作业所需时间较长，主要原因是预计翻箱率较高，但优点是占用箱位较少；垂直式堆码作业预计翻箱率相对垂直式和阶梯式较低，但占用箱位最多；阶梯式效果介于垂直式与平铺式之间；采用贪心算法求解的堆码策略在预计作业时间、预计翻箱率方面，相对三种传统堆码方式都有很大的优化，占用箱位数方面有所优化；而采用遗传算法优化计算顺序的贪心算法求解结果，相对于贪心算法各方面都有所优化，但优化幅度并不大。
.png)
图3.1 五种箱位分配策略对比
（2）空间利用率权重系数对堆垛效果的影响
空间利用率权重系数在模型中是一个较为重要的参数，其对于时间成本和空间成本的侧重有较大影响，在港口不同时期应采用不同的空间利用率权重系数。
.png)
图3.2 不同空间利用率优化效果
如图3.2所示，作业时间成本与空间利用率权重系数呈正相关，空间成本与空间利用率权重系数负相关。也就是说，在港口业务清闲，堆场空间资源相对富余时，可以采用较小的空间利用率权重系数，以降低作业成本；在港口业务繁忙时，堆场空间资源紧缺时，应采用较大的空间利用率权重系数，以提高堆场空间利用率。
4 结论与展望
本文主要研究了集装箱堆场箱位分配问题，将作业时间成本和堆场空间成本作为优化目标建立箱位分配数学模型，分别采用贪心算法、遗传算法进行求解，并与三种传统堆垛方式对比，验证了模型的有效性。
但本文中模型假设简化较多，考虑的是理想情况下的堆场。此外，堆场箱位分配问题只是港口智能化的一个小问题，后续研究可能需要着重于以下几点：船舶、列车等运输设备的到达时间预测问题、堆场门吊的多机协作调度问题、岸桥与堆场间运输调度问题等。
参考文献
[1] 江南,钱迈,渠洪涛,史峰.集装箱堆场作业计划模型及算法[J].铁道学报,2009,31(05):8-16.
[2] 王金红. 铁路集装箱堆场码垛模型与算法[D].中南大学,2010.
[3] 谢颖. 港口集装箱堆场码垛优化模型及算法[D].中南大学,2011.
[4] Panagiotis Angeloudis,Michael G.H. Bell. An uncertainty-aware AGV assignment algorithm for automated container terminals[J]. Transportation Research Part E,2009,46(3).
[5] 盟岩.中国港口:“空无一人”正引发“码头革命”[J].中国港口,2017(08):3.
[6] 欧美集装箱码头自动化的进程与启示[J].大陆桥视野,2017(08):28-31.
[7] S.H. Chung,K.L. Choy. A modified genetic algorithm for quay crane scheduling operations[J]. Expert Systems With Applications,2011,39(4).
[8] Bong Joo Jeong,Kap Hwan Kim. Scheduling operations of a rail crane and container deliveries between rail and port terminals[J]. Engineering Optimization,2011,43(6).
[9] 靳志宏,毛钧,李娜.基于混合动态规划的集装箱堆场贝位内翻箱作业调度优化[J].交通运输系统工程与信息,2011,11(06):131-136.
基金课题：19511105000自动化集装箱装卸设备智能维护系统关键技术研发与应用