面向大規(guī)模農(nóng)田的農(nóng)機(jī)跨區(qū)作業(yè)緊急調(diào)配研究

摘要：針對(duì)大規(guī)模農(nóng)田的糧食搶收工作，由于搶收約束時(shí)間的限制，導(dǎo)致可能無(wú)法在規(guī)定時(shí)間內(nèi)完成所有糧食的收割任務(wù)，此時(shí)則會(huì)出現(xiàn)糧食損失值。構(gòu)建以糧食損失值最小化為目標(biāo)的農(nóng)機(jī)跨區(qū)緊急調(diào)配模型，提出基于兩階段的農(nóng)機(jī)緊急調(diào)配算法（Agricultural Machinery Emergency Algorithm based on Two Stages，TSEA）。首先按照基于距離的分區(qū)策略對(duì)大規(guī)模農(nóng)田進(jìn)行分區(qū)，接著采用改進(jìn)的遺傳算法分別對(duì)各農(nóng)田分區(qū)進(jìn)行農(nóng)機(jī)緊急作業(yè)調(diào)配。為驗(yàn)證算法的有效性，主要從緊急任務(wù)的糧食損失值、算法運(yùn)行時(shí)間等方面將TSEA算法與GA、SA算法進(jìn)行比較， 試驗(yàn)結(jié)果表明，TSEA算法得到的緊急調(diào)度方案優(yōu)于其他兩種算法。為驗(yàn)證本文分區(qū)策略的有效性，分別采用TSEA算法和不分區(qū)的緊急調(diào)配算法從糧食損失值、算法運(yùn)行時(shí)間等方面進(jìn)行比較，驗(yàn)證分區(qū)策略的有效性。多組試驗(yàn)結(jié)果表明該文提出的策略和算法對(duì)于解決大規(guī)模農(nóng)田的農(nóng)機(jī)跨區(qū)緊急調(diào)配問(wèn)題更有效，可為農(nóng)機(jī)管理部門提供解決方案。

關(guān)鍵詞：農(nóng)業(yè)機(jī)械；大規(guī)模農(nóng)田；跨區(qū)作業(yè)；聚類分區(qū)；緊急調(diào)配

中圖分類號(hào)：S255.1" " " 文獻(xiàn)標(biāo)識(shí)碼：A" " " 文章編號(hào)：2095?5553 （2024） 08?0196?08

Research on emergency allocation of agricultural machinery for cross?regions operation in large?scale farmland

Yu Chunhui1， Chang Shuhui1， 2， Zhang Fan1， 2， Yao Jingfa3， Meng Yu4， Guo Yaqian1

（1. College of Information Science and Technology， Hebei Agricultural University ， Baoding， 071001， China；"2. Key Laboratory of Agricultural Big Data of Hebei Province， Baoding， 071001， China； 3. Department of"Software Engineering， Hebei Software Institute， Baoding， 071030， China； 4. College of Continuing Education，"Hebei Agricultural University， Baoding， 071001， China）

Abstract： In the busy farming season， the most urgent work is to rush to harvest grain. Due to the lack of scientific and reasonable emergency operation scheduling plan of agricultural machinery， the agricultural machinery management department cannot guide the agricultural machinery to complete the emergency operation task of large?scale farmland. For the grain rush harvest of large?scale farmland， due to the restriction of the rush harvest constraint time， it may not be able to complete all the grain harvest tasks within the specified time， and then the grain loss value will appear. In this paper， a trans?regional emergency allocation model of agricultural machinery with the goal of minimizing the grain loss value is constructed， and an agricultural machinery emergency allocation algorithm based on two stages （TSEA） is proposed. Firstly， the large?scale farmland is divided according to the distance?based division strategy， and then the improved genetic algorithm is used to carry out the emergency operation allocation of agricultural machinery for each farmland division. In order to verify the effectiveness of the algorithm in this paper， the TSEA algorithm is compared with GA and SA algorithms in terms of the grain loss value of the emergency task and the running time of the algorithm. The experimental results show that the emergency scheduling scheme obtained by the TSEA algorithm is superior to the other two algorithms. In order to verify the effectiveness of the zoning strategy in this paper， the TSEA algorithm and the non?zoning emergency allocation algorithm are used to compare the grain loss value， algorithm running time and other aspects to verify the effectiveness of the zoning strategy. The results of multiple groups of experiments show that the strategies and algorithms proposed in this paper are more effective for solving the problem of emergency allocation of agricultural machinery across?regions in large?scale farmland， and can provide solutions for agricultural machinery management departments.

Keywords： agricultural machinery； large?scale farmland； across?regions operation；cluster partition； emergency deployment

0 引言

糧食安全是國(guó)家經(jīng)濟(jì)和社會(huì)發(fā)展的“壓艙石”。在收獲季節(jié)，加強(qiáng)農(nóng)業(yè)機(jī)械的社會(huì)化服務(wù)與作業(yè)調(diào)配，組織農(nóng)戶及時(shí)搶收已成熟作物，確保糧食顆粒歸倉(cāng)，是第一要?jiǎng)?wù)。面向大規(guī)模農(nóng)田的農(nóng)機(jī)作業(yè)緊急調(diào)配一般由政府或者農(nóng)機(jī)管理部門主導(dǎo)，目的是在限定時(shí)間內(nèi)最大限度的完成大規(guī)模農(nóng)田的糧食搶收工作。因此，科學(xué)合理的農(nóng)機(jī)緊急調(diào)配方案成為迫切需求。

