摘 要

全球经济的繁荣发展带动了运输业的发展，作为链接水运陆运的重要节点，港口的发展在全国经济发展中处于重要的地位。港口物流的发展越来越迅速，不断扩大的港口业务也促使港口规模不断扩大，为了维持港口的高效运营，提升服务水平，除了更新硬件设施，拖轮作业作为货船进港、移泊、出港过程中的一项关键作业，其调度的合理化将在很大程度上节约港口的作业成本，科学调配拖轮进行辅助作业是港口效益提升的一个突破点。

本文首先思考了港口作业流程和拖轮作业流程及特点，通过对现有研究现状的分析，总结拖轮调度问题的基本思路及采用的方法，并思考研究中可能存在的问题。然后根据现实情况，在考虑到建模求解简便性的基础上，进行合理的条件假设，建立科学的多停泊基地约束下的拖轮调度数学模型，使建立的模型在一定程度上能够反映真实情况。本文的目标函数为最小化拖轮最大完工时间，分别考虑了多停泊基地允许交叉作业和限制交叉作业两种模式。接下来对求解类似问题的方法进行比较研究，本文采用遗传算法来对建立的拖轮调度数学模型进行求解，设计算法并用MATLAB进行运算，采用了多维整数编码方式，应用遗传算法工具箱适应度计算函数进行适应度分配，使用轮盘赌法选择具有更好适应性的个体并使用洗牌交叉以获得新的染色体。最后，对案例进行求解，分析实验结果对比两种作业模式，验证了方法的可行性。

关键词：多停泊基地，拖轮调度，遗传算法

Abstract

The prosperous development of the global economy has driven the development of the transportation industry. As an important node linking water transportation and land transportation, the development of ports plays an important role in the national economic development. The development of port logistics is getting faster and faster. The expanding port business also promotes the continuous expansion of the port scale. In order to maintain the efficient operation of the port and improve the service level, besides upgrading the hardware facilities, tugboat operation is a key operation to assist cargo ships to enter, move and leave the port. The rationalization of tugboat dispatching will greatly save the operating cost of the port. Scientific deployment of tugboats for auxiliary operations is a breakthrough point in improving the port efficiency.

In this paper, the port operation process and tugboat operation process and their characteristics are first considered. Through the analysis of the current research situation, the basic ideas and methods of tugboat scheduling problem are summarized, and the possible problems in the research are also considered. Then, according to the actual situation and considering the simplicity of modeling and solving, reasonable assumptions are made to establish a scientific mathematical model of tugboat dispatching under the constraint of multiple berthing bases, so that the established model can reflect the real situation to a certain extent. In this paper, the objective function is to minimize the maximum completion time of tugboats. Two modes are considered, one is to allow crossover operation at multiple berthing bases and the other is to limit crossover operation. The following is a comparative study of methods for solving similar problems. In this paper, Genetic Algorithm is used to solve the mathematical model of tugboat scheduling. The algorithm is designed and operated by MATLAB. Multidimensional integer coding is adopted. The fitness calculation function of Genetic Algorithm toolbox is used to allocate fitness. Roulette method is used to select individuals with better fitness. Shuffle crossover is used to obtain new chromosomes. Finally, the case is solved and the experimental results are compared with the two operation modes to verify the feasibility of the method.

Key words: tugboat scheduling；multi-anchorage bases；Genetic Algorithm

目 录

摘 要 I

Abstract II

第1章 绪论 1

1.1研究背景与意义 1

1.2国内外研究现状 2

1.3研究内容及技术方案 3

1.3.1研究目标 3

1.3.2研究内容 3

1.3.3采用的技术方案及措施 4

第2章 拖轮调度模型建立 6

2.1拖轮作业 6

2.2模型建立 6

2.2.1问题描述与假设 6

2.2.2符号说明 8

2.2.3模型构建 9

第3章 拖轮调度模型求解 12

3.1算法选择 12

3.2遗传算法基本原理 13

3.3遗传算法求解步骤 14

3.3.1个体编码及初始化 14

3.3.2适应度值 15

3.3.3选择操作 15

3.3.4交叉操作 15

3.3.5变异操作 16

第4章 案例分析 18

4.1案例描述及数据 18

4.2遗传算法参数设置 21

4.3结果分析 21

第5章 总结与展望 26

5.1全文总结 26

5.2研究展望 26

参考文献 27

致 谢 29

第1章 绪论

全球经济的繁荣发展带动了运输业的发展，作为链接水运陆运的重要节点，港口的发展在全国经济发展中处于重要的地位。除了港口的设施，有效地提升港口的服务水平和作业效率更是改善港口的经济效益的重要途径。港口拖轮作业作为货船进港、移泊、出港过程中的一项关键作业，影响着港口物流的运转效率，拖轮调度的合理化将在很大程度上节约港口的作业成本，为港口物流的持续发展提供重要支持。

1.1研究背景与意义

