四邊形田塊下油菜聯(lián)合收獲機(jī)全覆蓋作業(yè)路徑規(guī)劃算法

羅承銘，熊陳文，黃小毛※，丁幼春，王紹帥

（1. 華中農(nóng)業(yè)大學(xué)工學(xué)院，武漢 430070；2. 農(nóng)業(yè)農(nóng)村部長(zhǎng)江中下游農(nóng)業(yè)裝備重點(diǎn)實(shí)驗(yàn)室，武漢 430070）

0 引言

隨著城鎮(zhèn)化進(jìn)程的不斷推進(jìn)，中國(guó)農(nóng)村勞動(dòng)力老齡化與短缺問題逐漸凸顯，“機(jī)器換人”的需求日益增加。近年來隨著農(nóng)機(jī)自動(dòng)導(dǎo)航技術(shù)和農(nóng)用車輛底盤數(shù)字化驅(qū)動(dòng)技術(shù)的快速發(fā)展，智能化的農(nóng)業(yè)裝備被廣泛應(yīng)用于農(nóng)業(yè)生產(chǎn)的各個(gè)環(huán)節(jié)，無人農(nóng)場(chǎng)生產(chǎn)模式正迅速地被廣泛接受并進(jìn)行各種試驗(yàn)示范[1-3]。作業(yè)路徑是車輛自動(dòng)導(dǎo)航作業(yè)跟蹤的依據(jù)，作業(yè)路徑及調(diào)度策略一定程度上決定著具體作業(yè)條件下的機(jī)具、農(nóng)資消耗總量和利用率。

對(duì)比傳統(tǒng)農(nóng)業(yè)車輛在作業(yè)過程中通過駕駛員主觀判斷來規(guī)劃選擇作業(yè)路徑的方式，通過計(jì)算機(jī)規(guī)劃算法自動(dòng)規(guī)劃路徑能夠顯著提高農(nóng)機(jī)作業(yè)效率和質(zhì)量、節(jié)約能源消耗[4]。Palmer等[5]利用車載GPS記錄的數(shù)據(jù)，通過事后分析傳統(tǒng)噴霧機(jī)作業(yè)軌跡發(fā)現(xiàn)，作業(yè)重疊（13%～27%）和遺漏（0.03%～1.56%）現(xiàn)象嚴(yán)重，而通過提出的路徑規(guī)劃算法，作業(yè)距離減少16%，作業(yè)消耗減少10%。Bochtis等[6]通過不同形狀田塊、不同作業(yè)參數(shù)的288組實(shí)例對(duì)比研究發(fā)現(xiàn)，經(jīng)過算法優(yōu)化獲得的作業(yè)調(diào)度方案比傳統(tǒng)的逐行調(diào)度方案在非有效作業(yè)距離上平均降幅達(dá)到58.65%，而在地頭轉(zhuǎn)彎空間上則平均節(jié)約了19.23%。

自動(dòng)駕駛車輛跟蹤的目標(biāo)路徑經(jīng)歷了基于機(jī)器視覺目標(biāo)檢測(cè)識(shí)別在線規(guī)劃[7]、A-B點(diǎn)示教、全過程示教和全局離線事前規(guī)劃等幾個(gè)階段。Conesa-Mu?oz等[8]針對(duì)田間精準(zhǔn)除草問題，以路徑總長(zhǎng)度、油箱容量和除草劑補(bǔ)給等為優(yōu)化目標(biāo)，考慮農(nóng)機(jī)不同的行進(jìn)速度與轉(zhuǎn)彎半徑，建立多機(jī)協(xié)同作業(yè)路徑規(guī)劃方法。Seyyedhasani等[9]為優(yōu)化多機(jī)協(xié)同作業(yè)，提出了一種能夠動(dòng)態(tài)、實(shí)時(shí)更新車輛路徑的全覆蓋路徑規(guī)劃算法。Hameed[10]通過對(duì)二維與三維田塊進(jìn)行分析，設(shè)計(jì)了一種多目標(biāo)優(yōu)化的路徑規(guī)劃算法，可減少10%～15%的作業(yè)時(shí)間。Plessen[11]針對(duì)大田植保作業(yè)時(shí)噴霧機(jī)容量較小的問題，提出了基于多次補(bǔ)給作業(yè)的區(qū)域覆蓋路徑規(guī)劃方法。Utamima等[12]以最短路徑為優(yōu)化目標(biāo)，在農(nóng)機(jī)路徑規(guī)劃中提出了進(jìn)化混合鄰域搜索算法，有效縮短了農(nóng)機(jī)的作業(yè)總長(zhǎng)度。Nilsson等[13]以田塊全覆蓋為主要目標(biāo)，考慮路徑長(zhǎng)度、作業(yè)時(shí)間和土壤壓實(shí)等次要目標(biāo)，基于人工蜂群算法建立農(nóng)機(jī)路徑規(guī)劃方法。國(guó)內(nèi)對(duì)于農(nóng)機(jī)路徑規(guī)劃研究起步較晚，孟志軍等[14]針對(duì)凸多邊形田塊，提出了基于不同的路徑優(yōu)化目標(biāo)，通過計(jì)算最優(yōu)作業(yè)角度生成作業(yè)路徑的方法。劉剛等[15]提出了以農(nóng)田地勢(shì)高程分布特征為先決條件，以無效作業(yè)狀態(tài)、轉(zhuǎn)向操作和重復(fù)行走距離最少為優(yōu)化目標(biāo)的農(nóng)機(jī)全覆蓋路徑規(guī)劃方法。

