海上物流的配送瓶颈与无人机机遇

海上油气生产依赖于稳健的供应链体系，需要定期向大量分散的作业平台运送设备、备件、药品和文件等关键物资。目前这类配送任务由专业供应船执行，但面对数量众多的海上设施，仅依靠船舶完成所有小件紧急包裹的运输暴露出了明显的效率短板——船舶航行成本高、调配周期长，而许多包裹重量轻、体积小，使用大型船舶专程配送并不经济。

无人机技术的成熟为海上物流提供了新的可能。大疆FlyCart 30已具备30公斤载重能力，无人机在复杂海上环境中展现出较高灵活性，能够快速抵达船舶难以靠泊的偏远平台，显著降低燃料消耗和运营成本。然而，单一无人机的续航和载重限制了其对广泛分布平台的多点配送能力。为此，“船-无人机”协同配送模式应运而生：船舶作为移动母舰携带无人机出海，在接近平台时释放无人机执行投递，船舶则继续航行或原地等待回收。

本文是首篇将时间窗约束纳入船-无人机联合路由问题的研究，填补了从理论模型到实际运营之间的关键缺口。这一框架不仅适用于海上包裹配送，还可拓展至海上油田巡检、灾害应急响应和海洋科学监测等场景。

VURPTW：时间窗约束下的协同路由问题

研究定义了一个全新的问题——带时间窗的船-无人机路由问题（VURPTW）。场景中包含一艘母船和一架无人机，需要对N个海上平台执行包裹配送。每个平台j有确定的坐标位置和服务时间sj，并设有一个硬性时间窗[ej, lj]，配送必须在最早可服务时间ej之后开始，若在lj之后到达则产生延误惩罚。

VURPTW问题示意：母船从港口出发，无人机依次完成8个平台的配送任务。船舶在无人机执行任务期间可选择继续航行或原地等待。（取自Fig.1）

模型的核心决策包括三项：平台访问顺序的确定、无人机在每个配送任务中起飞点与降落点的坐标选择、以及无人机到达每个平台的时间。目标函数由五个成本组成：船舶等待成本、船舶航行成本（含等待期间的成本差异）、船舶在平台间的行驶成本、无人机运营成本，以及无人机因提前到达或延误产生的惩罚成本。

MISOCP建模与有效不等式强化

VURPTW被形式化为一个混合整数二阶锥规划（MISOCP）模型。建模的难点在于无人机可以在船舶航线的任意位置起降，起降点坐标是连续决策变量，导致约束中出现欧氏距离的二阶锥结构。基础模型M包含19组约束，涵盖船舶行驶时间限制、无人机飞行距离限制、续航约束、时间一致性约束以及等待/延误时间计算。

为提升模型求解效率，研究从两个方向对模型进行强化。首先，利用三角形边长关系理论重新设定大M约束中的M值，使得每个约束中M的取值尽可能小而仍保证不等式的正确性。例如，对于船舶在平台i和j之间的行驶距离约束，其M值被收紧为cij+2vur（其中vur为无人机最大航程半径），相比随意取大值显著压缩了搜索空间。

在此基础上，研究引入了一组基于三角形边长关系的有效不等式，限制船舶在任意两个连续访问平台之间的行驶距离下界。改进后的模型M'在17个小规模实例上的测试表明：平均上界从159,575降至146,007，最优性间隙从40.41%收窄至35.37%，计算时间也从1,962秒缩短至1,834秒，验证了有效不等式的实际价值。

有效不等式推导所依赖的三角形边长关系：船舶行驶距离、无人机飞行距离与平台间直线距离构成三角约束，分为港口-首平台、末平台-港口和连续两平台三种情形。（取自Fig.2）

ALNS算法：比率移除与并行搜索

由于VURPTW是NP难问题（可归约为旅行商问题），即使强化后的MISOCP模型也只能在合理时间内求解不超过12个平台的小规模实例。为此，研究设计了一套定制化的自适应大邻域搜索（ALNS）算法，通过四个关键设计实现了对实际规模问题的高效求解。

比率移除算子原理：节点2连接前后节点的距离之和远大于前后节点直连距离，造成空间冗余，算法优先移除以改善路径效率。（取自Fig.3）

ALNS的一个关键效率提升在于设计了SOCP成本的启发式近似评估方法。在破坏阶段评估节点移除后的成本时，不再反复求解耗时的二阶锥规划，而是用船舶直接访问平台的欧氏距离成本加上等待/延误惩罚来近似替代。这一近似在损失有限精度的前提下，大幅降低了破坏阶段的单次评估时间。

对比实验证实了比率移除算子的有效性。在小规模实例上，带比率移除的ALNS在平均解质量和计算时间上均优于不带该算子的基础ALNS：平均目标值从140,697降至140,230，平均计算时间从22.32秒降至17.34秒。

实验设计与模型对比验证

实验基于随机生成的52个实例进行，覆盖小规模（≤20个平台）、中等规模（21-35个平台）和大规模（36-100个平台）三个层级。平台坐标根据规模在不同区间内均匀生成，服务时间在10-20分钟之间随机取值，时间窗长度按总运营时长的1/8至1/4随机生成。所有实验在Intel Xeon Platinum 8269CY处理器（2.50 GHz，64 GB RAM）上运行，CPLEX和ALNS的时间上限均设为3600秒。

