摘 要

集装箱码头是海运与陆运的重要节点，在国际贸易快速增长的今天，提高码头作业效率是增加码头竞争力的有效方法。本文针对集装箱码头装卸系统作业进行研究，首先从码头实际背景出发，对码头三阶段装卸作业问题进行了分析，其次以令最大加工最小为目标函数，建立基于混合流水车间理论的码头装卸作业整数规划模型，接着采用约翰逊启发式算法，对集装箱在岸桥和场桥的卸载作业进行优化，得出作业块的卸载顺序，再对集卡进行指派作业，最后用Python软件对算法编程，求解得出目标函数，并根据码头实际情况，将实际算例代入程序进行数值计算。

优化后的结果比优化前平均高出15.49%，能有效提高集装箱码头装卸效率，降低码头设备空载率，减少船舶的在港时间，且适用于拥有较多集装箱数量的船舶装卸，有着较强的现实指导意义。

关键词：集装箱码头；装卸作业；混合流水车间调度；约翰逊算法

ABSTRACT

Container terminals are important nodes for sea and land transportation. In today's fast-growing international trade, improving the efficiency of terminal operations is an effective way to increase the competitiveness of terminals. This paper studies the operation of container terminal loading and unloading system. Firstly, it analyzes the three-stage loading and unloading operation problem from the actual background of the terminal. Secondly, it aims to minimize the maximum processing and establish a complex planning model for terminal loading and unloading operations based on the mixed flow shop theory. Then, using Johnson's heuristic algorithm to optimize the unloading operation of the container on the shore bridge and the field bridge, the unloading order of the operation block is obtained, and then the assignment of the set card is performed. Finally, the algorithm is programmed with Python to solve the objective function. According to the actual situation of the terminal, the actual calculation is substituted into the program for numerical calculation.

The optimized result is 15.49% higher than the average before optimization. It can effectively improve the loading and unloading efficiency of container terminals, reduce the time of ship arrival, reduce the no-load rate of terminal equipment, and is suitable for ship loading and unloading with a large number of containers. Realistic guiding significance.

Keywords: container terminal; loading and unloading operation; hybrid flow shop scheduling; Johnson algorithm

目录

第1章 绪论 1

1.1 研究背景 1

1.2研究意义 1

1.3国内外研究现状 2

1.4 主要研究内容 4

1.4.1 主要研究内容 4

1.4.2 论文结构安排 4

第2章 问题描述与理论介绍 6

2.1码头装卸设备与装卸工艺 6

2.1.1岸边装卸机械 6

2.1.2水平运输机械 6

2.1.3堆场装卸机械 6

2.1.4码头装卸工艺 7

2.2相关理论介绍 7

2.2.1混合流水车间调度模型介绍 7

2.2.2约翰逊（Johnson）法则介绍 8

2.3问题描述 9

2.4 本章小结 11

第3章 建立数学模型 12

3.1 问题假设 12

3.2模型参数设立 12

3.3 整数规划模型 13

3.4 本章小结 14

第4章 模型求解 15

4.1 算法思路 15

4.2 算法求解步骤 15

4.2.1阶段一：约翰逊（Johnson）启发式算法 15

4.2.2阶段二：集卡指派 17

4.3 数值实验及分析 17

4.4 本章小结 20

第5章 总结与展望 21

5.1 总结 21

5.2 展望 21

参考文献 23

致谢 25

第1章 绪论

1.1 研究背景

随着经济全球化的步伐不断加快，国际贸易在近年发展势头较好，海上运输业是运输中的重要方式，有研究表明，在世界范围内的贸易，海运占到了三分之二，而集装箱运输占到了海运的主要部分，相比于其他运输方式，集装箱运输具有操作便利，安全性好，作业效率高等特点。集装箱运输比例逐年增长，集装箱运输网络与管理渐渐成型完善，在集装箱迅速发展的同时，对其运输能力也提出了考验。

集装箱码头是决定集装箱运输效率的主要因素，也是国际化贸易的重要手段，它承担着连接不同运输方式的枢纽与节点。码头的吞吐量保持了近十年迅猛增长，尤其是国内，我国港口吞吐增长速度保持百分之三十以上，在未来仍具有很大的发展空间，针对集装箱码头的管理与研究在近年渐渐被人们所重视，各大码头开始着手提高自身的服务水平与码头运作能力，来增加码头的竞争力，使其能在激烈的竞争中脱颖而出，占取更高的贸易额。提高码头装卸的作业效率能够在一定程度上减少船舶在港的时间，也能够提高码头运作效率，增大码头吞吐能力，进而提高码头竞争力，同时，装卸作业效率会影响船舶运输的周转率，通过提高效率，能够降低码头和船公司的成本，使码头和单件货物更具竞争力。

