管理科学与工程

考虑碳排放的车机协同配送路径问题

  • 马佳 ,
  • 马心茹 ,
  • 唐金环
展开
  • 沈阳航空航天大学 经济与管理学院,沈阳 110136

马佳(1979—),女,辽宁盖州人,教授,博士,主要研究方向为物流系统优化与控制,E-mail:

收稿日期: 2025-03-05

  修回日期: 2025-05-24

  录用日期: 2025-05-25

  网络出版日期: 2026-07-06

基金资助

国家社会科学基金(24FGLB055)

辽宁省社会科学规划基金(L20CGL012)

The routing problem of vehicle-drone collaborative delivery considering carbon emissions

  • Jia MA ,
  • Xinru MA ,
  • Jinhuan TANG
Expand
  • College of Economics and Management,Shenyang Aerospace University,Shenyang 110136,China

Received date: 2025-03-05

  Revised date: 2025-05-24

  Accepted date: 2025-05-25

  Online published: 2026-07-06

摘要

为解决传统单一配送工具资源利用率低、成本高及碳排放量大的问题,提出双层无人机-电动车联合配送路径规划问题(2E-VRPD),充分考虑了车辆及无人机在不同配送阶段的能源消耗和碳排放等因素,建立以固定成本、能耗成本、碳排放成本之和最小为目标,以客户时间窗、车机容量和车机电池容量等为约束的混合整数线性规划模型。基于此模型,设计了混合遗传算法,根据贪婪法则生成初始种群,将大规模邻域搜索中的破坏和修复思想与遗传算法结合进行求解。实验结果表明,该混合算法能够有效解决2E-VRPD问题,能优化配送路径,提升车机协同配送效率,降低配送成本。

本文引用格式

马佳 , 马心茹 , 唐金环 . 考虑碳排放的车机协同配送路径问题[J]. 沈阳航空航天大学学报, 2026 , 43(3) : 83 -89 . DOI: 10.3969/j.issn.2095-1248.2026.03.011

Abstract

To address the problems of low resource utilization,high costs and high carbon emissions of traditional single delivery tools,a joint delivery routing problem for electric vehicles and drones with a two-tier system was proposed. It considered factors such as energy consumption and carbon emissions of vehicles and drones during different delivery stages. A mixed-integer linear programming model was established, aiming to minimize the sum of fixed costs, energy consumption costs, and carbon emission costs, subject to constraints including customer time windows, vehicle and drone capacities, and battery capacities. Based on this model, a hybrid genetic algorithm was designed. Initially, an initial population was generated according to a greedy rule, and the destruction and repair concept from large-scale neighborhood search was integrated with the genetic algorithm for solving. The experimental results verify that this hybrid algorithm can effectively solve the 2E-VRPD problem, optimize delivery routes, improve vehicle-drone collaborative delivery efficiency, and reduce delivery costs.

2023年国家邮政局倡导企业注重不同寄递运输方式有效衔接,选用高效低碳的运输方式。使用单一类型的车辆或无人机执行配送任务时,存在资源利用率低、成本高昂、受地形或天气影响、难以满足多样化的配送需求等问题。而车机协同配送可根据不同配送场景和需求,灵活调配配送设备,实现资源优化配置,降本增效,促进环保和可持续发展。因此,结合车辆和无人机的优势,二者联合配送并在客户密集区域建立中转站是一个很好的新模式。
Murray等1最早提出无人机辅助的旅行商问题和无人机并行的调度优化问题。Kim等2提出了带有一个远离配送中心的无人机站的旅行商问题。王新等3设置了多个无人机站点。许菱等4、梁爽等5将多无人机单一包裹配送改为多包裹配送。颜瑞等6、Dorling等7、蒋丽等8考虑了载重对能耗的影响。马华伟等9、Meng等10研究了同时取送货的多访问车辆-无人机协同路径规划问题。Xia等11、Sitek等12提出采用主动方法求解无人机配送规划问题。Breunig等13介绍电动两级车辆路径问题。Jie等14提出了带换电站的双梯队电动汽车路径问题;Enthoven等15引入了无碳排放的货运自行车和包裹储物柜。
与现有研究不同,本文考虑多个无人机-电动车中转站和顾客时间窗的需求,同时考虑载重对能耗的影响。中转站的设置是将两级车辆路径问题与车机并行调度问题相结合,无人机和电动车的引入减少了卡车配送路程及使用卡车产生的油耗成本、碳排放量。为解决该问题,本文提出高效的启发式算法,将大规模邻域搜索中的破坏和修复思想引入遗传算法中,提高全局寻优能力,进一步提升解的质量。

