同種農(nóng)機(jī)機(jī)群動(dòng)態(tài)作業(yè)任務(wù)分配方法

王 猛，趙 博，劉陽春，偉利國，汪鳳珠，方憲法

（中國農(nóng)業(yè)機(jī)械化科學(xué)研究院土壤植物機(jī)器系統(tǒng)技術(shù)國家重點(diǎn)實(shí)驗(yàn)室，北京 100083）

0 引言

中國是農(nóng)業(yè)大國，農(nóng)業(yè)機(jī)械化可極大提高農(nóng)業(yè)生產(chǎn)效率、減輕農(nóng)民體力勞動(dòng)。隨著農(nóng)機(jī)合作社和農(nóng)場作業(yè)模式的快速發(fā)展，農(nóng)機(jī)和土地都呈現(xiàn)集中的趨勢，如何更有效地規(guī)劃機(jī)群作業(yè)，提高作業(yè)效率，對有作業(yè)窗口期要求的農(nóng)業(yè)生產(chǎn)具有重大作用。

動(dòng)態(tài)任務(wù)分配是機(jī)群作業(yè)領(lǐng)域的一個(gè)重要研究內(nèi)容，動(dòng)態(tài)任務(wù)分配指機(jī)群作業(yè)過程中，面對導(dǎo)致機(jī)群無法繼續(xù)執(zhí)行原有作業(yè)計(jì)劃的意外情況時(shí)，根據(jù)任務(wù)執(zhí)行進(jìn)度和機(jī)群位置，對作業(yè)任務(wù)計(jì)劃進(jìn)行相應(yīng)的調(diào)整使得機(jī)群能夠繼續(xù)執(zhí)行并完成新的任務(wù)計(jì)劃。動(dòng)態(tài)任務(wù)分配方法在機(jī)器人搜索、無人機(jī)作戰(zhàn)、水下機(jī)器人搜索和無人機(jī)搜索等領(lǐng)域有了較深入的研究和發(fā)展[1-5]。研究人員對靜態(tài)任務(wù)分配技術(shù)研究較多，研究方法包括基于作業(yè)經(jīng)驗(yàn)和效率的任務(wù)分配[6-8]、基于聚類的任務(wù)分配[9]、基于博弈論的任務(wù)分配[10]和基于啟發(fā)式算法的任務(wù)分配[11-16]等，對動(dòng)態(tài)任務(wù)分配研究較少，主要采用合同網(wǎng)算法，動(dòng)態(tài)任務(wù)分配比靜態(tài)任務(wù)分配更加復(fù)雜[17-20]。農(nóng)機(jī)作業(yè)領(lǐng)域的相關(guān)研究有任務(wù)規(guī)劃和調(diào)度等。其中任務(wù)規(guī)劃指規(guī)劃農(nóng)機(jī)執(zhí)行任務(wù)的先后順序和田塊間的路徑，曹如月等[21]采用蟻群算法解決機(jī)群作業(yè)任務(wù)規(guī)劃，使農(nóng)機(jī)行駛的距離最短；Jensen等[22]研究了一臺(tái)運(yùn)糧車對多臺(tái)收割機(jī)運(yùn)糧的田塊內(nèi)和田間的路徑規(guī)劃方法，使農(nóng)機(jī)作業(yè)代價(jià)最??；姚竟發(fā)等[23]提出聯(lián)合收割機(jī)多機(jī)無沖突協(xié)同作業(yè)路徑優(yōu)化算法，縮短了矩形農(nóng)田和梯形農(nóng)田農(nóng)機(jī)作業(yè)時(shí)間。農(nóng)機(jī)調(diào)度是對一系列作業(yè)點(diǎn)選擇合適的行車路徑，讓農(nóng)機(jī)有序地通過它們，在滿足作業(yè)點(diǎn)的時(shí)間窗和所需農(nóng)機(jī)數(shù)約束條件下，達(dá)到路程最小或收益最高[24-28]。隨著我國農(nóng)機(jī)合作社和農(nóng)場作業(yè)模式的快速發(fā)展和農(nóng)機(jī)管控平臺(tái)的開發(fā)[28]，農(nóng)機(jī)和土地趨于集中且參數(shù)可知趨勢，如何在合作社或農(nóng)場土地范圍內(nèi)對多臺(tái)農(nóng)機(jī)進(jìn)行有效的任務(wù)分配，并在有突發(fā)狀況條件下進(jìn)行合理的任務(wù)再分配對具有強(qiáng)“農(nóng)時(shí)”性的農(nóng)業(yè)生成具有重要意義。

本研究以同種作業(yè)農(nóng)機(jī)為研究對象，以農(nóng)機(jī)合作社或農(nóng)場作業(yè)模式為作業(yè)場景，綜合考慮機(jī)群中作業(yè)時(shí)間最長的農(nóng)機(jī)作業(yè)時(shí)間、農(nóng)機(jī)機(jī)群的油耗和路上的路程建立機(jī)群代價(jià)，以代價(jià)最小作為優(yōu)化目標(biāo)，構(gòu)建基于合同網(wǎng)算法的機(jī)群動(dòng)態(tài)任務(wù)分配招投標(biāo)流程和投標(biāo)代價(jià)函數(shù)，針對農(nóng)機(jī)作業(yè)特點(diǎn)優(yōu)化合同網(wǎng)算法以降低機(jī)群作業(yè)代價(jià)、得到最優(yōu)動(dòng)態(tài)任務(wù)分配結(jié)果。

1 機(jī)群系統(tǒng)體系結(jié)構(gòu)

