姚竟发，刘静，滕桂法，张璠，范晓飞

(1. 河北农业大学机电工程学院，河北保定，071001； 2. 河北农业大数据重点实验室，河北保定，071001； 3. 保定理工学院基础课教学部，河北保定，071001； 4. 河北农业大学信息科学与技术学院，河北保定，071001)

0 引言

随着我国农业机械化的快速发展，农业领域的“互联网+农机”智慧农业机械应运而生，如今农机作业基本上仍然是经验作业，如何提升农机精准作业和降低作业成本是首要任务。农机大数据中心实时定位农机作业位置、监测农机运行状态及农田状态，并通过客户端实时调控农机作业。机群协同作业时，一般按照优化算法预先规划好的路径进行作业，而在实际作业过程中，由于意外的机群运行状态或农田环境，经常偏离原作业路径，如果仍按原路径进行作业，不仅作业效率低，而且作业成本比较高。如何有效动态优化机群协同作业路径，节省作业成本，是目前亟待解决的问题。

为降低机群作业成本、提高作业效率，国内外学者对单机和多机作业路径优化问题展开研究。Hunt[1]早在2001年就提出农机非作业行驶是影响农机作业效率的主要因素。随后Oksanen等[2]、Hameed等[3]、孟志军等[4]研究了各种农田路径生成方法的效率，Bochtis等[5]将VRP(Vehicle Routing Problem)问题模型引入农机作业路径优化中，对单农机作业路径优化进行了深入研究。Bochtis等[6]提出一种关于农田作业的理论模型，为后续研究奠定了理论基础。由于单农机体积较大，虽然经过路径优化，能提高作业效率，但是容易压实土壤[7-8]，不利于作物生长，同时单农机出现故障后影响作业进度。

提高作业效率的另一个途径是采用机群协同作业[9]。Seyyedhasani等[10]以总作业时间和作业时长为综合最短为优化目标，使用禁忌算法TS(Tabu Search)对3台农机进行作业路径优化，有效提高了机群作业效率，但是Seyyedhasani并没有对机群作业路径冲突展开研究。目前对机群协同作业冲突方面的研究较少，Li等[11]设计了一种基于冲突概率的AVG(Automated Guided Vehicle)动态调整方法，张素云等[12]针对自动集装箱码头水平运输中可能出现的自动导引车路径冲突问题，提出了一种多参数控制策略和改进的速度控制策略，有效地改进了AVG路径冲突。以上路径冲突研究均为自动化物流领域，没有针对农业领域机群作业路径冲突展开研究。机群协同作业过程中，意外的农机运行状态或农田环境会导致原作业出现偏差，Seyyedhasani等[13]提出在农机数量发生改变、农机作业速率发生改变以及农田面积发生改变三种情况下，将机群协同作业路径动态优化问题转换D-MDVRP(Dynamic Vehicle Routing Problem with Multiple Depots)问题，动态调整机群作业路径，始终确保作业路径最优。但以上研究没有考虑机群作业冲突问题[14-18]。

本文以总作业时间和作业时长综合最短为优化目标，提出一种机群协同作业路径动态优化DOFOP(Dynamic Optimization of Fleet Operation Path)算法，在机群作业过程中，实时监测并动态调整机群作业路径，在作业路径无冲突前提下，确保机群协同作业路径的合理性。

1 模型构建

1.1 问题分析

作业路径动态调整需要实时监测机群作业状态，为机群协同作业提供科学、合理的作业路径。当机群运行状态或农田环境发生改变时，农机大数据中心利用物联网、GPS/北斗定位等信息技术，实时采集机群作业位置、行驶速率、作业时间、农田状态，使用相应的作业路径动态优化算法，重新为机群分配合理作业路径，如图1所示。

图1 机群协同作业系统结构

作业过程中，机群作业状态可能随时发生改变，主要包括：农机运行故障，导致机群数量发生改变；驾驶员熟练程度不同、作物长势差异等，导致农机作业速率发生改变；农田某区域由于积水或作物长势等原因，原农田部分区域不能作业，作业面积发生改变。