提高集装箱码头装卸能力主要有两种方法，第一是增加码头设备数量，随着吞吐量的增长，设备的增长可以一定程度上提高装卸能力，但码头设备的数量受到岸线长度，码头规模等参数的限制，不能无限增长，当今国内集装箱码头的平均岸桥数目已经超过其他国家，设备过多容易导致资源浪费，因此，在码头设备既定的条件下，选择对装卸作业调度进行研究的方法，通过对码头装卸系统实施合理的作业调度，来提高码头的装卸效率，这种方式对装卸系统的合理性要求更高，可以有效降低设备空载，避免浪费，实现资源实际有效的利用，并通过对码头装卸的优化，建立一个完整，行之有效的装卸作业调度系统，提高码头的作业效率，使作业调度具有较强的稳定性与可靠性。

1.2研究意义

随着我国各港口的发展水平逐渐提高，船舶向着大型化方向发展，集装箱码头的吞吐量也在日益增长，这是集装箱码头发展的黄金时期，但也对集装箱码头的能力提出了较高的要求。对集装箱码头装卸作业进行调度研究，能使生产作业环节更为流畅，整体作业效率增加，并能有效的对装卸系统进行决策，同时，集装箱码头装卸要用到的设备有岸桥，场桥，集卡，它们属于码头的重要资源，将三种设备综合考虑，能够尽量减少设备空载或闲置时间，降低船舶靠泊时间，也能大大降低作业成本，避免不必要的浪费，提高码头通货能力。

除此之外，码头装卸系统是一个多阶段，多目标优化问题，同时涉及到多个约束，在实际生产中较为复杂，对该课题的研究可以很好地提高码头作业效率，有实际的工程应用价值，研究集装箱码头装卸作业的意义主要在于以下几点：

（1）适应港口贸易的增长

国外海运贸易额在近年来不断增长，国内集装箱码头规模逐渐扩大，码头设备不断完善，码头吞吐量也连年增长，这对码头装卸作业提出了更高的要求，规模的提升，范围的扩大也加大了问题的难度和复杂度，因而，对装卸作业系统的优化不但符合当今实际生产的需求，满足集装箱运输增长的需求，同时，良好的装卸作业调度通过推进装卸作业的整体化，能够促进贸易的进一步增长。

（2）提高港口竞争力

船舶日趋大型化带来的不仅是贸易的繁荣，运输能力的增加，也对港口的作业效率和装卸能力提出了要求，码头的作业效率关系着船舶的经济效益，而中国水运发达，从经济腹地到沿海码头，各大港口之间存在着激烈的竞争，因而，做好港口与船舶的对接服务，减少船舶靠泊时间，同时能吸引更多船舶靠泊，将港口打造成海运线路的中心枢纽。

（3）降低各方成本

一个良好的码头装卸系统调度可以提高码头作业效率，降低船舶在港时间，提高船舶的周转效率，进而降低船运公司整体运输系统网络成本，也能降低货物的单箱成本降低；除此外，通过对港口资源的有效调度，降低了港口的投入，避免了不必要的设备空载或浪费，降低了码头运营的成本，而码头是物流供应链中的一个重要环节，提高了码头的运营效率，能使整体物流运输系统的效率得到提升，降低物流的总成本。

（4）理论研究意义

港口装卸作业是一个复杂的问题，在理论上三阶段集成调度属于NP-hard问题，本研究将港口实际背景与理论知识结合，尽可能将问题与实际约束相结合，对集装箱码头进行合理的调度优化，具有一定的理论价值和应用意义。

1.3国内外研究现状

对于集装箱码头装卸作业问题，国内外都进行了研究，但因为装卸系统的作业调度影响因素多，系统实施较为复杂，大多数研究是针对作业系统的某一作业环节进行优化研究。Kim^[1]对岸边吊桥阶段建立整数规划模型，并采用遗传算法的方式求解；曾庆成，杨忠振^[2]等通过Q学习算法，对码头装卸过程中，集装箱卡车的动态调度进行求解；对于堆场内的作业，韩晓龙^[3]对场桥路径问题进行研究，建立了混合整数规划模型，求解出最优路径。