綜上，現(xiàn)有研究大多針對(duì)輪式拖拉機(jī)或收獲機(jī)展開，針對(duì)履帶式油菜聯(lián)合收獲機(jī)的研究較少，更鮮有考慮油菜聯(lián)合收獲機(jī)的分禾豎割刀對(duì)作業(yè)路徑的影響。鑒于此，本研究通過分析長(zhǎng)江中下游稻油水旱輪作區(qū)油菜作物聯(lián)合收獲過程的作業(yè)特點(diǎn)，以最小漏收面積為前提、最短作業(yè)總長(zhǎng)度為優(yōu)化目標(biāo)，針對(duì)四邊形這一最為常見的田塊邊界類型條件下的油菜聯(lián)合收獲作業(yè)路徑問題，分別為單側(cè)豎割刀和雙側(cè)豎割刀的油菜聯(lián)合收獲機(jī)，提出傳統(tǒng)環(huán)形路徑（輪廓平行路徑）和混合路徑（先輪廓平行路徑、后方向平行路徑）的全覆蓋作業(yè)路徑規(guī)劃算法，以期為長(zhǎng)江中下游稻油輪作無人農(nóng)場(chǎng)中油菜無人化聯(lián)合收獲提供作業(yè)路徑規(guī)劃方面的理論與技術(shù)支撐。

1 油菜聯(lián)合收獲過程的作業(yè)特點(diǎn)及路徑要求

中國(guó)南方地區(qū)農(nóng)田耕地面積相對(duì)較小且分散，尤其在長(zhǎng)江中下游稻油水旱輪作區(qū)，田塊之間的邊界界限十分明顯，一般都伴隨著田埂、溝渠、坡岸等不可跨越的障礙物。因此油菜聯(lián)合收獲機(jī)作業(yè)時(shí)，除了出入口外（有時(shí)連出入口也沒有，而需借助專用爬梯），田塊的邊界均為不可跨越，這是長(zhǎng)江中下游區(qū)域油菜聯(lián)合收獲作業(yè)過程的第一個(gè)特點(diǎn)。第二，油菜作物植株分叉較多，機(jī)械收獲時(shí)，為減少割臺(tái)損失，需要在割臺(tái)側(cè)邊加裝豎式割刀進(jìn)行主動(dòng)分禾[16-17]，有雙側(cè)豎割刀和單側(cè)（左或右）豎割刀兩種形式。其中雙側(cè)豎割刀對(duì)收獲次序沒有要求，而單側(cè)豎割刀則需要按照一定的次序進(jìn)行收獲作業(yè)。

油菜為旱地作物，因此南方油菜田內(nèi)部均設(shè)有一定數(shù)量的排水溝，為保證機(jī)器良好的通過性能，油菜聯(lián)合收獲機(jī)一般采用履帶式而非輪式底盤。履帶式油菜聯(lián)合收獲機(jī)通常以差速方式進(jìn)行轉(zhuǎn)向[18]，利用兩側(cè)履帶卷繞速度大小或方向上的不同，使機(jī)器完成轉(zhuǎn)向和轉(zhuǎn)彎過程。若不考慮土壤地表造成的滑移滑轉(zhuǎn)現(xiàn)象，履帶式車輛轉(zhuǎn)向原理按照兩側(cè)履帶速度方向是否一致可分成兩種情形（圖1）。當(dāng)兩側(cè)履帶速度方向相同時(shí)，若速度大小相等（V1=V2）機(jī)器會(huì)直線前行，而若一側(cè)速度減小且兩側(cè)速度比值k保持不變（即k=|V2|/|V1|為定值），則機(jī)器會(huì)向速度值小的一側(cè)轉(zhuǎn)向，此時(shí)機(jī)器作回轉(zhuǎn)運(yùn)動(dòng)，回轉(zhuǎn)中心O落在機(jī)器外部且物理中心O′繞回轉(zhuǎn)中心O作圓周運(yùn)動(dòng)，轉(zhuǎn)彎半徑一般大于機(jī)器寬度的一半（圖1a）。當(dāng)速度方向相反且比值k不變時(shí)，機(jī)器原地回轉(zhuǎn)，回轉(zhuǎn)中心O落在機(jī)器履帶中心和物理中心O′之間，即O′繞O作圓周運(yùn)動(dòng)，此時(shí)轉(zhuǎn)彎半徑一般小于機(jī)器寬度的一半（圖1b）。當(dāng)V1=-V2時(shí)，O′、O重合，轉(zhuǎn)彎半徑為R=0，為原地逆差式轉(zhuǎn)向；當(dāng)V1=0時(shí)，圖1中兩種情形歸為一種，為單側(cè)制動(dòng)式轉(zhuǎn)向。兩種情形下，機(jī)器的瞬時(shí)回轉(zhuǎn)中心O的位置始終保持不變，因此回轉(zhuǎn)中心周圍土壤會(huì)遭到嚴(yán)重不均勻擠壓和破壞。實(shí)際操作中，除轉(zhuǎn)彎空間受限時(shí)采用原地回轉(zhuǎn)式轉(zhuǎn)彎外，一般多用變速動(dòng)態(tài)式轉(zhuǎn)彎，即邊行進(jìn)、邊轉(zhuǎn)彎，此時(shí)機(jī)器瞬時(shí)回轉(zhuǎn)中心的位置和轉(zhuǎn)彎半徑的大小會(huì)隨行進(jìn)量和速度比值的變化而變化。此外，轉(zhuǎn)彎半徑還與履帶的滑轉(zhuǎn)率（%）、滑移率（%）等因素相關(guān)，實(shí)際轉(zhuǎn)彎半徑相對(duì)于理論轉(zhuǎn)彎半徑的修正系數(shù)在1.737～2.947之間變化[19]。為簡(jiǎn)化計(jì)算過程，算法設(shè)計(jì)時(shí)假設(shè)轉(zhuǎn)彎半徑恒定不變，但會(huì)取多組不同數(shù)值進(jìn)行驗(yàn)證。

