碳交易机制下卡车-无人机协同配送问题研究

摘 要：在“双碳”背景下，为探究卡车-无人机协同配送模式的经济和环境效益，文章以总成本最小化为目标，构建了碳交易机制下的卡车-无人机协同配送路径优化模型，并针对问题特性设计自适应大邻域搜索算法进行求解，通过具体的数值算例验证模型的有效性。结果表明，与传统情况下仅使用燃油车的配送模式相比，卡车-无人机协同配送模式能够显著降低碳排放和总成本，为物流企业选择绿色经济的配送方式提供参考。

关键词：卡车-无人机协同配送；车辆路径；碳交易机制；自适应大邻域搜索算法

中图分类号：F252；TP18 文献标志码：A DOI：10.13714/j.cnki.1002-3100.2024.20.022

Abstract： In order to investigate the economic and environmental advantages of the truck-UVA cooperative distribution model in the "dual carbon" context， this paper constructs a optimization model for the truck-UVA cooperative distribution path under the carbon trading mechanism with the objective of minimizing the total cost， uses the adaptive large neighborhood search to solve the problem based on the characteristics of the problem， and verifies the effectiveness of the model through specific numerical examples. The results show that compared with the traditional distribution mode using only fuel trucks， the truck-UVA cooperative distribution model can significantly reduce the carbon emission and total cost， which provides logistics enterprises with a reference for selecting green and economical distribution schemes.

Key words： truck-UVA cooperative distribution; vehicle routing; carbon trading mechanism; adaptive large neighborhood search

0 引 言

随着全球变暖等气候问题日益严重，控制温室气体排放已成为各国关注的焦点。为此，我国提出实现碳达峰和碳中和的绿色发展目标。碳交易机制是我国实现“双碳”目标的重要手段之一，旨在通过经济市场促进各行业和企业采取措施降低碳排放。在碳交易机制下研究物流配送，不仅是对国家政策的积极响应，也有助于推动物流行业的绿色转型。侯跃等[1]探究碳交易机制对运输成本的影响，构建了多车型路径优化模型，证明企业可以从碳交易中获得经济效益，并降低碳排放。陈婉茹等[2]基于碳交易政策，建立了燃油车和电动车构成的混合车队多中心配送路径优化模型，并研究了车队配置、碳交易机制、速度优化对配送方案的影响。

近年来，无人机逐渐进入物流配送领域。2013年，亚马逊率先尝试使用无人机进行商品配送。随后，谷歌、UPS、顺丰、JD等企业也开始积极探索无人机配送新模式。无人机具有灵活高效、不受地面交通限制等优点，但是其续航和载重能力有限，难以满足长途运输和大规模货物配送的需求。因此，结合无人机和车辆运输的优势，一些学者提出卡车与无人机协同配送包裹的概念并对此展开研究。范厚明等[3]用电动汽车与无人机协同，以总成本最小化为目标建立时变路网下多配送中心的路径优化模型，并设计遗传大邻域搜索混合算法进行求解。杨雷博等[4]针对现实中存在限飞区和限行区的情况，以最小化服务时间优化目标构建双层规划模型并求解。彭勇等[5]借鉴无人机在特殊环境下的物流配送，构建服务时间最短的卡车-无人机协同配送路径优化模型。现有研究大多关注卡车-无人机协同配送的经济性和时效性，对其环境效益的探讨比较有限。

基于上述背景和已有研究的不足，本文从碳排放角度进一步对卡车-无人机协同配送模式展开研究。通过碳交易机制将碳排放量转化为成本，并将其纳入目标函数中，以总配送成本最小为目标建立数学模型，设计自适应大邻域搜索算法对算例求解，得到优化后的配送方案，同时通过对比实验证明模型的有效性，进一步丰富路径优化问题的现有研究，为物流行业降本降碳提供参考。

1 模型构建

1.1 问题描述