根據(jù)農(nóng)機(jī)機(jī)群動(dòng)態(tài)任務(wù)分配特點(diǎn)設(shè)計(jì)了農(nóng)機(jī)機(jī)群作業(yè)的體系結(jié)構(gòu)，主要包括農(nóng)機(jī)、服務(wù)器和客戶端三個(gè)部分。其中農(nóng)機(jī)安裝車載計(jì)算機(jī)、北斗定位模塊和無線自組網(wǎng)模塊等，可實(shí)現(xiàn)自身定位和與其他農(nóng)機(jī)通信；服務(wù)器中儲(chǔ)存田塊信息和農(nóng)機(jī)信息并且具有計(jì)算功能；客戶端可以選擇和下發(fā)任務(wù)到指定作業(yè)機(jī)群。其結(jié)構(gòu)如圖1所示。

2 農(nóng)機(jī)機(jī)群代價(jià)數(shù)學(xué)模型

2.1 基本假設(shè)

農(nóng)機(jī)機(jī)群作業(yè)過程中，作業(yè)情況往往過于復(fù)雜，為突出動(dòng)態(tài)任務(wù)分配問題，簡化其他次要問題，做出農(nóng)機(jī)作業(yè)的基本假設(shè)。

1）作業(yè)機(jī)群為具有高精度定位與導(dǎo)航功能的同種作業(yè)農(nóng)機(jī)。

2）任務(wù)田塊數(shù)量大于作業(yè)農(nóng)機(jī)數(shù)量。

3）每個(gè)任務(wù)田塊只有1臺(tái)農(nóng)機(jī)作業(yè)，同一臺(tái)農(nóng)機(jī)可以在連續(xù)多個(gè)任務(wù)田塊作業(yè)。

4）不考慮其他補(bǔ)給或配合農(nóng)機(jī)的調(diào)配。

5）任務(wù)田塊沒有嚴(yán)格的作業(yè)時(shí)間窗口要求。

6）農(nóng)機(jī)機(jī)群從車庫出發(fā)，完成全部任務(wù)后返回車庫。

7）機(jī)群的作業(yè)時(shí)間為機(jī)群中用時(shí)最長農(nóng)機(jī)的作業(yè)時(shí)間。

2.2 目標(biāo)函數(shù)

假設(shè)作業(yè)的農(nóng)機(jī)數(shù)量為m，任務(wù)田塊的數(shù)量為n，用A={a1,a2,…,am}表示農(nóng)機(jī)集合，T={T1,T2,…,Tn}表示任務(wù)田塊集合，任務(wù)分配是指將任務(wù)田塊集合T按一定的作業(yè)順序分配給農(nóng)機(jī)集合A。

農(nóng)機(jī)作業(yè)過程中，對于農(nóng)資、能源補(bǔ)給類車輛常以農(nóng)機(jī)的路程為代價(jià)；對于需要在田間作業(yè)的農(nóng)機(jī)常以農(nóng)機(jī)作業(yè)的總時(shí)間為代價(jià)。本文考慮機(jī)群的作業(yè)時(shí)間、油耗和路程建立目標(biāo)函數(shù)：

式中f為機(jī)群代價(jià)函數(shù)，α為系數(shù)向量，α=[1,0,0]表示以機(jī)群作業(yè)時(shí)間為代價(jià)，α=[0,1,0]表示以機(jī)群作業(yè)油耗為代價(jià)，α=[0,0,1]表示以機(jī)群到達(dá)作業(yè)地塊的路程為代價(jià)；ti為農(nóng)機(jī)ai的作業(yè)時(shí)間，h；ci為農(nóng)機(jī)ai的油耗，L；si為農(nóng)機(jī)ai路上的路程，km。

當(dāng)系數(shù)確定的情況下，當(dāng)代價(jià)函數(shù)最小時(shí)，對應(yīng)的任務(wù)分配方案即為該確定系數(shù)下多機(jī)協(xié)同最優(yōu)分配方案。

2.2.1 田間路徑規(guī)劃

參考文獻(xiàn)[29-31]，以農(nóng)田最長邊為作業(yè)方向可有效提高作業(yè)效率，降低作業(yè)代價(jià)；滿足半圓形調(diào)頭時(shí)采用半圓形調(diào)頭，不滿足半圓形調(diào)頭時(shí)采用弓形調(diào)頭可提高調(diào)頭效率，本文以不滿足半圓形調(diào)頭情況為例進(jìn)行研究。

地頭轉(zhuǎn)彎區(qū)域分為種植農(nóng)作物和不種植農(nóng)作物2種情況，本文以種植農(nóng)作物為例設(shè)置作業(yè)模式，根據(jù)文獻(xiàn)[32]，為實(shí)現(xiàn)作業(yè)區(qū)域的全覆蓋，采用直行與繞行相結(jié)合的方式進(jìn)行路徑規(guī)劃，如圖2所示。

以圖2所示的帶斜邊的多邊形田塊為例，根據(jù)文獻(xiàn)[32]，弓形路徑調(diào)頭中地頭最小轉(zhuǎn)彎地帶寬度E∏為

式中R為農(nóng)機(jī)的最小轉(zhuǎn)彎半徑，m；W為作業(yè)幅寬，m；Lk為農(nóng)機(jī)機(jī)組中心至最遠(yuǎn)農(nóng)具作業(yè)部件的距離，m。

為使繞行路徑可以滿若干幅寬作業(yè)，令地頭轉(zhuǎn)彎地帶寬度為農(nóng)機(jī)幅寬的整數(shù)倍，則地頭轉(zhuǎn)彎寬度E為

其中

弓形路徑調(diào)頭過程中，根據(jù)幾何關(guān)系，農(nóng)機(jī)轉(zhuǎn)彎跳過的最小路徑smin為

