大型船舶的船体体量巨大，无法以整体方式建造，一般以三级中间产品分级建造，按照规模由小到大进行划分，可分为零件级、组立级和分段级。其中，分段在船厂的生产设计、生产管理中居于核心地位。多数分段的水平投影尺寸在20 m×20 m以内，高度在5 m以内，重量为100~300 t。分段在组装完成之后，大部分还要经历4种工艺，即预舾装、冲砂打磨、涂漆和预总组，由专用的平板运输车实现场地之间的转运。为了充分利用各个工艺场地的制造资源，一般会划分出30%~40%的场地面积作为分段堆场，用于各个工艺之间的分段周转。分段堆场常为露天矩形场地，并通过在地面划线分割为方形分段堆位。

在分段加工过程中，除了用于满足分段加工需求的转运(即生产性转运)，还有大量因堆场中分段互相阻挡导致的衍生转运，造成了资源的浪费和成本的提升，称之为非生产性转运。在韩国现代重工造船厂，分段加工中的生产性转运次数平均为7.8次，非生产性转运次数平均为2.8次，即全船厂非生产性转运率约为25.7%^[1]。与之相比，我国船厂分段转运过程管理粗放，堆场调度效率不高。以国内技术领先的某大型船厂为例，根据本文对该船厂的实地调研和对分段转运日志的统计结果，某号船分段加工中的生产性转运平均次数为7.9次，非生产性转运平均次数为4.9次，即非生产性转运率约为38.0%；该船厂年均分段转运次数约为3.7万次，年均转运成本达到2 200万元，按照38%的非生产性转运率水平估算，其中非生产性转运成本约为840万元，如果该船厂的非生产性转运率达到韩国现代重工的水平，每年可节约成本360万元。在造船行业国际竞争日趋激烈的当下，降低非生产性转运率，对我国船厂降低成本、提高准时交船能力具有重要作用。

韩国蔚山大学Park等^[1-4]最早研究了如何降低非生产性转运率的问题，提出了网格模型用于堆场建模，用矩阵记录堆位上的分段信息，提出了一些直观的调度规则，仿真调度效果优于生产实际情况。但是网格模型不允许分段在堆场内转弯，与实际不符，限制了优化效果。同济大学张志英等^[5-10]使用以堆位为图节点的图模型作为堆场模型，应用多种智能算法和最短路径算法优化调度效果，但是其事先设定了分段的出入顺序，仅优化分段转运路径和入场堆位，限制了调度效果。图模型允许堆场内转弯，与实际更加接近，但是不同轨迹下平板运输车在相邻节点之间的转移难度不同，而图模型的表达方式默认堆场内可以定点转弯、轨迹不影响转移难度，这导致图模型在描述转弯时不准，在实用中仍有优化空间。陶宁蓉和陈凯等^[11-13]在这两个模型的基础上，在调度策略层面研究了入场分段堆位分配策略、分段临时移动策略、基于禁忌搜索的分段调度策略，取得了截至目前最好的调度效果，但是在入场分段堆位分配时混淆了堆位分配顺序和分段入场顺序，导致作为优化目标的启发式函数耦合了堆场自由度及其变化度、影响度，与减少阻挡分段的原目标之间的解释性不足，限制了调度效果。此外，由于船厂的总堆位数一般为300~500个，而以上3个团队所研究调度策略的算法效率不足，不适用于堆位数超过100个的堆场调度问题，对更大规模调度问题往往只能采取分而治之的策略，难以实现整体调度。

因此，针对现有研究中堆场模型难以准确表达平板运输车的堆场内转弯，以及调度策略的效果有待提高、算法效率不足的问题，本文从堆场模型和调度策略两个方面开展了研究：1) 研究更接近实际的堆场模型，特别是提高模型对平板运输车堆场内转弯的描述能力，允许平板车在堆场中转弯并留足转弯空间；2) 研究更高效、更快速的调度策略，降低分段转运中的非生产性转运率，同时算法效率足以应用于船厂规模的堆场调度问题。

