Benchmark Instances and Optimal Solutions for the TSP with Drone

本数据集名为‘Benchmark Instances and Optimal Solutions for the TSP with Drone’，由意大利摩德纳和雷焦艾米利亚大学的DISMI研究机构创建。数据集包含172个实例，分为两部分：72个10客户实例和100个9客户实例，均用于研究卡车与无人机协同配送问题。每个实例提供详细的旅行时间矩阵和无人机服务客户的能力信息。数据集旨在为该领域的研究提供基准测试和最优解，以验证新解决方案的有效性。

This dataset, named 'Benchmark Instances and Optimal Solutions for the TSP with Drone', was created by the DISMI research institution of the University of Modena and Reggio Emilia, Italy. It includes 172 total instances, divided into two subsets: 72 instances with 10 customers and 100 instances with 9 customers, all dedicated to research on the collaborative truck-drone delivery problem. Each instance provides detailed travel time matrices and information on the customer-serving capabilities of drones. This dataset is designed to offer benchmark test cases and optimal solutions for studies in this domain, enabling the validation of the effectiveness of newly proposed solution approaches.

搜集汇总

数据集介绍

构建方式

该数据集基于旅行商问题与无人机协同配送的经典场景，由M. Dell’Amico等人构建。研究团队从文献中提炼出九个基本问题设定，涵盖无人机循环飞行、发射与回收时间、电池续航、地面等待等核心组件。数据集包含两组基准实例：一组源自Murray和Chu的72个10节点实例，另一组源自Poikonen等人的100个9节点实例。每份实例均提供卡车与无人机的行驶时间矩阵，以及可选的可服务客户列表。通过精确求解数学规划模型，利用Gurobi优化器获得所有问题设定的最优解，并将实例与解集整理为公开的基准测试库。

特点

该数据集具有高度的系统性与完整性，首次为卡车-无人机协同配送问题提供了公认的基准测试集。其显著特点在于覆盖了九种不同的问题设定，从基础模型到包含循环、发射时间、电池限制等复杂约束的变体，能够全面评估不同算法的性能。所有实例均附带精确的最优解，为算法验证提供了可靠的标准。此外，数据集结构清晰，每份实例独立存储，包含详细的CSV格式时间矩阵，便于研究者直接调用与复现实验。

使用方法

研究者可直接从公开网站下载数据集文件夹，其中包含DMN-B1与DMN-B2两个子集。每个实例文件夹内含tauT.csv与tauD.csv时间矩阵文件，以及可选的Cprime.csv文件。通过读取这些数据，可构建完整的TSP-D问题模型。建议根据研究需求选择对应的九种问题设定之一，并利用提供的精确最优解作为基准，验证新提出算法的求解质量与效率。数据集支持多种编程环境，研究者可将其嵌入优化算法或机器学习框架中进行对比实验。

背景与挑战

背景概述

随着城市物流需求的激增，无人机与卡车协同配送作为一种创新模式，正逐步从理论构想走向实际应用。该数据集由M. Dell'Amico、R. Montemanni和S. Novellani于2021年创建，隶属于意大利摩德纳与雷焦艾米利亚大学，旨在填补旅行商问题与无人机协同优化（TSP-D）领域缺乏统一基准的空白。核心研究问题聚焦于如何精确建模卡车与无人机协同配送的九种基本问题设定，涵盖目标函数最小化、客户覆盖、路径规划及同步约束等关键组件。该数据集通过提供72个10客户和100个9客户实例的最优解，为后续算法验证奠定了坚实基础，显著推动了无人机物流运筹优化领域的发展。

当前挑战

该数据集面临的核心挑战在于解决TSP-D领域的多重困境。首先，领域问题层面，卡车与无人机协同优化需同时处理路径规划、时间同步及电池续航等复杂约束，属于NP-hard问题，现有模型难以在可接受时间内求得大规模实例的最优解。其次，构建过程中，研究人员需在缺乏公认基础模型的情况下，从文献中提炼出九种问题设定，并确保组件定义（如发射时间、环路允许性）的精确无歧义。此外，数据生成需协调曼哈顿距离与欧氏距离的混合计算，并处理随机化时间矩阵的对称性，这增加了求解器验证的难度。最终，尽管实例规模较小，但最优解的获取仍依赖长达两小时的运算，凸显了算法效率与可扩展性的严峻挑战。

常用场景

经典使用场景

在物流与运筹优化领域中，卡车与无人机协同配送问题日益成为研究热点。该数据集聚焦于旅行商问题（TSP）的无人机变体，提供了九个不同问题设定下的基准实例与最优解。这些设定涵盖了是否允许无人机循环飞行、是否考虑发射与回收时间、是否限制电池续航以及是否允许无人机在节点降落等待等关键组件。研究者可借此标准化评估新型算法在卡车-无人机协同路径规划中的表现，为后续方法比较提供坚实可靠的参考基准。

解决学术问题

该数据集有效填补了文献中缺乏公认基础模型与标准化测试实例的空白。长期以来，由于不同论文对问题组件的定义存在歧义，导致算法比较困难。该工作通过明确界定九种问题设定，并给出精确的数学模型与最优解，解决了学术界在卡车-无人机路径优化中模型不统一、基准不一致的难题。其意义在于为精确算法、启发式方法及元启发式策略的性能验证提供了权威的对照标准，推动了该领域研究走向规范化与系统化。

衍生相关工作

该数据集衍生了一系列经典研究工作，包括Dell'Amico等人提出的改进混合整数线性规划模型、基于分支定界的精确求解方法，以及结合局部搜索的数学启发式算法。此外，Schermer等人开发的支路切割算法与Roberti等人设计的精确求解框架均以此基准作为验证平台。这些工作不仅提升了求解效率，还拓展了问题变体，如考虑多无人机协同或动态电池消耗，进一步丰富了卡车-无人机协同配送的理论体系与算法工具箱。