港口有着优良的发展条件和优秀的资源整合能力，对于国内外贸易货物运输来说，港口是不可或缺的。大部分的外贸货物运输由港口来承担，港口将海外和内陆链接起来，对形成一个完整的物流供应链体系起着十分关键的作用。随着全球经济的高速发展，我国的港口建设与经济发展也越来越迅速，对外贸易量在不断增加，相应的港口货运量的增加对于港口的发展壮大来说，无疑是一个不可错失的好机遇，港口业的迅速发展也将带动周边地区的经济发展，对我国国民经济的迅猛发展也有着无法替代的作用。现代物流的发展也促进了港口的建设，港口物流将呈现出越来越蓬勃的发展趋势。港口需要更大程度上的自我提升才能适应新的经济环境，港口要发展成为综合性的供应链节点，运用高新科学技术与理念，提升港口作业效率和综合服务水平。港口的自身的发展潜力也是港口竞争力的重要因素，在运营水平上，提升港口自身实力，需要从港口作业的多个部分来进行优化改善以达到港口综合实力的提升。

不断扩大的港口业务也促使港口规模不断扩大，为了维持港口的高效运营，提升服务水平，除了更新硬件设施，在港口作业中起到极为重要的作用的拖轮作业，也需要用更为高效的方法来进行调度。到港货船数量的增大不能单一地靠着增加泊位和拖轮等设施的数量来应对，建设新的泊位以及管理与使用拖轮的成本也是巨大的，所以有必要在一定的资源约束下优化拖轮调度。拖轮具有体积小马力大的特点，行驶时能快速反应且操作灵活，拖轮的使用具有多样性，港作拖轮主要为大型货船提供预警护航、港湾内牵引、协助离靠泊等服务，确保船舶进出港时的安全，在港口作业系统中有着至关重要的作用。从货船准备进入港口时，拖轮作业开始，货船在锚地等待进港，拖轮前往货船所在位置，辅助货船进入港口，拖轮将货船经由航道拖曳至所收到的货船信息的目的泊位，完成靠泊作业，然后拖轮前往下一任务点，而货船则在泊位进行相应的装卸作业，若货船装卸作业涉及多个泊位码头，则需要进行移泊作业，由于港口内水位较低，货船速度也有限制，货船不能自行在各位置移动，需要拖轮协助其作业，货船装卸完成后需要拖轮辅助离开泊位，经由航道拖曳到出港处后货船离开港口。

在需要拖轮作业的三个主要环节：进港、移泊、出港中，不同长度大小的船舶所需要的协助作业拖轮的类型和数量是有差别的，要考虑到现有资源并保证到港船舶进出港及离靠泊的速度及安全性，才能控制作业成本与服务水平。而港口建设的可用于作业的安全区域范围及岸线长度有限，可用拖轮数量有限，如果不能在有限资源约束下合理地调度拖轮，使拖轮能高效进行船舶拖曳及离靠泊作业，满足船舶作业需求使其装卸作业流畅进行，将会导致船舶的在港时间大大增加，同时造成船舶在港口滞留占用港口资源，造成资源的浪费。拖轮调度工作合理与否对船舶的在港时间和拖轮作业成本有着直接的影响，拖轮作业的变动成本主要为油耗成本，即影响拖轮作业成本的主要是拖轮的功率大小及其作业时间，拖轮调度优化需要在保证利润的情况下节约拖轮作业成本，合理调度拖轮以节约时间。不合理的拖轮调度会造成资源的浪费也会直接影响服务质量，为了保证港口的日常运营，做好港口拖轮的调度是必须的。

1.2国内外研究现状

对于港口拖轮调度问题，近年来国内外众多学者对这个问题都有相关研究，并通过不同的方法对拖轮调度进行了优化，对于优化的方法也有不同的改进。

易剑琦^[1]等学者运用eM-plant软件建立仿真模型来进行港口拖轮调度的系统仿真，包括单停泊基地和多停泊基地两种模式，并考虑在多停泊基地下限制或允许其交叉作业的情况，对三种拖轮作业模式的优缺点进行横向比较分析。

在拖轮调度问题模型建立方面，谈鹏^[2]建立了以最小空载距离为目标的拖轮调度优化模型，实现动态调度；王巍^[5]等学者建立了以总作业油耗和最大完工时间最小化为目标的多停泊基地下两种作业模式的拖轮调度模型；刘志雄^[6]以作业最大完成时间的最小化为目标，建立了调度模型，并嵌入启发式规则；刘志雄^[7]针对单向航道港口，建立了基于滚动时间窗拖轮动态调度模型；周晓光^[8]建立了包括作业时间和作业成本两个最小化目标的多目标拖轮调度模型；白洁^[9]构建了双目标的泊位和拖轮协同调度模型，以最晚完成靠泊的船舶的靠泊时刻和泊位浪费长度最小化为目标；HeTao^[10]等学者以作业最大完成时间的最小化为目标，建立了调度模型；徐奇^[11-14]等学者构建了单停泊基地及多停泊基地下的拖轮调度模型，以缩短拖轮总作业时间为目标，将拖轮调度问题与多处理器任务调度问题联系起来，并提出拖轮返回停泊基地的假设。

在解决拖轮调度问题的算法研究方面，谈鹏^[2]改进了标准遗传算法，釆取实数编码方式，并且在交叉和变异操作中以时序长度为单位；黄健^[3]将遗传算法与非线性规划结合，使其拥有较好的全局搜索能力的同时，兼顾到其局部搜索能力，经过算例分析表明该方法可以较快地收敛到全局的近似最优解。

