标题：Optimising vertical deliveries with integrated hybrid drone-truck systems
DOI：DOI: 10.1080/00207543.2025.2536193

摘要

最后一公里配送占据供应链总成本的75%以上¹，在探索最后一公里问题中，无人机占据了巨大的优势。但仍然有三个制约因素：续航里程和负载能力有限、电池的容量限制使得飞行时间较短、合规性制约需要对多个无人机配送系统就行高效的协调控制²
我们的目标：最大化无人机利用率（缩短总配送时间）和最小化资源浪费。而其中的无人机的能耗取决于有效载荷（与航程相关联）、风况和坡度。
本文主要的创新：提出了一种精确的三维空间优化模型来优化路线和充电，对垂直维度进行建模并考虑了离开配送节点时的实时剩余载荷、有效载荷承载能力以及无人机电池容量以及重力影响等因素，以优化无人机-卡车配送垂直路径的能量消耗。也就是把原来2d的整数规划问题变为考虑垂直空间状态的3d整数规划问题。
论文假设：单卡车带多无人机，其装载包裹、更换电池和起飞时间都被忽略。无人机的电池容量、负载能力、飞行速度没有差异性，电池容量和承载能力足够就可以在一条线路上向多个客户送货。卡车到后无人机才能在特定站点取货，而且在等待卡车时不许悬停。

overall business strategy as it can incur up to 75% of the total SC costs (Gevaers, Van de Voorde, and Vanelslander 2014; Madani, Ndiaye, and Salhi 2024) ↩︎
The first is related to the drones’ limited range and payload-carrying capacity. The second results from the limited capacity of current battery technology, leading to short flight times which in turn impact delivery operations. The third constraint is related to safety/security and regulations, and requires an efficient coordinated control of several drone-based delivery systems. ↩︎

问题设定

向客户集合 C 送货，使用 R 架同构无人机并由卡车作为移动发射与回收平台。卡车不仅能作为移动仓库，还可以由直接完成部分配送。从仓库出发，完成所有配送后返回仓库。每个客户$i∈C$ （x,y,z）需求 $w_i$重量并可能位于特定高度（即三维坐标中的 z）。卡车配有可更换电池，并负责将无人机运送到配送区域内的不同发射地点或直接在指定地点直接向客户运送包裹。如果卡车停在有顾客的地点，则卡车必须向该地点的所有顾客完成送货，也就是说该位置不管是高度为0的地点还是一些额外停靠点S都作为卡车停靠点（停靠点的所有客户都由卡车来送）。无人机具有最大载重 $Q$、电池容量 $P$、速度 $s^D$、以及同一停靠点最多起飞次数 $v_{max}$，无人机每公里成本 $c^D$、卡车每公里成本 $c^T$ 使用笛卡尔坐标系（Cartesian coordinate system）来计算节点之间的距离以便于嵌入高度数据，对于无人机的距离使用欧氏距离$δ^{D}_{ij}$来衡量，对于卡车的行驶距离使用曼哈顿距离$d^{T}_{ij}$度量。对于一些包含其他因素的路径计算，可以考虑A-star和Dijkstra算法来进行计算。在本文中，为了在同一停靠点实现多次发射，本文通过将每个卡车停靠点复制$v_{max}$ 次来扩展原始路径网络（这样可以避免搞一套新的轮子，直接在只起降一次的轮子上用，用图规模变大的代价换取不用引入3d决策变量改进算法）。下图为 $v_{max}$=3 的网络示例。

作者用“水平等效距离”把这个效果折算进“距离”里：

d_{ij}^D = \delta_{ij}^D (1 + \alpha \sin \theta_{ij})

上升：sin⁡θ>0→ 等效距离变大 → 能耗更高
下降：sin⁡θ<0 → 等效距离变小 → 能耗更低
α 是“高度影响强度”（实验标定，引用自 Abeywickrama et al. (2018)）

然后把每段飞行能耗写成：

E_{ijr}=f(x_{ijr},q_{ijr},s^D)\cdot d_{ij}^D

这里 f(x) 的意思是：单位距离能耗不是常数，$x_{iJ}$为1代表着使用无人机运送货物，会随着载重 $q_{iJ}$、速度等变化。 只要使用无人机运送货物，就按照$E_{ijr}$来增加$w$，如果无人机在卡车上被运走，那就不加飞行能耗，但是时间按照卡车行驶时间走。无人机在卡车到达后起飞（允许在停靠点等待），起飞后则不能悬停等待卡车，在汇合点要求无人机到达时间 ≥ 卡车到达时间无人机离开时间≤卡车离开时间，且无人机必须在卡车离开前完成会合。（卡车可以等无人机降落无人机必须在卡车走之前走人）