在集装箱码头装卸作业集成调度的研究中，大多采用建立模型，通过算法优化对码头各阶段的作业进行研究，或是用系统仿真的方法对其求解。

在系统仿真方面，张莉^[4]等运用Witness软件进行建模，通过对国内集装箱码头岸桥至堆场的装卸运输实行仿真运行，得出集卡的配置与装卸速度的关系；Maurizio等运用JAVA软件，搭建码头调度仿真系统；张海霖^[5]等将集装箱集疏运问题转化为FMS生产调度问题，并用Witness仿真工具，分别模拟了集装箱集疏运调度面向作业线的两种调度模式；何山^[6]结合eM-Plant仿真软件，对SDEVS离散系统进行改进，并基于该软件用对集装箱码头装卸系统进行分析。

针对模型优化算法的研究主要有以下内容：Chen^[7]等用禁忌搜索算法对集装箱码头三阶段作业进行求解，但只适用于小于100个集装箱的规模；Lau^[8]等对码头装卸设备提出最小化AGV距离等多目标决策，比较了两种遗传算法的不同优化方法，但没有考虑岸桥碰撞约束；曾庆成^[9]建立集成调度模型，对装卸序列进行集成优化，通过对三阶段的岸桥，集卡，场桥作业序列同时优化，协调作业系统环节，实现集卡共享到不同作业线，设计出模型求解的混合优化算法，提高了模型求解的效率，乐美龙^[10]等用多层遗传算法，对岸桥与集卡协同调度问题进行研究，并在模型中考虑岸桥间碰撞、安全距离等条件约束；邢曦文^[11]在对集装箱装卸作业顺序排列的基础上，研究了两船同时装卸的情况下，将集卡路径的优化问题作为车辆路径问题的延伸，用蚁群算法和改进的启发式算法两种方法进行优化求解。

近年来的学科交叉也让集装箱码头装卸作业问题有了更多的求解思路和方向，该问题可看作混合流水车间问题的延伸，混合流水车间模型是生产制造车间的一类常见模型，大多研究从启发式算法着手，对该模型进行优化求解^[18-23]，Narges　Kaveshga^[12]基于混合流水车间，建立岸桥和集卡的两阶段模型，并采取遗传算法求解；Kim^[1]建立了三级物料装卸时间的预测模型，为码头装卸作业三阶段集成模型打下了基础；Mohamed　Haouari^[13]将求解混合流水车间问题的各个算法进行比较，并给出了该问题的理论完工时间下界值；Kurz^[14]等研究了混合流水车间问题，提出三个启发式算法，用于求解该问题，分别是插值算法，基于Johnson规则的启发式算法以及贪婪启发式算法，并将算法进行比较；梁亮^[15]根据集装箱码头装卸作业的实际情况，设置了码头作业预定义约束以及岸桥碰撞约束，建立三阶段整数规划模型，并用两阶段的启发式算法进行求解；陆志强^[16]把禁忌搜索算法和遗传算法结合起来，对该问题进行求解；谢晨^[17]在求解过程中，考虑了集卡的因素，用约翰逊法则的启发式算法进行求解，在集卡运输阶段加上一个权重因子，使其满足条件约束，并将改进的算法与遗传算法进行结果比较，在对算例分析后得出结论：改进后的约翰逊启发式算法优于遗传算法。

1.4 主要研究内容

1.4.1 主要研究内容

集装箱码头装卸系统是一个多阶段的复杂系统，针对该系统的研究有很多不同方向，接下来将阐述本文研究内容，界定研究范围和方向。

集装箱码头是以码头设备搬运为基础，来实现集装箱的转运功能，单船的装卸具体分为三个步骤，在船舶靠泊后，第一步：由岸边吊桥（QC）将集装箱从船上卸载至集装箱卡车；第二步：由集装箱卡车将集装箱运输至该集装箱所要放置的箱区；第三步：由场吊（YC）将集装箱从集装箱卡车上卸下，放入堆场中；装船步骤与其相反，该过程可以看作三阶段混合流水车间问题的延伸，将集装箱装卸的过程模拟成工件在流水线上被加工的过程，工件是待装卸的集装箱，岸桥，集卡运输和场桥作业看成三个作业环节，集装箱的作业顺序决定了三个阶段设备的运行与空载时间，将岸桥，集卡，场桥三个阶段进行集成调度，对集装箱装卸顺序进行优化可以减少设备对集装箱的作业时间，提高作业效率，使最大加工时间最小。基于以上理论分析，本文主要研究以下内容：