1 模型构建

1.1 问题描述

本文提出了双层无人机-电动车联合配送路径规划问题(2E-VRPD)。第一阶段,需要在顾客较密集区域建立无人机-电动车中转站,由卡车将货物从配送中心运送到多个中转站;第二阶段,由电动车和无人机并行配送,由于航程和载重限制,无人机不能配送的部分货物由电动车配送。卡车-电动车-无人机联合配送示意图如图1所示。
图1 卡车-电动车-无人机联合配送示意图
本文为简化模型,提出如下假设:1)无人机和电动车采用电池为动力;2)在配送途中电量不足时返回同一个中转站;3)无人机具有航程和容量限制;4)无人机续航时间与载重有关;5)每个客户只能由一架无人机或电动车服务一次;6)车辆和无人机匀速行驶;7)每个客户都有时间窗需求;8)车辆、无人机都是同质的;9)一架无人机可以装载多个包裹,服务多个客户点。

1.2 符号说明

N C为客户点集合;N CT为只能由电动车访问的客户点集合;N CD为无人机可访问的客户点集合;N S为中转站集合;N=N CN SN O,其中,N O为配送中心集合;T为每个客户点所需的服务时间; Q t为配送卡车最大载重; Q k为配送电动车最大载重; Q v为无人机最大载重; q i为客户点i的需求量;α为无人机每kg载重的功率消耗;β为无人机自身在空中飞行的功率消耗;B为电动车的电池容量; ε m i n为电池被允许的最低荷电状态;E为无人机一次飞行的最大能耗; C a t C a k c a v分别为使用一辆卡车、电动车、无人机的固定成本; C b k C b v为电动车、无人机每kJ成本; C b t为卡车单位油耗费用; C c t为卡车单位碳排放费用;[ETiLTi ]为客户点i的服务时间窗; x i j t x i j k y i j v等于1表示卡车、电动车、无人机从节点i行驶到j ε i k为电动车k离开节点i时的荷电状态; f i v为中转站出发的无人机离开客户点i时的累计能耗; F i v为无人机从客户点i回到中转站后的累计能耗; c i j t为卡车t从节点i行驶到j的碳排放率; p i j为路段(ij)上的能源消耗率; r i k为电动车k离开节点i时的能耗; λ i j为从节点i到达j的时间; d i j为节点ij之间的距离; λ i为到达客户i的时间; W i为离开节点i时的载重。

1.3 成本分析

1.3.1 卡车碳排放及油耗成本分析

卡车t的单位碳排放率(单位g/km)为
ϕ v = ω 0 + ω 1 v + ω 2 v 2 + ω 3 v 3 + ω 4 v + ω 5 v 2 + ω 6 v 3
碳排放率载重修正因子为
φ = χ 0 + χ 1 γ + χ 2 γ 2 + χ 3 γ 3 + χ 4 v + χ 5 v 2 + χ 6 v 3 + χ 7 v
式中: ϕ v为车辆空载时以速度v行驶时的碳排放量; γ为车辆在路径(ij)行驶时实际载重量与最大载重量的比值。
卡车的碳排放率(单位kg/km)为
c i j t = ϕ v φ 1000
产生1 kg碳排放量的油耗约为0.43 L,因此卡车的油耗率为
f i j t = c i j t 2.32

