基于小麦收割机作业路线行走方向的调度优化研究*

南风，曹光乔，李亦白，陈聪，刘东

(农业农村部南京农业机械化研究所，南京市，210014)

0 引言

农机调度已经在农业领域中得到广泛的使用，例如收割机跨区收获、无人机植保作业、农作物测绘、监测以及收割机与运粮车响应等农业作业环节[1]。农业机械的作业路径很大程度上决定作业过程的质量、效率和成本消耗[2]，因此农业设备作业路径的规划和优化工作具有重要意义。随着人工智能技术的不断发展，国内外农业正在经历一个重要的转折点：传统农业的耕作过程正在逐步转变为一种全新智能视角下的作业方式[3]。其中国外相关研究内容较多，但更多针对大型农场与大型地块的农业机械调度问题，由于我国的“大国小农”国情，因此在国内现阶段的推广应用较少且适用性较差[4-5]。目前全覆盖路径规划问题在国内农业领域的相关研究处于起步阶段：一方面集中在植保无人机的飞行航迹规划上；另一方面关于地面农机的路径规划问题集中在联合收割机在多个区域的转移路径上[6-8]，并不属于同一区域的全覆盖作业问题。徐博等[9-11]对多边形边界单田块的无人机作业路径提出了具体的算法并对多区域路径转移进行了研究。王宇等[12]对无人机作业提出了一种基于栅格模型的路径规划算法。黄小毛等[2]基于复杂边界田块对无人机自主作业路径进行了研究。总体来看，关于农机作业区域全覆盖路径规划相关文献仍然较少，而且地面与空中农业设备相比[13]，地面农机的作业不具备无人机的速度、通过性强等特点，地面农机全覆盖作业要时刻受到作业环境、少重复及遗漏面积等条件的制约，因此植保无人机路径规划方法虽然可以借鉴，但仍然需要考虑适合众多地面环境、设备本身参数及具体作业流程的影响。

对于重要的小麦收获作业环节，联合收割机通常在规则农田区域内沿着边界长边方向进行收获作业[14]。小麦播种时，大面积的农田通常采用机械直播(条播)方式，中小面积通常还是人工均匀播撒，分布较为集中且均匀，因此对于不规则形状地块或受环境因素制约的不规则地块，可以采用优化行驶方向使小麦收割机转弯次数最少。该场景下的收割机全覆盖作业路径优化对于不规则农田的小麦播种、水稻播种、全覆盖深耕等全覆盖作业路径规划问题都具有一定的借鉴和推广价值。

本文拟针对小麦收获环节联合收割机作业时可能遇到的复杂类型田块问题，提出一种基于作业优化方向的全覆盖路径规划算法，以获得凸边形、凹边形等多边形边界地块的作业路径轨迹，为实际环境下复杂边界地块的农机全覆盖路径规划提供借鉴和理论支持。

1 优化转弯次数的全覆盖调度

小麦联合收割机田间收获作业路径规划应该满足以下要求：有效工作路径中达到农田所有区域的全覆盖，重复作业及遗漏作业面积尽可能小；联合收割机转弯次数尽可能少。

传统的收割机田内覆盖收获作业方式较为适合标准、规整的矩形农田区域，通常表现为沿固定方向往复行走，该行走方向平行于区域最长边界，又被称为牛耕往复法，能够取得最少的转弯次数。而对于不规则形状的农田区域(非平行四边形)，行走路线无法与区域大多数边界平行或垂直，总存在一定的角度，因此会出现收割机转弯次数较多的现象。

对于一般小麦收获作业环节，联合收割机在规则农田区域内，沿区域边界的最长边方向进行作业。但对于不规则边界地块，当收割机基于不同方向进行作业时，由于割幅相同、作业面积固定，整体行走的有效路径长度是一定的，但是各方向受场地形状与边界限制，转弯次数发生改变，在田内转弯次数增多则会造成耕作面积遗漏的风险，收割效率降低。因此基于不规则多边形农田区域的调度模型，需要优化不同收获方向使收割机转弯次数最少。同时由于国内收割机通常转弯在田块内部，不必考虑收割机在田外的重复和多余覆盖面积，因此行走方向不同直接影响了收割机的转弯次数，且转弯过程总是伴随着收割机的减速和加速过程，增加作业时间和油耗。可以得出：在收获环节收割机的行走方向能够影响转弯次数从而增加收获作业的成本，因此需尽可能减少转弯次数，对田间收获作业过程中收割机行走方向进行优化。

