Optimization approach for multiple trucks and drones flexible collaboration routing problem

doi:10.11918/202410063

多卡车-多无人机灵活协同路径问题优化方法

doi: 10.11918/202410063

刘成昊，徐金华，梁淑娟，邵进，李岩

长安大学运输工程学院，西安 710064

基金项目: 国家自然科学基金（72371035）；陕西省自然科学基础研究计划（2020JM-237）

详细信息

作者简介

刘成昊(2000—)，男，硕士研究生；

李岩(1983—)，男，教授，博士生导师

通讯作者

李岩，lyan@chd.edu.cn

中图分类号: F253.4

文献标识码: A

文章编号: 0367-6234(2025)11-0085-10

Optimization approach for multiple trucks and drones flexible collaboration routing problem

LIU Chenghao ， XU Jinhua ， LIANG Shujuan ， SHAO Jin ， LI Yan

School of Transportation Engineering, Chang′an University, Xi′an 710064 , China

摘要

为提高配送运输的效率，降低综合成本，针对卡车-无人机灵活协同路径问题设计优化方法。首先，综合多卡车-多无人机灵活协同和无人机连续运输的特点，以最小化运营成本与客户等待成本为目标，构建混合整数线性规划（mixed integer linear programming,MILP）模型。其次，设计两阶段启发式求解框架，在两个阶段分别优化无人机和卡车路径。最后，结合破坏算子、修复算子和k-opt算子构造混合邻域，提出自适应混合邻域搜索（adaptative hybrid neighborhood search,AHNS)算法进行每个阶段的优化。在Solomon数据集上进行数值实验，结果表明：相较于CPLEX求解器，所提方法可以在短时间内获取质量较高的满意解；相较于迭代局部搜索算法、变邻域搜索算法和蚁群算法，所提方法的求解质量在小、中和大规模算例中分别平均提高了5.49%、6.88%和27.82%；与纯卡车运输模式相比，卡车-无人机协同运输模式更适合小、中规模场景的作业，可以降低4.70%~8.56%的综合成本。研究结果可为卡车-无人机联合运输实践提供理论基础。

关键词

无人机运输 / 卡车-无人机协同 / 车辆路径问题 / MILP / AHNS

Abstract

To improve transportation efficiency and reduce total costs, an optimization approach is adopted to address truck-drone flexible collaboration routing problem. Firstly, a mixed integer linear programming model with the goal of minimizing the operation cost and customer waiting cost is formulated, combining the characteristics of multiple-truck-drone flexible collaboration and drone continuous delivery. Secondly, a two-stage heuristic solution framework is designed to optimize the routes of drones and trucks respectively in two stages. Finally, a tailored adaptive hybrid neighborhood search algorithm based on destroy operator, repair operator and k-opt operator is proposed for routing in each stage. The Solomon dataset is selected for numerical experiments, and the results show that: compared with CPLEX solver, the proposed method can obtain satisfactory solutions with higher quality in a short time. Compared with iterative local search, variable neighborhood search and ant colony optimization algorithm, the solution quality of the proposed method is improved by 5.49%, 6.88% and 27.82% in small-, medium- and large-scale instances, respectively. Compared to pure truck transportation mode, the truck-drone collaborative transportation mode is more suitable for small- and medium-scale operations, achieving a 4.70% to 8.56% reduction in overall costs. The research results can provide theoretical basis for the practice of truck-drone collaborative transportation.

Keywords

drone delivery / truck-drone collaboration / vehicle routing problem / mixed integer linear programming (MILP) / adaptative hybrid neighborhood search (AHNS)

1 问题描述与建模 1.1 问题描述 1.2 问题假设 1.3 问题建模 2 求解算法 2.1 求解框架 2.2 解的编码 2.3 自适应混合邻域搜索算法 2.3.1 初始解生成方法 2.3.2 算子 2.3.3 自适应算子选择机制 2.3.4 Metropolis接受准则 3 数值实验与结果分析 3.1 算法有效性检验 3.2 与纯卡车运输模式的比较分析 3.3 灵敏性分析 4 结论

无人机技术的日益成熟与其应用场景的不断拓展为运输行业的发展带来新的机遇。作为新兴的运输载具，无人机具有快速、灵活、绿色和低成本的优点^[1]。相较于地面车辆，无人机还有不受交通条件约束的优势^[2]，即使在交通拥堵等不良条件下也能稳定地完成运输任务。因此，被视为解决“最后一公里”交付问题的有效方案。

然而，无人机的飞行距离和载重能力十分有限，难以胜任长距离运输任务。2014年，AMP公司提出了卡车辅助无人机协同运输模式来填补该缺陷^[3]。这种运输模式引入了协同机制，即允许无人机与卡车汇合，卡车为无人机提供货物和电池的补充。该机制综合了卡车大容量的优点和无人机灵活的优势，可以有效拓展无人机的服务范围，有助于提高物流运输的工作效率^[4]。

