随着我国政府推出一系列关于智能制造和“互联网+”的标准化和相关产业融合政策, 对我国物流行业的发展起到了极大的促进作用. 根据刘林山^[1]文中所述, 2018年618全球年中购物节的时候, 电商平台京东1天累计下单金额达到1592亿元, 天猫、苏宁易购、国美Plus、亚马逊中国等47家电商平台总销售额达到2844.7亿元. 因此, 拥有一套完善、现代的物流体系是各大电商当前最迫切需要解决的问题.

此外, 我国的物流成本近年来已经占到我国的GDP的18%, 比发达国家要高出一倍左右. 其中一个重要原因在于物流的环节过多, 而其中“最后一公里的配送”占到总成本的30%以上. 基于此, 本文的研究重点在于优化“最后一公里”的配送过程以及耗费的成本.

现有“最后一公里配送”之所以成本较高, 主要有以下几点原因:

(1)运输工具问题. 快递人员送货的交通工具, 如电动车、自行车等, 不仅送货速度慢, 效率低下, 而且交通事故时有发生, 快递人员易受伤, 货物易破损. 同时, 也加剧了道路的拥挤状况.

(2)从业人员缺少. 快递行业属于劳动密集型行业, 从业人员的工作强度较大, 一旦遇上如双十一等高峰期就会出现爆仓现象.

(3)安全问题和道德问题. 随着电子商务的不断发展, 物流信息追踪过程中的漏洞也逐渐暴露了出来. 通常客户下单后, 对快递的追踪只停留在片面的地点信息上, 当出现丢件, 损件的情况, 难以进行责任确定.

(4)运输难度和成本. 经济发展较好的城市区域, 往往是客户需求大的地区. 然而, 发达城市的道路交通情况往往都不容乐观, 尤其是上下班时期. 与此相对的乡村地区, 虽然道路车辆较少, 但是客户比较分散, 距离配送点也较远, 道路情况也比较复杂, 对快递人员的安全也存在一定的影响.

针对上述问题, 一些快递公司, 如京东、亚马逊逐渐开始尝试使用无人机进行“最后一公里”的配件服务. 使用无人机送货具有下面的这些优点:

(1)使用无人机, 可以不受地面交通情况的影响, 还可以在一定程度上缓解地面道路的拥挤情况. 同时, 配件服务无人化, 对快递从业人员的安全也是一种保障.

(2)降低配送时间. 根据文献[2], 亿航智能携手大灰狼快运公司开通了全国首条城市内无人机物流快递航线, 可以将该线路的单程配送时间从40 min大幅缩短至8 min.

(3)物流信息便于跟踪. 由于使用无人机, 相比于传统配送, 配送路线和配送单位可以明确追溯, 在一定程度上能缓解丢件等问题.

(4)在乡村地区道路情况相对较差的情况, 依然可以以相对安全的方式进行物件的配送.

在无人机逐渐应用到物流的同时, 学者做了很多工作, 希望能从技术层面上提高无人机的续航能力、安全性、稳定性以及载重能力, 这些都是无人机送货的局限所在. 在这些现实约束条件下, 无人机的路径规划方案显得尤为重要. 下面列出了一些关于无人机应用于物流配送的相关工作.

许卫卫等人^[3]在A*算法的基础上考虑了低空规划区域、物理性能等内外限制, 设计了一种改进的A*算法用来快速求解路径. 其仿真实验结果也表明此算法能够快速规划出危险程度小、能耗小的避障运输路径. 任新惠等人^[4]主要论述了车辆和无人机组合运行的4种模式. 另外还探讨了目前无人机和车辆组合路径规划的一些现实因素, 如无人机电池电量、运送包裹数量和时间窗等. 常波等人^[5]针对无人机的三维航迹规划问题提出了一种基于几何法的航迹规划算法, 研究了无人机最大过载系数、最大平飞速度、升限等性能与航迹可行性的关系, 并得出了生成最优航迹的限定条件. 杨玉等人^[6]针对无人机的航迹规划问题提出了一种融合简化稀疏A*算法与模拟退火算法的航迹规划方法, 其实验结果表明相比于稀疏A*算法内存占有量少了两个量级, 与模拟退火算法相比其所得航迹的综合代价平均减少了35%左右. 王琪等人^[7]根据遗传算法与动态的稀疏A*搜索算法各自的特点, 提出了一种新的组合优化算法来解决不确定环境下的自适应航迹规划, 仿真实验结果表明该组合算法不但能生成近似最优解而且能够满足在线实时应用的要求.