当作业状态发生改变时，机群位于农田任意位置，需要将机群当前位置作为动态出发点，重新优化作业路径。为方便操作和避免增加处理节点，当机群数量减少时，视为该行未作业，重新优化路径时包括该作业行；其他作业状态发生改变时，机群总要将该行作业完(不考虑行间转向)，因此将动态出发点移到该作业行作业结束地头；如果作业状态发生改变时，农机正处于地头，则动态出发点移至即将进入作业的行地头，因此，作业路径重新优化时，需要考虑当前作业行剩余作业时间。为了区分农田地头，如图2所示，将机群开始作业的地头称为A地头，另一端地头称为B地头。机群作业结束，可能从A地头返回，也可能从B地头返回。

图2 作业状态发生改变时动态出发点调整结果

本文以作业时长和总作业时间综合最短为优化目标，动态优化机群作业路径，同时确保作业无冲突，机群作业结束回到原出发点，该类问题可归为D-MDVRP问题[19-26]。

1.2 模型参数

机群作业路径动态优化与天气、农机新旧程度、机手操作技术、农作物长势等有很大关系，同时与农机大数据中心软件、硬件等环境也有很大关系，是一个复杂优化问题。本文假设机群型号、新旧程度、机手操作技术相同，作业过程中不考虑中途返回、机手休息、天气等因素，机群从仓库出发、作业完成后返回仓库，农机发生故障后不考虑维修、返回、重新作业等情况，机群均在地头转弯，不考虑田间转弯情况。

1.2.1 问题形式化描述

根据对机群作业路径动态优化问题分析，形式化描述如下。

1) 设At={fw,fl,Ntf}表示机群作业t分钟后，作业状态发生改变时，剩余的未作业农田。fw表示农田宽度，fl表示农田长度，集合Ntf={r1,r2,…,r|Ntf|}表示联合收割机作业t分钟后，作业状态发生改变时的剩余作业行。

2) 设Vt={Nm,rmin,w,htsi,ztsij,etsij,vf,vw,vt,bts}表示作业t分钟后的联合收割机。Nm表示联合收割机数量；rmin表示联合收割机最小转弯半径；w为联合收割机作业幅宽；htsi、ztsij、etsij分别为作业t分钟后，第s台联合收割机按照重新优化的路径到达第i行地头的时间、从第i行到第j行的转弯时间、从第i行结束进入第j行的时间；vf、vw、vt分别为联合收割机空行驶速度、作业速度和转弯速度；bts表示作业t分钟后，重新优化路径时第s台联合收割机的动态出发点，当联合收割机位于农田内，bts表示如下

(1)

当联合收割机位于地头时，bts表示如下

(2)

3)ρts表示作业t分钟后，第s台联合收割机从第i行当前位置到第i行地头作业结束的时间，表示如下

(3)

1.2.2 模型构建

作业t分钟后，多联合收割机作业路径动态优化问题由有向图Gt={Nt,Et}表示，Nt表示作业t分钟后的相关节点，包括三类节点，农田作业行节点Ntf、农机动态出发点Ntv(包括新增联合收割机)、结束点Nd；Et为连接两节点的边集合。

通过上述分析，节点间包括三类时间：联合收割机行内作业时间和行间转弯时间、从动态出发点到达待作业行地头时间、作业结束返回仓库时间。

作业t分钟后，机群总作业时间

(4)

式中：i、j——农田作业行；

cij——第i行的作业时间；

xij——联合收割机从第i行到第j行的转弯时间。如果存在从第i行到第j行的作业路径，则xij为1，否则为0。

作业t分钟后，作业时长

(5)

作业t分钟后，本文优化目标Tc表示如下

(6)

式中：z——权重变量。

2 机群协同作业路径动态优化算法

