引言

电子商务高速发展与城市化进程加快，推动物流配送需求向个性化、多样化升级。传统配送模式已难以满足客户对配送时效、方式灵活性的要求，融合无人机、卡车、接驳柜与驿站的多模式协同配送路径问题，成为学界与业界的研究热点。无人机配送凭借其突破地理与交通限制的优势，在提升配送效率、降低成本方面表现突出。中通研究院测算显示，“末端支线” 无人航空物流模式可降低综合经营成本超30%。基于此，本文提出考虑无人机接驳柜、卡车接驳柜、卡车驿站、送货上门四种配送方式的多目标路径优化问题。不仅要考虑卡车无人机的行驶成本、卡车和无人机的出动成本、驿站和接驳柜的寄存成本，还要考虑满足顾客满意度。同时，我们会将卡车载重量、无人机载重量、无人机电池续航及接驳柜容量这几类客观因素综合起来进行研究，使得问题更加贴近现实情况。

1. 国内外研究现状

1.1 多目标车辆路径问题

多目标车辆路径问题因更贴合现实需求成为研究热点，核心优化目标涵盖成本、车辆使用数、行驶距离及客户满意度等。现有研究多采用启发式算法求解，如吕垚远等、罗梓瑄等运用NSGA-Ⅱ算法，分别围绕车辆使用数、行驶距离与客户满意度等目标构建模型；部分学者引入深度学习、强化学习等方法，如Zhang, J.等提出基于权重分解的深度学习策略，实现多目标问题的拆分求解。

1.2 无人机配送问题

无人机配送问题研究主要分为两类。一是无人机与卡车协同配送，Wang等提出VRP-D模型，证实无人机引入可大幅节约成本；Sacramento等设计自适应大邻域搜索算法，解决载重与时间约束下的多车协同问题。相关研究还关注时变路网、动态能耗等现实约束，优化路径规划方案。二是无人机与物流柜协同配送，朱外明等提出变领域搜索算法，优化接驳柜无人机配送调度完工时间；Zou, B.等聚焦储物柜选址与无人机数量配置，以降低运营成本为目标优化网络设计。现有研究多聚焦单一配送模式，鲜少将无人机、卡车、物流柜与驿站等多种方式结合。

1.3 多种配送方式的车辆路径问题

多种配送方式的车辆路径问题（如VRPDO）逐渐受到关注，Dumez等人考虑家庭、储物柜等多种交付选项，构建混合整数非线性模型并采用大邻域搜索算法求解；Mancini和Gansterer引入客户补偿机制，研究私人与共享送货地点的路径优化问题。这类研究虽整合了多种配送场景，但大多未纳入无人机配送方式，且在复杂多目标约束下的求解能力仍有局限。

2. 问题描述与数学模型

2.1 问题描述

在VRPDO中，每个客户预先提供一个或多个指定的配送位置和优先级的配送选项。本文使用的优先级是指客户对该选项的优先级，即较小的数字表示更高的客户满意度。此外，就可服务的客户数量而言，接驳柜的容量有限。VRPDO的问题是在给定的客户提供的配送选项和相应的配送选项优先级中，为每个客户精确地选择一个配送选项，并确定一组成本最小的可行路线，以服务于所选的配送选项，同时考虑最大化顾客满意度，并尊重交付地点的时间窗口和容量。

	送货上门	驿站自提	无人机+接驳柜		卡车+接驳柜
顾客1优先级	1	3	2	4
顾客2优先级	4	2	3	1
顾客3优先级	2	1	4	3
顾客4优先级	3	2	4	1

在这个模型中，本文提出了一个混合整数规划模型，当求解时，为每个客户找到最优的配送选项，以最大限度地满足他们更高的满意度，以及最优的路线(即最小化成本)。给定一个完整的有向图 ，由物理网络中考虑的顶点组成，即 ，包括每个配送选项的顶点加上仓库起点0和仓库终点 。卡车和无人机从中心仓库0出发，假设中心仓库停有一定数量的卡车和无人机，最后回到中心仓库。用 表示顾客集合， 表示配送选项集合， 四个配送方式，HL表示送货上门，DL表示无人机+接驳柜配送，VL表示卡车＋接驳柜配送，CS表示驿站自提。驿站集合用E表示，接驳柜集合用 表示。 是连接顶点 中的弧的集合， 中的每条弧线都有一个与之相关的行驶距离 ，卡车（无人机）的行驶时间 （）。 表示每个顾客 可接受服务的时间窗口，卡车（无人机）必须在该时间窗口内到达并开启服务。