綜上，概括長(zhǎng)江中下游稻油輪作區(qū)油菜聯(lián)合收獲自動(dòng)化作業(yè)過程對(duì)所規(guī)劃作業(yè)路徑的要求為：

1）遵循以不碾壓未收獲作物且與田塊的剛性邊界相適應(yīng)（機(jī)器在田間移動(dòng)時(shí)尤其是地頭轉(zhuǎn)彎或轉(zhuǎn)移時(shí)不可觸碰邊界）的總原則，一般執(zhí)行“先外圍、后內(nèi)部”的田塊遍歷覆蓋總策略，須先采用輪廓平行路徑進(jìn)行作業(yè)以騰出足夠的地頭轉(zhuǎn)彎空間。

2）收獲的具體次序要與油菜聯(lián)合收獲機(jī)割臺(tái)上豎割刀的形式相適應(yīng)：左側(cè)豎割刀的油菜聯(lián)合收獲機(jī)，只能相對(duì)于田塊中心沿逆時(shí)針方式作業(yè)；右側(cè)豎割刀的油菜聯(lián)合收獲機(jī)，只能相對(duì)于田塊中心沿順時(shí)針方式作業(yè)。雙側(cè)豎割刀的油菜聯(lián)合收獲機(jī)則沒有限制。

3）以收獲作業(yè)路徑全覆蓋為總前提，以油菜聯(lián)合收獲機(jī)最小能耗和最少作業(yè)時(shí)間為優(yōu)化總目標(biāo)，即在基礎(chǔ)的有效收獲作業(yè)路徑和無作業(yè)的轉(zhuǎn)移銜接路徑生成時(shí)盡可能使油菜聯(lián)合收獲機(jī)的漏收面積最小、總的作業(yè)路徑最短、轉(zhuǎn)彎次數(shù)最少、倒車次數(shù)最少。

2 算法基本原理

2.1 田塊邊界數(shù)據(jù)定義及算法流程

以多邊形表示田塊邊界，田塊邊界的頂點(diǎn)可通過人工手持GPS實(shí)地打點(diǎn)或地理信息系統(tǒng)（Geographic Information System，GIS）中鼠標(biāo)選取，經(jīng)過通用橫軸墨卡托（Universal Transverse Mercator，UTM）投影算法[20]進(jìn)行坐標(biāo)轉(zhuǎn)換，將GPS坐標(biāo)數(shù)據(jù)轉(zhuǎn)化為平面坐標(biāo)數(shù)據(jù)，按逆時(shí)針方向依次存儲(chǔ)在多邊形數(shù)組中。

以多邊形田塊邊界信息、田塊出入口位置和油菜聯(lián)合收獲機(jī)的基本參數(shù)為輸入。算法執(zhí)行時(shí)，首先通過等距偏置處理生成輪廓平行路徑，當(dāng)油菜聯(lián)合收獲機(jī)為單側(cè)豎割刀時(shí)，生成由輪廓平行路徑為主要作業(yè)路徑的環(huán)形路徑；當(dāng)油菜聯(lián)合收獲機(jī)具有雙側(cè)豎割刀時(shí)，則需要再經(jīng)過多邊形掃描線填充算法處理，生成由輪廓平行路徑和方向平行路徑為主要作業(yè)路徑的混合路徑。算法流程如圖2所示。

在混合路徑中，油菜聯(lián)合收獲機(jī)由入口位置開始作業(yè)，先按照輪廓平行路徑及其銜接路徑完成田塊外圍區(qū)域收割，形成足夠的地頭轉(zhuǎn)彎空間，再按照方向平行路徑及其銜接路徑繼續(xù)作業(yè)，直至完成整個(gè)田塊的收割任務(wù)，如圖3所示。

