干散货码头互联取料机的无冲突调度

《TRANSPORTATION RESEARCH PART C-EMERGING TECHNOLOGIES》：Conflict-Free scheduling of interconnected reclaimers in dry bulk terminals

　　

• 我们研究了一种面向多轨取料机调度的新型无冲突调度方法。• 时空网络模型刻画了取料机间的互联作业关系。• 两级元启发式将任务排序与无冲突路径规划解耦。• 并行岛屿-细胞算法实现了显著加速。1. 引言干散货，如煤炭和铁矿石，对全球电力生产和钢铁生产至关重要。它们占全球海运贸易总量的83%，使得干散货运输成为国际贸易的关键组成部分（Benbrik et al., 2025b, Cao et al., 2025a）。干散货码头是关键的跨模式枢纽，不仅处理散货的进出口，还作为运输网络中的必要节点（Wang et al., 2024）。其运营效率直接影响供应链的流畅性和整体运输可靠性。随着全球干散货贸易需求的增长，提高码头效率和吞吐量可有效减少船舶和列车的延误，带来显著的经济效益，并促进全球运输的优化与可持续化。堆场是干散货码头中存储和管理进出口散装物料的关键运营枢纽。在进口流程中，船舶由卸料机卸载，物料通过输送带系统运至堆场，由堆料机堆垛。在出口流程中，取料机从料堆中取料并装载到输送带上，运至装车点。为实现高处理量，多台取料机协同作业，如图1所示。每台取料机服务于其轨道两侧的材料堆，多台设备可能从相邻轨道上的共享材料堆取料，形成了一个高度互联的系统。虽然完整的码头涉及堆料机和取料机，但这些作业在实践中往往解耦以防止严重的交叉干扰。因此，本研究明确聚焦于取料作业，针对专门的清料阶段。下载：下载高分辨率图片（646KB）下载：下载全尺寸图片图1. 进口干散货码头堆场的布局示意图。具体而言，这一协同挑战并非源于孤立的作业摩擦，而是源于多轨场景下深度交织的约束条件。与单轨布局中材料堆服务资格固定且局限于单条轨道不同，多轨堆场中内侧料位上的材料堆横跨两条相邻轨道，使得分配候选高度重叠，排除了轨道独立的分配决策。空间干涉限制也超出单条轨道的范围：将一个完全重叠的材料堆分配给某台取料机不仅会阻断同一轨道上的其"孪生"设备，还会阻断相邻轨道上的设备，将一个分配选择传播为跨轨道的约束链。最关键的是，任务分配与路径规划相互锁定在一个闭环中：材料堆在任务序列中的优先级定义了所有相邻取料机可行的时空窗口，而实际路径规划结果又反过来决定后续分配的可行性，使传统的单轨"先分配、后规划路径"分解方法从根本上失效。此外，这些约束因斗轮取料机的长行程作业而被放大，其占用了材料堆的全长并产生移动的禁行区域，加剧了重叠材料堆区域内的空间竞争。针对互联取料机无冲突路径规划的研究仍基本上处于未被探索的状态，因为在非规则布局和多轨不交叉约束下，任务分配与路径规划本质上相互耦合。目前，无冲突调度仅限于单轨场景，且未整合任务分配，限制了整体处理量（Angelelli et al., 2016, Xin et al., 2024a）。因此，需要一种将任务分配与无冲突路径生成相整合的新型方法。为应对这些挑战，本文提出了一种创新的一体化方法。首先，引入一种时空网络模型，统一任务分配、排序和不交叉约束，以更真实地刻画取料机作业。其次，设计一种定制化的两级元启发式框架，将任务排序与详细的无冲突路径规划解耦。这种分离简化了编码方式，并通过下层适应度评估建立反馈回路，从而降低复杂度、提高搜索效率，并从根本上避免不可行解。最后，开发了一种基于混合岛屿-细胞模型的并行算法，该算法在保持解质量的同时加速收敛，在大规模场景下实现显著加速，支持实际部署。1.1 相关研究1.1.1 干散货码头运营港口码头的决策问题通常分为战略层、战术层和运营层（Xin et al., 2015, Xin et al., 2014）。本研究聚焦于干散货码头的运营决策，涉及码头设备与资源的详细规划与调度。这些决策主要关注码头关键区域之间的作业协调，尤其是岸区和堆场。核心运营问题因此包括泊位分配、堆场存储空间分配以及堆取料机调度。在岸区，泊位分配和装船机调度是两个关键的运营问题。大量研究关注了泊位分配，产生了多种解决方法，涵盖精确算法（Martin-Iradi et al., 2022, Unsal and Oguz, 2019）、启发式方法（Cheimanoff et al., 2021）以及元启发式方法（Wang et al., 2022）。此外，泊位分配经常是多类型码头设备集成调度模型中的关键要素（Cao et al., 2025b, Song et al., 2024）。同时，装船机调度研究主要关注其与其他码头流程的集成，例如与泊位分配的联合调度模型（Cao et al., 2022）或与船舶交通管理相结合的模型（Wang et al., 2023）。堆场是干散货码头的关键区域，堆场存储空间分配和堆取料机调度是两个核心研究问题。为应对码头土地稀缺带来的高昂成本，堆场分配聚焦于最大化每个可用区段的体积利用率。为解决分散小料位的实际问题，Sun等提出了一种基于逻辑的Benders分解方法，以最优解决内部散货码头的存储空间分配问题（Sun et al., 2020）。此外，Tang等（2022）提出了一种比Sun等（2020）使用的槽位策略更灵活且更精确的存储空间建模方法，重点关注大型铁矿石码头。对于干散货码头，运营计划常因船舶到港时间不可预测、交货计划变化以及订单优先级调整而受到干扰。为应对这些动态变化，有研究提出了模型预测控制等方法，将处理过程建模为混合逻辑动力系统（Xin et al., 2018）。1.1.2 堆取料机调度除存储空间分配外，堆取料机调度也是一个关键研究主题。在干散货码头中，取料机沿堆场中的轨道行驶，堆料或取料以满足出站运输需求，形成并提取材料堆。早期研究主要关注任务分配和排序，对同轨不交叉约束的关注有限。堆取料机调度最早由Hu和Yao（2012）研究，他们考虑了单条轨道上一台堆取料机的作业。Kalinowski等（2017）研究了煤炭码头中单台取料机服务单个料垫的调度问题。类似地，Benbrik等（2025a）研究了一个每条轨道仅有一台斗轮取料机作业的场景。区别在于方法：Hu和Yao（2012）将问题建模为混合整数规划（MIP）模型并提出遗传算法来处理其复杂度，而Benbrik等（2025a）基于商品变量引入了一种新型混合整数线性规划（MILP）公式，为大规模算例开发了三种贪心启发式算法，并提出了一种有效的广义变邻域搜索算法以提高启发式结果的精确度。Jesus-Junior等（2025）研究了实际的取料机铁矿石取料问题并提出了一种混合元启发式算法，侧重于分配和排序而非同轨无冲突路径规划。为提高处理量，同一轨道上部署多台取料机，如图1所示。van Vianen等（2015）指出，使用两台设备而非一台可显著减少船舶和列车的等待时间。然而，这引入了复杂的非交叉约束以防止碰撞，需要同时协调取料和移动过程——这一挑战在文献中仍鲜有涉及。同轨两台堆取料机（或简称取料机）的无冲突调度由Angelelli等（2016）率先研究。然而，他们的限制性假设允许每台取料机仅改变一次方向。其方法要求将材料堆划分为不相交的子集以防止碰撞，这一策略在实际操作中往往不切实际。Unsal和Oguz（2019）将取料机调度与泊位和堆场分配相结合，使用基于逻辑的Benders分解算法，但其关注点在于码头层面的规划而非部分和完全重叠条件下的详细无冲突路径规划。ünsal（2020）研究了类似的多机场景，但在其简化的MIP模型中忽略了重叠材料堆，这可能导致移动过程中的碰撞风险。尽管采用约束编程方法处理非交叉约束，其抽象模型缺乏明确的公式化和详细的解释。较近的研究中，Xin等（2024a）研究了孪生取料机的路径规划问题，明确考虑了非交叉约束、重叠材料堆和任务排序。然而，通过预先确定每台任务由哪台取料机处理，其工作限制了运营灵活性。此外，单轨聚焦限制了其向多轨堆场的适用性。代表性堆/取料机调度研究的系统比较见表1。表1. 堆/取料机调度研究的系统比较。参考文献对象布局模型部分与完全重叠任务分配目标/度量（最小化）求解方法Hu和Yao（2012）堆取料机SM-MTMIP??生产周期遗传算法van Vianen等（2015）堆取料机SM-MTDES??列车等待时间规则ünsal（2020）取料机MM-MTMIP??总加权完成时间约束编程Angelelli等（2016）取料机MM-ST???生产周期多项式时间Kalinowski等（2017）取料机SM-STMIP??总完成时间分支定界Unsal和Oguz（2019）取料机MM-MTMIP??总加权离港时间LBBDBenbrik等（2025a）取料机SM-MTMILP??生产周期与流转时间VNSJesus-Junior等（2025）取料机N.S.-MT???总加权流转时间混合元启发式Xin等（2024a）取料机MM-STMILP??生产周期与行驶时间TLM本文取料机MM-MTMILP??生产周期与行驶时间（分布式）TLM注：R：取料机；S-R：堆取料机（组合型）；SM/MM/N.S.：每条轨道单机/多机/未指定；ST/MT：单轨/多轨；P&C：材料堆之间的部分和完全重叠；?/?：对应项的有无；MILP：混合整数线性规划；MIP：混合整数规划；DES：离散事件仿真；CP：约束编程；B&B：分支定界；LBBD：基于逻辑的Benders分解；VNS：变邻域搜索；TLM：两级元启发式。值得注意的是，非交叉约束也在集装箱码头起重机调度中有所研究，其中如握手区（Oladugba et al., 2023）或单向移动限制（Abou Kasm and Diabat, 2019）等策略简化了作业。尽管启发式方法有效解决了带有任务分配的双堆场起重机调度（Eilken, 2019），且岸桥调度因复杂度而异（Liang et al., 2018），但这些问题与取料机调度存在根本差异。与起重机不同，起重机的加工位置（如岸桥区或集装箱）不会相互干扰，而两台取料机由于材料堆区域重叠无法独立运行（见图2）。因此，我们的调度问题需要通过管理加工位置之间的空间干涉来实现，而不仅仅是限制行驶路径。下载：下载高分辨率图片（117KB）下载：下载全尺寸图片图2. 部分和完全重叠材料堆的示意。1.1.3 总结堆场是干散货码头的核心运营区域，堆取料机的协同调度对码头吞吐量具有关键影响。当多台取料机在同一轨道上作业时，必须严格执行非交叉约束以防止碰撞。尽管近期研究已针对孪生取料机的无冲突调度进行了探讨，但它们往往依赖限制性假设，如固定任务分配或简化布局，从而限制了运营灵活性。至关重要的是，现有方法很少考虑取料机必须穿越多条平行轨道和重叠材料堆的场景。这种多轨环境在任务分配、路径规划和作业同步排序中引入了耦合决策。因此，需要一种新方法在整个堆场范围内联合优化取料机的派工与移动时序，明确考虑包括空间干涉和重叠材料堆区域在内的实际约束。本研究仅聚焦于取料阶段，假设料堆已预先堆好。堆料机和取料机使用同一设备，但堆料涉及更复杂的空间决策。在进口干散货码头中，取料将物料转运至驳船或列车，而堆料发生在船舶卸货过程中。在共享料位上同时进行堆料和取料会引入额外的空间约束，形成一个建立在此基础上的更复杂的联合问题。联合堆取料机调度被确定为未来研究的重要方向。1.2 贡献本研究的主要贡献总结如下：• 我们研究了一种面向多轨布局互联取料机的新型无冲突路径规划问题，整合了任务分配、排序和防碰撞。虽然先前的单轨工作（Xin et al., 2024a）有效地将分配与路径规划解耦，但未捕捉多轨布局特有的跨轨重叠干扰。本研究通过解决这一局限性拓展了现有研究。• 我们提出了一种时空网络模型，统一了所有运营和冲突约束，解决了使多轨场景下顺序优化无效的时间-空间依赖关系。