國(guó)外農(nóng)機(jī)一般都是農(nóng)場(chǎng)主自有，所以很少組織大規(guī)模農(nóng)機(jī)跨區(qū)作業(yè)，重點(diǎn)考慮的是農(nóng)機(jī)田內(nèi)路徑規(guī)劃以及農(nóng)機(jī)與運(yùn)糧車之間的協(xié)同調(diào)度等問(wèn)題［1］。而農(nóng)機(jī)跨區(qū)作業(yè)更符合中國(guó)國(guó)情，國(guó)內(nèi)學(xué)者對(duì)農(nóng)機(jī)跨區(qū)作業(yè)研究較多。王雪陽(yáng)等［2］針對(duì)帶時(shí)間窗的農(nóng)機(jī)調(diào)度問(wèn)題，構(gòu)建了基于多個(gè)基站帶時(shí)間窗的農(nóng)機(jī)調(diào)度數(shù)學(xué)模型，通過(guò)改進(jìn)傳統(tǒng)遺傳算法的編碼和交叉操作來(lái)進(jìn)行問(wèn)題的求解，有效降低了農(nóng)機(jī)調(diào)度成本。張璠等［3］針對(duì)農(nóng)機(jī)跨區(qū)作業(yè)問(wèn)題，提出了一種基于機(jī)主選擇的農(nóng)機(jī)調(diào)配模式，建立了以高收入低成本為調(diào)度目標(biāo)的優(yōu)化模型，設(shè)計(jì)了基于啟發(fā)式優(yōu)先級(jí)規(guī)則的農(nóng)機(jī)調(diào)配算法，最后通過(guò)對(duì)農(nóng)田實(shí)例的計(jì)算求解，驗(yàn)證了所設(shè)計(jì)算法從服務(wù)收入、調(diào)配路程和等待時(shí)間等方面優(yōu)于一般的農(nóng)機(jī)調(diào)配算法，證明了算法的有效性。張帆等［4］分析多塊農(nóng)田需連續(xù)進(jìn)行多產(chǎn)任務(wù)的多機(jī)協(xié)同作業(yè)問(wèn)題，建立了以最小化時(shí)間為目標(biāo)的農(nóng)機(jī)作業(yè)調(diào)配模型，提出了改進(jìn)多父輩遺傳算法的優(yōu)化方法求解農(nóng)機(jī)作業(yè)規(guī)劃方案。南風(fēng)［5］在多農(nóng)機(jī)調(diào)度問(wèn)題基礎(chǔ)上引入小農(nóng)戶的訂單場(chǎng)景，提出改進(jìn)的GA?PFIH算法，有效優(yōu)化了農(nóng)機(jī)作業(yè)效率和轉(zhuǎn)移距離。李婷［6］研究了極端天氣下的農(nóng)機(jī)緊急調(diào)配問(wèn)題，以農(nóng)機(jī)調(diào)配成本最小化和時(shí)間偏差最小化為目標(biāo)，建立了多機(jī)多目標(biāo)的調(diào)配模型，提出了基于循環(huán)博弈算法的農(nóng)機(jī)應(yīng)急調(diào)配算法，可最大限度的挽回經(jīng)濟(jì)損失，但未考慮農(nóng)機(jī)數(shù)量對(duì)此算法的影響。張璠等［7］針對(duì)目前農(nóng)機(jī)跨區(qū)緊急作業(yè)缺少合理的調(diào)配方案，建立了以最小化調(diào)度成本和糧食損失為目標(biāo)的緊急調(diào)配模型，并根據(jù)距離和貢獻(xiàn)度兩個(gè)指標(biāo)分別提出了SDFA算法和MAFA算法，最后通過(guò)多組試驗(yàn)驗(yàn)證了算法的適用性。高威［8］根據(jù)緊急調(diào)配任務(wù)的截止時(shí)間約束，先確定所需要的農(nóng)機(jī)數(shù)量，再使用改進(jìn)的蟻群算法以農(nóng)機(jī)成本最低為目標(biāo)給出農(nóng)機(jī)緊急調(diào)配路徑，但未考慮農(nóng)機(jī)數(shù)量不足情況下如何減少糧食損失。農(nóng)機(jī)跨區(qū)作業(yè)研究多數(shù)是從如何節(jié)約成本考慮，而跨區(qū)緊急調(diào)配則是以糧食損失最小為目標(biāo)。目前針對(duì)農(nóng)機(jī)緊急調(diào)配研究偏少，災(zāi)區(qū)物資緊急調(diào)配研究可為農(nóng)機(jī)緊急調(diào)配提供一定的研究思路。Cui等［9］為了應(yīng)對(duì)災(zāi)后應(yīng)急物資的物流和配送。重點(diǎn)考慮供應(yīng)鏈中斷和路徑風(fēng)險(xiǎn)等因素，以物資運(yùn)輸時(shí)間和物資運(yùn)輸成本最小化為目標(biāo)，建立了不確定性條件下的災(zāi)后物資運(yùn)輸模型。利用遺傳算法求解該問(wèn)題，得到了災(zāi)后應(yīng)急物資車輛調(diào)度和物資運(yùn)輸優(yōu)化方案。Wang等［10］針對(duì)災(zāi)后救援中物資運(yùn)輸路線與配送中心選址問(wèn)題。構(gòu)建了一個(gè)考慮行程時(shí)間、總成本和分次配送可靠性的救濟(jì)分配問(wèn)題的非線性整數(shù)開(kāi)放式選址模型，提出了非支配排序遺傳算法和非支配排序差分進(jìn)化算法來(lái)求解該模型。Vahdani等［11］針對(duì)救災(zāi)物資有效分配的問(wèn)題，在三級(jí)救濟(jì)鏈中提供了一個(gè)兩階段、多目標(biāo)、多周期和多商品的數(shù)學(xué)模型，同時(shí)為了使模型更接近現(xiàn)實(shí)，使用魯棒優(yōu)化方法，在不確定的條件下開(kāi)發(fā)模型，使用NSGAII和MOPSO兩種元啟發(fā)式算法來(lái)解決給定的問(wèn)題，并通過(guò)多組數(shù)值示例評(píng)估了模型的準(zhǔn)確性和所提算法的效率。Zhang等［12］為了提高應(yīng)急救援管理中的可持續(xù)救援能力，提出了一種基于條件概率的情景樹(shù)來(lái)定義主次災(zāi)害之間的相關(guān)性，建立了以運(yùn)輸時(shí)間最短、運(yùn)輸成本最低以及不滿意需求量最少為目標(biāo)的三階段隨機(jī)規(guī)劃模型，使用了一種基于隸屬度模糊輔助變量的備選單目標(biāo)模型來(lái)處理多目標(biāo)函數(shù)，并通過(guò)汶川地震的案例驗(yàn)證了所提方案的有效性。目前車輛緊急調(diào)度的相關(guān)研究可為農(nóng)機(jī)緊急調(diào)度問(wèn)題提供一定的研究思路，但這兩類問(wèn)題還存在著很多差異。如車輛有裝載量的限制，農(nóng)機(jī)緊急作業(yè)一般不考慮容量，只要時(shí)間允許可以一直作業(yè)。

