包含冲突引发抢占操作的散货港口泊位分配与堆场安排集成优化

《European Journal of Operational Research》：Integrated berth allocation and yard assignment with conflict-induced preemptive operations in bulk cargo ports

　　

## 摘要要点

• 一种考虑带setup的抢占式操作的综合泊位分配与堆场分配的紧凑数学模型。

• 一种由新型分解与标签设置代理定价加速的有效分支定价算法。

• 一项对抢占式与非抢占式策略均进行考察的大规模计算研究。

## 引言

干散货航运在全球海运物流中发挥着重要作用，尤其是在工业原材料的大规模运输方面。2024年，铁矿石的海运贸易量增长了约3.5%（UNCTAD，2025）。作为钢铁生产的基础原材料，铁矿石需要大规模的海运运输和码头处理。在此背景下，许多钢铁公司投资或依赖大型干散货码头作为其原材料物流系统的一部分，以提高运营效率并降低物流成本（ArcelorMittal Nippon Steel India，2024）。本文所考虑的运营场景受一家中国钢铁公司运营的实际干散货码头的启发，该码头与下游钢铁生产相集成。

如图1所示的散装物料进口作业中，散装物料首先在泊位侧从船舶上卸载，然后运输并堆存在堆场进行临时储存，等待在需要时进行取料作业以供后续生产使用。从泊位侧到堆场侧的运输通过一系列互联的皮带输送机完成。一旦启动，进口作业的三个子操作（即卸载、运输和堆存）必须连续且同步进行，因为它们之间没有缓冲。换言之，在卸载某种物料的过程中，必须首先建立由卸船机、皮带输送机路线和堆料机组成的作业联线，然后同步运行。其中任何一个组件的中断都会导致整个联线停止。因此，在本文研究的场景中，"抢占"并非指整体中断船舶的作业，而是指临时暂停该船舶上某一特定物料所关联的卸载—运输—堆存联线。当分配给该物料的堆存行由于堆取料机（SR）冲突而不可用时，系统可以选择等待直到所需的堆存行资源再次可用并恢复中断的操作，也可以切换到同一艘船上的另一种物料。因此，干散货港口中与泊位和堆场相关的决策高度相互关联。

与集装箱码头不同，干散货港口中泊位和堆场相关决策的强关联性要求泊位分配与堆场分配进行同步，即我们必须以综合方式考虑泊位分配问题（BAP）和堆场分配问题（YAP）。这大大增加了进口流程调度的复杂性，使得设计有效的优化方法来求解此类复杂问题以避免高昂的物流成本变得至关重要。大多数干散货港口采用离散泊位布局，整个堆场由若干独立的堆存行组成，每一行都是一个长条形的连续堆存区域。在堆场分配问题中，每种物料的储存位置应从分布于不同堆存行中的若干候选储存位置中决定。

在许多干散货港口中，堆料机和取料机要么安装在同一轨道上，要么集成为专用的堆取料机。因此，同一堆存行内的堆存和取料操作往往紧密耦合，可能相互干扰。此类冲突不仅可能源于堆取料机之间的直接交互，还可能源于皮带输送机联线的限制或共享装卸设备的占用。当这种情况发生时，与某种物料相关的卸载—运输—堆存联线可能不得不暂时中断，因为SR冲突导致所分配的堆存行或相应的装卸系统不可用。在本文中，我们将此类情况称为SR冲突。这一运营视角也得到了干散货码头文献的支持。近期的研究报告指出，取料—装车作业可能因设备处理能力有限和操作线可达性受限而遭遇冲突和延误（Liu等，2024）。在码头层面，de Leeuw（2025）对Tata Steel IJmuiden的报告指出，设备堵塞（BE）包括堆料机/取料机被占用和皮带输送机路线不可用等情况，且BE占平均泊位状态的10.1%。

