張 帆，羅錫文，張智剛，何 杰，張聞宇

（華南農業(yè)大學工程學院，南方農業(yè)機械與裝備關鍵技術省部共建教育部重點實驗室，廣州 510642）

0 引言

傳統(tǒng)農機跨區(qū)作業(yè)存在組織效率低、勞動生產率不高等問題，造成資源浪費[1]。農機作業(yè)時效強，特別是在農忙時節(jié)，要求農機在規(guī)定時間內完成作業(yè)任務，以確保糧食歸倉和及時播種，提高農機作業(yè)效率已經(jīng)成為農業(yè)生產的首要問題。農機導航技術與物聯(lián)網(wǎng)技術的興起，為農機規(guī)?；{度和農場規(guī)?；鳂I(yè)的實現(xiàn)提供了技術支撐，加速了傳統(tǒng)農機作業(yè)邁向智能農機作業(yè)的進程[2]，也為無人農場的建設運營提供理論依據(jù)[3-4]。

在農業(yè)生產過程中，隨著對自動導航作業(yè)需求的不斷增加，實現(xiàn)多臺同種或異種作業(yè)農機之間協(xié)同作業(yè)已成為農機導航研究的重點[5]。對于單作業(yè)任務而言，國內外對農機的協(xié)同作業(yè)的研究重點主要集中收獲農機與運輸車輛之間的配合作業(yè)上[6]，如Lida等[7]和Noguchi等[8]分別研究了農機車輛自動跟隨作業(yè)與協(xié)同導航作業(yè)操作的問題。Zhang等[9]開發(fā)了一套跟隨式農機主從導航作業(yè)系統(tǒng)，實現(xiàn)了從機對主機的輔助運輸和加油等作業(yè)。針對多作業(yè)任務的需求，通常要根據(jù)機器、人員以及作業(yè)任務等信息，設計優(yōu)化算法與決策策略，科學地對機器和人員進行運營調配，在保證所有作業(yè)任務及時完成的前提下，實現(xiàn)作業(yè)時間最短或作業(yè)成本最小[10-11]。

國內外許多學者對多農機執(zhí)行多種作業(yè)任務的資源配置問題進行了研究。Jena等[12]利用混合整數(shù)規(guī)劃的方法確定甘蔗收獲機的作業(yè)路徑；Sethanan等[13]以甘蔗收獲機作業(yè)距離最小化和甘蔗收獲產量最大化為目標，提出了改進粒子群優(yōu)化算法（MO-GLNPSO）解決甘蔗收獲機路徑規(guī)劃問題；Pitakaso等[14]提出了一種基于時間窗的聯(lián)合收獲機分配與路由問題的領域搜索方法，在聯(lián)合收獲機在任務共享的情況下，最大限度地提高收獲機的服務面積；Cerdeira等[15]研究了一個具有附加集群約束、時間窗和城市處理時間約束的旅行商問題（Traveling Salesman Problem，TSP）的變換模型[16]，并采用禁忌搜索和模擬退火思想相結合的算法對一個農機合作社幾個聯(lián)合收獲機的作業(yè)路徑進行了優(yōu)化。國內方面，曹如月等和張小花等類比旅行商問題[17-18]，采用蟻群算法求解多機協(xié)同作業(yè)任務規(guī)劃問題，但未將農機在田間作業(yè)的約束進行綜合考慮；He等[19]提出了一種基于禁忌搜索和遺傳算法算子的混合算法以確定小麥的最優(yōu)收獲時間，達到減少收獲時間的目的；王雪陽等[20]采用改進遺傳算法對跨區(qū)域作業(yè)的農機調度問題進行了研究；Zhou等[21]采用粒子群算法和遺傳算法相結合的方法求解了農機調度服務問題。部分研究采用啟發(fā)式算法，如吳才聰?shù)萚22]針對單一農機的作業(yè)問題建立了時空調度模型，并以動態(tài)規(guī)劃的方式進行基于時間窗的分步求解，最終完成整個模型的調度；Zhang等[23-24]針對農機跨區(qū)緊急作業(yè)調度問題進行了模型設計，并采用基于距離最近優(yōu)先的多機多任務緊急調配和基于貢獻度最大優(yōu)先的多機多任務緊急調配的啟發(fā)算法進行了求解，完成了農機的調度任務。