卡车-无人机协同路径规划问题近年来备受关注。Murray等^[5]首先研究了单卡车-单无人机的带无人机旅行商问题（traveling salesman problem with drone，TSP-D），将一部分卡车客户分配给无人机以降低总体完工时间。Wang等^[6]提出了多卡车-多无人机的带无人机车辆路径问题（vehicle routing problem with drone，VRP-D）问题。后续研究关注于各个场景下的应用。Yin等^[7]通过卡车-无人机解决带时间窗问题。Ham^[8]和Stodola等^[9]讨论了多仓库的场景。贾兆红等^[10]研究了卡车、车载无人机和独立无人机混合作业的配送问题。季金华等^[11]研究了疫情场景下基于卡车与无人机的无接触配送问题。这类问题的目标函数包括最小化完工时间^[12-13]、最小化运输成本^[14]和最小化行驶距离^[15]等。

在模型求解方面，Bouman等^[16]设计了动态规划方法进行求解，并结合A^*算法进行加速。彭勇等^[17]针对VRP-D开发了结合K-means聚类与智能通用变邻域搜索（smart general variable neighborhood search，SGVNS）算法的求解方法。Xu等^[18]采取有向扰动算子与LKH算法分别进行客户分配与路径优化。Madani等^[19]使用贪婪算法与2-opt算子生成TSP-D的初始解，随后使用自适应变邻域搜索（adaptive variable neighborhood search，AVNS）算法搜索解空间。Ren等^[20]为VRP-D问题开发混合变邻域搜索（hybrid variable neighborhood search，HVNS）算法，并且针对子问题设计启发动态规划算法以快速求解。由于精确算法难以获取大规模问题的解，因此大部分文献采取启发式算法以高效获取大规模问题的满意解。

上述研究大多在模型中假设卡车与无人机一一对应，无人机仅能从固定一辆卡车处获取补给，这限制了作业方案的灵活性。此外，无人机在一个航程内能访问的节点多被限制在一个节点，该假设限制了无人机性能的发挥。为此，本文针对多卡车-多无人机灵活协同路径问题（multiple trucks and drones flexible collaboration routing problem，MTDFCRP），建立混合整数线性规划模型。模型以运营成本与客户等待成本为目标函数，结合连续运输与灵活协同特征，允许无人机连续服务多个客户，以及允许从不同卡车处接受补给。为加快求解速度，设计两阶段启发式求解框架，并通过自适应混合邻域搜索（adaptive hybrid neighborhood search，AHNS）算法实现路径优化。

1 问题描述与建模

1.1 问题描述

使用多辆卡车与多架无人机为区域内客户进行运输，其作业模式如图1所示。无人机从仓库出发，直接为客户服务。每个客户仅服务一次，不能重复服务。当无人机电池能量不足或携带包裹已配送完毕时，派出卡车为无人机进行补给。在选定对接地点后，卡车和无人机在该点汇合，卡车为无人机更换电池或补充包裹。补给完成后，无人机起飞，继续为其余客户服务；卡车驶往下一个对接点为无人机补给，或返回仓库。无人机在客户之间的移动和服务客户的耗时均考虑在路程时间内。无人机在任意节点的载重量不得超过最大载重能力，每个航程的距离受到电池容量限制。所有无人机和卡车均从同一个仓库出发，并且在完工后返回该仓库。

图1卡车-无人机协同运输示意

Fig.1Schematic diagram of truck-drone collaborative transportation

1.2 问题假设

针对该问题场景，基于以下假设进行建模：1）卡车与无人机均只有一个型号，没有性能差别; 2）卡车与无人机保持匀速水平移动，垂直方向上的移动忽略不计; 3）无人机可以在一个航程内连续服务多个客户; 4）无人机可以从不同卡车处接受补充，而非固定一辆卡车; 5）每一辆卡车均可以为任意数量的无人机提供足量的电池和货物; 6）卡车与无人机在对接结束后立刻出发，继续执行补给与运输任务。符号定义与解释如表1所示。

表1符号定义及解释

Tab.1Definition and interpretation of symbols

1.3 问题建模

使用表1中的符号，建立MTDFCRP的混合整数线性规划模型如下：

1）目标函数为

\begin{matrix} m i n f = \sum_{(i, j) \in A} (c_{1} \sum_{d \in D} d_{i j} x_{i j}^{d} + c_{2} \sum_{k \in K} d_{i j} y_{i j}^{k}) + \\ c_{3} \sum_{i \in N} \sum_{k \in K} \sum_{d \in D} z_{i}^{k d} + c_{4} D_{m} \overset{d}{\underset{d \in D}{m a x}} t_{n + 1}^{d} \end{matrix}

(1)

2）路径约束为

\sum_{j \in N \cup {n + 1}} x_{0 j}^{d} = \sum_{i \in N \cup {0}} x_{i, n + 1}^{d} = 1, \forall d \in D

(2)

\sum_{j \in N \cup {n + 1}} y_{0 j}^{k} = \sum_{i \in N \cup {0}} y_{i, n + 1}^{k} = 1, \forall k \in K

(3)

\sum_{d \in D} \sum_{i \in N \cup {0}} x_{i j}^{d} - \sum_{d \in D} \sum_{i \in N \cup {n + 1}} x_{j i}^{d} = 0, \forall j \in N