2.2 基本假设

由于数学模型不能够完全地描述现实中所遇到的场景，为了便于建模处理，对该模型的构建做了以下基本假设：

1. 每个客户只能被服务一次；
2. 卡车和无人机速度恒定；
3. 无人机从仓库出发时满电状态，电池更换时间和发射回收时间忽略不计；
4. 服务时间内不增加成本，所以忽略不计；
5. 无人机可以携带多个包裹，无人机到达接驳柜时瞬间完成装卸；
6. 接驳柜容量等于可以容纳包裹的数量，不考虑包裹体积。

2.3 模型构建

MO-VRPDO的数学模型如下：

模型的目标包括最小化配送成本和最大化顾客满意度。目标函数（1）是最小化配送成本，第一项和第二项是卡车和无人机出动的固定成本，第二项是卡车的配送成本，第三项是无人机的充电成本，第四项和第五项分别是接驳柜和驿站的寄存成本。目标函数（2）是最大化顾客满意度，量化为最小化每个顾客配送选项优先级的总和：

3. 算法设计

3.1 QNSGA-Ⅱ算法框架

QNSGA-Ⅱ是非支配排序遗传算法和Q-learning结合的混合智能优化算法。非支配排序遗传算法是由Deb等人首次提出的，是解决多目标问题常用的算法。非支配排序遗传算法具有快速的非支配排序过程和拥挤度排序的特点，将上一代的种群经过适应度选择、交叉和变异之后的子代种群与父代种群相结合，对结合后的种群进行非支配和拥挤度的排序。非支配排序将种群划分为不同的支配层，而拥挤度排序用来在每个支配层内部选择拥挤度更大的个体。该算法的复杂度为 ，其中 是目标数， 是种群规模。因为每个解都需要计算支配该解的解的数量和被该解支配的解的数量，计算这些需要 次比较。与以往算法相比大大节省了所需时间。在整个算法过程中，种群经过交叉变异之后利用Q-leaning选择改进算子。

3.2 编码和解码

编码是将完整的解决方案转化为染色体，本文的每个解通过三组染色体来表示，三组染色体分别对应顾客的配送方式，卡车路径和无人机路径。顾客配送方式染色体表示每个顾客选择的配送方式是哪一种。卡车路径染色体表示每辆卡车访问的顺序。无人机路径染色体表示每架无人机的访问顺序。图1表示了某个解的表示，C3选择送货上门HD，C4选择卡车配送到接驳柜VL，都由卡车K1来进行配送；C5和C7选择HD，C2和C6选择驿站自提CS，都由卡车K2来进行配送；C4和C8都选择无人机配送到接驳柜，由无人机U1进行配送。解码是编码的逆过程，将染色体转化为实际的配送方案。将路径染色体直接对应实际行驶路线，配送方式染色体集合路径确定具体的执行方案。

3.3 初始解生成

初始解是基于顾客配送方式的选择与无人机和卡车路径的确定来生成的。首先对于每个顾客，只能选择一种配送方式（如送货上门、无人机配送、接驳柜自提和驿站自提）。记录每个顾客可用的配送方式和优先级，随机选择一种配送方式，如果顾客选择接驳柜或者驿站，则会进一步确定最优的接驳柜或者驿站的位置。之后根据客户选择的配送方式，构建卡车和无人机路径。生成的路径需要满足所有约束条件，包括无人机和卡车容量、无人机的电池能耗以及顾客和驿站时间窗等，通过这两个步骤获得最终的初始解，作为未来优化的起点。

3.4 非支配排序

