DOI: 10.12677/aam.2025.142083, PDF, HTML, XML,  被引量   
作者: 岳存慧：河北工业大学理学院，天津
关键词: 协同配送；多目标优化；目标空间分解；稳定匹配；并行策略；Coordinated Delivery； Multi-Objective Optimization； Objective Space Decomposition； Stable Matching； Parallel Strategy

文章引用：岳存慧. 基于多目标演化算法的卡车无人机协同路径问题研究[J]. 应用数学进展, 2025, 14(2): 430-447. https://doi.org/10.12677/aam.2025.142083

1. 引言

卡车无人机协同配送作为一种新型的物流配送模式，为最后一公里配送提供了一个较为经济的配送方式[1]。单卡车单无人机问题通常被认为是飞行伙伴旅行商问题(FSTSP)或带无人机的旅行商问题(TSP-D)，分别由Murray和Chu [2]和Agatz等人[3]首次提出。后来，Ha等人[4]考虑了TSP-D的一个新变体，其目标是最小化操作成本。Luo等人[5]考虑了经典的两级TSP的变体，其中卡车在道路网络上行驶，无人机在道路以外的区域行驶，以访问卡车无法到达的节点。单卡车多无人机问题是单卡车单无人机问题的扩展。Murray和Chu [3]提出了一个称为并行无人机调度TSP (PDSTSP)的版本。在PDSTSP中，多架无人机从一个仓库发射，为附近的客户提供服务，一辆卡车独立地为其他客户提供服务。并行无人机调度旅行推销员问题(PDSTSP)是卡车无人机混合交付系统的典型优化问题，很难通过元启发式方法解决。Mbiadou Saleu等人[6]提出了一个迭代的两步启发式方法求解PDSTSP。Chen等人[7]尝试将强化学习技术集成到基于毁坏重建的元启发式算法中，提出了一种混合启发式方法求解PDSTSP。多卡车多无人机是单卡车多无人机问题和单卡车单无人机问题的扩展。在多卡车多无人机协同配送情况下，Teimoury等人[8]专注于卡车和无人机协调，在一个双层次交付系统中引入了带利润的成对取货和送货问题，提出一种混合变邻域搜索算法求解多卡车多无人机协同配送问题。Ham [9]通过引入多架无人机和多辆卡车扩展了PDSTSP，并通过使用约束编程解决了问题。Lin等人[10]设计了混合遗传算法和混合粒子群算法求解多卡车多无人机协同配送问题。

上述研究仅涉及单一目标优化，但在实际的卡车无人机协同配送问题中，单一目标优化往往无法完全满足现实需求。为了增强决策的多样性和灵活性，需要同时考虑多个优化目标。当前对于使用多目标演化算法求解多目标卡车无人机协同配送问题的研究尚不充分。2020年Wang等人[11]将FSTSP扩展到多目标版本，并提出了改进的NSGA-II算法来求解该模型。2022年Luo等人[12]针对柔性时间窗口下的单卡车多无人机路径规划问题建立多目标模型，并提出了将NSGA-II与改进的Pareto局部搜索相结合的混合多目标遗传优化方法求解该模型。2023年Luo等人[13]进一步研究了软时间窗口下的多目标单卡车多无人机送取货问题(MCRP-DP)，并提出了一种基于目标空间分解的自适应资源分配的多目标进化算法(ODEA-ARA)来求解该模型。

本文针对柔性时间窗下的多目标多卡车多无人机协同路径问题(Multi-Objective Multi-Truck Multi-Drone Collaborative Routing Problem with Flexible Time Windows, MO-MTMDCRP-TW)，构建了一个最小化运输成本和最小化客户不满意度的多目标优化模型，并提出基于目标空间分解的改进MOEA/D算法(MOEA/D-OSD)来求解该模型。

2. 问题描述和模型建立

为了解决MO-MTMDCRP-TW，本节构建了一个多目标优化模型，旨在最小化运输成本的同时最小化客户不满意度。

2.1. 问题描述

在该问题中，存在一个仓库和多个顾客，每个顾客的需求量，仓库与顾客之间以及任意两个顾客之间的距离是已知的。仓库拥有数量不限的相同类型的卡车，每辆卡车携带R辆无人机。单个无人机可以在其最大载荷容量和最远飞行距离内将货物运送给多个顾客。每个顾客只能由一辆卡车或一架无人机服务一次。由仓库派遣多辆卡车和无人机向顾客运送货物。卡车从仓库出发，卡车的货物负载必须不超过其最大载荷容量。无人机可以从携带它的卡车上起飞，在向多个顾客交付和接收货物后返回仓库或所属卡车。当无人机到达客户节点时，无人机会自动卸载包裹并立即离开。在完成无人机交付后，无人机可以再次从卡车上发射新包裹。虽然无人机可以多次发射，但在同一节点只允许发射一次。卡车配送与无人机配送有些许不同，卡车在客户节点处需要一段服务时间，这段服务时间包含驾驶员手动卸载包裹可能需要的时间以及为无人机安装新包裹和新电池的时间。此外由于多种不确定因素，很难确保卡车和无人机同时到达同一个客户节点。因此，首先到达汇合节点的卡车或无人机需要等待未到达的。图1展示了多卡车多无人机协同路径问题的示意图。本研究的目的是设计出卡车和无人机协同配送路径，以最大限度地减少运输成本和提高客户满意度。

Figure 1. MO-MTMDCRP-TW model diagram

图1. MO-MTMDCRP-TW模型示意图

MO-MTMDCRP-TW模型中涉及的参数和决策变量见表1。

在建立数学模型之前，必须建立一些基本假设：

1) 所有顾客的位置已知，且一位顾客每次只能由一辆卡车或一架无人机服务一次。

2) 在一次无人机行程中，每架无人机在容量和续航里程约束内可以携带多个包裹，访问一个或者多个客户点。

3) 无人机在被取回之前不能重新发射。

4) 无人机在被卡车取回后立即更换电池。

5) 无人机只能由卡车在客户节点处取回，而不能沿着卡车路径中两个节点之间的弧取回。

6) 无人机派送完之后回到了仓库点，则无人机停止服务。

7) 每个客户点都有一个期望时间窗口和允许时间窗口。

8) 只有一个仓库作为派送的起点和终点。

9) 除了在客户节点处之外，卡车处于连续匀速运动中。

10) 无人机在服务之后立即离开客户节点，用于发射和取回无人机以及向无人机供应电池和包裹的时间很短，并且由卡车的服务时间覆盖。

11) 无人机在等待为客户服务过程中以及提前到达汇合点等待卡车过程中降落在安全着陆区。

12) 由于城市道路网的限制，卡车的路线使用曼哈顿距离测量。

13) 无人机在两个节点之间沿直线行驶，其路线使用欧几里得距离测量。无人机的路线仅由水平行进组成，不考虑垂直移动。

14) 不考虑无人机轻件点的配送时间。

Table 1. Symbol description

表1. 符号描述