机群按照原路径进行作业，作业过程中，农机大数据中心实时对作业状态进行监测。在t时刻，监测到机群作业状态改变，获取剩余作业行及每台农机当前作业行剩余作业时间ρts。DOFOP算法以机群当前作业行节点为动态出发点，以剩余作业行为染色体编码，根据作业时间矩阵，重新为机群分配作业路径，如果计算的路径中没有作业冲突，则当前作业路径即为最优作业路径，否则重新计算新作业路径。

2.1 初始解优化策略

机群协同作业路径动态优化问题属于VRP问题，随作业行数增加，算法从随机初始解中寻优难度呈指数增长。DOFOP算法引入改良圈算法，对初始解进行改良优化。改良圈算法原理为：根据Gt={Nt,Et}，先将t时刻DOFOP算法随机初始化的作业路径Rt=〈r0,r1,r2,…,ri,rj,rj-1,rj-2,…,ri+1,rj+1,rj+2,r|Ntf|,r0〉作为Hamildon圈，采用最邻近算法，对Rt进行遍历并修改Rt，得到总作业时间更小的另一个Hamildon圈。但是最终最邻近算法求解的Hamildon圈并不是最优解。

2.2 作业路径冲突检测

作业t分钟时，设第s台和第s′收割机分别位于第i行和第i′行，当前行剩余作业时间分别为ρts和ρts′，作业完成当前行后位于同一地头，并分别转向第j行和第j′行进行作业，转弯时间窗分别为[etsi+(ρtsi-t),etsi+ztsij+(ρtsi-t)]和[ets′i′+(ρts′i′-t),ets′i′+tts′i′j′+(ρts′i′-t)]，如果转弯路径、转弯时间窗同时出现重叠，则第s台和第s′台联合收割机作业路径冲突。

2.3 作业状态监测

农机作业状态是被时刻监测的，当农机出现故障时，监控设备立即感知并上传状态信息。虽然作业状态是被时刻感知的，但是为了农机便于操作，本文算法要求农机在地头调整作业路径，具有一定的滞后性。

2.4 行作业剩余时间的计算

由于当农机作业状态改变时，需要计算从状态改变到地头作业路径的调整时间，本文称其为行作业剩余时间，在重新优化作业路径时，需要将该时间考虑在内。行作业剩余时间的计算方式为，当农机作业状态改变时，监控设备记录作业状态改变时间，行作业时间减去该行已作业时间即为行作业剩余时间。

2.5 作业结束的判断

作业结束应该以最后一台农机作业结束为依据，因此，作业完成时间应为该农机的作业时间，同样，该判断也是监控设备时刻进行监控的。

DOFOP算法具体流程如图3所示。

图3 算法流程图

3 机群协同作业试验

3.1 试验条件

试验选用4台约翰迪尔W210联合收割机，其作业幅宽w=4 m，最小转弯半径rmin=3.8 m，空行驶速度vf=5.47 m/s，作业速度vw=2.78 m/s，转弯速度vt=2.22 m/s。

试验选用的农田位于内蒙古自治区呼伦贝尔市陈巴尔虎旗(49°28′40.0″N 120°00′21.2″E，49°28′53.6″N 120°01′00.6″E)，农田地头长278.05 m，宽852 m，面积约为23.69 hm2，机群仓库距离农田894.29 m，如图4所示。

图4 作业农田

DOFOP算法选用的种群规模为500、交叉概率为0.9、变异系数为0.1、迭代次数为500。由于作物收获时，机手和农户更关注农田的作业时长，将式(6)优化目标中的权重变量z设定为0.6。

3.1.1 改变机群数量

设机群分别作业26 min、50 min、70 min时，被监测到第2台联合收割机M2发生故障，作业状态发生改变，机群数量由4台变为3台，需要为剩余3台联合收割机重新优化作业路径。

1) 作业26 min时，机群作业情况统计如表1所示。

表1 26 min后M2作业发生故障时作业统计Tab. 1 Operation statistics in case of M2 failure after 26 minutes