非支配排序的目的是将种群划分为不同的支配层。首先遍历种群找出所有的非支配解，存入第一非支配解集，然后移除这些第一级解，在剩余的种群中重复操作，找出第二非支配解集，以此类推直到所有个体都分配到相应的层级。

3.5 拥挤度计算

对每个非支配等级的个体计算拥挤度，用于衡量个体在目标函数空间中的分布情况，以保持种群多样性。对每个非支配前沿中的个体，按目标函数值排序后，两端个体的拥挤度设为无穷大，中间个体的拥挤度为两侧个体目标函数值差的总和。

3.6选择、交叉和变异算子

采用二元锦标赛选择算子，从当前种群中筛选出优质个体作为父代来生成下一代。随即从种群中选取2个个体，比较两者的非支配等级，等级越低即非支配层级越小的个体优先被选中，如果等级相同则比较拥挤度距离，距离越大的个体即解周围越稀疏的个体优先被选中。该方法只允许可行个体参与后续的交叉变异操作从而提高解的质量。

交叉算子是通过部分匹配交叉（PMX）思想，针对每条卡车和无人机的路径进行操作。对两个父代中对应的卡车或者无人机的路径，随机选择两个交叉点 和 ，交换两个路径在 区间内的片段。

变异算子是通过交换、插入和反转三个操作来进行的。交换是指随机交换路径中两个顾客的位置。插入是指随机抽取一个客户插入到另外一个位置。反转是指随机选择一段路径并反转其顺序。

3.7 邻域搜索算子设计

由于问题的特殊性，模型中包括多种配送方式，所以对此设计了五个关于配送方式的改进算子。

（1）成本驱动的配送方式改进算子。以降低整个配送网络的配送成本为目标，为每个客户选择成本最低的配送方式。首先遍历每个顾客获取每个客户可用的配送方式，调整顾客的配送方式并重建路径，选择其中成本最低的配送方式替换当前的配送方式。

（2）优先级驱动的配送方式的改进算子。为了提升顾客满意度，在控制成本增加幅度的前提下优化顾客优先级。首先遍历每个顾客获取每个客户可用的配送方式，计算每种配送方式对应的优先级，数值越小表示优先级越高，选择其优先级最高的配送方式，如果新方式的成本相比原成本增加不超过5%，则接受该改进。

（3）容量平衡改进算子。为了平衡卡车和无人机的负载，避免设备过载，分析当前卡车和无人机的负载情况，识别过载或接近过载的设备。针对过载的卡车，将其负责配送且距离储物柜较近的客户或者尝试转换为无人机配送；针对过载的无人机，将其负责配送的客户，尝试转换为其他卡车相关配送方式。

（4）地理聚类改进算子。基于客户地理位置的聚类结果，优化配送方式以减少运输距离。对客户进行地理聚类，确定每个聚类的中心位置，为每个聚类找到最近的储物柜和驿站等设施，根据客户与这些设施的距离，为聚类内的客户选择最优配送方式。

（5）时间窗感知改进算子。根据客户的时间窗约束优化配送方式。计算客户时间窗的松紧度，对于时间窗较紧的客户优先选择送货上门，以确保按时送达。对于时间窗较宽松的客户，若当前为送货上门，尝试转换为成本更低的方式。

3.8 基于Q-learning的算子组合选择机制

改进的NSGA-Ⅱ是用轮盘赌的方式来选择邻域搜索算子，在实验中发现轮盘赌的方法会导致算法陷入局部最优，影响解的质量。所以在改进NSGA-Ⅱ的基础上结合Q-learning来代替轮盘赌的方式来选择算子，如果在当前状态下找到更好的解，则给予奖励。

Q-leaning的核心在于通过状态、动作、奖励的定义和Q值的更新规则，结合MO-VRPDO的问题特质，对这些要素进行了设计。在每次迭代中，系统处于状态 ，通过动作 获得奖励 ，其中学习率 ，折扣因子 ，随后根据以下公式更新Q值：

3.8.1 状态设计

在每次迭代t中，使用集合覆盖率 函数计算收敛性指标 ，该函数量化P1中被P2中至少一个解支配的解的比例同时计算多样性指标，这个方法主要是利用种群P内解之间的欧氏距离。

