生鲜农产品车辆和无人机组合配送路径优化及效果测试

张荣, 庞梦荻, 刘斌

(1.上海海事大学物流科学与工程研究院,上海 201316;(2.上海理工大学管理学院,上海 200093)

随着冷链市场规模的不断壮大,物流服务系统的不断升级,生鲜农产品电商数量的急剧增多,冷链的配送方式和配送质量[1-2]成为用户广泛关注的重点问题。因生鲜农产品的保质期相对较短,通常会采用冷链的方式进行运输和配送[3-4],但是在配送过程中,路径规划会直接影响配送效率以及配送经济成本;并且生鲜农产品在配送过程中,由于类别较多,在配送时会产生不同的配送总成本[5-6];除此之外,在生鲜农产品配送过程中,无法依据生鲜农产品的保鲜时间长短进行针对性配送,保鲜期较短的产品会发生延迟配送现象,导致产品损坏。

为提升生鲜农产品物流配送效率,基于时间窗和温度控制[7],提出生鲜农产品配送优化方法,该方法主要是针对产品的生鲜价值构建配送物流优化模型,实现产品配送物流优化。但是在应用过程中,无法对配送中心位置进行确定。因此,如果配送距离较远时,则配送效率仍然较低。为实现生鲜农产品配送路径规划,构建生鲜农产品鲜度最大化目标函数[8],并通过改进的遗传算法进行求解,实现产品配送路径优化。但是,该方法在应用过程中,无法针对重件和轻件的分类配送,因此,配送成本仍旧较高。

无人机在多个领域中均具有良好的应用效果,例如快递运输、航拍、电力巡检等领域[9]。蚁群算法在优化路径寻找方面具有极好的应用效果[10]。因此,本研究结合生鲜农产品车辆配送存在的不足,将车辆和无人机相结合用于生鲜农产品配送,并且利用蚁群算法在优化路径规划方面的优势,实现生鲜农产品配送。

1 生鲜农产品车辆与无人机组合配送方案优化

1.1 生鲜农产品冷链配送体系要求

近几年来,随着电商平台的规模不断扩大,消费者对生鲜农产品的需求不断增加,利用无人机对生鲜农产品进行配送也是新兴起的一种配送服务模式。由于其发展时间不长,难免在配送过程中存在一定的问题和不足。除此之外,生鲜农产品的属性与其他产品存在显著差异[11],其具有鲜活性、易腐坏性、地域差异性以及需求稳定性等。基于这些特性,生鲜农产品在配送过程中,需进行冷链运输,以此避免影响产品的鲜活性以及避免产品发生腐坏。

研究生鲜农产品车辆与无人机组合配送路径规划时,需充分考虑当下生鲜农产品冷链配送体系[12],生鲜农产品冷链配送体系见图1。

图1 生鲜农产品冷链配送体系

由图1可知,生鲜农产品冷链配送整个过程中,主要包含低温存储、低温运输、低温销售,客户提取4个部分,低温运输过程中,配送中心是生鲜农产品冷链配送结构中的核心。因此,为保证生鲜农产品车辆与无人机组合配送路径规划效果,需先确定生鲜农产品配送中心位置。

1.2 生鲜农产品配送中心的确定

根据运输物品的性质、种类可以划分出多种配送中心,使产品运输路径的规划更具针对性。生鲜农产品配送是配送中心的业务之一,生鲜农产品通过冷链配送结构,在低温条件下运输至配送中心,并由配送中心进行下一步分区配送[13-14]。生鲜农产品配送过程中,由于该类产品对配送方法、配送路径的要求较高,运输途中的环境、温度等条件均会直接影响资源利用效益、物流需求、物流时效性以及物流成本等[15-16],所以需要重视生鲜农产品的运输配送。因此,在规划生鲜农产品配送路径前,需要从多个配送中心中确定出主营生鲜农产品的配送中心。

配送中心主营业务的确定需要依据配送中心的业务分类和覆盖范围完成。为实现生鲜农产品配送中心的选取,并保证生鲜农产品运输的合理性,采用模糊K-means聚类方法确定生鲜农产品配送中心成为配送中心主营业务的必要性。该方法在确定过程中,需考虑生鲜农产品的类型及运输配送要求自然环境因素、交通运输因素以及服务质量因素等多个影响因素[17-18]。因此,将果蔬花卉产品、冷鲜冷冻肉产品、水产品作为一级指标,对生鲜农产品的类型进行初步确定,为选取生鲜农产品配送中心作为配送中心主营业务做铺垫。根据一级指标进行细化,设置二级运输要求指标,每个一级指标下可划分出多个二级指标,果蔬花卉产品的二级指标为产品包装程度、运输配送稳定性;冷鲜冷冻肉产品的二级指标为配送环境温度、运输状态;水产品的二级指标为运输方式、配送时长。通过梯形直觉模糊数描述一级与二级指标不同因素的属性;将所有的特征值进行集成处理后,使其均位于一级指标上,获取一级指标,在此基础上结合K-means聚类方法,通过生鲜农产品类型及配送要求,选取聚类要求,进而获取生鲜农产品配送中心作为配送中心主营业务的必要性。配送中心确定流程如下所述:

步骤1:设一级指标综合评价值的梯形模糊数为w=(a,b,c,d),其中a、b、c、d表示配送中心一级评价指标的模糊属性,集成后一级指标的梯形模糊数值集成数值计算公式为:

(1)

式中:v表示决定生鲜农产品配送中心作为主营业务的一级指标数量,这里为3,分别为果蔬花卉产品、冷鲜冷冻肉产品、水产品。

步骤3:随机选取k个选取因素,并定义其为初始聚类范围,同时确定簇的数量为k。

步骤4:将uj,1、uj,2、uj,3输入至模糊K-means聚类算法中,以欧式距离为参考,计算k个聚类中心和聚类对象之间的欧氏距离d(xi,xj);并依据d(xi,xj)和各个聚类中心要求,划分不同聚类单元。

步骤5:在根据步骤4划分的聚类单元中计算其样本平均值,并将其定义为聚类单元的新中心。通过不断更新聚类中心,直至聚类中心不再变化或达到最大迭代次数,即可得到最终的聚类结果。

步骤6:采用TOPSIS排序方法[19]对聚类中心进行排序,选取前n个生鲜农产品配送必要性,用于后续生鲜农产品配送路径规划。

1.3 配送路径优化的方法

1.3.1 配送路径规划目标函数 依据1.2中确定生鲜农产品配送中心,以该中心为研究对象,构建配送总成本最小目标函数,设计车辆和无人机组合配送路径。

如果总成本用Z表示,该成本中包含配送固定成本Z1、运输成本Z2、货损总成本Z3(包含运输损耗和卸货损耗),3者的计算公式分别为:

(2)

(3)

(4)

总目标函数的计算公式为:

miniZ=Z1+Z2+Z3

(5)

1.3.2 目标函数求解 以确定的生鲜农产品配送中心为车辆和无人机组合配送的起点,该中心主要用于对m个生鲜农产品进行配送,并且各个产品的质量也存在差异变化。因此,文中在目标函数求解前,按照车辆和无人机的最大配送质量对生鲜农产品进行划分,分别为轻件和重件。前者通过无人机进行配送,后者通过车辆进行配送。并且,在生鲜农产品配送过程中无人机与车辆同时进行,需充分考虑无人机在配送过程中,最大配送半径的耐力限制,并忽略无人机在车辆上充电的时间。

因此,生鲜农产品配送路径规划目标函数求解问题,可看作成一类二级车辆路径规划问题。其中无人机属于二级路径规划,其是建立在一类车辆配送路径的基础上。并且无人机在进行生鲜农产品配送时,主要以空间直行线路完成,可无须考虑地面的交通状态和限制。同时,单位行驶成本较小,远低于车辆的行驶成本。因此,最大程度利用无人机的配送优势,将其和车辆相结合实现生鲜农产品配送。基于此,在进行目标函数求解时,需依据无人机的不同情况完成,分别为3种情况,一是无人机数量充足,二是无人机数量不充足,三是无人机可用数量为0。其求解流程如图2所示。

图2 生鲜农产品配送路径规划目标函数求解流程

(1) 无人机数量充足:在该情况下,通过蚁群算法对车辆配送路径进行求解,在此基础上采用无人机物流车协同配送算法,求解无人机的配送路径,以此获取配送过程中产生的总成本结果。

(2) 无人机数量不充足:在该情况下,需对生鲜农产品的重件和轻件比例的配送进行调整,以此降低无人机的运送压力。该调整需依据蚁群算法和无人机物流车协同配送算法的路径规划求解结果完成,同时按照求解的总成本结果,获取其中总成本最小结果对应比例结果为重件和轻件调整比例。

(3) 无人机可用数量为0:直接定义全部待配送的生鲜农产品快递件均为重件,全部由车辆进行配送,并仅依据蚁群算法求解目标函数,获取总成本最小的结果作为配送路径。

蚁群算法在求解过程中,主要是模拟蚂蚁觅食过程中,通过群体协作完成觅食,实现最优路径的寻找。通过随机方式将m只蚂蚁放入n个配送中心的位置上,该位置的编号用(1,2,…,n)表示,蚂蚁从其当下时刻自身所处位置开始,遍历所有的目的地。其在遍历过程中,对下一个转移的目的地确定,是依据转移规则P完成,则在t时刻下,蚂蚁从地点i转移至j的概率计算公式为:

(6)

式中:τij表示信息素浓度;ηij表示蚂蚁视距函数;α表示信息素权重;β表示距离启发因子;Uk表示蚂蚁在遍历过程中下一步可选地点的集合。

依据公式(6),蚂蚁完成下一个生鲜农产品配送地点的选择,并将选择的地点接入禁忌列表中。对所有的配送地点进行遍历,完成遍历后,进行信息素的更新,以此实现1次迭代操作,并获取当前最优蚂蚁,定义其为最优解。在此基础上,对当前最优配送结果进行更新。重复该过程中,当迭代次数达到设定条件后,输出最终的全局最优结果,即获取无人机与车辆结合配送路径规划结果。

1.3.3 无人机配送空间安全系数约束 依据上述小节完成生鲜农产品车辆与无人机组合配送路径规划后,无人机在配送过程中,需充分考虑天气情况,保证无人机在大雨、大风等较为恶劣天气下配送的安全性,避免无人机坠落和损坏。因此,文中在蚂蚁转移规则中引入安全启发函数,对转移规则进行优化,优化后的转移规则公式为:

(7)

式中:ξij(t)表示安全启发函数;ω表示安全启发因子,如果该因子的值较小,则表示无人机在配送时面临的安全风险越小,反之,则越大。

引入ξij(t)后,则可对无人机配送路径安全进行评价,如果蚂蚁的遍历路径共存在φ个栅格,则第i个栅格的安全系数用ξi表示,则无人机配送路径安全评价指标的计算公式为:

(8)

无人机配送路径规划前,先设定V值,在路径规划时,寻找路径中安全值大于设定的值的配送路径,只对该路径上的信息素进行更新,以此保证无人机配送路径的安全。

2 效果测试

为验证本研究方法对于生鲜农产品车辆和无人机组合配送路径规划效果,以某生鲜农产品电商服务平台及其覆盖范围为测试对象进行对比分析。

2.1 测试准备

将本研究方法用于某生鲜农产品电商服务平台中,该平台的用户人数接近30万人,日均访问量接近13万,其覆盖的配送范围内已经存在480个社区配送站点。该平台为进一步扩大自身服务覆盖范围,提升自身竞争能力以及经济效益,构建异地配送中心,覆盖22个二、三线城市。

目前,在异地配送中心进行产品配送时,配送成本相对较高,达不到预期的经济效益。本研究根据1.2从该平台覆盖的10个不同类别的配送中心中选取主营生鲜配送的中心,生成配送中心及范围示意图(图3)。

图3 配送中心及范围示意图

由图3可知,本研究从该区域中确定了3个主营生鲜配送的中心,分别配备配送车辆数量为47、33和22辆,并且为3个配送中心分别部署20架、12架和7架无人机,以此为基础进行路径规划试验。

2.2 测试指标

评估聚类质量的准则有2种:内部质量评价准则(internal quality measures)和外部质量评价准则(external quality measures)。内部质量评价准则是通过计算簇内的平均相似度、簇间的平均相似度或整体相似度评价聚类效果,适用于K-means聚类算法的常用指标包括Dunn指标、CH指标、DB指标[20]。DB指数表示集群之间的平均“相似度”,相似度是比较集群之间的距离和集群本身的大小的度量,它是关于同一簇中样本的紧密程度与不同簇之间样本分散程度的一个函数[21]。

2.2.1 CH指标 CH指标经过计算类中各点与类中心的距离平方和来度量类内的紧密度,计算各种中心点与数据集中心点距离平方和来度量数据集的分离度,CH指标由分离度与紧密度的比值获得。CH值越大,代表着类自身越紧密,类与类之间越分散,聚类效果越好。缺点是凸得簇的CH指数通常高于其他类型的簇。

(9)

式中:u表示聚类数量;k表示当前的类别数;Tu(Si)、Tu(Sj)分别表示类间、类内离差矩阵的迹。

2.2.2 Dunn指标 Dunn指数指的是一种通过计算2个簇之间的最短距离除以簇内的最大距离来评估聚类效果的指标,DVI越大代表类间距越大,反之则类间距越小。缺点:对离散点的聚类测评很高、对环状分布测评效果差。

(10)

2.2.3DB指标DB指标是任意两类别的类内距离平均距离之和除以两聚类中心距离,并求最大值。DB指标的取值范围在[0,1]之间,其值越大表示聚类效果越佳,则位置确定中心效果越佳,反之则越差。该指标的计算式为:

(11)

式中:u表示聚类数量;s(di)、s(dj)分别表示对应不同样本类别和聚类中心之间的平均距离;hij表示两个样本i和j之间的距离。

为验证本研究方法对于生鲜农产品配送中心确定效果,本研究采用DB指数作为评价指标,DB指数的计算只需要知道数据集的数量和特征,能够更快速准确地衡量位置确定过程中的聚类效果,是更符合本研究所需的评价指标。

2.3 结果分析

依据式(11)得到的评价指标与影响确定效果的指标范围,在应用本研究方法的基础上,同时引入文献[7]和文献[8]这两种方法选取生鲜农产品的配送中心。文献[7]针对产品的生鲜价值构建配送物流优化模型的路径优化方法,简称为“衡量生鲜农产品价值方法”;文献[8]构建生鲜农产品鲜度最大化目标函数,从而改进遗传算法的路径优化方法,简称为“生鲜农产品新鲜度最大化方法”。

按照本研究方法和以上2个方法分别进行测试,将DB指数设置聚类样本中的测试数据。其数值越接近于1,表示聚类效果越好,反之越差。基于此对3种方法的聚类效果进行对比,对比结果见表1。

表1 聚类效果测试结果Table 1 Clustering effect test results

依据表1测试结果可知,经本研究方法处理的聚类样本,随着聚类样本数量的逐渐增加,DB指数的结果也存在一定的波动变化,但DB指数大部分均高于0.8,更接近1。而NSGA Ⅱ算法方法的DB指数波动范围较小,DB指数值均低于0.15,极大程度接近0。GT-AS算法的DB指数波动幅度较大,不能趋于稳定。因此,本研究方法具有较好的聚类效果,能够更好地完成配送中心的确定。

根据在图3的测试区域中确定的主营生鲜配送的中心与为其配备的车辆数及无人机数量,随机选择1个配送中心及部署的车辆和无人机,进行配送路径规划,获取路径规划结果,以此验证本文方法对于车辆和无人机组合配送路径规划效果。验证结果见图4。

图4 车辆和无人机组合配送路径规划结果

由图4可知,本研究方法应用后,能够有效完成车辆和无人机组合配送路径规划,并且通过无人机的配合,可降低车辆的行驶路程;与此同时,无人机可与车辆同时进行配送,能够提升生鲜农产品的配送效率。

为进一步验证本研究方法对于无人机配送安全的优化效果,根据在图4测试区域中的优化前与优化后的车辆、无人配送路径,选取规划前和规划后的2条无人机配送路径。在不同天气情况下,其配送路径的规划结果,可体现无人机配送安全优化效果。本研究中结果仅随机呈现大风天气下的路径规划效果,如图5所示。

图5 无人机配送安全优化效果

由图5可知,本研究方法应用后,可有效优化无人机的配送路径,优化后的路径尽量避免无人机过多接近配送范围内存在的建筑物,以此降低无人机发生碰撞或者损坏;并且,优化的配送路径长度的变化幅度不大,在保证配送安全的情况下,不会导致配送成本的明显增加。

根据图4产生的优化配送路径,设置生鲜农产品重件和轻件在配送时产生的成本,获取在不同的总配送生鲜农产品快件数量下,优化前与优化后的配送成本。以此对比本研究方法应用前后,重件和轻件的配送成本结果见表2。

表2 配送成本测试结果

依据表2测试结果可知,本研究方法应用前重件和轻件的配送成本明显更高于本研究方法应用后的成本,本研究方法应用后,能够显著降低生鲜农产品的配送总体成本,应用效果满足应用需求。

3 结论与讨论

为保证生鲜农产品配送的时效性,避免产品配送效率较低,导致产品腐坏。本研究提出基于蚁群算法的生鲜农产品车辆与无人机组合配送路径规划方法,该方法利用无人机无须受到交通约束和限制的优势,将其和车辆结合进行配送,并利用蚁群算法的鲁棒性和并行性优势,对不同无人机数量情况下的配送路径进行优化求解,并创新性地引入安全启发函数,保障无人机生鲜农产品配送安全性。本研究设计了3个对照试验,分别对本研究方法,文献[7]衡量生鲜农产品价值方法和文献[8]生鲜农产品新鲜度最大化方法进行综合对比分析,不仅利用K-means聚类效果找出合适的配送中心位置,还验证了模型与算法在降低运输成本上的效果。结果显示,本研究所提出的数学模型使生鲜农产品物流企业在城市配送货物的过程中,能够合理选取配送中心,保证配送中心的覆盖程度。此外,与其他文献相比,本研究还验证了在货物质量划分为轻件和重件时,本研究方法应用后可以更高质量地完成配送路径规划,显著降低生鲜农产品的配送总成本,提升配送效率。

基于本研究,今后还有许多需要扩展的方面。比如,对于车辆行驶速度,本研究仅是对其进行了按时间段划分取平均值的处理,下一步可以考虑结合GIS等技术,实现实时路况监控,对于早晚高峰和其他特殊时间进行系统分析,使问题更贴合实际。另外,本研究考虑无人机的安全性,引入安全系数时,无人机的安全使用情况不仅与极端天气,建筑高度有关,实际上还受电耗续航时长的影响,以后的研究可以更全面地考虑无人机因为续航问题影响生鲜农产品配送的情况。