帶時間窗的多目標(biāo)農(nóng)機跨區(qū)協(xié)同作業(yè)調(diào)度方法研究

摘要：由于缺少科學(xué)合理的優(yōu)化調(diào)度策略，在農(nóng)收季節(jié)多機跨區(qū)作業(yè)常常出現(xiàn)作業(yè)成本高、作業(yè)效率低、無法在適宜作業(yè)的時間內(nèi)完成農(nóng)田任務(wù)等情況。針對此問題，在作業(yè)時間窗的約束下，以農(nóng)機作業(yè)轉(zhuǎn)移距離最短、調(diào)度總成本最低為目標(biāo)，構(gòu)建多機多目標(biāo)跨區(qū)協(xié)同作業(yè)調(diào)度模型，設(shè)計基于優(yōu)先級策略的多目標(biāo)自適應(yīng)優(yōu)化調(diào)度算法（APRMOGA）。采用雙層編碼方式對基因進行編碼，按照時間窗優(yōu)先級規(guī)則依次分配聯(lián)合收割機進行作業(yè)，產(chǎn)生初始種群；設(shè)計基于雙層編碼的時間窗優(yōu)先級順序交叉方法，優(yōu)先保留開始作業(yè)時間早的基因，結(jié)合自適應(yīng)變異概率和精英策略對個體進行選擇變換，得到全局最優(yōu)的Pareto解集。選取河北省內(nèi)某地區(qū)24塊農(nóng)田進行試驗驗證，結(jié)果表明：APRMOGA算法運行效率要高于NSGA-Ⅱ算法；通過APRMOGA算法計算得到的聯(lián)合收割機作業(yè)轉(zhuǎn)移距離和調(diào)度總成本比NSGA-Ⅱ算法分別下降23.60%、13.72%。

關(guān)鍵詞：農(nóng)機；時間窗優(yōu)先級策略；多目標(biāo)優(yōu)化；路徑規(guī)劃

中圖分類號：TP391" " " 文獻標(biāo)識碼：A" " " 文章編號：2095?5553 （2024） 10?0184?09

Research on multi?objective cross?area collaborative operation scheduling method of

agricultural machinery with time window

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

（1. College of Information Science and Technology， Hebei Agricultural University， Baoding， 071000， China;

2. Key Laboratory of Agricultural Big Data of Hebei Province， Baoding， 071000， China;

3. Software Engineering Department， Hebei Software Institute， Baoding， 071000， China;

4. College of Continuing Education， Hebei Agricultural University， Baoding， 071000， China）

Abstract： Due to the lack of scientific and reasonable optimization and scheduling strategies， multi?machine cross?regional operations during the agricultural harvest season often result in high operational costs， low operation efficiency and the inability to complete field tasks within the optimal time frame. In order to address this issue， a multi?machine and multi?objective cross?regional collaborative operation scheduling model was constructed， targeting the shortest transfer distance for agricultural machinery and the lowest total scheduling cost under the constraint of operation time windows. A multi?objective adaptive priority?based optimization scheduling algorithm （APRMOGA） was designed. The genes were encoded by" dual?layer encoding method， the combine harvesters were assigned successively for operation according to time window priority rules to generate the initial population. A time window priority sequence crossover method based on dual?layer encoding was designed to preferentially retain genes with earlier start times. This is combined with adaptive mutation probability and elitism strategies to select and transform individuals， and obtain the globally optimal Pareto solution set. An experiment was conducted by using 24 fields in a certain region of Hebei Province for verification. The results indicated that the operational efficiency of the APRMOGA algorithm was higher than that of the NSGA-II algorithm. The transfer distance and total scheduling cost of combine harvesters calculated by the APRMOGA algorithm were reduced by 23.60% and 13.72%， respectively， compared to the NSGA-II algorithm.

Keywords： agricultural machinery; time window prioritization strategy; multi?objective optimization; path planning

0 引言

農(nóng)業(yè)機械化是我國農(nóng)業(yè)發(fā)展的必經(jīng)之路，但我國耕地資源存在劃分細(xì)碎、經(jīng)營管理分散等問題限制了農(nóng)業(yè)機械化發(fā)展[1]。以聯(lián)合收割機跨區(qū)域作業(yè)為代表的農(nóng)機跨區(qū)協(xié)同作業(yè)解決了小規(guī)模經(jīng)營與大規(guī)模機械化作業(yè)之間的矛盾[2]。農(nóng)機跨區(qū)協(xié)同作業(yè)能夠有效提高農(nóng)機利用效率和作業(yè)質(zhì)量、滿足農(nóng)戶需求、推動農(nóng)業(yè)機械化水平發(fā)展。在農(nóng)忙季節(jié)，多機跨區(qū)域協(xié)同作業(yè)調(diào)度通常需要滿足作業(yè)成本最小化、作業(yè)效率最大化、行駛總路徑最短、作業(yè)總時長最小等多個優(yōu)化目標(biāo)。研究多機多目標(biāo)協(xié)同作業(yè)優(yōu)化調(diào)度問題，調(diào)配多輛農(nóng)機協(xié)同作業(yè)并使多個目標(biāo)值都達到最優(yōu)，可為農(nóng)機合作社、農(nóng)機管理部門等提供合理的調(diào)度策略，從而提高農(nóng)機作業(yè)質(zhì)量與作業(yè)效率、節(jié)省作業(yè)時間與成本。