當(dāng)緊急情況發(fā)生，農(nóng)機(jī)管理部門需要緊急調(diào)配農(nóng)機(jī)完成大量農(nóng)田作業(yè)點(diǎn)的糧食搶收工作，如果沒(méi)有科學(xué)合理的調(diào)配方案，將會(huì)造成糧食大量損失?，F(xiàn)有的農(nóng)機(jī)調(diào)度研究大多只考慮農(nóng)機(jī)調(diào)配成本，并且未考慮農(nóng)田規(guī)模對(duì)農(nóng)機(jī)緊急作業(yè)調(diào)配的影響。本文研究主要針對(duì)在市或縣級(jí)行政區(qū)域內(nèi)，組織多機(jī)在多地塊間進(jìn)行搶收搶種工作，綜合農(nóng)田、農(nóng)機(jī)、農(nóng)機(jī)站信息以及緊急任務(wù)截止時(shí)間等因素，以糧食損失值最小化為目標(biāo)，構(gòu)建緊急調(diào)配模型，設(shè)計(jì)基于遺傳算法的優(yōu)化算法，為面向大規(guī)模農(nóng)田的緊急調(diào)配問(wèn)題提供解決思路。

1 問(wèn)題描述與模型構(gòu)建

1.1 問(wèn)題描述與假設(shè)

當(dāng)惡劣天氣等緊急情況發(fā)生時(shí)，理想狀態(tài)下，農(nóng)機(jī)管理部門可調(diào)配農(nóng)機(jī)在限定時(shí)間內(nèi)完成所有農(nóng)田的糧食搶收工作，每個(gè)農(nóng)田地塊可能只包含一戶田地，也可能包含多戶相鄰的田地，統(tǒng)稱為一個(gè)農(nóng)田點(diǎn)或一個(gè)農(nóng)田地塊。但是由于緊急任務(wù)限定時(shí)間與當(dāng)前農(nóng)機(jī)保有量的限制，導(dǎo)致可能出現(xiàn)無(wú)論如何調(diào)配農(nóng)機(jī)仍存在個(gè)別農(nóng)田不能被及時(shí)收割的現(xiàn)象，此時(shí)則存在糧食損失值。面向大規(guī)模農(nóng)田的農(nóng)機(jī)跨區(qū)緊急調(diào)配問(wèn)題描述為：在市或縣級(jí)行政區(qū)域內(nèi)，組織多機(jī)在多地塊間進(jìn)行糧食搶收的作業(yè)優(yōu)化調(diào)度，在限定時(shí)間內(nèi)最大限度的降低糧食損失值，綜合農(nóng)田、農(nóng)機(jī)站以及農(nóng)機(jī)信息等因素，以糧食損失值最小作為優(yōu)化目標(biāo)，計(jì)算得到最佳的農(nóng)機(jī)緊急調(diào)配方案，供政府或者農(nóng)機(jī)管理部門參考。

已知各個(gè)農(nóng)田點(diǎn)的地理位置、地塊面積、農(nóng)機(jī)站點(diǎn)的地理位置以及農(nóng)機(jī)信息。結(jié)合復(fù)雜的農(nóng)業(yè)環(huán)境與訂單需求，本研究做出假設(shè)：（1） 每臺(tái)農(nóng)機(jī)可以服務(wù)多個(gè)農(nóng)田點(diǎn)，每個(gè)農(nóng)田點(diǎn)只能由一臺(tái)農(nóng)機(jī)服務(wù)。（2） 農(nóng)機(jī)轉(zhuǎn)移速度恒定，作業(yè)效率恒定，暫不考慮轉(zhuǎn)移與作業(yè)過(guò)程的農(nóng)機(jī)故障、農(nóng)機(jī)加油情況。（3） 農(nóng)機(jī)從同一農(nóng)機(jī)站點(diǎn)出發(fā)完成所分配的緊急任務(wù)之后返回原農(nóng)機(jī)站點(diǎn)。（4） 暫不考慮農(nóng)機(jī)的卸糧時(shí)間、機(jī)手的非工作時(shí)間。

1.2 調(diào)配模型建立

針對(duì)上述分析，對(duì)緊急調(diào)配問(wèn)題進(jìn)行形式化描述。

1） 農(nóng)田信息。集合A=｛a1，a2，…，am｝表示m塊農(nóng)田，任意農(nóng)田可以表示為ai=｛si，lngi，lati｝，其中，si表示農(nóng)田i的面積，lngi和lati分別表示農(nóng)田i的經(jīng)緯度信息。

2） 農(nóng)機(jī)信息。集合B=｛b1，b2，…，bn｝表示n臺(tái)農(nóng)機(jī)，v表示農(nóng)機(jī)轉(zhuǎn)移速度，km/h；w表示農(nóng)機(jī)作業(yè)效率，hm2/h；dij表示農(nóng)機(jī)從農(nóng)田i到農(nóng)田j的轉(zhuǎn)移距離。

3） 決策變量。[xki]為農(nóng)田的收割狀態(tài)，如果農(nóng)機(jī)k完成了農(nóng)田i的收割任務(wù)，其值為1，否則為0。[ykij]為農(nóng)機(jī)的轉(zhuǎn)移狀態(tài)，如果農(nóng)機(jī)k從農(nóng)田i轉(zhuǎn)移到農(nóng)田j，其值為1，否則為0。trule表示農(nóng)機(jī)緊急調(diào)配限定時(shí)間。

調(diào)配目標(biāo)為

[minL=total S-fact S] （1）

[total S=i=1msi] （2）

[fact S=i=1msixki] （3）

約束條件為

[fact S≤total S] （4）

[i=1mi=jmdijykijv+1w（i=1msixki）≤trule] （5）

式（1）表示農(nóng)機(jī)緊急調(diào)配的糧食損失值；式（2）表示應(yīng)收糧食總量；式（3）表示實(shí)收糧食總量；式（4）表示實(shí)收糧食總量應(yīng)≤應(yīng)收糧食總量；式（5）表示農(nóng)機(jī)k完成所分配任務(wù)所用時(shí)間不能超過(guò)緊急任務(wù)的截止時(shí)間。

