人工智能背景下的配送网络优化方法研究*

叶春森，王雪轩， 时章漫， 黄成成

(1.安徽大学 商学院，合肥，230601； 2.安徽大学 物流与供应链研究中心， 合肥 230601)

0 引 言

配送网络优化对提高配送效率、降低碳排放量、促进绿色配送发展具有重要意义。SBIHI A等[1]学者认为，为了有效降低碳排放量，有必要对传统路线规划问题的研究目标进行扩展，不仅考虑经济效益，还更应该关注对社会和环境的影响。BAUER等[2]学者则建立了考虑碳排放的多式联运模式下的决策优化模型，并对东欧的铁路运输网络进行了实证研究。CARLSSON J G和SONG S[3]提出基于卡车和无人驾驶飞机的联合配送路线规划问题。藩斌斌[4]综述了国内外不同背景下多目标路径优化算法的应用及现有成果。苏涛[5]构建了基于再订购点的电子商务低碳配送路径优化模型。李进等[6]研究了基于碳排放与速度优化的带时间窗车辆路径问题。这些研究为建立人工智能与传统配送融合的新模式奠定了基础，但对其差异和优势分析的文献还较少。本文在分析传统卡车配送和无人机配送各自优缺点的基础上，提出卡车与无人机的联合配送模式，分别以碳排放量与配送效率为目标，建立相关模型，提出相应解法，以展示人工智能与传统配送模式融合发展的重要意义。

1 单卡车和无人机联合配送模式

1.1 传统单卡车配送模式

在传统配送路线选择问题中，设集合U={p1，p2，…，pn}为某一区域的n个配送点集合，对任意的pi，pj∈U，令dij表示配送点pi与配送点pj之间的距离，xij=1表示配送点pi与配送点pj相连接，xij=0表示配送点pi与配送点pj不相连。特定的配送工具要走到上述的每一点，具体过程如图1所示；其一次配送过程的最优化问题则可建立如下数学模型：

(1)

(2)

其中目标函数式(1)表示为从任一配送点出发，途中经过所有集合U={p1，p2，…，pn}中其他配送点节点后再回到出发点行驶距离最短。约束条件式(2)分别表示对于每个配送点有且仅有一条路径出去；对于每个配送点有且仅有一条路径进入。另外还有个约束条件为除了起点与终点外，各条路径不构成圈。

图1 单独卡车配送

1.2 卡车和无人机联合配送模式

传统单独卡车配送相对于无人机配送具有规模经济性，但其单位配送成本高，而无人机单位配送成本低，并且可以在没有人为干预的情况下运行，即不受道路交通影响的情况下高速行驶。但无人机载重量极低，行驶半径小。针对单独卡车与单独无人机两种配送模式的优势与不足，本文考虑在人工智能背景下对单独卡车配送模式进行优化，采用卡车与无人机联合配送模式。确定一个无人驾驶的交付系统的效率飞行器(UAV)通过正在移动的卡车向客户提供服务。即配送的过程为无人机从卡车上拿起一个包裹(卡车继续行进)，并将包裹送达到相应的配送点完成配送后即包裹交付后，无人机再返回到卡车装载下一个包裹并进行配送，直至完成所有的配送任务。卡车与无人机联合配送模式下的配送路线如图2所示。其中实线轨迹圆为卡车的行驶路径，轨迹圆周围的虚线轨迹为无人机对各个配送点的配送路径。采用这种联合配送模式可以有效结合单卡车与单无人机两种配送模式的优势与不足。

图2 卡车与无人机协调配送

2 卡车与无人机联合配送路径规划

联合配送模式下首先确定卡车行驶的路径，本文将卡车的最优配送路径规划为一个圆，再基于卡车配送路径上确定无人机对每一个配送点配送的起始点与返回点。

2.1 卡车配送路径的规划

对于卡车配送路径的规划，首先采用重心法求得各配送点的重心坐标，接着以重心为圆心，以各配送点到圆的距离和最短为目标函数确定其半径，求得的圆即为卡车的配送路径。具体步骤如下：

(1) 重心法确定圆心。假设U={p1，p2，…，pn}为一个区域内n个配送点的集合，将配送点的坐标设为(pix，piy)，其中i=1，2，…，n，配送点的重心坐标设为P(x0，y0)，重心点到各配送点的运输费用设为w1di，其中w1为无人机运输费率(单位为元/km)，di为重心点到各配送点的直线距离，其中di为

di=[(x0-pix)2+(y0-piy)2]1/2

再以重心到各个点的总费用T最小为目标函数，求出重心坐标，其中T为

(2) 确定路径圆的半径。以各配送点的重心点为圆心，以各配送点到圆面的距离和最短为目标，求得路径圆的半径R。即：

2.2 无人机配送路径规划

2.2.1 效率约束下的无人机配送路径规划模型