1 船舶分段堆场的改进图模型 1.1 改进图模型建模

如上所述，现有堆场模型主要有两种，即网格模型和图模型，前者限制了堆场内平板运输车只能直线行驶；后者以堆位为节点建图，边的权重代表了在节点之间的转移难度，允许转弯，这更接近实际情况，但是难以描述堆场内的转弯。

本文仍以图作为描述堆场状态的形式，为了计算最佳路径，边定义为节点间的直接转移，权重为转移难度。历史轨迹通过影响平板运输车在堆位上的姿态(经向或纬向)来进一步影响转移难度，平板运输车的负载状态(负载或空载)也会影响转移难度，为了准确地设置边的权重，需要在节点中表达堆位、平板运输车的姿态以及负载状态信息。负载状态不因平板运输车的运动而改变，即图的负载节点和空载节点之间不存在边，故一个堆场下，可以使用两个图，即空载图和负载图来分别描述空载平板运输车和负载平板运输车面临的堆场状态。

因此，本文提出改进图模型〈g^U，g^L〉，包含空载图g^U和负载图g^L。改进图模型是一个状态类实体，对应了堆场在某个时刻的状态。改进图模型及其相关实体的主要实体关系如图 1a所示。在g^U和g^L中，堆场间道路作为一个特殊的节点，称为“道路姿态”，联系各个堆场；其余节点为堆位和姿态的耦合，称为“堆位姿态”；二者合称“位姿”。图 1b是堆位姿态、堆位、分段等实体的示意图，其中也包含了堆位的相邻堆位、堆位的周边区域、平板运输车等概念的图示。边为相邻节点间的联系，表现为“单步”，权重为这一单步的转移难度，一共有5种单步类型，其中侧滑步是由其他类型的单步复合而成，如图 1c所示。

1.2 改进图模型相关实体说明

为描述堆场调度过程，形式化定义了改进图模型的相关实体，如表 1所示。

上标用来区分属于同一父类的不同子类，下标用于索引不同实例。场外分段的Shape为方形时，入场后允许空载平板车从其下方经纬两个方向穿过，矩形时仅允许一个方向。InDate和OutDate分别代表分段的入场日期和出场日期。Row、Column和OpenSides代表堆场行数、列数和开口边。RowIndex、ColumnIndex代表堆位行索引和列索引。Pose代表堆位姿态的姿态(经向或纬向)。AdjacentPs指相邻位姿列表p^C，是其所在堆位的周围区域中的所有位姿；p^W是所有所在堆位在开口边上的堆位姿态。ObstructiveB^Is是单步上的阻挡分段列表。单步x仅可能出现在相邻位姿之间，单步的p_k1和p_k2是单步的起点和终点位姿，单步的Difficulty(难度)由单步的类型、单步起止位姿周围堆位的分段状态等决定。移动m是平板运输车没有发生负载状态变化的一系列首尾相接的单步，使用x^Us或x^Ls来表示这些空载或负载单步，移动的p_k1和p_k2是移动的起点和终点位姿。转运t对应了堆场状态的一次转变，分为入场转运和出场转运，均由起始堆场状态s₁、被移动的分段(b^O或b^I)、终止堆场状态s₂、两次m(一次m^L、一次m^U)组成。根据改进图模型中g^U和g^L的定义，某一堆场状态s下，g^U的邻接矩阵为

$ \begin{matrix} {\boldsymbol{A}^{\mathrm{U}}=\left[a_{k_1 k_2}^{\mathrm{U}}\right] .} \\ {其中, a_{k_1 k_2}^{\mathrm{U}}= \begin{cases}x_{p_{k_1} p_{k_2}}^{\mathrm{U}} . \text { Difficulty, } & x_{p_{k_1} p_{k_2}}^{\mathrm{U}} \text { 存在; } \\ +\infty, & \text { 其他情况. }\end{cases}} \\ \end{matrix} $

(1)

g^L的邻接矩阵为