2 問(wèn)題求解與算法設(shè)計(jì)

2.1 傳統(tǒng)農(nóng)機(jī)調(diào)配算法

隨著對(duì)農(nóng)機(jī)調(diào)配問(wèn)題分析和研究的深入，遺傳算法GA、模擬退火算法SA等智能優(yōu)化算法被廣泛應(yīng)用，且在不同的作業(yè)情境下取得了良好的效果。

1） 遺傳算法。遺傳算法是將要解決的問(wèn)題模擬成一個(gè)生物進(jìn)化過(guò)程，每個(gè)個(gè)體都有對(duì)環(huán)境的適應(yīng)程度，一定數(shù)量的個(gè)體組成了一個(gè)種群，通過(guò)選擇、交叉、變異等操作產(chǎn)生新一代種群，根據(jù)“物競(jìng)天擇，適者生存”的思想，并逐步淘汰適應(yīng)度低的個(gè)體，最終生成符合優(yōu)化目標(biāo)的個(gè)體［13?15］。

遺傳算法緊急調(diào)配流程如下：Step1：編碼。先對(duì)農(nóng)田點(diǎn)進(jìn)行隨機(jī)排序，直接產(chǎn)生調(diào)度路徑，如有10個(gè)農(nóng)田任務(wù)點(diǎn)，染色體編碼可能就是：3-2-6-8-0-9-10-1-0-7-4-5，其中0代表從此處切割分為三條調(diào)配路徑，第一臺(tái)農(nóng)機(jī)的調(diào)度路徑為3-2-6-8，第二臺(tái)農(nóng)機(jī)的調(diào)度路徑為9-10-1，第三臺(tái)農(nóng)機(jī)的調(diào)配路徑為7-4-5；Step2：初始化種群。編碼之后，根據(jù)所設(shè)置的種群規(guī)模參數(shù)隨機(jī)生成對(duì)應(yīng)規(guī)模的初始化種群；Step3：適應(yīng)度函數(shù)。按照目標(biāo)函數(shù)值計(jì)算適應(yīng)度去評(píng)價(jià)可行解的優(yōu)劣；Step4：選擇操作。采用精英選擇法和輪盤(pán)賭選擇法相結(jié)合，首先選取若干適應(yīng)度最大個(gè)體直接放入下一代種群，然后用輪盤(pán)賭選擇法將下一代種群數(shù)量填充至種群規(guī)模；Step5：交叉操作。隨機(jī)挑選2個(gè)不同的個(gè)體作為父代，然后生成一個(gè)（0，1）之間的隨機(jī)數(shù)r，如果r大于預(yù)先設(shè)置的交叉概率，2個(gè)父代不進(jìn)行交叉操作，直接放入到下一代種群中，反之，則執(zhí)行交叉操作，隨機(jī)選擇父代1中2個(gè)基因的起止位置，生成子代1，并保證子代中被選擇的基因的位置與父代相同，將父代2中不屬于子代1的基因按照順序依次填充到子代1中，生成完整的子代1，另一個(gè)子代生成過(guò)程完全相同，只需交換兩個(gè)父代的位置。重復(fù)此過(guò)程至下一代種群數(shù)量達(dá)到種群規(guī)模；Step6：變異操作。生成一個(gè)（0，1）之間的隨機(jī)數(shù)r，如果r大于預(yù)先設(shè)置的變異概率，此個(gè)體不進(jìn)行變異操作，直接放入到下一代中，反之，則將此個(gè)體執(zhí)行變異操作，隨機(jī)選擇2個(gè)不同的基因，交換這2個(gè)基因的位置產(chǎn)生新個(gè)體，放入到下一代中。重復(fù)此過(guò)程至遍歷完此代中的所有個(gè)體；Step7：重復(fù)Step4、Step5、Step6至達(dá)到算法進(jìn)化次數(shù)。

2） 模擬退火算法。模擬退火算法是模仿物理學(xué)中金屬固體退火過(guò)程而提出的一種組合優(yōu)化算法，其物理退火過(guò)程主要分為加溫過(guò)程、等溫過(guò)程和降溫過(guò)程。加溫過(guò)程對(duì)應(yīng)算法中初始溫度的設(shè)定。降溫過(guò)程對(duì)應(yīng)算法中控制參數(shù)的下降過(guò)程，即外循環(huán)。等溫過(guò)程對(duì)應(yīng)算法中的內(nèi)循環(huán)，其中Metropolis抽樣過(guò)程是算法的關(guān)鍵所在，如果新個(gè)體的適應(yīng)度大于舊個(gè)體則直接保留放入下一代中，反之則概率性的接收新個(gè)體［16?18］。

模擬退火算法緊急調(diào)配流程如下：Step1：升溫操作。設(shè)置初始溫度T0、等溫迭代參數(shù)K以及對(duì)農(nóng)田點(diǎn)進(jìn)行隨機(jī)排序生成初試解；Step2：等溫過(guò)程。隨機(jī)交換兩個(gè)農(nóng)田點(diǎn)的位置生成新解，用Metropolis準(zhǔn)則概率性的接收新解。迭代K次；Step3：降溫過(guò)程。降低初始溫度T0；Step4：重復(fù)Step2和Step3至終止溫度。

2.2 基于兩階段的農(nóng)機(jī)緊急調(diào)配算法

TSEA算法流程如圖1所示。

傳統(tǒng)農(nóng)機(jī)調(diào)配研究多為算法改進(jìn)工作，往往直接使用改進(jìn)的算法得出調(diào)配方案，雖能給出具體可行的調(diào)配方案，但隨著農(nóng)田規(guī)模的擴(kuò)大，所給出解的質(zhì)量明顯下降，且求解算法所需時(shí)間也會(huì)呈指數(shù)上升。因此，本文提出基于兩階段的農(nóng)機(jī)緊急調(diào)配算法TSEA。算法分為兩個(gè)階段，首先根據(jù)農(nóng)田位置特點(diǎn)對(duì)大規(guī)模農(nóng)田進(jìn)行分區(qū)處理，接著以糧食損失值最小為目標(biāo)，調(diào)度可用農(nóng)機(jī)對(duì)各分區(qū)的農(nóng)田進(jìn)行緊急作業(yè)。