2) 作业50 min时，机群作业情况统计如表2所示。

表2 50 min后M2作业发生故障时作业统计Tab. 2 Operation statistics in case of M2 failure after 50 minutes

3) 作业70 min时，机群作业情况统计如表3所示。

表3 70 min后M2作业发生故障时作业统计Tab. 3 Operation statistics in case of M2 failure after 70 minutes

3.1.2 改变机群作业速率

设机群分别作业26 min、50 min、70 min时，监测到第2台联合收割机M2作业速率发生改变，作业进度比原计划提前20%。

1) 作业26min时，机群作业情况统计如表4所示。

表4 26 min后M2速率发生改变时作业统计Tab. 4 Operation statistics when M2 rate changed after 26 minutes

2) 作业50 min时，机群作业情况统计如表5所示。

表5 50 min后M2速率发生改变时作业统计Tab. 5 Operation statistics when M2 rate changed after 50 minutes

3) 作业70 min时，机群作业情况统计如表6所示。

表6 70 min后M2速率发生改变时作业统计Tab. 6 Operation statistics when M2 rate changed after 70 minutes

3.1.3 改变农田作业面积

设机群作业过程中，被监测到农田第79行到第90行区域(共12行，约1.33 hm2)不能作业。按照原作业路径，当作业到第19.78 min时，M4作业完成第90行时首先到达该区域，作业状态发生改变，需要为机群重新优化作业路径，此时机群作业统计如表7所示。

表7 19.78 min后农田作业面积减少时的作业统计Tab. 7 Operation statistics of farmland operation area reduction after 19.78 minutes

3.2 评价指标

当机群作业状态发生改变后，DOFOP算法重新优化作业路径，为机群分配合理作业路径。评价机群作业性能的指标主要为有效农田作业能力(Effective Field Capacity，EFC)、农田效率(Field Efficiency，FE)两个指标。本文通过AEFC、FE、总作业时间和作业时长4个指标来评价机群协同作业路径动态优化结果。

有效农田作业能力为评价单位时间内机群作业的农田面积，与机群作业速度、非作业时间有很大的关系，计算方式如式(7)所示。

(7)

式中：Af——农田面积。

根据式(7)，在农田面积一定的情况下，提高EFC需要减少作业时长clast，即最后完成作业的机群所需作业时间。AEFC(Average Effective Field Capacity)用来表示机群的平均有效农田作业能力，计算方式如式(8)所示。

(8)

农田效率为机群理论总作业时间和实际总作业时间的比值，主要用来衡量算法对机群非作业时间的优化程度，计算方式如式(9)所示。

(9)

式中：ctheoratial——机群理论总作业时间；

call——实际总作业时间。

ctheoratial为联合收割机在农田内的作业时间，面积一定的情况下，理论总作业时间是固定的，而实际总作业时间除了ctheoratial外，还包括机群地头转弯所需的非作业时间，计算方式如式(10)所示。

(10)

如要提高FE，需尽可能缩短call，即减少地头转弯所需时间。

4 结果与分析

4.1 改变机群数量

机群作业过程中，由于第2台联合收割机M2发生故障，为与重新优化后的作业路径进行对比，本文分别在机群作业26 min、50 min和70 min后，采用三台联合收割机对剩余作业路径进行并排作业。并排作业时，为避免冲突，机群按照作业顺序依次延后30 s。机群作业状态发生改变后，重新优化后的机群作业与机群并排作业对比结果如表8所示。重新优化后的作业结果与机群并排作业结果对比提高率Rindex(表8括号中百分比)。提高率计算方式如式(11)所示。

(11)

式中：Iorigin——优化前作业指标；

Ioptimize——优化后作业指标。

表8 农机发生故障后的优化结果Tab. 8 Dynamic optimization results of operation path for agricultural machinery fleet after failure