根據(jù)文獻(xiàn)[30，33]，采用弓形調(diào)頭路徑時(shí)實(shí)現(xiàn)作業(yè)區(qū)域全覆蓋的的最小路徑數(shù)量Bmin為

作業(yè)過程中，當(dāng)田塊剩余寬度小于農(nóng)機(jī)作業(yè)幅寬時(shí)，收獲機(jī)械可直接進(jìn)行作業(yè)；播種機(jī)械等為避免重復(fù)作業(yè)可采用小型機(jī)械補(bǔ)耕或調(diào)整相鄰作業(yè)行出種行數(shù)的方式，本研究中田塊數(shù)量較多且分散，采用后種方式。農(nóng)機(jī)在田塊中總的縱向路徑數(shù)量N為田塊垂直于作業(yè)路徑的寬度與作業(yè)幅寬的比值，則N為

式中bT為任務(wù)田塊垂直于作業(yè)路徑的寬度，m。

當(dāng)(N-2kE)≥Bmin時(shí)，滿足弓形調(diào)頭要求，將農(nóng)田劃分為多個(gè)標(biāo)準(zhǔn)區(qū)塊和1個(gè)非標(biāo)準(zhǔn)區(qū)塊，為使農(nóng)機(jī)在每個(gè)區(qū)塊都能完成全覆蓋作業(yè)，令標(biāo)準(zhǔn)區(qū)塊路徑數(shù)量為Bmin，非標(biāo)準(zhǔn)區(qū)塊數(shù)量BN≥Bmin，采用弓形調(diào)頭路徑進(jìn)行逐區(qū)塊作業(yè)。圖3所示為smin=2時(shí)的區(qū)塊劃分結(jié)果，其中左側(cè)為標(biāo)準(zhǔn)區(qū)塊右側(cè)為非標(biāo)準(zhǔn)區(qū)塊。標(biāo)準(zhǔn)區(qū)塊數(shù)量ks為

標(biāo)準(zhǔn)區(qū)塊路徑編號(hào)qi,j為

式中qi,j為田塊中第j個(gè)區(qū)塊內(nèi)第i個(gè)順序的路徑編號(hào)。

非標(biāo)準(zhǔn)區(qū)塊路徑數(shù)量BN為

非標(biāo)準(zhǔn)區(qū)域跳過的路徑數(shù)量sN為

非標(biāo)準(zhǔn)區(qū)塊路徑編號(hào)為

農(nóng)機(jī)進(jìn)入和離開田塊位于同一端地頭時(shí)，作業(yè)路徑數(shù)量為偶數(shù)，位于不同端地頭時(shí)則為奇數(shù)。若作業(yè)路徑數(shù)量為偶數(shù)，要實(shí)現(xiàn)農(nóng)機(jī)進(jìn)入和離開農(nóng)田位置位于不同端地頭、或作業(yè)路徑數(shù)量為奇數(shù)要實(shí)現(xiàn)農(nóng)機(jī)進(jìn)入和離開農(nóng)田位置位于同一端地頭時(shí)，需要在繞行區(qū)域增加一條空行路徑。當(dāng)2個(gè)需要作業(yè)的田塊地頭相鄰，且農(nóng)機(jī)可以從地界處進(jìn)入田塊時(shí)，令要進(jìn)入的田塊為目標(biāo)田塊，正在作業(yè)的田塊為當(dāng)前田塊，為方便農(nóng)機(jī)進(jìn)入目標(biāo)田塊后經(jīng)過最小的調(diào)整就能作業(yè)，令當(dāng)前田塊的最后作業(yè)路徑與目標(biāo)田塊的第1條作業(yè)路徑橫向偏差最小，如圖4所示，其中No.last（白色）行為當(dāng)前田塊的最后作業(yè)行，區(qū)塊劃分中不包括No.last行。

根據(jù)文獻(xiàn)[32]，弓形調(diào)頭路徑近似長度S∏為

式中x為調(diào)頭中2條路徑的距離，m。

(N-2kE)2kE且(N-2kE)

魚尾形調(diào)頭路徑最小轉(zhuǎn)彎地帶寬度ET為

魚尾形調(diào)頭路徑近似長度ST為

2.2.2 農(nóng)機(jī)作業(yè)時(shí)間

農(nóng)機(jī)ai的作業(yè)時(shí)間ti主要由農(nóng)機(jī)在路上的時(shí)間和農(nóng)機(jī)在田塊的時(shí)間2部分構(gòu)成：

式中tRi為農(nóng)機(jī)ai在路上的時(shí)間，h；tFi為農(nóng)機(jī)ai在田塊的時(shí)間，h；si為農(nóng)機(jī)ai在路上的總路程，km；vi為農(nóng)機(jī)ai在路上的速度，km/h。

2.2.3 農(nóng)機(jī)作業(yè)路上的總路程

建立n個(gè)任務(wù)田塊間農(nóng)機(jī)可行駛的實(shí)際最短距離矩陣，若將車庫作為第0個(gè)任務(wù)，得到矩陣D為

式中dij為第i-1個(gè)任務(wù)田塊到第j-1個(gè)任務(wù)田塊之間的實(shí)際可行駛距離，km，i,j=2,3,…,n+1,且i≠j。

如果j、k兩個(gè)任務(wù)田塊地頭相鄰，且農(nóng)機(jī)可從地界直接駛?cè)胩飰K進(jìn)行作業(yè)，則dj+1,k+1=0。