该模型明确捕捉了由全重叠约束跨轨道传播所引起的组合爆炸，这是多轨道布局特有的复杂性。

我们的两级元启发式框架将高层任务优先级排序与底层无冲突路由解耦。底层解码器明确考虑了配作过程中由重叠料堆引起的跨轨道约束，避免了因紧耦合而生成不可行解的陷阱，并相比于穷举联合优化降低了搜索复杂度。

我们开发了该算法的集中式与并行式两种实现方式。并行版本利用具有迁移机制的混合岛屿-单元模型，加速了收敛过程，在不牺牲解质量的前提下，实现了大规模场景中的显著加速。

本文的组织结构如下：第2节提出一种新型时间空间网络模型来描述所研究的无冲突路由问题。第3节基于两级元启发式框架，引入集中式与并行算法来求解混合整数规划问题。第4节通过大量实验评估并分析了所提方法的性能。最后，第5节总结研究并展望未来的研究方向。

## 2. 建模

本节定义了多堆取料机在多轨道干散货堆场中运行的无冲突路由问题，并引入了相应的时间空间网络模型，包括相关目标函数和约束条件。

### 2.1 问题描述

图1展示了一个典型的干散货进口码头，由堆场、装车区和卸船区组成。从船舶卸下的物料通过输送系统堆存为矩形料堆。当火车到达时，斗轮堆取料机从这些料堆中取料并将其运送至装车站。作为船舶与火车之间的缓冲环节，高效的堆场作业对于最小化船舶和火车的等待时间至关重要（van Vianen, 2015）。本研究关注多轨道堆场网络中多堆取料机协同无冲突路由问题。

堆场由平行堆位组成，堆位之间以轨道分隔，每条轨道上配有两台堆取料机，分别服务于相邻的堆位。由于纵向取料机制，堆取料机在作业时占据料堆的整个长度，为同轨道上的配对机器创建了动态排他区域。为避免过度保守的调度，我们根据料堆中点的相对位置，将空间干扰分为部分重叠和完全重叠两类。这一区分决定了相邻机器是仅受限制不能同时取料，还是被完全禁止穿越重叠区域，构成了我们数学模型的概念基础。

我们将此问题作为van Vianen（2015）滚动时域框架下的一个运营调度子问题来处理。给定一批火车请求的预堆料堆，我们确定专门清料阶段的任务分配、排序和无冲突路径，在此期间堆存作业暂停以消除跨干扰。这种解耦在实际进口干散货码头中是合理的，因为在共享堆位上堆存和取料通常在时间上是分离的，这使我们能够专注于核心协调挑战：在多轨道网络上协调堆取料机，既包括同轨道防撞，也包括对互相可访问料堆的跨轨道竞争。目标是最小化完工时间和总行驶时间的加权和。最小化工期可以加快火车周转，释放容量用于后续批次；而最小化行驶时间可以减少能耗和机械磨损，从而提升整体码头吞吐量。将模型扩展至堆取料联合操作留作未来工作。

重要假设如下：

- 每台堆取料机从其初始位置出发，完成后返回初始位置。
- 堆取料机在空闲（等待）期间停留在料堆中点或初始位置。
- 任意两个料堆之间的行驶时间假设为相同（单位时间间隔）。鉴于取料与行驶在时间尺度上的差异，以及可变行驶时间将为时间空间网络框架引入的巨大复杂度，此简化在建模精度与计算可行性之间取得平衡。
- 每个料堆分配给一台堆取料机（按照Angelelli等人（2016）的多次长行程切割模式），因为活跃设备占据整个料堆长度，阻止其他设备进入以避免碰撞。
- 每个料堆的取料过程不可抢占。

### 2.2 数学模型

时间空间网络模型有效地解决了制造、运输和物流领域多机器人系统中的复杂路由挑战（Murakami, 2020）。这些模型将碰撞和干扰避免约束与时间和空间定位约束相结合，确保多机器人的协调高效路径规划。

为将物理堆场环境映射为数学优化框架，我们将系统形式化为由有向图 $G=(V_1, E_1)$ 表示的时间空间网络。连续规划时域被均匀离散为 $T$ 个持续时间为 $\Delta t$ 的时间段，索引集 $H=\{0,1,\cdots,T\}$ 表示离散时间点，使得 $t \in H$ 对应物理时间 $t \cdot \Delta t$。在空间维度上，堆场被划分为有限个操作位置集合 $V_1 = V \cup \{h_k \mid k \in K\}$，其中 $V$ 表示目标料堆，$h_k$ 表示堆取料机 $k$ 的初始车场位置。