2.2 多邊形等距偏置處理

多邊形等距偏置算法[21]是輪廓平行路徑的基礎(chǔ)算法，以油菜聯(lián)合收獲機(jī)的作業(yè)幅寬為偏置距離，將待作業(yè)田塊的邊界輪廓線逐步向內(nèi)偏置，即可獲得一組等距多邊形。對(duì)于凸多邊形而言，其等距多邊形可以通過解析法準(zhǔn)確求解獲得，且不會(huì)隨著偏置次數(shù)的增加而出現(xiàn)“退化現(xiàn)象”（多邊形頂點(diǎn)減少或多邊形個(gè)數(shù)增加）[21]。對(duì)任意相鄰的兩邊界輪廓線P1P2、P2P3，利用平行線定理可得出等距線AB、BC所在直線的斜截式方程，如式（1）所示，解方程即可得到頂點(diǎn)P2偏置后對(duì)應(yīng)的B點(diǎn)坐標(biāo)（圖4）。以此類推，求出其他各頂點(diǎn)偏置后的坐標(biāo)，即可得到偏置后的等距多邊形。

式中x1、y1分別表示P1的橫坐標(biāo)、縱坐標(biāo)，m；x2、y2分別表示P2的橫坐標(biāo)、縱坐標(biāo)，m；W為油菜聯(lián)合收獲機(jī)的作業(yè)幅寬，m；12ppl、23ppl為邊界線段P1P2、P2P3的長(zhǎng)度，m。

若田塊內(nèi)部區(qū)域的作業(yè)路徑以方向平行路徑為主，則需要先通過輪廓平行路徑收獲邊界附近區(qū)域來為方向平行路徑的行間調(diào)度騰出足夠的地頭轉(zhuǎn)彎空間。該區(qū)域空間的大小取決于實(shí)際操作時(shí)的轉(zhuǎn)彎類型和機(jī)器的物理參數(shù)，保證機(jī)器順暢轉(zhuǎn)彎并避免在轉(zhuǎn)彎過程中觸碰到田塊邊界上的潛在障礙物。通過大量測(cè)試分析，本研究擬定經(jīng)驗(yàn)公式來計(jì)算實(shí)際偏置次數(shù)，如式（2）所示。

式中m為偏置次數(shù)；表示向上取整；R為油菜聯(lián)合收獲機(jī)的轉(zhuǎn)彎半徑，m；B為油菜聯(lián)合收獲機(jī)的車身寬度，m；LS為安全距離，根據(jù)油菜聯(lián)合收獲機(jī)的導(dǎo)航精度進(jìn)行取值，m。

2.3 輪廓平行路徑及其銜接路徑

按照多邊形等距偏置算法，將田塊的輪廓邊界依次偏置處理m次，偏移距離除第一次偏置為W/2外，后續(xù)偏置時(shí)的偏置距離均在前一次基礎(chǔ)上加W，即可得到初始的輪廓平行路徑環(huán)組。該路徑環(huán)組存在2個(gè)問題需要進(jìn)一步進(jìn)行平滑過渡處理：1）各環(huán)之間彼此孤立；2）每環(huán)為一組首尾相連的線段，各相鄰線段間夾角小于180°。為滿足機(jī)器行駛要求，需分別進(jìn)行環(huán)間銜接處理和環(huán)上拐角處理，獲得環(huán)間銜接路徑和環(huán)上拐角銜接路徑。

對(duì)于輪廓平行路徑的環(huán)間銜接，根據(jù)田塊入口相對(duì)于所在邊位置的不同，又分為兩種情況：1）剛好位于所在邊一側(cè)；2）處于所在邊中間。分別采取兩種不同的處理策略，以盡可能獲得最優(yōu)的路徑，如圖5所示。對(duì)于進(jìn)入點(diǎn)剛好位于所在邊一側(cè)且與單側(cè)豎割刀方位屬性一致時(shí)（左側(cè)豎割刀，逆時(shí)針收割，對(duì)應(yīng)所在邊右側(cè)；右側(cè)豎割刀，順時(shí)針收割，對(duì)應(yīng)所在邊左側(cè)），采用的銜接策略如圖5a所示。算法設(shè)計(jì)時(shí)，取當(dāng)前環(huán)的最后一直線段AB和相鄰下一環(huán)形路徑的第一直線段CD，反向延長(zhǎng)線段CD，交線段AB于B′點(diǎn)，對(duì)∠AB′C進(jìn)行半徑為R的圓角處理，垂足分別為A′和C′。按照“AB直線前進(jìn)，BA′直線倒車，A′C′圓弧轉(zhuǎn)彎，C′D直線前進(jìn)”的路徑完成銜接。當(dāng)進(jìn)入點(diǎn)位于非側(cè)邊位置或與豎割刀方位屬性不一致時(shí)，采用的銜接策略如圖5b所示。算法設(shè)計(jì)時(shí)，作入口所在輪廓線的垂線分別交線段AB、線段CD于B點(diǎn)、C點(diǎn)。過B點(diǎn)以O(shè)1為圓心做半徑為R的圓，同時(shí)以O(shè)1為圓心做半徑為2R的圓，對(duì)C點(diǎn)同樣處理，圓心位置為O2，其中兩個(gè)半徑為2R的圓交于O3點(diǎn)，并以O(shè)3為圓心做半徑為R的圓，與前述兩個(gè)半徑為R的圓分別相切于E、F點(diǎn)，此時(shí)按照“AB直線前進(jìn)，BE圓弧轉(zhuǎn)彎，EF圓弧倒車，F(xiàn)C圓弧轉(zhuǎn)彎，CD直線前行”的路徑完成銜接。