就本文研究的问题，配送中心要有足够数量的卡车，且每辆卡车上配备一架小型无人机与之协同，共同为区域内客户提供服务。配送时，卡车携带对应的无人机和包裹从配送中心出发，到达客户点时，卡车为客户提供服务，同时可将该客户点作为无人机的发射节点，将无人机放飞。在无人机单独配送的同时，卡车继续前进为剩余客户提供服务，并将下一客户点作为无人机的回收节点，等待无人机与之汇合，以进行下一阶段的配送。在满足所有限制条件的前提下，进行客户点服务工具的合理分配，并规划卡车和无人机的配送路线，以降低总体配送成本。卡车与无人机协同配送具体如图1所示。

针对该问题，本文做出以下假设：

一是只有一个配送中心，配送中心有若干辆同型号的配送车辆和无人机；

二是所有客户的需求和地理位置已知，每个客户点只能被服务一次；

三是每辆卡车仅搭载一架无人机，且每次发射无人机只能为一个客户点提供服务；

四是每架无人机起飞、降落和更换电池的时间可以忽略不计；

五是无人机只能在配送中心或客户点处进行发射和汇合；

六是当无人机从卡车上起飞，需要在卡车路径的下一个节点处汇合。

1.2 符号说明

本文问题定义在一张无向图G=（N，A）上。其中，点集合N={C∪0∪c+1}表示配送网络中所有节点，C={1，2，...，c}表示客户点集合，0和c+1代表配送中心；N0={0，1，2，...，c}为可离开的节点集合，N+={1，2，3，...，c，c+1}为可到达的节点集合；T={1，2，3，...，t}表示卡车-无人机组合的集合；A={（i，j）：i∈N0，j∈N+，i≠j}为边集合；元组＜i，j，k＞表示无人机飞行路径，即从节点i处起飞，服务客户j后飞到节点k处与卡车汇合；Cd表示由无人机服务的客户点集合。

决策变量xtij表示卡车t是否从节点i行驶节点j，若是则为1，否则为0；ytijk表示卡车t对应的无人机从节点i起飞，为节点j服务后，飞到节点k与卡车汇合，若是则为1，否则为0。

非决策变量sti和分别表示卡车或无人机到达节点i的时间；σtij和分别表示卡车或无人机在边（i，j）上的行驶时间。

模型中所使用的其他参数说明如表1所示。

1.3 成本分析

本文所研究模型的成本由三部分组成，分别是固定成本、运输成本、碳交易成本。

1.3.1 固定成本

固定成本包括卡车的固定成本和无人机的固定成本两部分。卡车的固定成本仅与车辆的使用数量有关，主要包括司机工资、车辆的折旧费用、维修费用等。无人机的固定成本与无人机的放飞次数有关，主要包括在节点处操作者装卸无人机、更换电池的费用、无人机的损耗等。固定成本计算公式如下。

1.3.2 运输成本

运输成本包括卡车的行驶成本和无人机的飞行成本。运输成本会随着运输距离的增加而改变。因此，建模为与运输距离线性相关的函数，具体表达式如下。

1.3.3 碳交易成本

在计算碳交易成本时需要先确定二氧化碳排放量。本文模型中的二氧化碳排放主要考虑两个方面：一是卡车行驶过程中燃油消耗产生的碳排放；二是无人机配送过程中所消耗电量在上游发电源头所产生的碳排放。

在计算车辆行驶过程中的油耗时，需考虑行驶距离和车辆载重对油耗的影响。当车辆从节点i行驶到节点j时，其载重量为mij，单位距离的燃油消耗量（升/千米）表示如下。

因此，在配送过程中，车辆从节点i到节点j时所产生的碳排放量Etij如下。

无人机使用电能进行驱动，在飞行过程中不直接产生碳排放，但我国主要采用火力发电。因此，会在发电源头处间接产生碳排放。本文通过计算无人机在配送过程中的电量消耗来确定源头发电设施需要产生的电量，进而测算碳排放量。

在飞行路径＜i，j，k＞中，无人机消耗的总电量如下。

考虑到电力在传输过程中的损耗，假设发电厂生产单位电力所产生的二氧化碳排放量为θ，则无人机的碳排放量Edijk如下。

