基于改进型果蝇算法的联运物流揽件调度仿真

黄继梅，陈进强

(1. 南昌航空大学科技学院，江西 九江 332020；2. 南昌大学共青学院，江西 九江 332020)

1 引言

随着各类网络应用的普及，电子商务已经成为促进经济增长的亮点。在此背景下，物流行业发展迅速，联运物流作为运输的高级方式，综合了各类交通工具的优势，并将其有机组合，确保成本最低的同时提高运输效率。在联运物流模式下，揽件作为首个环节，一定程度上决定货物整体运输效率。现阶段，大多数快递揽收利用固定的分区揽收形式，每个快递员负责一个区域，且互不支援。若某揽件区域任务数量分配不均，会导致揽件员业务能力与业务量不匹配。因此揽件速度慢、距离长等问题就会越来越突出，尤其是在大型电商活动节期间，无法满足快递数量急剧增长的需求。随着电子商务的不断发展，客户特征体现为小批量、多批次，在顾客需求复杂多变情况下，如何实现高效、灵活揽收是保证高效物流的关键。

为解决以上问题，应毅[1]等人将地理信息系统技术与K近邻算法(K-Nearest Neighbors，KNN)相结合，建立“最后一公里”配送的智能信息系统，在此系统中，利用加权KNN方法完成快递员的实时揽件调度。马军平[2]等人提出基于服务时长与可选择性的揽收车辆调度方法。在正负半轴分别提出Replan与ReOPT策略，综合分析揽件时长等因素制定具体调度策略。

但以上方法在求解过程中无法实现快速收敛，所得结果也容易陷入局部最优[3]。为解决这一问题，本文提出基于改进型果蝇算法的联运物流揽件调度方法。通过改进果蝇算法对物流揽件调度模型进行求解，获取最优揽件路线。果蝇算法是模仿果蝇寻找食物的行为完成设计的，应用过程简单，搜索效率高，且参数能够自由调节。通过不断迭代操作[4]，获得问题最优解。为进一步提高寻优精度，本文对该算法进行改进，对种群规模、初始位置与迭代步长的合理设置，提高搜索能力，避免陷入局部最优。

2 确立联运物流揽件约束条件

揽件调度问题与多约束条件具有紧密关联性。但约束条件通常较为复杂，这对调度模型的构建产生一定障碍，本文将最大程度给出和此问题具有较强相关性的约束条件。

车辆约束[5]：任意一揽件车辆在重量与体积方面均有固定限制；每辆车都会受到揽件时间限制；车辆均有维修期等闲置时期；不同车辆类型满足不同货物需求；

顾客约束：顾客的揽件需求包括数量与种类；顾客对于揽件具有时间要求，也是提高顾客满意度的关键，是互利的，必须最大程度满足；分析顾客的优先级，便于企业发展，增强顾客信任度；

2.1 单个揽件中心

在建立约束模型之前，给出如下假设：

1)揽件中心全部车辆类型相同，且载重量相同；

2)计算揽件中心和用户节点、两个用户节点之间的距离。

若用户i与j的坐标分别表示为(Xi，Yi)与(Xj，Yj)，则两点之间的距离计算公式为

(1)

式中，u为距离系数，也是两个用户具有的真实距离和理想距离之间的系数。

决策变量[6]表示为

(2)

式中，K代表揽件车数量，i，j=0，1，2，3，…，N，k=0，1，2，3，…，K-1。

(3)

揽件系统的目标体系分为：根据用户规定的时间准时完成揽件任务，且减少车辆等待时长；合理规划揽件路线，降低总成本，保证车辆指派数量最少。

上述不同目标之间互相关联影响，构建目标体系[7]，得出揽件中心的目标函数：

最短揽件时长

(4)

式中，ei表示客户i给出的最早揽件时间，ti为车辆在用户i处起始揽件时间。

最少派出车辆

B=Min∑yk

(5)

最短揽件距离：

(6)

结合目标重要程度，设计约束条件优先级P1

P1A+P2B+P3C

(7)

确立单揽件中心与多顾客情况下的约束模型

(8)

(9)

(10)

式中，N为用户总数量，h描述揽件中心。

2.2 多个揽件中心

若该地区由多个揽件中心负责揽件，则将其转换为单揽件中心问题处理，从而确定揽件中心的服务任务。假设H表示揽件中心数量，Vh表示第h个揽件中心h=0，1，2，…，H-1，各中心具备的车辆数量表示为a0，a1，a2，…，aH-1。则目标函数如下

(11)

式中，Ah、Bh与Ch分别代表第h个揽件中心完成此次任务所有的最短时间、最少车辆以及最短距离。

与单揽件中心利用的决策变量相同，针对任意一个揽件中心h∈[0，H-1]的路径约束模型为

(12)

(13)

(14)

3 基于改进型果蝇算法的联运物流揽件调度

3.1 调度模型构建

假设各揽件中心与用户位置一致，某车辆从中心出发到用户所在处执行揽件任务后再回到揽件中心，如何合理安全调度路线，并将揽件成本降到最低，是调度模型的关键应用要求。在上述约束条件作用下，将揽件距离最短设定为最终目标，构建揽件调度模型，再通过果蝇算法对该模型求解，获取最优调度路线。

假设存在m+1个揽件点，xij代表取值为0或1的决策变量，若揽件车辆从客户i处能直接到达客户j处，此时xij=1，反之xij=0。若i与j之间不能实现直接通行，则dij=∞。

因此，车辆从揽收中心出发到某一客户处的调度策略描述为

X′=(xij)(m+1)×(m+1)

(15)