總路程si由3部分組成：農(nóng)機(jī)ai從車庫到其第一個(gè)任務(wù)田塊Tj的路程d1,j+1、農(nóng)機(jī)從第j個(gè)任務(wù)田塊Tj到下一個(gè)任務(wù)田塊Tk的路程dj+1,k+1、農(nóng)機(jī)從最后一個(gè)任務(wù)田塊Tl回到車庫的路程d1,l+1，其中j,k,l=1,2,…,n。具體計(jì)算如下：

其中

農(nóng)機(jī)在田塊的作業(yè)時(shí)間tFi主要由作業(yè)時(shí)間、調(diào)頭時(shí)間和直線空行時(shí)間構(gòu)成：

式中l(wèi)i,j,k為農(nóng)機(jī)ai在任務(wù)田塊Tj的第k條直行路徑的長度，km；bi,j,k為農(nóng)機(jī)ai在任務(wù)田塊Tj中繞行的第k條橫行路徑的長度，km；Si,j,k為農(nóng)機(jī)ai在任務(wù)田塊Tj的第k條轉(zhuǎn)彎路徑的長度，km；Ni,j,t為農(nóng)機(jī)ai在任務(wù)田塊Tj的調(diào)頭數(shù)量；lB為農(nóng)機(jī)ai在任務(wù)田塊Tj的空行直線路徑長度，km；vwi為農(nóng)機(jī)ai的作業(yè)速度，km/h；vti為農(nóng)機(jī)ai在田塊的調(diào)頭的速度，km/h。 其中

2.2.4 農(nóng)機(jī)作業(yè)油耗

農(nóng)機(jī)ai的作業(yè)油耗ci主要農(nóng)機(jī)在路上的油耗和農(nóng)機(jī)在田塊的油耗由2部分構(gòu)成：

式中cRi為農(nóng)機(jī)ai在路上的油耗，L；cFi為農(nóng)機(jī)ai在田塊的油耗，L；Fci為農(nóng)機(jī)ai非作業(yè)狀態(tài)下平均每公里的油耗，L/km；Fwci為農(nóng)機(jī)ai作業(yè)狀態(tài)下平均每公里油耗，主要由作業(yè)油耗、調(diào)頭油耗和直線空行油耗構(gòu)成，L/km。

3 動(dòng)態(tài)任務(wù)分配

農(nóng)機(jī)機(jī)群作業(yè)過程中，受一些因素的影響，機(jī)群無法繼續(xù)執(zhí)行原有作業(yè)計(jì)劃，需要根據(jù)任務(wù)執(zhí)行進(jìn)度和機(jī)群狀態(tài)進(jìn)行動(dòng)態(tài)任務(wù)分配。農(nóng)機(jī)機(jī)群作業(yè)過程中需要進(jìn)行動(dòng)態(tài)任務(wù)分配的情況主要有：①新增作業(yè)任務(wù)；②作業(yè)過程中有農(nóng)機(jī)出現(xiàn)故障無法繼續(xù)作業(yè)；③原有作業(yè)任務(wù)中一些作業(yè)任務(wù)取消。其中情況①、②是多機(jī)作業(yè)過程中最常見的情況，本文主要針對情況①、②進(jìn)行動(dòng)態(tài)任務(wù)分配研究。

動(dòng)態(tài)任務(wù)分配分為集中式和分布式，在本文的體系結(jié)構(gòu)中，集中式任務(wù)分配由服務(wù)器負(fù)責(zé)整個(gè)機(jī)群的任務(wù)分配，分布式任務(wù)分配由整個(gè)機(jī)群聯(lián)合處理進(jìn)行任務(wù)分配。其中，在集中式任務(wù)分配中服務(wù)器處理所有計(jì)算，需要服務(wù)器具有強(qiáng)大的計(jì)算功能，對終端設(shè)備要求較低，當(dāng)終端很多時(shí)會(huì)導(dǎo)致響應(yīng)速度變慢；在分布式任務(wù)分配中所有終端都參與計(jì)算，對終端設(shè)備要求較高，處理能力強(qiáng)?？紤]到目前農(nóng)機(jī)終端計(jì)算機(jī)都有較強(qiáng)的計(jì)算能力，為減少服務(wù)器壓力，采用分布式方式處理動(dòng)態(tài)任務(wù)分配問題。

3.1 合同網(wǎng)算法

合同網(wǎng)算法（CNP，Contract Net Protocol）是處理分布式任務(wù)分配方法的常用算法，通過模仿經(jīng)濟(jì)行為的“招標(biāo)-投標(biāo)-中標(biāo)”機(jī)制來實(shí)現(xiàn)任務(wù)分配[34-36]，其基本流程如圖5所示。

使用CNP解決農(nóng)機(jī)機(jī)群任務(wù)分配過程中，服務(wù)器端作為招標(biāo)者、農(nóng)機(jī)端作為投標(biāo)者。假設(shè)機(jī)群原分配任務(wù)及順序?yàn)樽顑?yōu)分配結(jié)果，動(dòng)態(tài)任務(wù)分配過程中投標(biāo)者計(jì)算投標(biāo)值時(shí)，使用將招標(biāo)任務(wù)插入原有任務(wù)序列的方法計(jì)算農(nóng)機(jī)ai執(zhí)行新任務(wù)田塊Tj的代價(jià)Δfij，招標(biāo)者選擇Δfij最小的招標(biāo)者作為中標(biāo)者。

農(nóng)機(jī)ai對任務(wù)田塊Tj投標(biāo)的代價(jià)函數(shù)Δfi j為