求解算法

通过一种启发式求解方法，结合了Relax-and-Fix（RF）分解法与列生成（CG）算法。

生成卡车路径

为最终的为最终的无人机-卡车配送决策确定一个潜在的卡车路径，通过求解 3.4里面给出的(3)-(43)的限制，将所有决策变量除了 $y_{ij}$（卡车路径选择）以外的变量进行放松（relax）(这期间固定$y_{ij}$)然后基于该卡车路径检查是否能生成无人机路线（感觉其实按照part2那样去跑集群就算检查了），若无法找到无人机路径，则让卡车在路径中至少再增加一个停靠点。对于卡车路径上卡车在每个停靠点的停留时间，由卡车为该位置的客户提供服务的时间和剩余的时间 总配送时间减去行驶和服务时间后的剩余的时间用来平均分配给所有停靠点来进行无人机的起飞和回收，基于这一假设，计算出每个停靠点的到达时间 ARRi和离开时间 DEPi,并将这些时间与卡车路径、已访问的停靠点集合 $S_\mathrm{visited}$、已服务客户集合$C_\mathrm{serv}$、总卡车行驶时间 $t^T$、以及引起的总成本$c^T$存储，供下一步使用。

划分生成集群

我个人的观感来看的话可以考虑使用VNS之流实现这一部分而非列生成算法，就是可能pk不过

按照卡车路径确定无人机的最优路线以最小化总配送成本。文章引入集群划分模型 (set partitioning formulation),依赖于所有可行的无人机路径集合$M$,决策变量$\lambda_m$ ($m\in M$),以及定义在客户$i\in C\setminus C_\mathrm{serv}$上的参数$\alpha_m^D$:

\lambda_m=\begin{cases}1&\text{如果无人机路径}m\in M\text{ 被选择}\\0&\text{否则}&\end{cases}

\boldsymbol{\alpha}_m^D=\begin{cases}1&\text{如果无人机路径}m\in M\text{ 服务客户}i\in C\setminus C_{\text{serv}}\\0&\text{否则}&\end{cases}

目标函数为：$\min\sum c_m^D\lambda_m$

由于在于考虑所有可行路径集合M 会导致计算量过大，因此使用列生成算法(CG)来逐步生成可行路径。每次求解的限制版主问题(RMP) 仅包含一个较小的路径子集$M^{\prime}$其实也就是先生成的可以飞无人机的卡车路径 ,而新的可行路径在先前子集的基础上通过迭代生成。
以下是列生成的过程：

通过求解 RMP,获取对偶变量$(\pi,\theta)$ ,并在定价子问题 (SP)中用于确定是否存在负的减价路径 (即新生成的路径)。每次迭代中，如果存在负的减价路径，就将该路径加入到RMP 中。路径的减价成本$r_m^c$计算公式为：

r_m^c=c_m^D-\sum_{i\in C\setminus C_{\mathrm{serv}}}\alpha_m^D\pi_i-\theta

目标是寻找减价最小的路径，以最小化总成本。这是一个资源约束最短路径问题(RCSP) ,属于 NP-hard 问题。反复求解并更新路径到一个接受的上界。

实验大PK

无人机的能量消耗率按照D’Andrea (2014)进行计算

数据集生成

一点数据的配置 客户的需求$w_i\sim\mathcal{U}(0.5,2)$。卡车服务于停靠站 i 的所有户所需的时间$t_{i}^{T,\mathrm{serv}}$定义为 $t_{i}^{T,\mathrm{serv}}=t_{i}^{\mathrm{fixed}}+t_{i}^{\mathrm{max}}+t^{\mathrm{variable}}n_{i}^{c}$。其中，$t_{i}^{\mathrm{fixed}}$ 表示准备包裹所需的固定时间，$t^{\mathrm{variable}}$ 表示将包裹送达每位客户所需的时间，$t_{i}^{\mathrm{max}}$ 表示到达最高海拔客户处并返回卡车所需的时间。

在4km的指定配送区域内随机生成卡车停靠点并给出停靠点坐标：（x,y,0）。然后随机选择1~3个客户丢到不同的z高度上，按照上面的配置各生成了 40 个不同的问题实例，其中卡车停靠站的数量 n 从 10 到 25 不等，各 10 个实例。