(4)

\sum_{k \in K} \sum_{i \in N \cup {0}} y_{i j}^{k} - \sum_{k \in K} \sum_{i \in N \cup {n + 1}} y_{j i}^{k} = 0, \forall j \in N

(5)

\sum_{d \in D} \sum_{i \in N \cup {0}} x_{i j}^{d} = 1, \forall j \in N

(6)

3）协同约束为

\sum_{d \in D} \sum_{k \in K} z_{i}^{k d} ⩽ 1, \forall i \in N

(7)

\sum_{k \in K} z_{j}^{k d} - \sum_{i \in N \cup {0}} x_{i j}^{d} ⩽ 0, \forall j \in N, d \in D

(8)

\sum_{d \in D} z_{j}^{k d} - \sum_{i \in N \cup {0}} y_{i j}^{k} = 0, \forall j \in N, k \in K

(9)

4）载重与距离约束为

\begin{matrix} M (1 - x_{i j}^{d}) + r_{j}^{d} ⩾ (r_{i}^{d} + d_{i j}) \\ (1 - \sum_{k \in K} z_{i}^{k d}), \forall (i, j) \in A, d \in D \end{matrix}

(10)

\begin{matrix} M (1 - x_{i j}^{d}) + q_{i}^{d} - p_{j} + (Q_{m a x} + p_{j} - q_{i}) \\ \sum_{k \in K} z_{j}^{k d} ⩾ q_{j}^{d}, \forall (i, j) \in A, d \in D \end{matrix}

(11)

r_{i}^{d} ⩽ R_{m a x}, \forall i \in N \cup N_{W}, d \in D

(12)

q_{i}^{d} ⩽ Q_{m a x}, \forall i \in N \cup N_{W}, d \in D

(13)

5）时间约束为

M (1 - x_{i j}^{d}) + t_{j}^{d} ⩾ t_{i}^{d} + \frac{d_{i j}}{S_{D}} + τ_{i}, \forall (i, j) \in A, d \in D

(14)

M (1 - x_{i j}^{d}) + t_{j}^{k} ⩾ t_{i}^{k} + \frac{d_{i j}}{S_{K}}, \forall (i, j) \in A, d \in D

(15)

M (1 - z_{i}^{k d}) + t_{i}^{d} ⩾ t_{i}^{k}, \forall i \in N, d \in D, k \in K

(16)

M (1 - z_{i}^{k d}) + t_{i}^{k} ⩾ t_{i}^{d}, \forall i \in N, d \in D, k \in K

(17)

6）变量取值范围为

x_{i j}^{d} \in {0,1}, \forall (i, j) \in A, d \in D

(18)

y_{i j}^{k} \in {0,1}, \forall (i, j) \in A, k \in K

(19)

z_{i}^{k d} \in {0,1}, \forall i \in N, k \in K, d \in D

(20)

r_{i}^{d} ⩾ 0, \forall i \in N, d \in D

(21)

q_{i}^{d} ⩾ 0, \forall i \in N, d \in D

(22)

t_{i}^{d} ⩾ 0, \forall i \in N, d \in D

(23)

t_{i}^{k} ⩾ 0, \forall i \in N, k \in K

(24)

式（1）即目标函数，旨在最小化综合了运营成本与客户等待成本的总成本。运营成本包括无人机路径成本、卡车路径成本和对接成本。客户等待成本基于客户最大等待时间，即服务完成时间进行描述。该项成本以无人机数量为系数，以平衡运营成本与客户等待成本的比例，且避免无人机利用不均。约束（2）、（3）限制无人机和卡车均从仓库出发且最终返回仓库。约束（4）、（5）为流量平衡约束，保证无人机和卡车进入某一客户和离开该客户的次数相同。约束（6）表明每个需求恰好被一架无人机服务一次。约束（7）表明在任意节点最多允许一架无人机与一辆车协同。约束（8）、（9）表明无人机与卡车必须到达节点才能在该点进行协同。当无人机在某点产生协同需求时，需要有恰好一辆卡车进行满足，该卡车可以是卡车集合中的任意一辆。约束（10）、（11）分别用于计算无人机在路径中各个节点间的累计飞行距离和累计送货量。其中的非线性项可以进行等价线性化。约束（12）、（13）限制无人机的累计飞行距离和累计送货量不能超过最大限制。约束（14）、（15）分别用于约束无人机与卡车在路径中各个节点的驶出时间。约束（16）、（17）限制参与对接的无人机与卡车离开对接节点的时间。出于提高工作效率的目的，当无人机在对接点接收卡车的补给后，立即赶往下一个客户点服务；卡车在完成对无人机的补给后，也会立刻驶往下一个对接点，为后续无人机服务。约束（18）~（24）限制决策变量的取值范围。

2 求解算法

MTDFCRP是VRP-D的变体，具有NP-Hard特性，难以获得大规模问题的精确解。因此设计一种两阶段启发式框架进行求解。该框架将问题分解为无人机路径问题与卡车路径问题。针对两个子问题，设计并运用AHNS算法进行迭代优化。求解框架与流程如图2所示。