式中tij為第i臺(tái)農(nóng)機(jī)添加任務(wù)田塊Tj后所需作業(yè)的總時(shí)間，h；tmax為招標(biāo)開始前整個(gè)機(jī)群的機(jī)群工作時(shí)間，h；Δci為第i臺(tái)農(nóng)機(jī)添加任務(wù)Tj后所需油耗的增量，L；Δsi為第i臺(tái)農(nóng)機(jī)添加任務(wù)Tj后路上路程的增量，km。

當(dāng)?shù)趇臺(tái)農(nóng)機(jī)中標(biāo)任務(wù)田塊Tj后整個(gè)機(jī)群代價(jià)f'為

式中f為招標(biāo)前機(jī)群的總代價(jià)。

3.2 改進(jìn)合同網(wǎng)算法

3.2.1 任務(wù)分配結(jié)構(gòu)設(shè)計(jì)

為減少服務(wù)器的計(jì)算量，設(shè)計(jì)了基于農(nóng)機(jī)間招-投標(biāo)過程的動(dòng)態(tài)任務(wù)分配方法。如圖6所示，服務(wù)器端設(shè)有管理者和公告板2個(gè)模塊，管理者可以與客戶端和農(nóng)機(jī)終端進(jìn)行通信，當(dāng)有新任務(wù)需要?jiǎng)討B(tài)分配時(shí)，管理者通知相關(guān)農(nóng)機(jī)讀取公告板；公告板接收管理者信息并展示，起到信息共享作用；農(nóng)機(jī)終端可與管理者通信、讀取公告板信息；動(dòng)態(tài)任務(wù)分配在農(nóng)機(jī)終端之間進(jìn)行。

3.2.2 算法改進(jìn)

在設(shè)計(jì)的動(dòng)態(tài)任務(wù)分配結(jié)構(gòu)中，任務(wù)分配過程在正常作業(yè)的農(nóng)機(jī)間進(jìn)行，所有作業(yè)的農(nóng)機(jī)作為投標(biāo)者，其中一臺(tái)農(nóng)機(jī)既作為招標(biāo)者又作為投標(biāo)者。招投標(biāo)過程中可能出現(xiàn)以下問題，如果招標(biāo)者距離其他投標(biāo)者距離過遠(yuǎn)會(huì)加大丟包率，影響任務(wù)分配效果；如果招標(biāo)者為最終的中標(biāo)者，多次招投標(biāo)通信為無效通信；在有新任務(wù)加入的情況下，農(nóng)機(jī)原有任務(wù)及序列可能不是最優(yōu)分配?；谝陨蠁栴}設(shè)計(jì)了幾種改進(jìn)基于公告板合同網(wǎng)算法的幾種辦法。

1）選擇招標(biāo)者

任務(wù)分配的招投標(biāo)過程由農(nóng)機(jī)間無線網(wǎng)絡(luò)完成通信，選擇招標(biāo)者使招標(biāo)者與投標(biāo)者之間的直線距離和最短

式中(xi,yi)為農(nóng)機(jī)ai當(dāng)前位置的高斯平面坐標(biāo)，m。

2）設(shè)定招標(biāo)閾值

由于招標(biāo)者自身也作為投標(biāo)者，為減少無效投標(biāo)，降低任務(wù)分配過程中農(nóng)機(jī)間的通信，采用設(shè)定招標(biāo)閾值的方法，招標(biāo)者在對任務(wù)Tj進(jìn)行招標(biāo)前，首先計(jì)算招標(biāo)者自身執(zhí)行該任務(wù)的最小代價(jià)Δf j作為動(dòng)態(tài)閾值。

式中Δfbidj為招標(biāo)者執(zhí)行新增任務(wù)Tj的代價(jià)。

投標(biāo)者ai接收招標(biāo)信息并計(jì)算自身執(zhí)行該任務(wù)的最小代價(jià)Δfij，如果Δfij<Δf j發(fā)送投標(biāo)信息，如果Δfij≥Δf j，則不發(fā)送投標(biāo)信息。

3）中標(biāo)者任務(wù)再分配

為使農(nóng)機(jī)任務(wù)分配更加均衡，減小農(nóng)機(jī)間作業(yè)代價(jià)的差，建立單機(jī)代價(jià)函數(shù)，按中標(biāo)農(nóng)機(jī)作業(yè)代價(jià)從高到低的順序依次作為招標(biāo)者進(jìn)行任務(wù)再分配，i臺(tái)農(nóng)機(jī)的代價(jià)函數(shù)fi為

按招標(biāo)農(nóng)機(jī)任務(wù)面積從小到大的順序進(jìn)行任務(wù)再分配，農(nóng)機(jī)ai對任務(wù)田塊Tj招標(biāo)的閾值Δf j為

式中ti-j為農(nóng)機(jī)ai去掉任務(wù)田塊Tj后完成任務(wù)的時(shí)間，h；Δci'為農(nóng)機(jī)ai去掉任務(wù)田塊Tj后減少的油耗，L；Δsi'為農(nóng)機(jī)ai去掉任務(wù)田塊Tj后減少的路程，km。

4）農(nóng)機(jī)間任務(wù)交換

農(nóng)機(jī)執(zhí)行任務(wù)過程中有部分代價(jià)發(fā)生在從一個(gè)任務(wù)到另一個(gè)任務(wù)的路程中，進(jìn)行合理的任務(wù)交換以減少總路程是降低整體代價(jià)的一個(gè)辦法。

設(shè)農(nóng)機(jī)ai執(zhí)行任務(wù)Tj的路程代價(jià)fsij為

式中si-j為農(nóng)機(jī)ai去掉任務(wù)Tj后的路程，km。

任務(wù)交換流程如下：

① 完成任務(wù)代價(jià)最大的農(nóng)機(jī)ai計(jì)算出最大路程代價(jià)max(fsij)和對應(yīng)的任務(wù)田塊Tj。

