基于逻辑的旅行商问题与设施型无人机的分解方法

《TRANSPORTATION RESEARCH PART E-LOGISTICS AND TRANSPORTATION REVIEW》：A logic-based Benders decomposition for the traveling salesman problem with facility-based drones

　　

• •
  该模型可同时优化设施选址、配送路线规划以及无人机任务分配。
• •
  一种基于精确逻辑的本德斯分解方法，融合了整数规划与约束编程技术。
• •
  通过定制化的有效不等式与本德斯割策略，提升了问题求解的效率。
• •
  在最多160个节点的场景下，该方法的性能优于现有的商业求解器及分支剪枝算法。

引言

随着电子商务的快速发展，全球包裹递送量预计将大幅增长——2025年约为4070亿件，2026年上升至约4350亿件，到2028年这一数字更可能接近4980亿件（SellersCommerce，2026）。其中，最后一段配送环节占据了物流总成本的约53%（世界经济论坛，2024），给物流服务提供商带来了巨大的成本和时间压力。传统卡车配送还面临着交通拥堵、燃料成本上升以及日益严格的排放法规等挑战，这使得满足人们对快速、可靠且低成本配送服务的需求愈发困难。

无人飞行器，即无人机，作为一种具有诸多优势的替代配送方式逐渐受到重视。与传统车辆相比，无人机能够沿近乎直线的路径飞行，不受地面交通影响，因此能够实现更快的配送速度，并有可能降低运营成本和碳排放量（Aurambout等人，2019；Goodchild和Toy，2018）。然而，无人机载重能力有限，飞行范围也较为受限（Wang等人，2022），同时还受天气条件及监管规定的制约，难以独立承担大规模的配送任务。

自Murray和Chu在2015年提出相关研究以来，卡车与无人机协同配送模式引发了众多研究者的关注。目前主要研究了两种运作模式：串联模式与并行模式。在串联模式下，无人机由卡车搭载，飞往客户处提供服务后再返回卡车处（Agatz等人，2018；Murray和Raj，2020；Poikonen等人，2019）。虽然这种模式能扩展无人机的有效服务范围，但由于需要等待卡车以及进行同步操作，会导致效率显著下降。而在并行模式下，卡车和无人机分别从配送中心出发（Dell’Amico等人，2020；Mbiadou Saleu等人，2018；Saleu等人，2022）。这种模式避免了直接等待，但跨模式协调性较差，且仍受限于无人机的续航能力。

为解决卡车搭载无人机所存在的运营限制，尤其是卡车与无人机之间的同步问题，近期有一些研究开始探讨借助设施的无人机配送系统——在这种系统中，无人机被部署在无人机站、微型仓库、中转点或城市配送枢纽等中间设施中。这些设施由卡车定期补充物资，无人机则从这些地点出发完成最后一段配送任务。Kim和Moon在2018年提出了包含无人机站的旅行商问题模型（TSP-DS），Shi等人在2026年为该问题开发出了精确求解方法。Schermer等人则在2019年进一步拓展了该模型，加入了设施开放决策的考量，并允许启用多个设施。尽管取得了这些进展，现有的基于设施的模型大多侧重于最小化总作业时间，通常仅考虑单次往返的可行性，而没有考虑在单个无人机电池容量或飞行距离限制条件下的多次任务分配问题。正是这一不足促使本文开展了相关研究。

本文以成本最小化为目标，研究基于设施的无人机旅行商问题（TSP-FD）。该问题需要同时确定设施的开放时机、需由无人机服务的客户分配、各无人机的配送任务，以及卡车在已开放的设施和剩余客户之间的行驶路线。其核心目标是降低整体运营成本。图1展示了所提出的配送系统。本文的主要贡献如下：

• •
  我们为该问题提出了一个混合整数线性规划模型，并推导出若干有效的不等式，这些不等式被整合到一种定制化的分支剪枝算法中。
• •
  我们开发了一种基于精确逻辑的本德斯分解算法，该算法融合了混合整数线性规划与约束编程技术。借助针对该问题的特殊割策略及加速方法，所提出的算法能够解决最多包含160个节点的问题实例。
• •
  我们通过大量数值实验，对比了所提出的本德斯分解算法与现有的先进商业求解器以及定制化分支剪枝算法的效率，并对关键运营参数进行了敏感性分析，以期为实际应用提供参考。

本文的其余结构安排如下：第2节回顾相关文献；第3节介绍问题描述及数学模型；第4节阐述精确的本德斯分解方法；第5节展示计算结果，包括所提算法的性能表现及敏感性分析结果；第6节对全文进行总结，并探讨未来的研究方向。

章节要点

文献综述

在本节中，我们将回顾两个与之密切相关的问题：借助设施的卡车与无人机协同配送问题，以及两层选址路径问题。

问题描述与建模

首先，我们对问题进行正式描述，并提出了一种基于弧的混合整数线性规划模型。

基于逻辑的本德斯分解方法

TSP-FD是旅行商问题的一种变体，因此属于NP难问题。随着问题规模的增长，直接求解混合整数线性规划模型AF-MILP会变得极其复杂。为解决这一问题，我们采用了基于逻辑的本德斯分解方法。

原问题被分解为一个选址路径主问题（记为LRMP，见第4.1节）以及一组无人机任务分配子问题（记为DASP，见第4.3节）。通过这种方式可以强化主问题的

计算实验

这些算法是用Java语言实现的，而数学模型则是通过IBM ILOG CPLEX Optimization Studio 20.1软件进行求解的。所有实验都在一台配备有Intel Core i7-14700处理器（2.10GHz）和32GB内存的计算机上完成，每次运行的时间限制为3600秒。

结论

本文研究了基于设施的无人机旅行商问题（TSP-FD），该问题旨在通过同时优化设施开放、客户分配、卡车路线规划以及无人机任务分配，来实现整体运营成本的最小化。在所提出的配送系统中，卡车通过补货操作同时为客户和设施提供服务，而部署在已开放设施中的无人机则负责完成最后一段配送任务。针对TSP-FD问题，我们建立了混合整数线性规划模型

CRediT作者贡献说明

Yuan Yuan：方法设计、问题研究、资金获取、形式化分析、概念构建、初稿撰写。Huan Tang：初稿撰写、软件开发、数据整理、形式化分析、问题研究。Jiliu Li：文稿审阅与修改、项目监督、方法设计、概念构建。Frederic Semet：文稿审阅与修改、项目监督、结果验证。Hu Qin：文稿审阅与修改、概念构建、结果验证。

利益冲突声明

作者声明，他们不存在任何可能影响本文研究成果的已知财务利益关联或个人关系。

Yuan Yuan|Huan Tang|Jiliu Li|Frederic Semet|Hu Qin