《TRANSPORTATION RESEARCH PART C-EMERGING TECHNOLOGIES》：A stage-based formulation and meta-heuristic algorithm for the revisit Flying SideKick Traveling Salesman Problem
编辑推荐：
•提出了RV-FSTSP模型，该模型允许卡车在部署无人机时返回或保持静止。•首次建立了多项式规模的5指数和3指数模型，用于处理循环配送和重复访问问题。•提出了一种将ALNS与CMSA框架相结合的元启发式算法。•该算法的性能优于现有基准启发式方法，最佳改进幅度分别为9.20%和6.
- •
提出了RV-FSTSP模型，该模型允许卡车在部署无人机时返回或保持静止。
- •
首次建立了多项式规模的5指数和3指数模型，用于处理循环配送和重复访问问题。
- •
提出了一种将ALNS与CMSA框架相结合的元启发式算法。
- •
该算法的性能优于现有基准启发式方法，最佳改进幅度分别为9.20%和6.19%。
引言
作为供应链的最后一段，负责将货物从配送中心送到最终客户手中的“最后一公里”配送，已成为现代物流系统中最为复杂且成本最高的环节之一。由于配送点分散、需求变化大、城市交通拥堵（进而带来污染和空气质量问题，Nguyen等人，2022年）、以及消费者期望不断提高，最后一公里物流可能占据总运输成本的50%以上（Shaikley，2024年）。随着电子商务的快速发展以及对快速灵活配送服务需求的增加，物流企业面临着优化这一关键环节的巨大压力。
为应对这一挑战，越来越多的研究和行业创新致力于将新兴技术融入最后一公里物流中。其中，无人驾驶飞行器，也就是通常所说的无人机，正逐渐得到广泛应用。无人机最初是为军事目的而研发的，如今已越来越多地被应用于农业、零售等多个民用领域。具体而言，无人机配送已在美国的多个地方开展试点，展现出其变革最后一公里物流的潜力。在物流和供应链创新方面处于领先地位的亚马逊，正处于这一变革的前沿。该公司正在积极测试使用其最新的MK30无人机进行配送，这类无人机在载重能力和飞行距离方面都有显著提升。它们能够携带重达5磅的包裹，飞行距离也是以往型号的两倍，因此有望成为实现高效快速配送的理想解决方案。
受到这些进展的启发，其他企业也在探索将无人机纳入自身的服务体系中，以此补充传统的最后一公里配送方式，甚至用于运送食品和药品等易腐或重要的物品。例如，温迪公司在2024年初在弗吉尼亚州克里斯蒂安斯堡进行的试点测试就取得了不错的成果。针对这一成功，温迪公司表示（Hamblen，2024年）：“无人机配送可以说是我们配送平台的一种自然延伸。”随着人们对无人机兴趣的日益浓厚，相关市场也呈现出强劲的发展势头：预计到2028年，全球无人机包裹配送市场规模将达到280亿美元，这充分体现了人们对于无人机能够在复杂配送环境中以极高的准确性和速度完成配送任务的信任。
尽管取得了这些突破，但仍然存在一些阻碍无人机在最后一公里配送中得到广泛应用的难题。无人机在运营能力上存在固有限制，比如载重和飞行距离都受到限制。此外，建立纯无人机配送系统需要大量的基础设施投资，同时还要应对复杂的监管要求。正因如此，利用无人机来辅助卡车配送便成为一种解决上述问题的实用方案，因为将无人机与卡车配送相结合，企业就可以构建一种混合式系统，充分利用两种运输方式的优点。温迪公司进一步强调了这一策略，称（Hamblen，2024年）：“将无人机配送与传统司机相结合，能够确保温迪公司满足那些希望以数字方式接收订单的客户的需求。”亚马逊也在研究类似的物流系统，即由配送卡车先运送包裹，然后再从卡车上派出无人机来完成最后的配送任务（Antunes，2021年）。
这种整合方式还能应对那些因运营限制而需要更加灵活处置的情况。例如，当中间的一些客户地点不适合无人机起飞或回收，或者只有少数几个合适的交接点可供使用时，卡车可能需要返回之前已经服务过的地点。又或者，在无人机完成配送任务期间，卡车可以保持静止状态，这样可以简化协调工作，或者将无人机操作集中在法律和操作上都可行的起飞/回收地点。如图1(a)所示，卡车首先前往地点A，然后派无人机将包裹送到位于河对岸的客户E手中。之后，卡车继续前往B、C和D等地为更多客户配送。由于路线上的某些地点，如B和C，可能不适合无人机作业，因此卡车在完成剩余的配送任务后会返回A地点取回无人机。在图1(b)所示的另一种情况下，卡车会前往地点A并停留在那里，而无人机则负责向附近的多个客户配送包裹。这些例子都体现了在最后一公里配送系统中，实现卡车与无人机之间灵活且动态的协作的重要性，这也是推动本研究的原因所在。
在本文中，我们提出了一种改进版的“飞行伙伴旅行商问题”（FSTSP），该版本通过允许卡车（i）返回之前已经服务过的地点，或（ii）在派遣无人机进行配送时保持静止，从而提升了运营的灵活性。这种改进版本能够涵盖更广泛的现实物流场景，尤其是那些存在地理或运营限制、可能导致无人机无法正常起飞或回收的场景。通过扩展传统的FSTSP框架，我们的研究旨在缩小理论模型与混合式无人机-卡车配送系统实际应用之间的差距。据我们所知，本研究在统一的优化框架下，对现有文献中研究的各类FSTSP变体进行了全面概括。
我们在该领域的贡献主要有三点。
- •
我们提出了两种基于多项式阶段的建模方法，这些方法允许卡车返回已访问的地点，并在循环模式下作业。利用这些方法，我们能够在1小时内精确解决最多20个客户的配送问题。
- •
我们开发了一种元启发式算法，该算法将自适应大邻域搜索（ALNS）与构建-合并-求解-调整（CMSA）框架相结合，能够高效地解决最多90个客户的配送问题。
- •
我们进行了大量实验，以评估所提出的问题模型及建模方法的优势，并将这种元启发式算法与其他方法进行了对比测试。与用于传统FSTSP问题的两种最先进的启发式方法相比，所提出的新模型和元启发式算法在特定场景下分别实现了9.20%和6.19%的效率提升。
本文的其余部分结构如下。第2节我们将回顾和总结近期与FSTSP相关的研究成果。第3节和第4节则会详细介绍问题模型，并给出我们的数学建模方法以及相应的算法解决方案。第5节将通过全面的计算实验，来评估我们所提出的建模方法和解决方案的有效性。最后在第6节进行总结。
章节摘要
文献综述
近年来，关于卡车与无人机在最后一公里配送中协同工作的研究已经取得了很大进展，我们主要关注的是卡车和无人机并行作业以缩短配送完成时间的场景。有兴趣的读者可以参考Otto等人（2018年）、Roca-Riu和Menéndez（2019年）、Macrina等人（2020b年）、Merkert和Bushell（2020年）、Boysen等人（2020年）、Ding等人（2021年）、Li等人（2021年）以及Moradi等人（2024年）所做的综述文章。
问题描述与建模
RV-FSTSP模型涉及一辆卡车和一架无人机共同为客户配送包裹。每个客户的需求量为一件，这件包裹可以由卡车或无人机送达。不过，由于一些实际限制，有些客户无法通过无人机送达，这些限制包括：
- •
耐力限制：包裹的重量可能超过无人机的承载能力。此外，无人机的电池容量也可能不足以支撑其飞到客户所在地。
基于MIP的RV-FSTSP算法
算法1是一种两阶段元启发式算法，用于解决“可返回飞行伙伴旅行商问题”（RV-FSTSP）。该算法将一种基于构造性的删除-重新插入启发式方法与基于MIP的局部搜索方法相结合，从而高效地探索和利用解空间。该算法的具体步骤如下：
- •
第一阶段：通过删除与重新插入实现迭代优化。算法从通过算法2生成的初始可行解开始，反复删除一部分客户，
实验评估
本节对我们为解决RV-FSTSP问题所提出的方法进行了全面的实验评估，这些方法包括精确的优化建模方法和元启发式算法。实验的主要目的是评估这些方法在各种基准测试场景下的计算质量、可扩展性以及稳定性。评估工作主要包括两个部分：
- •
建模方法评估（第5.1节）：我们研究了不同MIP模型的性能
结论
本文在“飞行伙伴旅行商问题”的基础上进行了拓展，该问题研究的是卡车和无人机协同为多个客户配送包裹的场景。我们通过允许卡车返回之前已经服务过的地点，或在派遣无人机配送时保持静止，来考虑不同的地理或运营限制因素。我们将这类问题称为“可返回飞行伙伴旅行商问题”（RV-FSTSP）。
我们在该领域做出了重要贡献，因为我们是首次提出
CRediT作者贡献说明
Le Thi Hong：撰写——初稿、软件工具、方法论、研究实施、概念设计。Duc D. Vu：撰写——审阅与编辑、可视化呈现、结果验证。Tran Nam Khanh：撰写——初稿、软件工具、方法论、形式化分析、概念设计。Nguyen Dinh Cong：撰写——审阅与编辑、监督指导、研究实施。Duc-Minh Vu：撰写——审阅与编辑、撰写——初稿、结果验证、监督指导、项目管理、方法论、研究实施、形式化分析，
Le Thi Hong|Duc D. Vu|Tran Nam Khanh|Nguyen Dinh Cong|Duc-Minh Vu