对区域内n个配送点集合U={p1，p2，…，pn}，其中i=1，2，…，n，卡车与无人机联合配送模式下，令卡车行驶的速度为φ0，无人机行驶的速度为φ1，配送时间为T1，目标函数则求解最短配送总时间。对每个配送点pi，确定无人机从卡车配送路径上配送起飞点Ii及配送返回点Oi。为简化计算，考虑在极坐标系下建立模型，以卡车配送路径的圆心P(x0，y0)为原点，则各个配送点的坐标可表示为pi(ρ，θ)，无人机对每个配送点pi的配送起飞点可表示为Ii(R，θIi)，返回点可表示为Oi(R，θOi)，在极坐标系下以配送时间最短为目标函数建立模型如下：

(3)

(4)

目标函数(3)中‖·‖表示两点之间的距离，T1为无人机单独行驶配送的总时间与卡车载着无人机行驶总时间之和。约束条件(4)分别表示为卡车在配送过程中无返程现象；无人机的上一个配送返回点处于下一个配送起点之前；对于每个配送点pi，无人机配送的行驶时间要大于卡车在无人机起飞点Ii及配送返回点Oi间的行驶时间。

2.2.2 碳排放约束下的无人机配送路径规划模型

物流活动中的碳排放主要来源于物流活动中消耗各类物质和能源所带来的间接或者直接的二氧化碳排放。现以在物流活动过程所消耗的燃料量来核算碳排量，其代换公式为碳排量=燃料消耗量×CO2排放系数[7-8]。为简化问题，假设物流活动中的燃料消耗量与运输距离有关，设单位距离下卡车配送的燃料消耗量为β0，无人机燃料消耗量为β1，已知CO2排放系数为e0。

卡车与无人机联合配送模式下，令卡车与无人机总的碳排放量为E1，以整个配送过程中碳排放量最小为目标函数建立模型如下：

2πRβ0e0

(5)

其中目标函数(5)中前半部分为整个配送过程中无人机配送的碳排放量，后半部分为卡车配送的碳排放量。

3 模型求解

3.1 单卡车配送路径规划模型求解

单卡车配送问题是一个NP难问题，遗传算法能较好地解决这一问题。其求解单卡车配送问题有三步：首先对配送点进行编码，从而产生解集的初始种群M；其次通过设定Pc和Pm产生新的种群，不断繁衍进化；当到达预订迭代次数T后，收敛于最适应环境的个体即为问题满意解[9-10]。同时令单独卡车配送碳排放量E0=θβ0e0，配送效率T0=θ/φ0，以完善单卡车配送模型。

3.2 联合(无人机)配送路径规划模型求解

本文通过LINGO软件对效率约束下联合配送模式的路径规划进行求解，由于模型的变量较多，本文在求解过程中对初始解的设置进行了特定编制，从而快速得到最优解。

在碳排放量约束条件下，当卡车的行驶路径确定时，以无人机配送距离最短为目标确定的无人机配送路径即为模型的最优解。求得各个配送点与卡车行驶路径圆心的连线与圆的交点即为无人机最优配送起始点与配送返回点，此时配送起始点与返回点重合。

4 算 例

4.1 算例描述

已知区域内有12个待配送的需求点，假设其坐标分别为

p1(24.80，12.75)p2(28.65，14.55)

p3(34.26，12.74)p4(22.09，20.12)

p5(18.39，15.49)p6(12.99，20.33)

p7(14.71，13.03)p8(8.47，15.41)

p9(8.28，10.86)p10(19.84，10.54)

p11(34.71，20.73)p12(35.72，16.50)

其中坐标轴的单位为km。已知具体相关参数值如表1所示。

表1 相关参数及数值

4.2 结果对比

在单卡车配送路径规划的遗传算法求解中，令M=20，T=100，Pc=0.6，Pm=0.05，结果如图3所示：

图3 单卡车配送模式优化路径Fig.3 Optimization path of single truck distribution mode

由卡车与无人机联合配送模式，求得联合配送模式下卡车配送路径圆心坐标为P(21.01，14.94)，圆的半径R=7.657。通过求解碳排放及效率约束下的无人机配送路径规划模型，得到两种约束条件下卡车与无人机的最优配送路径，如图4—图5所示。

通过模型结果可得单独卡车配送碳排放量及效率值与卡车和无人机联合配送碳排放量及效率值对比，如表2所示。

由表2中的结果可知，卡车与无人机的联合配送模式相比于单独的卡车配送模式在配送效率以及碳排放量有明显优化。

图4 配送效率约束下最优配送路径Fig.4 Optimal distribution path under the constraint of distribution efficiency

图5 基于碳排放量优化后配送路径Fig.5 Optimal distribution path under carbon emission constraints

模 式配送效率碳排放量卡车配送模式T0=1.832 5 hE0=286.970 7 kg联合配送模式T1=1.071 9 hE1=249.591 5 kg

5 总 结

本文提出卡车与无人机联合配送模式，建立相应模型，设计相关求解方法，对指导人工智能在配送中的应用具有指导意义。