1.3.2 无人机能耗成本分析

无人机能源消耗与载重量之间的线性关系为
p ( m 1 + m 2 ) = α ( m 1 + m 2 ) + β
本文忽略无人机的电池质量,则式(5)变为
p ( m 1 ) = α m 1 + β

1.3.3 电动车能耗成本分析

根据Xia等11提出的燃油消耗和车辆总质量之间的线性关系,本文定义能源消耗和车辆总质量之间的线性关系为
p i j k = p 0 + p * - p 0 Q k W i k

1.4 模型构建

构建模型如式(8)所示,式(9)—(37)为约束条件
m i n   z   =   f 1 + f 2 + f 3
f 1 = C a t j N S t T x i j t + C a k i N S j N C T k K x i j k + C a v i N S j N C D v V y i j v ,
f 2 = C b t i , j N 0 N S t T x i j t p i j t d i j + C b k i , j N C T N S k K x i j k p i j k d i j + C b k i N C D v V y i j v F i v ,
f 3 = C c t i , j N 0 N S t T x i j t c i j t d i j
s . t .   i N k K x i j k + i N k K y i j v = 1 , j N C D
i N k K x i j k = 1 , j N C T
i N C D N S y i j v = i N C D N S y j i v = 0 , j N C T , v V
i N 0 N S t T x i j t i N k K x i j k + i N v V y i j v , j N S
i N C T N S x i j k = i N C T N S x j i k 1 , j N C T , k K , i j
i N C D N S y i j v = i N C D N S y j i v 1 , j N C D , v V , i j
i N C D y s i v = i N C D y i s v = 1 , s N S , v V
i N C T x s i k = i N C T x i s k = 1 , s N S , k K
j N S x 0 j t = j N S x j 0 t = 1 , t T
i N S j N S t T x i j t S - 1 , S N , i j
i N j N k K x i j k S - 1 , S N , i j
i N j N v V y i j v S - 1 , S N , i j
W i t - q j x i j t - Q t ( 1 - z i j t ) W j t W i t - q j x i j t + Q t ( 1 - z i j t ) , i , j N S N 0 , i j
W i v - q j y i j v - Q v ( 1 - y i j v ) W j v W i v - q j y i j v + Q v ( 1 - y i j v ) , i , j N S N C D , i j
W i k - q j x i j k - Q k ( 1 - x i j k ) W j k W i k - q j x i j k + Q k ( 1 - x i j k ) , i , j N S N C T , i j
λ i + λ i j t - λ j M ( 1 - t T x i j t ) , i , j N S N 0 , i j
λ i + λ i j k - λ j M ( 1 - k K x i j k ) , i , j N S N C T , i j
λ i + λ i j v - λ j M ( 1 - v V y i j v ) , i , j N S N C D , i j
E T i λ i L T i
p i j v = α W i v + β , i , j N S N C D , v V
f i v + p i j v ( t i j v + T ) M ( 1 - y i j v ) , i N S , j N C D
f i v - f j v + p i j v ( t i j v + T ) M ( 1 - y i j v ) , i , j N C D
f i v - F j v + p i j v t i j v M ( 1 - y i j v ) , i N C D , j N S
F j v E y i j v , i N C D , j N S
p i j k = P 0 + P * - P 0 Q k W i k , i , j N S N C T , k K
j N C T x i j k ε i k = 1 , i N S , k K
r j k = r i k - x i j k p i j k d i j k , i , j N S N C T
r j k B x i j k p i j k d i j k B + ε m i n , i N C T , j N S N C T
x i j t , x i j k , y i j v 0,1
目标函数式(8)为最小化总成本,其中,f 1为固定成本之和;f 2为车辆和无人机的运输费用之和,包括燃油成本、电动车能源消耗成本、无人机能源消耗成本;f 3为车辆的碳排放成本。式(9)表示每个顾客只能被电动车或无人机访问一次;式(10)表示电动车访问无人机由于载重和里程限制无法访问的客户点;式(11)表示无人机无法访问超出无人机载重和里程的客户点;式(12)表示在卡车访问中转站后,站内无人机、电动车才能开始配送服务;式(13)—(14)表示电动车、无人机对于顾客点的出入流量平衡;式(15)—(17)表示3种配送工具在中转站的出入流量平衡;式(18)—(20)为消除子回路约束;式(21)—(23)是对车辆、无人机的容量约束;式(24)—(26)表示3种配送工具满足客户时间要求;式(27)表示配送时间点满足客户需求;式(28)表示无人机在(ij)上的功率与该路径上的载重量成正线性关系;式(29)—(32)表示无人机在(ij)上的能耗约束;式(33)表示电动车在(ij)上的功率与载重量成线性关系;式(34)表示电动车从中转站出发时处于满电状态;式(35)表示电动车从客户点ij的剩余能源;式(36)确保电动车荷电不低于最低荷电状态;式(37)定义决策变量范围。