$ \begin{gathered} \boldsymbol{A}^{\mathrm{L}}=\left[a_{k_1 k_2}^{\mathrm{L}}\right] . \\ 其中, a_{k_1 k_2}^{\mathrm{L}}= \begin{cases}x_{p_{k_1} p_{k_2}}^{\mathrm{L}} \text {. Difficulty }, & x_{p_{k_1} p_{k_2}}^{\mathrm{L}} \text { 存在; } \\ +\infty, & \text { 其他情况. }\end{cases} \end{gathered} $

(2)

在x的难度设置上，每个阻挡分段的难度为1，从某个分段下穿过的难度设为0.01，无阻挡、无下穿、无转弯的难度设为0.000 1，无阻挡、无下穿、有转弯的难度设为0.000 2。侧滑步的难度由其两种分解方式中较低的累积难度决定。这样分级的难度设置可判断m或t的可行性：若m或t中包含的某个x的ObstructiveB^Is不为空，则其为不可行，累积难度≥1；反之，其为可行的，累积难度小于1。如果存在t为可行转运，用最短路径算法(本文使用经典的Dijkstra算法^[14])可求解可行的、少从分段下穿行的、距离较短的两次m，如图 2所示的分段出场可行性判断算法(算法1)和空堆位可达性(即入场可行性)判断算法(算法2)。

1.3 模型效果分析

对现有网格模型、图模型和本文所提出的改进图模型的模型效果进行分析对比。以某堆场出场当日到期的4个分段为例，用3种模型得到的最佳出场方案如图 3所示，箭头上的序号为出场转运的顺序：

1) 网格模型出场方案。只允许直线运动，平板运输车无法纬向下穿位于(2, 8)，(3, 11)处的两个矩形到期分段，因此无法在这两个分段出场；位于(2, 14)，(3, 15)处的两个分段可以通过直线运动实现出场，需要在第2次和第3次转运中出场2个阻挡分段。

2) 图模型出场方案。允许转弯，位于(2, 8)，(3, 11)处的两个矩形到期分段可以出场，但是其无法区分转弯处平板车的姿态，进而无法识别转弯处和准确评估转弯处的阻挡分段数量，给出的折线移动在转弯处缺少空间，这与实际是有区别的。

3) 改进图模型出场方案。兼顾转弯处的空间需求，为了腾挪转弯空间，需按序移出9个阻挡分段。

对以上3种方案进行比较，可以发现改进图模型克服了以堆位为节点的图模型无法准确表达转弯及其难度的问题，允许平板车在堆场中转弯并留足了转弯空间，使堆场模型更接近实际。

2 船舶分段堆场三阶段调度策略 2.1 三阶段调度策略架构

船厂分段堆场的每日调度通常采用先出场后入场的策略，为了研究高效、快速的调度策略，本文将分段调度过程分为3个阶段。第一阶段为无阻挡出场阶段，存在可以直接无阻挡出场的到期分段；第二阶段为有阻挡的出场阶段，到期分段的出场需要先搬离阻挡分段；第三阶段为入场阶段，将之前临时出场的阻挡分段和新入场的分段重新选择堆位入场。非生产性转运产生在第二、三阶段，存在阻挡分段是产生非生产性转运的直接原因。

基于船舶分段堆场的改进图模型，对第二、第三阶段阻挡分段的具体产生原因和在调度中减少阻挡分段的对策进行了具体分析，提出了分段堆场三阶段调度策略，以及各个阶段分段调度方案的求解方法，三阶段调度策略架构如图 4所示。

在无阻挡的出场阶段，需要为到期分段规划合适的出场顺序，应用提出的算法3实现所有的到期分段出场，可以得出这一阶段的分段出场调度方案；在有阻挡的出场阶段，要以尽可能少的阻挡分段为代价，让所有到期分段出场，这一阶段通过应用提出的算法4将剩下的到期分段出场，同时伴随着阻挡分段出场，这部分阻挡分段要暂存在船厂道路上，在之后的入场阶段与新入场分段一起选位入场；在入场阶段，解耦了堆位分配顺序和分段入场顺序，通过合理安排入场顺序避免了本阶段产生阻挡分段，通过优化空堆位分配方案减少未来调度中的阻挡分段。