上述研究對多農機在特定時間內完成同一種作業(yè)任務提供了很好的解決方案，但是對農機作業(yè)過程中多種任務連續(xù)作業(yè)的問題，如需連續(xù)進行耕整、播種和施肥等作業(yè)，無法提供科學合理的決策服務。本文主要研究多農機多任務的連續(xù)調度問題，綜合考慮了調度損耗與作業(yè)損耗，通過采集的任務與農機的作業(yè)參數(shù)，建立農機調度模型，以作業(yè)時間最短為優(yōu)化目標，利用改進的多父輩遺傳算法進行農機作業(yè)任務序列規(guī)劃，為解決多任務多農機的調度問題提供理論依據(jù)，也為開發(fā)基于無人農場智能農機管控平臺提供決策參考。

1 多農機多任務作業(yè)調度問題

1.1 問題描述

隨著3S技術[25]與農機自動駕駛技術[26]的不斷發(fā)展，智能農機可通過移動互聯(lián)網(wǎng)與云平臺進行實時通訊，將農機的實時位置、速度、作業(yè)等信息上傳至云端，這為農機的精準調度提供了數(shù)據(jù)參考與技術支撐[27-28]。農機作業(yè)具有很強的時效性，特別是在農忙時節(jié)，需要在較短的時間內完成農田的耕整、播種、施肥等作業(yè)操作，而進行每種作業(yè)的農機具也各不相同，這就要求在有限的作業(yè)期限內做出科學的農機作業(yè)調度決策，在保證作業(yè)任務及時完成的前提下，實現(xiàn)作業(yè)成本最小化[29-30]。

在農機調度中，單機單任務的農機作業(yè)序列規(guī)劃問題可類比成TSP問題進行分析，對農田空間分布和農機作業(yè)時間進行綜合考慮；而對于多機多任務的農機作業(yè)序列規(guī)劃問題，可描述為：m臺能執(zhí)行不同作業(yè)任務的農機需要在n塊農田上進行特定作業(yè)，指定每塊農田特定的作業(yè)任務及順序、每塊農田作業(yè)參數(shù)及每臺農機的參數(shù)，安排每臺處于不同位置的農機在不同田塊的作業(yè)任務和作業(yè)順序，使整個農場的生產作業(yè)耗時達到最短。此外，本研究還綜合考慮了農機從當前位置到目標田塊的遷移時間，以及農機在達到目的地后作業(yè)準備時間。

1.2 數(shù)學規(guī)劃模型

根據(jù)多機多任務調度問題的描述，對該問題的抽象模型定義如下：

1）農田集合F={F1,F2,…,Fm}，以Fi代表第i塊農田，其屬性描述為Fi={LocFi,SFi}，其中LocFi和SFi分別表示農田Fi的入口位置和面積，

2）農機集合M={M1,M2,…,Mr}，以Mj代表第j臺農機，其屬性描述為Mj={LocMj, RSj, WSj，ReadyTj}，其中，LocMj表示農機Mj的當前位置，RSj表示農機Mj地塊轉移過程中的平均行駛速度，WSj表示農機Mj的平均作業(yè)速度,ReadyTj表示農機作業(yè)前準備時間，且有 [1,]jr∈ ；

3）農機集群MT={MT1,MT2,…,MTn}，以MTk代表第k種類型農機，表示為MTk={Mk1,Mk2,…,Mka}，a為第k種類型的農機總數(shù)，且有

4）作業(yè)任務序列的集合Task={Task1,Task2, …,Taskm}，Taski代表農田Fi的作業(yè)序列，并表示為Taski={Taski1,Taski2,…,Taskin}，Taskik代表在農田Fi上進行第k種作業(yè)，且對應作業(yè)的農機類型為MTk，[1,]kn∈ 。

此外，農機調度還需滿足下述條件：

1）每臺機器只能同時在某一塊地上進行作業(yè)；

2）在農機數(shù)量充足的條件且農田面積大于0.3 hm2時，每塊地可安排多臺同種作業(yè)任務的農機進行作業(yè)；

3）為避免不同類型農機因作業(yè)任務不同而產生干擾，單塊農田只進行同一種作業(yè)類型的作業(yè)，而需要多機協(xié)同完成同一作業(yè)任務的情況（如收獲機與運糧車的協(xié)同收獲作業(yè)），將其處理成同一類型作業(yè)任務；