集合、符号参数、决策变量
$V$	所有客户点的集合 $V=\left\{0,1,\cdots ,c,c+1\right\}$ ，其中0和c + 1代表仓库点
$C^T$	只能由卡车服务的客户点的集合
$C^D$	可以由卡车或无人机服务的客户点的集合
$C$	所有客户节点的集合 $C=\left\{1,2,\cdots ,c\right\}$
$E$	弧集
$K$	同类卡车组成的车队集合
$R$	每辆卡车携带的无人机数目
$D^k$	卡车 $k\in K$ 携带的无人机的行程
$q_i$	客户点 $i\in C$ 的货物需求量
${\delta }_{ij}^T$	与弧 $\left(i,j\right)\in E$ 相关的卡车行驶距离
${\delta }_{ij}^D$	与弧 $\left(i,j\right)\in E$ 相关的无人机行驶距离
${\tau }_{ij}^T$	与弧 $\left(i,j\right)\in E$ 相关的卡车行驶时间
${\tau }_{ij}^D$	与弧 $\left(i,j\right)\in E$ 相关的无人机行驶时间
$\epsilon$	无人机的飞行耐力
$Q^T$	卡车载重
$Q^D$	无人机载重
$W^D$	无人机自重
$C^T$	卡车每单位距离运输成本
$C^D$	无人机每单位距离运输成本
$s_i$	卡车在客户点 $i\in C$ 的服务时间
$M$	很大的正数
$\left[a_i,b_i\right]$	客户点 $i\in C$ 的期望时间窗
$\left[m_i,n_i\right]$	客户点 $i\in C$ 的允许时间窗
${\mu }_i(t_i)$	车辆到达客户点 $i\in C$ 时的客户时间不满意度
$y_i$	在客户点 $i\in C$ 的货物损坏程度
${\phi }_i\left(y_i\right)$	车辆到达客户点 $i\in C$ 时的客户货损不满意度
$z_i{}^{k,T}$	$z_i{}^{k,T}=1$ ，若客户点 $i\in C$ 被卡车 $k\in K$ 服务，否则 $z_i{}^{k,T}=0$
$z_{i{d}^k}^{k,D}$	$z_{i{d}^k}^{k,D}=1$ ，若客户点 $i\in C$ 被卡车 $k\in K$ 的无人机行程 $d^k\in D^k$ 服务，否则 $z_{i{d}^k}^{k,D}=0$
$x_{ij{d}^k}^k$	$x_{ij{d}^k}^k=1$ ，如果卡车 $k\in K$ 的无人机行程 $d^k\in D^k$ 沿着弧 $\left(i,j\right)\in E$ 行驶，否则 $x_{ij{d}^k}^k=0$
$y_{ij}^k$	$y_{ij}^k=1$ ，如果卡车 $k\in K$ 沿着弧 $\left(i,j\right)\in E$ 行驶，否则 $y_{ij}^k=0$
$d_i{}^k$	卡车 $k\in K$ 在 $i\in V$ 处携带的无人机数目
$t_i{}^{k,T}$	卡车 $k\in K$ 到达节点 $i\in V\backslash \left\{0\right\}$ 的时间
$t_{i{d}^k}^{k,D}$	卡车 $k\in K$ 的无人机行程 $d^k\in D^k$ 到达节点 $i\in V\backslash \left\{0\right\}$ 的时间
$r_i{}^{k,T}$	卡车 $k\in K$ 离开节点 $i\in V\backslash \left\{c+1\right\}$ 的时间
$r_{i{d}^k}^{k,D}$	卡车 $k\in K$ 的无人机行程 $d^k\in D^k$ 离开节点 $i\in V\backslash \left\{c+1\right\}$ 的时间
$h_{i{d}^k}^{k,L}$	$h_{i{d}^k}^{k,L}=1$ ，如果 $i\in V\backslash \left\{c+1\right\}$ 为卡车 $k\in K$ 的无人机行程 $d^k\in D^k$ 的发射节点，否则 $h_{i{d}^k}^{k,L}=0$
$h_{i{d}^k}^{k,R}$	$h_{i{d}^k}^{k,R}=1$ ，如果 $i\in V\backslash \left\{0\right\}$ 为卡车 $k\in K$ 的无人机行程 $d^k\in D^k$ 的回收节点，否则 $h_{i{d}^k}^{k,R}=0$
$W_i{}^{k,T}$	卡车 $k\in K$ 在 $i\in V\backslash \left\{0\right\}$ 处等待无人机的时间长度
$W_{i{d}^k}^{k,D}$	卡车 $k\in K$ 的无人机行程 $d^k\in D^k$ 在 $i\in V\backslash \left\{0\right\}$ 处等待卡车的时间长度

2.2. 数学模型

本文旨在以最低的运输成本和最小的客户不满意度找到多卡车多无人机的协同配送路线。由于运输成本与无人机和卡车的行进距离有关，所以第一个目标可以表示为：

$\min f_1={\displaystyle \underset{k\in K}{\sum }\left({\displaystyle \underset{\left(i,j\right)\in E}{\sum }{C}^T{\delta }_{ij}^T{y}_{ij}^k}+{\displaystyle \underset{\left(i,j\right)\in E}{\sum }{\displaystyle \underset{d^k\in D^k}{\sum }{C}^D{\delta }_{ij}^D{x}_{ij{d}^k}^k}}\right)}$ (1)

第二个目标是最小化客户不满意度(即最大化客户满意度)，目的是提高客户服务水平。高满意度通常带来更多的业务机会和收入增长。客户满意度与车辆到达客户点时间和货物损坏程度有关。

由于各种外部因素(如交通状况、交通拥堵等)的影响，可能导致车辆无法准确按照预定的时间到达客户点。因此，在实际配送中，通常会采用柔性时间窗的概念，允许一定的时间窗口来容纳车辆的到达。由车辆交付的节点i处的客户时间不满意度 ${\mu }_i\left(t_i\right)$ 可以表示为：

