需求不确定下卡车-无人机协同的路径优化研究

Research on Path Optimization of Truck–Drone Collaboration under Uncertain Demand

摘要

针对突发事件发生后，部分受灾点的应急物资需求呈现波动性，为提高应急物资配送效率，对需求不确定下的卡车-无人机协同的路径优化问题进行研究。首先，引入需求不确定水平参数，建立卡车与无人机协同配送的鲁棒路径优化模型；其次，提出一种改进的自适应大规模邻域搜索算法(IALNS)，通过设计多样化的删除与修复算子以增强解的多样性，同时通过模拟退火过程更新解，保证解的收敛性；然后，利用Solomon算例验证算法的有效性，并与传统的遗传算法(GA)和粒子群算法(PSO)进行比较，GA、PSO与IALNS算法的平均GAP分别为15.18%，12.91%，验证了算法的可靠性；最后，对需求不确定水平参数、无人机载重以及续航里程进行灵敏度分析。实验结果表明，鲁棒优化模型和IALNS算法可以保证受灾点在需求波动下卡车-无人机路径的可行性。

Abstract

In response to the fluctuation of emergency material demand in some disaster-stricken areas after the occurrence of emergencies, research was conducted on the path optimization problem of truck-drone collaboration under uncertain demand to improve the efficiency of emergency material distribution. Firstly, the parameter of uncertain demand level was introduced, and a robust path optimization model for the collaboration between trucks and drones was constructed. Secondly, an improved adaptive large neighborhood search algorithm (IALNS) was proposed. This algorithm enhanced solution diversity by designing diversified removal and repair operators and updated the solution through a simulated annealing process to ensure its convergence. Then, the Solomon benchmark was employed to evaluate the algorithm’s effectiveness, and the algorithm was compared with the traditional genetic algorithm (GA) and particle swarm optimization (PSO) algorithm. The average GAP of GA, PSO, and IALNS algorithms was 15.18% and 12.91%, respectively, verifying the reliability of the algorithm. Finally, sensitivity analysis was conducted on uncertain level parameters of demand, drone load capacity, and range. The experimental results show that the robust optimization model and IALNS algorithm can ensure the feasibility of the truck–drone path at the disaster-stricken site under demand fluctuations.

Graphical abstract

关键词

路径优化 / 卡车-无人机协同 / 需求不确定 / 自适应大规模邻域搜索算法

Key words

Path Optimization / Truck–Drone Collaboration / Uncertain Demand / Adaptive Large Scale Neighborhood Search Algorithm

0　引言

近年来各类突发事件频发，如自然灾害、公共卫生事件等，给人们的生命和财产造成了巨大损失。灾害发生后，对应急物资运输的紧迫性非常强，应急物资无法及时运输会造成更严重的伤亡^[1]。随着受灾情势不断变化，部分地区的应急物资需求量呈现波动态势，要求应急管理部门能够按实际情况及时调整应急物资调配策略，从而保障救援工作高效展开。如何在部分受灾点应急物资需求波动的情况下有效地开展这项工作，使救援行动更加高效，是当下相关领域学者需要重点考虑的问题。

目前，随着铁路巡检向天空地立体化发展，无人机被逐渐运用于铁路巡检工作中^[2]。同时，无人机技术也正逐步引入交通运输行业，如赵明丽等^[3]提出的铁路非正常接发列车人机协同作业模式，能够显著提升作业效率和安全性，为铁路运输的智能化转型提供新的解决方案，释放铁路车站运能。目前，卡车-无人机协同配送模式也逐渐被运用在物流领域。2015年，Murray等^[4]首次提出了货车无人机协同配送的概念，并建立货车-无人机协同优化模型。突发事故发生后，传统的卡车配送模式无法在短时间内响应所有受灾点的应急物资需求，且道路损毁的受灾点卡车无法到达；纯无人机配送模式受载重和续航限制，单次配送能力有限，也无法满足所有受灾点的应急物资需求；同时，事故发生初期对受灾点的应急物资需求预测与实际情况往往存在误差，受灾点的应急物资需求是波动变化的，此时无人机可以针对单次配送所获取到的受灾点实时信息，从而对该受灾点进行多次配送，应急响应部门也可根据实时信息对卡车-无人机的路线进行动态调整。卡车-无人机协同调度作为一种创新的物流调度模式，通过结合卡车和无人机各自的优势，克服传统物流方式的局限性，在应急场景中展现出独特的价值。

卡车-无人机协同的路径优化问题作为物流领域的新兴研究热点，吸引了众多学者的关注。在模型构建方面，已有研究提出了多种优化模型，包括混合整数规划模型、多目标优化模型以及适用于动态环境的实时调度模型。这些模型为利用卡车-无人机解决实际配送问题提供了理论基础。如钟导峰等^[5]针对面向中长距离应急物资的“火车-卡车-无人机”协同运输，以总运输成本最小为目标，构建“火车-卡车-无人机”协同运输的整数规划模型。Das等^[6]研究利用卡车进行发射和接收无人机，以最大限度地降低运输成本和提高客户服务水平。Wang等^[7]提出了动态的TDHRP-TDRTT模型，模型中考虑了实时的城市道路堵塞程度。同时，在构建卡车-无人机协同路径优化模型时，需考虑相关的约束条件，现有研究多集中于考虑时间窗约束^[8]、道路通行约束^[9]、载重续航约束^[10]以及飞行区域限制^[11]等方面。在算法研究方面，由于卡车-无人机协同路径优化问题通常是NP-hard问题，求解大规模问题时面临较大困难。为此，学者们提出了多种求解方法，包括精确算法、启发式算法和元启发式算法，如遗传算法^[12-13]、模拟退火算法^[14]和蚁群优化算法^[15]等。这些算法在提高求解效率和优化配送方案方面发挥了重要作用。在应用场景方面，卡车-无人机协同配送模式已广泛应用于灾害应急、偏远地区物流^[16]、城市“最后一公里”配送^[17]以及医疗物资运输^[18]等领域。尤其在灾害应急场景中，协同配送模式通过结合卡车的大批量运输能力和无人机的灵活性，有效提升了应急响应效率。如胡大伟等^[19]为了在应急响应初期，将应急物资及时送达受灾地区、降低人员伤亡以及减少财产损失，结合卡车相对运量大、无人机运行速度快等特点，提出卡车-无人机联合配送应急物资模式；龚英等^[20]为提高洪灾应急物资配送效率，提出卡车-无人机动态协同配送应急物资模型。