2 算法设计

上述联合配送模型是车辆路径问题的拓展,属于NP-hard问题,求解过程复杂。本文针对联合配送特征,采用贪婪策略生成初始解,并设计了基于大规模邻域搜索思想优化的遗传算法(large neighborhood search algorithm with genetic algorithm, LNS-GA),引入破坏算子和修复算子,以此扩大解空间搜索范围,避免陷入局部最优。LNS-GA算法流程图如图2所示。
图2 LNS-GA算法流程图

2.1 染色体编码

采用自然数编码方式,自然数表示客户点编号。一条染色体表示一辆卡车、电动车或无人机的路径,如式(38)所示。 染色体长度L=顾客数目+ 配送工具最大使用数目-1
可能的染色体如图3所示。
图3 可能的染色体示意图

2.2 构造初始解

基于贪婪策略生成初始解,步骤如下:
Step1:分配客户。基于距离的贪婪法则将每个客户分配给一个中转站,将每个客户按照需求递减的顺序排序,然后按照距离最近的原则将每个客户分配到相应的中转站。
Step2:确定无人机配送点。用欧氏距离计算中转站和所包含的客户之间的距离,根据此距离及客户需求判断无人机是否为此客户配送。
Step3:根据中转站包含的客户需求逆推出中转站的配送需求。
Step4:根据中转站包含的客户时间窗逆推出中转站的配送时间窗。所有客户的最早左时间窗为中转站的最早开始服务时间,所有客户的最早右时间窗减去当前中转站到达客户点的时间为中转站的最晚开始服务时间。
Step5:先根据中转站时间窗及需求决策卡车配送路径,然后得到到达中转站的时间,再决策无人机和电动车的路径。

2.3 LNS-GA算子

1)选择算子:随机遍历抽样法选择N个个体时只需一次生成N个等间距的标记指针位置,此方法可避免适应度大的个体垄断下一代。
2)顺序交叉算子:保留一个父代染色体的一段基因序列和另一个父代染色体的相对顺序来生成子代个体。
3)变异算子:随机生成的概率rand与变异概率Pm 比较,决定基因是否进行变异操作。
4)局部搜索策略
①移除算子:随机选出部分顾客,根据各个客户点之间的相关性判断,将相关性较高的任务点进行移除操作。相关性计算公式为
R i j = 1 c + v i j , c = d i j d i j m a x ( i j )
②插入算子:本文应用最远插入法,将被移出的顾客重新插回电动车或无人机路径中。
Step1:找到同时满足时间窗和容量约束的所有客户i可插入的点;
Step2:若没有合理的插入点,则新增一辆交通工具为客户i进行配送;
Step3:有可插入点则计算客户插入后的距离增量;将其从小到大排序,第一行为任一客户的距离增量最小的插入点;
Step4:找到客户点i和客户点j距离增量最小的插入点didj,比较二者的值,将距离增量较大的客户点放到路径中,得到新的可行解。

3 仿真与分析