目前國外關(guān)于多目標(biāo)跨區(qū)域農(nóng)機調(diào)度的研究相對較少，現(xiàn)有研究多集中于農(nóng)機田間作業(yè)路徑規(guī)劃。Zheng[3]綜合考慮農(nóng)機作業(yè)時長、農(nóng)機作業(yè)成本和作業(yè)質(zhì)量等多個優(yōu)化目標(biāo)，設(shè)計了基于時間窗的多目標(biāo)粒子群優(yōu)化算法，采用自適應(yīng)網(wǎng)格法和輪盤賭選擇法來選擇粒子，提高了農(nóng)機作業(yè)調(diào)度效率。Cong等[4]針對使用NSGA-II算法解決多無人機協(xié)同執(zhí)行檢測任務(wù)時存在容易陷入局部最優(yōu)解且運行效率低等問題，建立檢測利潤最大、能耗和飛行距離最低的多目標(biāo)優(yōu)化函數(shù)，提出TS-NSGA-II算法。結(jié)合禁忌搜索算法將獲得的新種群添加到NSGA-II算法的精英保留策略中，與NSGA-II算法相比，TS-NSGA-II算法可以獲得更好的帕累托解，在收斂方面具有顯著的優(yōu)勢。Mahmud等[5]為解決溫室內(nèi)農(nóng)藥噴灑作業(yè)的多目標(biāo)路徑規(guī)劃問題，采用NSGA-Ⅲ算法，對機器人行駛距離和行駛路徑角度進行優(yōu)化，有效降低了機器人作業(yè)路徑成本。Wang等[6]針對存在障礙物的無人機路徑規(guī)劃中傳統(tǒng)遺傳算法存在局部搜索能力較差容易過早收斂的問題，基于NSGA-Ⅱ算法，采用自適應(yīng)調(diào)整交叉概率和變異概率，設(shè)計定向凸變策略取代隨機突變機制，有效降低陷入局部最優(yōu)的風(fēng)險，提高了算法的收斂速度。

近年來，國內(nèi)對多目標(biāo)多機協(xié)同作業(yè)調(diào)度技術(shù)研究逐漸成為熱點，在運輸車、無人機等領(lǐng)域開展了相關(guān)研究。曹光喬等[7]考慮農(nóng)田內(nèi)病蟲害的侵染狀況，對訂單排序并進行調(diào)度作業(yè)，采用非支配排序遺傳算法對農(nóng)用無人機多目標(biāo)作業(yè)路徑進行規(guī)劃。Wang等[8]為突破同類型無人機作業(yè)時多目標(biāo)優(yōu)化問題的局限性，綜合考慮傳統(tǒng)粒子群算法的收斂性和粒子分布問題，設(shè)計多層編碼策略和約束調(diào)度方法，并改進解的評價方法，合理保留一些特殊邊界解，與傳統(tǒng)算法相比，該方法可以更好的處理約束，提高解的質(zhì)量。鄭彥輝等[9]為提高應(yīng)急物資管理，構(gòu)建非合作博弈環(huán)境下的應(yīng)急物資調(diào)配雙目標(biāo)優(yōu)化模型，設(shè)計NSGA-Ⅱ算法求解最佳調(diào)度方案。王芳等[10]在遺傳算法中引入模擬退火算法中的自適應(yīng)接受準(zhǔn)則，求得多目標(biāo)優(yōu)化蔬菜配送路徑。上述多目標(biāo)協(xié)同作業(yè)調(diào)度研究多集中在應(yīng)急物資調(diào)配、物流配送、無人機作業(yè)調(diào)度等領(lǐng)域，對基于多目標(biāo)的農(nóng)機田間協(xié)同作業(yè)調(diào)度問題的研究較少。針對帶時間窗的農(nóng)機協(xié)同調(diào)度問題，將調(diào)度成本最低、調(diào)度農(nóng)機數(shù)量最少、作業(yè)準(zhǔn)時性最高作為優(yōu)化目標(biāo)，王文權(quán)[11]通過綜合調(diào)度成本函數(shù)將多目標(biāo)問題轉(zhuǎn)化為單目標(biāo)問題進行研究，基于改進插入式路徑構(gòu)造了啟發(fā)式算法和鄰域優(yōu)化技術(shù)的遺傳算法，提高了算法運行效率。呂云杰等[12]采用極差值法將多個目標(biāo)函數(shù)進行優(yōu)化組合，得到綜合目標(biāo)函數(shù)進行研究，設(shè)計符合農(nóng)田作業(yè)時間窗的染色體編碼方式，改進自適應(yīng)遺傳算子求解問題，降低了農(nóng)田維數(shù)變化問題的調(diào)度成本。南風(fēng)[13]以PFIH算法為基礎(chǔ)結(jié)合其他智能算法對跨區(qū)域轉(zhuǎn)移大規(guī)模訂單問題進行研究，通過對不同目標(biāo)賦予不同的權(quán)重將問題轉(zhuǎn)化為單目標(biāo)問題，有效優(yōu)化了作業(yè)效率和轉(zhuǎn)移距離。王猛等[14]設(shè)計了兩段式編碼、分組交叉算子和多種變異算子，提出了基于多變異分組遺傳算法的農(nóng)機多機協(xié)同作業(yè)任務(wù)分配方法，采用不同的代價權(quán)重進行任務(wù)分配仿真試驗。但實際生產(chǎn)過程中很難確定合理的權(quán)重系數(shù)來反應(yīng)實際問題的重要程度，而且農(nóng)田環(huán)境十分復(fù)雜很多優(yōu)化目標(biāo)之間存在沖突，一個目標(biāo)的優(yōu)化可能需要以其他目標(biāo)劣化作為代價，難以得出全局最優(yōu)解。

綜上所述，本文綜合考慮農(nóng)田作業(yè)時間窗、地塊位置、轉(zhuǎn)移成本等因素，研究以農(nóng)機轉(zhuǎn)移距離最短、調(diào)度總成本最低為目標(biāo)的多機跨區(qū)協(xié)同作業(yè)優(yōu)化調(diào)度問題。通過構(gòu)建多目標(biāo)調(diào)度模型，設(shè)計優(yōu)化調(diào)度算法，將兩個目標(biāo)視為同等重要，同時對兩個目標(biāo)進行優(yōu)化，提高作業(yè)效率，降低作業(yè)成本，為農(nóng)機合作社的多機協(xié)同作業(yè)提供科學(xué)可行的調(diào)度方案。