在本文所考虑的钢铁生产场景中，干散货码头通常与下游工厂共址或紧密相连。这种集成式布局在行业实践中也得到证实（ArcelorMittal Nippon Steel India，2024），意味着堆场库存被直接取料投入生产，从而在储存与需求之间形成了紧密的耦合。因此，取料操作被赋予更高的优先级，因为它们必须在规定的时间内满足下游生产需求。因此，当SR冲突导致所分配的堆存行或相关装卸系统暂时不可用时，与受影响物料相关的卸载—运输—堆存联线可能不得不暂时中断。由于此类操作可能持续数小时至数天，假设每次堆存操作必须在单个不间断的连续段内完成可能具有限制。此外，延长船舶停留时间的中断和联线重建在实际中也可能产生额外的延误相关成本，鉴于船舶在港时间和港口等待在海运中仍然具有重要的运营相关性（UNCTAD，2025）。然而在实际中，中断并非没有代价。每次中断都可能引发当前进口联线的切换。在恢复处理之前，包括皮带输送机在内的运输联线必须重建，且残留物料必须被清除。这一setup操作需要额外的时间、成本、能源消耗、清洁工作和操作风险。因此，运营商通常对切换次数施加严格的限制。这些setup效应可能增加船舶停留时间，对排放和延误相关的租船成本产生潜在影响。

在本文考虑的运营条件下，纯粹的非抢占式模型可能具有局限性，因为它要求每个任务在单个不间断的可行时段内完成。这可能导致运营商不得不等待足够长的连续窗口或推迟任务，尽管在本文研究的场景中，中断的操作可以在所需的堆场资源再次可用且相应联线重新建立后恢复。因此，我们研究了综合泊位分配与堆场分配问题（IBYP）的带中断次数上限的抢占式变体，其中抢占允许一个任务跨越多个可行时段，每次中断都会产生与setup相关的惩罚，并受到明确的上限约束。在此意义上，有限抢占相对于纯粹的非抢占式模型提供了额外的运营灵活性，同时仍然反映了实践中观察到的切换限制。

从经典的三字段调度分类法（Graham等，1979）的角度来看，本文研究问题的堆场侧调度部分与Liao和Sheen（2008）研究的抢占式并行机调度问题 $Pm,NCwin \mid p_mtn, r_j, M_j \mid C_{max}$ 密切相关。在此解释中，每个物料处理操作对应于一个作业，堆存行充当并行机，$M_j$ 表示某物料的候选堆存行集合，$NCwin$ 捕捉由于预定取料操作导致的堆存行间歇性不可用性，$r_j$ 表示船舶引起的释放限制，$p_mtn$ 表示可中断的物料处理。Liao和Sheen（2008）所考虑的经典问题不包含setup时间和setup成本，并且可以通过基于网络流的方法在多时间内求解。相比之下，当中断引发setup需求时，抢占式调度变得更加困难，且带有抢占和setup时间或成本的相关调度问题已知包含NP-hard变体（Allahverdi，2015；Monma和Potts，1993）。本文研究的问题进一步扩展了这一经典调度结构，要求每种物料必须始终分配给同一堆存行，通过船舶级资源限制将同一艘船所运载物料的加工程序耦合在一起，明确限制额外中断的次数，并将每次中断与联线重建时间和成本相关联。此外，这些堆场侧调度决策与泊位分配决策联合优化，目标函数综合考虑船舶运营成本、延误惩罚和联线重建成本，而不仅仅是最小化完工时间。

图2比较了一个抢占式调度（图2(a)）和一个非抢占式调度（图2(b)），针对一个具有三个堆存行、两艘船舶、每艘船两种物料的实例，且在相同的堆场分配下（以虚线彩色线表示）。对于每个堆存行，因取料操作而不可用的时段在左侧标出。两种不同的斜纹图案区分了两种类型的setup/联线重建时段。点状斜纹矩形表示物料完成后的切换所对应的重建操作，而对角斜纹矩形表示SR冲突导致中断后的切换所对应的重建操作。在任一类型的重建时段期间，联线被重新配置，且不处理任何物料。在后者情况下，系统可以选择等待并在所需堆存行资源再次可用后恢复中断的操作，也可以将联线切换到同一艘船上的另一种物料；如果选择后者，则会产生额外的setup/联线重建时段。例如，在图2(a)中，时刻10处的点状斜纹时段跟在物料完成和后续切换之后，而时刻6处的对角斜纹时段跟在SR冲突导致的中断和后续切换之后。通过明确表示这些重建时段，图2还展示了有限抢占的潜在运营优势。抢占式调度在时段21完成进口作业，而非抢占式调度尽管切换次数少了两次，却在时段24才完成。此例说明了一个运营权衡，而非暗示抢占式调度总是经济上更优的。抢占式操作引发的额外联线重建操作会产生与setup相关的成本，包括联线重建和残留物料清洁所付出的努力，而更早完成可能降低船舶运营成本和延误惩罚。因此，只有当这些节省超过额外联线重建成本时，抢占才更优；否则，等待并避免额外切换的成本更低。相应地，该示例表明有限抢占可以缩短总体完工时间，但其经济上的可取性取决于提前完工与额外联线重建操作之间的权衡。