从这些相关文献可以看出, 当今学者在解决无人机的路径规划时大多使用的是元启发算法, 如遗传算法等智能算法. 使用这些启发式算法可以高效的解决无人机的路径规划问题, 然而这些方法本身也存在一些问题, 如容易陷入局部最优、收敛时间过长等. 本文使用的自适应大邻域搜索算法则可以通过一些优良的邻域搜索算子来跳出局部最优以及保证算法能够快速的收敛到全局最优. 此外借鉴于当前学者的一些启发式算法, 在本文中我们使用了启发式的方法来进行邻域搜索算子的选择从而进一步提高了算法的搜索效率.

1 问题描述

在使用无人机进行“最后一公里”的物流配送过程中, 无人机必须从仓库点出发并最终返回仓库点, 所有的顾客的货件只能被一个无人机送达且只能送达一次. 另外, 由于无人机本身的载重和电量限制, 所以我们在规划路径的时候, 需要保证其载重量不能超过其最大载重量以及保证无人机能够返回仓库点. 另外, 顾客通常会要求货件在规定的时间内到达, 因此除了需要考虑路线长度还需要将因为送货时间超过顾客的规定最晚时间导致顾客的满意度下降所带来的损失考虑在内. 下面将给出该问题的数学模型.

${C}$ 表示所有需要服务的顾客集合, 0表示仓库点, S表示需要服务的顾客点和仓库点的集合, ${A}$ 表示使用的无人机集合. ${{X}}_{{i}{j}{a}}$ 为0–1整数变量, 等于1时表示无人机a从点i到达点j, 其他情况则为0. ${{W}}_{{i}}$ 为第i个顾客所需货物的重量, N为无人机的最大载重量. ${U}({a},{b})$ 为无人机在当前载重量为b时行驶a距离所耗费的电量, Q为无人机的电池容量, ${{W}}_{{a}{i}}$ 为无人机a在到达顾客点i时的载重量. ${{T}}_{{i}}$ 为到达顾客i的时间, ${{s}}_{{i}{j}}$ 为无人机从点i到点j所花费的时间.

目标值如式(1)所示由两部分组成, TD表示所有路线的总长度, 第二部分中的Arrive(i)表示到达顾客点i的时间, T(i)表示顾客i所要求的最晚送达时间, $\;{\beta }$ 表示惩罚系数. 其意义为我们在最小化路线长度的同时要尽可能避免不能按时服务顾客的情况发生:

$f = \alpha \times TD + \beta \times \sum\limits_i {\max (0,Arrive(i) - T(i))} $

(1)

约束(2)表示所有的无人机需要从仓库点出发:

$ \mathop \sum \limits_{i \in C} {X_{i0a}} = 1,a \in A $

(2)

约束(3)保证了所有点的出度和入度相等:

$ \sum\limits_{i\in S}{X}_{ija}=\sum\limits_{i\in S}{X}_{jia}, j\in S,a\in A $

(3)

约束(4)限制了所有的顾客点均被访问一次且仅被访问一次:

$ \mathop \sum \limits_{a \in A} \mathop \sum \limits_{i \in S} {X_{ija}} = 1,j \in C $

(4)

约束(5)保证了所配送的货物总重量不会超过无人机的最大载重量:

$ \mathop \sum \limits_{i \in S} \mathop \sum \limits_{j \in C} {X_{ija}}\times{W_j} \le N,a \in A $

(5)

约束(6)为无人机的电量约束:

$ \mathop \sum \limits_{i,j \in S} {X_{ija}}\times U\left( {{d_{ij}},{W_{ai}}} \right) \le Q $

(6)

约束(7)和约束(8)为时间约束:

$ {{{T}}_{{i}}} + {s_{ij}} - M\left( {1 - \mathop \sum \limits_{a \in A} {x_{ija}}} \right) \le {T_j},i \in C,j \in C $

(7)

$ {{{T}}_0} + {s_{0j}} - M\left( {1 - \mathop \sum \limits_{a \in A} {x_{0ja}}} \right) \le {T_j},j \in C,a \in A $

(8)

2 算法描述

自适应大邻域搜索(ALNS)算法是由Ropke与Pisinger^[8]在2006年提出的一种元启发式方法, 该方法在邻域搜索算法的基础上加入了自适应的机制, 能够根据搜索算子的历史表现来自动选择好的邻域搜索算子, 从而能够增加找到更高质量解的几率. 该方法属于邻域搜索算法变种方法之一. 在邻域搜索方法的变种方法中, 有的算法可以只使用一种邻域搜索算法, 如模拟退化算法, 遗传算法等. 该类算法的邻域搜索部分仅搜索了解空间的一小部分, 找到全局最优的概率较小, 这类算法的优势之一可以避免陷入局部最优. 而有的算法可以使用多种算子, 如变邻域搜索算法, 该算法通过对当前解进行多个邻域中搜索从而可以以更高的概率找到全局最优解. 但是经典的变邻域搜索算法在选择搜索算子的时候过于随机, 缺乏了一些启发式信息的指导. 自适应大邻域搜索算法就弥补了这种不足, 该算法通过搜索算子的历史表现与使用次数来选择下一次迭代使用的算子, 通过这种启发式的搜索可以有较大概率找到更好的解. 自适应大邻域搜索算法的步骤如算法1所示: (1) 生成初始解; (2)根据邻域搜索算子的分数, 使用轮盘赌来选择邻域搜索算子. 然后对当前解使用该邻域搜索算子进行改进. 最后更新该邻域搜索算子的分数; (3)重复步骤(2)直到达到最大迭代次数, 返回找到的最优解并退出程序.