1 多目標(biāo)農(nóng)機跨區(qū)協(xié)同作業(yè)調(diào)度問題分析

1.1 問題描述

在已知農(nóng)田位置、作業(yè)面積、待作業(yè)農(nóng)田數(shù)量、農(nóng)田作業(yè)點的適宜作業(yè)時間窗（時間窗由該作業(yè)點最早適宜作業(yè)的開始時間和適宜完成任務(wù)的最晚時間組成）、農(nóng)機數(shù)量等信息的前提下，本文主要研究多機跨區(qū)協(xié)同作業(yè)優(yōu)化調(diào)度策略，即在農(nóng)田適宜作業(yè)時間窗的約束下，以農(nóng)機轉(zhuǎn)移距離最短、調(diào)度總成本最低為目標(biāo)，如何協(xié)同優(yōu)化調(diào)度同一農(nóng)機合作社的多臺聯(lián)合收割機（下文簡稱為農(nóng)機）到某市級行政區(qū)域內(nèi)的多塊農(nóng)田開展作業(yè)服務(wù)，具體如圖1所示。

農(nóng)機田間作業(yè)的真實環(huán)境與影響因素復(fù)雜多變，為便于研究現(xiàn)做出如下假設(shè)。

1） 農(nóng)機合作社的農(nóng)機類型與作業(yè)能力均相同，轉(zhuǎn)移過程中農(nóng)機速度恒定。

2） 本文中暫不考慮農(nóng)機故障情況。

3） 一個農(nóng)田作業(yè)點只允許一臺農(nóng)機進行作業(yè)服務(wù)。

4） 農(nóng)機完成當(dāng)前所在路徑全部作業(yè)任務(wù)后返回農(nóng)機合作社。

1.2 模型構(gòu)建

本文對相關(guān)變量做出以下描述。農(nóng)田作業(yè)點集合[N=1，2，3，…，i]，其中i為任一作業(yè)點。農(nóng)田面積集合[S=S1，S2，S3，…，Si]，Si為第i個農(nóng)田作業(yè)點作業(yè)面積（hm2），i[∈][1，24]。農(nóng)機集合[M=1，2，3，…，k]，其中k為任一農(nóng)機，其性能參數(shù)表示為[P=Pk，Vkt，Vko，Ckt，Ckw，Cko，Wki]。其中，Pk表示單位時間內(nèi)農(nóng)機作業(yè)效率，hm2/h；Vkt表示單位時間內(nèi)農(nóng)機非作業(yè)轉(zhuǎn)移行駛速度，km/h；Vko表示單位時間內(nèi)農(nóng)機作業(yè)行駛速度，km/h；Ckt表示單位距離內(nèi)農(nóng)機k的轉(zhuǎn)移成本，元/km；Ckw表示單位時間內(nèi)農(nóng)機等待作業(yè)的懲罰成本，元/h；Cko表示單位面積內(nèi)農(nóng)機k的作業(yè)成本，元/hm2；[Wki]表示農(nóng)機k在農(nóng)田i內(nèi)的等待總時長，h；k [∈][1，8]。[ρki]表示控制變量，當(dāng)[ρki]值為1時，表示農(nóng)機k在作業(yè)點i產(chǎn)生等待時間t，[ρki]值為0時，農(nóng)機k不產(chǎn)生等待時間。[Dkij]表示農(nóng)田間轉(zhuǎn)移距離，表示農(nóng)機k從農(nóng)田i出發(fā)到農(nóng)田j之間的轉(zhuǎn)移距離。TWi表示農(nóng)田i的作業(yè)時間窗。ei表示農(nóng)田i允許農(nóng)機進行作業(yè)的最早時間。li表示農(nóng)機完成農(nóng)田i作業(yè)任務(wù)的最晚時間。ri表示農(nóng)機進行收割作業(yè)的實際開始時間。

針對k臺農(nóng)機在i個農(nóng)田作業(yè)點進行作業(yè)調(diào)度的情況，給出以下目標(biāo)函數(shù)，如式（1）～式（5）所示。式（1）以農(nóng)機轉(zhuǎn)移距離最短作為優(yōu)化目標(biāo)之一。式（2）以農(nóng)機調(diào)度總成本最低作為優(yōu)化目標(biāo)之一。

[minD=i，j∈Ik=1KDkij] （1）

[minC=CostA+CostD+CostW] （2）

[CostA=i=1Ik=1KCkoSi] （3）

[CostD=i=1Ik=1KCktDkij] （4）

[CostW=i=1Ik=1KρkiCkwWki] （5）

式中： D——農(nóng)機轉(zhuǎn)移距離；

C——農(nóng)機調(diào)度總成本；

CostA——農(nóng)機作業(yè)總成本；

CostD——農(nóng)機路徑轉(zhuǎn)移總成本；

CostW——農(nóng)機等待作業(yè)總成本。

農(nóng)機作業(yè)環(huán)境復(fù)雜，為方便研究本文對約束條件做出以下規(guī)定，如式（6）～式（8）所示。式（6）表示農(nóng)田作業(yè)點i適宜作業(yè)時間窗，包括適宜開始作業(yè)的最早時間和適宜完成作業(yè)的最晚時間，農(nóng)機應(yīng)在任務(wù)窗口[ei，li]內(nèi)到達農(nóng)田作業(yè)點i。式（7）表示農(nóng)機k在農(nóng)田作業(yè)點i最早開始作業(yè)前到達作業(yè)點將產(chǎn)生等待時間，否則不產(chǎn)生等待時間。式（8）表示每個農(nóng)田作業(yè)點僅有一臺農(nóng)機進行作業(yè)。

[ei≤ri≤li，?i∈N] （6）