通过取空间节点与时间索引的笛卡尔积，我们定义网络的核心结构：节点 $(i, t) \in V_1 \times H$ 表示堆取料机在时刻 $t$ 处于位置 $i$ 的状态。弧集 $E_1$ 连接连续区间 $[t, t+1]$（$t \in H \setminus \{T\}$）上的时空节点，并结构性地分为两类。行驶弧 $((i,t) \to (j,t+1)$，$i \neq j$）建模物理位移，产生正的行驶时间和距离；而静止弧 $((i,t) \to (i,t+1)$，$i = j$）表示"不移动"转换，使堆取料机可以停留在同一节点以执行取料任务或空闲等待以避免碰撞，两者行驶代价均为零。

为系统地追踪每台堆取料机的动态状态，我们引入两类决策变量。路由变量 $x_{ijk}^t$ 定义时空轨迹，而操作状态变量 $(y_{ik}^{st}, y_{ik}^{et}, y_{ik}^{rt})$ 捕获斗轮堆取料机的独特机制。将空间位置与操作状态解耦对于制定精确、非保守的无冲突约束至关重要。详细定义见表2和表3。

**表2. 索引符号与输入参数**

| 符号 | 描述 |
|------|------|
| $T$ | 整个规划期间离散化时间段的数量 |
| $t$ | 时间索引 |
| $t'$ | 时间辅助索引 |
| $i, j$ | 料堆节点索引 |
| $H$ | 离散时间点索引集合，$H=\{0,1,\cdots,T\}$ |
| $K$ | 堆取料机集合 |
| $R$ | 轨道集合 |
| $V$ | 待取料料堆节点集合 |
| $V_1$ | 所有节点的集合（集合$V$与堆取料机初始位置集合的并集） |
| $E$ | 连接$V$中任意两个节点的弧集合 |
| $E_1$ | 连接$V_1$中任意两个节点的弧集合 |
| $w_1$ | 目标函数中完工时间的权重 |
| $w_2$ | 目标函数中堆取料机行驶时间的权重 |
| $h_k$ | 堆取料机$k$的初始位置节点 |
| $T_i$ | 取料堆料堆$i$所需的时间 |
| $z_{ik}$ | 料堆$i$与堆取料机$k$之间的位置关系。若堆取料机$k$位于料堆$i$相邻的轨道上，则$z_{ik}=1$；否则，$z_{ik}=0$ |
| $O_r$ | 轨道$r$两侧重叠料堆对的集合 |
| $F_r$ | 轨道$r$两侧完全重叠料堆对的集合，$F_r$是$O_r$的子集 |
| $P_r^R$ | 轨道$r$上堆取料机的相对位置关系集合，其中每个元素$(k_1, k_2)$表示堆取料机$k_1$位于堆取料机$k_2$的左侧 |
| $P_r^S$ | 轨道$r$两侧料堆节点的相对位置关系集合，其中每个元素$(i, j)$表示节点$i$位于节点$j$的左侧 |

**表3. 决策变量**

| 符号 | 描述 |
|------|------|
| $x_{ijk}^t$ | 0-1变量，$x_{ijk}^t=1$表示堆取料机$k$在$t$到$t+1$期间沿弧$(i,j)$移动（定义域$t \in H\setminus\{T\}$），否则为0 |
| $y_{ik}^{st}$ | 0-1变量，$y_{ik}^{st}=1$表示堆取料机$k$在$t$时刻开始取料堆$i$（其中$t \in H\setminus\{T\}$），否则为0 |
| $y_{ik}^{et}$ | 0-1变量，$y_{ik}^{et}=1$表示堆取料机$k$在$t$时刻结束取料堆$i$（其中$t \in H\setminus\{0\}$），否则为0 |
| $y_{ik}^t$ | 0-1变量，$y_{ik}^t=1$表示堆取料机$k$在$t$到$t+1$时间区间内正在取料堆$i$（其中$t \in H\setminus\{T\}$），否则为0 |
| $t_s^i$ | 整数变量，取料堆$i$的开始时间索引 |
| $t_e^i$ | 整数变量，取料堆$i$的结束时间索引 |
| $T_{max}$ | 整数变量，所有操作的完工时间（最大时间索引） |

目标是最小化工期（$T_{max}$）和总行驶时间。基于定义的弧类型，行驶时间指标仅统计物理行驶弧（$i \neq j$）上的持续时间，排除静止弧。多目标时间空间网络模型如下：

$$\min \, J = w_1 \cdot T_{max} + w_2 \cdot \sum_{(i,j) \in E_1, \, i \neq j} \sum_{k \in K} \sum_{t=0}^{T-1} x_{ijk}^t \tag{1}$$

将总行驶时间作为次级目标纳入，弥补了纯粹以完工时间为中心方法的局限性。虽然最小化$T_{max}$优化了瓶颈操作，但它对于完工时间相同的调度方案区分度有限，对非瓶颈资源的惩罚力度较弱。具体而言，短视地关注$T_{max}$可能允许非关键堆取料机在不受惩罚的情况下采取冗余绕行。因此，行驶时间分量作为路由效率准则，减少不必要的移动，从而降低整个车队的能耗和机械磨损。

相关约束条件如下：

**第一组：空间约束**

$$\sum_{j \in V_1} x_{h_k j k}^0 = 1, \quad \forall k \in K \tag{2}$$

$$\sum_{i \in V_1} x_{i h_k k}^{T-1} = 1, \quad \forall k \in K \tag{3}$$

$$\sum_{i \in V_1} x_{ijk}^{t-1} = \sum_{l \in V_1} x_{jlk}^t, \quad \forall j \in V_1, k \in K, t \in H\setminus\{0,T\} \tag{4}$$

$$\sum_{(i,j) \in E_1} x_{ijk}^t = 1, \quad \forall k \in K, t \in H\setminus\{T\} \tag{5}$$

**第二组：时间约束**

$$\sum_{i \in V} \sum_{k \in K} y_{ik}^{s0} = 0 \tag{6}$$

$$y_{ik}^{rt'} = t' \sum_{t=0}^{t'} y_{ik}^{st} \times \sum_{t=t'+1}^{T} y_{ik}^{et}, \quad \forall i \in V, k \in K, t' \in H\setminus\{0,T\} \tag{7}$$

$$\sum_{i \in V} y_{ik}^t \leq 1, \quad \forall k \in K, t \in H\setminus\{T\} \tag{8}$$

$$\sum_{i \in V_1} x_{ijk}^{t-1} \geq y_{jk}^{st}, \quad \forall j \in V, k \in K, t \in H\setminus\{0,T\} \tag{9}$$

$$t_s^i = \sum_{k \in K} \sum_{t=0}^{T-1} t \cdot y_{ik}^{st}, \quad \forall i \in V \tag{10}$$

$$t_e^i = \sum_{k \in K} \sum_{t=1}^{T} t \cdot y_{ik}^{et}, \quad \forall i \in V \tag{11}$$

$$T_i = \sum_{k \in K} \sum_{t=0}^{T-1} y_{ik}^t, \quad \forall i \in V \tag{12}$$

$$x_{iik}^t \geq y_{ik}^t, \quad \forall i \in V, k \in K, t \in H\setminus\{T\} \tag{13}$$

$$T_{max} \geq t_e^i, \quad \forall i \in V \tag{14}$$

**第三组：无冲突约束**

$$\sum_{i \in V_1} x_{nik_1}^t + \sum_{j \in V_1} x_{mj k_2}^t \leq 1, \quad \forall r \in R, (m,n) \in P_r^S, (k_1,k_2) \in P_r^R, t \in H\setminus\{T\} \tag{15}$$

$$y_{ik_1}^t + y_{jk_2}^t \leq 1, \quad \forall r \in R, (i,j) \in O_r, (k_1,k_2) \in P_r^R, t \in H\setminus\{T\} \tag{16}$$

$$y_{i_1 k_1}^t + \sum_{j \in V_1} x_{i_2 j k_2}^t \leq 1, \quad \forall r \in R, (i_1,i_2) \in F_r, (k_1,k_2) \in P_r^R, t \in H\setminus\{T\} \tag{17}$$

$$y_{i_1 k_2}^t + \sum_{j \in V_1} x_{i_2 j k_1}^t \leq 1, \quad \forall r \in R, (i_1,i_2) \in F_r, (k_1,k_2) \in P_r^R, t \in H\setminus\{T\} \tag{18}$$

**第四组：分配约束**

$$\sum_{k \in K} \sum_{t=0}^{T-1} y_{ik}^{st} = 1, \quad \forall i \in V \tag{19}$$

$$\sum_{t=0}^{T-1} y_{ik}^{st} = \sum_{t=1}^{T} y_{ik}^{et}, \quad \forall i \in V, k \in K \tag{20}$$

$$\sum_{t=0}^{T-1} y_{ik}^{st} \leq z_{ik}, \quad \forall i \in V, k \in K \tag{21}$$

如在式(1)中定义，目标函数旨在最小化工期与堆取料机总行驶时间的加权聚合。

**第一组**中：约束(2)和(3)确保所有堆取料机在$t=0$时从各自初始位置出发，并在完成所有任务后返回初始位置。约束(4)和(5)提供时间空间网络模型中的流平衡条件。约束(4)规定如果堆取料机$k$在$t$时刻到达节点$j$，则必须在$t+1$时刻离开节点$j$。约束(5)表示特定堆取料机在$t$到$t+1$时间区间内沿弧$(i,j)$移动。若堆取料机$k$在$t$到$t+1$之间停留在节点$i$，则表示为沿弧$(i,i)$移动。

**第二组**中：约束(6)确保在$t=0$时没有料堆开始取料。约束(7)定义了决策变量$y_{ik}^{st}$、$y_{ik}^{et}$和$y_{ik}^{rt}$之间的关系，注意该约束为非线性约束。约束(8)保证每台堆取料机在任一时刻最多处理一个料堆。约束(9)防止堆取料机$k$在未到达节点$i$之前就开始取料堆$i$。约束(10)和(11)控制料堆$i$取料的开始和完成时间。约束(12)将取料堆$i$所需的时间（记为$T_i$）与变量$y_{ik}^t$关联起来。约束(13)施加非抢占条件，确保堆取料机$k$在取料过程完成之前不能离开料堆$i$。约束(14)将$T_{max}$限制为不小于任何取料任务$i$的结束时间，有效地以线性形式捕捉了调度的工期。

**第三组**中，安全约束旨在执行碰撞避免，同时保持配对堆取料机的并行行驶能力——这是高效共享轨道堆场作业的关键需求。约束(15)施加轨道不交叉规则，维持每对堆取料机$(k_1,k_2) \in P_r^R$沿堆场轨道的指定纵向顺序。约束(16)–(18)进一步细化长行程取料任务的碰撞避免逻辑。为避免牺牲并行效率的过度保守调度，对配对$(k_1,k_2) \in P_r^R$的空间干扰由重叠集$O_r$及其完全重叠子集$F_r \subseteq O_r$（见图2）进行刻画，以区分不同层级的时空限制。

对于$(i,j) \in O_r \setminus F_r$，对应于图2(a)所示的部分重叠情况，$i$的中点位于$j$的纵向取料跨度之外，允许$k_1$在$k_2$取料堆$j$期间穿越$i$，但禁止同时取料——由约束(16)通过禁止$y_{ik_1}^t$和$y_{jk_2}^t$同时激活来执行，对路由变量$x$无限制。对于$(i,j) \in F_r$，对应于图2(b)所示的完全重叠情况，$i$的中点落入$j$的跨度内，完全阻断通行；约束(17)-(18)通过强制$k_2$操作期间$k_1$穿越$i$中点时$x=0$来执行此限制。此设计仅对部分重叠限制$y_r$，对完全重叠增加$x$约束，消除了统一禁行规则的过度保守性。

**第四组**中，约束(19)确保每个料堆只能由一台堆取料机处理。约束(20)强制开始取料堆$i$的堆取料机$k$必须与完成取料堆$i$的堆取料机相同。约束(21)强制堆取料机$k$只能取位于其行驶轨道两侧的料堆。

注意约束(7)为非线性约束，可由以下三个线性方程替代：

$$y_{ik}^{rt'} \leq t' \sum_{t=0}^{t'} y_{ik}^{st}, \quad \forall i \in V, k \in K, t' \in H\setminus\{T\} \tag{22}$$

$$y_{ik}^{rt'} \leq \sum_{t=t'+1}^{T} y_{ik}^{et}, \quad \forall i \in V, k \in K, t' \in H\setminus\{T\} \tag{23}$$

$$t' \sum_{t=0}^{t'} y_{ik}^{st} + \sum_{t=t'+1}^{T} y_{ik}^{et} - y_{ik}^{rt'} \leq 1, \quad \forall i \in V, k \in K, t' \in H\setminus\{T\} \tag{24}$$

约束(22)–(24)通过McCormick包络（McCormick, 1976）提供了式(7)的精确二值线性化，对整数解无最优性损失。然而，这些包络产生的连续松弛解非常宽松，严重限制了分支定界算法的剪枝能力。因此，商业求解器（如Gurobi）无法在标准3600秒时间限制内证明即使是中等规模实例的最优性。

在将约束(7)线性化之后，整体路径规划问题可以表述如下：(??) min ?? s.t. (2)–(6), (8)–(21), (22)–(24)。

**注记1** 问题P是强NP-hard问题，因为它推广了共享轨道上的双取料机调度问题，该问题已被Angelelli等人(2016)证明是NP-hard的。为说明这一点，考虑一个受限实例，其中一条轨道服务于两个相对堆料垫，且所有堆料对两台取料机均可访问(??????=1, ???,??)，目标函数简化为完成时间最小化(??1=1, ??2=0)。在这些条件下，P简化为Angelelli等人(2016)中的精确设置。P的强NP-hard性质意味着为实际规模实例计算精确解是不可行的，这也促使我们在第3.3节中采用元启发式框架。

**求解方法** 如第2节所示，无冲突路径规划问题是强NP-hard问题。精确MILP面临时间索引变量的组合爆炸和弱的LP松弛，使得精确求解不可行。因此，我们开发了一种定制的双层元启发式算法，将任务排序与碰撞避免解耦，大幅缩减搜索空间。我们实现了集中式和并行两种变体；本节其余部分将详细介绍算法原理、层次结构和并行化策略，以实现更快的计算。

**3.1 总体描述**

为应对任务分配与无冲突调度集成问题的计算挑战，我们提出了一种层次化双层元启发式方法。在上层，任务优先级排序作为编码机制，隐式地表示潜在解。下层作为解码器，分配任务并构建无冲突路径。这些构建的路径构成了适应度评估的基础，其中计算的目标函数值作为反馈，引导上层搜索趋向运营效率。关键在于，这种双层框架将任务排序与详细的任务分配和路径生成解耦，从而降低搜索空间复杂度，显著提高高质量解的生成效率。

基于此框架，我们开发了集中式和并行两种实现方式。并行版本采用岛屿模型（图3），将全局种群划分为独立进化的子种群，部署在分布式计算资源上。这些岛屿按照预定规则定期迁移个体，利用分布式处理增强全局搜索能力和可扩展性。

下载：下载高分辨率图片(262KB) 下载：下载全尺寸图片 图3. 并行化双层元启发式流程图。

**3.2 上层**

在 proposed框架的上层，任务优先级排序由任务集V的一个排列π表示，其中每个任务的位置决定其在解码过程中的优先级。这种表示与基于染色体的搜索结构天然兼容，因为每个染色体定义一个完整的优先级序列，可在下层解码为任务分配和无冲突路径。因此，采用定制遗传算法(GA)作为上层优化器。选择GA是因为它提供了基于排列的排序问题的直接编码(Gon?alves等人, 2005)，并维护一组候选优先级序列，这些序列可被下层解码器独立评估。与模拟退火和变邻域搜索等单解元启发式相比，GA为 proposed解码结构和并行评估策略提供了更直接的接口。

本研究采用定制GA优化任务排序π。作为一种受自然选择启发的随机搜索技术，GA尽管算法简单，但仍能有效在可行解空间内维持搜索多样性(Tang等人, 2021)。此外，GA在解决类似的路径规划问题(包括多旅行商问题)中表现出高效性。值得注意的是，其基于种群的性质使GA非常适合并行化，能够同时处理多个候选子种群(Harada和Alba, 2020)。

迭代优化由一组解染色体的持续进化驱动。在每一代中，选择、交叉、变异和精英操作被应用于引导搜索趋向收敛。每个个体的适应度由下层反馈确定，确保进化趋向高质量解。选择识别有前途的个体以传播有效的排序特征，精英策略保留最优解以维持稳定性并加速收敛。

为产生具有改善特性的后代，采用顺序交叉(OX)算子。该方法适用于旅行商问题等序列依赖问题，因为它保留了任务的相对顺序——这是维持有前途路径结构的关键因素(Cergibozan和Tasan, 2022; ?lhan, 2021)。辅以OX，随机交换变异策略对序列引入微小随机调整，帮助避免早熟收敛，并实现局部搜索以获取更好的路径选择。

**3.3 下层**

基于上层提供的任务优先级排序，详细的无冲突任务分配和无冲突路径在下层通过算法1和算法2确定。算法1按照任务优先级，依次将机器分配给任务，确定取料时间，并为机器生成无冲突节点路径。其策略综合考虑了碰撞避免、干扰解决和机器负载均衡。在此过程中，无冲突节点路径的生成与任务分配同步，使路径规划能够基于任务的具体位置和加工时间进行。这种集成时空信息的实时路径生成，显著简化了任务分配过程中的干扰解决。尽管算法1为取料机规划任务节点路径，但它并未完全详细规划取料机在节点之间的调整路径。因此，将其描述为生成无冲突节点路径。随后，算法2细化节点间行驶路径，以产生最终的无冲突路径。通过检测行驶过程中的潜在碰撞或干扰并调整不必要的移动，该算法有效防止了节点和路径上的安全违规，显著提高了路径规划的效率和安全性。

下载：下载高分辨率图片(188KB) 下载：下载全尺寸图片 算法1. 基于优先级的无冲突任务分配。
下载：下载高分分辨图片(220KB) 下载：下载全尺寸图片 算法2. 路径优化。

**3.3.1 基于优先级的无冲突任务分配**

算法1是一种构造性启发式方法，将高层任务序列π映射为机器分配和无冲突时空轨迹。输入包括任务持续时间????、取料机初始位置???以及序列π。关键空间集合控制路径约束：????(i的合格取料机)、????/????(部分/完全重叠的堆料)、????(共享轨道伙伴)和????(空间前驱)。输出为Route，指定每台取料机的节点序列和操作状态。

算法按π顺序处理任务。对于任务i，评估合格取料机??∈????。可行性检查排除导致碰撞或违反由????、????和????施加安全约束的时间区间。从剩余可行窗口中，任务分配给产生最早完成时间(ECT)的取料机。

采用此基于ECT的规则是因为它与解码器的时空结构一致。给定每个堆料的固定加工时间，完成时间综合反映了取料机的就绪时间、序列依赖的行驶时间和任务加工时间。基于完成时间的分配规则在调度研究中被广泛用于评估机器分配和构建可行调度方案(Gacias等人, 2010)。在此多取料机设置中，ECT规则优于更简单的替代方案，因为它同时考虑了时间和空间因素。最小行驶时间规则可能忽略工作负载，最早就绪时间规则可能忽略空间距离，而轮询和随机规则两者均未使用。因此，在固定任务序列下，ECT提供了合适的解码器级准则，用于减少完成时间和不必要的移动。

一旦任务分配的机器和时间被确定，系统状态和机器路径立即更新：时间区间被预留，相应轨迹被添加到路径中。在调度后续低优先级任务时，算法引用这些更新的路径来检测和解决时空冲突。这种顺序检查-更新机制确保在整个规划期内生成全局一致的路径，满足所有安全约束。

**3.3.2 路径改进**

算法2旨在优化算法1生成的无冲突节点路径，减少不必要的行驶时间。它缓解了算法1中空闲时间策略导致的额外移动。在算法1中，重点是任务调度和取料机在堆料取料期间的位置。同时，取料机在空闲期间停留在初始节点，可能导致额外行驶。为执行此优化，算法2利用算法1的初始解Route作为基准，由系统参数????(轨道)、????(堆料)和初始位置???支持。过程进一步受空间集合????和????约束，并以从前一阶段继承的完成时间戳????为界限，最终产生精化的轨迹集Routeopt。

具体而言，对于取料机k，其空闲时间t期间的改进位置??????取决于其前一位置???????1和下一取料操作位置，定义为??????′。对??????的调整通过评估停留在???????1或??????′的可行性来实现，同时确保满足约束(15)、(17)和(18)。算法2中的路径优化按轨道顺序进行，同时考虑不同轨道上取料机行驶的独立性以及同一轨道上取料机之间可能发生的物理碰撞。算法旨在最小化取料机不执行任务时的不必要移动，优化总行驶时间并减少能耗。

**3.4 并行化**

鉴于优化问题的庞大规模和高维度，算法的计算速度面临重大挑战。为解决此问题，本文对算法进行并行化并部署在多核CPU上以提升性能。参照Cheng和Gen(2019)的工作，采用混合方法，将岛屿模型和细胞模型集成，以并行化proposed算法上层的标准GA。通过将每个核心作为自主单元进行并发适应度评估，该架构将细粒度的多样性保持与粗粒度的迁移相结合，显著提高效率并加速解探索。

如图4所示，岛屿模型将种群划分为具有地理结构的独立子种群，每个子种群被视为一个"岛屿"。这些子种群在不同CPU核心上独立进化，并通过迁移定期交换信息。控制此模型的关键因素包括岛屿数量、迁移拓扑、间隔以及选择/替换策略(Izzo等人, 2012)。相比之下，细胞模型有一个单一种群，个体在不同核心上独立进化，通过网络结构连接。个体只能在其邻域内竞争和交配，由于邻域重叠，优良个体逐渐扩散到整个种群中。

下载：下载高分辨率图片(269KB) 下载：下载全尺寸图片 图4. 多CPU核心混合模型。

如图4所示，混合模型集成岛屿模型和细胞模型，将每个CPU核心视为一个岛屿，内部运行细胞模型，采用2D环形迁移拓扑进行核心通信。此模型在不同岛屿间维持遗传多样性，并在子种群内增强局部搜索。它比纯岛屿模型更有效地利用邻域结构，比纯细胞模型更好地保持多样性，同时减少通信开销。通过将并行GA部署在多核CPU上，我们解决更复杂的实际问题。

此混合模型非常适合并行计算，允许多个"岛屿"在独立CPU核心上运行，从而充分利用CPU的计算能力。基于此结构，我们将原始集中式双层元启发式算法并行化为并行版本，如图3所示。初始时，种群随机分布在n个"岛屿"(即CPU核心)上，每个"岛屿"运行一个细胞模型。每个"岛屿"按照集中式双层元启发式算法的过程独立进化。在此过程中，每个个体只能与其八个邻近个体交配，保持种群多样性并有效防止早熟收敛。

经过预定代数且满足迁移条件后，每个岛屿选择一组适应度最高的精英个体迁移到其他岛屿。到达后，这些高质量解替换目标子种群中适应度最低的成员。此迁移机制将优越遗传物质引入新岛屿，促进有效构建模块的传播。由此产生的交互通过允许有前途的个体与不同遗传背景重组来增强全局搜索，从而提高产生更优后代的概率。

**4 结果讨论**

本节评估和讨论所提出的双层元启发式（基于TSN模型）的计算结果。数值案例研究评估了其性能。首先，描述实验设置。其次，对小规模和大规模案例的结果进行比较和分析，将集中式双层元启发式算法与其他方法进行比较。最后，对两种规模的集中式和并行算法结果进行比较。

**4.1**

# 实验设置

本节介绍了用于评估所提方法有效性的实验设计和案例实例。实验包括一组小规模实例（轨道线数量 $L$ 设置为 2、3、4，每个堆场的堆料数量 $S$ 设置为 3、4、5、6）和大规模实例（$L$ 设置为 3、4、5、6，$S$ 设置为 9、12、15）。在后续实验中，字母 $L$ 和 $S$ 的组合表示特定的测试实例，字母 $I$ 表示实例索引。每个实例测试 10 次，以确保进行全面的比较。

所有参数设置均与文献中报道的堆料取料机调度实际配置保持一致（Hu 和 Yao, 2012; Tang 等, 2016; van Vianen 等, 2015）。在时间维度上，时间单位 $\Delta t$ 设置为 15 分钟，遵循 van Vianen 等（2015）的建议，以在操作现实性和计算可行性之间取得平衡。在空间维度上，每个堆场均匀离散化为长度为 $\Delta s = 5$ m 的槽位。每个堆料的长度在 $[6\Delta s, 15\Delta s]$ 范围内随机生成，平均为 $10\Delta s$，这与 Hu 和 Yao（2012）中观察到的上海港堆料尺寸一致，其中堆料长度各异以满足不同客户需求的差异性。为防止物料混合，相邻堆料之间保留 0-2 个槽位的间隙，以便进行紧凑的取料操作。取料机在任意两个堆料之间的行驶时间假设为常数 $\Delta t$，使得堆料间行驶时间与平均取料时间之比为 1:10。

最大完工时间和总行驶时间是路径问题研究中的重要指标。最小化最大完工时间可以最大化终端的处理能力，从而提高其收入；而最小化总行驶时间则可以减少取料机的运营成本。因此，需要同时最小化最大完工时间和总行驶时间。然而，由于最大完工时间是更为关键的优化目标，应赋予其更高的权重因子。为了确保对最大完工时间的显著优先级，权重 $w_1$ 和 $w_2$ 分别设置为 0.99 和 0.01（Xin 等, 2024a）。该配置在关注最大化完工时间优化的同时，仍然考虑了总行驶时间的重要性。

为了进行公平比较，所有启发式方法共享相同的调度解码器、碰撞检查规则和适应度函数。所提出的 CTLM 与最先进的精确求解器和三种代表性的（元）启发式方法进行了比较，总结如下：

- **Gurobi**：采用该最先进的求解器求解由所开发的时间空间网络模型推导出的混合整数规划问题 P。
- **SP**：在此方法中，所有堆料按地理顺序进行调度。它赋予堆料两种优先级：一种基于其序列位置，另一种基于堆场编号，优先处理编号较小的堆场上的堆料。
- **BSEM（双序列编码元启发式）**：由 Ding 和 Gu（2020）提出，该方法采用双染色体编码来联合表示任务优先级和机器分配。任务按顺序解码到其分配机器上的最早可行时间窗口中，同时遵守同轨不交叉约束。
- **TSM（两阶段元启发式）**：遵循 Xin 等（2024b），采用两阶段分层分解：第一阶段贪心地分配任务以最小化机器工作负荷不均衡；第二阶段应用遗传算法（GA）优化预分配机器的任务序列，并在解码过程中解决碰撞问题。

所提出的数学模型使用 Python 实现，并采用 Gurobi 11.0.1 求解器求解。所有实验在一台配备 Intel Core i7-9700（3.0 GHz）CPU 和 16 GB 内存的 Windows 10 工作站上进行，Gurobi 求解器被配置为在 3600 秒后终止。性能基于两项关键绩效指标（KPI）进行评估：目标函数值和计算时间（CT）。

## 4.2 参数配置

### 4.2.1 元启发式设置

对于所考虑的元启发式，参数需要仔细选择。在本部分，我们设定了适用于时间空间网络模型的遗传算法重要参数。

为了将核心算法编码效果与实现偏差隔离开来，所有随机方法均使用严格控制的进化预算。每种启发式算法在每个实例上运行 10 次独立重复实验。所有方法共用统一的遗传参数：种群规模 $N_p$、最大迭代次数 $\text{iter}_{\max}$、交叉概率 $P_c$ 和变异概率 $P_m$。

在基于元启发式的方法中，参数值的变动会显著影响算法性能。在提出的双层元启发式框架内，显著影响性能的关键参数包括种群规模 $N_p$、最大迭代次数 $\text{iter}_{\max}$、交叉概率 $P_c$ 和变异概率 $P_m$。遵循 Sun 等（2023）的指导原则，我们设计了 $L_9$ 正交实验以确定最优参数配置，如表 4 所示。该实验涵盖四个参数，每个参数评估三个潜在值，构成四因素三水平正交设计。

**表 4. $L_9$ 正交实验：实验编号与参数配置**

| 实验编号 | $P_c$ | $P_m$ | $N_p$ | $\text{iter}_{\max}$ |
|:---:|:---:|:---:|:---:|:---:|
| 1 | 0.7 | 0.05 | 100 | 50 |
| 2 | 0.7 | 0.1 | 400 | 100 |
| 3 | 0.7 | 0.2 | 200 | 150 |
| 4 | 0.8 | 0.05 | 400 | 150 |
| 5 | 0.8 | 0.1 | 200 | 50 |
| 6 | 0.8 | 0.2 | 100 | 100 |
| 7 | 0.9 | 0.05 | 200 | 100 |
| 8 | 0.9 | 0.1 | 100 | 150 |
| 9 | 0.9 | 0.2 | 400 | 50 |

每个测试组包含五个缩放的测试用例。性能指标——目标函数值（Obj）和计算时间（CT）——取十次独立运行的平均值。为实现公平比较，采用 Min-Max 归一化将两者映射到 $[0,1]$ 区间（值越高越好），分别记为 $\text{Obj}_{\text{norm}}$ 和 $\text{CT}_{\text{norm}}$。计算加权总和 $\text{WS} = 0.5 \cdot \text{Obj}_{\text{norm}} + 0.5 \cdot \text{CT}_{\text{norm}}$，然后将所有用例的 WS 汇总为 $\text{Sum} = \sum \text{WS}$；Sum 最高的配置为最优。结果见表 5。

**表 5. $L_9$ 正交实验的归一化结果与加权总和**

| 实验编号 | L3S9 | | | L3S15 | | | L4S12 | | | L5S9 | | | L6S15 | | | Sum |
|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|
| | Obj | CT | WS | Obj | CT | WS | Obj | CT | WS | Obj | CT | WS | Obj | CT | WS | |
| 1 | 0.00 | 1.00 | 0.50 | 0.00 | 1.00 | 0.50 | 0.00 | 1.00 | 0.50 | 0.00 | 1.00 | 0.50 | 0.00 | 1.00 | 0.50 | 2.52 |
| 2 | 1.00 | 0.36 | 0.68 | 0.84 | 0.36 | 0.60 | 0.74 | 0.35 | 0.55 | 0.92 | 0.36 | 0.64 | 0.90 | 0.36 | 0.63 | 3.09 |
| 3 | 0.45 | 0.54 | 0.50 | 1.00 | 0.54 | 0.77 | 0.91 | 0.54 | 0.72 | 1.00 | 0.54 | 0.77 | 1.00 | 0.54 | 0.77 | 3.53 |
| 4 | 0.82 | 0.00 | 0.41 | 0.80 | 0.00 | 0.40 | 1.00 | 0.00 | 0.50 | 0.61 | 0.00 | 0.30 | 0.43 | 0.00 | 0.22 | 1.83 |
| 5 | 0.63 | 0.91 | 0.77 | 0.51 | 0.91 | 0.71 | 0.35 | 0.91 | 0.63 | 0.56 | 0.91 | 0.74 | 0.40 | 0.91 | 0.65 | 3.49 |
| 6 | 0.45 | 0.91 | 0.68 | 0.58 | 0.91 | 0.74 | 0.70 | 0.91 | 0.80 | 0.48 | 0.91 | 0.69 | 0.50 | 0.91 | 0.70 | **3.62** |
| 7 | 0.37 | 0.73 | 0.55 | 0.51 | 0.72 | 0.62 | 0.48 | 0.72 | 0.60 | 0.52 | 0.73 | 0.63 | 0.50 | 0.73 | 0.61 | 3.01 |
| 8 | 0.09 | 0.82 | 0.45 | 0.77 | 0.82 | 0.80 | 0.44 | 0.82 | 0.63 | 0.35 | 0.82 | 0.58 | 0.37 | 0.82 | 0.59 | 3.05 |
| 9 | 0.72 | 0.71 | 0.72 | 0.93 | 0.72 | 0.83 | 0.44 | 0.71 | 0.57 | 0.70 | 0.72 | 0.71 | 0.70 | 0.72 | 0.71 | 3.53 |

表 5 显示，第 6 组在解质量与计算成本之间取得了最佳平衡。因此，我们采用其参数配置：$P_c = 0.8$，$P_m = 0.2$，$N_p = 100$，$\text{iter}_{\max} = 100$，以确保在相同计算预算下实现公平的基准比较。所提出的 CTLM 始终优于 BSEM 和 TSM，且在大规模实例上表现出更优的稳定性。

### 4.2.2 权重参数敏感性分析

为证明所选权重设置的合理性，我们在实例 L4S12I3 上进行网格搜索，将 $(w_1, w_2)$ 从 $(1.0, 0.0)$ 变化至 $(0.0, 1.0)$。CTLM 对每种配置运行 10 次独立实验，结果见表 6。由于优化后的加权目标函数依赖于 $(w_1, w_2)$ 的取值。

**表 6. 不同权重组合下的解耦优化指标（案例：L4S12I3）**

| 权重 $(w_1, w_2)$ | 最大完工时间 $T_{\max}$ | | | 总行驶时间 | | | 平均 CT（s） |
|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|
| | 最优值 | 平均值 | 标准差 | 最优值 | 平均值 | 标准差 | |
| (1.0, 0.0) | 84 | 88.90 | 5.17 | 68 | 68.50 | 0.81 | 66.88 |
| (0.99, 0.01) | 86 | 86.80 | 0.98 | 68 | 68.00 | 0.00 | 66.73 |
| (0.90, 0.10) | 85 | 87.00 | 1.18 | 68 | 68.00 | 0.00 | 66.97 |
| (0.75, 0.25) | 85 | 87.80 | 2.89 | 68 | 68.10 | 0.30 | 67.41 |
| (0.50, 0.50) | 85 | 92.50 | 11.67 | 68 | 68.10 | 0.30 | 70.36 |
| (0.25, 0.75) | 86 | 98.90 | 13.13 | 68 | 69.10 | 1.30 | 68.65 |
| (0.0, 1.0) | 92 | 106.10 | 8.93 | 68 | 68.00 | 0.00 | 69.11 |

如表 6 所示，在所有测试配置中，$(0.99, 0.01)$ 提供了最均衡的综合性能。对于最大完工时间，纯粹的最大完工时间优化 $(1.0, 0.0)$ 达到了最优的单次运行值 84；然而，其平均最大完工时间达到 88.90，标准差为 5.17。相比之下，$(0.99, 0.01)$ 实现了最低的平均最大完工时间 86.80 和最小的标准差 0.98，表明具有明显更高的调度稳定性。对于总行驶时间，所有配置的最优观测值均为 68，且平均值仅在 68.00 至 69.10 之间略有差异。占主导地位的最大完工时间权重保持了时间的紧凑性，而较小的行驶时间权重则抑制了不必要的移动，进一步稳定了解的稳定性。当最大完工时间权重大幅降低时，如纯粹的行驶时间优化 $(0.0, 1.0)$ 所示，平均最大完工时间明显恶化至 106.10。

总体而言，$(0.99, 0.01)$ 的设置提供了稳健的权衡：它优先考虑了主要的工业目标（最小化最大完工时间），同时使用较小的行驶时间惩罚来抑制不必要的移动并增强调度稳定性。

## 4.3 实验结果

### 4.3.1 小规模案例

本小节提供了五种替代方法在小规模实例上计算性能的比较分析。这些小型实例验证了集中式双层元启发式（CTLM）方法能否匹配使用求解器 Gurobi 获得的优化解。比较结果详细列于表 7，并如图 5 所示。为便于理解，图 5 中 x 轴上的索引 1-36 依次对应表 7 中列出的实例（从上至下）。

**表 7. 小规模实例结果**

| 实例 | Gurobi | | SP | | BSEM | | TSM | | CTLM | |
|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|
| | Obj | CT | Obj | CT | Obj | CT | Obj | CT | Obj | CT |
| L2S3I1 | 29.83 | 247.00 | 29.83 ± 0 | 4.76 ± 0.07 | 29.83 ± 0 | 2.26 ± 0.03 | 38.74 ± 0 | 2.64 ± 0.01 | 29.83 ± 0 | 4.81 ± 0.02 |
| L2S3I2 | 28.84 | 126.39 | 28.84 ± 0 | 4.72 ± 0.03 | 29.24 ± 0.48 | 2.26 ± 0.05 | 40.72 ± 0 | 3.26 ± 0.04 | 28.84 ± 0 | 4.75 ± 0.04 |
| L2S3I3 | 28.84 | 103.50 | 31.81 ± 0 | 4.77 ± 0.02 | 28.84 ± 0 | 2.24 ± 0.02 | 45.67 ± 0 | 3.17 ± 0.03 | 28.84 ± 0 | 4.78 ± 0.01 |
| L2S4I1 | 34.81 | 3200.29 | 39.76 ± 0 | 6.89 ± 0.05 | 35.01 ± 0.59 | 3.13 ± 0.02 | 57.58 ± 0 | 5.42 ± 0.17 | 34.81 ± 0 | 6.85 ± 0.07 |
| L2S4I2 | 35.80 | 3600.00 | 41.74 ± 0 | 6.64 ± 0.04 | 36.79 ± 0.99 | 3.14 ± 0.01 | 49.66 ± 0 | 4.76 ± 0.06 | 35.80 ± 0 | 6.84 ± 0.05 |
| L2S4I3 | 34.81 | 3600.00 | 42.33 ± 0.79 | 6.97 ± 0.06 | 34.81 ± 0 | 3.12 ± 0.04 | 53.62 ± 0 | 4.23 ± 0.08 | 34.81 ± 0 | 6.94 ± 0.05 |
| L2S5I1 | 42.76 | 3600.00 | 50.68 ± 0 | 10.13 ± 0.11 | 43.75 ± 0.99 | 4.58 ± 0.05 | 62.56 ± 0 | 7.37 ± 0.11 | 42.76 ± 0 | 10.27 ± 0.10 |
| L2S5I2 | 44.74 | 3600.00 | 49.69 ± 0 | 10.21 ± 0.07 | 44.25 ± 0.80 | 4.57 ± 0.06 | 63.55 ± 0 | 6.99 ± 0.17 | 42.76 ± 0 | 10.13 ± 0.06 |
| L2S5I3 | 42.76 | 3600.00 | 50.68 ± 0 | 10.14 ± 0.11 | 43.85 ± 0.69 | 4.60 ± 0.04 | 65.53 ± 0 | 9.03 ± 0.08 | 41.97 ± 0.40 | 10.13 ± 0.07 |
| L2S6I1 | 126.94 | 3600.00 | 59.42 ± 1.07 | 12.82 ± 0.15 | 51.50 ± 1.07 | 5.80 ± 0.10 | 62.59 ± 0 | 7.81 ± 0.25 | 49.72 ± 0 | 12.61 ± 0.12 |
| L2S6I2 | — | — | 59.22 ± 1.27 | 12.97 ± 0.20 | 52.59 ± 1.50 | 5.84 ± 0.25 | 87.34 ± 0 | 12.09 ± 0.25 | 51.50 ± 0.40 | 12.63 ± 0.11 |
| L2S6I3 | — | — | 57.64 ± 2.83 | 13.12 ± 0.15 | 51.90 ± 0.97 | 5.82 ± 0.08 | 78.43 ± 0 | 11.23 ± 0.35 | 50.41 ± 0.45 | 12.66 ± 0.14 |
| L3S3I1 | 23.94 | 93.41 | 31.86 ± 0 | 5.95 ± 0.04 | 24.24 ± 0.63 | 2.54 ± 0.02 | 45.72 ± 0 | 4.89 ± 0.05 | 23.94 ± 0 | 5.73 ± 0.10 |
| L3S3I2 | 25.92 | 1349.48 | 34.81 ± 0 | 5.99 ± 0.02 | 28.29 ± 2.22 | 2.57 ± 0.02 | 29.88 ± 0 | 2.79 ± 0.02 | 25.92 ± 0 | 5.82 ± 0.07 |
| L3S3I3 | 23.94 | 100.43 | 27.90 ± 0 | 5.97 ± 0.04 | 25.52 ± 1.34 | 2.54 ± 0.01 | 32.85 ± 0 | 2.95 ± 0.02 | 23.94 ± 0 | 5.73 ± 0.06 |
| L3S4I1 | 30.91 | 3600.00 | 38.83 ± 0 | 9.98 ± 0.04 | 33.68 ± 2.20 | 4.29 ± 0.05 | 43.78 ± 0 | 6.07 ± 0.13 | 31.11 ± 0.40 | 9.82 ± 0.07 |
| L3S4I2 | 30.91 | 3600.00 | 36.85 ± 0 | 9.88 ± 0.06 | 33.58 ± 1.40 | 4.27 ± 0.08 | 46.75 ± 0 | 5.97 ± 0.05 | 30.91 ± 0 | 9.92 ± 0.09 |
| L3S4I3 | 32.89 | 3600.00 | 40.02 ± 0.59 | 9.95 ± 0.09 | 35.17 ± 0.45 | 4.38 ± 0.11 | 63.58 ± 0 | 10.78 ± 0.11 | 33.09 ± 0.59 | 9.83 ± 0.10 |
| L3S5I1 | 56.69 | 3600.00 | 47.29 ± 1.55 | 13.78 ± 0.12 | 41.44 ± 1.78 | 5.82 ± 0.13 | 65.60 ± 0 | 8.36 ± 0.12 | 38.77 ± 0.69 | 13.62 ± 0.14 |
| L3S5I2 | 49.76 | 3600.00 | 46.89 ± 1.21 | 13.58 ± 0.10 | 41.35 ± 1.11 | 5.93 ± 0.29 | 71.54 ± 0 | 11.91 ± 0.14 | 38.97 ± 0.93 | 13.62 ± 0.20 |
| L3S5I3 | — | — | 48.08 ± 0.77 | 13.68 ± 0.12 | 39.27 ± 1.48 | 5.82 ± 0.15 | 66.59 ± 0 | 11.59 ± 0.12 | 36.89 ± 0.77 | 13.64 ± 0.10 |
| L3S6I1 | 126.06 | 3600.00 | 58.81 ± 0.69 | 17.35 ± 0.16 | 49.60 ± 1.92 | 7.66 ± 0.67 | 63.66 ± 0 | 9.23 ± 0.24 | 46.83 ± 0.89 | 17.12 ± 0.12 |
| L3S6I2 | — | — | 60.29 ± 0.79 | 17.75 ± 0.25 | 49.11 ± 1.54 | 7.47 ± 0.23 | 80.49 ± 0 | 13.75 ± 0.25 | 45.84 ± 0.63 | 17.35 ± 0.11 |
| L3S6I3 | — | — | 57.72 ± 2.08 | 17.94 ± 0.22 | 48.31 ± 1.48 | 7.49 ± 0.27 | 77.52 ± 0 | 11.40 ± 0.10 | 46.43 ± 0.91 | 17.43 ± 0.22 |
| L4S3I1 | 21.81 | 1152.49 | 29.92 ± 0 | 7.82 ± 0.04 | 22.90 ± 0.30 | 3.22 ± 0.04 | 31.91 ± 0 | 4.12 ± 0.03 | 22.21 ± 0.40 | 7.54 ± 0.10 |
| L4S3I2 | 23.00 | 300.99 | 31.90 ± 0 | 7.72 ± 0.03 | 23.79 ± 0.86 | 3.20 ± 0.05 | 41.81 ± 0 | 6.13 ± 0.04 | 23.00 ± 0 | 7.55 ± 0.10 |
| L4S3I3 | 23.99 | 2171.96 | 29.92 ± 0 | 7.78 ± 0.08 | 25.67 ± 1.33 | 3.28 ± 0.08 | 34.88 ± 0 | 3.45 ± 0.01 | 23.99 ± 0 | 7.46 ± 0.06 |
| L4S4I1 | 31.96 | 3600.00 | 36.90 ± 0 | 11.81 ± 0.11 | 33.74 ± 1.31 | 4.90 ± 0.14 | 58.69 ± 0 | 9.75 ± 0.08 | 30.97 ± 0.44 | 11.51 ± 0.10 |
| L4S4I2 | 33.94 | 3600.00 | 37.39 ± 1.49 | 12.38 ± 0.13 | 34.43 ± 1.84 | 4.85 ± 0.12 | 57.70 ± 0 | 9.03 ± 0.09 | 31.56 ± 0.91 | 11.68 ± 0.12 |
| L4S4I3 | — | — | 41.86 ± 0 | 11.90 ± 0.15 | 34.43 ± 1.67 | 4.94 ± 0.13 | 42.85 ± 0 | 6.59 ± 0.05 | 31.46 ± 0.50 | 11.63 ± 0.08 |
| L4S5I1 | — | — | 47.45 ± 0.91 | 18.28 ± 0.33 | 40.13 ± 1.64 | 7.70 ± 0.46 | 57.75 ± 0 | 11.47 ± 0.25 | 36.96 ± 0 | 17.85 ± 0.12 |
| L4S5I2 | — | — | 48.64 ± 2.75 | 18.10 ± 0.17 | 41.41 ± 1.35 | 7.60 ± 0.38 | 57.75 ± 0 | 12.05 ± 0.23 | 38.35 ± 0.91 | 18.10 ± 0.12 |
| L4S5I3 | — | — | 47.85 ± 0 | 18.05 ± 0.12 | 40.23 ± 3.07 | 7.43 ± 0.25 | 48.84 ± 0 | 8.03 ± 0.05 | 37.06 ± 0.53 | 17.58 ± 0.12 |
| L4S6I1 | — | — | 60.97 ± 1.70 | 23.38 ± 0.31 | 50.18 ± 2.80 | 10.29 ± 0.68 | 57.80 ± 0 | 12.27 ± 0.66 | 46.51 ± 0.79 | 22.71 ± 0.15 |
| L4S6I2 | — | — | 56.41 ± 3.66 | 23.52 ± 0.27 | 48.40 ± 3.26 | 10.07 ± 1.10 | 66.71 ± 0 | 18.53 ± 0.54 | 43.94 ± 0.89 | 22.82 ± 0.15 |
| L4S6I3 | — | — | 60.47 ± 0.89 | 23.32 ± 0.22 | 48.79 ± 1.21 | 10.13 ± 0.56 | 82.55 ± 0 | 22.94 ± 0.44 | 45.92 ± 0.44 | 22.79 ± 0.17 |
| 平均值 | — | — | 44.46 ± 10.71 | 11.94 ± 5.37 | 38.22 ± 9 | 5.16 ± 2.29 | 56.48 ± 14.81 | 8.39 ± 4.45 | 36.30 ± 8.43 | 11.73 ± 5.22 |

*注："—" 表示 Gurobi 未在规定时间内求解该实例；"±" 表示均值 ± 标准差。*


表 7 总结了小规模实例集的平均目标函数值和平均计算运行时间。此外，表格底部包含所有小规模实例的总体平均目标值和计算时间。值得注意的是，Gurobi 现已在 3600 秒的时间限制内提供了 36 个实例中 23 个的结果。在这些案例中，在时间限制前终止的实例已求解至最优，而在 3600 秒时停止的实例表示在给定时间内获得的最佳可行解。其余未求解的实例在表中以"—"表示。由于 Gurobi 未能为所有实例提供完整结果，其平均值被排除在底部汇总之外。

表 7 中的比较结果表明，CTLM 优于其他四种方法。该算法在保持可接受的计算效率的同时，实现了最低的总体目标值。与 Gurobi 相比，CTLM 对于求解至最优的实例，获得了与已证明最优解相同或非常接近的目标值，对于求解器达到时间限制的实例，CTLM 的结果可与或优于 Gurobi 返回的最佳可行解。

图5比较了所有小规模实例的平均目标值及其标准差，表明CTLM在目标值方面展现出最佳精度和最高鲁棒性。此外，SP方法在目标值上的较差表现突显了解决来自重叠料堆的空间干扰问题的必要性。同样，TSM方法表现不佳且未能收敛至最优解，原因在于其任务分配过程中采用贪心分配策略，这表明在任务分配过程中需要考虑与机械运动和取料过程相关的碰撞问题。尽管CTLM在目标值上优于BSEM方法，但其计算时间超过了BSEM方法。该发现表明，采用单序列任务优先级编码提升了精度，但需要额外的任务分配时间，指出了潜在优化领域以缓解计算速度损失。

为将提出的CTLM与精确求解器对比并阐明精确求解器的局限性，表8针对前12个代表性小规模实例（按自然顺序排列）详细呈现了界限分析结果。在3600秒时间限制下，Gurobi成功求得前几个实例的已证明最优解，提出的CTLM完美匹配这些全局最优解（0.00%差距）。负的差距至上界值表明CTLM在3600秒时间限制内优于Gurobi的最佳解，例如实例L2S6I1的值达到-60.83%。

表8 前12个代表性实例的详细性能与界限分析

| 实例 | Gurobi | CTLM | 最优性差距 (%) | 上界 | 下界 | CT | 差距至上界 | 差距至下界 |
|------|--------|------|---------------|------|------|----|-----------|-----------|
| L2S3I1 | 29.83 | 29.83 | 247.00 | 29.83 | 4.81 | 0.00 | 0.00 | 0.00 |
| L2S3I2 | 28.84 | 28.84 | 126.39 | 28.84 | 4.75 | 0.00 | 0.00 | 0.00 |
| L2S3I3 | 28.84 | 28.84 | 103.50 | 28.84 | 4.78 | 0.00 | 0.00 | 0.00 |
| L2S4I1 | 34.81 | 34.81 | 3200.29 | 34.81 | 6.85 | 0.00 | 0.00 | 0.00 |
| L2S4I2 | 35.80 | 33.10 | 3600.00 | 35.80 | 6.84 | 0.00 | 8.16 | 8.16 |
| L2S4I3 | 34.81 | 32.19 | 3600.00 | 34.81 | 6.94 | 0.00 | 8.14 | 8.14 |
| L2S5I1 | 42.76 | 37.17 | 3600.00 | 42.76 | 10.27 | 0.00 | 15.04 | 15.04 |
| L2S5I2 | 44.74 | 38.84 | 3600.00 | 42.76 | 10.13 | -4.43 | 10.09 | 10.09 |
| L2S5I3 | 42.76 | 38.97 | 3600.00 | 41.97 | 10.13 | -1.85 | 7.70 | 7.70 |
| L2S6I1 | 126.94 | 45.95 | 3600.00 | 49.72 | 12.61 | -60.83 | 8.20 | 8.20 |
| L2S6I2 | - | 46.78 | 3600.00 | 51.50 | 12.63 | -10.09 | - | - |
| L2S6I3 | - | 45.70 | 3600.00 | 50.41 | 12.66 | -10.31 | - | - |

注：UB表示Gurobi可获得时的最佳可行解目标值，LB表示Gurobi终止时报告的最佳有效下界。差距至上界和差距至下界衡量CTLM相对于相应Gurobi界限的相对偏差。

最关键的是，对于时空约束密集的实例（例如L2S6I2和L2S6I3），精确求解器变得不可解，在时间限制内无法找到任何可行整数解。在这些情况下，理论上界在结构上停滞不前——这是问题强NP难性和由约束(7)线性化引起的弱连续松弛共同导致的后果。将CTLM与这些本质上松散的理论上界进行基准比较，产生了膨胀的最优性差距（例如10.09%-15.04%）。这证实了显著的差距至下界主要是混合整数线性规划弱根节点松弛的理论产物，而不是启发式次优性的指示，从而验证了CTLM的鲁棒性和实际应用必要性。

4.3.2 大规模实例

本小节继续比较大规模实例的实验结果。表9比较了大规模实例的平均目标值和计算时间，并在底部总结了总体平均结果。由于求解器Gurobi无法解决所有大规模实例，因此未将其结果包含在表中。图6比较了所有大规模实例的平均目标值和标准差。与小规模分析一致，图6的x轴索引按顺序对应表9中列出的实例（从上至下）。

表9 大规模实例结果

| 实例 | SP Obj | SP CT | BSEM Obj | BSEM CT | TSM Obj | TSM CT | CTLM Obj | CTLM CT |
|------|--------|-------|----------|---------|---------|--------|----------|---------|
| L3S9I1 | 90.02 ± 2.18 | 33.48 ± 0.34 | 72.10 ± 3.38 | 14.39 ± 0.55 | 101.40 ± 0 | 24.06 ± 1.55 | 67.64 ± 0.53 | 33.11 ± 0.26 |
| L3S9I2 | 85.96 ± 2.81 | 34.23 ± 0.86 | 71.80 ± 2.64 | 14.53 ± 1.22 | 101.40 ± 0 | 23.72 ± 1.24 | 67.54 ± 0.74 | 32.98 ± 0.26 |
| L3S9I3 | 94.17 ± 2.26 | 33.69 ± 0.55 | 75.86 ± 4.87 | 14.48 ± 0.67 | 86.55 ± 0 | 16.45 ± 0.47 | 71.01 ± 0.89 | 33.20 ± 0.39 |
| L3S12I1 | 124.09 ± 3.09 | 53.84 ± 0.69 | 98.55 ± 3.28 | 24.32 ± 2.17 | 118.06 ± 1.10 | 34.37 ± 2.10 | 90.04 ± 1.01 | 53.14 ± 0.27 |
| L3S12I2 | 123.99 ± 1.33 | 53.10 ± 0.59 | 102.71 ± 9.72 | 23.53 ± 1.28 | 124.60 ± 0.45 | 38.39 ± 2.36 | 91.22 ± 0.91 | 53.30 ± 0.27 |
| L3S12I3 | 119.74 ± 3.07 | 53.91 ± 0.53 | 99.54 ± 4.73 | 23.93 ± 2.25 | 135.18 ± 0 | 39.06 ± 2.19 | 91.12 ± 1.27 | 53.19 ± 0.26 |
| L3S15I1 | 159.36 ± 3.07 | 79.90 ± 0.84 | 133.63 ± 4.79 | 41.63 ± 3.37 | 149.78 ± 3.55 | 53.61 ± 4.02 | 115.80 ± 1.09 | 80.04 ± 0.70 |
| L3S15I2 | 151.83 ± 2.77 | 79.95 ± 1.08 | 126.10 ± 8.91 | 37.23 ± 2.51 | 139.26 ± 0 | 39.33 ± 2.37 | 112.13 ± 1.41 | 80.21 ± 0.77 |
| L3S15I3 | 155.60 ± 3.87 | 80.03 ± 0.75 | 126.50 ± 5.54 | 38.70 ± 2.66 | 155.10 ± 0 | 58.08 ± 3.46 | 111.94 ± 1.01 | 80.27 ± 0.44 |
| L4S9I1 | 89.33 ± 1.93 | 44.60 ± 0.88 | 71.22 ± 4.65 | 19.88 ± 3.35 | 125.27 ± 0 | 43.95 ± 1.43 | 64.68 ± 0.59 | 44.15 ± 0.69 |
| L4S9I2 | 88.64 ± 1.98 | 44.24 ± 0.65 | 72.21 ± 2.59 | 19.62 ± 1.97 | 75.28 ± 0.49 | 20.32 ± 0.60 | 65.38 ± 1.19 | 43.80 ± 0.45 |
| L4S9I3 | 91.21 ± 3.01 | 44.81 ± 0.62 | 75.28 ± 3.17 | 19.50 ± 1.13 | 81.81 ± 0.30 | 24.40 ± 0.95 | 64.78 ± 1.12 | 43.96 ± 0.57 |
| L4S12I1 | 120.97 ± 1.84 | 67.57 ± 0.89 | 98.90 ± 4.83 | 30.94 ± 1.75 | 125.43 ± 0.01 | 54.21 ± 4.34 | 85.92 ± 1.29 | 67.06 ± 0.80 |
| L4S12I2 | 126.01 ± 2.70 | 67.33 ± 0.39 | 100.58 ± 6.79 | 32.41 ± 4.97 | 138.29 ± 0 | 57.71 ± 3.32 | 88.10 ± 1.47 | 67.00 ± 0.48 |
| L4S12I3 | 125.72 ± 3.22 | 68.22 ± 0.79 | 99.69 ± 7.77 | 33.15 ± 4.91 | 109.69 ± 0.30 | 37.69 ± 2.01 | 87.11 ± 0.99 | 67.80 ± 0.57 |
| L4S15I1 | 152.50 ± 2.76 | 101.96 ± 1.04 | 125.89 ± 8.58 | 51.24 ± 6.59 | 125.77 ± 2.90 | 49.00 ± 2.90 | 105.57 ± 0.86 | 100.70 ± 0.89 |
| L4S15I2 | 154.08 ± 2.79 | 101.56 ± 0.92 | 125.49 ± 4.96 | 56.60 ± 9.95 | 154.29 ± 0.01 | 86.56 ± 5.03 | 105.97 ± 1.24 | 101.21 ± 0.71 |
| L4S15I3 | 157.25 ± 3.07 | 100.89 ± 1.01 | 123.50 ± 5.58 | 53.16 ± 8.89 | 178.05 ± 0.01 | 83.13 ± 2.93 | 108.54 ± 1.58 | 101.20 ± 1.35 |
| L5S9I1 | 91.13 ± 2.70 | 51.78 ± 0.49 | 74.50 ± 4.28 | 24.43 ± 4.42 | 94.69 ± 0 | 33.97 ± 0.62 | 62.91 ± 0.82 | 51.06 ± 0.31 |
| L5S9I2 | 92.22 ± 1.78 | 51.98 ± 0.52 | 75.88 ± 4.18 | 26.21 ± 8.02 | 105.59 ± 0.01 | 50.67 ± 2.49 | 63.90 ± 0.93 | 51.29 ± 0.43 |
| L5S9I3 | 93.50 ± 2.50 | 51.60 ± 0.40 | 75.29 ± 3.14 | 24.66 ± 3.39 | 93.81 ± 0.30 | 40.30 ± 2.57 | 64.89 ± 1.12 | 51.35 ± 0.60 |
| L5S12I1 | 127.54 ± 2.17 | 83.94 ± 1.07 | 98.05 ± 5.28 | 45.28 ± 11.02 | 114.67 ± 0 | 60.52 ± 4.44 | 85.76 ± 1.15 | 84.24 ± 0.60 |
| L5S12I2 | 124.87 ± 2.08 | 84.15 ± 1.09 | 101.52 ± 6.03 | 48.23 ± 12.32 | 104.97 ± 0.40 | 53.48 ± 2.80 | 82.99 ± 0.99 | 83.71 ± 0.46 |
| L5S12I3 | 124.97 ± 0.91 | 84.25 ± 0.95 | 103.10 ± 4.90 | 45.20 ± 10.40 | 110.22 ± 2.27 | 46.06 ± 3.91 | 85.56 ± 1.48 | 84.20 ± 0.53 |
| L5S15I1 | 158.71 ± 4.11 | 121.85 ± 1.92 | 131.22 ± 5.88 | 73.14 ± 12.53 | 159.41 ± 0.01 | 110.55 ± 6.60 | 105.74 ± 1.52 | 120.18 ± 0.65 |
| L5S15I2 | 153.36 ± 2.00 | 120.92 ± 1.27 | 126.95 ± 5.00 | 63.73 ± 10.24 | 183.18 ± 0.01 | 111.40 ± 4.97 | 105.54 ± 1.10 | 120.87 ± 0.68 |
| L5S15I3 | 155.24 ± 1.97 | 122.21 ± 1.03 | 127.95 ± 10.36 | 69.71 ± 15.79 | 133.77 ± 0.30 | 65.46 ± 1.28 | 104.46 ± 1.67 | 120.91 ± 0.76 |
| L6S9I1 | 89.45 ± 1.19 | 62.73 ± 0.70 | 77.98 ± 5.17 | 29.97 ± 2.68 | 100.74 ± 0 | 51.73 ± 3.42 | 63.22 ± 0.94 | 61.82 ± 0.38 |
| L6S9I2 | 91.53 ± 2.69 | 62.33 ± 0.61 | 75.89 ± 4.80 | 29.75 ± 4.16 | 99.75 ± 0.00 | 46.94 ± 1.34 | 63.22 ± 1.21 | 61.30 ± 0.40 |
| L6S9I3 | 95.30 ± 1.73 | 62.09 ± 0.62 | 77.98 ± 4.47 | 34.83 ± 6.10 | 94.80 ± 0 | 46.26 ± 1.97 | 64.01 ± 1.12 | 61.39 ± 0.75 |
| L6S12I1 | 123.92 ± 3.62 | 97.50 ± 0.91 | 105.62 ± 5.74 | 57.71 ± 6.56 | 133.63 ± 0.01 | 79.61 ± 4.52 | 84.91 ± 0.97 | 96.48 ± 0.84 |
| L6S12I2 | 125.90 ± 3.78 | 96.92 ± 1.54 | 104.14 ± 4.39 | 60.06 ± 11.87 | 136.59 ± 0 | 70.84 ± 1.08 | 84.42 ± 1.54 | 96.26 ± 0.90 |
| L6S12I3 | 122.44 ± 2.43 | 96.68 ± 1.15 | 102.95 ± 4.41 | 54.96 ± 6.15 | 131.65 ± 0 | 92.98 ± 2.70 | 84.32 ± 1.52 | 96.34 ± 0.78 |
| L6S15I1 | 157.00 ± 2.08 | 146.34 ± 1.43 | 127.73 ± 4.22 | 85.37 ± 16.89 | 140.78 ± 0.01 | 112.78 ± 11.53 | 103.14 ± 2.46 | 144.42 ± 0.98 |
| L6S15I2 | 157.69 ± 1.79 | 145.99 ± 1.98 | 127.72 ± 4.65 | 77.65 ± 7.27 | 140.77 ± 0.01 | 102.83 ± 6.43 | 104.13 ± 1.82 | 144.94 ± 0.98 |
| L6S15I3 | 155.81 ± 2.57 | 145.41 ± 1.84 | 130.10 ± 7.98 | 87.73 ± 15.35 | 161.58 ± 0.01 | 154.73 ± 9.21 | 105.62 ± 1.55 | 145.07 ± 0.81 |
| 平均 | 123.64 ± 26.65 | 78.67 ± 31.91 | 101.23 ± 22.48 | 41.33 ± 21.84 | 124.05 ± 26.26 | 58.75 ± 30.87 | 86.48 ± 17.51 | 78.12 ± 31.78 |

表9的比较结果显示，CTLM在大规模实例上始终优于其他四种方法，特别是在目标值方面，其表现显著优于其他方法。与在小规模实例上的结果相比，该算法在大规模实例上的目标值取得了更显著的优势。值得注意的是，尽管该算法在小规模实例上的目标值仅略优于BSEM，但在大规模实例上却对BSEM取得了显著优势。这表明，基于机器与任务间位置关系进行任务分配的双序列编码方法在大规模问题上难以维持精度，与基于优先级的无冲突任务分配相比。

图6进一步展示了大规模实例的平均目标值和标准差比较。图6表明，CTLM在目标值上显著优于其他三种方法，同时也展现出最高的鲁棒性。

4.3.3 集中式与并行算法性能

CTLM在处理大规模实例时平均计算时间超过一分钟。在第二部分，我们介绍了一种并行化CTLM以提高计算速度的方法，称为并行双层元启发式算法（PTLM）。在本小节中，我们比较了CTLM和PTLM的性能。

该实验使用了与之前实验相同的实例，将PTLM的迁移间隔设置为10代，迁移率为30%，岛屿数为8。PTLM的其他参数与CTLM一致。图7记录了平均目标值、平均计算时间及其标准差。

如图7所示，对于小规模实例，CTLM的平均目标值为36.3 ΔT，平均计算时间为11.73秒，而PTLM的平均目标值为36.4 ΔT，平均计算时间为4.23秒。对于大规模实例，CTLM在78.12秒内实现了86.48 ΔT的平均目标值，而PTLM在19.18秒内实现了88.11 ΔT的平均目标值。这些结果表明，对于小规模实例，PTLM仅牺牲0.27%的精度，但实现了2.77倍的平均加速比；对于大规模实例，PTLM以仅1.88%的精度降低为代价实现了4.07倍的平均加速比。值得注意的是，随着问题规模的增加，PTLM的计算速度优势变得更加明显。

4.3.4 总结

我们总结结果如下：
• 对于极小规模实例，CTLM产生与Gurobi求解器相同的最优解。对于其余实例，CTLM在解质量方面表现最强（即平均目标值始终优于其他方法），验证了我们提出的编码和解码方法的精度优势。
• PTLM在保持CTLM精度的同时，将计算速度提高了数倍。与其他方法相比，PTLM在精度和计算速度方面均显示出显著优势，表明设计并行算法结构可有效提高计算效率。

4.4 无冲突路径示例

在图8中，我们展示了使用提出的PTLM算法求解实例L4S6I1生成的甘特图。有关该实例的堆场布局、料堆编号以及取料机编号的详细信息，可通过以下仓库获取：https://github.com/jianbinxin/Instances-of-cooperative-reclaimers。在该实例中，8台取料机在4条轨道上协作取料30个料堆，取料机在取料或运动过程中均未发生碰撞或干扰。

5. 结论与未来研究

本文研究了具有多条并行轨道的干散货码头中多台取料机的新型无冲突路径策略，重点解决物料取料与料堆运动冲突。我们提出了TSN框架，在严格约束下整合任务分配、排序和路径规划，旨在最小化系统完工时间和总旅行时间。为解决该NP难混合整数线性规划问题带来的计算挑战，我们开发了一种双层元启发式框架，分别处理任务排序和路径生成，从而简化流程并加速搜索。基于该双层元启发式框架，实现了集中式（CTLM）和并行式（PTLM）解决方案。综合实验表明CTLM在解质量上优于Gurobi、SP、BSEM和TSM。CTLM在复杂干扰下有效协调取料机，基于优先级的无冲突分配提高了与贪心分配相比的精度。尽管参数取自历史数据Hu和Yao (2012); van Vianen (2015)，但实例仍为合成的，缺乏现实验证。PTLM在大规模实例上实现了4.07倍的加速，精度损失可忽略不计，使其具有实用性。

从实际应用的角度来看，本研究为干散货码头及类似大规模物流系统提供了三个关键见解：首先，同时考虑设备分配和路径规划有助于避免由时空冲突引起的重复操作调整；其次，利用并行机制充分利用计算资源可在保持解质量的同时显著减少调度时间；最后，优先考虑如不交叉和避碰等关键约束对于确保系统稳定性和安全性至关重要。

未来研究将在两个方向上扩展本工作。首先，为处理如不可预测船舶到达和优先级变化等动态中断，提出的框架将被嵌入滚动时间窗方案中，并采用事件驱动的响应策略进行实时重新调度。其次，将研究共享场地上的取料机与堆料机联合调度，这需要新的建模框架来捕捉额外的空间约束和动态交互。

针对这两个方向的研究为未来的探索提供了一个有前景的途径。
CRediT 作者贡献声明
Xin Jianbin：撰写——审阅与编辑、撰写——原稿、监督、方法、调查、资金获取。
Wu Hongcai：撰写——审阅与编辑、可视化、方法、调查。
Liu Chang：调查、撰写——原稿。
Andrea D'Ariano：监督、方法。
Liang Jing：监督、方法、概念构思。
Xin Jianbin|Wu Hongcai|Liu Chang|Andrea D'Ariano|Liang Jing