TDRP-TW instances

Considering the commercial interest and attention on both trucks and drones carried by trucks for last-mile parcel deliveries, we introduce the TDRP-TW. Solving the TDRP-TW necessitates finding the cost-minimizing routes. Each TDRP-TW network includes a number of customers and one depot housing a fleet of truck–drone combinations. The network is denoted by an undirected complete graph in which the nodes represent the depot and customers, and the arcs represent the possible moves of trucks and drones. The depot is the only parcel source. The truck–drone combination includes one truck carrying several drones. All customer demand should be satisfied. Customer demand cannot be split. Customers are classified into two types: truck customer (TC) or drone customer (UC). Each TC should be serviced by one truck, and each UC should be serviced by one drone. The number of drones carried by each truck is assumed to be the same. A vehicle in use may be a single truck or drone, or a truck–drone combination. Each truck–drone combination works in a “paired” modality. A drone can carry several parcels to serve more than one customer. It is assumed that there are enough trucks and drones. Along its route, a truck can dispatch and retrieve the carried drones only at a TC, which is referred to as the satellite. A drone can be retrieved by its truck at a satellite, or can return directly to the depot. We choose the test instances from the Solomon (1987) VRPTW benchmark problems with 100 customers and convert them to TDRP-TW instances. Let nc denote the number of customers included in the TDRP-TW network. The nc customers are classified into TCs and UCs. Parameter p denotes the percentage of UCs in the nc customers, and p = 25%, 50% or 75%. All customer time windows are scale down by the same constant. The demand of a TC or a UC is a random number in the range of (0, 50 kg) or (0, 2.5 kg), respectively. When nc < 100, the converted instances are specified as small- and medium-scale instances. Each of the small- and medium-scale instances is denoted by C“nc”-25, C“nc”-50, or C“nc”-75; and C“nc”-25, C“nc”-50, or C“nc”-75 has the percentage of UCs 25%, 50%, or 75%, respectively. When nc = 100, the converted instances are specified as large-scale instances. Each of the large-scale instances is denoted by “name of VRPTW benchmark instance”-75, which has the percentage of UCs 75%.鉴于卡车及车载无人机用于末端包裹配送的商业价值与行业关注度持续走高，我们提出了带时间窗的卡车-无人机配送路径问题（Truck-Drone Routing Problem with Time Windows, TDRP-TW）。求解该问题的核心目标为找到总成本最小的配送路径。每个TDRP-TW配送网络包含若干客户节点与一个配送中心，该中心配备多组卡车-无人机协同车队。该网络以无向完全图建模：节点代表配送中心与客户，边对应卡车与无人机的可行移动路径。配送中心是唯一的包裹货源。每组卡车-无人机协同车队由1台搭载多架无人机的卡车组成。所有客户的配送需求均需全额满足，且需求不可拆分。客户分为两类：卡车服务客户（Truck Customer, TC）与无人机服务客户（Drone Customer, UC），每类客户分别需由1台卡车或1架无人机完成配送服务。每台卡车搭载的无人机数量固定一致。可用的作业单元可分为单一卡车、单一无人机，或卡车-无人机协同编队。每组卡车-无人机协同编队采用“配对”作业模式：无人机可搭载多件包裹为多位客户提供配送服务。仅可在卡车服务客户（即所谓的卫星节点）处，由搭载该无人机的卡车完成调度与回收操作。无人机可在卫星节点由所属卡车回收，亦可直接返回配送中心。 我们的测试实例源自Solomon（1987）提出的含100个客户的带时间窗的车辆路径问题（Vehicle Routing Problem with Time Windows, VRPTW）基准测试集，并将其转换为TDRP-TW格式实例。设$n_c$为TDRP-TW网络中的客户总数量。将$n_c$个客户划分为TC与UC两类，参数$p$表示UC在总客户数中的占比，取值为25%、50%或75%。所有客户的时间窗均按同一比例进行缩放。TC的配送需求为区间(0, 50 kg]内的随机数，UC的配送需求则为区间(0, 2.5 kg]内的随机数。 当$n_c < 100$时，转换得到的实例被划分为中小型规模实例。每组中小型规模实例以C“$n_c$”-25、C“$n_c$”-50或C“$n_c$”-75的格式命名，其中C“$n_c$”-25、C“$n_c$”-50与C“$n_c$”-75分别对应UC占比为25%、50%与75%的实例。当$n_c = 100$时，转换得到的实例被划分为大规模实例，每组大规模实例以“原VRPTW基准实例名称”-75的格式命名，其UC占比固定为75%。