本文算法通过MATLAB实现,使用CPLEX Studio IDE22.1.0构建数学模型,实验运行环境为Windows 11操作系统,Intel(R)Core (TM) i5-8265U CPU@1.60 GHz 1.80 GHz处理器。

3.1 算例描述

本文使用由Breunig等13提出的求解配送-选址联合决策问题的标准算例,加入Solomon数据集中的时间窗,生成了不同规模的数据集。由于缺乏小规模算例,在Step3中抽取12个客户点信息形成小规模算例。根据3种运输工具的特性设计算法,相关参数设置为:选择概率为0.9,交叉概率为0.6,变异概率为0.05,最大迭代次数为50, C a t为120, C a k为60, C a v为5, C b t为0.8, C b k为0.3, C b v为0.1, C c t为0.1, p *为0.3, p 0为0.15, α为0.271, β为0.510 5, ω 0 ω 1 ω 2 ω 3 ω 4 ω 5 ω 6分别为110、0、0、0.000 375、8 702、0、0; χ 0 χ 1 χ 2 χ 3 χ 4 χ 5 χ 6分别为1.27、0.061、-0.001 1、-0.002 35、0、0、-1.33。

3.2 算例结果分析

通过CPLEX和LNS-GA分别求解改编算例,CPLEX最大允许运行时间为3 600 s;LNS-GA对每组算例求解10次,取最小值为最优解。表1为CPLEX与遗传算法小规模算例结果对比,由表1可知,在10个小规模算例中,CPLEX平均计算时间为5.15 s;本文算法平均计算时间为6.43 s,GAP的平均值为0.18%。表2为CPLEX与遗传算法中规模算例结果对比,由表2可知,由于模型规模较大,CPLEX在限制时间内均无法求得最优解,部分算例能输出当前找到的最优上界解,其余算例无法给出可行解;LNS-GA时间上均少于CPLEX,平均运行时间为34.04 s。
表1 CPLEX与遗传算法小规模算例结果对比
算例 CPLEX LNS-GA GAP
CPU/s Cost/元 CPU/s Cost/元 误差/%
12-s01-08 5.32 603.10 5.18 604.68 0.26
12-s01-02 6.80 641.03 10.41 641.89 0.13
12-s02-07 4.47 646.86 6.99 649.51 0.41
12-s02-09 4.25 712.29 6.51 712.47 0.02
12-s04-08 6.21 536.55 5.45 536.91 0.07
12-s04-09 4.16 546.56 4.28 549.61 0.56
12-s05-06 3.14 598.94 4.11 599.01 0.01
12-s05-07 3.21 569.88 5.59 570.81 0.16
12-s06-12 6.67 633.48 10.58 634.58 0.17
12-s10-12 7.29 690.21 5.15 690.39 0.03

注:“—”表示在限制时间内无法找到可行解

表2 CPLEX与遗传算法中规模算例结果对比
算例 CPLEX LNS-GA GAP
CPU/s Cost/元 CPU/s Cost/元 误差/%
22-k4-s13-14 3 600+ 946.18 18.08 915.45 -3.25
22-k4-s09-19 3 600+ 899.78 17.40 788.58 -12.36
22-k4-s11-12 3 600+ 998.42 24.09 824.83 -17.39
22-k4-s13-16 3 600+ 804.58 37.73 629.63 -21.74
33-k4-s22-26 3 600+ 907.97 33.90 611.61 -32.64
33-k4-s01-09 3 600+ 1 048.3 15.20 864.13 -17.57
33-k4-s16-24 3 600+ 613.44 35.49 537.41 -12.39
50-s2-01 3 600+ 58.98 1 387.0
50-s2-02 3 600+ 54.33 1 693.6
51-k5-s12-18 3 600+ 36.62 692.11

注:“—”表示在限制时间内无法找到可行解

3.3 灵敏度分析