2.2.1 基于距離的分區(qū)策略

農(nóng)田分區(qū)階段采用基于距離的分區(qū)策略來(lái)處理大規(guī)模農(nóng)田劃分問(wèn)題，使用輪廓系數(shù)作為聚類分區(qū)結(jié)果的評(píng)價(jià)指標(biāo)，從而確定農(nóng)田分區(qū)的個(gè)數(shù)。輪廓系數(shù)是評(píng)價(jià)聚類結(jié)果優(yōu)劣的一種重要方式。本文將輪廓系數(shù)定義如式（6）所示。SC為聚類總的輪廓系數(shù)，數(shù)值越大代表同一分區(qū)內(nèi)農(nóng)田分布越密集，不同分區(qū)內(nèi)農(nóng)田距離越遠(yuǎn)，即農(nóng)田聚類分區(qū)效果越好。

[Si=Bi-Aimax（Ai，Bi）] （6）

[SC=1Ni=1NSi] （7）

式中： Ai——農(nóng)田點(diǎn)i與所在分區(qū)內(nèi)其他農(nóng)田點(diǎn)的平" " " " " " " " "均距離；

Bi——與其他分區(qū)內(nèi)農(nóng)田點(diǎn)的平均距離；

N——農(nóng)田總數(shù)；

Si——農(nóng)田點(diǎn)i的輪廓系數(shù)。

基于距離的分區(qū)策略具體步驟如下：Step1：將大規(guī)模農(nóng)田默認(rèn)分成K'個(gè)分區(qū)，首次分區(qū)K'取值為2；Step2：在大規(guī)模農(nóng)田區(qū)域內(nèi)隨機(jī)選取K'個(gè)位置作為初始的聚類中心；Step3：計(jì)算每個(gè)農(nóng)田點(diǎn)與聚類中心之間的距離，把每個(gè)農(nóng)田點(diǎn)分配給離它最近的聚類中心。這樣，聚類中心以及分配給它們的農(nóng)田點(diǎn)就組成一個(gè)分區(qū)；Step4：根據(jù)各分區(qū)內(nèi)農(nóng)田點(diǎn)的位置，計(jì)算均值并取之位置作為新的聚類中心；Step5：重復(fù)Step3和Step4，直到聚類中心的位置不再改變，完成聚類；Step6：計(jì)算本次聚類結(jié)果的輪廓系數(shù)記為SCk；Step7：重復(fù)步驟Step1到Step5，計(jì)算K'+1以及K'+2的輪廓系數(shù)記為SCk1和SCk2；Step8：如果SCk1和SCk2均小于SCk，則確定大規(guī)模農(nóng)田分區(qū)個(gè)數(shù)為k，保留分區(qū)方案進(jìn)行接下來(lái)的農(nóng)機(jī)緊急調(diào)配工作。否則，將k+1，重復(fù)Step1到Step7。

2.2.2 區(qū)域內(nèi)多機(jī)緊急調(diào)配算法

基于距離的分區(qū)策略將大規(guī)模農(nóng)田分區(qū)后，下一步將研究各區(qū)域內(nèi)的農(nóng)機(jī)緊急作業(yè)調(diào)配。本文以糧食損失值最小化為目標(biāo)，根據(jù)緊急調(diào)配問(wèn)題的特點(diǎn)以及遺傳算法中存在的不足，對(duì)遺傳算法的編碼、解碼以及變異操作進(jìn)行改進(jìn)，使用改進(jìn)的遺傳算法進(jìn)行問(wèn)題的求解。

1） 改進(jìn)的編碼和解碼操作。在使用遺傳算法解決調(diào)度問(wèn)題時(shí)，確定染色體的編碼方式是一項(xiàng)非常重要的工作，直接決定算法的實(shí)現(xiàn)難度以及性能的優(yōu)劣。傳統(tǒng)算法直接插入分割點(diǎn)的編碼方式可能會(huì)出現(xiàn)某臺(tái)農(nóng)機(jī)完成所分配任務(wù)時(shí)長(zhǎng)會(huì)超出緊急任務(wù)截止時(shí)間的約束，根本不符合實(shí)際情況。本文提出一種全新的染色體編碼方案，染色體編碼方式是一條總的任務(wù)路徑，并不是開(kāi)始直接給出每一臺(tái)農(nóng)機(jī)的調(diào)度路徑，而是在算法每一次迭代的過(guò)程中以緊急任務(wù)截止時(shí)間為約束條件再進(jìn)行路徑分割給出具體每臺(tái)農(nóng)機(jī)的任務(wù)路徑，保證每條調(diào)度路徑的真實(shí)性和可行性。

染色體的編碼方式步驟：（1）對(duì)服務(wù)區(qū)所有農(nóng)田點(diǎn)進(jìn)行隨機(jī)排序，即對(duì)每個(gè)農(nóng)田點(diǎn)賦值唯一的編號(hào)；（2）每個(gè)區(qū)域分別執(zhí)行各自的農(nóng)機(jī)緊急調(diào)配操作；（3）將區(qū)域內(nèi)的所有農(nóng)田點(diǎn)連接構(gòu)成一條完整的染色體，這個(gè)染色體就是該區(qū)域所需農(nóng)機(jī)的緊急調(diào)配方案，后續(xù)根據(jù)緊急任務(wù)截止時(shí)間約束將該染色體分割，形成具體每一臺(tái)農(nóng)機(jī)的緊急調(diào)配方案。