因此，配送过程中总碳排放量EM可由公式（7）计算。

综上，碳交易成本F3的计算公式如下。

1.4 模型构建

基于以上对各部分成本的分析，构建出碳交易机制下的卡车-无人机协同配送路径优化模型，如下所示。

式（9）表示配送总成本最小的目标函数；式（10）约束每个客户只能被卡车或无人机访问一次；式（11）保证无人机无法服务的客户仅由一辆卡车进行服务；式（12）是卡车在配送中心的出发与返回约束；式（13）表示卡车从配送中心出发后不得直接返回配送中心；式（14）是在客户点处的进出流量平衡约束；式（15）表示无人机的起降节点必须被配对的卡车访问；式（16）表示无人机不允许服务只能由车辆服务的客户点；式（17）和式（18）分别表示每辆卡车在各节点处最多只能发射和接收一次无人机；式（19）表示卡车路径上的无人机发射节点和汇合节点需相邻；式（20）和式（21）分别为卡车和无人机的载重约束；式（22）为无人机的最大飞行距离约束；式（23）—（29）对卡车和无人机在各节点处的时间一致性进行约束；式（30）和式（31）分别表示车辆和无人机在配送中心的初始化时间为0；式（32）和式（33）是决策变量的取值范围约束；式（34）和式（35）是非决策变量的取值范围约束。

2 算法设计

自适应大邻域搜索（ALNS）算法自提出以来，在解决复杂车辆路径问题上有较好的表现，具有快速收敛特性、不易陷入局部最优等特性。因此，本文选择该算法对模型进行求解。本节介绍ALNS算法的主要内容及流程图。

2.1 编码方式

考虑研究问题的特性，采用整数编码的方式，将染色体分为两个部分（见图2）：第一部分表示服务节点的顺序，其中“0”代表配送中心，非零值则表示对应的客户节点；第二部分与第一部分的编码长度相同，表示服务该客户点的运输工具，用二进制数表示，其中0表示该客户点由卡车服务，1表示该客户点由无人机进行服务。

2.2 构造初始解

求解复杂的路径问题时，一个质量较好的初始解能在一定程度上提升后续迭代优化的效率。本文采用一种两阶段的方式构造初始解。首先根据最近邻思想生成一个只有车辆配送的路径解，接着考虑无人机的载重和距离等限制，并对客户点的服务工具进行分配，生成一条完整的染色体。

2.3 邻域操作

在得到一组解后，ALNS算法会对当前解进行邻域搜索，并使用不同的邻域算子扩大解空间的搜索范围，以找到更优的解。为了增加解的多样性，避免算法陷入局部最优，本文采用8种不同的邻域操作算子。

位置交换：交换路径中任意两个客户的位置。

互换：交换路径中编号最大值与最小值的位置。

反转：选取路径中的一段序列并水平旋转。

插入：随机选择路径中的某一客户，插入另一位置。

滑动：选取路径中两个客户点，将其中一个插入另一个位置之后。

序列交换：交换路径中两段序列的位置。

序列移动：将路径中一段序列移动到另一位置。

反向序列移动：将路径中一段序列移动到另一位置并水平反转。

2.4 自适应机制

ALNS算法的自适应机制主要体现在算子的选择上。本文采用轮盘赌选择法对8种邻域操作算子进行随机选择，并根据各算子的权重占所有算子总权重的比例来划分轮盘。

开始时，所有邻域操作算子均具有相同的权重，且每个算子都有相同的概率被选择。每次迭代结束时，根据新解的质量好坏来更新所使用算子的权重。算子的权重越大，在轮盘中被选中的概率越大，可用以提高算法的寻优能力。

2.5 解的接受准则和终止条件

采用模拟退火思想作为新解的接受准则。在算法的每次迭代过程中，如果通过邻域操作后新生成可行解的总成本小于当前解的总成本，则将新解直接更新到当前可行解的解集中；若新解的总成本高于当前可行解的总成本，则根据模拟退火思想，该劣解有一定的概率被接受。

当算法达到最大迭代次数时，则终止。

