KMG：考虑逆向物流的无人机路径规划策略研究

       1 引言

       随着逆向物流的需求不断提高，国内外自营物流企业的物流配送成本急剧上升。通过包含逆向物流的路径规划模型，物流厂商在商业领域的成本问题上可以得到改善和优化。无人机是一种通过动力驱动的无人驾驶、可重复使用的飞行器[1-3](unmanned aerial vehicle，UAV)。2013年9月，国内物流公司顺丰速运首次进行了无人机派件测试；2013年12月初，美国电商巨头亚马逊公司和联合包裹运送服务公司(UPS)先后宣布启动无人机配送项目；2015年11月，亚马逊向媒体公开展示最新一代无人机Prime Air drone[1]；2016年5月，国内大型自营物流电商京东也推出两款无人机，分别是垂直起降固定翼无人机和三轴六旋翼无人机[4]。DHL、淘宝菜鸟物流、圆通等企业都测试或构想无人机运送方案。物流公司都认识到，启用无人机投递快件能够缩短客户从订货到签收的时间，并且无人机具有垂直起降、起飞着陆场地小、空中悬停、机动灵活、任务能力广泛、造价低等功能特点和应用优势[5,6]。

       美国物流管理协会提出逆向物流的定义：为了资源回收以及处理废弃物，并且成本控制在有效和适当的范围。对原材料、在制品、成品和相关信息，从消费点到原始出产点的流动和储存进行规划、执行与管理的过程，从而达到回收价值和适当处置的目的[7]。在物流的逆向过程中，物流的复杂性和不确定性给当代物流企业带来不小的额外物流成本。所以逆向物流受到了越来越多企业的重视[8]。

       目前针对包含逆向物流的路径规划问题，国内外学者对无人机路径规划研究方向总体上可以分为两类。一类是将正向物流和逆向物流分开处理，将二者进行不同的分配调度[8-10]。其好处是能快速适用于当前物流规划模型，能最大程度上的保留原先物流模型和资源。但是在逆向物流的数量级较大时，此方案会导致调度总成本指数级增长[11]。第二类是将逆向物流和正向物流融合在一起进行处理，采用欧拉回路使得调度成本降低[7]。因为最后一公里配送的特殊性，通过对包裹派送地点聚类，将区域划分从而提高配送效率，减少无人机配送数量[7,11,12]。但是受限于无人机载荷量的约束，在[4,13-15]基础之上还需要考虑派送包裹之间不同差异性。因为无人机的载荷量取决于不同属性值的包裹，所以一些质量和体积较大的包裹会减少该批次携带包裹数量的上限。

       为了针对逆向物流需求的不确定性，本文KMG模型需要处理不同数量级的包含逆向物流路径规划。根据企业的不同情况，将逆向物流也融入到传统物流路径之中。并且企业可以针对不同地区、不同时期的条件下建立仿真模型，提前合理分配不同地域无人机数量的调度，将物流成本降到最低。对应不同数量、位置、大小和重量包裹，通过带权值的拓展性K-Means++来确定无人机最小数量。本文KMG模型把配送点的坐标数据映射到连通图中，将问题转化为TSP旅行商问题[9]，通过一种特殊字符编码型的遗传算法求解派送路径的最优解。因此有效避免算法迭代过程中奇异解的产生，从而得到每架无人机的飞行最优派送路径。在设计模型是还需要考虑到无人机的性能指标[15]，如最大飞行速度60千米/小时，铅垂面内最大加速±2米/秒[2]，最大续航时间为2小时[16]，飞行时的转弯半径不小于100米，最大爬升(俯冲)角度为±15°，与其它障碍物(含地面)的安全飞行距离不小于50米，最大飞行高度为海拔1000米等[17]。

       2 KMG模型

       2.1 KMG模型结构

       在KMG模型结构中，派送区域的经纬度坐标数据为｛X[,1]，X[,2]，…，X[,n]｝；W[,j]为对应特征属性X[,j]的加权系数，其中特征属性X[,j]包括包裹的数量、体积、质量和正逆向；K为当前派送任务最小无人机数量；TSP最优路径可行解为T=[t[,1]，t[,2]，…，t[,n]]。

      

       图1 KMG模型流程图

       如图1所示，区域派送任务可以转化为子区间内派送问题。在每一个子区间内实现无人机派送的最优路径，从而实现整个区域的派送任务。通过聚类算法，将区域分块化并符合一台无人机的执行能力。无人机在执行派件任务时，每一架无人机派送路径是欧拉回路，所以在设计物流路径可以融入逆向物流。逆向物流采用不同特征属性值X[,j]与正向物流所区分，以便加权拓展性K-Means++聚类算法确定无人机最小数量K。在派送的过程中，随着派送的进度无人机的载荷量会逐步提高。针对这部分的载荷量，KMG模型将空出的载荷量分配给逆向物流，从而实现高效的路径规划。当无人机分配到对应的派送任务时，在子任务中采用遗传算法对TSP问题求解，最终得到调度策略。因此在KMG模型中，无需将逆向物流和正向物流分开处理。当有逆向物流需求，采用加权聚类的方式判定是否能符合载荷量从而规划对应的派送路径。

       2.2 加权归一化

       对于配送包裹有数量、位置、体积和质量四个特征属性，只考虑位置参数对其聚类太过于片面化[15]。因此将其数量、体积、质量和正逆向这四个数值加权后的结果，作为坐标数据的加权系数，从而解决不同坐标下权重分配问题。数量、体积、质量的单位、物理意义和定义域的范围都各不相同，所以在数值加权前必须进行归一化处理，解决数据不统一的问题。考虑到三个数据的物理意义，直接将其映射到[0，1]区间，式(1)。

       X[(i)][,j]=X[(i)][,j]-min/max-min。 (1)

       其中max为X[,j]定义域内的最大值；min为X[,j]定义域内的最小值；X[,1]为包裹的数量；X[,2]为包裹的体积；X[,3]为包裹的质量；X[,4]为正向或逆向物流。