對(duì)于輪廓平行路徑的環(huán)上拐角銜接，同樣存在兩種不同的情況及處理策略。對(duì)于最外環(huán)而言，因?yàn)樘飰K邊界除入口外多為不可觸碰和跨越的“剛性邊界”，采用“AB直線前行，BA′直線倒車，A′C′圓弧轉(zhuǎn)彎，C′D直線前行”的銜接路徑如圖6a所示。對(duì)于其它非最外環(huán)路徑而言，因最外環(huán)的收割作業(yè)而騰挪出一定的轉(zhuǎn)彎空間，采用“AB直線前行，BE圓弧倒車，EC′圓弧轉(zhuǎn)彎，C′D直線前行”的銜接路徑如圖6b所示。

2.4 方向平行路徑及其銜接路徑

當(dāng)油菜聯(lián)合收獲機(jī)僅具有一側(cè)豎割刀時(shí)，通過由輪廓平行路徑組成的環(huán)形路徑，即可完成整個(gè)田塊區(qū)域的收割任務(wù)，這是最傳統(tǒng)也是目前采用最多的一種收割策略。當(dāng)油菜聯(lián)合收獲機(jī)具有雙側(cè)豎割刀時(shí)，則有更多的選擇。當(dāng)按照輪廓平行路徑完成田塊外圍區(qū)域收割后，形成足夠的地頭轉(zhuǎn)彎空間，剩下的待收獲區(qū)域，可以采用方向平行路徑進(jìn)行作業(yè)，此時(shí)的組合路徑稱為混合路徑。

方向平行路徑是指機(jī)器的有效作業(yè)路徑線段互相平行，且方向固定地平行于田塊的某一條邊界。該方向稱之為最優(yōu)作業(yè)方向，可按照多邊形最小跨度法[22]求解得到，有效作業(yè)路徑線段為一組間距為W的平行線組，可采用基于活性邊表法的掃描線填充算法[23]獲得。有效作業(yè)路徑是彼此孤立的平行線段，同樣需要銜接處理，也即是通常意義上的轉(zhuǎn)彎掉頭。

當(dāng)轉(zhuǎn)彎半徑大于0時(shí)，為使車輛行進(jìn)順暢，其轉(zhuǎn)向過程須遵循一定的轉(zhuǎn)彎策略進(jìn)行平滑過渡。黃小毛等[24]在U型、Ω型和T型等3種常見轉(zhuǎn)彎策略的基礎(chǔ)上，提出了長(zhǎng)度更短的M型轉(zhuǎn)彎策略和T′型轉(zhuǎn)彎策略。具體選擇哪種轉(zhuǎn)彎策略，主要取決于2條方向平行路徑間間距（W，m）和最小轉(zhuǎn)彎半徑（R，m）之間的關(guān)系，同時(shí)考慮轉(zhuǎn)彎路徑長(zhǎng)度、地頭空間的大小和作業(yè)種類，保證最小的轉(zhuǎn)彎長(zhǎng)度和地頭空間且不造成作物碾壓。通過對(duì)比，選取U型轉(zhuǎn)彎策略和T′型轉(zhuǎn)彎策略作為方向平行銜接路徑，其轉(zhuǎn)彎過程原理如圖7所示。當(dāng)使用U型轉(zhuǎn)彎時(shí)，機(jī)器采用“AB直線前行，BH1圓弧轉(zhuǎn)彎，H1H2直線前行，H2C圓弧轉(zhuǎn)彎，CD直線前行”的路徑如圖7a所示。當(dāng)使用T′型轉(zhuǎn)彎時(shí)，機(jī)器采用“AB直線前行，BH2圓弧轉(zhuǎn)彎，H2H1圓弧倒車，H1C圓弧轉(zhuǎn)彎，CD直線前行”的路徑如圖7b所示。

2.5 方向平行路徑調(diào)度優(yōu)化

方向平行路徑中有效作業(yè)路徑的調(diào)度次序會(huì)極大地影響轉(zhuǎn)彎的路徑總長(zhǎng)度和效率。傳統(tǒng)作業(yè)中普遍采取逐行往復(fù)式的調(diào)度策略，該調(diào)度策略配合Ω型轉(zhuǎn)彎策略被廣泛使用、操作手法相對(duì)容易被接受，但實(shí)踐證明并非最優(yōu)策略[25]。通過對(duì)方向平行路徑進(jìn)行調(diào)度優(yōu)化，可以有效減少非工作路徑的長(zhǎng)度。