4）每塊農田不同任務的作業(yè)順序固定，須滿足專門的作業(yè)規(guī)程，且每塊農田的任務必須被執(zhí)行。

上述調度問題在考慮農田作業(yè)任務要求的同時，還考慮農田與農機的相對位置關系，以最近距離農機優(yōu)先作業(yè)為原則，求出每塊農田上農機的作業(yè)順序集Si={Si1,Si2,…,Sir}，并以Sij表示農機Mj到農田Fi的調配方案，選取總調度時間最小為優(yōu)化目標，調度模型表示如下：

調度目標：

約束條件：

式中T為任務總時間，h；TiF為第i塊農田的作業(yè)總時間，h，其中i=1, 2,…,m；transTik為農機集群MTk到農田Fi的轉移時間，h，其取值為農機集群MTk中每臺農機出發(fā)去農田Fi的轉移過程中所耗時間的最大值；readyTik為農機群MTk中每臺農機到達農田Fi作業(yè)前的準備時間，h；workTik為農機集群MTk在農田Fi的作業(yè)總時間，h；SiF為農田Fi的面積大小，hm2；Dij為農機Mj當前位置到農田Fi的距離，km，文中采用農機Mj到農田Fi兩點之間的距離進行簡要計算；Ek為第k種類型農機的工作效率，即每小時的作業(yè)面積，hm2/h；zik表示農機群MTk是否在田塊Fi進行作業(yè)，其中k與任務Taskik相對應，當農田中Fi中有任務需要被執(zhí)行的任務k時，zik取值為1，否則為0；tij表示農機Mj是否到農田Fi進行作業(yè)，若該農機的田間轉移時間大于當前已經(jīng)到達農田Fi的農機集群MTk完成農田任務總時間，則當前農機不參與該地塊的作業(yè)，此時tij置于0，否則為1；Yi為農田Fi的的任務數(shù)量。式（5）表示農田Fi的每個任務都允許有多臺農機參與，且每個任務必須被執(zhí)行。

2 IMPGA算法原理

基于上述數(shù)學模型，本文提出了基于時間窗的改進多父輩遺傳算法求解多任務多農機調度問題，算法流程如圖1所示。

具體算法步驟如下：

1）初始化問題參數(shù)集。錄入農機、農田、作業(yè)任務等基礎信息，同時設置種群規(guī)模數(shù)PopulationNumber和迭代次數(shù)Iteration；

2）編碼。基于農田序號的編碼并初始化種群。

對于m塊農田有r種作業(yè)任務情況下的作業(yè)調度問題，每條染色體的基因數(shù)量為個（Ni表示農田Fi的任務個數(shù)），使用農田編號進行編碼，農田編號在染色體中出現(xiàn)的頻次代表農田作業(yè)任務號，第x次出現(xiàn)的作業(yè)序號代表該農田的第x個作業(yè)任務。如在一個2×2的調度問題中，農田集合F={F1,F2}，對應的任務集合Task={(1,2)，(2,3)}，則隨機分布的編碼共有6種類型，如[1 2 1 2]或[1 1 2 2]等。

3）適應度函數(shù)計算。以作業(yè)時間最短為優(yōu)化目標，則遺傳算法的適應度函數(shù)為

式中f為染色體適應度，依據(jù)公式（1）～（5）對每個染色體的適應度值進行計算。

4）個體選擇。由于種群中優(yōu)秀的父代個體中的基因質量更好，為了保證優(yōu)秀個體基因的遺傳，加速尋優(yōu)結果的收斂速度，按適應度值將種群劃分成優(yōu)秀和良好2種種群，其中優(yōu)秀種群占總群體規(guī)模的1/3，良好種群占2/3，從優(yōu)秀群體里隨機選取個體Parent1，從良好群體隨機選取個體Parent2和Parent3。

5）變異。算法設計可調整的變異概率，當在進行多次迭代之后，如果種群中最優(yōu)染色體的適應度沒有發(fā)生變化，則調整變異概率，若發(fā)生進化，則截至當前未進化的代數(shù)index置為0并重新開始累積，調整的變異概率用函數(shù)表示為：

式中pm為當前變異概率，%；pm0為初始變異概率，%；index為截至當前未進化的代數(shù)。