然而，尽管现有研究在理论和实践方面取得了一定的进展，但大多数研究集中于确定性需求量进行模型构建和求解，忽略了应急物资需求的波动性，从而导致模型的假设过于理想化，无法充分应对实际应急场景中的复杂性。因此，本研究在考虑需求不确定的基础上构建卡车-无人机协同的路径鲁棒优化模型，该模型保证卡车-无人机在部分受灾点需求波动下路径的可行性。同时根据模型特征，提出了一种改进的自适应大规模邻域搜索算法(Iterated Large Neighborhood Search，IALNS)，结合Solomon算例进行算法有效性分析。

1　问题描述与模型构建

1.1　问题描述

突发事件发生后，采用卡车-无人机协同配送模式对应急物资进行配送。卡车-无人机路线示意图如图1所示，研究问题可描述为：一个应急配送中心配备多辆卡车和多架无人机，每辆卡车携带一架无人机从应急配送中心出发，对多个受灾点进行应急物资配送，卡车与无人机一一对应，无人机从卡车起飞与降落。无人机在其载重和里程限制内，每次为一个受灾点进行配送。无人机在对单个受灾点进行多次配送过程中，卡车需要在受灾点进行等待；无人机在对受灾点进行单次配送时，卡车不需要等待无人机往返，可前往其他受灾点进行配送，并在下一个受灾点与无人机汇合，直到所有受灾点配送完毕。

为将问题模型化，做出以下假设。

（1）应急配送中心和受灾点的位置已知。

（2）每辆卡车携带一架无人机从应急配送中心出发，完成路径上所有受灾点的配送，无人机只能从卡车上起飞与降落。

（3）暂不考虑无人机充电或更换电池的时间，无人机每次只能配送一个受灾点。

（4）无人机、卡车型号均一致且所有参数已知，卡车和无人机的行驶速度采用平均值，且行驶速度不受载质量的变化影响。

（5）无人机从某一卡车上发射后，不能降落在另一辆卡车上。

（6）每个受灾点都有硬时间窗限制。

1.2　符号说明

受灾点集合I分为2类，一类是卡车负责配送的集合I₁，一类是无人机负责配送的集合I_2，I = I₁∪I₂。应急物资配送路线包括2种，一种是卡车路线，一种是无人机路线。模型中使用的集合符号及说明如表1所示，参数符号及说明如表2所示，决策变量符号及说明如表3所示。

1.3　模型构建

以卡车-无人机总配送时间最短为目标，包括所有卡车的总配送时间T₁和所有卡车-无人机协同配送的时间T₂。考虑部分受灾点需求的不确定性，构建卡车-无人机协同的路径鲁棒优化模型。

目标函数为

\mathrm{m}\mathrm{i}\mathrm{n}Z=T_{\mathrm{1}}+T_{\mathrm{2}}(1)

T_{\mathrm{1}}=\sum _{i\in I_{\mathrm{1}}}\sum _{j\in I_{\mathrm{1}}}\sum _{k\in K}{x}_{ijk}{d}_{ij}/v_k+\sum _{i\in I_{\mathrm{1}}}\sum _{k\in K}{z}_{ik}{s}_i(2)

T_{\mathrm{2}}=\sum _{i\in I_{\mathrm{1}}}\sum _{k\in K}\sum _{f\in F}{t}_{ikf}(3)

约束条件表述如下。

\sum _{k\in K}{z}_{ik}=\mathrm{1}\begin{array}{cc}& \end{array}\forall i\in I_{\mathrm{1}}(4)

\sum _{f\in F}\sum _{k\in K}{\omega }_{ikf}=\mathrm{1}\begin{array}{cc}& \end{array}\forall i\in I_{\mathrm{2}}(5)

\sum _{j\in I_{\mathrm{1}}\bigcup \{\mathrm{0}\}}{x}_{ijk}=\sum _{j\in I_{\mathrm{1}}\bigcup \{\mathrm{0}\}}{x}_{ijk}=z_{ik}\begin{array}{cc}& \end{array}\forall k\in K，\forall i\in I_{\mathrm{1}}(6)

f_{ik}-f_{jk}+M{x}_{ijk}\le M-\mathrm{1}\begin{array}{cc}& \end{array}\forall i，j\in I_{\mathrm{1}}，\forall k\in K(7)

D_{ij}{y}_{ijkf}\le \lambda \begin{array}{cc}& \end{array}\forall i\in I_{\mathrm{1}}，j\in I_{\mathrm{2}}，k\in K，f\in F(8)

d{\tilde{e}}_i{\omega }_{ikf}e\le Q_f{n}_{ikf}\begin{array}{cc}& \end{array}\forall i\in I_{\mathrm{2}}，k\in K，f\in F(9)

\sum _{i\in I_{\mathrm{1}}}d{\tilde{e}}_i{z}_{ik}e+\sum _{i\in I_{\mathrm{2}}}\sum _{f\in F}d{\tilde{e}}_i{\omega }_{ikf}e\le Q_k\begin{array}{cc}& \end{array}\forall k\in K(10)

t_i^k\ge T_i^k+d_{ij}/v_k-M(\mathrm{1}-x_{ijk})\begin{array}{cc}& \end{array}\forall i，j\in I_{\mathrm{1}}，k\in K(11)

T_i^k\ge t_i^k+s_i+T_{\mathrm{1}}+T_{\mathrm{2}}-M(\mathrm{1}-z_{ik})\begin{array}{cc}& \end{array}\forall i\in I_{\mathrm{1}}，

k\in K(12)

R_{ikf}\ge t_i^k+T_{\mathrm{1}}-M(\mathrm{1}-z_{ik})\begin{array}{cc}& \end{array}\forall i\in I_{\mathrm{1}}，k\in K，

f\in F(13)

t_i^f\ge R_{ikf}+T_{\mathrm{2}}-M(\mathrm{1}-y_{ijkf})\begin{array}{cc}& \end{array}\forall i\in I_{\mathrm{1}}，\forall j\in I_{\mathrm{2}}，

