李文鑫，張璠, 2，姚竟發(fā), 2，常淑惠, 2，郭亞倩

(1. 河北農(nóng)業(yè)大學(xué)信息科學(xué)與技術(shù)學(xué)院，河北保定，071000； 2. 河北省農(nóng)業(yè)大數(shù)據(jù)重點(diǎn)實(shí)驗(yàn)室，河北保定，071000)

0 引言

在現(xiàn)代農(nóng)業(yè)中，農(nóng)村土地經(jīng)營方式逐漸由分散經(jīng)營轉(zhuǎn)向集中經(jīng)營。既要關(guān)注糧食安全，也要考慮土地的經(jīng)營效率[1]。隨之對農(nóng)業(yè)機(jī)械配置與路徑的規(guī)劃要求也愈來愈高，多臺聯(lián)合收割機(jī)間的協(xié)同作業(yè)雖然有效提高機(jī)械利用率與作業(yè)效率，但沒有運(yùn)糧車的及時響應(yīng)將導(dǎo)致整體作業(yè)時間增長，浪費(fèi)農(nóng)機(jī)資源。因此對于多臺聯(lián)合收割機(jī)完成多約束復(fù)雜農(nóng)田任務(wù)，需要配備精確合理的運(yùn)糧車響應(yīng)，這不僅節(jié)約了農(nóng)機(jī)機(jī)械成本，并且對整個田間運(yùn)輸效率的提升具有重要意義。

國內(nèi)外針對農(nóng)業(yè)機(jī)械調(diào)度問題主要集中在田間農(nóng)機(jī)資源調(diào)度與路徑規(guī)劃的問題上，根據(jù)不同的農(nóng)機(jī)調(diào)度類型可整體分為有無運(yùn)糧車響應(yīng)的收割機(jī)間協(xié)同調(diào)度的農(nóng)田作業(yè)問題。面對多農(nóng)機(jī)調(diào)度問題，Conesa-Muoz等[2-3]使用模擬退火方法的元啟發(fā)式算法提出較為通用的農(nóng)機(jī)調(diào)度路徑規(guī)劃算法，解決了車輛同質(zhì)和車輛異質(zhì)的農(nóng)機(jī)路徑規(guī)劃問題。Seyyedhasani等[4-5]考慮了多輛農(nóng)機(jī)協(xié)同作業(yè)的情況，將農(nóng)機(jī)調(diào)度問題轉(zhuǎn)換為車輛調(diào)度問題，使用改進(jìn)Clarke-Wright算法和禁忌搜索算法提供合理的農(nóng)機(jī)作業(yè)路徑規(guī)劃和調(diào)度方案。林濤等[6]在分析車輛路徑問題的基礎(chǔ)上，將其轉(zhuǎn)換為經(jīng)典TSP優(yōu)化問題進(jìn)行求解，提出了一種改進(jìn)的遺傳算法，在加快尋優(yōu)速度的同時防止陷入局部最優(yōu)。曹如月[7]、張小花[8]類比旅行商問題，采用蟻群算法求解多機(jī)協(xié)同作業(yè)任務(wù)規(guī)劃問題，但未將農(nóng)機(jī)在田間作業(yè)的約束進(jìn)行綜合考慮。劉正偉等[9]以秸稈回收機(jī)械的綜合成本問題為研究目標(biāo)，綜合考慮秸稈回收機(jī)械路徑和作業(yè)沖突的情況，避免回收農(nóng)機(jī)路徑重復(fù)沖突的問題。Utamima等[10-11]提出進(jìn)化混合鄰域搜索算法和進(jìn)化分布式評估算法來優(yōu)化非作業(yè)路程。Cariou等[12]提出了基于回旋曲線的掉頭方法，Boryga等[13]提出了基于多項(xiàng)式曲線的掉頭路徑規(guī)劃方法。姚竟發(fā)等[14]以總作業(yè)時間和作業(yè)時長為綜合優(yōu)化目標(biāo)，考慮聯(lián)合收割機(jī)和作業(yè)沖突的情況，提出聯(lián)合收割機(jī)多機(jī)無沖突協(xié)同作業(yè)路徑優(yōu)化算法，但尚未考慮加入運(yùn)糧車的響應(yīng)。王雪陽等[15]基于啟發(fā)式優(yōu)先規(guī)則農(nóng)機(jī)調(diào)配策略，在農(nóng)機(jī)充足的條件下，多機(jī)并行任務(wù)采用收益最大的農(nóng)田作業(yè)點(diǎn)優(yōu)先調(diào)配規(guī)則進(jìn)行分配，實(shí)現(xiàn)整個工程最小化的調(diào)度成本。艾長勝等[16]為提高植保機(jī)器人在路徑規(guī)劃中的準(zhǔn)確度與可靠性，對果園信息進(jìn)行預(yù)處理實(shí)現(xiàn)精確作業(yè)，但沒有對農(nóng)田進(jìn)行全局路徑規(guī)劃。而對于多臺聯(lián)合收割機(jī)與運(yùn)糧車的響應(yīng)調(diào)度問題，李世超[17]研究了一種跟隨式農(nóng)機(jī)主從導(dǎo)航系統(tǒng)，從機(jī)根據(jù)位姿信息生成預(yù)設(shè)路徑，并跟蹤主機(jī)作業(yè)，初步實(shí)現(xiàn)了主從導(dǎo)航協(xié)同作業(yè)。曹光喬等[18]將農(nóng)田區(qū)域定義為任務(wù)單元，探究收割機(jī)與運(yùn)糧車的響應(yīng)模式，最大化地減少了收割機(jī)非生產(chǎn)性的作業(yè)時間。He等[19-20]將收割機(jī)收割與運(yùn)糧車運(yùn)輸問題視為一個帶動態(tài)衛(wèi)星的多行程車輛路徑問題，依據(jù)運(yùn)糧車需要響應(yīng)的具體位置的動態(tài)變化，提出了一種啟發(fā)式算法的最優(yōu)解，且屬于概念性的調(diào)度響應(yīng)問題。Jing等[21]圍繞實(shí)現(xiàn)農(nóng)業(yè)資源分配和配送車輛協(xié)同調(diào)度的高效智能優(yōu)化，提出一種改進(jìn)的強(qiáng)化免疫算法，提高了算法的自適應(yīng)性和全局搜索能力。

