引言

近年来，随着全球劳动力成本持续攀升、自主智能技术不断迭代成熟，以及全社会环保意识的日益增强，依托自动化设备开展无人配送已逐渐突破传统物流模式的局限，成为物流行业转型升级的主流发展趋势，受到学术界与产业界的广泛关注（Li等；Srinivas等）。在各类无人配送技术与设备中，无人机凭借其独特的技术优势实现了快速发展与广泛应用，相较于传统地面配送工具，无人机不仅具备飞行速度快、配送效率高的特点，还能有效减少地面交通拥堵带来的延误，降低燃油消耗与碳排放，契合绿色物流的发展理念，同时在配送范围的扩展性与场景适配的灵活性上表现突出，能够满足不同区域、不同类型的配送需求（Zhou等）。

1 国内外研究现状

1.1 无人机配送问题

Zou等和Yang等近期的一项研究表明，低空经济的快速崛起，为物流配送模式创新注入了新动能。无人机具备规避地面交通拥堵的核心优势，在城市拥堵区域或偏远地区不仅能够实现更高效的配送服务，与现代物流高质量发展的需求非常契合。

1.2 中间站点在物流网络中的作用

中间站点，又称转运设施，是支撑末端配送高效开展的核心枢纽，在优化配送流程、提升运营效率中发挥着不可或缺的重要作用。早期研究的中间站点更多作为多级配送网络的交会节点，用于提取、暂存或转运货物。Baldacci等、Santos等多位学者对此问题展开了研究。Zhou等将转运设施融入两级配送网络，创新性地构建了包含转运环节的网络架构，为多级配送网络中的转运设施布局与路径规划提供了有效解决方案。

2 PDPTW-D-DDS模型概述

2.1 问题描述

本问题的研究对象PDPTW-D-DDS可形式化定义在有向图上：其中由物理网络中考虑的所有顶点组成，即包含了所有取货顶点、送货顶点、卡车仓库、无人机接驳柜和无人机充电站在内的物理节点；弧集是连接顶点中所有节点的有向路径集合，代表节点间的可行运输路径。中的每条弧线都有一个与之相关的行驶距离、卡车在该弧段上的行驶时间。无人机在该弧段上的行驶时间，为简化模型，将货物在各节点的装卸货时间均纳入对应路径的行驶时间中，不再单独进行计算。设为卡车行驶在有向弧上的运输成本；设为无人机在有向弧上的电池耗电量，其计算公式为，其中为无人机在单位时间内的耗电量系数，为无人机的自重，为无人机的实时有效负载。设为无人机单位电量的充电成本，则无人机在有向弧上的电池消耗成本可表示为。

参考Su等的研究方法，本文对物理顶点集进行针对性的逻辑重构处理，具体处理方式为：在每个接驳柜中生成所有顾客点的虚拟逻辑节点，为每个配送请求在各个无人机接驳柜处新增一对逻辑取货节点与逻辑送货节点，一个取货点在各个接驳柜中对应一个取货虚拟节点，相应地，一个送货点在接驳柜中对应一个送货虚拟节点，即针对个客户请求，每个接驳柜均对应生成个逻辑取货点和个逻辑送货点（图1）。

2.3 PDPTW-D-DDS模型构建

结合表1中定义的补充符号与决策变量，下文将给出所研究问题的混合整数线性规划（MILP）模型。

目标函数（3.1）旨在最小化卡车行驶和无人机电量消耗的总成本。

3 PDPTW-D-DDS优化算法设计

3.1 解的表示

在本文所设计的遗传算法中，每个求解方案均通过三组染色体共同表征，三者共同构成一个完整可解析的配送方案，这三组染色体分别为卡车路线染色体、请求类型染色体和无人机接驳柜染色体。其中，卡车路线染色体的核心作用是明确每辆配送卡车的客户访问顺序与行驶路径；请求类型染色体主要用于界定每个配送请求的具体执行模式，明确其采用纯卡车或卡车无人机配合两种方式选其一完成配送任务；无人机接驳柜染色体则专门对应其服务的每个配送请求，用于标识该请求在配送过程中所关联的两个不同的无人机接驳柜，明确卡车与无人机之间的包裹交接位置。

3.2 初始种群的构造