本研究將該調(diào)度問題看作旅行商問題（Travelling Salesman Problem，TSP）[24]并采用Google公司開發(fā)的一種用于組合優(yōu)化問題的開源軟件套件OR-Tools進(jìn)行優(yōu)化。將每條方向平行路徑線段的端點(diǎn)看成一個(gè)城市，為確保屬于同一條方向平行路徑的2個(gè)城市以相鄰方式依次包含在最終解里面，將對(duì)應(yīng)兩點(diǎn)的“名義距離”設(shè)置為0。此外考慮到2條方向平行路徑銜接時(shí)一般按照同側(cè)方式進(jìn)行轉(zhuǎn)移，因此對(duì)于2條方向平行路徑AB、CD而言，擬定按照表1方式計(jì)算優(yōu)化時(shí)的TSP距離矩陣。

表1 距離矩陣計(jì)算方法 Table 1 Calculation method of distance matrix

由于TSP屬于典型的組合優(yōu)化問題，目前尚無可求取準(zhǔn)確解的完美算法，該問題也一直是計(jì)算機(jī)領(lǐng)域的難點(diǎn)問題[26-27]。本研究通過調(diào)用OR-Tools軟件套件內(nèi)的路由解算器，完成方向平行路徑的調(diào)度優(yōu)化。路徑規(guī)劃算法在執(zhí)行調(diào)度優(yōu)化前，需先采用距離矩陣計(jì)算方法求出方向平行路徑各端點(diǎn)之間的距離矩陣。調(diào)度優(yōu)化時(shí)，首先使用局部最優(yōu)路徑策略得到調(diào)度次序的初始解，再通過引導(dǎo)式局部搜索策略繼續(xù)求解獲得新的調(diào)度次序，同時(shí)計(jì)算每一個(gè)調(diào)度次序?qū)?yīng)的路徑總長(zhǎng)度，當(dāng)搜索時(shí)間大于設(shè)定時(shí)間（最大搜索時(shí)間設(shè)置為4 s）時(shí)，輸出最小路徑總長(zhǎng)度所對(duì)應(yīng)的調(diào)度次序，即為最優(yōu)調(diào)度次序。

2.6 算法運(yùn)行環(huán)境

本研究的油菜聯(lián)合收獲作業(yè)路徑規(guī)劃算法以Python作為編程語(yǔ)言，在PyCharm平臺(tái)上編程實(shí)現(xiàn)，并結(jié)合PyQt5開發(fā)工具編寫路徑規(guī)劃軟件。在Inter(R) Core(TM) i5-9400 CPU @ 2.9 GHz、16 GB、Windows10操作系統(tǒng)環(huán)境下，運(yùn)行程序并進(jìn)行效果測(cè)試。

3 實(shí)例仿真計(jì)算

選取4塊典型的四邊形實(shí)際田塊進(jìn)行算法求解和效率計(jì)算分析測(cè)試。田塊邊界數(shù)據(jù)通過Google Earth軟件獲取，并以KML格式作為交換格式。其中田塊1、2為湖北武漢市實(shí)際田塊，田塊3、4為湖北宜昌市實(shí)際田塊，田塊面積分別為2 033.02、2 571.35、2 784.94和3 329.01 m2。采用星光4LZY-3.5S油菜聯(lián)合收獲機(jī)的作業(yè)參數(shù)，外形尺寸為5.12 m×2.52 m×2.72 m、割幅為W=2.20 m、喂入量為3.50 kg/s。因履帶式車輛底盤實(shí)際轉(zhuǎn)彎半徑受行進(jìn)速度和土壤特性等多個(gè)因素影響無法準(zhǔn)確量化，故對(duì)該機(jī)器分別取R=1.50、1.70、2.00、2.20 m 4個(gè)數(shù)值進(jìn)行算法仿真試驗(yàn)。試驗(yàn)中，將路徑規(guī)劃算法規(guī)劃出的路徑按照是否執(zhí)行收割操作分為作業(yè)路徑（邊行走、邊收割）和非作業(yè)路徑（只行走轉(zhuǎn)移、不收割），求出相應(yīng)路徑總長(zhǎng)度，算法耗時(shí)為主程序在進(jìn)行算法求解過程中所消耗的CPU時(shí)間。

3.1 環(huán)形路徑和混合路徑的對(duì)比仿真試驗(yàn)