[ρi=1，" " 農(nóng)機k在農(nóng)田i最早作業(yè)時間ei前到0，" " 農(nóng)機k在農(nóng)田i最早作業(yè)時間ei后到] （7）

[k=1Ki=1] （8）

2 基于優(yōu)先級策略的多目標(biāo)自適應(yīng)優(yōu)化調(diào)度算法

根據(jù)上節(jié)構(gòu)建的模型，設(shè)計基于優(yōu)先級策略的多目標(biāo)自適應(yīng)優(yōu)化調(diào)度算法（APRMOGA）。以農(nóng)機轉(zhuǎn)移距離最短、調(diào)度總成本最低為雙目標(biāo)，為多機跨區(qū)協(xié)同作業(yè)問題求解最佳路徑規(guī)劃方案。本算法以多目標(biāo)優(yōu)化算法NSGA-Ⅱ為基礎(chǔ)，設(shè)計基于時間窗優(yōu)先級規(guī)則的初始種群生成策略和順序交叉策略、基于適應(yīng)度值的自適應(yīng)變異策略對個體進行操作，優(yōu)先保留效果更好的個體。算法設(shè)計流程如圖2所示。

本文采用基于Parato支配關(guān)系的多目標(biāo)遺傳算法，利用快速非支配排序法和擁擠度算子，無需設(shè)定權(quán)重，能夠避免使用權(quán)重系數(shù)反映實際問題時的缺陷。在每次迭代過程中計算所有個體的兩個目標(biāo)值，通過對所有個體進行快速非支配排序，尋找種群中所有非支配解，獲得全局最優(yōu)解。

Step 1：約束條件處理。本文采用單邊硬時間窗的約束條件[15]，即農(nóng)機必須在作業(yè)點時間窗內(nèi)進行作業(yè)，提前到達作業(yè)點的農(nóng)機必須原地等待至作業(yè)點的最早開始作業(yè)時間才可進行作業(yè)，農(nóng)機在等待過程中產(chǎn)生一定的等待作業(yè)費用；對于超出作業(yè)點最晚作業(yè)時間到達的農(nóng)機采用懲罰函數(shù)處理時間窗約束條件，農(nóng)機需支付較大的懲罰費用以減少種群中不可行解的比例，保證種群數(shù)量和解的質(zhì)量。

Step 2：初始化參數(shù)。輸入農(nóng)機M、作業(yè)任務(wù)N等信息。設(shè)置最大迭代次數(shù)gen，種群規(guī)模N，交叉概率Pc，變異系數(shù)P，迭代次數(shù)g=1。

Step 3：生成初始種群。基于時間窗優(yōu)先級規(guī)則產(chǎn)生總數(shù)為N的父代個體作為初始種群[P0=x1，x2，x3，…，xn]。

Step 4：非支配排序和擁擠度計算。對種群中所有個體進行非支配排序并計算個體的擁擠距離。在每一次迭代過程中計算所有個體的路徑轉(zhuǎn)移距離和調(diào)度總成本，依次比較所有個體的兩個目標(biāo)值，對其進行分層。若個體x的兩個目標(biāo)值都不劣于其他個體，則支配個體x的個體數(shù)np=0。按照np的值完成所有個體的分層操作，np=0為第一層。按分層由低到高選擇個體進入下一次迭代，當(dāng)該層個體不能全部被選中時，計算個體擁擠度，優(yōu)先選擇擁擠度大的個體。

Step 5：適應(yīng)度值計算。將調(diào)度總成本作為Y軸，轉(zhuǎn)移距離作為X軸，以個體到坐標(biāo)原點的距離作為適應(yīng)度值的評價指標(biāo)，計算所有個體適應(yīng)度值。

Step 6：選擇操作。采用二元錦標(biāo)賽選擇方式，隨機選擇兩個個體進行比較，選取適應(yīng)度值高的個體參與后續(xù)交叉、變異操作。

Step 7：交叉操作。選取父代個體按照交叉概率Pc進行基于時間窗優(yōu)先級的順序交叉操作。

Step 8：變異操作。根據(jù)個體適應(yīng)度值計算每個個體的變異概率Pmi，按照變異概率Pmi對父代個體的農(nóng)機作業(yè)路徑編碼片段進行變異操作，得到新的子代個體。

Step 9：合并、產(chǎn)生新種群。將父代種群Pg和子代種群Pg+1根據(jù)非支配排序和擁擠度距離結(jié)果進行合并，選擇擁擠度較大的個體進入新父代種群，將其恢復(fù)為規(guī)模為N的種群。

Step 10：計算目標(biāo)值。計算種群中個體對應(yīng)的轉(zhuǎn)移路徑距離和調(diào)度總成本。

Step 11：判斷是否達到最大迭代次數(shù)。若igt;gen，則輸出當(dāng)前最優(yōu)Paroto解集并繪制相關(guān)圖表，跳轉(zhuǎn)至Step 12；否則g=g+1，跳轉(zhuǎn)至Step 4。

Step 12：結(jié)束。

2.1 編碼設(shè)計

采用雙層編碼的方式對農(nóng)田作業(yè)點和農(nóng)機進行編碼，算法中每個染色體表示一個調(diào)度方案，每個染色體有多個基因位，基因位數(shù)等于農(nóng)田作業(yè)點數(shù)量。每個農(nóng)田作業(yè)點都必須在染色體中出現(xiàn)且只可以出現(xiàn)1次，如圖3所示。

圖3中染色體第一層為農(nóng)田編碼，第二層為農(nóng)機編碼，該染色體包含3輛農(nóng)機在9個農(nóng)田作業(yè)點的作業(yè)調(diào)度路徑，農(nóng)機k1的作業(yè)路徑為1→5→6→9，表示k1從農(nóng)機合作社出發(fā)依次經(jīng)過1、5、6、9號農(nóng)田作業(yè)點，完成全部農(nóng)田作業(yè)點任務(wù)后再次回到農(nóng)機合作社。以此類推，第二輛農(nóng)機的作業(yè)調(diào)度路徑為2→4→8，第三輛農(nóng)機的作業(yè)調(diào)度路徑為3→7。為避免染色體在交叉、變異過程中發(fā)生異常，農(nóng)機的出發(fā)點和終點未在編碼中顯示。該編碼方式不僅簡單，而且能夠區(qū)分每輛農(nóng)機的作業(yè)路徑，方便算法后續(xù)操作。