因此，该揽件调度策略必须符合

(16)

但是，由于车辆必须经过所有揽收点后再返回揽收中心，故有

(17)

(18)

综上所述，结合xii=0，0≤i≤m得出

(20)

(21)

揽件调度模型为

(22)

3.2 基于果蝇算法的揽件调度模型求解

传统的果蝇算法作为寻优方法同样具有一定缺陷。当利用其协作与共享机制求解最优算法时，一般具备较强的全局搜索能力，但是揽件调度模型属于较为复杂的模型，若直接利用此算法会导致后期搜索效率下降。因此必须从下述几方面进行改进。

1)种群规模

果蝇种群大小会直接影响其搜索能力，规模越大，寻找食物的时间也越短。此外种群大小也影响寻优质量，当种群规模大时，果蝇行进速度加快，收敛精度[8]提高。

但是在实际应用过程中，并非种群数量越大越好，当数量过大时，会损耗较多的系统内容，CPU的运行时间也更长。必须结合揽件调度模型的实际特点，经过大量实验后，给出种群的合理数量，满足搜索实时性要求。

2)果蝇初始位置

初始位置越合理，算法收敛速度越快，表明在较短时间内可以获取最优值。而初始位置与理想位置距离越大，算法效率也低，易出现局部最小情况。传统的果蝇算法中初始位置的确定是通过随机搜索方式完成，为改进这一缺陷，本文缩短了初始位置与最优值的距离[9]，以优化算法性能。

3)步进值

步进值，又称作寻优步长，是指果蝇利用其嗅觉优势将搜索步长为单位，完成搜索与寻优。若果蝇数量确定，步长越大，寻优范围也越广，改善全局寻优性能，但局部搜索性能会降低；反之当步长过小，算法的全局寻优能力会下降。

本文利用自适应搜索寻优步长[10]的方式，使全局与局部搜索能力达到平衡[11]，改善算法的整体性能。详细做法如下：

递减搜索寻优步长的表达式如下

(23)

式中，L0代表原始步长，maxgen为最大迭代次数，g表示现阶段迭代次数。

则计算自适应步长的公式如下

(24)

4)果蝇味道浓度

在传统果蝇算法中，种群在较大范围内任意分布，因此个体与原点之间的距离Disti′值也会越大，结合下述味道浓度表达式能够得出，此时，味道浓度判定值Si′较小。因Si′值与0接近，则果蝇判断函数Smelli′=function(Si′)的数值变化范围过小，造成算法早熟。

Si′=1/Disti′

(25)

为确保算法有效性，避免出现早熟问题[12]，本文利用有效因子α与避免局部最优因子β对传统算法这一缺陷进行改进

Si′=1/(Disti′+α)+β

(26)

式中，α>0，而β则分为下述两种情况

(27)

经过上述改进后，利用改进型果蝇算法求解联运物流揽件调度模型的全部过程如下：

第二步：嗅觉搜索，将原始迭代数设置为g=0，同时定义迭代时果蝇在寻找食物过程中飞行方向与寻优步长：

(28)

第三步：初步计算，因不能掌握食物的详细方位，需得出个体与原点之间的距离Disti′，进而获取味道浓度值Si′；

第四步：将浓度判断值代入式(29)的判断函数中，得出现阶段所有果蝇的气味浓度smelli′：

smelli′=function(Si′)

(29)

第五步：按照浓度值大小，确定种群中最优个体

[bestSmell，bestindex]=min/max(smelli)

(30)

第六步：视觉定位，对最优浓度值与最佳个体坐标进行记录。此时，果蝇群体将通过视觉定位飞向最佳个体方位

(31)

第七步：迭代寻优，判定是否满足停止条件g=maxgen。若g

4 仿真与结果分析

为证明所提方法的优越性，在仿真环境为Windows7/CPU3.8GHz/VC++下与文献[1]方法、文献[2]方法进行对比实验。为降低随机因素对上述算法性能测试产生影响，将最大迭代次数设置为500。首先在揽件点数量不断增长情况下，结合各方法目标函数获得的最大值、最小值与均值对均方差进行计算，结果如表1所示。

表1 不同方法的均方差计算结果表

由表1可知，在揽件点数量较小时，三种算法的均方差没有出现明显区别。但随着揽件点数的增长，文献[1]方法与文献[2]方法的均方差大幅度变大，而所提方法的均方差较为稳定，表明该方法搜索过程较为稳定。这是因为本文通过对果蝇算法的改进，设置合理的迭代步长，使搜索过程更加平稳，避免陷入局部最优。

为进一步验证所提方法的应用优势，将三种方法进行实践，实验的揽件地址与数量完全相同，利用不同方法给出的最优策略进行揽件调度，不同方法调度路线分别如图1～图3所示，图中星型表示顾客揽件位置。

图1 本文方法揽件调度路线

图2 文献[1]方法揽件调度路线

图3 文献[2]方法揽件调度路线

由图1～图3提供的路线图可知，传统方法在满足所有揽件需求时，出现路线重复问题，工作效率偏低，且顾客等待时间较长，降低了满意度。相比之下，本文方法能够规划出更加合理的调度路线，验证了所提方法理想的应用性能。

5 结论

为提高物流揽件工作效率，本文利用改进型果蝇算法实现联运物流揽件调度。仿真结果证明，该方法搜索效果稳定，能够获得合理的调度路线，节省了人力资源与运输成本，适用于业务量较多地区，为今后电商的自动化调度提供可靠依据。但是在研究揽收调度策略的同时，也应不断改进揽件工作模式，提高业务能力，使其能够支撑电商行业的快速发展。