2.6 算法流程图

结合以上内容，ALNS算法流程图如图3所示。

3 数值实验分析

3.1 实验数据及参数

本文选取Solomon算例作为模型求解的数据来源，采用Solomon算例中R201数据，生成30个客户点的案例，并在MATLAB中将各节点坐标具体化，如图4所示。结果显示，每辆卡车的最大载重量设为150 千克，固定成本设为300 元，单位距离行驶成本为2.3 元/千米，计算卡车碳排放的相关参数为ρ0=1升/千米，ρ*=2 升/千米，β=2.65千克CO2/升。所搭载的无人机自重为10千克，最大载重为10千克，协调成本为5元，单位距离运输成本为0.87元/千米，计算无人机碳排放的相关参数为：g=9.8，（s）=3，η=0.73，ηb=0.9，ηr=0.956，θ=1.058×10-4kgCO2/J。单位碳排放成本为0.03元/千克CO2，碳配额Tq设为300千克，交易价格设为0.05元/千克。使用Matlab 2018b对算法进行编码和实验，最大迭代次数设为300，连续运行10次。

3.2 仿真结果

对本文的模型和算例进行了10次试验，得到最优解的配送路径如表2所示。

由表2可知，配送中心派出三辆卡车与三架无人机共同为区域内所有客户提供服务。第一辆卡车依次为客户15、13、14、30、8、27、29、12服务。最后返回配送中心，与之协同的无人机1为客户6、21、10、16、18服务，并在路径相邻节点处进行起飞和降落。

同理，第二辆卡车依次为客户24、25、11、4、7服务；无人机2为客户22服务。第三辆卡车依次为客户26、9、19、20、2、1、3、23服务；无人机3为客户5、28、17服务。

该最优解的各项成本和产生的碳排放量如表3所示。

3.3 对比分析

为探究卡车-无人机协同配送模式的优越性，将本文构建的模型（记为P1）与仅使用燃油车配送模型（记为P2）进行比较，求解结果如表4所示。

由表4可以看出，与仅使用燃油车进行配送相比，卡车与无人机协同配送情况下降低了7.08%的总成本，使用无人机会增加固定成本，但运输成本和碳交易成本分别降低了23.72%和60.09%，碳排放量降低了40.25%。

由此可见，为区域内客户进行配送时，使用无人机与卡车进行协同配送既可以降低配送成本，又可以显著减少碳排放，可有效解决物流环节成本高、碳污染严重等问题，实现经济效益和环境效益的双重优化。

4 总结与展望

结合我国现阶段实行的碳交易政策，本文对卡车-无人机协同配送进行了深入研究，构建了碳交易机制下的卡车-无人机协同配送路径优化模型，以使固定成本、运输成本、碳交易成本之和最小。针对问题特性设计ALNS算法求解，并通过具体的数值算例验证本文模型的有效性。实验结果表明，与仅使用燃油车的配送模式相比，无人机与卡车进行协同配送能够显著降低碳排放和总成本。本文为物流企业在碳交易市场下选择合适的运输工具、制定合理的配送策略提供参考。

卡车和无人机之间有多种协同方式，本文的研究仅考虑了其中一种，未来的研究可进一步探究其他协同方式下的经济与环境效益。为求得优化效果更好的解，可尝试其他启发式算法，或者尝试使用精确算法求解此类问题。

参考文献：

[1] 侯跃，杨斌，许波桅，等．考虑碳交易的多车型运输车辆配送路径优化[J]．辽宁工程技术大学学报（自然科学版），2015，34（5）：647-652.

[2] 陈婉茹，徐光明，张得志，等．碳交易机制下多中心混合车队配送路径和速度优化研究[J]．系统工程理论与实践，2023，43（11）：3320-3335.

[3] 范厚明，张跃光，田攀俊．时变路网下多中心电动车-无人机协同配送路径优化[J]．管理工程学报，2023，37（2）：131-142.

[4] 杨雷博，周俊．限制区下货车联合无人机配送路径问题研究[J]．计算机工程与应用，2023，59（12）：326-332.

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