图2两阶段求解框架

Fig.2Framework of two stage solution

2.1 求解框架

在已有相关文献中，大多将无人机视作卡车运输的辅助工具，采取“卡车优先”策略，即首先构造卡车路径，在此基础上生成无人机路径。MTDFCRP中所有客户均由无人机服务，因此采取“无人机优先”策略，首先优化无人机路径，其次优化卡车路径。

第一阶段，无人机路径规划阶段。针对客户信息，使用K-means聚类和节约算法生成无人机服务客户的初始路径。随后通过AHNS迭代搜索，对无人机的路径进行优化，以提升初始解的质量。该阶段暂时忽略无人机最大连续飞行距离与最大载重约束，以生成理想情况下质量较高的无人机路径。由于第一阶段忽略了两类约束，所以最终得到不可行解。为了将其可行化，基于贪婪思想，将无人机停靠的对接点插入路径，从而将路径划分为多个航程。使每一个航程同时满足航程距离和载重量约束，且每程内航程距离和载重量得到尽可能大的利用，即在最后一个客户，没有足够的航程距离或空余载重量抵达或服务下一个客户。

第二阶段，卡车路径规划阶段。首先根据无人机的航程信息，生成与卡车的对接节点以及交互次序限制。与第一阶段类似，根据对接需求信息应用K-means聚类和节约算法生成卡车初始路径，随后使用AHNS的迭代搜索程序对路径进行优化。这一阶段考虑无人机最大连续飞行距离与最大载重约束，以保证解的可行性。最终，输出无人机与卡车的联合运输路径。

2.2 解的编码

两个阶段的路径问题都可以通过引入虚拟仓库点等价转化为旅行商问题（traveling salesman problem，TSP），便于对解进行编码以及应用算子。根据问题中载具数量，需引入相同数量的虚拟仓库点。真实仓库点的序号记作0^（0），虚拟仓库点的序号记作0^（1），0^（2），···，0^（^k^）。虚拟仓库点到各个客户的距离与真实仓库点到客户的距离相同，而所有仓库点之间的距离均设置为足够大的正数M。

图3展示了一个2卡车2无人机11客户问题的解的编码示例。其中两架无人机均从仓库点出发，分别访问了客户1~7和客户8~11。第1辆卡车依次在点2和点4协助无人机，第2辆卡车依次在点10、点8和点6协助无人机。

图3解的编码示例

Fig.3Example of coding solution

2.3 自适应混合邻域搜索算法

自适应混合邻域搜索算法流程如图4所示。该算法首先通过聚类算法和节约算法生成每个阶段问题的初始解，随后通过混合使用破坏算子、修复算子和k-opt算子来生成新解，以Metropolis准则接受新解。当算法迭代次数达到指定次数后流程终止，输出最优解。

2.3.1 初始解生成方法

节约算法是一种近似算法，可以生成质量较高的TSP解。然而，其在求解由VRP转化而来的TSP时，不同车辆的路径往往长短不均，导致车辆利用率不足，生成质量较差的解。因此将K-means聚类方法与节约算法结合，以生成车辆路径长度均匀的初始解。将该生成方法应用于两个阶段，分别生成无人机路径初始解与卡车路径初始解。其具体步骤如下：

步骤1 输入客户集合N、任意两点间的距离d_ij、载具（卡车或无人机）数量C_m。

图4AHNS算法流程

Fig.4Flow chart of AHNS

步骤2 使用K-means聚类算法将客户节点聚为C_m类，得到每一类客户集合N_c={n₁，n₂，···}，c=1，2，···，C_m。

步骤3 对每辆载具c∈C，执行步骤4~7。

步骤4 令载具c从仓库出发，每次仅访问一个客户后回到仓库，持续访问直到所有客户均被访问，构成初始环路T={（1，n₁），（n₁，1），（1，n₂），（n₂，1），···}。

步骤5 寻找所有可行节约客户对（i，j），也就是使用（i，j）替代（i，1）和（1，j）后，路径仍然保持环路结构的客户对。

步骤6 计算所有可行节约客户对（i，j）的节约值Saving_（_i_，_j_）=d_i₁+d₁_j-d_ij，选择节约值最大的可行节约客户对（i^*，j^*），替代环路中的（i^*，1）和（1，j^*），形成新的环路T′。

步骤7 重复步骤5、6直到形成可行的TSP环路（从仓库出发连续访问所有客户后回到仓库的路径）。

步骤8 输出所有载具的作业路径。

在生成卡车路径时，步骤3结束后需要额外进行路径可行性检测。路径可行的必要条件是由全部节点、卡车路径和无人机路径组成的有向图中无环。如果图中存在环，则卡车和无人机的对接会陷入矛盾。例如，在图3的例子中，第一辆卡车不能先访问点4，后访问点2。因为无人机必须先在点2接受补给，才能抵达点4。若卡车路径不可行，则交换其路径中顺序错误的点，直到可行。

2.3.2 算子