王巍^[5]、刘志雄^[6]等学者采用演化策略算法进行优化，提出一种基于轮盘赌概率分配的多维实数编、解码方式，采用三点交叉进行互换重组，通过对个体内两个基因交叉互换进行变异，通过计算验证了演化策略算法的有效性；刘志雄^[7]等学者将三种不同的局部搜索策略与演化策略算法相结合来求解模型，其中，基于互换操作的混合演化策略算法能够更好地优化算法性能；周晓光^[8]采用的局部搜索策略是基于相邻不同基因互换；白洁^[9]、HeTao^[10]采用的局部搜索策略是基于交换操作。

徐奇^[11-14]设计了混合启发式规则的模拟退火算法，解的编码方式采用二维实整数编码，生成初始解时，在其中嵌入启发式规则，采用三点交叉的互换重组方式来更新解；Santos^[15]等学者采用模糊模拟退火算法进行并行机调度研究，解决不相关的并行机调度问题。

董良才^[19]等学者采用改进后的粒子群算法，与传统粒子群算法进行对比，验证了改进后算法的优越性；Ezzinbi^[20]等学者利用粒子群优化算法求解航空人员调度问题，并与遗传算法进行了比较；Wei Yan^[21]等学者提出改进的粒子群优化算法，提出的算法在拖轮上调度成功应用，与标准粒子群算法相比，改进后算法拥有更快的速度及更好的收敛性；Su Wang^[22]等学者提出了一种改进的混沌粒子群优化算法，嵌入混沌搜索作为局部搜索方法可以防止过早收敛。

对于拖轮调度问题的研究，一种为建立数学模型并利用智能算法进行拖轮调度优化研究，包括遗传算法、演化策略、模拟退火算法等，这些算法在解决全局最优解的问题上各有优缺点，且都是通过对自然过程的模拟，来达到求解的目的。通过在其中嵌入启发式规则，或者进行混合改进，可以一定程度上优化算法性能，提升其速度和收敛性。另一种为运用eM-plan等仿真软件建立仿真模型，对现实进行模拟，利用港口的实际运营数据，对多种作业模式下港口拖轮作业进行仿真，研究港口拖轮配置和作业调度问题，比较各作业模式的优劣，为现实中的拖轮调度提供决策参考。

1.3研究内容及技术方案

1.3.1研究目标

本文的研究目标是，通过对拖轮实际作业流程以及国内外拖轮调度研究现状进行研究，分析问题，明确关键约束条件，在考虑拖轮最大完工时间最小化的情况下，建立多停泊基地约束下的港口拖轮调度模型，运用遗传算法对拖轮调度进行优化研究。将实际案例代入模型中，利用设计的遗传算法在MATLAB中进行运算，验证模型及算法的可行性，并分析结果，对比允许停泊基地拖轮交叉作业和限制停泊基地拖轮交叉作业两种作业模式，为港口多个停泊基地下的拖轮作业调度提供参考。

1.3.2研究内容

建立多停泊基地约束下的港口拖轮调度模型，基于遗传算法进行编程求解，研究的主要内容包括：

（1）研究问题的背景及意义，思考港口作业的流程和现状，分析拖轮作业在港口作业中的重要性，分析港口拖轮调度优化问题的国内外研究现状，总述研究目标及内容，研究所采用的技术方案及措施。

（2）阐述拖轮作业流程，依据实际情况，并在考虑到建模求解简便性的基础上，进行合理的条件假设，建立科学的多停泊基地约束下的拖轮调度数学模型，使建立的模型在一定程度上能够反映真实情况，讨论两种作业模式，即允许两停泊基地拖轮交叉作业和限制两个停泊基地拖轮交叉作业。

（3）比较遗传算法、粒子群算法、模拟退火算法等启发式算法的优缺点，选择遗传算法求解该问题，综述遗传算法的相关理论和基本步骤，针对建立的模型设计相应的遗传算法进行求解，算法步骤包括编解码，适应度值计算，选择、交叉和变异操作。

（4）根据港口资料以及随机数据，选择算例，用设计的算法求解，并对比分析在不同船舶数量下两种作业模式的适用性，验证算法的可行性和有效性，为拖轮作业调度决策提供参考。

（5）结论与展望，对本文进行总结，在研究过程中有哪些待改进的部分，对未来研究方向及内容的展望。

本章研究框架图如图1.1。

1.3.3采用的技术方案及措施

（1）通过学习有关港口拖轮调度及启发式算法的文献，以及其他港口信息相关资料，了解港口作业流程及现状，掌握目前最新的研究进展。在学习相关文献时，注意理清文献的技术路线，归纳问题研究中的数学模型，总结采用的求解方法及存在的问题。

（2）分析现实情况确立优化目标，思考可能影响优化目标的因素，进行合理的条件假设，建立简明的拖轮调度数学模型，结合实际情况及相关的建模知识，分析建立的模型是否合理，使通过本模型计算出的结果在合理预期范围内，具有使用价值。