${\mu }_i\left(t_i\right)=\{\begin{array}{l}\frac{t_i-b_i}{n_i-b_i},b_i\le t_i\le n_i\\ 0,a_i\le t_i\le b_i\\ \frac{a_i-t_i}{a_i-m_i},m_i\le t_i\le a_i\\ 1,其他\end{array}$ (2)

关于货损满意度[14]，在整个配送过程中，货物的损坏程度也一定程度上影响着客户服务水平。货物损坏概率越高，客户满意度越低。只考虑运输过程中随运输时间积累造成的货损。货损率计算公式为：

$y_i=\beta \left(t_i-t_0\right)$ (3)

其中 $y_i$ 为客户点i的货物损失率， $t_0$ 是从仓库出发的时间， $\beta$ 为货物单位时间货损系数。假设货物货损率范围 $\left[0,h\right]$ ，客户可容忍的货损率范围为 $\left[h,H\right]$ ，车辆交付的节点i处的货损不满意度函数为：

${\phi }_i\left(y_i\right)=\{\begin{array}{l}0,0\le y_i\le h\\ \frac{y_i-h}{H-h},h\le y_i\le H\\ 1,y_i>H\end{array}$ (4)

所以第二个目标可以表示为最小化客户的总体不满意度(即最大化满意度)：

$\min f_2={\displaystyle \underset{k\in K}{\sum }\left({\displaystyle \underset{i\in C}{\sum }{z}_i^{k,T}}{\mu }_i\left(t_i^{k,T}\right)+{\displaystyle \underset{i\in C^D}{\sum }{\displaystyle \underset{d^k\in D^k}{\sum }{z}_{i{d}^k}^{k,D}{\mu }_i}}\left(t_{i{d}^k}^{k,D}\right)+{\displaystyle \underset{i\in C}{\sum }{z}_i^{k,T}{\phi }_i}\left(y_i\right)+{\displaystyle \underset{i\in C^D}{\sum }{\displaystyle \underset{d^k\in D^k}{\sum }{z}_{i{d}^k}^{k,D}{\phi }_i}}\left(y_i\right)\right)}$ $(5)$

下面是约束条件：

${\displaystyle \underset{k\in K}{\sum }\left({\displaystyle \underset{d^k\in D^k}{\sum }{z}_{i{d}^k}^{k,D}+z_i^{k,T}}\right)}=1,\forall i\in C^D$ (6)

${\displaystyle \underset{k\in K}{\sum }{z}_i^{k,T}}=1,\forall i\in C^T$ (7)

${\displaystyle \underset{i\in V\backslash \left\{c+1\right\}}{\sum }{x}_{ij{d}^k}^k}\ge z_{j{d}^k}^{k,D},\forall j\in C,\forall k\in K,\forall d^k\in D^k$ (8)

${\displaystyle \underset{i\in V\backslash \left\{c+1\right\}}{\sum }{y}_{{}_{ij}}^k}=z_j^{k,T},\forall j\in C,\forall k\in K$ (9)

${\displaystyle \underset{j\in V\backslash \left\{0\right\}}{\sum }{x}_{ij{d}^k}^k}\le 1,\forall i\in V\backslash \left\{c+1\right\},\forall k\in K,\forall d^k\in D^k$ (10)

${\displaystyle \underset{j\in V\backslash \left\{c+1\right\}}{\sum }{x}_{ji{d}^k}^k}\le 1,\forall i\in V\backslash \left\{0\right\},\forall k\in K,\forall d^k\in D^k$ (11)

$h_{i{d}^k}^{k,L}+{\displaystyle \underset{m\in C^D}{\sum }{x}_{mi{d}^k}^k}=h_{i{d}^k}^{k,R}+{\displaystyle \underset{l\in C^D}{\sum }{x}_{il{d}^k}^k},\forall i\in V,\forall k\in K,\forall d^k\in D^k$ (12)

${\displaystyle \underset{k\in K}{\sum }\left({\displaystyle \underset{d^k\in D^k}{\sum }{x}_{ij{d}^k}^k}+{\displaystyle \underset{d^k\in D^k}{\sum }{x}_{ji{d}^k}^k}\right)}\le 1,\forall \left(i,j\right)\in E$ (13)

$h_{i{d}^k}^{{}^{k,L}}\ge 1-M\times \left(2-x_{ij{d}^k}^k-z_{j{d}^k}^{k,D}+z_{i{d}^k}^{k,D}\right),\forall i\in V\backslash \left\{c+1\right\},\forall j\in \left\{C^D:i\ne j\right\},\forall k\in K,\forall d^k\in D^k$ (14)

$h_{j{d}^k}^{k,R}\ge 1-M\times \left(2-x_{ij{d}^k}^k-z_{i{d}^k}^{k,D}+z_{j{d}^k}^{k,D}\right),\forall i\in C^D,\forall j\in \left\{V\backslash \left\{0\right\}:i\ne j\right\},\forall k\in K,\forall d^k\in D^k$ (15)

${\displaystyle \underset{i\in V\backslash \left\{c+1\right\}}{\sum }{h}_{i{d}^k}^{k,L}}={\displaystyle \underset{j\in V\backslash \left\{0\right\}}{\sum }{h}_{j{d}^k}^{k,R}}\le 1,\forall k\in K,\forall d^k\in D^k$ (16)

${\displaystyle \underset{l\in C^D}{\sum }{\displaystyle \underset{d^k\in D^k}{\sum }\left(h_{i{d}^k}^{k,L}+x_{lj{d}^k}^k\right)}}={\displaystyle \underset{m\in C^D}{\sum }{\displaystyle \underset{d^k\in D^k}{\sum }\left(h_{j{d}^k}^{k,R}+x_{im{d}^k}^k\right)}},\forall i\in V\backslash \left\{c+1\right\},\forall j\in V\backslash \left\{0\right\},\forall k\in K$ (17)

$h_{i{d}^k}^{k,L}+h_{i{d}^k}^{k,R}\le 1,\forall i\in V,\forall k\in K,\forall d^k\in D^k$ (18)

$h_{i{d}^k}^{k,L}\ge 1-M\times \left(3-y_{ij}^k-x_{il{d}^k}^k-z_{l{d}^k}^{k,D}\right),\forall \left(i,j\right)\in E,\forall l\in C^D,\forall k\in K,\forall d^k\in D^k$ (19)

$h_{i{d}^k}^{k,R}\ge 1-M\times \left(3-y_{ji}^k-x_{li{d}^k}^k-z_{l{d}^k}^{k,D}\right),\forall \left(j,i\right)\in E,\forall l\in C^D,\forall k\in K,\forall d^k\in D^k$ (20)

${\displaystyle \underset{j\in V}{\sum }{y}_{ij}^k}={\displaystyle \underset{l\in V}{\sum }{y}_{li}^k}\le 1,\forall i\in V,\forall k\in K$ (21)

${\displaystyle \underset{j\in C}{\sum }{y}_{0j}^k}\le 1,\forall k\in K$ (22)

${\displaystyle \underset{i\in C}{\sum }{y}_{i,c+1}^k}\le 1,\forall k\in K$ (23)

$y_{0,c+1}^k=0,\forall k\in K$ (24)

${\displaystyle \underset{l\in V\backslash \left\{0\right\}}{\sum }{y}_{0l}^k}\ge y_{ij}^k,\forall \left(j,i\right)\in E,\forall k\in K$ (25)

${\displaystyle \underset{i\in C}{\sum }{x}_{0i{d}^k}^k}+{\displaystyle \underset{i\in C}{\sum }{x}_{i,c+1,d^k}^k}\le 1,\forall k\in K,\forall d^k\in D^k$ (26)

${\displaystyle \underset{i\in C}{\sum }{q}_i{z}_{i{d}^k}^{k,D}}\le Q^D,\forall k\in K,\forall d^k\in D^k$ (27)

$R{W}^D+{\displaystyle \underset{i\in C}{\sum }{q}_i}{z}_i^k+{\displaystyle \underset{i\in C}{\sum }{\displaystyle \underset{d^k\in D^k}{\sum }{q}_i{z}_{i{d}^k}^{k,D}}}\le Q^T,\forall k\in K$ (28)

$d_0+{\displaystyle \underset{j\in C}{\sum }{\displaystyle \underset{d^k\in D^k}{\sum }{x}_{0j{d}^k}^k}}=R,\forall k\in K$ (29)

$d_i+{\displaystyle \underset{l\in V\backslash \left\{c+1\right\}}{\sum }{\displaystyle \underset{d^k\in D^k}{\sum }{x}_{lj{d}^k}^k}}\ge d_j+{\displaystyle \underset{m\in V\backslash \left\{0\right\}}{\sum }{\displaystyle \underset{d^k\in D^k}{\sum }{x}_{jm{d}^k}^k}}-M\times \left(1-y_{ij}^k\right),\forall k\in K,\forall \left(i,j\right)\in E$ (30)

$d_i+{\displaystyle \underset{j\in C}{\sum }{\displaystyle \underset{d^k\in D^k}{\sum }{x}_{j,c+1,d^k}^k}}\ge R-M\times \left(1-y_{i,c+1}^k\right),\forall k\in K,\forall i\in C$ (31)

$t_{i{d}^k}^{k,D}-r_{j{d}^k}^{k,D}\le \epsilon +M\times \left(3-y_{ji}^k-x_{jl{d}^k}^k-x_{mi{d}^k}^k\right),\forall \left(i,j\right)\in E,\forall l\in C^D,\forall m\in C^D,\forall k\in K,\forall d^k\in D^k$ (32)

$t_{j{d}^k}^{k,D}\ge r_{i{d}^k}^{k,D}+{\tau }_{ij}^D-M\times \left(1-{\displaystyle \underset{d^k\in D^k}{\sum }{x}_{ij{d}^k}^k}\right),\forall \left(i,j\right)\in E,\forall k\in K$ (33)

$r_{i{d}^k}^{k,D}\ge t_{i{d}^k}^{k,D}+{\omega }_{i{d}^k}^D-M\times \left(1-{\displaystyle \underset{d^k\in D^k}{\sum }{z}_{i{d}^k}^{k,D}}\right),\forall i\in C,\forall k\in K$ (34)

$t_i^{k,T}\ge r_j^{k,T}+{\tau }_{ij}^T-M\times \left(1-y_{ji}^k\right),\forall \left(i,j\right)\in E,\forall k\in K$ (35)

$r_i^{k,T}\ge t_i^{k,T}+s_i+{\omega }_i^{k,T}-M\times \left(1-z_i^{k,T}\right),\forall i\in C,\forall k\in K$ (36)

$r_i^{k,T}\ge t_{i{d}^k}^{k,D}-M\times \left(1-z_i^{k,T}\right),\forall i\in C,\forall k\in K,\forall d^k\in D^k$ (37)

$r_{i{d}^k}^{k,D}\ge r_i^{k,T}-M\times \left(1-h_{i{d}^k}^{k,L}\right),\forall i\in C,\forall k\in K,\forall d^k\in D^k$ (38)

$r_{i{d}^k}^{k,D}\le r_i^{k,T}-M\times \left(1-h_{i{d}^k}^{k,L}\right),\forall i\in C,\forall k\in K,\forall d^k\in D^k$ (39)

${\omega }_i^{k,T}=\max \left\{0,a_i-t_i^{k,T},t_{i{d}^k}^{k,D}-t_i^{k,T}\right\},\forall i\in C,\forall k\in K,\forall d^k\in D^k$ (40)

${\omega }_{i{d}^k}^{k,D}=\max \left\{0,a_i-t_{i{d}^k}^{k,D},t_i^{k,T}-t_{i{d}^k}^{k,D}\right\},\forall i\in C,\forall k\in K,\forall d^k\in D^k$ (41)

约束(6)和(7)确保每个客户点恰好被服务一次；约束(8)确保由无人机服务的客户都有相应的无人机行程访问；约束(9)确保由卡车 $k\in K$ 访问的每个客户都直接由卡车 $k\in K$ 服务；约束(10)和(11)确保每个客户节点被无人机访问最多一次；约束(12)平衡无人机行程访问的所有节点；约束(13)确保每条边被无人机最多访问一次；约束(14)、(15)确保每个无人机行程至少服务于每一个客户，防止无人机沿着卡车路径飞行；约束(16)确保无人机行程只有一个发射点和一个回收点；约束(17)确保同一发射点发射的无人机在另一相同点取回；约束(18)确保同一无人机行程发射点和回收点不同；在卡车 $k\in K$ 的路径中，无人机发射节点和汇合节点由约束(19)和(20)确定；约束(21)平衡节点的卡车流；约束(22)确保每辆车离开仓库最多一次；约束(23)确保每辆车返回仓库最多一次；约束(24)禁止卡车从仓库直接到仓库；约束(25)确保每辆卡车只能在离开仓库后使用；约束(26)禁止无人机独立完成任务；约束(27)确保无人机飞行期间不能超过其负载能力；约束(28)确保卡车不超过其负载能力。

由于无人机是同质的，只跟踪整个物流过程中的无人机数量。约束(29)确保每辆卡车携带的无人机总数目为R；约束(30)确保离开j点时无人机数量不能超过在j点的无人机数目；约束(31)确保最终每辆车的无人机数目。约束(32)确保无人机飞行不能超过其飞行耐力；约束(33)捕获无人机在节点处的到达时间；约束(34)限制无人机从节点i的离开时间；约束(35)捕获卡车在节点i处到达时间；约束(36)、(37)规定卡车从节点i的出发时间；约束(38)、(39)规定卡车与无人机同时离开节点的时间；约束(40)代表卡车可能的等待时间；约束(41)代表无人机可能的等待时间。

3. 求解MO-MTMDCRP-TW模型的MOEA/D-OSD算法

基于分解的多目标演化算法(Multi-Objective Evolutionary Algorithm Based on Decomposition, MOEA/D) [15]是比较流行的多目标演化算法。该算法将多目标优化问题分解为多个标量优化子问题，并利用子问题之间的邻域关系，协作优化所有子问题，进而有效逼近Pareto前沿。为了使MOEA/D算法适合MO-MTMDCRP-TW模型，本研究提出一种基于目标空间分解的改进的MOEA/D算法(An Improved MOEA/D Algorithm Based on Objective Space Decomposition, MOEA/D-OSD)，该算法对经典的MOEA/D算法进行了多个改进：

1) 提出了适合卡车无人机协同配送问题的染色体解码、编码方式，以保证进化过程中产生可行的高质量解；

2) 集成目标空间分解策略、交配亲本选择策略、子种群更新策略等多个策略提高种群多样性；