② 農(nóng)機(jī)ai作為招標(biāo)者對任務(wù)田塊Tj進(jìn)行交換招標(biāo)；

③ 其他工作正常的農(nóng)機(jī)作為投標(biāo)者，投標(biāo)者將任務(wù)田塊Tj依次與自身未作業(yè)任務(wù)田塊進(jìn)行替換，并使用2-opt進(jìn)行優(yōu)化，計(jì)算替換后自身最小代價(jià)；

④ 如果替換后代價(jià)小于替換前，該任務(wù)作為投標(biāo)信息；

⑤ 招標(biāo)者計(jì)算刪除任務(wù)j后加入每個(gè)投標(biāo)任后的代價(jià)，并取最小代價(jià)fik和對應(yīng)的任務(wù)田塊Tk；

⑥ 如果fik

3.3 基于改進(jìn)合同網(wǎng)算法的任務(wù)分配流程

基于改進(jìn)合同網(wǎng)算法的任務(wù)分配流程如圖7所示。

4 仿真試驗(yàn)

由于農(nóng)機(jī)油耗與農(nóng)機(jī)牽引力正相關(guān)，每公里油耗確定困難,為驗(yàn)證改進(jìn)合同網(wǎng)算法動(dòng)態(tài)任務(wù)分配效果，以α=[1,0,0]為例，從中國農(nóng)機(jī)開發(fā)的農(nóng)業(yè)機(jī)械化精準(zhǔn)作業(yè)平臺(tái)選擇包括多個(gè)較集中且平整地塊參數(shù)作為仿真試驗(yàn)地塊參數(shù)，選擇農(nóng)機(jī)合作社常見拖拉機(jī)及機(jī)具參數(shù)作為仿真試驗(yàn)農(nóng)機(jī)參數(shù)，試驗(yàn)田塊如圖8所示，共15個(gè)任務(wù)，任務(wù)主要參數(shù)如表1所示，田塊較規(guī)則，均為標(biāo)準(zhǔn)矩形田塊；共4臺(tái)農(nóng)機(jī)，農(nóng)機(jī)主要性能參數(shù)如表2所示。分別用傳統(tǒng)合同網(wǎng)算法和改進(jìn)合同網(wǎng)算法對新增任務(wù)情況和出現(xiàn)故障的情況進(jìn)行動(dòng)態(tài)任務(wù)分配仿真試驗(yàn)。

表2 農(nóng)機(jī)性能參數(shù) Table 2 Performance parameters of agricultural machineries

表1 任務(wù)田塊參數(shù) Table 1 Task field parameters

4.1 有新任務(wù)加入情況的動(dòng)態(tài)任務(wù)分配試驗(yàn)

假設(shè)農(nóng)機(jī)a1、a2和a3共同進(jìn)行作業(yè)，分別以{T1～T10}、{T1～T11}和{T1～T12}為原任務(wù)，{T11～T14}、{T12～T15}和{T13～T15}為新增任務(wù)。使用遺傳算法將原任務(wù)進(jìn)行靜態(tài)任務(wù)分配，原任務(wù)的多機(jī)協(xié)同代價(jià)分別為7.63 、8.57 和9.22 h。實(shí)際作業(yè)過程中，假設(shè)農(nóng)機(jī)同時(shí)開始作業(yè)，新增任務(wù)可能發(fā)生在農(nóng)機(jī)作業(yè)后的各個(gè)階段，根據(jù)原有任務(wù)的作業(yè)時(shí)間，假設(shè)當(dāng)作業(yè)時(shí)間分別為2、4、6 h時(shí)進(jìn)行新增任務(wù)的動(dòng)態(tài)任務(wù)分配，任務(wù)分配結(jié)果如表3所示。

表3 新增任務(wù)情況下動(dòng)態(tài)任務(wù)分配結(jié)果 Table 3 Dynamic task allocation results in the case of new tasks

{T1～T10}為原任務(wù){(diào)T11～T14}為新增任務(wù)時(shí)，動(dòng)態(tài)任務(wù)分配前的任務(wù)分配結(jié)果為農(nóng)機(jī)a1田塊作業(yè)順序?yàn)?→2 →4→6，農(nóng)機(jī)a2田塊作業(yè)順序?yàn)?→8→10→9，農(nóng)機(jī)a3田塊作業(yè)順序?yàn)?→5，動(dòng)態(tài)任務(wù)分配結(jié)果表明，基于改進(jìn)合同網(wǎng)算法比基于傳統(tǒng)合同網(wǎng)算法的動(dòng)態(tài)任務(wù)分配農(nóng)機(jī)機(jī)與服務(wù)器通信次數(shù)較少85%，機(jī)群多機(jī)協(xié)同時(shí)間代價(jià)降低7.34%～8.05%。

{T1～T11}為原任務(wù){(diào)T12～T15}為新增任務(wù)時(shí)，動(dòng)態(tài)任務(wù)分配前的任務(wù)分配結(jié)果為農(nóng)機(jī)a1田塊作業(yè)順序?yàn)? →10→9→11，農(nóng)機(jī)a2田塊作業(yè)順序?yàn)?→1→3→4，農(nóng)機(jī)a3田塊作業(yè)順序?yàn)?→8→7，動(dòng)態(tài)任務(wù)分配結(jié)果表明，基于改進(jìn)合同網(wǎng)算法比基于傳統(tǒng)合同網(wǎng)算法的動(dòng)態(tài)任務(wù)分配農(nóng)機(jī)機(jī)與服務(wù)器通信次數(shù)較少85%，機(jī)群多機(jī)協(xié)同時(shí)間代價(jià)降低4.41%～6.67%。