算法1. 自适应大邻域搜索算法

输入: 顾客的订单信息以及无人机的相关参数

输出: 满足约束条件下的最优解

Begin

生成初始解T

记录当前最优解S=T

While 当前迭代次数小于最大迭代次数:

根据当前邻域搜索算子的各自分数选择一个邻域搜索算子O

将解T应用邻域搜索算子O, 获得改进解I

If f(I) < f(T):

更新邻域搜索算子O的分数

T = I

EndIf

更新当前最优解S, 将当前迭代次数加1

End

返回最优解S

End

2.1 初始解的生成

本文采取了逐点选择的方法来构造初始解. 首先, 我们初始化一个当前可访问列表. 然后, 我们考虑所有未被访问过的顾客点, 如果能够满足如下条件就将其放入可访问列表里面: (1)该顾客的货件重量不超过当前无人机的最大载重量. (2)当前无人机的电量可以支持无人机从当前点出发到达该点并能够返回仓库点. 当得到可访问列表后, 我们根据列表内的顾客点距离当前点的距离来进行选择, 即距离当前点越近的顾客被选择的概率就越大. 例如: 当前点为0, 可访问列表为[2,5,6], 点0距离可访问列表内各点的距离为[10,8,5], 那么我们就以其距离的倒数归一化之后的值作为选择该点的概率, 即得到选择2的概率为0.24, 选择5的概率为0.29, 选择6的概率为0.47. 然后我们将当前点更新为该步骤选择得到的点, 并重复上述步骤, 直至所有顾客点均被服务过. 需要注意的是, 如果计算得到的访问列表为空的话, 表明当前路线已经构造完成, 那么无人机就执行返回仓库点的操作, 并重新从仓库点出发, 计算新的服务路线. 最终获得的初始解的形式类似于[[0,1,2,3,0], [0,4,5,6,0]], 这表明我们总共需要两个无人机完成送货任务, 第1个无人机从仓库点出发依次服务顾客1,2,3并返回仓库点, 第2个无人机从仓库点出发依次服务顾客4,5,6并访问仓库点.

2.2 邻域搜索算子

本文使用了来自文献[4]的5种邻域搜索算子.

(1) 2-opt. 选择一条路线的部分顾客, 逆序其访问顺序.

(2) Swap(1,1). 交换两条路线的顾客点.

(3) Shift(1,0). 将一条路线的顾客点, 插入到其他路线.

(4) CrossOver. 选择两条路线, 然后将其分为两部分将第1条路线的前部分和第2条路线的后部分进行组合, 第2条路线的前部分和第1条路线的后部分进行组合.

(5) Exchange. 选择一条路线, 交换其中两个顾客点的服务顺序.

本文在执行上述邻域搜索的时候, 只选择对当前解有改进的操作, 如果存在多个操作可以改善当前解的质量, 则只选择其中改善程度最大的操作进行当前解的更新.

2.3 自适应邻域算法选择

在本文中, 每个算子的分数由两部分组成: (1)该算子的历史表现; (2)该算子的使用次数, 然后将这两部分进行加权求和作为该算子的最后分数. 具体如式(9)所示, 其中score表示算子的最终分数, ${h}{i}{s}{t}{o}{r}{y}$ 表示算子的历史表现, ${c}{n}{t}$ 表示该算子的使用次数, ${\alpha }$ 表示权重系数.

$ score = \gamma \times history + (1 - \gamma ) \times \frac{1}{{1 + cnt}} $

(9)

其中, 算子的历史表现更新量, 按照式(10)进行更新, f为式(1)用来计算目标值, old为当前解, new为进行邻域搜索后的解. 如果执行该邻域搜索后, 解的质量没有改进, 则当前算子历史表现的更新量为0即保持不变, 如果有改进的话, 则更新其历史表现分数. 第一部分为使用该算子所导致的提升量, $ \mathrm{\theta } $ 则是固定提升量. 另外, 无论是否改进, 该算子的使用次数都增加1.