3) 集成多个交叉变异算子以加速算法收敛。

MOEA/D-OSD算法的框架如图2所示。

3.1. MOEA/D-OSD框架

初始阶段通过对目标空间中均匀分布的权向量进行聚类，将目标空间分解为若干个子空间[16] [17]。初始化过程使用Das和Dennis的系统方法[18]来生成权重向量集 $W=\left\{w^1,w^2\cdots ,w^N\right\}$ ，W的大小是 $N=C_{H+M-1}^{M-1}$ ，其中 $H>0$ 是每个目标坐标的分割数，N是生成的权重向量的数量，M是目标数。然后使用K均值聚类算法[19]将权重向量划分为K个聚类的集合，表示为 $C{W}^1,C{W}^2,\cdots ,C{W}^K$ 。由于权重向量在目标空间中均匀分布，每个簇中的权重向量数量近似为 $\lfloor \frac{N}{K}\rfloor$ 。在此之后，可以获得一组中心聚类向量 $C=\left\{c^1,c^2,\cdots ,c^K\right\}$ ，每个中心聚类都与一个子空间 ${\Omega }_i$ 相关联，其中 ${\Omega }_i=\left\{v\in R_{+}^M|\langle v,c^i\rangle \le \langle v,c^j\rangle ,i,j\in 1,\cdots ,K\right\}$ ， $\langle v,c^i\rangle$ 是v和 $c^i$ 之间的锐角， $R_{+}^M$ 是包括所有目标向量的M维目标空间，v是归一化目标向量。初次分解目标空间后，在各子空间中利用切比雪夫聚合函数为每个子