{T1～T12}為原任務(wù){(diào)T13～T15}為新增任務(wù)時(shí)，動(dòng)態(tài)任務(wù)分配前的任務(wù)分配結(jié)果為農(nóng)機(jī)a1田塊作業(yè)順序?yàn)?→3 →11→9→12，農(nóng)機(jī)a2田塊作業(yè)順序?yàn)?→8→6→5，農(nóng)機(jī)a3田塊作業(yè)順序?yàn)?→10→2，動(dòng)態(tài)任務(wù)分配結(jié)果表明，基于改進(jìn)合同網(wǎng)算法比基于傳統(tǒng)合同網(wǎng)算法的動(dòng)態(tài)任務(wù)分配農(nóng)機(jī)機(jī)與服務(wù)器通信次數(shù)較少80%，機(jī)群多機(jī)協(xié)同時(shí)間代價(jià)降低0.83%～5.58%。

由任務(wù)分配結(jié)果可知，在不同時(shí)刻執(zhí)行新增任務(wù)的動(dòng)態(tài)任務(wù)分配，基于改進(jìn)合同網(wǎng)算法的結(jié)果都優(yōu)于基于傳統(tǒng)合同網(wǎng)算法的結(jié)果，在新增任務(wù)試驗(yàn)情況下農(nóng)機(jī)與服務(wù)器的通信次數(shù)降低80%～85%，機(jī)群時(shí)間代價(jià)降低0.83%～8.05%，均有較明顯降低。試驗(yàn)結(jié)果表明，在新增任務(wù)情況下，基于改進(jìn)合同網(wǎng)算法的動(dòng)態(tài)任務(wù)分配方法性能更加優(yōu)秀。

4.2 有農(nóng)機(jī)出現(xiàn)故障情況的動(dòng)態(tài)任務(wù)分配試驗(yàn)

播種作業(yè)過程中，故障農(nóng)機(jī)所在作業(yè)行及作業(yè)行中間的未作業(yè)行由故障農(nóng)機(jī)修復(fù)后完成作業(yè)；收獲類作業(yè)將未作業(yè)區(qū)域全部規(guī)劃進(jìn)行作業(yè)。以收獲作業(yè)為例假設(shè)作業(yè)開始前將任務(wù)T1～T15分配給農(nóng)機(jī)a1～a4，任務(wù)分結(jié)果為：農(nóng)機(jī)a1的田塊作業(yè)順序?yàn)?5→5→1→3；農(nóng)機(jī)a2的田塊作業(yè)順序?yàn)?3→12→8→14；農(nóng)機(jī)a3的田塊作業(yè)順序?yàn)?→4→6→7；農(nóng)機(jī)a4的田塊作業(yè)順序?yàn)?→10→11；機(jī)群作業(yè)時(shí)間代價(jià)為10.26 h。分別假設(shè)開始作業(yè)1、3、5 h后農(nóng)機(jī)a3發(fā)生故障，對農(nóng)機(jī)a3未完成的任務(wù)進(jìn)行動(dòng)態(tài)任務(wù)分配，任務(wù)分配結(jié)果如表4所示，基于改進(jìn)合同網(wǎng)算法比基于傳統(tǒng)合同網(wǎng)算法的動(dòng)態(tài)任務(wù)分配農(nóng)機(jī)與服務(wù)器通信次數(shù)較少77.4%，機(jī)群多機(jī)協(xié)同時(shí)間代價(jià)降低1.77%～12.89%。

表4 有農(nóng)機(jī)故障情況下動(dòng)態(tài)任務(wù)分配結(jié)果 Table 4 Dynamic task allocation results in the case of agricultural machinery failure

由任務(wù)分配結(jié)果可知，在有農(nóng)機(jī)出現(xiàn)故障的情況下基于改進(jìn)合同網(wǎng)算法的動(dòng)態(tài)任務(wù)分配結(jié)果比基于傳統(tǒng)合同網(wǎng)算法的動(dòng)態(tài)任務(wù)分配結(jié)果機(jī)群時(shí)間代價(jià)平均降低5.86%，最高降低12.89%，農(nóng)機(jī)與服務(wù)器間的通信次數(shù)降低77.4%，均有較明顯降低。試驗(yàn)結(jié)果表明，在有農(nóng)機(jī)出現(xiàn)故障情況下，基于改進(jìn)合同網(wǎng)算法的動(dòng)態(tài)任務(wù)分配方法性能更加優(yōu)秀。

仿真結(jié)果表明，傳統(tǒng)合同網(wǎng)算法和改進(jìn)合同網(wǎng)算法都可以用來處理動(dòng)態(tài)任務(wù)分配問題。其中，使用改進(jìn)合同網(wǎng)算法可以得到更好的任務(wù)分配效果并且減少農(nóng)機(jī)與服務(wù)器間的通信次數(shù)，同時(shí)，在使用改進(jìn)合同網(wǎng)算法的任務(wù)分配過程中，服務(wù)器只執(zhí)行簡單的通信而不參與任務(wù)分配的計(jì)算，將全部計(jì)算和部分通信放在農(nóng)機(jī)終端計(jì)算機(jī)，充分利用了農(nóng)機(jī)終端計(jì)算機(jī)的計(jì)算能力，大大減輕了服務(wù)器負(fù)擔(dān)，因此，基于改進(jìn)合同網(wǎng)算法的動(dòng)態(tài)任務(wù)分配方法具有明顯優(yōu)勢。

5 實(shí)際播種作業(yè)試驗(yàn)