k\in K，f\in F(14)

t_i^f\ge T_i^f+D_{ij}/v_f-M(\mathrm{1}-y_{ijkf})\begin{array}{cc}& \end{array}\forall i\in I_{\mathrm{2}}，\forall j\in I_{\mathrm{1}}，

k\in K，f\in F(15)

T_i^f\ge t_i^f+s_i-M(\mathrm{1}-{\omega }_{ikf})\begin{array}{cc}& \end{array}\forall i\in I_{\mathrm{2}}，k\in K，

f\in F(16)

S_i\ge (t_i^k+s_{ik})z_{ik}+T_i^f{\omega }_{ikf}\begin{array}{cc}& \end{array}\forall i\in I，k\in K，f\in F(17)

l_i\le S_i\le L_i\begin{array}{cc}& \end{array}\forall i\in I(18)

公式(2)表示所有卡车的总配送时间，包括卡车总的行驶时间和受灾点总的服务时间；公式(3)表示卡车-无人机协同的总配送时间，包括以下2个部分。

（1）配送前的协同时间。若卡车k携带无人机f到达受灾点i，则卡车-无人机协同配送前的时间t_{ikf}^{\mathrm{1}}=\mathrm{0}。若无人机f单独前往受灾点i，则协同时间有以下2种情况。

①卡车k比无人机f先到达受灾点i，即，则先由卡车k服务该受灾点，再计算卡车k与无人机f的协同时间，包括卡车k在受灾点i等待和接收无人机f的时间，即t_{ikf}^{\mathrm{1}}=\mathrm{m}\mathrm{a}\mathrm{x}([t_i^f-(t_i^k+s_{\mathrm{i}})],\mathrm{0})+t_{\mathrm{U}}。

②卡车k比无人机f后到受灾点i，即t_i^k>t_i^f，则卡车k和无人机f的协同时间仅包含收回无人机f的时间，即t_{ikf}^{\mathrm{1}}=t_{\mathrm{U}}。

（2）配送中的协同时间。当卡车k和无人机f位于受灾点i，无人机f需要对集合I₂中的δ个受灾点进行配送，其中每个受灾点需要n_ikf 次配送，在无人机f对其中一个受灾点进行前n_ikf -1次配送时，卡车k需要在受灾点i等待无人机f。

①若受灾点j属于前δ-1个受灾点，无人机f对受灾点j的配送时间可以表示为

{\tau }_{ijkf}=(n_{jkf}-\mathrm{1})(\mathrm{2}\frac{D_{ij}}{v_f}+s_j+t_u+t_U)+\frac{D_{ij}}{v_f}+t_u

\forall i\in I_{\mathrm{1}}，j\in I_{\mathrm{2}}，k\in K，f\in F(19)

其中{\tau }_{ijkf}包括无人机f对受灾点j进行前n_jkf -1次配送的往返飞行时间、服务时间、起飞时间和回收时间，加上对受灾点j进行最后一次配送的起飞和飞行时间。假设h为δ个受灾点中的最后一个受灾点，则卡车-无人机在前δ-1个受灾点的协同时间可以表示为

t_{ikf}^{\mathrm{2}}=\sum _{j\in \vartheta \backslash \{h\}}({\tau }_{ijkf}+\mathrm{2}\frac{D_{ij}}{v_f}+s_j+t_U)\begin{array}{cc}& \end{array}\forall i\in I_{\mathrm{1}}，

j\in I_{\mathrm{2}}，k\in K，f\in F(20)

②当无人机f配送最后一个受灾点h时，卡车-无人机的协同时间可分为以下2种情况：无人机f配送完受灾点h后返回受灾点i与卡车k汇合，即y_{hikf} = 1，则卡车k与无人机f的协同时间包括无人机f的起飞和接收时间以及服务受灾点h的时间，即t_{ikf}^{\mathrm{3}}={\tau }_{ihkf}+\frac{D_{ih}}{v_f}+s_h+t_U；无人机f配送完受灾点h后不返回受灾点i，直接前往下一个受灾点，即y_{hikf} = 0，则卡车k与无人机f的协同时间截止于最后一次发射无人机f到受灾点h的时间，即t_{ikf}^{\mathrm{3}}={\tau }_{ihkf}-\frac{D_{ih}}{v_f}。

因此，卡车-无人机在受灾点i的协同时间t_ikf 可表示为

t_{ikf}=t_{ikf}^{\mathrm{1}}+t_{ikf}^{\mathrm{2}}+t_{ikf}^{\mathrm{3}}\begin{array}{cc}& \end{array}\forall i\in I_{\mathrm{1}}，k\in K，f\in F(21)

约束(4)表示集合I₁中的受灾点只能由卡车配送。约束(5)表示集合I₂中的受灾点只能由无人机配送。约束(6)保证卡车服务受灾点时出入流量平衡。约束(7)是避免卡车子回路约束。约束(8)表示不能超过无人机的里程限制。约束(9)表示无人机需要对一个受灾点进行多次配送。约束(10)表示受灾点的实际需求量不能超过卡车的载重。约束(11)表示卡车到达某受灾点的时间限制。约束(12)表示卡车离开某受灾点的时间限制。约束(13)表示卡车在某受灾点发射无人机的时间限制。约束(14)表示无人机到达下一个受灾点与卡车汇合的时间不小于卡车在上一个受灾点发射无人机的时间加上卡车的行驶时间。约束(15)表示无人机与卡车汇合的时间不小于从上一个发射点出发的时间加上两点之间的飞行时间。约束(16)表示无人机离开某受灾点的时间限制。约束(17)表示某受灾点服务完成的时间。约束(18)表示受灾点配送的时间窗。在模型的求解过程中，约束条件是通过罚函数机制在适应度评价阶段体现，当个体违反某约束时，目标函数值将被加上一个惩罚因子，使其在迭代过程中被自然淘汰。因此，约束条件虽未直接嵌入变量中，但在整个搜索与选择过程中始终发挥着限制与筛选作用，确保最终收敛的最优解一定在可行域内。

1.4　模型转化