AHNS算法综合使用破坏算子、修复算子和k-opt算子进行混合邻域搜索。破坏算子按照破坏比例β将N_des=β×N个节点移除，修复算子将这些点重新插入解中，k-opt算子使用新的边取代路径中的边。所采用的具体算子如下。

破坏算子：1）随机破坏算子d₁，从解中随机地移除N_des个节点。2）贪婪破坏算子d₂，移除解中成本最高的节点，重复移除直到N_des个节点被破坏；节点i的成本通过公式cost_i=d_i_-1，_i+d_i_，_i₊₁计算，其中i-1和i+1分别为路径中与点i相邻的两个节点。3）延误破坏算子d₃，移除解中延误最高的协同节点，即卡车与无人机相互等待时长最长的对接节点。节点i的对接延误通过公式delay_i=abs（a^k_i-a^d_i）计算，其中 abs（·）为绝对值函数，a^k_i为卡车k到达节点i的时间，a^d_i为无人机d到达节点i的时间。4）相关破坏算子d₄，首先随机移除一个节点，然后移除与该节点相关性最高的节点，重复移除直到N_des个节点被破坏；任意两个不同节点i与j的相关度通过公式R（i，j）=（D（i，j）+P（i，j））^-1计算，其中

D （ i ， j ） = \frac{d_{i j}}{\underset{i ， j \in N}{m a x} d_{i j}} ， P （ i ， j ） = \frac{|p_{i} - p_{j}|}{\underset{i ， j \in N}{m a x} |p_{i} - p_{j}|}

。

修复算子：1）随机修复算子r₁，将被移除节点随机地插入当前路径中。2）贪婪插入算子r₂，将被移除节点按照最小成本规则插入到当前路径，节点i插入位置的成本通过公式cost_i=d_i_-1，_i+d_i_，_i₊₁计算，其中i-1和i+1分别为点i拟插入位置相邻的两个节点。3）后悔插入算子r₃，将被移除节点按照最小后悔规则插入到当前路径，节点i插入某位置的后悔值由成本和对其他节点的影响构成，具体通过公式

{R e g}_{i} = {c o s t}_{i} + \sum_{j \in {R e m ∖ i}} Δ {c o s t}_{j}

计算，其中， Rem为全体被破坏节点的集合，Δcost_j为节点j在点i插入路径前后最小成本值的差值。

k-opt算子：1）2-opt算子o₁，该算子使用2条新的边取代当前解中的2条边；从当前解中随机选择2条边，然后将对应的4个点重新组合，使路径重新可行。2）3-opt算子o₂，使用3条新的边取代当前解中的3条边；从当前解中随机选择3条边，然后将对应的6个点重新组合，使路径重新可行。

2.3.3 自适应算子选择机制

AHNS算法在选择算子时，根据可选集合O={1，2，···，O_m}中每个算子的分数ω_i，i∈O，计算其被选中的概率。算子i被选中的概率为

q_{i} = \frac{ω_{i}}{\sum_{j \in O} ω_{j}}

。由于破坏算子和修复算子需要共同作用才能生成新可行解，而k-opt算子可以独立生成。因此在进行算子选择时，首先从破坏算子和k-opt算子的并集中按照概率选择算子。若选中算子属于破坏算子，则额外选择修复算子与之结合；若选中k-opt算子，则跳过修复算子的选择。

初始时每个算子均拥有相等的分数ω₀。每次生成新的可行解后，根据可行解的质量更新算子分数。从而自适应地调整算子分数，改变算子被选中的可能性。分数更新公式为

ρ_{i + 1} = λ ρ_{i} + (1 - λ) ψ

(25)

式中：ρ_i和ρ_i₊₁分别为对应算子在第i次和第i+1次迭代时的分数，λ∈（0，1）为反应系数，ψ为更新分数，其当新解优于历史最优解时，取ω₁；当新解优于当前解时，取ω₂；当新解被Metropolis准则接受时，取ω₃；当新解未被接受时，取ω₄。

2.3.4 Metropolis接受准则

为了降低陷入局部最优的可能性，结合模拟退火机制的Metropolis准则进行解的接受决策。准则内容如下：当新解优于当前解时，必然接受新解；当新解不优于当前解时，以概率P接受新解作为当前解。概率P计算公式为

P = e x p (- \frac{O b j (N e w S) - O b j (C u r S)}{T_{0} \cdot α^{i t e r - 1}})

(26)

其中：Obj（·）为目标函数，NewS为新解，CurS为当前解，T₀为初始温度，α为温度衰减系数，iter为当前迭代次数。

3 数值实验与结果分析

为检验本文所提出算法的有效性，采取Solomon的CVRP数据集中R1、R2、C1、C2、RC1、RC2 6个案例进行测试。其中R代表客户随机分布；C代表客户集群分布；RC为前两类的综合分布。对每个测试案例，依序选取客户生成算例。包括6、8、10个客户的微型算例和25、50、100个客户的常规算例。微型算例使用2辆卡车与2架无人机进行运输，常规算例使用2辆卡车与4架无人机进行运输。客户需求p_i和服务时间τ_i由算例给定。任意两点间距离d_ij以欧氏距离计算。参考Wang等^[6]与Kim等^[15]，标定参数如下：卡车速度S_K=1，无人机速度S_D=1.25；无人机的航程最大距离R_max=125，载重量P_max=50；成本参数c₁=1/3，c₂=1，c₃=20，c₄=1。