Figure 2. MOEA/D-OSD flowchart

图2. MOEA/D-OSD流程图

问题分配权重向量。值得注意的是：1) 在初次将解决方案分配到其相关联的子空间时，许多解的目标向量可能与相同的单位向量具有相同的最小角度，导致子空间相关联的解的数目可能超过 $\lfloor \frac{N}{K}\rfloor$ ；2) 原MOEA/D算法中进化前期子问题和解的匹配具有随机性，匹配度较差。为解决以上两个问题，在初始进化阶段使用稳定匹配[20]，将每个子空间中的解与该子空间中各个子问题相匹配，保证各子空间中解的数量与该子空间中权重向量数量相等的同时又为每个子问题选择较合适的解。

进化阶段，各子空间的子种群进化相对独立，且在每个子空间中，对多个子问题同时进行选择、交叉和变异操作，从而生成对应的新解。在选择操作中，各子问题以较低的概率 $1-\alpha$ 选择PF中的部分稀疏解作为交配亲本，以较高的概率 $\alpha$ 选择对应子问题的邻域解作为该子问题的交配亲本；在交叉和变异操作中，随机使用多种交叉算子和变异算子。

新解分配阶段，将各个子空间产生的新解分配到相应子空间。

子种群更新阶段，选择稳定匹配策略作为子种群更新策略，保持每个子空间所关联解的数量不变的同时平衡收敛性与多样性。表2为MOEA/D-OSD算法的伪代码。

3.2. 交配亲本选择

每个子问题的父代种群选取方法与[21]类似，首先在整个种群的PF中使用拥挤距离，计算PF中非支配解的适应值，再用二元锦标赛方法从这些非支配解中选出q个稀疏解。各子问题以较低的概率 $1-\alpha$ 从稀疏解集中选择交配亲本，以较高的概率 $\alpha$ 从该子问题的邻域解中选择交配亲本后进行遗传操作，生成对应于该子问题的新解。这种父代种群选择策略有利于局部搜索与全局搜索相结合，以较低的概率从稀疏解集中选择交配亲本，有助于保持全局多样性，防止子种群陷入局部最优。

Table 2. Pseudo-code of the MOEA/D-OSD algorithm

表2. MOEA/D-OSD算法的伪代码

算法1. MOEA/D-OSD框架

输入：所有节点V，种群大小N，最大迭代次数iter，邻域大小T，子空间数目K

输出：近似帕累托前沿PF

1 初始化： $gen\leftarrow 1$

2 生成N个均匀分布的权重向量 $w^1,w^2,\cdots ,w^N$

3利用K均值聚类法将权重向量划分成K个聚类的集合

4 通过算法2生成N个初始解，并进行解码得到具体解决方案，计算目标函数

5 更新PF

6 使用二元锦标赛算法选择PF的q个稀疏解，构成解集Q

7 将初始种群中的解分配到不同的子空间 ${\Omega }_k$ 中得到子种群 $P_k$ ， $k=1,2,\cdots ,K$

8 使用稳定匹配算法将各子空间中的解与子问题一一对应

9 While $gen\le iter$ do:

10 $gen\leftarrow gen+1$

11 K个子种群协同并行进化：

12 ${\Omega }_k$ 中各子问题以概率 $\alpha$ 从其邻域中选择交配亲本，以 $1-\alpha$ 从Q中选择交配亲本进行遗传操作

13 子空间中新生成的个体重新分组分配到不同的子空间 ${\Omega }_1,{\Omega }_2,\cdots ,{\Omega }_K$

14 各子空间利用稳定匹配算法选择出个体以形成新的 $P_k$

15 更新PF

16 更新Q

17 end

3.3. 子种群更新策略

与MOEA/D、NSGA-III算法[22]不同，MOEA/D-OSD在考虑进行解的替换时，不仅考虑所得到的解的收敛性还要考虑解在目标空间中的分布。每个子种群在选择下一代子种群时1) 对于子空间中的子问题，计算所有解到该子问题的切比雪夫聚合函数值，每个子问题通过聚合函数值排名所有解，子问题倾向于具有更好的聚合函数值的解。2) 每个解根据其到这些子问题方向向量的距离对所有子问题进行排名，解偏爱方向向量接近该解的子问题。各子种群选择下一代子种群时使用该稳定匹配[19]策略，有利于平衡各子空间解的多样性和收敛性，进而有利于解在目标空间中的多样性分布。

3.4. 初始种群

染色体编码是算法流程中至关重要的一步，编码的优劣会影响优化问题的解决速率。因此应合理设计染色体编码策略。

卡车无人机协同配送问题涉及卡车和无人机两种类型的路线，解决方案较为复杂。为此，本文采用包含所有客户节点的巨型路径编码来表示该问题的一个解决方案。巨型路径编码的使用简化了遗传操作的实现。

本文构造初始解以及解码的方法，类似于[23]，如在表3中，初始解构造方法即所有客户的随机排列。在随机排列中，第一个节点和最后一个节点是相同的仓库，而其他节点是所有客户点随机序列，以提高初始种群的多样性得到巨型路径编码。然后，基于巨型路径编码进行解码，采用卡车路线分割算法[24]将巨型路线转换为卡车路线。然后，对每条卡车路线，利用无人机路线构建算法以及每条路径的无人机路线，用无人机路线修改该卡车路线得到修改后的卡车路线。使用这种方法的好处是卡车路线分割构建算法和无人机路线构建算法的执行结果是确定性的，所以一个巨型路径可以唯一地表示一种解决方案。

在解码过程中，以图3为例，一个染色体中包含多辆卡车和多架无人机的组合路线。对染色体[0, 11, 12, 6, 8, 2, 10, 5, 3, 9, 1, 4, 7, 0]采用卡车路径分割算法，将巨型路线转换为多条卡车路径，第一辆卡车路径[0, 11, 12, 6, 8, 2, 10, 0]，第2条卡车路径[0, 5, 3, 9, 1, 4, 7, 0]，搜索每条卡车路径上的无人机路径，得到第一辆卡车路径中的无人机[11, 6, 12]，[8, 10, 2]路线，得到第二辆卡车路径中的无人机[0, 3, 5]，[5, 1, 4, 9]路线，其中每个无人机路径包括发射节点、客户节点和取回节点。根据无人机路径，修改卡车路径编码，在第一条卡车路径中因为客户点6、10被分配给无人机服务，所以最终第一条卡车路径被修改为[0, 11, 12, 8, 2, 0]，在第二条卡车路径中因为客户点3、1、4被分配给无人机服务，所以最终第二条卡车路径被修改为[0, 5, 9, 7, 0]。由无人机路线和修改的卡车路线得到一个具体的解决方案，一个染色体与一个具体的解决方案对应。

本文采用[13]提出的无人机构建算法，以构建具有最多航班的可行无人机航线。

Table 3. Encoding and decoding pseudocode

表3. 编码解码伪代码

算法2. 编码解码过程

输入：所有节点V

输出：无人机行程 $D^k$ ，修改后的卡车路线 $T^k$ ， $k=1,2,\cdots$

1 客户点随机进行排列，构建巨型路径编码

2 利用卡车路径分割算法将巨型路径分割成多条卡车路径

3 对于每条卡车路径 $G^k$ 执行：

4 初始化：无人机行程 $D^k\leftarrow \varnothing$