2.2 基于時間窗優(yōu)先級規(guī)則的初始種群生成策略

傳統(tǒng)遺傳算法在求解農(nóng)機調(diào)度問題時，多采用隨機生成的方式構(gòu)建初始種群，這樣的方式容易產(chǎn)生大量劣質(zhì)解或不可行解。為保證初始解的可行性，同時降低劣質(zhì)解或不可行解對算法運行效率的影響，本文設(shè)計了基于時間窗優(yōu)先級規(guī)則的初始種群生成策略。為便于描述，特做如下定義說明。

定義： 若[TWi∩TWj=?]，則農(nóng)田作業(yè)點i與農(nóng)田作業(yè)點j為串行任務(wù)；若[TWi∩TWj≠?]則農(nóng)田作業(yè)點i與農(nóng)田作業(yè)點j為并行任務(wù)；其中[TWi=[ei，li]]為農(nóng)田作業(yè)點i的作業(yè)時間窗、[TWj=][[ej，lj]]為農(nóng)田作業(yè)點j的作業(yè)時間窗。

首先將所有農(nóng)田作業(yè)點按照作業(yè)最早開始時間進行升序排序，若作業(yè)點最早開始作業(yè)時間相同，則按照最晚結(jié)束作業(yè)時間進行升序排序。對于具有相同作業(yè)時間窗的農(nóng)田，按照農(nóng)田面積進行升序排序。將完成排序的所有農(nóng)田作業(yè)點保存到作業(yè)任務(wù)隊列O中；依次從隊列O中取出作業(yè)點判斷是否為串行任務(wù)，將其劃分為不同的作業(yè)等級R[m]；根據(jù)作業(yè)等級優(yōu)先順序依次為每層內(nèi)作業(yè)點隨機分配農(nóng)機進行作業(yè)，具體流程如下。

第一步，對農(nóng)田作業(yè)點劃分等級。（1）導(dǎo)入完成排序的作業(yè)任務(wù)集N以及農(nóng)機集M，設(shè)置i=j=1、層級R[1]=1、任務(wù)總數(shù)為n。（2）如果jgt;n，轉(zhuǎn)至步驟5；否則j=i+1。（3）判定i和j是否并行，是則令R[i]=R[j]；否則令R[i]=R[j]+1。（4）i++，轉(zhuǎn)至步驟2。（5）整理退出。

第二步，向農(nóng)田作業(yè)點派遣農(nóng)機。（1）X[m]為第m層作業(yè)點的數(shù)量，K為農(nóng)機總數(shù)，令p為最大層數(shù)、m=1。（2）如果mgt;p，則跳轉(zhuǎn)至步驟5，否則順序執(zhí)行。（3）如果X[m]≤K，則為第m層作業(yè)點同時調(diào)配農(nóng)機，記錄該調(diào)配方案；否則向農(nóng)田作業(yè)點派遣完所有農(nóng)機后，由最早結(jié)束作業(yè)的收割機繼續(xù)完成當(dāng)前層級剩余作業(yè)點任務(wù)，記錄調(diào)配方案。（4）m=m+1，轉(zhuǎn)至步驟2。（5）結(jié)束。

2.3 適應(yīng)度值計算

本文采用個體距離函數(shù)計算每個個體的適應(yīng)度值，對種群中所有個體進行二次評價[16]。具體操作為：將調(diào)度總成本作為Y軸，轉(zhuǎn)移距離作為X軸，每個個體都是坐標(biāo)軸上的點，以個體到坐標(biāo)原點的距離作為適應(yīng)度值的評價指標(biāo)，距離坐標(biāo)原點越近的個體，兩個目標(biāo)的值更低，適應(yīng)度值越高；反之，適應(yīng)度值越低。適應(yīng)度函數(shù)表示為

[Fiti=1Dki] （9）

式中： Dki——個體距離函數(shù)，即個體i到坐標(biāo)原點的距離，如圖4所示。

為避免不同數(shù)量級對種群適應(yīng)度的影響，計算個體距離函數(shù)前需先對調(diào)度總成本和轉(zhuǎn)移距離進行歸一化處理，如式（10）所示。

[Di'=di-mindmaxd-mindCi'=ci-mincmaxc-minc] （10）

式中： [di、ci]——個體i的轉(zhuǎn)移距離和調(diào)度總成本；

[maxd]——種群中個體的最大轉(zhuǎn)移距離；

[mind]——種群中個體的最小轉(zhuǎn)移距離；

[maxc]——種群中個體的最高調(diào)度總成本；

[minc]——種群中個體的最低調(diào)度總成本。

[Dki=Di'2+Ci'2] （11）

2.4 遺傳算子

2.4.1 選擇算子

選擇算子根據(jù)個體適應(yīng)度值從種群中選擇個體參與交叉、變異操作。本文采用二元錦標(biāo)賽選擇方法，每次隨機從種群中選擇兩個個體進行比較，選取適應(yīng)度值高的個體進行后續(xù)操作[17]。二元錦標(biāo)賽選擇方法能夠保證最差的個體一定會被淘汰。

2.4.2 基于時間窗優(yōu)先級的順序交叉算子