由于部分受灾点的应急物资需求量是不确定的，为了避免所有受灾点出现极端情况，引入需求不确定水平参数Γ，表示最多只有Γ个受灾点的应急物资需求可以偏离其名义值达到极端偏差，而其余的受灾点则保持在名义状态。首先，定义添加到模型中的参数和变量：de_i 为受灾点i的需求名义值；d{\widehat{e}}_i为受灾点i的需求最大偏离值；Γ为需求不确定水平参数；μ_i 为应急物资需求偏离程度。

其中d{\widehat{e}}_i = de_i × ε，ε表示需求扰动系数，受灾点i受需求扰动后的实际物资需求d{\tilde{e}}_i = (1 + ε) × de_i。

在鲁棒优化模型中，使用区间来描述实际的应急物资需求。

d{\tilde{e}}_i\in [d{e}_i-d{\widehat{e}}_i{\mu }_i,d{e}_i+d{\widehat{e}}_i{\mu }_i]\begin{array}{cc}& \end{array}\forall i\in I(22)

其中，μ_i 表示d{\tilde{e}}_i的应急物资需求偏离程度。当μ_i = 1时，表示该受灾点应急物资需求正好偏离其名义值至最大值d{\widehat{e}}_i；若0 ≤ μ_i < 1，则表示偏离程度低于最大可能偏差。为了避免模型过于保守，应急物资需求偏离程度的区间\phi被定义为

\phi =\left\{{\mu }_i|\sum _{i\in I}{\mu }_i\le \Gamma ，\mathrm{0}\le {\mu }_i\le \mathrm{1}\begin{array}{cc}& \end{array}\forall i\in I\right\}(23)

其中，Γ用于反映决策者的风险偏好。Γ ∈ [0，N]，N为受灾点的数量，若Γ = 0，表示模型不考虑受灾点应急物资需求波动；若Γ = N，表示模型中的所有受灾点应急物资需求达到最大偏离值的极端情况；若0 < Γ < N，则实现了鲁棒性与性能之间的折中。Γ越大，表示模型越保守，决策者的风险厌恶程度越高。\sum _{i\in I}{\mu }_i\le \Gamma表示最多只有Γ个受灾点的应急物资需求可以达到极端偏差，而其他受灾点则必须低于这个极限。决策者可以根据实际情况选择合适的Γ值，以达到既不过于冒险也不过于保守的效果，从而得到合适的路径规划方案。

考虑应急物资需求的不确定性，将μ_i 代入原确定性模型中的约束(9)和(10)，得到以下表达式。

\sum _{i\in I_{\mathrm{2}}}\sum _{f\in F}\left(d{e}_i+\begin{array}{c}\mathrm{m}\mathrm{a}\mathrm{x}\\ {\mu }_i\in U\end{array}d{\widehat{e}}_i{\mu }_i\right)w_{ikf}e+

\left(d{e}_i+\begin{array}{c}max\\ {\mu }_i\in U\end{array}d{\widehat{e}}_i{\mu }_i\right)z_{ik}e\le Q_k\begin{array}{cc}& \end{array}\forall k\in K(24)

\left(d{e}_i+\begin{array}{c}max\\ {\mu }_i\in U\end{array}d{\widehat{e}}_i{\mu }_i\right)w_{ikf}e\le Q_f{n}_{ikf}\begin{array}{cc}& \end{array}\forall i\in I_{\mathrm{2}}，

k\in K，f\in F(25)

根据强对偶定理，通过引入对偶变量θ和ϑ_i，∀i ∈ I，将最大化问题转化为最小化问题，公式(24)可等价于

\sum _{i\in I_{\mathrm{1}}}d{e}_i{z}_{ik}e+\sum _{i\in I_{\mathrm{2}}}\sum _{f\in F}d{e}_i{w}_{ikf}e+\theta \Gamma +\sum _{i\in I}{\vartheta }_i\le Q_k

\forall k\in K(26)

\theta +{\vartheta }_i\ge d{\widehat{e}}_i{z}_{ik}e\begin{array}{cc}& \end{array}\forall i\in I_{\mathrm{1}}，k\in K(27)

\theta +{\vartheta }_i\ge d{\widehat{e}}_i\sum _{f\in F}{w}_{ikf}e\begin{array}{cc}& \end{array}\forall i\in I_{\mathrm{2}}，k\in K(28)

\theta ,{\vartheta }_i\ge \mathrm{0}\begin{array}{cc}& \end{array}\forall i\in I(29)

同理，公式(25)可等价于

d{e}_i{w}_{ikf}e+\theta \Gamma +\sum _{i\in I}{\vartheta }_i\le Q_f{n}_{ikf}\begin{array}{cc}& \end{array}\forall i\in I_{\mathrm{2}}，k\in K，

f\in F(30)

\theta +{\vartheta }_i\ge d{\widehat{e}}_i{w}_{ikf}e\begin{array}{cc}& \end{array}\forall i\in I_{\mathrm{2}}，k\in K，f\in F(31)

因此，研究的目标函数为公式(1)，约束条件为公式(4)—(8)、(11)—(23)、(26)—(31)。

2　算法设计

卡车-无人机协同配送属于NP-hard问题。突发事件发生时对应急物资配送的时效性要求高，需要在有限的时间内获得最优解方案。自适应大规模邻域搜索算法是一种优化的邻域搜索方法，与其他启发式算法相比，在求解效率和结果质量上表现更为优越。因此，在此基础上设计一种改进的自适应大规模邻域搜索算法(IALNS)进行求解。

2.1　编码

为满足卡车载重约束，生成初始解。将所有受灾点按其时间窗的最晚送达时间升序排序，采用贪婪策略优先处理截止时间最紧的受灾点。所有路线的第一个位置编码为0，表示所有车辆从应急配送中心出发。根据可达性将受灾点按照路径特点分成2类，一类是由卡车负责配送的受灾点，一类是卡车无法到达、由无人机负责配送的受灾点。依次遍历排序后的受灾点，随机选取一辆卡车并计算其剩余载重，若分配的受灾点需求超出卡车剩余载重，则返回重新选择车辆，否则将该受灾点插入到由此辆卡车和无人机负责配送的路线中。重复以上操作，直到所有受灾点分配完毕。以上编码操作对约束(4)—(10)进行了处理。这种编码既利用贪婪策略快速构造符合时间窗约束的路径，又通过随机选择车辆保持解的多样性，为后续IALNS算子的破坏和修复提供了丰富的初始解。