该场景的收割机调度优化对于不规则农田的小麦播种、水稻播种、全覆盖深耕等环节的全覆盖作业路径场景都具有一定的适用性，能够提高农机作业效率，降低农机油耗。收割机田内作业路径规划适合于所有复杂边界地块，无论是农田面积大小都能得到应用，大型农田的复杂边界地块优化效果更加明显。实际情况下，小麦联合收割机收获作业中会出现卸粮过程以及收割机在不同农田的田外转移过程，但上述环节并不影响收割机单独田块的转弯次数，因此为了简化处理过程，本研究不考虑收割机卸粮和往返农田的非工作时间、不考虑收割机配置参数等无关因素，固定割幅同时仅探究不同行走方向对转弯次数的影响。

因此小麦联合收割机田内作业场景可以描述为：当一台收割机采用牛耕往复法进行全覆盖收获作业时，在不规则区域内寻找最优路径方案使转弯次数最少，提高收割效率、降低作业成本。

2 基于牛耕往复的调度规划模型

本文针对常见的二维田块，对于规则形状农田(如矩形农田)，常用的区域覆盖作业方式主要是牛耕往复法和内外螺旋法，相关文献[9-11]已经证实采用内外螺旋法会造成重复覆盖和遗漏覆盖的现象，与牛耕往复法转弯次数相同，因此规则矩形采用牛耕往复方式进行联合收割机收获作业更为合适。牛耕往复法如图1所示。

图1 规则区域的牛耕往复法Fig. 1 Full coverage method for a regular region

当作业区域为规则矩形，沿着区域一边每隔二分之一割幅绘制扫描线，扫描线方向的参考线为矩形农田长边，从左向右排序，实线为收割机作业路径，箭头表示行走方向，可以快速获得牛耕往复法的作业路径，此时由于是规则矩形，收割机沿长边行走距离达到最大值，因此所需转弯次数最少，行走路径最优。当作业区域为不规则多边形时，利用简单图形几何关系无法精确满足路径规划的要求，因此本研究利用扫描线法获得农田路径信息，结合改进的角度寻优算法进行作业路径的规划。首先由GIS软件提取作业区域的地图信息，提取作业农田边界点经纬度，构建二维平面坐标地图，绘制包裹整个作业农田且长款均为收割机割幅整数倍的矩形。对于收割机作业而言，用一组方向相同、间距与收割机割台宽度相等的扫描线进行扫描，扫描线与闭合多边形的边界交点所形成的线段就即为收割机路径集合。根据地块形状和农机路径规划情况的分析，可将指定作业区域收割机作业路径规划等价于多边形区域与扫描线交点问题。

对于不规则多边形，待作业区域为凹边形或凸边形农田，农田面积为S，收割机收割幅宽为d，收割机基于行走方向为θ时的行走路径设置为集合L，路径个数为n，其中第i条直线路径设置为li，i=1，2，…，n。设置农田多边形边界与扫描线(即收割机工作路径)交点个数记为路径节点N，则可以计算出扫描线个数为交点个数的一半即N/2。

该模型目标数学表达式

Z=min(fθ(N/2-1))，∀θ∈(0°，360°)

(1)

式中：fθ(N/2-1)——行走方向θ时，收割机工作路径的转弯次数最小值。

约束条件

(2)

式(2)表明收割机总路径长度与割幅宽度的乘积，即最小覆盖面积要大于农田面积。

理论表明：当收割机每次行走路线上割幅相邻且不重合时即农田面积覆盖不重复且不遗漏，由于农田总面积固定，因此收割机的有效行驶路径长度是固定的。因此，本研究基于以下假设建立收割机路径规划模型：(1)不考虑作业农田的多收割机调度及田内障碍物；(2)收割机两个相邻路线中无农田遗漏面积及重复覆盖面积；(3)收割机始终按照牛耕往复法行驶，并保持同一工作方向，不考虑其他的转弯类型。

3 转弯次数求解及角度优化算法

3.1 转弯次数求解算法

3.1.1 凸多边形扫描线算法

扫描线法又称为有序边表法，是用于表征和求解地块数据集和位置信息的算法，是计算机图形学中的经典问题，在计算机动画、3D打印和机器人路径规划等领域均有运用。扫描线法能够提高对每一组线段相交信息的求解效率和速度，因此可以用于收割机牛耕往复法的作业情景。

