TDRP-SA Instances

We formally define the truck and drone routing problem with synchronization on arcs (TDRP-SA). Along truck routes, the locations where trucks can dispatch or retrieve drones, may be any nodes on arcs in the truck routes. At a location for a moving truck dispatching or retrieving drones, the arrival time of the truck, and the departure or arrival time of the drones affect each other, which is addressed here through the synchronization on arcs. An LRL (drone launch/retrieval location) that can be located at any node on arcs traveled by trucks, consists of a truck that keeps traveling on arcs. Each customer should be served exactly once. Customers are classified into two types; the first one is called the truck–drone customer (denoted as the TDC) and the other is called the drone customer (denoted as the DRC). Each truck–drone combination includes one truck carrying a predetermined number of drones. 1. Small-scale instances The depot in the VRPTW instance C101 is used as the depot of the TDRP-SA small-scale instance. Let nc denote the number of customer included. The nc customers are classified into TDCs and DRCs. Each truck carries two drones. The drone and truck capacity are 5 kg and 1000 kg, respectively. The maximum working time of each truck is 10 h, and the maximum flying time of one departure of each drone is 0.67 h. The average velocity of each truck and that of each drone are 60 km/h and 65 km/h, respectively. The variable cost of each truck is 0.8 Chinese Yuan/km, and the operating cost per departure of each drone is 15 Chinese Yuan. The penalty of a truck waiting for a unit of time at customer locations is estimated as 1. Each small-scale instance is denoted by C“nc”-1, C“nc”-2, or C“nc”-3. 2. Large-scale benchmark instances We modify the benchmark instances C101–C109, R101–R112, and RC101–RC108 by classifying customers into TDCs and DRCs. Each of the VRPTW benchmark instances is converted into three types of TDRP-SA test instances using a method of classifying the customers. We modify time windows of the benchmark instances C101–C109 with classified customers. If the model constraints cannot be ensured because of the modified time windows of some customers, the center of the time windows of these customers is adjusted as the arrival time of a vehicle that departs at the depot opening time. The drone and truck capacity are 60 and 1000, respectively. The maximum working time of each truck is 1000, and the maximum flying time of one takeoff for each drone is 40. The average velocity of each truck and that of each drone are 1 and 1.1, respectively. The variable cost of each truck is 1, and the operating cost per departure of each drone is 5. Each large-scale benchmark instance is denoted by “name of VRPTW benchmark instance”-1, “name of VRPTW benchmark instance”-2, or “name of VRPTW benchmark instance”-3.

我们首先正式定义**带弧上同步的卡车与无人机路径规划问题（Truck and Drone Routing Problem with Synchronization on Arcs, TDRP-SA）**。在卡车行驶路径中，可供卡车调度或回收无人机的位置，可位于卡车路径弧段上的任意节点。当行驶中的卡车在某一位置调度或回收无人机时，卡车的抵达时间与无人机的起飞、抵达时间会相互制约，本文通过弧上同步机制对此类协同约束进行处理。可部署于卡车行驶弧段任意节点的**无人机起降/回收点（Drone Launch/Retrieval Location, LRL）**，由一辆持续在弧段上行驶的卡车构成。每个客户需且仅需被服务一次。客户分为两类：第一类为**卡车-无人机协同服务客户（Truck–Drone Customer, TDC）**，第二类为**无人机独立服务客户（Drone Customer, DRC）**。每组卡车-无人机编队均由1辆搭载固定数量无人机的卡车组成。

1. 小规模测试实例
本研究将带时间窗车辆路径问题（Vehicle Routing Problem with Time Windows, VRPTW）基准实例C101的配送场站作为TDRP-SA小规模实例的起点场站。记$n_c$为测试实例包含的客户总数，该$n_c$个客户被划分为TDC与DRC两类。每辆卡车搭载2架无人机，无人机与卡车的额定载荷分别为5 kg与1000 kg。单辆卡车的最长作业时长为10 h，单架无人机单次起飞的最长飞行时长为0.67 h。卡车与无人机的平均行驶速度分别为60 km/h与65 km/h。卡车的单位里程可变成本为0.8元/公里，单架无人机每次起飞的运营成本为15元。卡车在客户位置等待单位时长的惩罚系数为1。每个小规模测试实例以`C"$n_c$"-1`、`C"$n_c$"-2`或`C"$n_c$"-3`命名。

2. 大规模基准测试实例
本研究通过将客户划分为TDC与DRC两类，对基准实例集C101–C109、R101–R112及RC101–RC108进行改造。每一个VRPTW基准实例通过客户分类方法被转换为3种不同的TDRP-SA测试实例。本研究对已完成客户分类的C101–C109基准实例的时间窗进行调整。若因调整部分客户的时间窗导致模型约束无法满足，则将这些客户的时间窗中心调整为以场站开放时刻为出发时刻的车辆抵达时间。无人机与卡车的额定载荷分别为60与1000，单辆卡车的最长作业时长为1000，单架无人机单次起飞的最长飞行时长为40。卡车与无人机的平均行驶速度分别为1与1.1，卡车的单位里程可变成本为1，单架无人机每次起飞的运营成本为5。每个大规模基准测试实例以`VRPTW基准实例名称`-1、`VRPTW基准实例名称`-2或`VRPTW基准实例名称`-3命名。

搜集汇总

背景与挑战

背景概述

该数据集定义了卡车和无人机在弧上同步的路由问题（TDRP-SA），包含基于VRPTW实例修改的小规模和大规模测试实例，涉及不同类型的客户和多种操作参数。