6）多父輩POX交叉。本文采用黃明等[31]提出的多父輩POX交叉方式，用優(yōu)秀個體Parent1分別與良好個體Parent2和Parent3進行交叉，產生后代Child1和Child2，以3×3的調度問題為例來說明交叉過程，如圖2所示。首先假定有3個選擇的染色體序列Parent1、Parent2和Parent3，且有2個非空互余的基因子集Gene1 {1，2}和Jene2{3}；分別將Parent1中Gene1和Gene2進行分離，并將分離的基因原位置于O，O表示該位置暫時為空，再將Parent2和Parent3進行處理，分別保留Gene2和Gene1；最后分別將Parent1中保留的Gene1和Parent2中保留的Gene2進行交叉，即按從前到后的順序將Parent1中屬于Gene1的基因依次放入Parent2中，生成Child1，同理將Parent1中屬于Gene2的基因依次放入Parent3中，生成Child2。至此，多父輩的POX交叉的過程結束。

7）迭代進化。判斷是否滿足算法結束條件，若不滿足，則返回至步驟3）迭代；若滿足終止條件，則算法終止，輸出最優(yōu)結果，并將最優(yōu)結果進行解碼。

解碼是步驟2）的編碼逆變換過程，用實例來描述解碼過程如下：在一個2×2的調度問題中，農田集合F={F1,F2}，對應的任務集合Task={(1,2)，(2,3)}，農機集合為MT={MT1,MT2,MT3}，其中Task中的1代表平地作業(yè)，使用農機群MT1進行作業(yè)，同理，2和3分別代表播種作業(yè)和施肥作業(yè)，相應地使用MT2和MT3進行作業(yè)，當染色體編號為[1 2 1 2]時，表示的農田作業(yè)次序為F1-F2-F1-F2，則農機調度流程為MT1-MT2-MT2-MT3。在確定農機集群的調度流程后，還需對MTk進行解碼。對于任意序列MTk的解碼可描述如下：考慮農機數(shù)量充足的情況，對處于不同位置的農機，當選擇農機集群MTk去同一目標農田Fi進行作業(yè)任務Tk時，本文以基于最短路徑的貪婪算法選擇作業(yè)的農機臺數(shù)，具體過程為：①在農機集合M中篩選農機類型為k的農機集合MTk，分別計算農機Mki到農田Fi之間距離，并按增序進行排列；②以農田Fi的面積SFi為調度約束，依據(jù)公式（3）～（5）選擇可作業(yè)農機，判斷某臺農機能否加入該農田作業(yè)的準則是：若該農機的田間轉移時間大于當前已加入集群作業(yè)農機完成農田任務總時間，則當前農機不參與該地塊的作業(yè)。

3 IMPGA算法驗證

3.1 試驗數(shù)據(jù)

本文的農田數(shù)據(jù)采自新疆塔城地區(qū)，依據(jù)實際作業(yè)環(huán)境設置仿真作業(yè)任務，以驗證算法的性能和穩(wěn)定性。算法的運行環(huán)境為：處理器Inter(R)i5-7500 3.4GHz，內存8G，操作系統(tǒng)Windows10，編程語言Java。表1為部分作業(yè)農田的基本信息，主要包括農田面積、農田入口經(jīng)緯度與作業(yè)類型。表2為可用農機裝備的基本信息，如農機作業(yè)效率和路面行駛速度，此外包括每臺農機的初始位置經(jīng)緯度及準備時間，準備時間即農機達到農田后需要進行作業(yè)準備的時間，如作業(yè)人員就位、裝料、加油、機器作業(yè)參數(shù)調整等作業(yè)前準備所需消耗的時間。

表1 部分作業(yè)農田的基本信息 Table 1 Basic information of part of farmland

表2 可用農機的基本信息 Table 2 Basic information of available agricultural machine

3.2 結果與分析

對上述農田的作業(yè)任務采用改進的遺傳算法進行仿真調度試驗，選取種群規(guī)模為300，進化500代，初始變異概率0.05。完成每種作業(yè)農機只有1臺時，選取農田數(shù)量為6，此時作業(yè)任務數(shù)量為20個，使用改進遺傳算法進行運算得出最優(yōu)調度方案，再通過Matlab生成甘特圖，如圖3a所示，其中甘特圖白色部分代表農機在田塊之間的轉移時間與準備時間之和，其他顏色代表了農機在不同農田的作業(yè)時間，該調度方案的總完工時間為85.42 h。同理，當執(zhí)行每種作業(yè)任務的農機數(shù)量為多臺時，調度結果如圖3b所示，該調度方案的總完工時間為38.45 h。