在小规模实例上，CPLEX仅能对≤12个平台的实例求得最优解；当平台数增至20时，CPLEX的最优性间隙高达90.43%。而ALNS在全部小规模实例上均找到了等于或优于CPLEX的解，对于20个平台的实例，ALNS的平均目标值较CPLEX上界改善了17.78%，计算时间从3600秒骤降至55秒。

进入中等规模（21-35个平台），CPLEX的全部实例均触达3600秒时间上限，最优性间隙超过90%，平均上界高达1,109,039。ALNS在平均243.90秒内即获得更好的解，相对CPLEX的平均改进幅度达到53.48%。大型实例（36-100个平台）中，CPLEX在部分实例上甚至无法找到可行解，而ALNS持续高效输出高质量解，改进幅度超过80%，最高达到98.15%。

不同无人机续航下的路径对比：续航从0.8小时增至1.5小时，船舶航行距离缩短，无人机承担更多飞行任务，总成本持续下降。（取自Fig.5）

敏感性分析揭示的运营洞见

研究围绕无人机续航时间、延误惩罚成本和时间窗长度三个关键参数进行了系统的敏感性分析，揭示了成本构成之间的深层权衡关系。

延误惩罚成本的增加则呈现出另一种规律。当单位延误成本从500元升至5000元时，总成本上升，且船舶与无人机成本同步增加。与此同时，延迟平台数量和总延迟时间均随惩罚成本的提高而下降——这表明在惩罚成本较低时，算法倾向于牺牲时间约束以追求更短的行驶距离；而惩罚成本提高后，路径优先满足时间窗，导致必要的绕行增加。

延误惩罚成本敏感性分析：惩罚成本升高导致总成本上升，但延迟平台数量和延迟时间同步下降。（取自Fig.6）

时间窗长度的影响最为直接。从宽松时间窗（总时长的1/4至3/8）收紧至严格时间窗（1/32至1/16）时，总成本、船舶成本和无人机成本均达到最高水平，延迟平台数量和延迟时间也显著增加。宽松的时间窗使算法能够规划更高效的访问序列，无需因时间约束而折返或交叉航行；而严格的时间窗迫使路径做出更多妥协。

这些发现为海上物流管理者提供了三点明确启示：第一，投资提升无人机续航技术具有直接的成本回报；第二，平台时间窗的设定需要在运营严格性与物流经济性之间取得平衡，过度收紧时间窗会推高配送成本；第三，延误惩罚成本是调节准时性与经济性的有效杠杆，合理的惩罚水平可引导配送方案在两者之间达到最优。

真实案例：10平台海上配送方案

为验证模型和算法在实际运营中的适用性，研究基于合作企业提供的真实数据进行了案例测试。案例涉及10个海上平台的包裹配送任务，每个平台有独特的坐标位置、服务时间和运营时间窗。例如，3号设施的时间窗为当日21:00至次日04:30，要求配送在夜间完成以保证次日早晨的生产连续性；而5号设施的时间窗为次日01:30至10:00，体现出不同平台作业节奏的差异。

真实案例配送路线：船舶与无人机从港口出发，按序列完成全部10个平台的配送，总运营成本142,499元。（取自Fig.10）

ALNS算法给出的最优配送方案显示，访问序列为港口→平台1→2→3→8→5→4→6→10→9→7→港口。全程总运营成本为142,499元人民币。从路径图中可以观察到船舶的行为模式：在某些平台处船舶保持静止等待无人机返回；而在其他平台处船舶继续航行，在下一个汇合点回收无人机。这种动态决策取决于后续平台时间窗的紧迫程度——当后续平台时间窗较宽裕时，船舶选择航行前进以缩短整体时间。

案例结果还显示了时间窗约束的实际效果。在10个平台中，有2个平台出现了延误（6号延误0.08小时，9号延误7.86小时，7号延误14.99小时），其余平台均在时间窗内完成配送。总延迟时间为22.93小时，占总运营时间的显著比例，这进一步印证了在实际运营中时间窗是不可忽视的紧约束。

协同模式与纯船舶模式的对比：船-无人机协同配送在成本和效率上均显著优于仅使用船舶的传统模式。（取自Fig.11）

研究贡献与未来方向

本研究在船-无人机协同路由领域做出了四项核心贡献。第一，首次将配送时间窗纳入母船-无人机路由问题框架，使得模型能够反映海上平台运营的实际时间约束，填补了理论研究与运营实践之间的空白。第二，建立了强化的MISOCP模型，通过大M值合理化和基于问题结构的有效不等式，显著提升了精确求解的能力。第三，设计了定制化的ALNS算法，其中创新的比率移除算子利用空间绕路比率的几何直观来引导搜索，并行架构进一步压缩了求解时间。第四，通过随机实例、三组基准测试集和真实案例的全方位验证，系统证明了方法的有效性。

研究也指出了若干值得探索的方向。当前模型假设船舶以恒定速度行驶，而实际中海况和油耗之间存在非线性关系，未来可引入变速航行和燃料消耗函数。模型目前仅考虑单架无人机，多无人机协同场景将带来起降时空协调的新挑战，需要开发更高效的求解策略来应对。此外，将并行计算、元启发式算法和精确方法的混合架构也可能进一步提升对超大规模实例的处理能力。