對(duì)傳統(tǒng)環(huán)形路徑（即輪廓平行路徑）算法和混合路徑（即先輪廓平行路徑、后方向平行路徑）算法的求解結(jié)果進(jìn)行對(duì)比研究。在算法設(shè)計(jì)時(shí)雖以最小漏收面積為首要滿足指標(biāo)，但由于實(shí)際田塊邊界部分夾角太小，導(dǎo)致尖角處機(jī)器無法進(jìn)入，無法保證絕對(duì)不漏收，故對(duì)比時(shí)忽略一些細(xì)小漏收面積的影響。方向平行路徑調(diào)度時(shí)采用傳統(tǒng)的逐行調(diào)度策略。設(shè)定轉(zhuǎn)彎半徑為1.50和2.00 m兩個(gè)水平，采用環(huán)形路徑算法和混合路徑算法對(duì)4塊實(shí)際田塊進(jìn)行仿真試驗(yàn)，試驗(yàn)數(shù)據(jù)如表2所示，部分算例的完整路徑結(jié)果如圖8所示。其中作業(yè)路徑由輪廓平行路徑中的前行路徑部分和方向平行路徑組成，非作業(yè)路徑由輪廓平行路徑中的倒車路徑、方向平行路徑間銜接路徑、退出路徑3個(gè)部分組成。倒車次數(shù)優(yōu)化率γ1= (N1-N2)/N1×100%，其中N1、N2分別是環(huán)形路徑和混合路徑結(jié)果中的倒車次數(shù)。由表2可知，2種路徑算法對(duì)應(yīng)的路徑總長(zhǎng)度都隨田塊面積的增加而增大，同時(shí)也隨轉(zhuǎn)彎半徑的增加而增大。其中環(huán)形路徑的算法耗時(shí)為0.17～0.25 s，混合路徑的算法耗時(shí)為0.38～0.61 s。由圖8可知，環(huán)形路徑算法和混合路徑算法獲得的路徑線基本覆蓋整個(gè)田塊。

表2 不同田塊下環(huán)形路徑和混合路徑的對(duì)比測(cè)試結(jié)果 Table 2 Test results comparison of circular parallel path and mixture path for different fields

3.2 方向平行路徑調(diào)度優(yōu)化仿真試驗(yàn)

為進(jìn)一步優(yōu)化混合路徑總長(zhǎng)度，在混合路徑算法內(nèi)嵌入OR-Tools軟件套件內(nèi)的路由解算器，對(duì)方向平行路徑進(jìn)行調(diào)度優(yōu)化。非作業(yè)路徑的優(yōu)化率（ε，%）為OR-Tools調(diào)度后混合路徑中非作業(yè)路徑長(zhǎng)度（T2，m）相對(duì)于逐行調(diào)度后混合路徑中非作業(yè)路徑長(zhǎng)度（T1，m）的降低幅度，即ε=(T1－T2)/T1×100%，且進(jìn)一步對(duì)比倒車次數(shù)減少的幅度，即γ2=(N3-N4)/N3×100%。設(shè)定本次試驗(yàn)中油菜聯(lián)合收獲機(jī)的轉(zhuǎn)彎半徑為1.70 m和2.20 m，采用逐行調(diào)度策略和OR-Tools調(diào)度策略對(duì)4塊實(shí)際田塊進(jìn)行仿真試驗(yàn)，試驗(yàn)數(shù)據(jù)如表3所示，部分算例的完整路徑結(jié)果如圖9所示。由表3可知，2種調(diào)度策略下混合路徑總長(zhǎng)度與田塊面積、轉(zhuǎn)彎半徑呈正相關(guān)，其中逐行調(diào)度策略的算法耗時(shí)為0.38～0.61 s，OR-Tools調(diào)度策略的算法耗時(shí)為4.42～4.73 s。由圖9可知，混合路徑在采用OR-Tools調(diào)度策略后獲得的路徑線基本覆蓋整個(gè)田塊。

表3 不同調(diào)度策略下混合路徑規(guī)劃算法的測(cè)試結(jié)果 Table 3 Testing results of mixed path planning algorithms under different scheduling strategies

3.3 仿真試驗(yàn)結(jié)果分析

針對(duì)四邊形邊界田塊下的油菜收獲路徑規(guī)劃問題，提出了環(huán)形路徑算法與混合路徑算法，分別對(duì)4組不同面積、不同形狀的實(shí)際田塊進(jìn)行了仿真試驗(yàn)。由圖8和圖9可知，環(huán)形路徑算法和混合路徑算法獲得的路徑線基本覆蓋整個(gè)田塊，滿足最小漏收面積要求。由表2和表3中的算法耗時(shí)可知，2種路徑類型對(duì)應(yīng)的算法在加入調(diào)度優(yōu)化前，算法耗時(shí)隨田塊面積的增大而緩慢增加，但均小于1.00 s；加入調(diào)度優(yōu)化后，因TSP問題求解，算法耗時(shí)大幅增加，但也均小于5.00 s。這說明設(shè)計(jì)的算法穩(wěn)定、可靠、高效。

對(duì)比表2中環(huán)形路徑總長(zhǎng)度和混合路徑總長(zhǎng)度可知，當(dāng)轉(zhuǎn)彎半徑設(shè)定在1.50 m時(shí)，混合路徑作業(yè)總長(zhǎng)度較短，而當(dāng)轉(zhuǎn)彎半徑增大至2.00 m時(shí)，此時(shí)環(huán)形路徑作業(yè)總長(zhǎng)度反而要短一些。為了探究這一規(guī)律，對(duì)實(shí)際田塊2進(jìn)行仿真試驗(yàn)，設(shè)置轉(zhuǎn)彎半徑范圍為1.40～2.30 m，間隔0.10 m。2種路徑算法下路徑總長(zhǎng)度結(jié)果如圖10所示，當(dāng)轉(zhuǎn)彎半徑在1.40～1.70 m時(shí)，混合路徑總長(zhǎng)度較短，當(dāng)轉(zhuǎn)彎半徑在1.80～2.30 m時(shí)，環(huán)形路徑總長(zhǎng)度更短。