分析表8可知，重新优化的作业路径明显优于并排作业。联合收割机M2在作业26 min、50 min、70 min后发生故障，DOFOP算法重新优化后的作业时长比并排作业分别降低了2.31%、1.37%、3.88%，平均降低了2.52%；总作业时间在机群作业26 min时优化最大，比并排作业降低了3.05%，平均降低了2.52%；如果作业面积相同，EFC、AEFC与作业时长clast相关，因此，算法对机群作业70 min后的优化最大，比并排作业降低了3.81%，平均提高了2.63%；随着作业时间的增加，由FE与总作业时间call相关，同样随作业时间增加，与并排作业的总作业时间相比，优化提高率呈递减趋势，平均提高2.59%。

4.2 改变机群作业速率

机群作业过程中，被监测到其中1台联合收割机作业速率变快，如果仍然按原路径作业，该联合收割机会提前完成作业而处于闲置状态，而其它联合收割机仍在进行作业。作业时长取决于最后完成作业的联合收割机所需时间，DOFOP算法为机群分配的作业路径较合理，因此，其中1台联合收割机作业速率发生改变对作业时长影响不大，但是总作业时间会明显减少。DOFOP重新优化后的作业时长、总作业时间与原作业对比结果如表9所示。

表9 农机作业速率改变后的优化结果Tab. 9 Optimization results of agricultural machinery operation after rate change

分析表9可知，机群在作业26 min、50 min、70 min 后，DOFOP算法重新优化后的作业时长与原作业时长相比，分别降低了2.45%、6.78%、12.42%，平均降低了7.22%；由于DOFOP算法改变了机群原作业路径，增加了地头转弯时间，因此优化后的作业路径与原作业相比，总作业时间优化不大，分别降低了1.95%、1.74%和4.49%，平均降低了2.73%。EFC、AEFC与作业时长有关，与原作业相比，优化后的AEFC也较明显提高，平均提高7.99%；FE与总作业时间相关，与原作业相比，FE有小幅提高，平均提高2.82%。

4.3 改变农田面积

农田作业面积改变后，如果不重新优化作业路径，联合收割机M1作业行数减少6行，联合收割机M4作业行数减少6行，因此M1与M4作业时间明显缩短，而其联合收割机作业时间不变，造成M1与M4提前完成作业而闲置。DOFOP算法重新优化后作业路径与原作业对比结果如表10所示。

从表10可知，农田面积改变后，DOFOP重新优化剩余作业路径，机群作业时长比原作业降低了6.26%，相应的AEFC提高了6.48%，改善了因M1与M4提前完成作业而闲置问题；与作业速率改变情况类似，机群按照重新优化的作业路径作业，额外增加了地头转弯时间，与原作业的总作业时间相比，总作业时间降低了0.1%，相应的FE提高了0.1%。

表10 农田面积改变后的优化结果Tab. 10 Optimization results after the change of farmland area

5 结论

以最小化作业时长与总作业时间为优化目标，在机群或农田作业状态发生改变时，使用DOFOP为机群动态优化作业路径，引入改良圈算法，对初始解进行了改良优化，提高了寻优效率，当有农机出现故障时，监控设备立即感知并上传状态信息，算法及时调整机群作业路径，同时算法能有效避免机群间的作业路径冲突，使用DOFOP算法优化的机群作业路径结论如下。

1) 当作业过程中有联合收割机发生故障时，DOFOP算法重新优化剩余作业路径，优化后的作业时长、总作业时间比并排作业平均降低了2.52%、2.52%，AEFC、FE比并排作业平均提高了2.63%、2.59%。

2) 当作业过程中有联合收割机速率发生改变时，DOFOP算法重新优化剩余作业路径，优化后的作业时长、总作业时间比原作业平均降低了7.22%、2.73%，AEFC、FE比原作业平均提高了7.99%、2.82%。

3) 当作业过程中农田作业面积发生改变时，DOFOP算法重新优化剩余作业路径，优化后的作业时长、总作业时间比原作业平均降低了6.26%、0.1%，AEFC、FE比原作业平均提高了6.48%、0.1%。