為驗(yàn)證本文基于改進(jìn)合同網(wǎng)算法的動(dòng)態(tài)任務(wù)分配方法在實(shí)際作業(yè)場景中的有效性，進(jìn)行實(shí)際播種作業(yè)試驗(yàn)。圖9為內(nèi)蒙古興安農(nóng)墾吐列毛杜農(nóng)場一區(qū)某日播種作業(yè)情況，3臺(tái)播種機(jī)共完成11個(gè)田塊任務(wù)。根據(jù)中國農(nóng)機(jī)院農(nóng)機(jī)合作社管理云服務(wù)平臺(tái)得到播種機(jī)性能參數(shù)和任務(wù)參數(shù)，3臺(tái)播種機(jī)所用拖拉機(jī)型號(hào)分別為約2臺(tái)翰迪爾2204拖拉機(jī)和1臺(tái)約翰迪爾1854拖拉機(jī)，主要性能參數(shù)如表5所示，11個(gè)任務(wù)參數(shù)如表6所示。

3臺(tái)播種機(jī)執(zhí)行任務(wù)的實(shí)際作業(yè)田塊順序分別為1→2→8 →9→10→11、6→7和3→4→5，如圖10所示，其中亮色區(qū)域?yàn)橄鄳?yīng)播種機(jī)該日作業(yè)田塊。3臺(tái)播種機(jī)的理論作業(yè)時(shí)間分別為14.14 、5.78 和6.50 h。播種機(jī)1率先完成任務(wù)1和任務(wù)2回到車庫后接到新增任務(wù)8、9、10和11，造成任務(wù)分配不均衡播種機(jī)1作業(yè)時(shí)間過大，導(dǎo)致機(jī)群作業(yè)代價(jià)增加。

假設(shè)3臺(tái)播種機(jī)同時(shí)出發(fā)作業(yè)，當(dāng)作業(yè)時(shí)間分為2、4、6 h時(shí)進(jìn)行基于改進(jìn)合同網(wǎng)算法的動(dòng)態(tài)任務(wù)分配試驗(yàn)，結(jié)果如表7所示。當(dāng)作業(yè)時(shí)間分別為2、4、6 h時(shí)，經(jīng)過基于改進(jìn)合同網(wǎng)算法的多機(jī)協(xié)同動(dòng)態(tài)任務(wù)分配機(jī)群時(shí)間代價(jià)比實(shí)際作業(yè)理論機(jī)群時(shí)間代價(jià)降低30.20～34.09%。

表7 不同時(shí)間下試驗(yàn)結(jié)果 Table 7 Experiment results at different times

由試驗(yàn)結(jié)果可知，在不同時(shí)間執(zhí)行動(dòng)態(tài)任務(wù)分配均可得到較優(yōu)的任務(wù)分配結(jié)果，任務(wù)分配后機(jī)群代價(jià)比實(shí)際作業(yè)理論機(jī)群代價(jià)降低30%以上。因此，基于改進(jìn)合同網(wǎng)的動(dòng)態(tài)任務(wù)分配方法可以較好的解決實(shí)際作業(yè)情況下有突發(fā)情況的動(dòng)態(tài)任務(wù)分配問題。

6 結(jié) 論

1）本文對同種作業(yè)農(nóng)機(jī)機(jī)群動(dòng)態(tài)任務(wù)分配問題進(jìn)行了研究，以機(jī)群中用時(shí)最長農(nóng)機(jī)的作業(yè)時(shí)間、機(jī)群的油耗和機(jī)群的路程為代價(jià)建立代價(jià)函數(shù)和目標(biāo)函數(shù)。

2）提出了基于合同網(wǎng)算法的動(dòng)態(tài)任務(wù)分配方法和改進(jìn)合同網(wǎng)算法的4種方法，包括基于直線距離和最短的招標(biāo)者選擇方法、基于招標(biāo)者作業(yè)能力的閾值設(shè)定方法、基于最小面積的任務(wù)再招標(biāo)方法和基于路程最大的任務(wù)交換方法。

3）選擇適當(dāng)田塊作為任務(wù)田塊，分別對有新任務(wù)增加的情況和農(nóng)機(jī)出現(xiàn)故障的情況進(jìn)行了基于合同網(wǎng)算法和基于改進(jìn)合同網(wǎng)算法的動(dòng)態(tài)任務(wù)分配仿真試驗(yàn)，仿真結(jié)果表明基于改進(jìn)合同網(wǎng)算法的動(dòng)態(tài)任務(wù)分配結(jié)果比基于傳統(tǒng)合同網(wǎng)的動(dòng)態(tài)任務(wù)分配結(jié)果農(nóng)機(jī)與服務(wù)器通信次數(shù)減少77.4%～85.0%，機(jī)群時(shí)間代價(jià)均降低0.83%～12.89%。

4）進(jìn)行實(shí)際播種新增任務(wù)情況下動(dòng)態(tài)任務(wù)分配試驗(yàn)，由試驗(yàn)結(jié)果可知，在不同的時(shí)間執(zhí)行基于改進(jìn)合同網(wǎng)算法新增任務(wù)的動(dòng)態(tài)任務(wù)分配，任務(wù)分配后機(jī)群時(shí)間代價(jià)比真實(shí)機(jī)群理論時(shí)間代價(jià)降低30.20%～34.09%。試驗(yàn)結(jié)果表明，基于改進(jìn)合同網(wǎng)的農(nóng)機(jī)機(jī)群動(dòng)態(tài)任務(wù)分配方法可以解決機(jī)群作業(yè)過程中有突發(fā)情況且無嚴(yán)格作業(yè)時(shí)間窗口的動(dòng)態(tài)任務(wù)分配問題。