在三阶段调度策略中提出的4个算法及其调用的算法1和算法2中，存在两个难点，即如何加快求解速度和如何设计堆位分配方案的评价依据。针对这两个问题，研究了快速求解算法和阻挡分段预测算法。

2.2 快速求解算法

为了加快调度方案的求解速度，使本文的策略适用于船厂规模的堆场调度问题，提出了快速求解算法，包括：

1) 增量式邻接矩阵计算。每次搬入或者搬出一个分段，堆场状态的g^U和g^L的邻接矩阵需要重新计算。如果遍历计算邻接矩阵的每个元素，单个矩阵的运算复杂度为O(n²)，n为堆场规模，非常耗时；而单个分段的改变，只会影响这个分段对应的堆位及其周围区域的位姿节点之间的边的权重。因此，通过计算邻接矩阵A^U和A^L中这些受影响节点之间边的权重对应的元素，即可实现邻接矩阵计算，如图 5中算法7.1所示。在算法1第3步，算法2第3步，算法3第3步，由于堆场状态仅发生了部分分段的改变，因此可以应用增量式邻接矩阵计算。

2) Dijkstra算法(及其逆向应用)结果的多算例共享。Dijkstra算法的输出是某一个起点到其他所有节点之间的最短路径，其运算复杂度为O(n²)，反复调用非常耗时，如果堆场状态没有改变，通过在全部有相同起点的算例之间共享已有的Dijkstra算法结果，可以节约大量的计算，如图 5中算法7.2所示；另外，Dijkstra算法具有对称性，可将某一堆场状态的邻接矩阵转置后用于求从所有节点到某一个共同终点之间的最短路径，即逆向应用，其结果的多算例共享如图 5中算法7.3所示。在算法5第1步，同一堆场状态下计算多个空堆位是否可达，所有算例在调用算法2的第1步时，有共同的起点p^W和不同的终点，可以共享同一个Dijkstra算法的结果；在算法3第1步和算法4第1步，均为同一堆场状态下计算多个分段是否可以出场，所有算例调用的算法1中的第1步有共同的终点p^W和不同的起点，可以共享同一个Dijkstra算法逆向应用的结果。

2.3 阻挡分段预测算法

分段入场时，首先需要获取可达空堆位集，为入场提供备选堆位。在堆位分配时，为了在未来有更少的阻挡分段，需要评估新入场分段是否会在未来成为阻挡分段，优先为剩余场内周转期最长的分段分配，使其不会在未来成为阻挡分段的可达空堆位。转运路径允许转弯，这不同于Park和Tao只允许直线转运路径的方法，因此难以通过遍历每个分段未来的所有出场路径来判断新入场分段是否会成为阻挡分段，需要研究具有针对性的阻挡分段预测算法。

本文通过一种简化的情境来模拟所有在场分段出场，即只出场无阻挡到期分段，被阻挡的到期分段则延后一天，进而观察这些分段路过可达空堆位的情况，预测新入场分段是否会在未来的调度中成为阻挡分段，具体步骤如图 6中算法8所示。

3 实验验证 3.1 快速求解算法验证

为了验证本文提出的快速求解算法，设置了13个仿真实验，基本信息如表 2所示。这些仿真实验在不同规模的方形四面开口堆场下进行，仿真周期均为2 d，负载率均为80%，分段堆场内周转期遵循1~7 d的离散均匀分布。

仿真中，堆场状态在初始化时，堆场状态对应的邻接矩阵采用遍历式计算；而当堆场状态仅发生部分变化时，采用增量式计算。统计遍历式计算和增量式计算的调用数和耗时，如表 3所示。增量式计算耗时远远少于遍历式，以实验13为例，单次计算耗时仅为遍历式的3%。

统计调用Dijkstra算法(包括其逆向应用)的次数，和以其结果为基础进行的转运可行性判断数(算法1和算法2的调用数)，如表 4所示。单次Dijkstra算法的结果可以多次应用在转运可行性判断中，最多时复用率达6.83次，节省了大量计算。以上结果证明了快速求解算法的有效性。

