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

國(guó)內(nèi)外針對(duì)農(nóng)業(yè)機(jī)械調(diào)度問題主要集中在田間農(nóng)機(jī)資源調(diào)度與路徑規(guī)劃的問題上，根據(jù)不同的農(nóng)機(jī)調(diào)度類型可整體分為有無(wú)運(yùn)糧車響應(yīng)的收割機(jī)間協(xié)同調(diào)度的農(nóng)田作業(yè)問題。面對(duì)多農(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)速度的同時(shí)防止陷入局部最優(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)化分布式評(píng)估算法來(lái)優(yōu)化非作業(yè)路程。Cariou等[12]提出了基于回旋曲線的掉頭方法，Boryga等[13]提出了基于多項(xiàng)式曲線的掉頭路徑規(guī)劃方法。姚竟發(fā)等[14]以總作業(yè)時(shí)間和作業(yè)時(shí)長(zhǎng)為綜合優(yōu)化目標(biāo)，考慮聯(lián)合收割機(jī)和作業(yè)沖突的情況，提出聯(lián)合收割機(jī)多機(jī)無(wú)沖突協(xié)同作業(yè)路徑優(yōu)化算法，但尚未考慮加入運(yùn)糧車的響應(yīng)。王雪陽(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)整個(gè)工程最小化的調(diào)度成本。艾長(zhǎng)勝等[16]為提高植保機(jī)器人在路徑規(guī)劃中的準(zhǔn)確度與可靠性，對(duì)果園信息進(jìn)行預(yù)處理實(shí)現(xiàn)精確作業(yè)，但沒有對(duì)農(nóng)田進(jìn)行全局路徑規(guī)劃。而對(duì)于多臺(tái)聯(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è)時(shí)間。He等[19-20]將收割機(jī)收割與運(yùn)糧車運(yùn)輸問題視為一個(gè)帶動(dòng)態(tài)衛(wèi)星的多行程車輛路徑問題，依據(jù)運(yùn)糧車需要響應(yīng)的具體位置的動(dò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ī)糧倉(cāng)容積、運(yùn)糧車協(xié)同作業(yè)等因素，以最小化聯(lián)合收割機(jī)總生產(chǎn)性作業(yè)時(shí)間和總非生產(chǎn)性作業(yè)時(shí)間為目標(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 問題描述

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

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

針對(duì)本文的研究?jī)?nèi)容，特做以下說(shuō)明。

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

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

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

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

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

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

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

1.2 模型構(gòu)建

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

1) 農(nóng)田作業(yè)行集合N={n1，n2，n3，…，ni}，即按照作業(yè)總行數(shù)從左向右進(jìn)行農(nóng)田順序編號(hào)。以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臺(tái)收割機(jī)，其屬性描述為mz={Cz，tz，Vz，Vz′}。其中，Cz表示收割機(jī)糧倉(cāng)容積，tz表示聯(lián)合收割機(jī)的等待時(shí)間，Vz表示聯(lián)合收割機(jī)直線作業(yè)速度，Vz′表示收割機(jī)轉(zhuǎn)彎作業(yè)速度，收割機(jī)糧倉(cāng)喂入量為h。運(yùn)糧車集群表示為YU={u1，u2，u3，…，uy}，以u(píng)y表示第y臺(tái)運(yùn)糧車，其屬性描述為uy={Cy′，Vy′}，Cy′表示運(yùn)糧車的糧倉(cāng)容積，且滿足Cy′≥Cz，Vy′表示運(yùn)糧車的作業(yè)速度。

3) 聯(lián)合收割機(jī)在農(nóng)田地頭主要有Ω型和U型兩種轉(zhuǎn)彎方式。Ω型轉(zhuǎn)彎不僅作業(yè)時(shí)間長(zhǎng)且操作難度較大，對(duì)比U型轉(zhuǎn)彎作業(yè)時(shí)間短、操作簡(jiǎn)便的特點(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)彎時(shí)兩作業(yè)行間的度量，d=|j-i|，i≠j；

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

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

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

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

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

minT1=(Disz+Disz′)/Vz

(1)

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

minT2=T′

(2)

(3)

約束條件

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