5 设置l为1

6 当 $l\le \left|G^k\right|-1$ 时:

7 设置r为 $l+1$

8 对于i从1到 $\left|G^k\right|$

9 如果 $\left(g_l,g_i,g_r\right)$ 可行，则：

10 如果 $Cos{t}_D\left(g_l,g_i,g_r\right)<Cos{t}_T\left(g_l,g_i,g_r\right)$ 则：

11 如果 $g_i$ 可以被插入到以 $g_l$ 为发射点的现有行程中则：

12 将 $g_i$ 插入到以 $g_l$ 为发射点的现有行程中

13 否则如果此时使用的无人机数小于R则：

14 将 $\left(g_l,g_i,g_r\right)$ 作为以 $g_l$ 为发射点的新行程加入 $D^k$

15 从 $G^k$ 中删除无人机服务的客户

16 设置 $l$ 为 $l+1$

Figure 3. Encoding and decoding illustration of the solution

图3. 解决方案的编码和解码示意图

3.5. 遗传算子

3.5.1. 交叉算子

为了加快算法收敛速度，在MOEA/D-OSD的交叉操作中随机使用部分匹配交叉(PMX)算子和顺序交叉(OX)算子[25]。图4(a)显示了部分匹配交叉算子的操作示例，首先随机选择父代巨型路线上的几个相邻客户点，称为交叉段，交叉段之间建立映射关系。PMX运算符是将父代巨型路线1上的交叉段替换为父代巨型路线2上的交叉段以创建新的巨型路线，再使用交叉段之间的匹配关系来消除新巨型路线上的重复客户。图4(b)显示了OX算子的操作示例，OX算子是为了保留父代旧巨型路线1上的交叉段以创建新的巨型路线。然后，除了新巨型路线上的重复客户之外，新巨型路线的其余部分按照父代旧巨型路线2上的客户顺序填充。

(a) 部分匹配交叉(PMX)算子 (b) 顺序交叉(OX)算子

Figure 4. Crossover operation illustration

图4. 交叉操作示意图

3.5.2. 变异算子

本文采用与[23]相同的互换变异算子，卡车路径重定位算子以及反向变异算子随机使用的突变操作。互换变异算子的思想就是交换路径上的两个客户，如图5(a)所示，交换巨型路径上的客户点3和5得到新路径。卡车路径重定位的思想(如图5(b)所示)是选取路径中最昂贵客户点位置，将它插入最便宜客户点的位置。通过计算客户点前后的路径长度找到最昂贵客户点的位置，将它移除，再重新插入到最便宜客户点的位置。反向变异算子(如图5(c)所示)用于对一条巨型路线上的多个相邻顾客进行反向操作。

(a) 互换变异算子

(b) 卡车路径重定位算子

(c) 反向突变算子

Figure 5. Mutation operation illustration

图5. 变异操作示意图

4. 数值实验

4.1. 性能度量

由于真实的Pareto前沿是未知。因此本文使用超体积(HV)和覆盖率(C度量)来评估算法的性能[26]。

超体积(HV)是测量算法多样性和收敛性的一个指标，表示解集和参考点之间的体积。

覆盖度量是一种比较两组非支配解质量的指标。C (A, B)表示B中的解被A中的任何解支配的百分比。

4.2. 基准实验

在评估所提出的算法之前，本文扩展了大仲马等人提出的TSPTW实例。从中提取出20个实例，客户节点数分别为20、40、80、100。为了模拟并非所有包裹都可以通过无人机交付的真实情况，在这些实例中，可以由无人机服务的客户百分比均为70%。每个大小的实例由5个数据集组成。所使用的实例信息是与客户节点i相关联的时间窗口的坐标、需求量、最早开始时间 $a_i$ 和最晚结束时间 $b_i$ 。由于原始实例要求所有客户节点必须在最早开始时间和最晚结束时间之间得到服务，因此为每个节点i生成一个灵活的时间窗口 $\left[m_i,n_i\right]$ ，以获得本文模型所需要相关的实例，其中 $m_i=a_i-\omega b_i^l\left(b_i-a_i\right)$ 和 $n_i=a_i+\omega b_i^u\left(b_i-a_i\right)$ 。特别地， $\omega b_i^l$ 和 $\omega b_i^u$ 是用于设置时间窗口的最大允许违反的两个分数。

设置卡车最大装载能力为200千克，参考[27]设置无人机最大载重为30千克，参考[28]设置卡车速度为60千米每小时，无人机速度为65千米每小时，参考[4]设置卡车的成本为无人机成本的25倍，卡车在每个客户点的服务时间为10分钟。为了设置无人机的飞行范围，本文使用[29]中介绍的方法，并假设无人机在每个实例中可以满足85%的可行飞行。

实验设置：为了评估MOEA/D-OSD算法解决MO-MTMDCRP-TW模型的性能，需将其与一些多目标演化算法进行比较。由于MO-MTMDCRP-TW的复杂性，没有现有的精确方法可以直接求解，需要使用本文的编码和解码方法以及多个交叉和突变运算符扩展三个具有代表性的多目标演化算法(MOEA/D [15], NSGA-II [30], MOEA/D-M2M [16])，将扩展后的三个算法与MOEA/D-OSD算法进行比较。在表4中设置了实验的参数。所有算法都是用Matlab编码的，实验在具有Windows 11系统、1.90 GHz 13th Gen Intel(R) Core(TM) i5-1340P和16 GB RAM的个人计算机上进行。

Table 4. Experimental parameter settings

表4. 实验参数设置

算法	MOEA/D-OSD	MOEA/D-M2M	MOEA/D	NSGA-II
N	200	200	200	200
K	3	3	—	—
T	8	—	16	—
iter	20	20	20	20
$\omega b_i^l$	0.2	0.2	0.2	0.2
$\omega b_i^u$	0.2	0.2	0.2	0.2
R	3	3	3	3
$\alpha$	0.8	0.8	0.8	0.8
$\beta$	0.1%	0.1%	0.1%	0.1%
h	0.2%	0.2%	0.2%	0.2%
H	1	1	1	1
交叉率	0.8	0.8	0.8	0.8
变异率	0.3	0.3	0.3	0.3
q	50	—	—	—

实验结果：对上述描述的20个实例进行了四种算法的独立运行，每个实例重复20次。1) 由于目标的取值范围不同，必须对其进行归一化。2) 每个实例的名称表示节点数量和组别(例如，n20-01表示有20个客户节点的第一组实例)。对于每个实例，表5、表6中最佳结果以黑体显示。

表5显示了HV的平均值以及标准偏差。由表5可以看出MOEA/D-OSD在除实例n80-02外的所有实例上生成的平均HV值均高于NSGA-II、MOEA/D和MOEA/D-M2M，说明MOEA/D-OSD算法在解决卡车无人机路径问题上可以获得高质量的解，并且比其他三种算法具有更好的多样性和收敛性。

Table 5. Comparison of HV for four algorithms

表5. 四种算法的HV对比

基准实例	MOEA/D-OSD		NSGA-II		MOEA/D		MOEA/D-M2M
	HV		HV		HV		HV
	Avg	Std.dev	Avg	Std.dev	Avg	Std.dev	Avg	Std.dev