（1）对问题提出合理假设，并进行适度简化，设定令最大作业时间最小为目标函数，基于对作业流程的分析，将码头实际作业情况转化为混合流水车间模型，建立集装箱装卸作业系统三阶段混合整数规划模型，并用数学式对实际约束进行描述。

（2）模型求解。本论文采用约翰逊启发式算法对模型求解，首先将三阶段整数规划模型划分为两个部分分别来解决，首先在集装箱卡车数量充足的情况下，不考虑集卡的运输，将模型变为抛开集卡阶段的两阶段问题，得出集装箱的卸船顺序；接着，在卸船顺序已知的情况下，对集卡进行指派。搜集实际港口集装箱码头数据，代入模型进行求解，并对求解后的结果进行算例分析，证明优化方案的有效性。

1.4.2 论文结构安排

本文各章节结构安排如下：

第1章绪论，阐明本文课题研究的相关背景和意义，对现有的国内外研究理论和研究现状进行介绍，阐述了论文的研究内容和相应的优化方法，提出文章的基本框架和结构安排。

第2章问题描述与相关理论介绍，对集装箱码头装卸设备与装卸工艺进行描述，对实际码头作业特点进行阐述，并对将要运用到的混合流水车间模型进行阐述，介绍相应的优化算法：约翰逊启发式算法。

第3章基于混合流水车间理论，建立集装箱码头装卸作业系统的三阶段模型，依据码头生产作业的实际情况，提出建模所需的前提条件，对模型参数进行设立，包括数学符号的定义，建立三阶段混合整数规划模型。

第4章对模型分步求解，第一步把问题转换成只考虑岸桥和场桥阶段的两阶段混合流水车间问题，并用约翰逊（Johnson）启发式算法求解，得到集装箱的装卸作业顺序，再对集装箱卡车进行指派，运用实际案例优化分析，以最大加工时间最小为目标，得出求解结果，通过比较初始值和卸船顺序优化后的值，证明优化算法的可行性。

第5章全文总结，阐述文章已完成的工作和目标完成状况，提出对未来展望和可改进之处。

第2章 问题描述与理论介绍

2.1码头装卸设备与装卸工艺

集装箱码头装卸系统是由岸边装卸机械，水平运输机械和堆场装卸机械组成的多阶段复杂操作系统，每个阶段有多台并行设备同时运转，以下将对装卸系统三个阶段的设备分别进行介绍。

2.1.1岸边装卸机械

岸边装卸机械的常用设备包括装卸桥，多用途门座起重机，高架轮胎式起重机等，在当今码头前沿，大多采用的设备是岸壁集装箱装卸桥（也称岸桥），是轨道式行走机构，属于固定机构设备，按结构可将其划分为A型和H型，随着船舶的日益大型化，码头岸线也不断拉长，因此对于独立泊位而言，平均每个泊位会配备2-3台岸桥。岸桥主要功能是对集装箱的装卸，即将集装箱从船上卸载至水平运输设备上，或将集装箱从岸边装载至船。其工作时候的速度根据工作类别，划分为满载时的起升速度，空载时的起升速度，大车行走速度和小车行走速度；它的体积大，购置成本较高，是码头服务能力和服务水平的的重要体现，其装卸时间和装卸效率对集装箱码头的装卸系统整体时间和效率有很大影响，同时，它的装卸效率也会影响船舶的靠泊时间和后续设备的作业时间和作业效率。同时，岸桥的运行还要遵守岸桥碰撞约束，即两台岸桥之间不能够越过对方交叉作业，并且相邻岸桥作业时要保持一定的安全距离。

2.1.2水平运输机械

水平运输机械的常用设备分为集卡（挂车），牵引车，叉车，跨运车等不同种类，是负责集装箱从码头前沿到堆场的水平运输设备，现今的码头大多采用集装箱卡车（简称集卡）作为运输工具。集卡的调度，配置和路径优化也是码头优化中的重要组成部分，对集卡资源的有效利用也能大幅度提高码头作业的效率。

2.1.3堆场装卸机械