交叉操作模擬自然界中染色體的交叉換位現(xiàn)象，將兩個父代個體的部分基因進行處理，用于生成新個體，交叉操作決定了算法的全局搜索能力。為擴大種群的搜索范圍，提高種群的多樣性，本文基于農(nóng)田作業(yè)時間窗設(shè)計時間窗優(yōu)先級順序交叉策略對父代進行操作，優(yōu)先為作業(yè)時間窗開始時間早的農(nóng)田派遣農(nóng)機。以包含3臺農(nóng)機、9個農(nóng)田作業(yè)點的兩個染色體編碼為例，各個農(nóng)田作業(yè)點時間窗優(yōu)先級由1～9升序排列，父代個體為A1、A2，子代個體為B1、B2，交叉結(jié)果如圖5所示。具體交叉過程為：依次對比兩個父代個體第一層編碼相同位置的基因，若A1該位置基因優(yōu)先級高于A2相同位置基因的優(yōu)先級，則直接將A1的該基因及對應(yīng)的下層農(nóng)機編碼基因填充到子代基因B1的相同位置。遍歷A2第一層編碼基因并剔除B1中已存在基因，將剩余基因及其對應(yīng)的下層農(nóng)機編碼基因依次填入子代B1中空缺位置，得到子代個體B1。按照同樣過程對A2進行操作，得到子代個體B2?；跁r間窗優(yōu)先級的順序交叉算子，能夠保留優(yōu)先調(diào)度作業(yè)時間窗開始時間早的農(nóng)田作業(yè)點基因，盡可能降低等待作業(yè)的懲罰值，滿足農(nóng)田作業(yè)點的時間窗約束。

2.4.3 自適應(yīng)變異算子

傳統(tǒng)遺傳算法選取一個常數(shù)作為變異概率，固定不變的變異概率無法公平對待種群中所有個體，優(yōu)良個體需要更小的概率保存優(yōu)秀基因，劣質(zhì)個體需要更大的概率改善劣質(zhì)基因。針對此問題，本文采用自適應(yīng)調(diào)整的變異概率，根據(jù)種群適應(yīng)度值情況動態(tài)調(diào)整每個個體的變異概率，進行變異操作[18?20]。個體變異概率計算如式（12）所示。

[Pmi=0" " " " " " " " " " " " fi=fmaxPfmax-fifmax-favg" " favglt;filt;fmax1" " " " " " " " " " " " fi≤favg] （12）

式中： fi——第i個個體的適應(yīng)度值；

fmax——種群最大適應(yīng)度值；

favg——種群平均適應(yīng)度值；

P——常數(shù)，設(shè)定P=0.5。

個體根據(jù)不同變異概率判斷是否進行變異操作。變異操作具體過程為：在農(nóng)田編碼序列中隨機產(chǎn)生兩個變異點，將該農(nóng)田編碼及其對應(yīng)的下層農(nóng)機編碼片段進行交換變異，得到一個新的子代個體，操作過程如圖6所示，C1為變異前個體編碼，C2為變異后個體編碼。

自適應(yīng)變異策略能夠根據(jù)不同個體的具體情況自動調(diào)整變異概率，降低適應(yīng)度值高的個體的變異概率，提高適應(yīng)度值低的個體的變異概率，在保持種群多樣性的同時加快算法的收斂速度，更好地保存了優(yōu)秀個體基因。

3 試驗分析

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

選取河北省范圍內(nèi)（北緯37°～40°，東經(jīng)114°～117°）農(nóng)田進行分析，將地塊劃分為24個農(nóng)田作業(yè)點進行仿真試驗。農(nóng)田作業(yè)點信息如表1所示，其中序號0表示農(nóng)機合作社，序號1～24表示農(nóng)田作業(yè)點。各個農(nóng)田作業(yè)點分布情況如圖7所示。

對試驗數(shù)據(jù)進行如下假設(shè)：（1）該區(qū)域有一個農(nóng)機合作社，農(nóng)機合作社中有k臺農(nóng)機，農(nóng)機作業(yè)效率相同，都為0.4 hm2/h。（2）農(nóng)機轉(zhuǎn)移行駛速度相同，都為40 km/h，路上轉(zhuǎn)移成本為2元/km，提前到達的等待成本為36元/h，農(nóng)機在作業(yè)點內(nèi)工作的作業(yè)成本為400元/hm2。（3）在仿真過程中假設(shè)農(nóng)機每天工作時間為12 h。（4）為便于農(nóng)機進行第二日的作業(yè)任務(wù)，農(nóng)機當(dāng)日工作完成后無需返回農(nóng)機合作社，在田間等待第二日工作。（5）農(nóng)機完成路徑全部作業(yè)后返回出發(fā)點。

3.2 算法運行結(jié)果

采用pycharm軟件對APRMOGA算法進行測試，設(shè)置初始參數(shù)種群規(guī)模為100，最大進化迭代次數(shù)為100，交叉概率為0.5，變異系數(shù)為0.5。使用APRMOGA算法對實例進行分析計算，并畫出最后1次運行結(jié)果中每輛農(nóng)機的最佳作業(yè)路徑，如圖8所示。

數(shù)字“0”表示農(nóng)機合作社，數(shù)字“1～24”表示農(nóng)田作業(yè)點，農(nóng)機使用數(shù)量為8輛，得到8條最優(yōu)作業(yè)路徑，車輛轉(zhuǎn)移距離為1 957.95 km，調(diào)度總成本為118 271.90元。

3.3 對比分析

將APRMOGA算法與帶精英策略的非支配排序遺傳算法NSGA-Ⅱ進行比較。NSGA-Ⅱ算法采用隨機生成的方式產(chǎn)生初始種群，經(jīng)過非支配排序后使用遺傳算法的基本選擇、交叉、變異操作產(chǎn)生第一代種群，從第二代開始根據(jù)非支配排序結(jié)果和擁擠度距離合并子、父代種群，隨后根據(jù)遺傳算法的基本操作產(chǎn)生新的子代種群，直到滿足結(jié)束條件[21]。本文將從作業(yè)轉(zhuǎn)移距離和調(diào)度總成本兩方面分別對NSGA-Ⅱ算法與本文提出的APRMOGA算法進行比較，將初始參數(shù)設(shè)置為種群規(guī)模100，最大進化迭代次數(shù)100，交叉概率0.5，變異系數(shù)0.5，試驗結(jié)果如表2所示。