$ \begin{array}{l} {{histor}}{{{y}}^{{{new}}}} = histor{y^{old}} + \delta \text{, } \\ {{\delta }} = \left\{ {\begin{array}{*{20}{l}} 0, \; {{{f}}\left( {{{old}}} \right) <{{ f}}\left( {{{new}}} \right)} \\ {\dfrac{{{{f}}\left( {{{old}}} \right) - {{f}}\left( {{{new}}} \right)}}{{{{f}}\left( {{{old}}} \right)}} + {{q}}},&{{{f}}\left( {{{old}}} \right) > {{f}}\left( {{{new}}} \right)} \end{array}} \right. \end{array} $

(10)

3 实验验证

本文使用的数据集来自于文献[9]中的Solomon数据集. 该数据集的顾客规模分别为25, 50, 100. 数据类型分为R型, C型和RC型. R型数据表明顾客的数据分布全部为随机生成的, C型数据意味着顾客的分布是通过聚类操作之后生成的, 即分布区域较为集中, RC类型则是混合这两种数据分布类型的. 其中RC类型分布的数据如图1所示.

3.1 参数设置

根据Song等人在文献[10]中的研究表明, 无人机的耗电量公式如式(11)所示, 其中Q为无人机最大载重, e为空载时无人机的耗电量其值为20 mAh/s, v为无人机的飞行速度其值为10单位每秒. 另外所使用样例中两点之间的最大距离设置为1500单位, 其他点距离按照同比例缩放. 无人机的最大载重量来自与具体的数据集文件所给出的数值. 自适应大邻域搜索的最大邻域搜索次数为5, 最大迭代次数为100. ${\alpha }$ 值为1, $\;{\beta }$ 值为0.2, ${\gamma }$ 值为0.9, ${\theta }$ 为1.

$ {U}\left({{d}}_{{i}{j}},{W}_{ai}\right)=\left(1+\frac{{W}_{ai}}{Q}\right) \times e \times \frac{{d}_{ij}}{v} $

(11)

3.2 实验结果

图2为该算法在样例RC101中得到的结果, 从图中可以看出路线之间几乎没有交叉的情况且把位置相近的顾客分配给同一辆无人机进行配送, 这样可以最大程度地节省无人机资源.

其具体数据如表1所示, Problem表示了测试的样例名称, Std, Mean, Best, Worst, CT分别表示的为程序运行10次的标准差, 平均值, 最好值, 最坏值以及程序的平均运行时间(s). 从表1可以看出, 程序运行结果的标准差在数据规模为25和50的时候基本在0.001左右, 随着问题规模的增加至100的时候, 标准差保持在相当小的值0.3以下, 这体现了本文所设计的算法不仅在小规模样例上具有很强的稳定性, 随着问题规模的增加算法的稳定性依然能够保证. 另外从表1可以看出算法在问题规模为25的运行时间为2 s左右, 问题规模为50时运行时间为10 s左右, 问题规模为100时运行时间在30–50 s之间. 算法的运行时间和问题规模基本是呈线性关系的, 这说明本文提出的算法能够在有限的时间内对大规模问题进行求解. 为了进一步验证本文设计算法的有效性, 本文设计了和GA (遗传算法)^[11], DPSO (离散粒子群算法)^[12]的对比实验, 各算法得到的目标值如表2所示, 其中加粗字体为3个算法所获得的最好结果. 根据表2中的数据可以看出本文提出的ALNS算法在总共18个样例上均得到了最好的结果. 这表明了本文提出的算法相比于经典的遗传算法和离散粒子群算法可以进一步地节省无人机进行物流运输的综合代价. 本文ALNS算法还具有非常强的扩展性和提升潜力比如说可以通过增加邻域搜索算子的方式来进一步地提升所获得的解的质量.

表1和表2实验结果表明, 本文与同类工作相比主要具有3点优势: (1)求解的效率更高, 能得到更高质量的解; (2) 具有很强的扩展性; (3)能够应用于大规模的问题的求解.

4 总结

本文探讨了使用无人机来进行“最后一公里”的物流配送的现状和实际应用价值以及设计了自适应大邻域搜索算法成功地解决了在具体配送过程中的路径规划问题. 首先, 我们将算法应用到经典数据集上来验证了我们算法的稳定性和鲁棒性. 然后我们又设计了和经典的遗传算法以及离散粒子群算法的对比实验证明了本文提出的算法对于该问题的求解是十分有效的. 接下来, 我们将研究在更复杂的环境下的路径规划, 如含有禁飞区的约束条件下进行无人机的路径规划. 除此之外, 还将尝试设计一些更加高效的邻域搜索算子来进一步提升解的质量.