可以将不规则农田区域的经纬度坐标转换为二维平面坐标系下的闭合多边形区域[15]，已知不规则多边形区域的顶点坐标，将扫描线与x轴的夹角θ作为扫描线方向。θ=0°，即若干等间距水平扫描线等价于行走路径，计算扫描线与多边形各边的交点坐标，能够计算每条路径的长短，通过统计与多边形各边交点个数来计算路径个数，从而计算转弯次数。

扫描线算法的最重要特点是，无须计算多边形所有边与扫描线的交点，每条扫描线与多边形相交位置仅仅存在几条边；同时相邻的扫描线由于具有相同间隔，因此对于多边形同一条边，所有相交扫描线均有一定的步进关系，可以证明相邻扫描线的步进量Δx为相交边所在直线(Ax+By+C=0)斜率的倒数。

Δx=-B/A

(3)

若相邻扫描线间距不是1而是Δt，则表达式

Δx=-B×Δt/A

(4)

因此，基于扫描线的重要几何、数量特征，将扫描线与多边形相交边集中在一个数据表中，就形成了“有序边表法”：储存边的数据结构，以水平扫描线(方向角为0°)为例，每行信息由数组(Ymax，Xymin，Δx，next)组成，Ymax表示该多边形边的纵坐标最大值即该边上端的Y值；Xymin表示该边纵坐标最小值对应的横坐标X值，即该边下端点X坐标；Δx表示沿该边方向相邻扫描线之间的水平增量(X方向增量)，next表示下一条相交边。建立边表时，先按照下端点纵坐标值(即从下到上的方向)对多边形所有边进行分类，再将同一组的各边按照下端点横坐标值进行增量排序，若横坐标相同，按照Δx大小增量排序。具体实现过程见相关文献[2]，本节不再赘述。

扫描线算法步骤如图2所示。

图2 扫描线算法流程图Fig. 2 Flow chart of scanning line algorithm

3.1.2 凹多边形假想区域求解算法

扫描线算法能够满足求解复杂凸多边形边界的收割机转弯次数，但是实际环境中，作业农田往往因为周围水池、树木、建筑等出现相邻边界形成内角大于180°的凹边形区域。因此本研究在扫描线求解凸多边形基础上改进并设计了基于凸边形填补方法的几何算法对凹边形区域进行行走方向的寻优计算。主要步骤如下。

步骤1：依次输入凹边形区域S0各边顶点，并选择顶角大于180°的区域顶点o两侧相邻顶点所成假想直线l与除该顶点外凹边形所有顶点共同组成凸边形区域S1，同时该直线与该顶点o相邻两边界组成假想三角形区域S2。

步骤2：设置收割机作业参数，以及行走方向θ=0°，旋转步进量Δθ=1°。

步骤3：使用扫描线算法(参见3.3.1节算法步骤)分别计算行走方向θ时，凸边形区域S1、S2对应的各边路径节点个数n1、n2，同时记录假想区域S2边界的直线l节点个数为nl。

步骤4：计算凹边形区域S0转弯次数，N(S0)=(n1+n2-2nl)/2-1。

步骤5：令θ=θ+Δθ。

步骤6：当θ>180°时，停止迭代并输出最小N(S0)对应的θ值。

该假想区域算法的示意如图3所示。

图3 假想凸边形区域组成Fig. 3 Composition of farmland in an imaginary convex region

如图3所示，当不规则区域图形为凹多边形时，可以通过填补的形式，将凹边形的相邻两条边(夹角大于180°)所形成的区域直接用一条假想线连接顶点，从而形成凸边形区域，因此该凸边形就由原先凹边形与假想区域凸边形组成。原凹边形由b、c边以及剩余边集合d组成，记为多边形No.1；组合凸边形由假想线a(图3中虚线)与边集合d组成，记为多边形No.2；假想区域所形成的也是凸边形，由假想线a、原边b、c形成，记为多边形No.3。对于收割机工作路径来说，转弯次数与路径线个数有关，可以通过区域边与路线交点数量计算得到，这里将多边形边与扫描线交点记为路径节点，数量用N表示，假设区域各边顶点不存在路径节点，可以得到

(5)