将无人机最大续航半径设定为45 km,载重分别设定为3、4、5、6 kg,进行无人机载重灵敏度分析。无人机载重灵敏度分析如图4所示,载重增加,在一定的续航半径内无人机可服务的客户点变多,由电动车配送的客户改为由无人机配送,而无人机的配送成本、配送时效都优于电动车,所以总配送成本会降低。当载重增大到一定数值后,续航半径不变,在该半径所覆盖的区域内不会再增加新的客户点。因此,车机并行配送时,载重应当设置为适中,过小会使后续配送成本提高,过大会增加初期成本。
图4 无人机载重灵敏度分析

4 结论

针对长物流链配送成本较高、配送速度较慢且碳排放量大的问题,本文提出了双层无人机-电动车联合配送路径规划问题,建立了以固定成本、能耗成本、碳排放成本之和最小为目标的混合整数线性规划模型。鉴于传统遗传算法处理此类复杂问题时依赖初始解、易陷入局部最优等缺点,本文设计了基于大规模邻域思想的混合遗传算法,应用贪婪策略生成初始解,加入破坏和修复算子提升优化效果;最后与CPLEX对比分析,验证了算法在解决2E-VRPD问题上的求解质量和寻优速度均有优势。然而,本文的研究尚属于初步探索,实际物流配送中,影响经济成本及环境成本的因素有许多,如天气、交通情况、无人机禁飞区等,未来研究可以考虑多种影响因素,进行多目标优化,以构建更加全面、贴近实际的配送优化模型。
[1]
Murray C C Chu A G.The flying sidekick trave-ling salesman problem:optimization of drone-assisted parcel delivery[J].Transportation Research Part C:Emerging Technologies201554:86-109.

[2]
Kim S Moon I.Traveling salesman problem with a drone station[J].IEEE Transactions on Systems,Man,and Cybernetics:Systems201949(1):42-52.

[3]
王新,王征,徐伟.面向多个无人机站点的车辆与无人机联合配送路径问题研究[J].运筹与管理202130(5):31-37.

[4]
许菱,杨林超,朱文兴.农村电商物流下无人机与车辆协同配送路径优化研究[J].计算机工程与应用202460(1):310-318.

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

[6]
颜瑞,陈立双,朱晓宁,等.考虑区域限制的卡车搭载无人机车辆路径问题研究[J].中国管理科学202230(5):144-155.

[7]
Dorling K Heinrichs J Messier G G,et al.Vehicle routing problems for drone delivery[J].IEEE Tran-sactions on Systems,Man,and Cybernetics.Systems201747(1):70-85.

[8]
蒋丽,杨露,梁昌勇,等.基于无人机的高层住宅最后“一百米”配送优化[J].交通运输系统工程与信息202222(4):236-245.

[9]
马华伟,宋洋.考虑同时取送货的车机协同路径优化问题[J].计算机应用研究202340(5):1335-1340.

[10]
Meng S S Guo X P Li D,et al.The multi-visit drone routing problem for pickup and delivery services[J].Transportation Research Part E:Logistics and Transportation Review2023169:102990.

[11]
Xia J Wang K Wang S A.Drone scheduling to monitor vessels in emission control areas[J].Transportation Research Part B:Methodological2019119:174-196.

[12]
Sitek P Wikarek J Jagodziński M.A proactive approach to extended vehicle routing problem with drones[J].Applied Sciences202212(16):8255.

[13]
Breunig U Baldacci R Hartl R F,et al.The electric two-echelon vehicle routing problem[J].Computers & Operations Research2019103:198-210.

[14]
Jie W C Yang J Zhang M,et al.The two-echelon capacitated electric vehicle routing problem with battery swapping stations:Formulation and efficient methodology[J].European Journal of Operational Research2019272(3):879-904.

[15]
Enthoven D L J U Jargalsaikhan B Roodbergen K J,et al.The two-echelon vehicle routing problem with covering options:city logistics with cargo bikes and parcel lockers[J].Computers & Operations Research2020118:104919.

文章导航

/