以某一區(qū)域?yàn)槔?，設(shè)區(qū)域1中共有7個(gè)農(nóng)田點(diǎn)，將區(qū)域內(nèi)所有農(nóng)田點(diǎn)隨機(jī)排序形成一條完整的染色體：3-5-1-7-2-4-6，之后的迭代過(guò)程中，首選派遣第1臺(tái)農(nóng)機(jī)，從農(nóng)機(jī)站點(diǎn)出發(fā)，根據(jù)距離和農(nóng)機(jī)的行駛速度，計(jì)算到達(dá)農(nóng)田點(diǎn)3的路程時(shí)間；再根據(jù)農(nóng)田點(diǎn)3的農(nóng)田面積以及農(nóng)機(jī)的工作效率，計(jì)算要完成農(nóng)田點(diǎn)3所需的工作時(shí)長(zhǎng)，判斷農(nóng)田點(diǎn)3是否超出緊急任務(wù)截止時(shí)間，如果沒(méi)有超過(guò)，則把農(nóng)田點(diǎn)5加入到第1臺(tái)農(nóng)機(jī)的調(diào)度路徑，繼續(xù)判斷是否超出緊急任務(wù)截止時(shí)間，再將農(nóng)田作業(yè)點(diǎn)1加入，然后再判斷，若仍不超過(guò)，繼續(xù)將農(nóng)田點(diǎn)7加入，再次判斷。設(shè)此時(shí)超出緊急任務(wù)截止時(shí)間，說(shuō)明農(nóng)田7不能加入到調(diào)配路徑，于是得到了第一臺(tái)農(nóng)機(jī)的緊急調(diào)配方案，繼續(xù)重復(fù)執(zhí)行此操作。得到區(qū)域1的農(nóng)機(jī)調(diào)配方案，如：0-3-5-1-0，0-7-2-4-6-0，0-3-5-1-0表示農(nóng)機(jī)站點(diǎn)中的第1臺(tái)農(nóng)機(jī)從站點(diǎn)出發(fā)依次完成農(nóng)田點(diǎn)3，5，1的收割任務(wù)之后返回該站點(diǎn)，0-7-2-4-6-0表示農(nóng)機(jī)站中的第2臺(tái)農(nóng)機(jī)從站點(diǎn)出發(fā)依次完成農(nóng)田點(diǎn)7，2，4，6的收割任務(wù)后返回站點(diǎn)。

2） 改進(jìn)的變異操作。傳統(tǒng)變異操作沒(méi)有考慮新個(gè)體適應(yīng)度的影響，新個(gè)體無(wú)論優(yōu)劣都會(huì)被直接放入到下一代中，使得算法收斂速度變慢甚至產(chǎn)生種群退化。本文在變異操作中引入模擬退火算法SA中的Metropolis準(zhǔn)則，完成對(duì)傳統(tǒng)變異操作的改進(jìn)，如式（8）所示。

[pz=1E（Xafter）gt;E（Xbefore）exp-E（Xafter）-E（Xbefore）TE（Xafter）≤E（Xbefore）] （8）

式中： E（Xbefore）——原解；

E（Xafter）——新解；

T——溫度系數(shù)。

因Metropolis準(zhǔn)則中的T隨著溫度的降低是不斷減小的，因此本文使用算法迭代次數(shù)的倒數(shù)替換T以達(dá)到同樣的目的。新的變異操作不再需要人為設(shè)置變異概率，具體操作步驟：（1）選取上一代中第一個(gè)個(gè)體，隨機(jī)選擇其中2個(gè)不同的基因，交換這2個(gè)基因的位置產(chǎn)生新個(gè)體；（2）比較變異前后2個(gè)個(gè)體的適應(yīng)度，如果變異之后的個(gè)體適應(yīng)度高，則直接放入下一代，如果變異之前的個(gè)體適應(yīng)度高，則生成一個(gè)（0，1）之間的隨機(jī)數(shù)r；（3）如果pzgt;r，接受變異之后的個(gè)體放入到下一代中，反之，則接受變異之前的個(gè)體。

改進(jìn)后的算法與傳統(tǒng)的算法相比，編碼和解碼方式是全新的，滿足所有約束條件，符合緊急調(diào)配實(shí)際情況。并且引入了Metropolis的變異策略使算法隨著迭代次數(shù)的增加，接受適應(yīng)度較差個(gè)體的概率變低，保證種群穩(wěn)定進(jìn)化的同時(shí)也不會(huì)使算法陷入局部最優(yōu)。改進(jìn)后的遺傳算法流程如圖2所示。

3 試驗(yàn)驗(yàn)證與分析

3.1 試驗(yàn)數(shù)據(jù)準(zhǔn)備

本文在河北省保定市（東經(jīng)113.4°～116.2°，北緯38.1°～40°）境內(nèi)隨機(jī)生成農(nóng)田位置與農(nóng)機(jī)站點(diǎn)位置信息進(jìn)行模擬仿真試驗(yàn)并對(duì)試驗(yàn)數(shù)據(jù)做出如下假設(shè)：（1） 在河北省保定市境內(nèi)，隨機(jī)生成100個(gè)農(nóng)田點(diǎn)以及1個(gè)農(nóng)機(jī)站點(diǎn)數(shù)據(jù)，包括農(nóng)田的經(jīng)緯度、地塊面積（0.30.6 hm2）以及農(nóng)機(jī)站點(diǎn)的經(jīng)緯度信息，農(nóng)機(jī)站點(diǎn)與農(nóng)田信息如表1所示。（2） 設(shè)農(nóng)機(jī)保有量為16，需要在8 h內(nèi)調(diào)配所擁有農(nóng)機(jī)完成糧食緊急搶收工作。（3） 設(shè)農(nóng)機(jī)行駛速度為30 km/h，農(nóng)機(jī)作業(yè)能力為3 335 m2/h。

3.2 算法對(duì)比分析

為驗(yàn)證本文所提算法的有效性，采用TSEA、GA、SA算法分別對(duì)該試驗(yàn)數(shù)據(jù)各進(jìn)行10次測(cè)試。表2、表3、表4分別記錄3種算法10次試驗(yàn)中最優(yōu)的農(nóng)機(jī)緊急調(diào)配方案。表5分別記錄每種算法10次試驗(yàn)結(jié)果的平均糧食損失值以及平均算法運(yùn)行時(shí)間，在這兩個(gè)方面對(duì)3種算法進(jìn)行比較。