CPLEX求解器是当前主流商业求解器之一，具有出色的性能和高效的求解能力^[21]。因此，在微型算例上，将本文所提算法与CPLEX求解器进行比较；在常规算例上，与迭代局部搜索算法（iterative local search，ILS）^[22]、变邻域搜索算法（variable neighborhood search，VNS）^[23]和蚁群算法（ant colony optimization，ACO）^[24]进行比较。CPLEX求解器求解时限设置为3 600 s。AHNS算法参数设置如下：初始温度T₀=200，温度衰减系数α=0.962 8，算子初始与更新分数ω₀=1，ω₁=20，ω₂=5，ω₃=1，反应系数λ=0.95，破坏比例β=0.1。AHNS、ILS、VNS的迭代次数设置为10 000，ACO的迭代次数设置为200。对于ACO算法，蚂蚁数为20，信息素系数α=1.65，启发函数系数η=1.4，信息素蒸发速率γ=0.01。所有算法均通过MATLAB编程实现，在搭载AMD Ryzen 77745HX @ 5.1 GHz CPU的计算机上进行实验。为减少随机因素对启发式算法的影响，取每个算例10次运行的结果进行分析。

3.1 算法有效性检验

在微型算例上比较CPLEX与AHNS的求解结果，如表2所示，其中Gap_Opt与Gap_Ave分别为AHNS最佳结果和平均结果与CPLEX解的差距，Gap_Opt=（Obj_Opt-Obj_CPLEX）/Obj_CPLEX；Gap_Ave=（Obj_Ave-Obj_CPLEX）/Obj_CPLEX，Obj_Opt和Obj_Ave分别为AHNS的最优目标值和平均目标值，Obj_CPLEX为CPLEX目标值；*表示求解器未在限时内获取最优解，使用上界作为替代。

表2CPLEX与AHNS求解结果比较

Tab.2Comparison between CPLEX and AHNS solution

在求解质量上，AHNS算法与CPLEX最优解的平均差距在4.40%~5.96%。而AHNS在10次求解中的最佳结果与最优解的平均差距仅有0.21%~1.84%，说明AHNS具有较好的搜索能力和收敛性能，可以获取满意解。就计算时间而言，AHNS算法0.3 s内就可以完成求解，而CPLEX在6节点和8节点规模的算例上分别需要1.59 s和423.07 s才能实现求解。当问题规模达到10后，CPLEX便无法在1 h内获取最优解。

为进一步检验算法在更大规模算例上的有效性，将AHNS与ILS、VNS和ACO算法进行比较。图5展示了各个算法在常规算例中的平均目标函数值和花费的平均求解时间。AHNS相对其他算法的求解质量优势在小、中和大规模算例上分别为5.49%、6.88%和27.82%。说明AHNS的表现稳定优于其他算法，且优势随着问题规模的增加而扩大。此外，AHNS求解小、中和大规模算例的平均时间分别为0.65、3.53、11.92 s，与最快算法的时间差距均在3%以内，具有快速求解的能力。

图5ILS、VNS、ACO和AHNS求解质量与求解时间

Fig.5Quality of solutions and computational time of ILS, VNS, ACO and AHNS

3.2 与纯卡车运输模式的比较分析

对纯卡车运输模式（模式1）与卡车-无人机协同运输模式（模式2）进行对比分析。模式1中卡车数量与模式2中全体载具数量相同。求解时采取相同的参数，根据问题规模分类，取6个案例的目标函数平均值作为结果，展示在图6中。图6（a）展示了两种模式的总成本。相较于模式1，模式2在中、小规模运输场景下可以显著降低综合成本，降低比例为4.70%~8.56%。随着运输规模的上升，混合使用卡车-无人机的优势逐渐降低。当规模达到100时，模式1的成本比模式2低3.73%。图6（b）进一步展示了两种模式在运营成本（OC）与客户等待成本（LC）上的差别。尽管卡车-无人机模式在各个规模下均可以保证更低的客户等待成本，但是由于同时使用两类载具，也导致了更高的运营成本。因此，就综合成本而言，卡车-无人机运输模式适宜实现小、中规模的运输作业。对于时效性高和价值高的货物，其对服务水平具有更高的要求，也适合使用卡车-无人机运输模式进行运送。

图6纯卡车运输模式与卡车-无人机协同运输模式的比较

Fig.6Comparison between pure truck and truck-drone collaborative delivery mode

3.3 灵敏性分析