通过凸多边形扫描线算法可以得到凸边形(No.2与No.3)各边路径节点数量。因此可以推出原凹变形区域节点数量，得到关于N(No.1)与N(a)的表达式如式(6)所示。

N(No.1)=N(No.3)+N(No.2)-2N(a)

(6)

因此已知原凹边形边界信息，形成的假想两个凸边形边界信息通过凸边形算法求解得到转弯次数及假想边界与路径的相交次数，就可以获得原凹边形的转弯次数。

(7)

式中：n——区域所有边界或指定边界线上的路径节点数量。

若实际复杂环境下的农田作业区域可以转换为不规则凸、凹边形区域，则通过转弯次数求解算法可以得到相应结果。

3.2 最优作业角度搜索算法

对单一多边形田块而言，可以采用“旋转法”进行近似求解，本质上属于穷举算法，从0°开始，以1°为步长，计算所有可能的行走方向的路径，比较所有路线的转弯次数N，取其最小者对应的方向值为最优行走方向。当θ≠0时，通过坐标变化可简化计算过程，将多边形顶点绕坐标原点顺时针旋转θ(正变换)得到旋转后的多边形顶点，基于扫描线法计算得到中间路径，再将路径线端点(x0，y0)绕着矩形原点逆时针旋转θ(逆变换)即得到真实路径的端点(x，y)。

正变换

θ=-θ*(互为相反数)

(8)

逆变换

(9)

总体来看，本研究通过旋转步进搜索算法，再结合多边形转弯次数求解算法，便能够得到基于最优行走方向的复杂多边形最优路径轨迹。具体算法步骤如图4所示。

图4 算法流程图Fig. 4 Algorithm flowchart

4 算例验证

上述全部算法过程在Window10系统环境下编码实现，在同一工作参数条件下进行多次试验，测试算法计算寻优结果。本研究利用假想田块边界，转化为二维平面直角坐标，对单一多边形边界的田块采用“旋转法”优化行走方向。转弯次数通过计算扫描轨迹线个数得到，扫描线数目通过计算多边形各边交点数目(即路径节点)总和得到。一般小型联合收割机割台宽度在1.5～3 m，因此根据常见联合收割机型号及中小型农田区域面积，本文取收割机的工作宽幅为2.5 m。

4.1 凸多边形作业路径优化方案

仿真算例转换至笛卡尔坐标系中，水平方向与x轴重合，农田边界信息及顶点坐标如图5所示，通过凸边形扫描线算法求解，得到最优作业角度为100°。为验证算法计算结果，使行走方向与水平方向夹角分别为0°、45°、90°、135°，沿区域最长边方向29.5°，以及算法得出最优角度100°的凸多边形区域农田填充扫描线如图6所示。

图5 凸边形区域农田Fig. 5 Cropland in single area with convex edge

(a) θ=0°

(b) θ=45°

(c) θ=90°

(d) θ=135°

(e) θ=29.5°

(f) θ=100°图6 凸边形区域不同行走方向路径轨迹线Fig. 6 Path trajectories of different operating directions in the convex edge area

当行走方向与水平夹角θ=100°时，该区域田块的作业方案最佳，作业进入点坐标为(168，41)，作业路径节点为96个，收割机转弯次数为47次。指标结果如表1所示：与基于其他方向的作业路径方案相比，当行走方向θ=100°时，同一收割机比行走方向为0°、135°转弯次数少13次，优化率达21.67%，比行走方向为45°转弯次数少9次，优化率达16.07%、比行走方向为90°少3次，优化率为6%、比作业沿长边方向为29.5°转弯次数少6次，优化率为11.32%，因此可以得出该算法能够有效处理基于不同角度寻优的凸多边形农田的收割机调度规划，并得出全局最优行走方向。

表1 基于不同角度的凸多边形农田指标Tab. 1 Indicators of convex polygons based on different operating directions

4.2 凹多边形田内作业路径优化方案

凹边形仿真算例的边界信息如图7所示，对凹边形进行填充的区域已通过图3表示，其中a为相邻内角大于180°的边界(b、c)顶点形成的假想线，d为原凹边形其余边界，最长边与横轴夹角为29.5°。由第3节凹边形作业角度优化算法原理可知，关于N(No.1)与N(a)的表达式为N(No.1)=N(No.3)+N(No.2)-2N(a)。

图7 不规则凹边形区域农田Fig. 7 Farmland with irregular concave edge area

