摘要：拖轮作业调度优化问题，实质上是一个资源约束下的动态调度难题，属于NP-hard问题的范畴。它需要根据进出港船舶的作业需求，综合考虑拖轮的位置、数量、型号和马力等多种因素，进行科学的调配。目前，研究者们主要围绕如何最小化拖轮和船舶的等待时间、最大化拖轮利用率、最
拖轮作业调度优化，不仅关乎港口的运营效率，还直接影响到船舶在港的安全性和港口的整体成本。那么，当前拖轮作业调度优化的研究现状究竟如何呢？
拖轮作业调度优化问题，实质上是一个资源约束下的动态调度难题，属于NP-hard问题的范畴。它需要根据进出港船舶的作业需求，综合考虑拖轮的位置、数量、型号和马力等多种因素，进行科学的调配。目前，研究者们主要围绕如何最小化拖轮和船舶的等待时间、最大化拖轮利用率、最小化港口运营总成本等目标，展开了一系列深入的研究。
1、拖轮作业调度优化问
随着大型船舶数量的不断增加，如何高效安排拖轮资源来协助船舶进出港口，提高拖轮的利用率，减少船舶等待时间，降低港口的运营成本，同时确保船舶在港的安全性，已经成为各大港口亟待解决的问题。受船舶到港时间、港口水域环境和天气状况等多方面因素的影响，如何科学合理地优化拖轮作业调度方案值得深入研究。
港作拖轮调度优化问题作为一类资源约束下的动态调度问题，属于NP-hard问题。依据进出港船舶作业需求，轮驳公司需根据当前拖轮位置、数量、型号、马力，进行综合调配。港作拖轮作业常用的调度原则包括：
(1)作业最短距离原则，即根据拖轮停泊地点与到服务船舶的距离最小值来安排，缩短船舶的等待时间；
(2)首艘可用原则，即按照拖轮上次任务与下次任务时间差最小安排；
(3)任务量平均原则：为了确保每艘拖轮都可以参与船舶任务，均衡拖轮驾驶员工作量。拖轮作业优化调度问题的总目标是最小化拖轮和船舶的等待时间，最大化拖轮利用率，最小化港口运营总成本，总成本包括时间成本、拖延成本和燃油成本等。
2、港作拖轮作业优化调度方法研究现状
进出港船舶会提前将船舶动态信息发送给港口，港口根据船舶申请制定计划表发送给轮驳公司，轮驳公司制定拖轮作业计划与待服务船舶的货物种类、船长和吃水有关。拖轮调度优化的核心是如何合理地对拖轮进行资源分配和任务规划，常用方法可分为数学规划方法、启发式搜索算法、强化学习算法和基于虚拟仿真的方法。
(1)数学规划方法
在数学规划模型中，线性规划模型(LP)的目标函数和约束条件都是线性的，难以解决目前拖轮调度的多目标匹配问题。因此，大多研究者将拖轮调度问题建模为混合整数线性规划模型(MILP)来解决港口拖轮、船舶和停泊基地的匹配问题，通常以燃油成本和任务拖延成本之和为目标函数，以拖轮任务分配为决策变量，通过求解最优化问题生成拖轮调度计划。
(2)启发式搜索算法
考虑到拖轮调度问题的复杂性、动态性、多约束性和求解难的特性，大部分研究者采用启发式搜索算法来求解拖轮调度问题，包括遗传算法(GA)、人工蜂群算法(ABC)、粒子群优化算法(PSO)、蚁群算法、模拟退火算法、灰狼优化算法和NSGA-II等。
遗传算法是基于自然选择和遗传学机理的一种全局优化搜索算法，模拟了自然选择和生物遗传中的复制、交叉、遗传和变异的过程，在潜在的解决方案种群中逐次产生近似最优的方案。该算法适用于各类问题，但需要大量的样本才能够求解，在运算过程中不易陷入局部最优解，对于操作而言，过程中需要编码和解码导致算法的编程困难。可将拖轮调度问题看作多机调度问题，以缩短任务完成时间为优化目标，构建适应度函数，根据进出港船舶序号、时序、船舶类型、初始和目标位置，以及随机分配的初始拖轮序号，运用遗传算法求解，得出优化调度计划，相比人工调度降低了使用拖轮的数量。
人工蜂群算法是由Karaboga在2005年提出的，通过模仿蜜蜂的智能觅食行为来求解数值优化问题。该算法具有较好的全局搜索能力和鲁棒性，但是当系统比较复杂的时候，会陷入局部最优解。研究者们以船舶等待时间最小化和运营成本最小化为目标函数，设计拖轮调度的多目标优化模型，包含多艘船舶、多艘拖轮和多个停泊基地，采用改进后的人工蜂群算法，经过初始解、种群初始化、雇佣蜂阶段、跟随蜂阶段、侦查蜂阶段和外部档案管理，考虑拖轮配置、动态任务和拖轮维修费用信息，进行算例求解，得出最后的拖轮调度方案表，包括安排拖轮的数量、派出时刻和完成时刻。
粒子群优化算法来自对鸟群捕食的研究，因此也叫做鸟群觅食算法，其基本思想是通过群体中个体之间的协作和信息共享来寻找最优解。该算法较其他智能算法局部搜索能力差，容易早熟，难以平衡局部和全局搜索的能力，但较为简单，易于调整，适合求解数值优化问题。拖轮调度问题可建模为生产过程中的混合流水线调度问题，设计目标函数为最小化拖轮溢出马力和船舶等待时间，决策变量设为给船舶分配的拖轮等级和数量，采用改进的粒子群优化方法求解模型，进行适应度的计算、更新个体与全局极值、更新粒子群的速度与位置，得出了包含拖轮的等级、数量、派出时刻和完成时刻的整体调度方案。
(3)强化学习算法
强化学习(RL)被用于求解调度优化问题，它主要关注智能体与环境之间的交互，在过程中通过学习策略到达最大回报或特定的目标。研究者们将拖轮调度问题建模为马尔科夫决策过程(MDP)，包括五个元组：状态、动作、状态转移、奖励和策略。其中，状态指的是任务(船舶)对当前拖轮的需求、任务所需拖轮功率等；动作指拖轮是否被调度到任务的目的地以及调度时间。以港口运营成本最小化作为目标函数，以拖轮作业任务编号和完成任务后是否返回基地为决策变量，Sarsa算法可以由当前策略进行更新，在每一步更新中进行决策和学习，仿真结果表明，该算法能够有效求解85艘船舶、120艘拖轮和51个拖轮停泊基地的拖轮调度优化问题，验证了采用强化学习算法解决拖轮调度问题的可行性。
深度强化学习近年来受到广泛关注，能够弥补数学规划方法和启发式搜索算法在解决复杂动态环境的不足，为更好地解决不确定因素的环境下拖轮调度问题，需要考虑船舶动态到达时间和环境因素的影响，以拖轮燃料成本和作业时间最小化为目标函数，建立了数学规划模型，以拖轮是否完成某作业任务与返回基地为决策变量，研究者们采用优先级重播机制与基于DDPG算法的衰减噪声策略结合，将拖轮到达任务位置的时间作为一个连续的动作空间来优化，针对不同的实例规模进行仿真实验验证，证明算法在拖轮调度问题中的可行性。
(4)基于虚拟仿真的方法
仿真技术在现代港口和航运业的应用越来越广泛，港口是由许多要素组成的复杂系统，仿真可针对复杂系统进行建模，模拟不同的方案下港口的实际运行效果，验证策略的优劣性，比较不同方案的差别。基于多阶段混合流水作业调度模型，研究者们采用混合模拟退火算法等优化方法对拖轮调度模型求解，通过对比传统人工调度方法和基于优化方法所得的拖轮调度方案中拖轮利用率，证明了优化的必要性与仿真的重要性。
(5)动态调度方法
港口的拖轮调度问题具有典型的时空不确定特征。因天气状况和环境因素影响，船舶到港时间存在不确定性，难以完全按照前24小时发送的信息执行，这也导致了拖轮作业服务需求的动态时变特性。研究者们将拖轮的动态调度问题建模为马尔科夫决策过程，以拖轮在服务时间窗内运营成本最小化为目标函数，以拖轮的任务分配和调度为决策变量，将响应式的任务分配与主动式拖轮等待决策结合，采用K-means聚类选取拖轮的等待地点，使拖轮提前在未来任务需求地点进行预先等待，减少拖轮航行时间的浪费和燃油成本，使用近似动态规划的方法解决提高最优求解效率。该方法已经在新加坡集装箱港口的大规模数值优化仿真实验中展现了良好的效果。
以上不同类型的拖轮调度方法的比较见表1。
表1 不同类型的拖轮调度方法的比较
拖轮调度问题大多建模为静态的混合整数规划模型，以预先获得的船舶进出港信息为基础，通过优化算法进行离线求解。拖轮调度优化模型中较少考虑到船舶到港时间随机性、天气条件等不确定性因素，对异构拖轮、港区水域环境和多拖轮协同的安全性等约束条件考虑不够全面，导致大部分研究工作都难以直接应用到实际的港口作业中。如何面向实际作业中的不确定性因素，融合多种方法的优点，充分利用虚拟仿真的优势，优化拖轮作业任务调度方案，提高模型和算法的鲁棒性，值得研究者们进一步深入研究。
选自《中国船检》杂志2025年第1期
来源：中国船检杂志社