为验证关键参数对于模型结果的影响，分别针对无人机速度和无人机数量进行灵敏性分析。图7展示了不同问题规模下，调整参数得到的目标函数值，该值为6个案例结果的均值。图中S、M和L分别代表小、中和大规模算例。由图7（a）可知，提高无人机速度对解的质量有明显提升。速度从1提升至2，累积改进率可达23.36%~39.05%。但边际效益递减，速度值较高时，提高速度的改进率较低。由图7（b）可知，当卡车数量固定时，部署更多无人机不一定能带来总体成本的降低。当无人机数量升高后，卡车无法及时交互，导致延误，无人机无法得到充分利用。因此，在确定无人机-卡车数量比时，需要考虑卡车与无人机协作的效率。

图7参数灵敏度分析

Fig.7Sensitivity analysis of parameters

4 结论

1）本文针对多卡车-多无人机灵活协同路径问题，以最小化运营成本与客户等待成本之和为目标函数，建立了混合整数线性规划模型。该模型整合了无人机连续运输与灵活协同的特征，提高了运输方案的灵活性。基于算例数据，使用CPLEX求解模型，验证了模型的可行性。

2）设计了两阶段启发式求解框架，综合破坏算子、修复算子和k-opt算子构建混合邻域，提出AHNS算法进行求解。AHNS算法与CPLEX求解器、ILS、VNS和ACO求解方法在Solomon数据集上比较的结果表明，AHNS算法不仅可以高效获取小规模问题的高质量满意解，还可以在保证求解质量的同时快速地求解大规模问题。

3）将卡车-无人机协同运输模式与纯卡车运输模式进行比较，量化了前者在总成本上的优势，分析了二者在不同场景的适用性。与纯卡车运输模式相比，卡车-无人机协同运输模式具有更低的客户等待成本，但也有更高的运营成本。

4）后续研究考虑建立多目标优化模型，以提供更多样化和更全面的决策方案。同时考虑综合更多现实因素，例如配置卡车、无人机和卡车-无人机组合的混合车队，以及考虑无人机的非线性能耗等特征。

图1卡车-无人机协同运输示意

Fig.1Schematic diagram of truck-drone collaborative transportation

下载: 全尺寸图片

图2两阶段求解框架

Fig.2Framework of two stage solution

下载: 全尺寸图片

图3解的编码示例

Fig.3Example of coding solution

下载: 全尺寸图片

图4AHNS算法流程

Fig.4Flow chart of AHNS

下载: 全尺寸图片

图5ILS、VNS、ACO和AHNS求解质量与求解时间

Fig.5Quality of solutions and computational time of ILS, VNS, ACO and AHNS

下载: 全尺寸图片

图6纯卡车运输模式与卡车-无人机协同运输模式的比较

Fig.6Comparison between pure truck and truck-drone collaborative delivery mode

下载: 全尺寸图片

图7参数灵敏度分析

Fig.7Sensitivity analysis of parameters

下载: 全尺寸图片

表1符号定义及解释

Tab.1Definition and interpretation of symbols

下载: 全尺寸图片

表2CPLEX与AHNS求解结果比较

Tab.2Comparison between CPLEX and AHNS solution

下载: 全尺寸图片

图1卡车-无人机协同运输示意

Fig.1Schematic diagram of truck-drone collaborative transportation

图2两阶段求解框架

Fig.2Framework of two stage solution

图3解的编码示例

Fig.3Example of coding solution

图4AHNS算法流程

Fig.4Flow chart of AHNS

图5ILS、VNS、ACO和AHNS求解质量与求解时间

Fig.5Quality of solutions and computational time of ILS, VNS, ACO and AHNS

图6纯卡车运输模式与卡车-无人机协同运输模式的比较

Fig.6Comparison between pure truck and truck-drone collaborative delivery mode

图7参数灵敏度分析

Fig.7Sensitivity analysis of parameters

表1符号定义及解释

Tab.1Definition and interpretation of symbols

表2CPLEX与AHNS求解结果比较

Tab.2Comparison between CPLEX and AHNS solution

图1卡车-无人机协同运输示意

Fig.1Schematic diagram of truck-drone collaborative transportation

图2两阶段求解框架

Fig.2Framework of two stage solution

图3解的编码示例

Fig.3Example of coding solution

图4AHNS算法流程

Fig.4Flow chart of AHNS

图5ILS、VNS、ACO和AHNS求解质量与求解时间

Fig.5Quality of solutions and computational time of ILS, VNS, ACO and AHNS

图6纯卡车运输模式与卡车-无人机协同运输模式的比较

Fig.6Comparison between pure truck and truck-drone collaborative delivery mode

图7参数灵敏度分析

Fig.7Sensitivity analysis of parameters

表1符号定义及解释

Tab.1Definition and interpretation of symbols

表2CPLEX与AHNS求解结果比较

Tab.2Comparison between CPLEX and AHNS solution

郭兴海, 计明军, 温都苏, 等.“最后一公里”运输的分布式多无人机的任务分配和路径规划[J]. 系统工程理论与实践,2021,41(4):946.GUO Xinghai, JI Mingjun, WEN Dusu,et al. Task assignment and path planning for distributed multiple unmaned aerial vehicles in the "last mile"[J]. Systems Engineering——Theory & Practice,2021,41(4):946

