BAP与时变QCSP建模与优化

《Ocean Engineering》：BAP and Time-variant QCSP Modeling and Optimization

港口作业优化：基于混合整数线性规划与自适应大型邻域搜索-强化学习框架的berths分配和时间变 quay crane调度研究。摘要：提出整合berths分配与时间变quay crane调度的MILP模型及ALNS-RL算法，通过动态更新船舶与起重机调度策略，显著降低港口停留时间7.61%和起重机闲置率13.48%，验证了该框架在30泊位90船舶规模下的有效性，并优于标准ALNS和混合遗传算法。

　　

程成|李增双|张勇

东南大学交通学院，南京，211189，中国

摘要

加强航运公司与港口之间的数据共享有助于促进无缝合作，并更高效地利用码头资源。本研究探讨了集装箱码头中的综合泊位分配问题（BAP）和时变码头起重机调度问题（QCSP），旨在优化船舶的停靠顺序、时间安排以及动态码头起重机的分配。本文提出了一种混合整数线性规划（MILP）模型，并结合了一种新的解决框架，该框架将自适应大邻域搜索（ALNS）与强化学习（RL）相结合。这种ALNS-RL框架能够依次更新船舶序列和码头起重机调度方案，在有限的迭代次数内高效地收敛到高质量解。数值实验表明：1）所提出的方法能够获得更优的解决方案，将港口停留时间减少了7.61%，码头起重机的空闲率降低了13.48%；2）码头泊位与码头起重机的比例对运营效率有显著影响，本文确定了最佳分配比例；3）该方法能够有效处理从小规模到大规模的各种问题，包括拥有30个泊位和90艘船舶的情况。此外，ALNS-RL框架的表现优于标准的ALNS和混合遗传算法（HGA），平均偏差仅为0.5%，远低于ALNS（2.64%）和HGA（4.07%）。尽管在处理小规模问题时计算效率较高，但该方法在处理大规模问题时表现出色，证明了其在复杂实际码头调度应用中的鲁棒性。

引言

集装箱码头是现代海运运营的重要组成部分；然而，持续的港口拥堵仍然是一个重大挑战，给全球供应链带来了压力。据《海运运输评论》2023年报道，拥堵导致230万个标准箱（TEU）的运力被闲置。泊位和码头起重机（QCs）作为港口为进港船舶提供的关键资源，对于确保码头高效运营至关重要。近期研究重点关注了多种港口资源的综合规划（Guo等人，2024年），强调了有效资源管理以应对这些挑战的必要性。

泊位分配问题（BAP）主要解决集装箱船舶的泊位分配和停靠时间调度问题，是码头规划的基础方面，为码头起重机分配和堆场存储提供了关键输入（Imai等人，2014年）。码头起重机分配问题（QCAP）涉及码头起重机的静态分配，每艘船舶在整个装卸过程中被分配固定数量的码头起重机。码头起重机仅在船舶服务完成后才会重新分配。更为复杂的码头起重机调度问题（QCSP）首次由Daganzo（1989年）提出，它允许码头起重机在多艘船舶之间切换。此外，这种重新分配可以在初始船舶仍在服务过程中进行。这种时变QCSP问题目前研究还不够充分。

依次考虑BAP和QCAP的问题引出了泊位分配和码头起重机分配问题（BACAP），最初由Park和Kim（2003年）提出。同样，依次考虑BAP和QCSP的问题也导致了BAP和时变QCSP问题的出现。鉴于BAP和QCSP之间的相互关联性，整合这两个问题对于提升港口运营效率至关重要（Meng等人，2014年）。然而，即使在确定性环境中，BAP和时变QCSP也被认为是NP难问题（Rodrigues和Agra，2021年；Makhado等人，2025年）。截至2022年初，关于BAP的文献中只有12%涉及BAP和时变QCSP，而后者通常被认为是三者中最具挑战性的（Rodrigues和Agra，2021年）。

本研究旨在通过新颖的建模和算法方法推进BAP和时变QCSP优化的最新进展，填补当前港口运营文献中的关键空白。本文提出了一个综合的混合整数线性规划（MILP）模型，联合优化船舶停靠顺序、时间安排和时变码头起重机分配，以解决综合码头资源规划中的问题。为了解决大规模问题，引入了一种结合自适应大邻域搜索与强化学习（ALNS-RL）的新混合框架。该框架能够动态更新船舶和码头起重机调度方案，利用RL有效地引导搜索过程，找到高质量解。通过在统一的优化框架中解决BAP和时变QCSP问题，本研究不仅深化了理论理解，还提升了集装箱码头调度的实际能力，为港口运营中的这一关键挑战提供了有意义的解决方案。

本文的结构如下：第2节回顾了相关研究；第3节详细介绍了用于BAP和时变QCSP的方法论；第4节介绍了ALNS-RL方法；第5节讨论了数值实验的结果与分析；第6节总结了全文。

节选内容

文献综述与研究空白

本研究旨在开发一个优化模型和高效算法，用于解决综合的BAP和时变QCSP问题。因此，本节主要回顾了基于优化的研究领域中与BAP、QCAP和QCSP相关的研究文献。对于更全面和系统的港口运营概述，有兴趣的读者可以参考最近的综述研究（如Makhado等人，2025年）。此外，还总结了从中发现的研究空白。

问题描述

集装箱航运公司通过定期班轮服务进行运营，要求港口能够管理可预测但复杂的船舶流量。在船舶到达之前，每艘船舶会提交一份服务请求，其中包含关键信息：预计到达时间（ETA）、需要处理的集装箱体积、预期离港时间以及船舶类型（这会影响所需的码头空间和水深）。港口运营商必须将这些请求整合成一个协调的运营计划，以分配

解决方案算法：综合ALNS-RL方法

在以往综合决策研究的基础上，所提出的方法进一步考虑了船舶在港口停留时间与每个时间步长内的码头起重机分配之间的相互作用。虽然启发式算法（如GA和PSO）常用于处理较大规模的问题（Zhen等人，2021年），但由于船舶和码头起重机之间的复杂相互作用，它们经常难以找到高质量解。相比之下，ALNS可以提高解决方案的效率

数值实验

本节基于从中国某集装箱码头收集的主要数据进行了案例研究。该码头具有2500米的岸线长度，包含10个泊位和23台码头起重机。泊位1至3、4至8以及9至10的长度分别为300米、200米和400米。测试数据集包括船舶长度、泊位长度、预计到达时间以及以二十英尺当量单位（TEU）表示的集装箱处理量。规划周期设置为48小时。

结果总结

本研究解决了BAP和时变QCSP问题，这是港口运营研究中一个复杂且研究不足的问题。有效分配泊位和调度码头起重机的重要性不容忽视，因为它们直接影响港口运营的效率和盈利能力。通过将BAP和QCSP整合到一个统一模型中，本研究为该领域提供了新的见解，并确保决策以协调的方式做出，从而最终提升整体性能。

CRediT作者贡献声明

程成：撰写——审稿与编辑、方法论、资金获取、概念构思。李增双：撰写——审稿与编辑、初稿撰写、可视化、验证、方法论、正式分析、数据整理。张勇：监督、资金获取、概念构思。

利益冲突声明

作者声明他们没有已知的财务利益或个人关系可能影响本文所述的工作。

致谢

本研究得到了国家自然科学基金（52302374）、中央高校基本科研业务费（RF1028623090）、广西重大科技项目（AA23062021）以及江苏省双创计划（JSSCBS20230031）的资助。