由表2顯示，農(nóng)機合作社為農(nóng)機規(guī)劃的最佳作業(yè)路徑分別為：1號農(nóng)機作業(yè)路徑15→1→17，2號農(nóng)機作業(yè)路徑16→7，3號農(nóng)機作業(yè)路徑6→9，4號農(nóng)機作業(yè)路徑22→23→21，5號農(nóng)機作業(yè)路徑3→12→24→4→19→20→18，6號農(nóng)機作業(yè)路徑10，7號農(nóng)機作業(yè)路徑13→11→2→5→8，8號農(nóng)機作業(yè)路徑14。采用APRMOGA算法調(diào)度總成本為118 271.90元，農(nóng)機作業(yè)轉(zhuǎn)移距離為1 957.95 km，采用NSGA-Ⅱ算法調(diào)度總成本為137 081.29元，農(nóng)機作業(yè)轉(zhuǎn)移距離為2 562.65 km。相較于采用NSGA-Ⅱ算法，本文提出APRMOGA算法的作業(yè)轉(zhuǎn)移距離和調(diào)度總成本比NSGA-Ⅱ算法分別下降了23.60%、13.72%，達到了更好的優(yōu)化效果。

運行過程中農(nóng)機調(diào)度總成本、轉(zhuǎn)移距離隨迭代次數(shù)變化的曲線如圖9、圖10所示。當(dāng)種群規(guī)模為100、最大進化迭代次數(shù)為100、交叉概率、變異系數(shù)都為0.5時，本文提出的APRMOGA算法在運行50代左右即可收斂至穩(wěn)定值，而NSGA-Ⅱ算法運行到80代左右才能夠收斂至穩(wěn)定值，并且使用APRMOGA算法得到的兩個目標(biāo)值都能得到更優(yōu)的結(jié)果，與NSGA-Ⅱ算法相比本文提出的APRMOGA算法具有更好的、更穩(wěn)定的收斂效果。

為進一步驗證算法的有效性、排除特殊試驗數(shù)據(jù)對試驗結(jié)果的影響，本文在河北省范圍內(nèi)（北緯38°～40°，東經(jīng)114°～117°）隨機生成5組數(shù)據(jù)進行試驗，每組數(shù)據(jù)包含24個農(nóng)田作業(yè)點。分別采用NSGA-Ⅱ算法與本文提出的APRMOGA算法對每組數(shù)據(jù)進行10次試驗，并記錄兩種算法最優(yōu)的運行結(jié)果，從調(diào)度總成本和轉(zhuǎn)移距離兩個目標(biāo)值進行對比分析。為避免算法其他參數(shù)對試驗結(jié)果的影響，將兩種算法參數(shù)設(shè)置均與上文相同。5組數(shù)據(jù)的運行結(jié)果如表3所示。通過對表中5組結(jié)果對比可知：在相同的試驗條件下，采用本文提出的APRMOGA算法相較NSGA-Ⅱ算法，農(nóng)機轉(zhuǎn)移距離最多減少了22.05%，最低減少了7.86%；農(nóng)機調(diào)度成本最多減少了20.27%，最低減少了6.94%。說明采用APRMOGA算法得到兩個優(yōu)化目標(biāo)的結(jié)果整體優(yōu)于NSGA-Ⅱ算法，本文提出的算法能夠合理有效的解決農(nóng)機作業(yè)路徑規(guī)劃問題，滿足農(nóng)田需求。

4 結(jié)論

針對跨區(qū)域農(nóng)機協(xié)同作業(yè)調(diào)度問題設(shè)計帶時間窗的多目標(biāo)優(yōu)化數(shù)學(xué)模型，提出APRMOGA算法，并結(jié)合實際情況對問題進行實例分析，驗證模型的有效性。

1） 以農(nóng)機轉(zhuǎn)移距離最短、調(diào)度總成本最低為雙目標(biāo)對多目標(biāo)農(nóng)機跨區(qū)調(diào)度問題進行求解，在滿足各農(nóng)田作業(yè)時間窗的前提下得到一個較好的Pareto解集，為農(nóng)機合作社派遣農(nóng)機提供更合理、更高效的解決方案。

2） 針對河北省內(nèi)某地區(qū)24塊農(nóng)田，分別采用APRMOGA算法和NSGA-Ⅱ算法進行試驗。結(jié)果表明，本文提出的APRMOGA算法運行效率要高于NSGA-Ⅱ算法，使用APRMOGA算法得到的聯(lián)合收割機作業(yè)轉(zhuǎn)移距離和調(diào)度總成本比NSGA-Ⅱ算法分別下降23.60%、13.72%。同時APRMOGA算法具有更好的收斂效果，相比NSGA-Ⅱ算法減少約30次，具有更短的迭代時間。

3） APRMOGA算法過早的收斂可能會帶來算法陷入局部最優(yōu)的問題，如何使算法避免陷入局部最優(yōu)是后續(xù)研究仍需解決的問題。

參 考 文 獻

[ 1 ] 阮冬燕， 周晶. 農(nóng)機跨區(qū)作業(yè)服務(wù)市場分化及其成因研究進展[J]. 湖北農(nóng)業(yè)科學(xué)， 2021， 60（18）： 9-13.

Ruan Dongyan， Zhou Jing. Research progress on market differentiation of agricultural machinery cross regional operation service and its causes [J]. Hubei Agricultural Sciences， 2021， 60（18）： 9-13.

[ 2 ] 黃炎忠， 羅小鋒. 跨區(qū)作業(yè)如何影響農(nóng)機服務(wù)獲取？[J]. 華中農(nóng)業(yè)大學(xué)學(xué)報（社會科學(xué)版）， 2020（4）： 89-97， 178.