由表2中作業(yè)路徑長(zhǎng)度和非作業(yè)路徑長(zhǎng)度可知，2種路徑下轉(zhuǎn)彎半徑增大對(duì)作業(yè)路徑長(zhǎng)度影響不大，主要影響非作業(yè)路徑長(zhǎng)度，其中混合路徑的非作業(yè)路徑長(zhǎng)度增幅較大，主要原因是混合路徑中方向平行銜接路徑的長(zhǎng)度受轉(zhuǎn)彎半徑變化影響較大。此外，從表2倒車次數(shù)可知，相比于環(huán)形路徑，采用混合路徑可減少36.36%～40.00%的倒車次數(shù)，進(jìn)而減少了農(nóng)機(jī)作業(yè)過程所消耗的時(shí)間。

由表3可知，對(duì)混合路徑進(jìn)行調(diào)度優(yōu)化后，非作業(yè)路徑長(zhǎng)度優(yōu)化效果在7.20%～20.23%之間。對(duì)比表3中不同轉(zhuǎn)彎半徑下的非作業(yè)路徑長(zhǎng)度，可以發(fā)現(xiàn)其優(yōu)化幅度與轉(zhuǎn)彎半徑的大小相關(guān)，當(dāng)轉(zhuǎn)彎半徑越大時(shí)，調(diào)度優(yōu)化的效果越明顯。同時(shí)對(duì)比圖9中田塊的規(guī)整程度可以發(fā)現(xiàn)，當(dāng)田塊的形狀越接近矩形，以及方向平行路徑需要的銜接路徑（轉(zhuǎn)彎）次數(shù)越多時(shí)，調(diào)度優(yōu)化效果就越明顯。因調(diào)度優(yōu)化后方向平行銜接路徑更多的采用U型轉(zhuǎn)彎，相比未采用調(diào)度優(yōu)化的混合路徑，倒車次數(shù)減少了33.33%～60.87%，能進(jìn)一步節(jié)省作業(yè)時(shí)間。

4 結(jié) 論

1）針對(duì)四邊形田塊邊界類型條件下的油菜聯(lián)合收獲作業(yè)路徑規(guī)劃問題，在分析油菜聯(lián)合收獲作業(yè)特點(diǎn)的基礎(chǔ)上，為單側(cè)豎割刀的油菜聯(lián)合收獲機(jī)，提出了全覆蓋作業(yè)環(huán)形路徑規(guī)劃算法；為雙側(cè)豎割刀的油菜聯(lián)合收獲機(jī)，提出了全覆蓋作業(yè)混合路徑規(guī)劃算法。

2）對(duì)4組實(shí)際田塊進(jìn)行仿真測(cè)試結(jié)果表明，本研究所設(shè)計(jì)的兩種收獲作業(yè)路徑算法滿足實(shí)際收獲過程中的各種要求。在不考慮調(diào)度優(yōu)化的情況下，環(huán)形路徑的算法耗時(shí)為0.17～0.25 s，混合路徑的算法耗時(shí)為0.38～0.61 s，當(dāng)轉(zhuǎn)彎半徑較小時(shí)，混合路徑總長(zhǎng)度較短，當(dāng)轉(zhuǎn)彎半徑較大時(shí)，環(huán)形路徑總長(zhǎng)度較短，在算法輸入?yún)?shù)相同的條件下，混合路徑相比于環(huán)形路徑能減少36.36%～40.00%的倒車次數(shù)。在對(duì)混合路徑算法進(jìn)行調(diào)度優(yōu)化后，其非作業(yè)路徑長(zhǎng)度減少了7.20%～20.23%，倒車次數(shù)進(jìn)一步減少了33.33%～60.87%，相較于環(huán)形路徑算法更優(yōu)，此時(shí)算法耗時(shí)在4.42～4.73 s，滿足油菜聯(lián)合收獲機(jī)在收獲作業(yè)準(zhǔn)備過程中快速規(guī)劃路徑的需要。

3）本研究為長(zhǎng)江中下游區(qū)域稻油輪作無人農(nóng)場(chǎng)中油菜無人化聯(lián)合收獲提供了作業(yè)路徑規(guī)劃方面的理論及技術(shù)支撐。其中多邊形偏置、輪廓平行路徑的環(huán)上及環(huán)間銜接處理、方向平行路徑調(diào)度優(yōu)化時(shí)距離矩陣等計(jì)算方法同樣適用于其他非四邊形的凸多邊形邊界田塊，但對(duì)于凹多邊形邊界田塊，則還需要進(jìn)一步深入研究。此外，算法中假設(shè)車輛轉(zhuǎn)彎半徑為某一定值，屬于靜態(tài)規(guī)劃，因此還需要進(jìn)一步研究動(dòng)態(tài)轉(zhuǎn)彎特性對(duì)路徑規(guī)劃結(jié)果的影響。