3.2 阻挡分段预测算法验证

为了验证阻挡分段预测算法(算法8)的有效性，设置单堆场仿真，堆场为10行、10列，四面开口，负载率为80%，分段的堆场内周转期遵循分布为1~10 d的离散均匀分布，仿真周期250 d。

对所有新入场分段，比较算法8给出的是否为阻挡分段的预测结果，以及在后续仿真中是否为阻挡分段的仿真结果，统计汇总为混淆矩阵，如表 5所示。

根据混淆矩阵，算法8的准确率为

$ \frac{296+3313}{296+309+229+3313} \times 100 \%=87.0 \%. $

(3)

这验证了阻挡分段预测算法的有效性，其预测结果和仿真获得的结果吻合，可以作为评估入场堆位分配方案的有效指标。

3.3 对比实验及船厂多堆场仿真

为了验证本文所提出调度策略的效果，以不允许平板车堆场内转弯的策略中非生产性转运率最低的Tao^[11]的策略，以及允许平板车在堆场内转弯，但未专门检验转弯空间，调度策略的研究较为完善、非生产性转运率较低的Chen^[12]策略为对照组，在只有一个长边为开口边的单堆场中，分段堆场内周转期遵循分布为1~7 d的离散均匀分布，在不同负载率(70%、80%和90%)、不同堆场形状(6×10、5×12、4×15和3×20)下进行多组堆场调度仿真，每组包含100次生产性转运。对3个策略的非生产性转运率和耗时求均值，结果如图 7所示。以负载率90%、6×10的堆场为例，本文策略、Chen的策略和Tao的策略分别获得了18%、34%和51%的平均非生产性转运率，耗时均值分别为17、731和163 s。在对比实验中，本文调度策略的非生产性转运率明显低于对照策略，耗时远小于对照策略。

以某船厂的真实堆场调度为背景，将提出的三阶段调度策略应用在船厂多堆场仿真上，验证其对大规模调度问题的有效性。分段堆场的最大负载率为85%；新入场分段中有90%的分段在入场时就给定出场日期，堆场内周转期设为1~10 d的均匀分布，每隔14 d会进行再规划(模拟双周计划会)确定未定分段的出场日期；40%的分段为矩形，下方只能通过一个方向的空载平板车；为保持负载率，每日出场到期分段，并入场与当日出场的到期分段数目相同的新分段；堆场规模为9个堆场、370个堆位，某一时刻堆场状态如图 8a所示；仿真周期100 d。这一仿真共耗时27 364 s(7.6 h)，共完成了12 194次生产性转运，1 172次非生产性转运的调度，非生产性转运率如图 8b所示。

船厂多堆场仿真中，通过应用本文提出的三阶段调度策略，获得的后40 d平均非生产性转运率为10%，与船厂现有38%的非生产性转运率水平相比，可为这种规模的船厂每年节约690万元，大幅降低船厂分段转运成本。策略求解速度快，实验中7.6 h内求解了100 d船厂规模的堆场调度问题。

4 结论

针对现有研究中存在的堆场模型和调度策略的不足，通过引入“位姿”节点构造分段堆场的改进图模型，克服了以堆位为节点的图模型无法准确描述转弯的问题，有效表达了堆场中分段的形状和姿态，允许平板车在堆场中转弯并留足了转弯空间，使得堆场模型更接近实际，为后续评估转运的可行性、求解调度方案打下了模型基础。提出了求解各个阶段调度方案的船舶分段堆场三阶段调度策略，运用快速求解算法加快求解速度，通过解耦堆位分配顺序和分段入场顺序、运用阻挡分段预测算法优化了入场分段堆位分配，优化了调度效果。在船厂多堆场仿真中将堆场的非生产性转运率降低到10%，可大幅降低船厂分段转运成本。策略求解速度快，可以在合理时间内求解船厂规模的堆场调度问题。