通過(guò)算法TSEA計(jì)算出的糧食損失值、算法運(yùn)行時(shí)間分別記為L(zhǎng)osst、Timet；通過(guò)算法GA計(jì)算出的糧食損失值、算法運(yùn)行時(shí)間分別記為L(zhǎng)ossg、Timeg；通過(guò)算法SA計(jì)算出的糧食損失值、算法運(yùn)行時(shí)間分別記為L(zhǎng)osss、Times。Ratio1指算法TSEA的糧食損失值比GA糧食損失值的下降比例，Ratio2指算法TSEA的糧食損失值比SA糧食損失值的下降比例；Ratio3指算法TSEA的算法運(yùn)行時(shí)間比GA算法運(yùn)行時(shí)間的下降比例，Ratio4指算法TSEA的算法運(yùn)行時(shí)間比SA算法運(yùn)行時(shí)間的下降比例。具體定義如式（9）～式（12）所示。

[Ratio1=Lossg-LosstLossg] （9）

[Ratio2=Losss-LosstLosss] （10）

[Ratio3=Timeg-TimetLossg] （11）

[Ratio4=Times-TimetLosss] （12）

從表5可知，在可用農(nóng)機(jī)為16的情況下， TSEA算法的糧食損失值比GA算法的降低了16.33%，比SA算法的降低了17.21%；算法的平均運(yùn)行時(shí)間比GA算法的降低了39.61%，比SA算法的降低了37.75%。即在可用農(nóng)機(jī)相同的情況下，TSEA算法可以完成更多的農(nóng)田收割任務(wù)，從而減少更多的糧食損失值，且算法運(yùn)行效率有明顯提升，驗(yàn)證了TSEA算法的有效性和優(yōu)越性。

3.3 試驗(yàn)分析

由于TSEA算法包含分區(qū)和調(diào)配兩個(gè)階段，為進(jìn)一步驗(yàn)證TSEA算法中分區(qū)策略的有效性，將完整的TSEA算法與不分區(qū)直接使用其中的調(diào)配算法進(jìn)行比較。使用完整的TSEA算法進(jìn)行緊急調(diào)配求解的模式記為分區(qū)模式；不分區(qū)直接使用其中區(qū)域內(nèi)多機(jī)緊急調(diào)配算法進(jìn)行緊急調(diào)配求解的模式記為不分區(qū)模式。依舊在河北省保定市隨機(jī)生成1組150塊農(nóng)田試驗(yàn)數(shù)據(jù)與200塊農(nóng)田試驗(yàn)數(shù)據(jù)，緊急任務(wù)限定時(shí)間仍為8 h。應(yīng)用不同數(shù)量的可用農(nóng)機(jī)分別從糧食損失值與算法運(yùn)行時(shí)間兩方面來(lái)對(duì)分區(qū)模式與不分區(qū)模式進(jìn)行比較，比較結(jié)果如表6所示。

由表6可知，在農(nóng)田數(shù)量為150塊，可用農(nóng)機(jī)為27臺(tái)時(shí)，分區(qū)模式的糧食損失值比不分區(qū)模式的降低了23.21%，算法運(yùn)行時(shí)間減少了42.86%；可用農(nóng)機(jī)為28臺(tái)時(shí)，不分區(qū)模式會(huì)造成糧食損失值，而分區(qū)模式則可以完成所有農(nóng)田的糧食搶收工作，不會(huì)出現(xiàn)糧食損失值，并且算法運(yùn)行時(shí)間遠(yuǎn)遠(yuǎn)小于不分區(qū)模式。通過(guò)農(nóng)田數(shù)量為200塊，可用農(nóng)機(jī)為37臺(tái)的調(diào)配結(jié)果進(jìn)一步驗(yàn)證了此結(jié)論，證明了TSEA算法中分區(qū)策略的有效性。

4 結(jié)論

利用聚類分析和遺傳算法研究面向大規(guī)模農(nóng)田的農(nóng)機(jī)緊急調(diào)配問(wèn)題，提出先分區(qū)再調(diào)配的兩階段農(nóng)機(jī)緊急調(diào)配算法TSEA，并通過(guò)多組試驗(yàn)驗(yàn)證算法的有效性。

1） TSEA算法的分區(qū)階段采用基于距離的分區(qū)策略，將大規(guī)模農(nóng)田進(jìn)行分區(qū)處理，減小問(wèn)題規(guī)模和計(jì)算復(fù)雜性。

2） TSEA算法農(nóng)機(jī)緊急調(diào)配階段以糧食損失值最小化為目標(biāo)，建立農(nóng)機(jī)緊急調(diào)配數(shù)學(xué)模型，并使用改進(jìn)的遺傳算法對(duì)問(wèn)題進(jìn)行計(jì)算求解。將TSEA算法分別與GA算法、SA算法進(jìn)行多組試驗(yàn)分析比較。結(jié)果表明TSEA算法的糧食損失值比GA算法的降低16.33%，比SA算法的降低17.21%；算法的平均運(yùn)行時(shí)間比GA算法降低39.61%，比SA算法降低37.75%，驗(yàn)證TSEA算法整體的有效性和優(yōu)越性。

3） 將完整TSEA算法與不分區(qū)直接使用其中的調(diào)配算法進(jìn)行多組試驗(yàn)分析比較。結(jié)果顯示，可用農(nóng)機(jī)為27臺(tái)時(shí)，分區(qū)模式比不分區(qū)模式的糧食損失值降低23.21%，算法運(yùn)行時(shí)間減少42.86%；可用農(nóng)機(jī)為28臺(tái)時(shí)，不分區(qū)模式會(huì)造成糧食損失值，而分區(qū)模式則可以完成所有農(nóng)田的糧食搶收工作，驗(yàn)證分區(qū)策略的有效性。

參 考 文 獻(xiàn)

[ 1 ] Seyyedhasani H， Dvorak J S， Roemmele E. Routing algorithm selection for field coverage planning based on field shape and fleet size [J]. Computers and Electronics in Agriculture， 2019， 156： 523-529.

[ 2 ] 王雪陽(yáng)， 苑侗侗， 苑迎春， 等. 帶時(shí)間窗的農(nóng)機(jī)調(diào)度方法研究[J]. 河北農(nóng)業(yè)大學(xué)學(xué)報(bào)， 2016， 39（6）： 117-123.

Wang Xueyang， Yuan Tongtong， Yuan Yingchun， et al. A study on method of agricultural scheduling with time?window [J]. Journal of Agricultural University of Hebei， 2016， 39（6）： 117-123.

