基于贪心算法的集装箱码头岸桥调度问题的研究

李言

天津港太平洋国际集装箱码头有限公司  天津市 300463

摘要：针对集装箱港口岸桥调度过程过度依赖人工的问题，本文综合虑40 尺、20尺集装箱混合堆叠、船舶稳性等多种实际因素，提出了基于贪心算法的岸桥调度算法。通过实际作业数据验证可知，此算法在满足各项约束条件下，编制合理的岸桥作业计划，能帮助减轻港口编制岸桥计划的工作量，提高计划合理性，进行准确的港口资源测算，给港口带来人力物力上的节省和切实的经济效益。

关键词：岸桥调度、集装箱混合堆叠、贪心算法、船舶稳性

引言

随着各国经济迅猛发展，海上贸易越来越频繁。为了满足激增的集装箱装卸量要求和船舶公司对集装箱港口服务水平要求，港口必须建立高效的生产调度系统，尽可能提高物流运营的效率。岸桥作为港口主要的装卸设备，优化其作业计划可缩短船舶在港时间和降低码头设备能耗从而提高港口生产运营效率和服务水平。

然而，相比于国外的先进港口，我国的港口生产自动化水平还不高，很多实际生产作业过程在靠工作人员的经验实施。对此，本文设计了符合抹高和船舶稳性等许多实际生产场景要求的岸桥调度算法，得出高质量岸桥作业计划。一般高质量的岸桥作业计划可节省单船在港时间30分钟，全年预计可节省因人员和机器调度、船期损失、码头占用等原因造成的费用超1亿元，社会经济效益显著[1]。

1岸桥调度问题描述

港口的作业场景如图1所示。假设有一艘船舶进入港口，港口根据集装箱配载报文得到装卸集装箱信息，再把装卸任务分给岸桥作业。岸桥调度算法要在满足各种约束条件和实际需求场景下，以尽可能减少单船完工时间和所用港口资源为目标，输出每条作业线的作业序列。

图1 港口集装箱作业图

船舶装卸过程中的诸多约束条件极大地增加了本问题的复杂性。有如下约束：装卸任务之间存在先后关系；岸桥之间不能交叉；部分位置的任务不得同时进行；各种类的集装箱的作业时长也不同；所处船舶位置高度不同的集装箱使用不同类型的岸桥进行作业；40尺的集装箱只能一个一个被岸桥作业；20尺的集装箱可以一个一个被作业，而一个大贝位所关联的两个相邻小贝位的两个重量差距不大的20尺的集装箱要同时被作业；岸桥工作时长最长不能长于所有岸桥平均作业时长一小时，最短不能短于所有岸桥平均时长一小时。

2基于贪心策略的智能岸桥调度算法

2.1 数据预处理算法

数据预处理第一部分为编号过程。编号的目的是使得分线时能够精准地将集装箱组进行分割和保证集装箱组内作业顺序合理。本文将集装箱分为上中下层三种集装箱。上层集装箱编号逻辑是指，按照进出口作业的层数优先规律和从靠岸侧到靠海侧的顺序，不顾动作类型优先级，逐层逐列进行编号。若该动作类型是40尺集装箱单钩或20尺单钩，则对单个集装箱编一个号；若该动作类型是20尺集装箱双钩，则对两个20尺集装箱编一个号。中层集装箱编号逻辑与上层集装箱编号逻辑基本一致，但由于中层集装箱不算特别高，可以考虑20尺和40尺岸桥吊具更换问题。下层集装箱编号逻辑考虑船舶稳性的问题。当舱盖数量等于4时，先按中层编号逻辑对1，4号舱盖下的集装箱编号，再对2，3号舱盖下的编号。

数据预处理第二部分为作业数统计过程。作业数统计的目的是帮助岸桥司机知道每一时间段需要作业哪个贝位的哪个位置的哪些集装箱，需要进行多少次钩取。岸桥的每一次钩取定义为一次动作。因此，按照贝位、船舶位置以及进出口的区分进行动作数的统计是必要的。此外，由于作业特种箱需要进行吊具的更换等特殊处理，因此在进行动作数统计的同时，也需要按照贝位、船舶位置以及进出口的区分统计出特种箱的类别和数量，便于岸桥司机进行实际作业的准备。动作数统计的思路为按位置顺序依次取出各箱子，进行不同类别的判断之后进行统计。

数据预处理第三部分为岸桥动作时长计算过程。每一个集装箱具有很多属性，其中包括轻重，集装箱所在船舶位置，集装箱类型等。由于岸桥动作作用的集装箱属性的不同，岸桥动作的时长也有所不同。