n20-01	0.710	0.055	0.554	0.102	0.583	0.068	0.562	0.067
n20-02	0.768	0.053	0.654	0.073	0.645	0.067	0.677	0.080
n20-03	0.747	0.051	0.671	0.105	0.690	0.076	0.695	0.060
n20-04	0.742	0.032	0.646	0.096	0.606	0.076	0.650	0.075
n20-05	0.744	0.056	0.674	0.073	0.668	0.080	0.675	0.050
n40-01	0.728	0.044	0.607	0.090	0.587	0.111	0.647	0.064
n40-02	0.721	0.053	0.648	0.093	0.658	0.090	0.678	0.084
n40-03	0.685	0.057	0.645	0.79	0.675	0.097	0.608	0.080
n40-04	0.692	0.049	0.567	0.119	0.611	0.097	0.644	0.102
n40-05	0.733	0.028	0.653	0.092	0.636	0.079	0.629	0.072
n80-01	0.711	0.062	0.633	0.095	0.644	0.072	0.593	0.095
n80-02	0.606	0.057	0.595	0.079	0.623	0.094	0.636	0.090
n80-03	0.780	0.050	0.626	0.088	0.619	0.883	0.602	0.105
n80-04	0.702	0.042	0.567	0.091	0.595	0.095	0.589	0.066
n80-05	0.713	0.046	0.633	0.099	0.634	0.080	0.644	0.079
n100-01	0.717	0.039	0.576	0.113	0.612	0.145	0.602	0.096
n100-02	0.712	0.033	0.602	0.086	0.585	0.110	0.664	0.055
n100-03	0.701	0.053	0.640	0.070	0.615	0.103	0.622	0.084
n100-04	0.721	0.039	0.626	0.069	0.613	0.088	0.608	0.052
n100-05	0.721	0.044	0.611	0.077	0.607	0.145	0.626	0.084

每个实例的平均C度量值见表6。可以发现，除实例n40-05的C (MOEA/D-OSD, NSGA-II)值略小于C (NSGA-II, MOEA/D-OSD)值以及n80-04、n100-04的C (MOEA/D-OSD, MOEA/D-M2M)值略小于C (MOEA/D-M2M, MOEA/D-OSD)值外，与其他所有实例相比，C (MOEA/D-OSD, -)值均大于C (-, MOEA/D-OSD)值。这进一步表明，MOEA/D-OSD在解决卡车无人机协同路径问题上优于其他三个比较算法。特别地，大多数C (MOEA/D-OSD, MOEA/D)值非常接近1，这表明通过MOEA/D获得的大多数解由MOEA/D-OSD的至少一个解支配。另一方面，大多数C (MOEA/D, MOEA/D-OSD)值比较接近0，这意味着MOEA/D-OSD的极少数解被MOEA/D的解所支配。尽管在除n40-05外的所有实例中，C (MOEA/D-OSD, NSGA-II)值均大于C (NSGA-II, MOEA/D-OSD)值，在除n80-04、n100-04外的所有实例中，C (MOEA/D-OSD, MOEA/D-M2M)值均大于C (MOEA/D-M2M, MOEA/D-OSD)值，但在少数情况下C (MOEA/D-OSD, NSGA-II)值与C (NSGA-II, MOEA/D-OSD)相差很小(例如n100-05)，C (MOEA/D-OSD, MOEA/D-M2M)值与C (MOEA/D-M2M, MOEA/D-OSD)相差很小(例如n80-05)，这表明在某些情况下它们的Pareto前沿覆盖率是相似的。

Table 6. Comparison of coverage rate between MOEA/D-OSD and other algorithms

表6. MOEA/D-OSD与其他算法在覆盖率上的比较

基准实例	C (MOEA/D-OSD, -)			C (-, MOEA/D-OSD)
	NSGA-II	MOEA/D	MOEA/D-M2M	NSGA-II	MOEA/D	MOEA/D-M2M
n20-01	0.636	0.962	0.625	0.468	0.086	0.494
n20-02	0.682	0.951	0.644	0.446	0.076	0.545
n20-03	0.743	0.963	0.691	0.420	0.093	0.515
n20-04	0.630	0.970	0.701	0.464	0.068	0.435
n20-05	0.590	0.960	0.984	0.740	0.146	0.149
n40-01	0.711	0.952	0.603	0.352	0.097	0.563
n40-02	0.671	0.993	0.895	0.355	0.001	0.106
n40-03	0.629	0.970	0.638	0.374	0.058	0.451
n40-04	0.689	0.963	0.616	0.330	0.044	0.470
n40-05	0.471	0.977	0.598	0.472	0.032	0.492
n80-01	0.617	0.948	0.591	0.482	0.160	0.519
n80-02	0.524	0.947	0.590	0.517	0.049	0.438
n80-03	0.627	0.962	0.568	0.412	0.048	0.438
n80-04	0.620	0.934	0.470	0.361	0.075	0.559
n80-05	0.631	0.901	0.611	0.521	0.199	0.590
n100-01	0.832	0.990	0.861	0.781	0.381	0.814
n100-02	0.825	0.990	0.795	0.739	0.334	0.743
n100-03	0.843	0.962	0.857	0.772	0.393	0.787
n100-04	0.889	0.996	0.804	0.520	0.323	0.807
n100-05	0.784	0.983	0.845	0.739	0.358	0.750

5. 结论

本文基于路径优化的思想，探讨了柔性时间窗下的多卡车多无人机协同配送路径问题。以现有的卡车无人机协同配送模型为基础，综合考虑配送成本、客户总体不满意度，设计了适合多卡车多无人机协同配送问题的数学模型，并提出基于目标空间分解的改进MOEA/D算法(MOEA/D-OSD)来对模型进行求解。经过仿真检验了改进算法的可行性，为求解多卡车多无人机协同配送路径优化问题进行了有益探索。

本文提出的MOEA/D-OSD算法在获得高质量的非支配解方面表现出色，能够有效解决卡车无人机协同配送问题。未来可以将Pareto局部搜索算法与MOEA/D-OSD算法结合，探索是否可以提高多目标优化算法在处理复杂问题时的效率和性能。此外，模型中还可以考虑碳排放、限飞区域等因素，以更好地适应现实世界场景。

参考文献