本小节在构造初始种群前先对所有请求进行分类。本文将所有客户配送请求的集合记为，我们以每个配送请求的取货点与送货点之间的距离作为核心划分依据，将集合进一步划分为两个互不重叠的子集，即0类请求集合与1类请求集合，分别对应单独配送请求与协同配送请求。具体的划分规则如下：预设一个距离阈值，对于任意一个客户配送请求，若其取货点与送货点之间的直线距离低于该预设阈值，则该请求将以极大的概率被分配至0类请求集合，优先采用单辆卡车直接配送的方式；若其取货点与送货点之间的实际距离高于或等于该预设阈值，则该请求被分配至1类请求集合的概率更高，优先采用两辆卡车与一架无人机协同配送的方式。

3.3 基于动态规划的染色体解码与评估

在PDPTW-D-DDS中，为更直观地阐释无人机路线的构成逻辑与规划思路，本文结合图2进行具体说明，该图清晰地展示了与3个1类请求、6个无人机接驳柜相关联的两条无人机路线实例。为便于后续的路线描述与算法求解，本文引入“飞行段”这一核心概念，将其定义为：无人机为完成单个1类请求的包裹转运任务，在该请求所关联的两个接驳柜之间的单次飞行过程。本文将所有1类请求对应的飞行段集合记为，基于此，构建有向图，其中顶点集由飞行段集合与无人机充电站集合共同构成，即，每条顶点分别对应一个飞行段或一个无人机充电站；边集由所有满足的顶点对构成，即.，每条边对应无人机的一段空载飞行过程，其权重为该段飞行的电池消耗成本。

无人机路线规划的核心目标可进一步转化为：通过优化无人机的飞行路线与任务组合，来最小化所有用于完成中请求配送任务的无人机的空载飞行总电池消耗成本。为高效求解上述有向图模型下的无人机路线最优解，第一项前置工作为生成飞行段访问顺序生成，按照特定的规则生成所有飞行段的初始访问序列，为后续的飞行段分组与无人机分配提供基础；第二项前置工作为飞行段聚类与无人机分配，采用层级聚类方法，将所有飞行段划分为若干个合理的分组，每个分组对应一架无人机，同时确定每架无人机对应的飞行段分组，明确无人机的任务范围。完成上述两项前置工作后，即可调用动态规划程序。在给定了飞行段访问顺序的前提下，本文所设计的动态规划算法核心思路如下：假设现有架无人机可供调配，且存在个需由无人机执行的飞行段任务，所有飞行段的执行顺序由集合表示，即。动态规划算法的每个阶段需完成一项核心决策：将单个飞行段或一组飞行段分配给某一架无人机执行，直至1类请求集合中的所有配送请求均完成分配。算法每个阶段的状态由剩余未分配飞行段数量和剩余可用无人机数量共同定义，记为状态。在初始状态下，剩余飞行段数量，剩余无人机数量。定义为：在状态下，某架无人机执行剩余个飞行段中前个飞行段时产生的空载电池消耗成本；其中，表示剩余个飞行段的序列，剩余个飞行段中的前个飞行段记为（该组前个飞行段可视为一个飞行段分组）。

最终，当剩余飞行段数量与剩余无人机数量相等时，此时得到的即为本文动态规划算法所要求解的最优成本，该最优成本对应无人机空载电池消耗最小的配送方案。

3.4 局部搜索算子

（）Swap-Ps：随机选取两条卡车路线，从每条路线中各随机选取一个取货顶点并进行交换。

（）Swap-Ds：从两条随机选取的卡车路线中，交换各自的送货顶点。该算子的操作逻辑与大致相同，核心区别在于：送货顶点需插入到对应取货顶点及用于包裹转运的无人机接驳柜之后，确保配送流程的合规性。

（）Request-Destroy-Repair：随机选取一个配送请求，将其关联的取货顶点和送货顶点从原卡车路线中移除，随后以一定概率将这两个顶点分别插入到另一条路线或两条不同的路线中。

（）B-Update：替换随机选取的一个配送请求所关联的两个无人机接驳柜。

（）Station-Relocate：该算子用于在路线内部对无人机接驳柜进行位置调整。