生成初始解的卡车-无人机路径如图2所示，红色数字表示由无人机负责配送的受灾点。k₁，k₂和k₃表示3辆卡车分别从应急配送中心出发，依次配送各受灾点。如卡车2从应急配送中心出发，依次配送受灾点15和受灾点14，其中，在受灾点15发射无人机，对受灾点19，20，17以及21进行配送，当无人机配送完受灾点21，返回到受灾点15，和卡车共同前往受灾点14，无人机从受灾点14出发，对受灾点16和18进行配送，配送完成后返回受灾点14与卡车汇合。

2.2　解码

（1）卡车-无人机协同配送策略。确保无人机符合其里程限制的解码步骤如下。

步骤1：当卡车在受灾点i发射无人机到受灾点j时，无人机的剩余可飞行距离D_f = \lambda-D_ij，若D_f < D_ij，表示无人机无法配送受灾点j，将该受灾点标记为违反约束点重新计算。

步骤2：如果下一个受灾点P ∈ I₂，无人机从上一个受灾点先返回受灾点i与卡车汇合，再配送受灾点P，则转回步骤1，否则转到步骤3。

步骤3：卡车从受灾点i出发到下一个受灾点与无人机汇合。

步骤4：若无人机从受灾点j到受灾点h与卡车汇合，计算D_jh，若D_jh > D_f，转到步骤5，否则转到步骤6。

步骤5：无人机返回受灾点i与卡车汇合。

步骤6：无人机前往受灾点h与卡车汇合。

（2）配送时间计算。

步骤1：遍历集合I₁中的受灾点，计算卡车的配送时间；遍历集合I₂中的受灾点，采用卡车-无人机协同配送策略计算协同配送时间。

步骤2：计算各受灾点的服务时间，检查是否违反时间窗约束，若违反，则在该解中添加一个惩罚因子，并将这些受灾点返回重新计算；否则根据公式(1)计算总配送时间，即目标函数值。

2.3　算子设计

2.3.1　删除算子设计

按照模型，设计以下5种删除算子，删除算子示例如图3所示。

（1）随机路线删除。在当前解中随机挑选一条路线，选择大于或等于n个受灾点进行删除，生成一条新的路线。如图3a所示。

（2）违反约束删除。对于给定的解，检查该受灾点是否违反约束，若违反，则删除该受灾点。重复该过程，直到路线中没有违反约束的受灾点。如图3b所示。

（3）随机受灾点删除。首先决定需要删除的受灾点数量n，然后随机选择一条路线，在该路线中随机选择受灾点进行删除，直到n个受灾点全部删除完毕。如图3c所示。

（4）最大保留点删除。在当前解x中，删除n个配送时间最长的受灾点。删除受灾点i所节约的时间\mathrm{\Delta }Time(i，x) = f (x) - f_-i (x)，f (x)为x的目标值。

（5）相关度删除。相关度删除是由Shaw提出的，指随机选择一个受灾点进行删除，然后根据公式(32)计算与路线中其他受灾点的相关度。由于受灾点集合分为I₁和I₂，因此只能计算同一个集合中的相关度。如i，j ∈ I₁，且i ≠ j，则

Q(i,j)={\partial }_{\mathrm{1}}\times \frac{d_{ij}}{\mathrm{m}\mathrm{a}\mathrm{x}(d_{ij})}+{\partial }_{\mathrm{2}}\times \frac{|l_i-l_j|}{\mathrm{m}\mathrm{a}\mathrm{x}(|l_i-l_j|)}+

{\partial }_{\mathrm{3}}\times \frac{|d{e}_i-d{e}_j|}{\mathrm{m}\mathrm{a}\mathrm{x}(|d{e}_i-d{e}_j|)}\begin{array}{cc}& \end{array}\forall i，j\in I_{\mathrm{1}}(32)

式中：d_ij 表示受灾点i到受灾点j的距离；|l_i -l_j |表示受灾点i，j之间的初始时间差；|de_i -de_j |表示受灾点i，j之间的名义需求差；∂₁，∂₂，∂₃分别表示各部分的权重。计算完成后，选取相关度最大的同类型受灾点进行删除，直到n个受灾点删除完毕。

2.3.2　修复算子设计

将无人机负责配送的受灾点插入到卡车路线中，设计以下3种插入算子。

（1）随机插入。在路线的任意位置随机插入一个被删除的受灾点。