Huang Yanzhong， Luo Xiaofeng. How does cross?regional operation affect agricultural machinery service acquisition？ [J]. Journal of Huazhong Agricultural University （Social Sciences Edition）， 2020（4）： 89-97， 178.

[ 3 ] Zheng L. Optimization of agricultural machinery task scheduling algorithm based on multiobjective optimization [J]. Journal of Sensors， 2022： 1-12.

[ 4 ] Cong R， Qi J， Wu C， et al. Multi?UAVs cooperative detection based on improved NSGA?II algorithm [C]. IEEE， 2020 39th Chinese Control Conference （CCC）， 2020： 1524-1529.

[ 5 ] Mahmud M S A， Abidin M S Z， Mohamed Z， et al. Multi?objective path planner for an agricultural mobile robot in a virtual greenhouse environment [J]. Computers and Electronics in Agriculture， 2019， 157： 488-499.

[ 6 ] Wang H， Tan L， Shi J， et al. An improved NSGA?II algorithm for UAV path planning problems [J]. Journal of Internet Technology， 2021， 22（3）： 583-592.

[ 7 ] 曹光喬， 張慶凱， 陳聰， 等. 基于多目標(biāo)優(yōu)化的飛防隊作業(yè)調(diào)度模型研究[J]. 農(nóng)業(yè)機械學(xué)報， 2019， 50（11）： 92-101.

Cao Guangqiao， Zhang Qingkai， Chen Cong， et al. Scheduling model of UAV plant protection team based on multi?objective optimization [J]. Transactions of the Chinese Society for Agricultural Machinery， 2019， 50（11）： 92-101.

[ 8 ] Wang J， Jia G， Lin J， et al. Cooperative task allocation for heterogeneous multi?UAV using multi?objective optimization algorithm [J]. Journal of Central South University， 2020， 27（2）： 432-448.

[ 9 ] 鄭彥輝， 朱昌鋒， 王慶榮， 等. 考慮有限理性的應(yīng)急物資博弈調(diào)配雙目標(biāo)優(yōu)化[J]. 中國安全科學(xué)學(xué)報， 2020， 30（11）： 168-174.

Zheng Yanhui， Zhu Changfeng， Wang Qingrong， et al. Bi?objective optimization of emergency material game allocation considering limited rationality [J]. China Safety Science Journal， 2020， 30（11）： 168-174.

[10] 王芳， 滕桂法， 姚竟發(fā). 帶時間窗的多目標(biāo)蔬菜運輸配送路徑優(yōu)化算法[J]. 智慧農(nóng)業(yè)（中英文）， 2021， 3（3）： 152-161.

Wang Fang， Teng Guifa， Yao Jingfa. Multi?objective vegetable transportation and distribution path optimization with time windows [J]. Smart Agriculture， 2021， 3（3）： 152-161.

[11] 王文權(quán). 帶時間窗農(nóng)機調(diào)度問題模型及算法研究[D]. 杭州： 浙江大學(xué)， 2020.

[12] 呂云杰， 郭輝， 魯東. 帶時間窗農(nóng)機調(diào)度問題的改進遺傳算法[J]. 新疆農(nóng)機化， 2021（2）： 38-41.

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

[14] 王猛， 趙博， 劉陽春， 等. 基于多變異分組遺傳算法的多機協(xié)同作業(yè)靜態(tài)任務(wù)分配[J]. 農(nóng)業(yè)機械學(xué)報， 2021， 52（7）： 19-28.

Wang Meng， Zhao Bo， Liu Yangchun， et al. Static task allocation for multi?machine cooperation based on multi?variation group genetic algorithm [J]. Transactions of the Chinese Society for Agricultural Machinery， 2021， 52（7）： 19-28.

[15] 黃凰， 陳燕燕， 陳鵬宇， 等. 基于時間窗的農(nóng)機調(diào)度技術(shù)研究進展[J]. 中國農(nóng)業(yè)科技導(dǎo)報， 2022， 24（4）： 93-106.

Huang Huang， Chen Yanyan， Chen Pengyu， et al. Research progress of agricultural machinery scheduling technology based on time window [J]. Journal of Agricultural Science and Technology， 2022， 24（4）： 93-106.

[16] 李二超， 楊潤寧. 基于多樣化初始種群的自適應(yīng)變異多目標(biāo)優(yōu)化策略[J]. 陜西師范大學(xué)學(xué)報（自然科學(xué)版）， 2020， 48（6）： 96-107.

[17] 馬梅瓊. 聯(lián)合收割機跨區(qū)作業(yè)調(diào)度研究[D]. 哈爾濱： 東北農(nóng)業(yè)大學(xué)， 2018.

[18] 張錚， 柯子鵬， 周嘉政， 等. 基于改進多目標(biāo)自適應(yīng)遺傳算法的機器人路徑規(guī)劃[J]. 西安理工大學(xué)學(xué)報， 2023， 39（1）： 69-78.

Zhang Zheng， Ke Zipeng， Zhou Jiazheng， et al. Robot path planning based on improved multi?objective adaptive genetic algorithm [J]. Journal of Xi'an University of Technology， 2023， 39（1）： 69-78.

[19] 馬碩. 基于非支配排序遺傳算法的多目標(biāo)車輛路徑規(guī)劃研究[D]. 大連： 大連海事大學(xué)， 2020.

[20] 徐夢穎， 王嬌嬌， 劉寶， 等. 基于改進遺傳算法的機器人路徑規(guī)劃[J]. 石河子大學(xué)學(xué)報（自然科學(xué)版）， 2021， 39（3）： 391-396.

[21] 羅梓瑄. 基于NSGA-Ⅱ的車輛路徑問題研究[D]. 重慶： 重慶師范大學(xué)， 2022.