一般在岸桥钩取集装箱放到拖车上的时候，会有港口的记录员把这一动作的时间和其他属性给记下。因此，对此类型的数据进行处理与分析可以统计得到各岸桥动作时长。

2.2 基于分割集装箱组的分线算法

在以各贝位上各船舶位置处的集装箱组为调度单位的情况下，为了能均匀地分配任务给各岸桥，本文提出了一种可分割集装箱组的分线算法。由于采用连续分配的贪心策略，每一个位置的作业量最多可由两台岸桥进行作业。

由于八层箱和九层箱具有作业的特殊性，因此各贝位的进口或出口的八九层箱只能由一台岸桥进行作业。而某些位置的甲板箱和舱内箱可以分给两台岸桥进行作业。堆场中，进口集装箱存放的位置和出口集装箱存放的位置不临近。假如进口作业和出口作业同时进行调度的话，场桥就会来回移动，产生较大的时间和经济成本。因此，本算法选择先对进口作业进行调度，再进行出口作业的调度，分两次进行分线算法和作业顺序算法。

2.3 基于多线程设计的作业顺序算法

为了能合乎实际地根据分线结果确定各作业线的作业顺序，本文设计了基于多线程设计的作业顺序算法，考虑了船舶稳性问题和生活区烟囱问题以及抹高问题。船舶稳性问题是指在船舶装卸货的过程中，由于卸货顺序不合理导致的船舶左右两侧货物总重量相差太多导致船舶不稳的情况。由于一般船舶有足够的长度，因此不需要考虑船舶前后稳性问题。某些体型较大的船舶会设置有生活区和烟囱的位置。生活区和烟囱会占有一定的船舶宽度，当此宽度大于等于两岸桥之间安全距离时，生活区和烟囱两侧便可同时作业；反之则不可同时作业。某些高岸桥会分配到抹高任务。为了不影响其他集装箱的作业，抹高集装箱必须是要最先进行作业的。因此各岸桥如果被分配了抹高任务，都要将该任务的作业顺序定为最先。作业顺序算法详细流程如图4所示。

3 基于实际作业数据的算法验证

对比单船完工时间和岸桥平均工作时长可知，通过本文算法所得出的岸桥计划的单船完工时间和岸桥平均工作时长都比人工计划的短，同时也能降低一次调度中岸桥的平均工作时长。从编制岸桥作业计划时长方面对比，人工平均花费6个小时的工作时长。对比本文算法从导入数据到出最后的岸桥计划总花费的10分钟来说，本文算法能够明显节省工作人员的工作时间和精力。对比实验结果的极差和方差可知，本文算法的各岸桥的工作时长数值相差不大，比较集中在平均工作时长附近，各岸桥之间的等待时间较短。

从某港口过去一年的历史数据中随机抽样了十份不同的实际作业数据，对比人工编制的岸桥作业计划的单船完工时间和本文算法的结果如表1所示。分析对比结果可知，本文算法能帮助缩短1.5个小时左右的单船完工时间，说明了算法具有普遍适用性。

表1 单船完工时间对比表

编号	1	2	3	4	5	6	7	8	9	10
人工	43.1	51.7	37.7	40.8	27.5	62.4	72.0	46.6	22.8	85.5
算法	41.3	50.1	36.5	39.5	26.0	60.5	71.2	45.5	22.2	83.1
相差	1.8	1.6	1.2	1.3	1.5	1.9	0.8	1.1	0.6	2.4

4 总结与展望

作为时代主旋律，经济全球化发展越来越快。时代趋势对于港口的智能化、自动化要求越来越高。研究岸桥调度问题以提出一个能做出高质量岸桥作业计划的算法至关重要。考虑到岸桥调度问题已被证明为一个 NP-hard 问题，和诸多实际影响因素，本文提出了一种基于贪心策略的智能岸桥调度算法。同时给出了以某港口实际作业数据进行算法的验证结果，证明了本文提出的算法的可用性和准确性。

同时，本文期待在后续的研究中，一方面能将分线问题和作业顺序问题在一个算法中同时考虑；另一方面能实现多船舶调度，考虑岸桥方面与拖车和堆场方面协调调度，着眼于整个港口的所有任务调度，得到更加科学的调度方案，实现更大的经济效益。

参考文献

[1] 厦门港口管理局 厦门港“打造智慧港口引航站”获评全国首创！[EB/OL]. 2022.09.08

[2] Lee,Wan,H Quay crane scheduling with noninterference constraints in port container terminals [J].Transportation Research Part E,2008,44 (1)