（）Request-Move：该算子是和算子操作的延伸。随机选取一个配送请求：若该请求属于0类请求集合，则重新定位其取货顶点和送货顶点，若该请求属于1类请求集合，则涉及两条卡车路线，需重新定位的顶点包括其取货（送货）顶点及其关联的取货（送货）无人机接驳柜。

（）Swap-TwoRequests-Order：随机选取两个1类配送请求，调整这两个请求所关联的飞行段在无人机服务序列中的访问顺序，通过顺序优化实现无人机路线成本降低。

（）Move-OneRequest-Order：随机选取一个1类配送请求，将其关联的飞行段移动到无人机服务序列中的新位置，优化飞行段组合方式，提升无人机路线的合理性。

（）Reshuffle：一次性对所有飞行段的访问顺序进行重新打乱排列，彻底改变无人机的服务序列，为动态规划算法提供全新的求解输入，进一步拓宽解空间搜索范围。

3.5 算法框架

针对PDPTW-D-DDS本文提出一种基于遗传算法的混合求解方法，HGADP的具体流程如图3所示。该算法首先进行种群初始化，生成可行解与不可行解这两类解，并将其分别存入可行子种群（记为）与不可行子种群（记为）。其中，违反卡车容量约束或客户时间窗约束的解，均归入不可行子种群。种群初始化完成后，算法进入迭代过程，直至满足终止条件后方可停止。本小节将定义为无改进迭代次数，将定义为算法允许的最长运行时间。在每次迭代过程中，先从整个种群中选取两个父代个体，通过交叉操作生成两个新的子代个体，随后子代个体以概率进行变异。变异完成后，对子代个体执行局部搜索操作以优化解的质量；若经过局部搜索后，子代个体仍为不可行解，则以概率通过局部搜索程序对其进行修复。

上述操作全部完成后，对子代个体进行评价，对于不可行子代个体，其适应度将包含一个惩罚项，该惩罚项会在迭代过程中动态调整，为提升遗传算法的求解性能。当任意一个子种群的规模达到，其中为每个子种群的最小规模，为每一代的个体数量时，HGADP算法将保留种群中质量最优的个个体，剔除剩余个体。若经过次迭代后，当前得到的最优解仍未取得任何改进，则启动种群多样性策略：保留种群中最优的个个体，删除其余个体，再调用算法3向种群中补充新的个体，直至每个子种群的规模均恢复至。

4 算例实验

4.1 实验设置

沿用该研究的分类方式，本文根据卡车容量与时间窗宽度的不同组合，将所有算例划分为AA、BB、CC、DD四类，具体参数组合分别为（60,15）、（60,20）、（120,15）和（120,20），以覆盖不同载荷约束与时间约束强度的场景。

4.2 算例对比

为初步验证HGADP算法的求解质量与效率，首先在小规模算例集上进行测试。算例命名规则为：“请求数_仓库数_接驳柜数_充电站数”，具体规模组合如下：4_2_2_1、5_2_2_1、6_3_2_1、7_3_2_1、8_3_2_2、9_3_3_2。表2汇总了两类方法的求解结果，包含双方找到的最优解的值（Best）及对应计算时间（TimeB）、平均解的值（Avg）及对应计算时间（TimeA）。实验结果显示在CPLEX未能求得最优解的场景中，HGADP算法能够稳定地找到质量更优的可行解；在CPLEX成功求得最优解的场景中，HGADP算法能够在相当或更短的时间内达到同等最优解水平。

算例		CPLEX Summary			HGADP Summary
		Best	TimeB	Gap	Best	TimeB	Avg	TimeA	Gap
				(%)					(%)
4_2_2_1	AA	398.53	0.55	0.00	398.53	3.39	419.14	4.73	0.00
	BB	262.10	0.55	0.00	262.10	34.90	276.50	14.97	0.00
	CC	354.47	1.7	0.00	354.47	0.46	354.47	6.10	0.00
	DD	263.01	1.69	0.00	263.01	2.49	264.95	2.49	0.00
5_2_2_1	AA	402.37	63.57	0.00	402.37	402.37	0.97	4.63	0.00
	BB	459.08	56.11	0.00	459.08	0.94	459.08	1.27	0.00
	CC	436.55	215.01	0.00	436.55	439.94	52.75	12.76	0.00
	DD	430.00	3.69	0.00	430.00	8.20	444.84	29.51	0.00