OTTO A, AGATZ N, CAMPBELL J,et al. Optimization approaches for civil applications of unmanned aerial vehicles(UAVs)or aerial drones:a survey[J]. Networks,2018,72(4):411

CARLSSON J G, SONG S Y. Coordinated logistics with a truck and a drone[J]. Management Science,2018,64(9):4052

ZHOU H, QIN H, CHENG C,et al. An exact algorithm for the two-echelon vehicle routing problem with drones[J]. Transportation Research Part B: Methodological,2023,168,124

MURRAY C C, CHU A G. The flying sidekick traveling salesman problem:optimization of drone-assisted parcel delivery[J]. Transportation Research Part C: Emerging Technologies,2015(54):86

WANG Z, SHEU J B. Vehicle routing problem with drones[J]. Transportation Research Part B: Methodological,2019(122):350

YIN Y, LI D, WANG D,et al. A branch-and-price-and-cut algorithm for the truck-based drone delivery routing problem with time windows[J]. European Journal of Operational Research,2023,309(3):1125

HAM A M. Integrated scheduling of m-truck,m-drone,and m-depot constrained by time-window,drop-pickup,and m-visit using constraint programming[J]. Transportation Research Part C: Emerging Technologies,2018(91):1

STODOLA P, KUTEJ L. Multi-depot vehicle routing problem with drones:mathematical formulation,solution algorithm and experiments[J]. Expert Systems with Applications,2024(241):122483

贾兆红, 王少贵, 刘闯. 多模式下的车辆和无人机联合运输模型与优化算法[J]. 控制与决策,2024,39(7):2125.JIA Zhaohong, WANG Shaogui, LIU Chuang. Vehicle and drones joint distribution model and optimization algorithm in multi-mode[J]. Control and Decision,2024,39(7):2125

季金华, 刘亚君, 别一鸣, 等. 基于无人机与卡车协作的封控社区生活物资运输方法[J]. 交通运输系统工程与信息,2022,22(5):264.JI Jinhua, LIU Yajun, BIE Yiming,et al. Delivery method of living goods in controlled communities based on cooperation between drones and truck[J]. Journal of Transportation Systems Engineering and Information Technology,2022,22(5):264

JEONG H Y, SONG B D, LEE S. Truck-drone hybrid delivery routing:payload-energy dependency and No-Fly zones[J]. International Journal of Production Economics,2019,214:220

POIKONEN S, GOLDEN B. Multi-visit drone routing problem[J]. Computers & Operations Research,2020,113:104802

JIANG J, DAI Y, YANG F,et al. A multi-visit flexible-docking vehicle routing problem with drones for simultaneous pickup and delivery services[J]. European Journal of Operational Research,2024,312(1):125

KIM D, SEONG KO C, MOON I. Coordinated logistics with trucks and drones for premium delivery[J/OL]. Transportmetrica A: Transport Science.(2023-11-17).https://doi.org/10.1080/23249935.2023.2282963

BOUMAN P, AGATZ N, SCHMIDT M. Dynamic programming approaches for the traveling salesman problem with drone[J]. Networks,2018,72(4):528

彭勇, 任志. 公交辅助无人机的城市物流运输模式研究[J]. 计算机工程与应用,2024,60(7):335.PENG Yong, REN Zhi. Research on urban logistics distribution mode of bus-assisted drones[J]. Computer Engineering and Applications,2024,60(7):335

XU J, LIU C, SHAO J,et al. Collaborative orchard pesticide spraying routing problem with multi-vehicles supported multi-UAVs[J]. Journal of Cleaner Production,2024:142429

MADANI B, NDIAYE M, SALHI S. Hybrid truck-drone delivery system with multi-visits and multi-launch and retrieval locations:mathematical model and adaptive variable neighborhood search with neighborhood categorization[J]. European Journal of Operational Research,2024,316(1):100

REN X, FROGER A, JABALI O,et al. A competitive heuristic algorithm for vehicle routing problems with drones[J]. European Journal of Operational Research,2024,318(2):469

DU Y, KOCHENBERGER G, GLOVER F,et al. Solving clique partitioning problems:a comparison of models and commercial solvers[J]. International Journal of Information Technology & Decision Making,2022,21(1):59

SOUSA M M D, GONZALEZ P H, OCHI L S,et al. A hybrid iterated local search heuristic for the traveling salesperson problem with hotel selection[J]. Computers & Operations Research,2021,129:105229

EL-ADLE A M, GHONIEM A, HAOUARI M. A variable neighborhood search for parcel delivery by vehicle with drone[J]. Computers & Operations Research,2023,159:106319

赵建有, 肖宇, 朱欣媛, 等. 考虑需求紧迫度的应急车辆路径优化方法[J]. 哈尔滨工业大学学报,2022,54(9):27.ZHAO Jianyou, XIAO Yu, ZHU Xinyuan,et al. Route optimization method for emergency vehicles considering demand urgency[J]. Journal of Harbin Institute of Technology,2022,54(9):27

Publication Statement

Journal Subscription

1 问题描述与建模

2 求解算法

3 数值实验与结果分析

4 结论