从环境角度来看，完工时间缩短三个时段也说明了缩短船舶停留时间的潜在效果。如果一个时段解释为一个小时，如计算实验中所示，这一量级的减少在代表性hotel-ing能源假设下，对应于约 $1 \times 10^3$ kWh的能源使用效应和约 $1 \times 10^2$–$1 \times 10^3$ kgCO?的相关碳排放效应。这些数字仅提供了一个示意性的数量级映射，而非特定码头的排放估计。我们将在第5.3节中通过关于最大允许抢占次数上限的敏感性分析进一步实证地考察抢占的运营价值。

本文其余部分安排如下：第2节回顾与本文工作相关的文献，随后阐述我们的贡献并概述论文结构。第3节正式描述问题并介绍备选数学模型，包括基于集合划分的形式化模型。第4节描述基于分支定价（B&P）求解方法的精确算法。具体而言，本节重点描述有效不等式以及定价算法的设计。第5节展示对基准实例的大规模计算分析。最后，第6节总结全文并展望未来的研究方向。

## 相关工作

港口运营管理在学术界已被广泛研究，尤其是在集装箱码头方面。如前所述，泊位分配和堆场分配是本文所研究的综合问题的两个关键决策阶段。在本节中，我们回顾与本文所处理问题密切相关的文献。

Bierwirth和Meisel（2010）提供了BAP的一种显式分类方法。根据...，BAP可大致分为连续型、离散型和混合型BAP。

## 问题描述与数学模型

设 $\mathcal{T}=\{1,\ldots,T\}$ 表示规划期内连续的时段集合。我们还给定一个船舶集合，用 $\mathcal{N}$ 表示，一个泊位集合，用 $\mathcal{B}$ 表示，以及一个堆存行集合，用 $\mathcal{R}$ 表示。对于每艘船舶 $i \in \mathcal{N}$，它运载若干种等待卸载的物料。令 $\mathcal{K}_i$ 为船舶 $i$ 所载物料的集合。注意 $\mathcal{K}_i \subseteq \mathcal{K}$，$i \in \mathcal{N}$，其中 $\mathcal{K}$ 为所有物料的集合。对于船舶 $i$ 所载的每种物料 $k \in \mathcal{K}_i$，仅有有限的候选储存位置...

## 精确的分支定价求解方法

本节描述IBYP的分支定价（B&P）求解方法。

在每个分支节点，我们通过列生成迭代方法求解集合划分模型 F3 的线性规划松弛（限制调度子集 S' ? S，称为受限线性主问题，简称 RLMP）。在每次迭代中，求解定价问题以识别可能构成最优解且具有负约化成本（相对于与 RLMP 相关联的当前对偶解）的列。读者请参阅计算结果部分。本文报告了第4节所述精确 B&P 算法（以下简称 EXM）的计算结果。算法 EXM 使用 .NET Core 8.0 框架以 C# 实现，所有实验均在同一台个人计算机上进行，该计算机配备 Intel Core i9-14900K CPU（3.20 GHz，24核，32线程）和 64 GB 内存，运行 Windows 11 专业版操作系统。使用 ILOG CPLEX 优化器 22.1.1.0 作为优化求解器。结论部分：本研究为散装材料港口的进口作业小时级规划开发了一种集成模型，在考虑可中断装卸、并行作业和堆存—取料冲突的同时，同步优化泊位分配和堆场分配。我们提出了两种模型：紧凑离散时间模型和集合划分模型。后者通过分支定价方法在大规模规模下求解：在可抢占情形下，每个定价问题首先通过启发式方法求解。CRediT 作者贡献声明：杨杰夫：写作——审阅与编辑、写作——原始草稿、可视化、验证、软件、资源、项目管理、方法论、调查、形式化分析、数据整理、概念化。孙德峰：写作——审阅与编辑、监督、资金获取。Roberto Baldacci：写作——审阅与编辑、监督。利益冲突声明：作者未报告任何潜在的利益冲突。致谢：作者感谢匿名审稿人和编辑对本论文的宝贵意见和认真审阅。本研究受国家自然科学基金重大项目（72192830，72192831）、一般项目（72472020）以及"111计划"（B16009）和中国留学基金委员会（CSC）资助。杨杰夫｜孙德峰｜Roberto Baldacci