本文状态根据Candice Destouet的文章，基于收敛性和多样性的概念定义了四个不同的状态：

3.8.2 动作设计

动作对应不同的邻域搜索算子，每次迭代过程中选择一个领域搜索算子。为了探索更多的解，采用了 策略。以 的概率选择当前状态下具有最高Q值的动作，以 的概率随机选择一个动作，其中 为[0,1]之间的随机数。

3.8.3 奖励函数

奖励函数优先考虑解的多样性。当多样性和收敛性都改善时，奖励最大化。如果只有多样性改善，奖励会略低，只有收敛性改善时奖励也减少。当收敛性和多样性都没有改善时，奖励最低。

4. 实验结果与分析

4.1 实验结果对比

MO-VRPDO的质量取决于收敛性和多样性，收敛性反映了帕累托前沿解与最优帕累托前沿之间的距离，后者反应了解集在空间内分布更均匀。所以本文采用了以下三个指标对这两个方面进行比较：

1. 帕累托前沿解的数量；
2. HV值：HV用于计算算法所得到的非支配解集在目标空间中形成的区域的体积，HV值越大，其算法的收敛性和多样性越好。设参考点为 ，帕累托前沿解集中的点为 （按目标 函数一的值升序排序）；
3. SP值：sp指标用来衡量每个解与其他解的最小距离标准差，SP值越小，解集分布越均匀。

表2展示了MO-VRPDO问题首先对8个算例进行测试，共计36个算例。每个算例是以“顾客数_驿站数_接驳柜数_仓库数”的格式来进行命名，比如“4_2_2_1”代表4个顾客，2个驿站，2个接驳柜和1个中心仓库。为了评估QNSGA-Ⅱ的求解质量，本文分别用CPLEX、NSGA-Ⅱ和QNSGA-Ⅱ来求解这些算例。用CPLEX求解这些算例时，限制时间为1h。用NSGA-Ⅱ和QNSGA-Ⅱ来求解这些算例，为消除随机性的影响每个算例独立运行了5次。表2展示了运行的结果，列出算法运行的结果的解的数量，HV值和SP值。

Instance	Class	Cplex		NSGA-Ⅱ		DNSGA-Ⅱ			QNSGA-Ⅱ
		解的数量	HV	解的数量	HV	解的数量	HV	Sp	解的数量	HV	Sp
4-2-2-1	0	1	-	7	250.8346	7	250.8346	5.5838	7	250.8346	5.5838
	1	3	174.0942	5	288.0459	5	288.0459	18.4286	5	288.0459	18.42
	2	3	151.2670	6	502.5467	6	502.5467	16.9023	6	502.8469	16.613
	3	1	-	6	203.5774	6	203.5774	8.3539	6	208.6098	7.4638
6-2-2-1	0	2	138.6064	10	554.1264	10	554.1264	6.1021	9	554.1264	6.1021
	1	3	161.1785	6	568.7513	6	568.7513	16.2067	7	569.0108	15.275
	2	3	34.5348	5	268.7975	5	268.7975	4.7650	6	268.7975	4.7650
	3	2	52.9841	6	287.7794	6	287.7794	4.0458	6	287.7794	4.0458
8-3-3-1	0	1	-	8	488.8567	8	488.8567	6.1903	8	497.2619	5.8402
	1	3	156.5461	7	882.0439	7	882.0439	4.2357	7	882.0439	4.2357
	2	3	128.5028	6	352.0287	6	352.0287	6.5586	6	369.1964	3.2751
	3	1	-	13	565.4568	13	565.4568	1.3371	14	565.4559	1.2949
10-3-3-1	0	2	79.2722	7	486.4630	7	486.4630	2.4433	9	488.9324	1.9313
	1	1	-	8	431.0684	8	431.0684	4.8316	10	523.8735	3.5942
	2	1	-	9	1471.841	9	1471.841	16.4307	9	1475.457	14.637
	3	1	-	11	696.9042	11	696.9042	1.8818	12	698.4012	1.7827