綜上所述，現(xiàn)有研究尚未能解決基于聯(lián)合收割機(jī)與運(yùn)糧車的多機(jī)協(xié)同調(diào)度問題，因此本文綜合考慮了聯(lián)合收割機(jī)糧倉容積、運(yùn)糧車協(xié)同作業(yè)等因素，以最小化聯(lián)合收割機(jī)總生產(chǎn)性作業(yè)時間和總非生產(chǎn)性作業(yè)時間為目標(biāo)，構(gòu)建了基于多機(jī)多目標(biāo)的協(xié)同優(yōu)化調(diào)度模型，設(shè)計(jì)了基于改進(jìn)蟻群算法的優(yōu)化算法，為解決聯(lián)合收割機(jī)與運(yùn)糧車間的協(xié)同調(diào)度問題提供了解決思路。

1 多機(jī)協(xié)同作業(yè)優(yōu)化調(diào)度問題分析

1.1 問題描述

本文主要研究多臺聯(lián)合收割機(jī)作業(yè)路徑優(yōu)化以及基于聯(lián)合收割機(jī)與運(yùn)糧車的協(xié)同調(diào)度問題。多聯(lián)合收割機(jī)在田間作業(yè)路徑規(guī)劃和運(yùn)糧車的調(diào)度示意圖如圖1所示。

圖1 多機(jī)路徑規(guī)劃與調(diào)度示意圖

由圖1可知，多臺聯(lián)合收割機(jī)在一塊農(nóng)田地塊上作業(yè)過程中，若糧倉裝滿后，需要運(yùn)糧車的輔助完成卸糧，然后才能繼續(xù)開展收割作業(yè)。因此本文將在多聯(lián)合收割機(jī)作業(yè)優(yōu)化路徑的基礎(chǔ)上，研究聯(lián)合收割機(jī)與運(yùn)糧車的協(xié)同優(yōu)化調(diào)度方案。

本文簡要描述如下：以總非生產(chǎn)性作業(yè)時間最短為目標(biāo)，計(jì)算m臺聯(lián)合收割機(jī)在一塊農(nóng)田上的最優(yōu)化作業(yè)路徑，接著綜合考慮u臺運(yùn)糧車輔助m臺聯(lián)合收割機(jī)協(xié)同卸糧的情況，以聯(lián)合收割機(jī)非生產(chǎn)性作業(yè)等待時間最短為目標(biāo)，計(jì)算聯(lián)合收割機(jī)與運(yùn)糧車的動態(tài)協(xié)同調(diào)度策略。按照作業(yè)行序列集進(jìn)行收割與卸糧任務(wù)，假定聯(lián)合收割機(jī)的糧倉容積為Cz，在t0時刻收割機(jī)糧倉達(dá)到容積V′時，依據(jù)相對距離最近原則向運(yùn)糧車發(fā)送信號使其進(jìn)行與收割機(jī)之間的協(xié)同調(diào)度，并依據(jù)在t0時刻后收割機(jī)與運(yùn)糧車行駛路程的大小進(jìn)行判斷收割機(jī)是否產(chǎn)生等待時間，再依據(jù)實(shí)際情況卸糧。保證運(yùn)糧車及時完成卸糧任務(wù)。