為了驗證改進遺傳算法的有效性和穩(wěn)定性，首先考慮執(zhí)行每種作業(yè)任務的只有1臺時（以下簡稱單農機作業(yè)），選取農田數(shù)量為5、10、15和20塊的作業(yè)任務，分別使用IMPGA和GA進行調配運算10次，調度結果如表3所示。由表3可知，當執(zhí)行每種任務的農機數(shù)量為1臺時，改進的遺傳算法的最優(yōu)解、平均解均優(yōu)于標準遺傳算法，其調度時間的最優(yōu)解和平均解分別縮短2.24%和3.16%，且改進遺傳算法的平均標準偏差小，證明了改進遺傳算法的魯棒性好于標準遺傳算法；為驗證IMPGA的收斂性，對比最優(yōu)解出現(xiàn)的迭代次數(shù)可以發(fā)現(xiàn)，除農田數(shù)量為15時IMPGA出現(xiàn)的次數(shù)大于IG之外，其余農田數(shù)量相同的條件下IMPGA均能更早找到最優(yōu)解，而對比平均值發(fā)現(xiàn)，GA最優(yōu)解平均出現(xiàn)的迭代次數(shù)為298.5，而IMPGA為255.8，IMPGA比GA收斂更快。此外，通過對比算法運行時間可知，2種算法的運行時間均隨著任務數(shù)量的增加而增加，改進遺傳算法的平均運行時間比標準遺傳算法的平均運行時間長2.36 s。

表3 單農機作業(yè)下IMPGA與GA的調度結果對比 Table 3 Comparison of results between IMPGA and GA under single number machinery

由表4可知，當執(zhí)行每種作業(yè)任務的農機多于1臺時，作業(yè)任務完工總時間小于農機數(shù)量為1臺的結果。在農機數(shù)量相同時，改進遺傳算法的調配結果仍優(yōu)于標準遺傳算法的結果：在農田數(shù)量為5時，2種算法均能求得最優(yōu)解；在農田數(shù)量為10時，使用改進遺傳算法求取調度的最優(yōu)時間和平均時間分別縮短3.77%和3.56%；農田數(shù)量為15時，最優(yōu)時間和平均時間分別縮短1.63%和3.76%；農田數(shù)量為20時，最優(yōu)時間和平均時間分別縮短4.46%和3.47%。此外，隨著農田數(shù)量增多時，算法運行時間增加，且改進遺傳算法的平均運行時間比標準遺傳算法的運行時間長8.92 s。

表4 多農機作業(yè)的IMPGA與GA調度結果對比 Table 4 Comparison of results between IMPGA and GA under multi-type machinery

總之，本文改進的遺傳算法在總體上優(yōu)于標準遺傳算法，其調度的最優(yōu)時間和平均時間分別能平均縮短2.47%和2.70%，能滿足農機作業(yè)調度的任務需求。

4 結 論

考慮實際農田作業(yè)情況，本文分析了針對連續(xù)作業(yè)任務的農機作業(yè)任務規(guī)劃問題，在農機隨機分布的情況下，以作業(yè)時間最短為優(yōu)化目標，建立了基于農業(yè)生產中多機執(zhí)行多任務的調度模型。在考慮農機田間轉移時間和作業(yè)準備時間的前提下，采用改進遺傳優(yōu)化算法對多機多任務的農田作業(yè)問題進行調配，通過與標準遺傳算法相對比，結果表明：改進的多父輩遺傳算法能有效解決多任務農機的作業(yè)分配問題，在迭代次數(shù)相同的情況下，盡管IMPGA比GA運行時間長8.92 s，但IMPGA求解調度方案的最優(yōu)時間和平均時間分別能縮短2.47%和2.70%，節(jié)約了時間成本，滿足農機運維和無人農場生產運營實際作業(yè)的調度需求。

后續(xù)研究將考慮多臺農機同時作業(yè)，某臺農機發(fā)生故障時如何對農機重新進行作業(yè)分配的問題；此外，隨著農機自動駕駛技術和物聯(lián)網(wǎng)技術的不斷發(fā)展，研究內容還將與智能無人農機管控平臺集成，逐步實現(xiàn)無人農場農機的智能化任務調度、自動化路徑規(guī)劃以及生產作業(yè)的全程管控。