12-3-3-1	0	2	40.5127	8	221.4841	8	221.4841	1.4565	8	236.8786	1.3368
	1	1	-	6	313.2004	6	313.2004	2.2368	8	383.7319	2.1934
	2	1	-	10	1884.655	10	1884.655	14.0127	12	1884.044	13.216
	3	2	16.5814	8	436.4612	8	436.4612	3.8772	10	440.4909	3.6102
14-3-3-1	0			13	742.7352	13	742.7352	2.36900	15	747.5652	2.0690
	1			9	995.7768	9	995.7768	11.6051	10	1323.282	10.461
	2			15	1363.741	15	1363.741	6.946622	16	1798.471	4.4748
	3			8	784.8074	8	784.8074	2.272909	9	787.2845	1.7278
20-5-5-1	0			11	2834.730	11	2834.730	17.26666	17	2874.713	1.7835
	1			9	1510.788	9	1510.788	8.75395	10	1611.623	8.4422
	2			10	2411.816	10	2411.816	15.25362	19	4771.580	6.26113
	3			9	1388.007	9	1388.007	8.085395	12	2774.293	6.9361
24-5-5-1	0			7	1603.781	7	1603.781	8.683172	20	5316.409	3.2732
	1			15	3688.928	15	3688.928	3.813173	17	3841.911	5.2555
	2			9	1293.639	9	1293.639	93.00181	11	1883.046	2.6569
	3			13	6599.171	13	6599.171	11.16992	18	7595.567	9.4717

如表2所示，当顾客数量超过12时，CPLEX无法在1h内找到可行解，而NSGA-Ⅱ、DNSGA-Ⅱ和QNSGA-Ⅱ可以在合理的时间内求解，此外对于更大规模的算例求解结果比CPLEX好。而用帕累托前沿解的数量、HV值和SP值三个指标来衡量时，QNSGA-Ⅱ均优于CPLEX、NSGA-Ⅱ和DNSGA-Ⅱ。

4.2 敏感性分析——单卡车配送

在该模型中，无人机由于其成本低、速度快等特点，在整个配送网络中发挥着重要作用。本文研究了无人机在协同配送网络中的使用价值，以单卡车配送模式来进行对比，所有顾客的订单都由卡车来进行配送，相应的实验结果如图2所示。

通过单卡车配送与卡车—无人机协同配送的实验结果，单卡车算例中HV值都明显下降，整体优化性能显著降低，可能的原因是，只有卡车参与配送网络时，不仅是整个配送网络的运营成本增加，以及卡车缺乏无人机的灵活性，对时间窗要求会比较高，配送时效性明显下降，所以在多目标优化性能方面比不上卡车—无人机协同配送模式。这验证了协同配送模式的有效性和实用性，对企业设计配送网络具有重要的参考意义。

参考文献：

1. [1] 吕垚远,张春美.考虑顾客满意度的多目标车辆路径优化问题[J].太原科技大学学报,2023,44(06):527-534.
2. [2] 罗梓瑄,杨杰庆,刘学文.基于NSGA-Ⅱ的考虑客户满意度的多目标车辆路径问题研究[J].重庆师范大学学报(自然科学版),2020,37(06):13-17.
3. [3] 冯斌.带时间窗约束的车辆路径多目标优化[D].燕山大学,2023.
4. [4] Tan K C, Lee T H, Chew Y H, et al. A multiobjective evolutionary algorithm for solving vehiclerouting problem with time windows[C]//IEEE International conference on systems.2003.
5. [5] 黄韬.改进遗传算法在多目标带时间窗车辆路径问题中的研究与应用[D].广东财经大学,2015.
6. [6] 李奕颖,秦刚.基于Spark的改进蚁群算法对带时间窗车辆路径问题的求解[J].计算机系统应用,2019,28(07):9-16.
7. [7] 王鼎.基于改进蚁群算法的带时间窗车辆路径问题的研究[D].郑州大学,2020.
8. [8] 张晓楠,范厚明.求解带时间窗车辆路径问题的混合Memetic算法[J].运筹与管理,2021,30(07):128-135.
9. [9] 陆湛晴.基于多目标决策的车辆路径问题算法研究[D].武汉科技大学,2018.