（2）贪婪插入。将被删除的受灾点插入到路线的最优位置，使总时间增量最小。对于每一个被删除的受灾点，将它重新插入到路线中，得到一条新的路径，选择时间增量最小的路径，并重复此过程，直到所有被删除的受灾点都被重新插入到路径中，最终得到新的解x^{\text{'}}。

（3）后悔值插入。将被删除的n个受灾点以插入后比较时间后悔值大小的方式插入到路线中。时间后悔值是指将受灾点插入到最佳位置和次佳位置的时间差。使用\mathrm{\Delta }{T}_i^p表示受灾点i的第P个最优插入位置，后悔值可以计算为R_i=\mathrm{\Delta }{T}_i^{\mathrm{2}}-\mathrm{\Delta }{T}_i^{\mathrm{1}}。计算完所有被删除受灾点的后悔值后，可以获得第一个受灾点的插入位置，重复该步骤，直到所有被删除的受灾点插入到路线中。

以上删除算子通过随机或策略性地从当前可行解中剔除若干受灾点，打破原来的路径结构；随后修复算子在所有可能的插入位置中通过随机插入、贪婪插入或以最小化成本增量为目标插入的方式，将这些受灾点重新安置，从而在“破坏”“构建”的过程中既能跳出局部最优，也保证新生成的解不比原解差。

2.3.3　自适应策略

算法在迭代过程中会根据算子的得分和迭代次数动态调整算子的权重，使用轮盘赌策略选择删除算子和修复算子。在更新解的过程中，若当前解中的受灾点没有违反约束条件，则选择另一种删除算子，其他算子依据自适应策略进行选择。所有算子的初始权重设为1，并在每次迭代时根据公式(33)进行更新。

{\omega }_d=\left\{\begin{array}{c}{\omega }_d{}_{}{}_{}{}_{}{}_{}{\mu }_d=\mathrm{0}\\ (\mathrm{1}-\rho ){\omega }_d+\rho \times {\frac{s_d}{{\mu }_d}}_{}{}_{}{}_{}{}_{}{\mu }_d>\mathrm{0}\end{array}\right.(33)

式中：ω_d 表示权重；s_d 表示算子的得分，s_d=s_d^{\mathrm{1}}+s_d^{\mathrm{2}}+s_d^{\mathrm{3}}，s_d^{\mathrm{1}}表示更新获得的解x^{\text{'}}优于全局解x\mathrm{*}，s_d^{\mathrm{2}}表示不优于全局解x\mathrm{*}但优于当前解x，s_d^{\mathrm{3}}表示不优于当前解x但以模拟退火概率接收当前解；μ_d 表示算子的迭代次数；ρ = 0.8，表示权重更新因子。各算子的初始得分为0，在迭代过程中会不断进行更新。

2.4　算法流程

通过设计删除算子和修复算子提高解的多样性，充分探索解的空间，同时通过模拟退火过程更新解，保证解的收敛性。IALNS算法通过动态调整权重和自适应策略来删除和插入受灾点，不断地迭代更新当前解，直至找到最优解。IALNS算法流程图如图4所示。

3　算例分析

由于考虑需求不确定的卡车-无人协同的路径规划问题研究较少，缺乏与模型完全匹配的算例。因此，以Solomon算例为基础，改变路网结构及参数，构造模拟算例来验证模型和算法的有效性。

为了符合模型特点，参考市场情况和文献[16]、[18]，货运卡车的载重范围通常在0.5~2 t之间，选定600 kg取值，可以满足大批量应急物资运输需求。参考主流无人机的实际载荷能力，20 kg可覆盖紧急医疗包、小型急救设备等关键应急物资的运载需求。因此，设置卡车、无人机载重分别为Q_k =600 kg、Q_f =20 kg，平均运行速度分别为v_k = 15 m/s、v_f =25 m/s，无人机的出发时间T_u 和回收时间T_U 均为20 s，需求不确定水平参数Γ = 0，3，6，9，12。由于突发事件发生后，受灾点对应急物资的需求具有紧迫性，因此设定每个受灾点的服务时间窗为30 min。

3.1　基本算例求解

当算例规模很大时，删除和修复操作的搜索空间呈指数级增长，单次破坏后找到“更好”的修复解变得更加困难，往往会反复产生同质解，导致迭代陷入局部最优循环。因此，采用Solomon算例C101和RC101中的25个需求点算例进行求解。为符合模型特征，将配送点按照3∶2划分为卡车配送点和无人机配送点。对每个算例进行10次计算，取平均值，不同不确定水平参数的计算结果如表4所示，卡车-无人机路线图如图5所示，最优值收敛曲线图如图6所示。

表4中，KT表示卡车配送时间，min；FT表示无人机配送时间，min；KFT表示卡车-无人机协同配送时间，min；TT表示总配送时间，min；CT表示计算机的运行时间，s。

根据表4的计算结果可以得出，①应急物资配送的总时间等于卡车的配送时间加上卡车-无人机协同配送时间，与目标函数相符。②随着Γ数值的增加，FT的数值变化较小，说明Γ的改变对无人机的配送时间影响不大。KT和TT的数值波动较大，说明Γ通过影响卡车的配送时间，进一步影响总配送时间。由于卡车的配送时间受Γ值改变的影响，使KFT的数值在小范围内变动。

由图5可以看出，Γ值的改变也会引起卡车无人机的路线变化。随着Γ值的增加，部分受灾点的应急物资需求也随之增加，由于卡车与无人机共同使用卡车的最大载重，Γ值增加后，原来的一组卡车-无人机可能无法满足此路线的受灾点应急物资需求，因此需要根据需求变动重新选择路线。如图5a所示，在Γ = 0时，表示不存在受灾点需求波动，图5b中，Γ = 6，表示存在6个受灾点的应急物资需求产生波动，为了满足在需求波动下卡车路径依然可行，需要重新调整路线，因此图5a和图5b中的部分路线产生了变化，进一步验证了IALNS算法能够根据实际情况合理规划配送路径，达到最小化总配送时间的目标。

由图6可以看出，算法可以在短时间内收敛，找到最优解，具有可行性。

综上所述，实验结果表明通过调整需求不确定水平参数，可以进一步优化应急物资配送的路径，确保决策者在面对不同情况时做出适当的选择，使配送方案有效且可靠。

3.2　算法规模分析

对不同规模的Solomon算例进行分析。C1，R1与RC1分别代表受灾点位置集中分布、随机分布以及集中随机相结合分布。算例按受灾点数量分为25，50，100这3种规模计算。不同规模算例的计算结果如表5所示，在不同规模的算例中，IALNS算法能够在给定的迭代次数范围内收敛。随着算例规模增大，迭代次数也不断增加，这是因为随着规模的增大，可行解的数量也随之增加，算法需要迭代多次来搜索更优的解。

3.3　算法对比分析

将IALNS算法与遗传算法(Genetic Algorithm，GA)和粒子群算法(Particle Swarm Optimization，PSO)进行比较。为保证算法对比的公正性，参考已有研究中的参数设置区间，设定GA的种群规模为200，交叉比例为0.9，变异概率0.1^[21]；参考陈峰和刘志等的研究，改进的粒子群算法采用动态惯性权重，范围约为0.4~0.9，因此设定PSO的惯性权重为0.5，自我认知因子为1.5，社会认知因子为1.5，粒子群的规模为200^[22-23]，为避免因调参带来的偏差影响结论的公正性，参数未进行特别调优。每种算法运行10次，不同算法计算结果对比如表6所示，不同算法算例收敛曲线对比如图7所示。

根据表6和图7可以看出，在算法计算结果上，IALNS算法计算出的目标函数值优于GA和PSO两种算法。GA、PSO与IALNS算法的平均GAP分别为15.18%，12.91%，其中，GAP = (对比算法的TT-IALNS的TT)/IALNS的TT × 100%。由于初始解采用了基于时间窗的“贪婪”策略，初始解已具备较高质量，算法在局部解空间中容易快速获得接近最优的解，且算例规模较小，算法容易在空间内快速进行搜索。因此，3种算法都能在短时间内收敛，差距较小。

3.4　灵敏度分析

3.4.1　需求不确定水平参数灵敏度分析

使用Solomon算例中的C101_050算例分析需求不确定水平参数对总配送时间的影响。将需求不确定水平参数Γ设置为0~12，扰动系数ε设置为20%，30%，40%和50%，需求不确定水平参数灵敏度分析结果如表7所示。

由表7可以看出，随着需求不确定水平参数以及扰动系数的增加，总配送时间(TT)也在递增，这是由于受灾点的需求波动会改变卡车原始的配送路线和配送方案，使卡车和无人机的载重限制随着扰动系数增加而改变。通过选择合适的Γ值，决策者可以在解的鲁棒性和目标性能之间取得平衡。较小的Γ值会使解更接近于名义情况，较大的Γ值则提供更高的鲁棒性。

3.4.2　无人机载重灵敏度分析

基于Solomon算例中的C101_050算例对单架无人机载重进行灵敏度分析，改变无人机载重限制，通过求解10次取最优目标函数值，无人机载重灵敏度分析结果如表8所示。

由表8可以看出，随着无人机的载重增加，总配送时间(TT)、无人机配送时间(FT)以及卡车-无人机协同配送时间(KFT)相应减少。这是由于单架无人机的载重增加，使无人机的配送次数减少，从而减少了与无人机相关的配送时间。结果表明通过增加无人机载重，可以提升应急物资配送效率。

3.4.3　无人机续航里程灵敏度分析

为分析无人机续航里程\lambda对模型的影响，在C101_050算例的基础上，改变无人机续航里程，通过算法求解10次取最优目标函数值，无人机续航里程灵敏度分析结果如表9所示。

由表9可以看出，随着无人机的续航里程增加，总配送时间(TT)和卡车-无人机协同配送时间(KFT)相应减少。这是由于无人机的续航里程增加，使无人机在一条路线上能覆盖尽可能多的受灾点，从而减少与卡车的协同时间。结果表明通过增加无人机续航里程，可以提升应急物资配送效率。

4　结论与启示

突发事件发生后，考虑部分受灾点需求不确定对卡车-无人机协同的路径优化问题进行研究，提出鲁棒优化模型，研究发现该模型可以有效解决应急物资需求波动的问题，有助于确保卡车路径的可行性。研究结论可总结为以下3个方面。①针对模型提出IALNS算法，通过算例分析，验证了IALNS算法能够根据实际情况合理规划卡车-无人机的协同配送路径，实现总配送时间最小化的目标。②将IALNS算法与传统的遗传算法和粒子群算法进行比较，IALNS算法计算出的目标函数值优于GA和PSO两种算法，且3种算法都能在短时间内收敛，验证了IALNS算法的可靠性。③通过对需求不确定水平参数进行灵敏度分析，决策者可以通过选择合适的Γ值，在解的鲁棒性和目标性能之间取得平衡，从而避免决策过于保守。最后对无人机载重和续航里程进行灵敏度分析，结果表明通过增加无人机载重和续航里程，可以提升应急物资配送效率。

研究结论带来的启示包括：①卡车-无人机的协同配送策略在突发事件发生后可以提升应急物资的配送效率。②决策人员应根据突发事件的规模选择合适的无人机载重和续航里程，使无人机配送能力得到最大程度发挥。③决策者可以根据实际情况调节需求不确定性水平参数，从而得到合适的卡车-无人机路线。研究不足在于随着受灾点规模的增加，模型的求解效率和准确性会受到显著影响：一方面，受灾点数量的增长会导致卡车路径组合增多，使删除和修复算子在大邻域搜索中评估的候选解数量急剧增多，从而增加单次迭代的计算时长；另一方面，为了维持较高的解质量，往往需要增大种群规模或迭代次数，这进一步加重了计算负担。若引入更复杂的交通网络和更紧迫的时间窗，当前基于静态距离和硬时间窗约束的总时间计算与插入算子的评估机制可能难以准确反映实际情况的可行性，且在极端情况下容易产生大量非法解，削弱算法的收敛性。因此，在面对大规模、复杂交通网络以及更紧急的时间限制的问题场景时，需要进一步结合实时路况信息以及多阶段的优化方法，以平衡求解效率与解的准确性。

参考文献

[1] ZHANG G W， JIA N， ZHU N，et al.Robust Drone Selective Routing in Humanitarian Transportation Network Assessment[J].European Journal of Operational Research，2023，305(1)：400-428.

[2] 李超，江南，张兵. 铁路巡检无人机操控人员胜任力模型研究[J]. 铁道运输与经济，2025，47(8)：51-58.

[3] LI Chao， JIANG Nan， ZHANG Bing. Competency Model of Unmanned Aerial Vehicle Operators for Railway Inspection[J]. RailwayTransport and Economy，2025，47(8)：51-58.

[4] 赵明丽，马小龙，曹若飞. 基于无人机的铁路非正常接发列车作业方案设计[J]. 铁道运输与经济，2025，47(8)：30-39.

[5] ZHAO Mingli， MA Xiaolong， CAO Ruofei. UAV-Assisted Operation Design for Abnormal Train Reception and Departure in Railway[J]. Railway Transport and Economy，2025，47(8)：30-39.

[6] 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-109.

[7] 钟导峰，尹传忠，梁亚莉，等. 应急物资“火车-卡车-无人机”协同运输优化[J]. 铁道运输与经济，2025，47(8)：40-50，58.

[8] ZHONG Daofeng， YIN Chuanzhong， LIANG Yali，et al. Optimization of Train-Truck-Drone Cooperative Transportation for EmergencySupplies[J]. Railway Transport and Economy，2025，47(8)：40-50，58.

[9] DAS D N， SEWANI R， WANG J W，et al.Synchronized Truck and Drone Routing in Package Delivery Logistics[J].IEEE Transactions on Intelligent Transportation Systems，2021，22(9)：5772-5782.

[10] WANG Y， WANG Z， HU X P，et al.Truck-Drone Hybrid Routing Problem with Time-Dependent Road Travel Time[J].Transportation Research Part C：Emerging Technologies，2022，144.

[11] 罗永琪，陈彦如，冉茂亮. 带收益和时间窗的多行程卡车-无人机协同配送问题[J]. 控制与决策，2025，40(6)：1817-1826.

[12] LUO Yongqi， CHEN Yanru， RANG Maoliang. Multi Trip Truck-Drone Collaborative Delivery Problem with Revenue and Time Window[J]. Control and Decision，2025，40(6)：1817-1826.

[13] 彭 勇，黎元钧. 考虑疫情影响的卡车无人机协同配送路径优化[J]. 中国公路学报，2020，33(11)：73-82.

[14] PENG Yong， LI Yuanjun. Optimization of Collaborative Delivery Routes for Trucks and Drones Considering the Impact of the Epidemic[J]. China Journal of Highway and Transport，2020，33(11)：73-82.

[15] 高娇娇，郭秀萍. 考虑卡车无人机协同配送模式下的车辆路径问题研究[J]. 工业工程与管理，2024，29(3)：30-39.

[16] GAO Jiaojiao， GUO Xiuping. Research on Vehicle Routing Problem in the Collaborative Delivery Mode of Trucks and Drones[J]. Industrial Engineering and Management，2024，29(3)：30-39.

[17] 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-233.

[18] 李雨辰，牟海波，袁 梦，等. 区域限制下卡车-无人机联合配送多目标优化[J]. 深圳大学学报(理工版)，2025，42(2)：205-215.

[19] LI Yuchen， MOU Haibo， YUAN Meng，et al. Multi Objective Optimization of Truck-Drone Joint Distribution under Regional Restrictions[J]. Journal of Shenzhen University(Science & Engineering)，2025，42(2)：205-215.

[20] 付朝晖，李君宇，刘长石. 山区生鲜物流卡车-无人机联合集货路径规划[J]. 计算机工程与应用，2025，61(14)：332-342.

[21] FU Zhaohui， LI Junyu， LIU Changshi. Joint Cargo Collection Path Planning of Fresh Logistics Truck-Drone in Mountainous Areas[J]. Computer Engineering and Applications，2025，61(14)：332-342.

[22] 孟姗姗，郭秀萍. 卡车-无人机联合取送货模式下物流优化[J]. 系统管理学报，2022，31(3)：555-566.

[23] MENG Shanshan， GUO Xiuping. Logistics Optimization under Truck-Drone Joint Pickup and Delivery Mode[J]. Journal of Systems & Management，2022，31(3)：555-566.

[24] 蒋 丽，王洪艳，梁昌勇，等. 农村地区卡车与无人机协同配送路径优化[J]. 计算机工程与应用，2023，59(14)：306-314.

[25] JIANG Li， WANG Hongyan， LIANG Changyong，et al. Optimization of Collaborative Delivery Routes between Trucks and Drones in Rural Areas[J]. Computer Engineering and Applications，2023，59(14)：306-314.

[26] 梁 爽，陈彦如，孙智彬. 基于自适应大邻域搜索算法的无人机-卡车-代收点协同配送[J]. 工业工程与管理，2024，29(1)：119-132.

[27] LIANG Shuang， CHEN Yanru， SUN Zhibin. Collaborative Delivery of Unmanned Aerial Vehicle-Truck-Collection Point based on Adaptive Large Neighborhood Search Algorithm[J]. Industrial Engineering and Management，2024，29(1)：119-132.

[28] MOKARRARI K R， SHIRAZIAN S， AGHSAMI A，et al.A Stochastic-Fuzzy Multi-Objective Model for the Last-Mile Delivery Problem Using Drones and Ground Vehicles，A Case Study[J].Scientia Iranica，2024，31(11)：847-865.

[29] 刘长石，吴 张，周愉峰，等. 疫区应急物资供应的卡车-无人机动态协同配送路径优化[J]. 系统科学与数学，2022，42(11)：3027-3043.

[30] LIU Changshi， WU Zhang， ZHOU Yufeng，et al. Optimization of Dynamic Collaborative Distribution Path between Trucks and Drones for Emergency Supplies Supply in Epidemic Areas[J]. Journal of Systems Science and Mathematical Sciences，2022，42(11)：3027-3043.

[31] 胡大伟，张世鹏，刘慧甜，等. 应急响应初期卡车-无人机联合配送路径问题[J]. 长安大学学报(自然科学版)，2024，44(1)：105-119.

[32] HU Dawei， ZHANG Shipeng， LIU Huitian，et al. The Problem of Truck-Drone Joint Distribution Path in the Early Stage of Emergency Response[J]. Journal of Chang’an University (Natural Science Edition)，2024，44(1)：105-119.

[33] 龚 英，涂熳熳，周愉峰. 卡车-无人机协同的洪灾应急选址-路径鲁棒优化问题[J]. 计算机工程与应用，2025，61(14)：307-321.

[34] GONG Ying， TU Manman， ZHOU Yufeng. Truck-Drone Collaborative Flood Emergency Site Selection-Path Robust Optimization Problem[J]. Computer Engineering and Applications，2025，61(14)：307-321.

[35] 于逸然，赖惠成，高古学，等. 基于遗传算法和A*算法的多农机协同作业优化方法[J/OL].系统仿真学报，1-12. (2024-07-31)[2025-04-10].

[36] 陈 峰，丁 泉，吴 乐，等. 混合驱动的粒子群算法[J]. 计算机工程与应用，2024，60(8)：78-89.

[37] CHEN Feng， DING Quan， WU Le，et al. Hybrid Driven Particle Swarm Algorithm[J]. Computer Engineering and Applications，2024，60(8)：78-89.

[38] 刘 志，宋 威. 搜索引导网络辅助的动态粒子群优化算法[J]. 计算机科学与探索，2024，18(12)：3189-3202.

[39] LIU Zhi， SONG Wei. Search Guided Network Assisted Dynamic Particle Swarm Optimization Algorithm[J]. Journal of Frontiers of Computer Science & Technology 2024，18(12)：3189-3202.

基金资助

福建省社会科学规划重点项目(FJ2024MGCA027)

福建省科协科技创新智库课题(FJKX-2024XKB014)