[ 3 ] 張璠， 滕桂法， 馬建斌， 等. 基于啟發(fā)式優(yōu)先級(jí)規(guī)則的農(nóng)機(jī)調(diào)配算法[J]. 農(nóng)業(yè)工程學(xué)報(bào)， 2012， 28（10）： 78-85.

Zhang Fan， Teng Guifa， Ma Jianbin， et al. Farm machinery scheduling and allocating based on heuristic priority rules [J]. Transactions of the Chinese Society of Agricultural Engineering， 2012， 28（10）： 78-85.

[ 4 ] 張帆， 羅錫文， 張智剛， 等. 基于改進(jìn)多父輩遺傳算法的農(nóng)機(jī)調(diào)度優(yōu)化方法[J]. 農(nóng)業(yè)工程學(xué)報(bào)， 2021， 37（9）： 192-198.

Zhang Fan， Luo Xiwen， Zhang Zhigang， et al. Agricultural machinery scheduling optimization method based on improved multi?parents genetic algorithm [J]. Transactions of the Chinese Society of Agricultural Engineering， 2021， 37（9）： 192-198.

[ 5 ] 南風(fēng). 小麥機(jī)收任務(wù)分配與收運(yùn)協(xié)同調(diào)度優(yōu)化研究[D]. 北京： 中國(guó)農(nóng)業(yè)科學(xué)院， 2021.

[ 6 ] 李婷. 極端天氣下的農(nóng)機(jī)應(yīng)急調(diào)配仿真模型[J]. 科技通報(bào)， 2014， 30（12）： 193-195.

Li Ting. Simulation modeling of agricultural machinery emergency deployment under extreme weather [J]. Bulletin of Science and Technology， 2014， 30（12）： 193-195.

[ 7 ] 張璠， 滕桂法， 苑迎春， 等. 農(nóng)機(jī)跨區(qū)作業(yè)緊急調(diào)配算法適宜性選擇[J]. 農(nóng)業(yè)工程學(xué)報(bào)， 2018， 34（5）： 47-53.

Zhang Fan， Teng Guifa， Yuan Yingchun， et al. Suitability selection of emergency scheduling and allocating algorithm of agricultural machinery [J]. Transactions of the Chinese Society of Agricultural Engineering， 2018， 34（5）： 47-53.

[ 8 ] 高威. 農(nóng)機(jī)緊急調(diào)配技術(shù)研究[D]. 保定： 河北農(nóng)業(yè)大學(xué)， 2014.

[ 9 ] Cui S， Liu S， Tang X， et al. Emergency material allocation problem considering post?disaster impact [C]. 2019 8th International Conference on Industrial Technology and Management， IEEE， 2019： 290-294.

[10] Wang H， Du L， Ma S. Multi?objective open location?routing model with split delivery for optimized relief distribution in post?earthquake [J]. Transportation Research Part E： Logistics and Transportation Review， 2014， 69： 160-179.

[11] Vahdani B， Veysmoradi D， Noori F， et al. Two?stage multi?objective location?routing?inventory model for humanitarian logistics network design under uncertainty [J]. International journal of disaster risk reduction， 2018， 27： 290-306.

[12] Zhang J， Liu H， Yu G， et al. A three?stage and multi?objective stochastic programming model to improve the sustainable rescue ability by considering secondary disasters in emergency logistics [J]. Computers amp; Industrial Engineering， 2019， 135： 1145-1154.

[13] 張立毅， 高楊， 費(fèi)騰， 等. 求解旅行商問(wèn)題的搜尋者遺傳算法[J]. 數(shù)學(xué)的實(shí)踐與認(rèn)識(shí)， 2019， 49（7）： 115-122.

Zhang Liyi， Gao Yang， Fei Teng， et al. Seeker genetic algorithm solving traveling salesman problem [J]. Mathematics in Practice and Theory， 2019， 49（7）： 115-122.

[14] 張維， 馬志華， 楊洋洋， 等. 基于改進(jìn)遺傳模擬退火算法的刀具準(zhǔn)時(shí)化配送路徑規(guī)劃[J]. 現(xiàn)代制造工程， 2 020（10）： 83-90.

Zhang Wei， Ma Zhihua， Yang Yangyang， et al. Just?in?time tools distribution route planning based on improved genetic simulated annealing algorithm [J]. Modern Manufacturing Engineering， 2020（10）： 83-90.

[15] 陳磊， 霍永亮， 霍波陶. 基于混合遺傳算法的物流車輛調(diào)度優(yōu)化[J]. 重慶師范大學(xué)學(xué)報(bào)（自然科學(xué)版）， 2015， 32（2）： 7-12.

Chen Lei， Huo Yongliang， Huo Botao. Vehicle schedule optimization of logistics based on combinational genetic algorithm [J]. Journal of Chongqing Normal University （Natural Science）， 2015， 32（2）： 7-12.

[16] 陳科勝， 鮮思東， 郭鵬. 求解旅行商問(wèn)題的自適應(yīng)升溫模擬退火算法[J]. 控制理論與應(yīng)用， 2021， 38（2）： 245-254.

Chen Kesheng， Xian Sidong， Guo Peng. Adaptive temperature rising simulated annealing algorithm for traveling salesman problem [J]. Control Theory amp; Applications， 2021， 38（2）： 245-254.

[17] 馬晗， 常安定， 陳童， 等. 基于文化混合優(yōu)化算法的旅行商問(wèn)題求解[J]. 計(jì)算機(jī)工程與科學(xué)， 2019， 41（7）： 1273-1278.

Ma Han， Chang Anding， Chen Tong， et al. A hybrid culture algorithm optimization strategy for traveling salesman problem [J]. Computer Engineering amp; Science， 2019， 41（7）： 1273-1278.

[18] 李景文， 李旭， 姜建武， 等. 改進(jìn)模擬退火算法在旅游路線定制中的應(yīng)用[J]. 科學(xué)技術(shù)與工程， 2020， 20（26）： 10808-10814.

Li Jingwen， Li Xu， Jiang Jianwu， et al. Application of improved simulated annealing algorithm in tourism route customization [J]. Science Technology and Engineering， 2020， 20（26）： 10808-10814.