[1]	Chung, S.H., Sah, B. and Lee, J. (2020) Optimization for Drone and Drone-Truck Combined Operations: A Review of the State of the Art and Future Directions. Computers & Operations Research, 123, Article 105004. https://doi.org/10.1016/j.cor.2020.105004
[2]	Murray, C.C. and Chu, A.G. (2015) The Flying Sidekick Traveling Salesman Problem: Optimization of Drone-Assisted Parcel Delivery. Transportation Research Part C: Emerging Technologies, 54, 86-109. https://doi.org/10.1016/j.trc.2015.03.005
[3]	Agatz, N., Bouman, P. and Schmidt, M. (2018) Optimization Approaches for the Traveling Salesman Problem with Drone. Transportation Science, 52, 965-981. https://doi.org/10.1287/trsc.2017.0791
[4]	Ha, Q.M., Deville, Y., Pham, Q.D. and Hà, M.H. (2018) On the Min-Cost Traveling Salesman Problem with Drone. Transportation Research Part C: Emerging Technologies, 86, 597-621. https://doi.org/10.1016/j.trc.2017.11.015
[5]	Luo, Z., Liu, Z. and Shi, J. (2017) A Two-Echelon Cooperated Routing Problem for a Ground Vehicle and Its Carried Unmanned Aerial Vehicle. Sensors, 17, Article 1144. https://doi.org/10.3390/s17051144
[6]	Mbiadou Saleu, R.G., Deroussi, L., Feillet, D., Grangeon, N. and Quilliot, A. (2018) An Iterative Two-Step Heuristic for the Parallel Drone Scheduling Traveling Salesman Problem. Networks, 72, 459-474. https://doi.org/10.1002/net.21846
[7]	Chen, P. and Wang, Q. (2024) Learning for Multiple Purposes: A Q-Learning Enhanced Hybrid Metaheuristic for Parallel Drone Scheduling Traveling Salesman Problem. Computers & Industrial Engineering, 187, Article 109851. https://doi.org/10.1016/j.cie.2023.109851
[8]	Teimoury, E. and Rashid, R. (2023) The Paired Pickup and Delivery Problem with Profit in a Two-Echelon Delivery System with Multiple Trucks and Drones. Transportation Letters, 16, 1171-1187. https://doi.org/10.1080/19427867.2023.2278855
[9]	Ham, A.M. (2018) Integrated Scheduling of M-Truck, M-Drone, and M-Depot Constrained by Time-Window, Drop-Pickup, and M-Visit Using Constraint Programming. Transportation Research Part C: Emerging Technologies, 91, 1-14. https://doi.org/10.1016/j.trc.2018.03.025
[10]	Lin, M., Lyu, J., Gao, J. and Li, L. (2020) Model and Hybrid Algorithm of Collaborative Distribution System with Multiple Drones and a Truck. Scientific Programming, 2020, 1-16. https://doi.org/10.1155/2020/8887057
[11]	Wang, K., Yuan, B., Zhao, M. and Lu, Y. (2019) Cooperative Route Planning for the Drone and Truck in Delivery Services: A Bi-Objective Optimisation Approach. Journal of the Operational Research Society, 71, 1657-1674. https://doi.org/10.1080/01605682.2019.1621671
[12]	Luo, Q., Wu, G., Ji, B., Wang, L. and Suganthan, P.N. (2022) Hybrid Multi-Objective Optimization Approach with Pareto Local Search for Collaborative Truck-Drone Routing Problems Considering Flexible Time Windows. IEEE Transactions on Intelligent Transportation Systems, 23, 13011-13025. https://doi.org/10.1109/tits.2021.3119080
[13]	Luo, Q., Wu, G., Trivedi, A., Hong, F., Wang, L. and Srinivasan, D. (2023) Multi-Objective Optimization Algorithm with Adaptive Resource Allocation for Truck-Drone Collaborative Delivery and Pick-Up Services. IEEE Transactions on Intelligent Transportation Systems, 24, 9642-9657. https://doi.org/10.1109/tits.2023.3267103
[14]	曹庆奎, 张雪飞, 任向阳. 货车和无人机联合配送路径优化研究[J]. 廊坊师范学院学报(自然科学版), 2022, 22(1): 5-13.
[15]	Zhang, Q.F. and Li, H. (2007) MOEA/D: A Multi-Objective Evolutionary Algorithm Based on Decomposition. IEEE Transactions on Evolutionary Computation, 11, 712-731.
[16]	Liu, H., Gu, F. and Zhang, Q. (2014) Decomposition of a Multiobjective Optimization Problem into a Number of Simple Multiobjective Subproblems. IEEE Transactions on Evolutionary Computation, 18, 450-455. https://doi.org/10.1109/tevc.2013.2281533
[17]	Bi, X. and Wang, C. (2016) An Improved NSGA-III Algorithm Based on Objective Space Decomposition for Many-Objective Optimization. Soft Computing, 21, 4269-4296. https://doi.org/10.1007/s00500-016-2192-0
[18]	Das, I. and Dennis, J.E. (1998) Normal-Boundary Intersection: A New Method for Generating the Pareto Surface in Nonlinear Multicriteria Optimization Problems. SIAM Journal on Optimization, 8, 631-657. https://doi.org/10.1137/s1052623496307510
[19]	Hartigan, J.A. and Wong, M.A. (1979) Algorithm as 136: A K-Means Clustering Algorithm. Applied Statistics, 28, 100-108. https://doi.org/10.2307/2346830
[20]	Li, K., Hang, Q.F., Kwong, S., et al. (2014) Stable Matching-Based Selection in Evolutionary Multi-Objective Optimization. IEEE Transactions on Evolutionary Computation, 18, 909-923.
[21]	Dong, N. and Dai, C. (2019) An Improvement Decomposition-Based Multi-Objective Evolutionary Algorithm Using Multi-Search Strategy. Knowledge-Based Systems, 163, 572-580. https://doi.org/10.1016/j.knosys.2018.09.018
[22]	Yuan, Y., Xu, H. and Wang, B. (2014) An Improved NSGA-III Procedure for Evolutionary Many-Objective Optimization. Proceedings of the 2014 Annual Conference on Genetic and Evolutionary Computation, Vancouver, 12-16 July 2014, 661-668. https://doi.org/10.1145/2576768.2598342
[23]	Zhang, S., Liu, S., Xu, W. and Wang, W. (2022) A Novel Multi-Objective Optimization Model for the Vehicle Routing Problem with Drone Delivery and Dynamic Flight Endurance. Computers & Industrial Engineering, 173, Article 108679. https://doi.org/10.1016/j.cie.2022.108679
[24]	Cordeau, J., Laporte, G. and Mercier, A. (2001) A Unified Tabu Search Heuristic for Vehicle Routing Problems with Time Windows. Journal of the Operational Research Society, 52, 928-936. https://doi.org/10.1057/palgrave.jors.2601163
[25]	Potvin, J. (1996) Genetic Algorithms for the Traveling Salesman Problem. Annals of Operations Research, 63, 337-370. https://doi.org/10.1007/bf02125403
[26]	Zitzler, E. and Thiele, L. (1999) Multiobjective Evolutionary Algorithms: A Comparative Case Study and the Strength Pareto Approach. IEEE Transactions on Evolutionary Computation, 3, 257-271. https://doi.org/10.1109/4235.797969
[27]	Gao, J., Zhen, L. and Wang, S. (2023) Multi-Trucks-and-Drones Cooperative Pickup and Delivery Problem. Transportation Research Part C: Emerging Technologies, 157, Article 104407. https://doi.org/10.1016/j.trc.2023.104407
[28]	Li, H., Wang, H., Chen, J. and Bai, M. (2020) Two-Echelon Vehicle Routing Problem with Time Windows and Mobile Satellites. Transportation Research Part B: Methodological, 138, 179-201. https://doi.org/10.1016/j.trb.2020.05.010
[29]	Moshref-Javadi, M., Hemmati, A. and Winkenbach, M. (2020) A Truck and Drones Model for Last-Mile Delivery: A Mathematical Model and Heuristic Approach. Applied Mathematical Modelling, 80, 290-318. https://doi.org/10.1016/j.apm.2019.11.020
[30]	Deb, K., Pratap, A., Agarwal, S. and Meyarivan, T. (2002) A Fast and Elitist Multiobjective Genetic Algorithm: Nsga-II. IEEE Transactions on Evolutionary Computation, 6, 182-197. https://doi.org/10.1109/4235.996017