針對本文的研究內(nèi)容，特做以下說明。

1) 每個作業(yè)行只允許一臺收割機(jī)遍歷1次。

2) 聯(lián)合收割機(jī)連續(xù)作業(yè)至滿倉，完全卸糧后再進(jìn)行下次作業(yè)。

3) 根據(jù)安裝在聯(lián)合收割機(jī)與運(yùn)糧車上的傳感器可以實(shí)時獲取其位置信息。

4) 農(nóng)機(jī)作業(yè)過程中不考慮農(nóng)機(jī)故障與田間遇到障礙物的情況。

5) 聯(lián)合收割機(jī)的型號相同，且作業(yè)能力相同；運(yùn)糧車的型號、作業(yè)速度等均相同。

6) 假設(shè)農(nóng)田地塊的形狀是規(guī)范的矩形，根據(jù)聯(lián)合收割機(jī)作業(yè)幅寬，將農(nóng)田劃分為等寬的若干作業(yè)行。

7) 聯(lián)合收割機(jī)與運(yùn)糧車都從同一個位置出發(fā)，聯(lián)合收割機(jī)完成作業(yè)、運(yùn)糧車卸糧后也回到該出發(fā)點(diǎn)，等待。

1.2 模型構(gòu)建

為方便問題描述與模型構(gòu)建，對相關(guān)變量做以下描述。

1) 農(nóng)田作業(yè)行集合N={n1，n2，n3，…，ni}，即按照作業(yè)總行數(shù)從左向右進(jìn)行農(nóng)田順序編號。以locNi和SNi分別表示農(nóng)田入口位置坐標(biāo)與農(nóng)田面積，i∈N*。

2) 農(nóng)機(jī)機(jī)群分別表示為：聯(lián)合收割機(jī)群ME={m1，m2，m3，…，mz}，以mz表示第z臺收割機(jī)，其屬性描述為mz={Cz，tz，Vz，Vz′}。其中，Cz表示收割機(jī)糧倉容積，tz表示聯(lián)合收割機(jī)的等待時間，Vz表示聯(lián)合收割機(jī)直線作業(yè)速度，Vz′表示收割機(jī)轉(zhuǎn)彎作業(yè)速度，收割機(jī)糧倉喂入量為h。運(yùn)糧車集群表示為YU={u1，u2，u3，…，uy}，以uy表示第y臺運(yùn)糧車，其屬性描述為uy={Cy′，Vy′}，Cy′表示運(yùn)糧車的糧倉容積，且滿足Cy′≥Cz，Vy′表示運(yùn)糧車的作業(yè)速度。

3) 聯(lián)合收割機(jī)在農(nóng)田地頭主要有Ω型和U型兩種轉(zhuǎn)彎方式。Ω型轉(zhuǎn)彎不僅作業(yè)時間長且操作難度較大，對比U型轉(zhuǎn)彎作業(yè)時間短、操作簡便的特點(diǎn)，如果要得到更好的聯(lián)合收割機(jī)路徑優(yōu)化效果，需盡量采用U型轉(zhuǎn)彎。具體公式表述為

U(d)=d·w+(π-2)rmin

式中：U(d)——轉(zhuǎn)彎距離；

w——農(nóng)機(jī)作業(yè)幅寬；

rmin——農(nóng)機(jī)從i行到j(luò)行的最小轉(zhuǎn)彎半徑；

d——轉(zhuǎn)彎時兩作業(yè)行間的度量，d=|j-i|，i≠j；

i——農(nóng)機(jī)作業(yè)結(jié)束行的序號；

j——農(nóng)機(jī)作業(yè)進(jìn)入下一行的行號。

4) 作業(yè)任務(wù)序列集Rz={{0，i1，i2，i3，0}，{0，i4，i5，i6，0}…}，以Rz表示第z臺聯(lián)合收割機(jī)的作業(yè)路徑序列集。

具體目標(biāo)函數(shù)與約束條件分別表示如下。

聯(lián)合收割機(jī)以總生產(chǎn)性作業(yè)時間最短的優(yōu)化目標(biāo)

minT1=(Disz+Disz′)/Vz

(1)

聯(lián)合收割機(jī)以最小化總非生產(chǎn)性作業(yè)時間為優(yōu)化目標(biāo)

minT2=T′

(2)

(3)

約束條件

iz0=i|Rz|+1=0，{i1，…，i|Rm|}?N