通过凸多边形扫描线算法可以得到凸边形(No.2与No.3)各边路径节点数量。N(a)可以通过扫描线算法得到。因此通过算法求解原凹边形区域填充扫描线，行走方向与水平方向夹角分别为0°、45°、90°、135°，沿区域最长边方向29.5°，以及算法得出假想凸多边形区域最优角度100°，如图8所示。

从图8可以看出，θ=100°是凸多边形No.2的最优作业角度，但是对于去掉假想区域(No.3)后的实际凹边形农田(No.1)来说，θ=100°的转弯次数要多于45°、90°、29.5°，即凹边形农田最优作业方向并不能通过填补的假想凸边形寻优计算直接获得。因此，依据3.2节的旋转搜索算法，在Window10系统上设置旋转步长为1°，旋转次数为180次，得到0°～180°中转弯次数最少的行走方向，即最优作业方向。凹边形农田区域旋转算法求解过程的收割机转弯次数如图9所示。

(a) θ=0°

(b) θ=45°

(c) θ=90°

(d) θ=135°

(f) θ=100°图8 假想区域的扫描线轨迹Fig. 8 Scan line trajectories of imaginary regions

图9 不同角度下凹多边形区域的转弯次数Fig. 9 Number of turns in a concave polygon area with different angles

通过图9可知，当行走方向为90°时，凹边形区域转弯次数最少，因此对于凹边形区域而言，收割机保持与水平夹角为90°的行走方向为最优作业方案。

凹边形区域不同角度的指标结果如表2所示：与基于其他方向的作业路径方案相比，当行走方向θ=90°时，同一收割机比行走方向为100°、135°转弯次数少10次，优化率达16.7%，比行走方向为0°转弯次数少20次，优化率达28.6%、比行走方向为45°少6次，优化率达10.7%、比作业沿边界最长边方向为29.5°转弯次数少3次，优化率达5.66%，因此可以得出，基于填补方法的混合优化算法能够有效处理基于不同角度的凹多边形农田的收割机调度规划，并得出全局较优的路径规划方案。

表2 基于不同角度的凹边形区域指标Tab. 2 Indexes of concave edge area based on different angles

5 结论

1) 单台联合收割机田间作业通常采用全覆盖路径规划，主要针对规则区域进行牛耕往复法，对于不规则区域，如凹、凸多边形农田不同行走方向总会造成收割机转弯次数增加，影响作业质量、油耗与工作效率。因此本文针对不规则区域的单台收割机作业角度建立调度模型与设计优化求解算法，实现转弯次数最少的田间行驶路径规划方案。结合仿真算例验证结果，所提出的优化行走方向算法针对不规则多边形区域而言能够有效优化收割机行走方向：在凸边形农田仿真案例中，该算法求解的最优作业角度是100°，该方向路径规划在转弯次数上要比沿区域最长边(方向29.5°)牛耕往复的路径轨迹优化程度为11.32%，比普通方向(行走方向0°、45°、90°、135°等)优化程度达到6%～21.7%；在凹边形农田仿真案例中，该算法求解的最优作业路径方向是90°，比沿边界最长边(方向29.5°)路径的优化程度为5.66%，比其他方向(行走方向0°、45°、135°、100°等)的优化程度达到10%～28.6%。

2) 本研究设计了凹凸多边形转弯次数求解算法并结合了旋转搜索算法以获得复杂边界区域最优行走方向，形成该区域小麦收割机的工作路径方案。能够进一步推广至实际复杂边界的农田区域，适用于全覆盖路径规划的转弯次数优化环节，如小麦收割机收获作业、小麦、水稻等播种、全覆盖深耕等具体环节，为减少农机作业转弯次数，提高作业效率等提供了有效的决策依据。

3) 针对全覆盖路径行走方向优化问题，本研究基于单个收割机对单独农田区域的作业路径规划，并未考虑多收割机协同作业方式，未来可以通过大型农田区域划分的方法解决多机协同问题；同时本研究基于复杂凹边形进行假想区域填补形成简单凸边形，最终获得转弯次数，若作业区域含有多个凹形区域，可以利用分割而非填补的思想对不规则凹边形进行区域划分，从而将整个不规则区域转化为若干凸边形作业区域，每个区域可以产生不同行走方向的优化路线，从而达到整体最优效果。因此未来研究方向可以集中在对复杂边界环境的区域划分方式及优化求解等。