6_3_2_1	AA	735.29	3600	24.37	671.62	180.25	692.48	135.93	-8.66
	BB	535.57	875.28	0.00	535.57	274.22	583.20	126.53	0.00
	CC	461.59	157.53	0.00	461.59	13.96	461.59	46.30	0.00
	DD	483.73	3600	29.43	461.16	38.85	467.00	23.61	-4.67
7_3_2_1	AA	628.34	3600	29.80	504.38	62.62	507.46	111.00	-19.73
	BB	635.75	3600	20.22	606.89	125.83	612.8	180.64	-4.54
	CC	481.88	3600	25.67	476.63	53.34	488.74	40.99	-1.09
	DD	807.6	3600	46.18	570.84	50.99	571.78	78.47	-29.32
8_3_2_2	AA	784.43	3600	0.32	715.03	24.71	719.42	52.32	-8.85
	BB	872.24	3600	0.34	778.50	9.94	778.50	33.99	-10.75
	CC	-	3600	-	585.16	8.06	585.16	18.25	-
	DD	-	3600	-	512.58	164.23	537.39	88.29	-
9_3_3_2	AA	-	3600	-	711.28	44.23	726.29	53.69	-
	BB	-	3600	-	931.08	115.54	941.53	116.73	-
	CC	-	3600	-	794.18	79.2	800.59	71.08	-
	DD	699.23	3600	24.54	690.93	84.19	696.47	55.92	-1.19

4.3 灵敏性分析

为评估将无人机融入配送过程的实际效益，将本文所研究问题的求解结果，与仅使用卡车的纯卡车运输系统结果进行对比分析。详细结果如表3所示，表中包含以下关键指标：问题类别（Class）、参与实验的算例数量（Num）、纯卡车运输系统的平均总成本（Truck-only）、含无人机配送系统的平均总成本（Withdrones），以及引入无人机后实现的成本节约率（Savings）。正如预期的那样，将无人机融入配送过程能够显著降低配送系统总成本。

Class	Num	Truck-only	Withdrones	Savings
AA	2	476.83	400.45	16.02%
BB	3	480.31	385.58	19.72%
CC	3	442.54	417.54	5.65%
DD	2	381.73	346.51	9.23%

参考文献：

1. [1] Li H, Chen J, Wang F, et al. Ground-vehicle and unmanned-aerial-vehicle routing problems from two-echelon scheme perspective: A review[J]. European Journal of Operational Research,2021,294(03):1078-1095.
2. [2] Srinivas S, Ramachandiran S, Rajendran S. Autonomous robot-driven deliveries: A review of recent developments and future directions[J]. Transportation Research Part E: Logistics and Transportation Review,2022(165):102834.
3. [3] Zhou J, Yi J, Yang Z, et al. A survey on vehicle–drone cooperative delivery operations optimization: Models, methods, and future research directions[J]. Swarm and Evolutionary Computation,2025(92):101780.
4. [4] Zou B, Wu S, Gong Y, et al. Delivery network design of a locker-drone delivery system[J]. International Journal of Production Research,2024,62(11):4097-4121.
5. [5] Yang Y, Liu J, Wang S. A bi-objective optimisation model for the drone scheduling problem in island delivery[J]. International Journal of Production Research,2025,63(19):7174-7195.
6. [6] Baldacci R, Mingozzi A, Roberti R, et al. An exact algorithm for the two-echelon capacitated vehicle routing problem[J]. Operations Research,2013,61(02):298-314.
7. [7] Santos F A, Mateus G R, da Cunha A S. A branch-and-cut-and-price algorithm for the two-echelon capacitated vehicle routing problem[J]. Transportation Science,2015,49(02):355-368.
8. [8] Zhou L, Baldacci R, Vigo D, et al. A multi-depot two-echelon vehicle routing problem with delivery options arising in the last mile distribution[J]. European Journal of Operational Research,2018,265(02):765-778.
9. [9] Su E, Qin H, Li J, et al. An exact algorithm for the pickup and delivery problem with crowdsourced bids and transshipment[J]. Transportation Research Part B: Methodological,2023(176):102831.