曹光喬 馬 斌,2 陳 聰 任保鑫,2 胡朝中

(1.農(nóng)業(yè)農(nóng)村部南京農(nóng)業(yè)機械化研究所, 南京 210014; 2.中國農(nóng)業(yè)科學(xué)院研究生院, 北京 100081)

0 引言

隨著我國新型生產(chǎn)經(jīng)營主體不斷涌現(xiàn),規(guī)?；?jīng)營等現(xiàn)代農(nóng)業(yè)生產(chǎn)模式開始興起,從而帶動對農(nóng)機社會化服務(wù)等需求的增加[1-3]。在我國,大多數(shù)地區(qū)的耕地呈現(xiàn)碎片化的地理分布,零散農(nóng)戶仍是農(nóng)業(yè)生產(chǎn)主體。農(nóng)民的收入很大程度上取決于農(nóng)產(chǎn)品的產(chǎn)量和市場價格,農(nóng)機的按需使用能夠幫助農(nóng)戶提高作物產(chǎn)量和收入[4]。然而,農(nóng)業(yè)機械價格昂貴,小農(nóng)難以負擔(dān),通常只有擁有較多田地的農(nóng)戶才會購買農(nóng)機以滿足作物收獲需求[5]。在農(nóng)忙時節(jié),采用收獲機跨區(qū)作業(yè)這種“共享農(nóng)機”模式是為零散農(nóng)戶提供按需和低成本服務(wù)最有效的方法。

小麥?zhǔn)墙话雭喼薜貐^(qū)居民的主要糧食來源,在我國,小麥產(chǎn)量超過全國糧食產(chǎn)量的1/5[6-7]。小麥成熟期因地理位置不同而具有差異,導(dǎo)致小麥?zhǔn)斋@機隨作物成熟期自南向北跨區(qū)遷徙作業(yè)[8],因此農(nóng)機跨區(qū)調(diào)度具有很強的時空演化特征和資源約束特征[9-11]。目前農(nóng)機跨區(qū)調(diào)度多憑借人為經(jīng)驗,調(diào)度計劃缺乏基于作物成熟期的合理規(guī)劃,存在作業(yè)區(qū)域順序混亂、農(nóng)機資源配置不合理等問題,造成作業(yè)效率低下,貽誤農(nóng)時,降低了作物的收獲產(chǎn)量和質(zhì)量[12]。因此,基于“三夏”(夏收、夏種、夏管)時節(jié)農(nóng)機跨區(qū)作業(yè)需求,研究多約束條件下農(nóng)機資源配置問題對提高收獲機跨區(qū)作業(yè)效率、保障作業(yè)質(zhì)量具有重要意義。

近年來,學(xué)者從不同角度對農(nóng)機調(diào)度問題進行了大量的研究,他們大都把農(nóng)機調(diào)度問題轉(zhuǎn)化為帶時間窗的VRP問題或運籌學(xué)中的運輸問題[13]。目前研究熱點多集中在單個任務(wù)或小區(qū)域調(diào)度,通常情況下只考慮一個農(nóng)機供應(yīng)點或同種類型的農(nóng)機,在農(nóng)機調(diào)度研究中常用的調(diào)度優(yōu)化目標(biāo)包括:最大作業(yè)收益、最小調(diào)度總成本、最小調(diào)度路程等[14-16]。農(nóng)機調(diào)度問題屬于NP-hard難題,遇到大型計算實例時,NP-hard問題無法在有效時間內(nèi)得到解決,常使用啟發(fā)式算法進行求解[17-18]。例如文獻[19]將模擬退火算法、遺傳算法和混合Petri網(wǎng)絡(luò)模型相結(jié)合,提出了一種兩階段的元啟發(fā)式算法用于求解甘蔗生產(chǎn)收獲的資源分配調(diào)度模型,并獲得了較高的資源利用率。文獻[20]以最小化農(nóng)機工作時間為目標(biāo),提出了一種規(guī)劃方法確定生物質(zhì)收獲和加工操作的順序,解決了多領(lǐng)域生物質(zhì)順序處理的調(diào)度問題。文獻[21]以收獲機服務(wù)總面積最大為目標(biāo),提出的ALNS元啟發(fā)式算法解決了帶時間窗的甘蔗收獲機械的調(diào)度問題。文獻[22]分析了農(nóng)機調(diào)度的各種成本,以總調(diào)度成本最低建立了重大疫情情況下的農(nóng)機調(diào)度模型,并改進模擬退火算法對模型進行求解。

上述研究都聚焦在區(qū)域內(nèi)的田間路徑優(yōu)化問題上,在農(nóng)忙季節(jié),農(nóng)戶作業(yè)需求往往來自不同的省、市、縣,空間跨度從幾十千米到幾百千米不等,多種農(nóng)機在空間大尺度下的規(guī)?；鐓^(qū)調(diào)度更能滿足農(nóng)業(yè)生產(chǎn)需求。在農(nóng)機跨區(qū)調(diào)度上,已有一部分研究,例如文獻[23]建立了以調(diào)配成本和損失最小為目標(biāo)的農(nóng)機跨區(qū)作業(yè)緊急調(diào)配模型,并提出兩種算法求解。文獻[24]通過改進的非支配鄰域搜索算法和禁忌搜索算法解決了農(nóng)機靜態(tài)分區(qū)和動態(tài)跨區(qū)協(xié)同調(diào)度問題。文獻[25]考慮多庫、多機型和作業(yè)時間窗等因素,對農(nóng)機跨區(qū)作業(yè)進行研究,提高了服務(wù)的準(zhǔn)時率和農(nóng)機的使用率。

通過分析文獻發(fā)現(xiàn),現(xiàn)有的研究很少涉及農(nóng)機車隊作業(yè),無論是小區(qū)域調(diào)度或大區(qū)域調(diào)度,很少考慮到作物的收獲周期。事實上,空間大尺度下的農(nóng)機跨區(qū)作業(yè)由若干臺農(nóng)機組成農(nóng)機車隊,當(dāng)多臺農(nóng)機進行跨區(qū)作業(yè)時,要綜合考慮調(diào)度距離、作物收獲時間窗、農(nóng)機利用率等因素,由于機械折舊費、路橋費等費用的存在,農(nóng)機跨區(qū)作業(yè)的調(diào)度距離又會存在合理的范圍[26]。近年來,帶時間窗的車輛路徑問題得到了廣泛的拓展,其中解決綠色車輛路徑問題是減少碳排放,實現(xiàn)“雙碳”目標(biāo)的重要手段,暫時尚未有研究在農(nóng)機調(diào)度中考慮碳排放成本。如何在制定農(nóng)機跨區(qū)調(diào)度計劃時尋求社會經(jīng)濟效益最大化,同時推動綠色發(fā)展是一個值得探討的問題。因此探討多庫、多機型、作業(yè)時間窗、空間距離等約束條件下的農(nóng)機跨區(qū)作業(yè)資源配置問題,建立考慮碳排放的農(nóng)機跨區(qū)調(diào)度模型,對保證糧食生產(chǎn)安全和促進碳中和具有重要意義。

本文針對“三夏”時節(jié)農(nóng)機跨區(qū)調(diào)度的特點建立以最小調(diào)度成本為目標(biāo)的跨區(qū)調(diào)度模型,同時考慮經(jīng)濟成本和環(huán)境成本,以期為農(nóng)機跨區(qū)調(diào)度的管理決策提供依據(jù)。并提出一種遺傳變鄰域搜索算法(Genetic algorithm variable neighborhood search,GAVNS)求解模型,在該算法中,采用自適應(yīng)機制對鄰域權(quán)重進行動態(tài)調(diào)整,以期減少跨區(qū)調(diào)度成本。

1 問題描述與模型建立

1.1 問題描述

我國幅員遼闊,小麥作物由南向北依次成熟,這種規(guī)律為農(nóng)機提供了一個連續(xù)的作業(yè)窗口,但我國的農(nóng)機資源在地理空間上分布不均,在農(nóng)忙時節(jié),農(nóng)戶往往通過租賃外地的收獲機服務(wù)來完成收獲任務(wù)。通常,少量農(nóng)戶依賴社會信任和關(guān)系網(wǎng)絡(luò),往往基于經(jīng)驗數(shù)據(jù),口頭或電話傳遞需求信息給農(nóng)機駕駛員以完成小麥的跨區(qū)機收作業(yè),但這種模式過于依賴個人關(guān)系且調(diào)度效率低下,易造成資源和信息的不匹配。在大規(guī)模的農(nóng)機調(diào)度中,農(nóng)機合作社參與的調(diào)度模式是“三夏”時節(jié)完成小麥跨區(qū)機收的主要方式。在收獲機跨區(qū)作業(yè)過程中,農(nóng)戶的作業(yè)需求往往來自不同的省、市、縣,合作社收到包含農(nóng)田類型、面積和位置等信息的作業(yè)訂單后完成收獲機的派遣。收獲機通過卡車搭載成隊列從合作社運輸至待收區(qū),完成收獲作業(yè),農(nóng)機跨區(qū)調(diào)度網(wǎng)絡(luò)如圖1所示。

圖1 農(nóng)機跨區(qū)調(diào)度網(wǎng)絡(luò)圖Fig.1 Network diagram of agricultural machinery cross-region scheduling

該問題考慮多個合作社為多個小麥待收區(qū)提供收獲機跨區(qū)作業(yè)服務(wù),且每個合作社具有多數(shù)量、多機型的聯(lián)合收獲機。在建立模型之前,作以下假設(shè):一個區(qū)縣即為一個待收區(qū);相同型號收獲機的運輸速率和工作效率相同,收獲機從合作社運輸?shù)酱諈^(qū)僅存在公路運輸一種方式,不考慮天氣狀況、道路擁堵情況,無道路容量限制;所有收獲機與其運載卡車之間的比重相同;將收獲機按型號分組,且每組收獲機數(shù)量可能不同,分別運往不同區(qū)域;每個待收區(qū)只能由一個收獲機組服務(wù);農(nóng)機合作社位置、待收區(qū)位置、待收區(qū)的待收獲面積已知,一個待收區(qū)最多由一個合作社提供服務(wù);收獲機組到達待收區(qū)的時間即為開始收獲時間;小麥在收獲時間窗內(nèi)的品質(zhì)、產(chǎn)量恒定。

1.2 模型建立

基于以上問題描述,對模型建立中使用的集合、參數(shù)和決策變量定義如下:

(1)集合

I:待收區(qū)中出發(fā)區(qū)域集合,I={1,2,…,i}

J:待收區(qū)中到達區(qū)域集合,J={i+1,i+2,…,i+j}

M:農(nóng)機合作社集合,M={1,2,…,m},M=I

V:收獲機組集合,V={1,2,…,k}

A:待收區(qū)中節(jié)點集合,A={(i,j)|i∈I,j∈J}

(2)下標(biāo)

i:待收區(qū)中的出發(fā)節(jié)點,i∈I

j:待收區(qū)中的到達節(jié)點,j∈J

k:收獲機組型號,k∈V

(3)參數(shù)

qk:k型號收獲機工作效率(hm2/h)

v:每臺收獲機轉(zhuǎn)運速度(km/h)

ct:每臺收獲機單位距離運輸成本(元/km)

wa:每個操作員時薪(元/h)

eijk:卡車k在路段(i,j)上的碳排放率(kg/km)

twj:完成待收區(qū)j收獲所需的工作時間(h)

tij:收獲機從待收區(qū)i轉(zhuǎn)運到待收區(qū)j所需時間(h)

tjk:收獲機組k到達待收區(qū)j的時間(h)

Sj:待收區(qū)j的待收獲面積(hm2)

dij:待收區(qū)i和j之間的距離(km)

T:每日可用工作時間(h)

Pc:碳交易價格(元/kg)

N:一個足夠大的正整數(shù)

Ej:待收區(qū)j小麥開始收獲時間

Lj:待收區(qū)j小麥?zhǔn)斋@結(jié)束時間

α:早到等待成本

β:晚到懲罰成本

(4)決策變量

該問題優(yōu)化目標(biāo)為調(diào)度成本C,包括收獲機運輸成本C1、車輛和人員固定成本C2、時間懲罰成本C3和碳排放成本C4。

收獲機運輸成本與路徑長度呈正相關(guān),運輸成本為

(1)

車輛和人員固定成本主要由駕駛員工資構(gòu)成,不考慮每臺收獲機在田間轉(zhuǎn)運的時間損耗,固定成本為

(2)

時間懲罰成本與收獲機到達待收區(qū)開始作業(yè)時間有關(guān),時間懲罰成本為

(3)

碳排放成本與收獲機轉(zhuǎn)運途中燃油消耗密切相關(guān),文獻[27]對目前流行的油耗估算模型進行了詳細的對比分析,考慮到收獲機實際轉(zhuǎn)運過程中的車輛特征、道路特征、車輛運行特征,采用MEET模型估算車輛碳排放量[28]?？ㄜ噆在路段(i,j)上的碳排放率(kg/km)為

(4)

其中:ε表示卡車空載且在坡度為0°以速度v行駛時的碳排放率,ω0～ω6為常數(shù),根據(jù)卡車類型取值。碳排放率的載重修正因子為

(5)

其中:γ為卡車i在路段(i,j)上的實際載重與其容量的比值,χ0～χ7為常數(shù),根據(jù)卡車類型取值?？ㄜ噆在路段(i,j)上的碳排放率(kg/km)為

(6)

在轉(zhuǎn)運過程中收獲機k的碳排放成本C4為

(7)

該問題構(gòu)建的數(shù)學(xué)模型,目標(biāo)函數(shù)為

(8)

(9)

(10)

(11)

(12)

(13)

(14)

(15)

(16)

(17)

(18)

Ej≤tjk+twj≤Lj(?j∈J)

(19)

(20)

該模型的目標(biāo)函數(shù)(8)表示最小經(jīng)濟成本與環(huán)境成本之和。其中,經(jīng)濟成本包括運輸成本、固定人力成本和時間懲罰成本,環(huán)境成本包括碳排放成本。約束式(9)表示派出的收獲機數(shù)小于或等于所有合作社的收獲機總數(shù)。約束式(10)表示每個待收區(qū)必須且只能被一個收獲機組服務(wù)一次,不允許多個收獲機組服務(wù)同一個待收區(qū)。約束式(11)表示每一個待收區(qū)域只能由一個收獲機組服務(wù),不接受多個機組的多次服務(wù)。約束式(12)表示從合作社出發(fā)的收獲機組在作業(yè)完成之后必須返回合作社。約束式(13)表示保證每個收獲機組在完成作業(yè)后必須離開該地。約束式(14)表示保證合作社之間不進行收獲機組的轉(zhuǎn)運。約束式(15)表示禁止收獲機組返回合作社后返回待收區(qū)。約束式(16)表示消除區(qū)域內(nèi)環(huán)流。約束式(17)表示每日的作業(yè)時間和轉(zhuǎn)運時間之和不超過規(guī)定的時間。約束 式(18) 表示收獲機組從待收區(qū)i到待收區(qū)j的時間窗應(yīng)滿足的條件。約束式(19)表示收獲機組到達待收區(qū)和完成作業(yè)需滿足的時間窗。約束式(20)表示決策變量的取值范圍。

2 模型解算

農(nóng)機跨區(qū)調(diào)度問題屬于NP-hard難題,采用精確算法求解大規(guī)模實例會出現(xiàn)運行時間長,難以求得最優(yōu)解,現(xiàn)有的研究都傾向于采用智能優(yōu)化算法求得近似最優(yōu)解,如遺傳算法、粒子群優(yōu)化算法、變鄰域搜索算法。遺傳算法能夠在解的空間進行全局搜索,且并行性高,變鄰域搜索算法通過在當(dāng)前解的鄰域內(nèi)搜索,可快速找到局部改進解,這種局部搜索能力使算法在每一步的迭代中逐漸改善解的質(zhì)量,向更優(yōu)解的方向前進。綜合考慮模型決策變量定義域的規(guī)則性,提出遺傳變鄰域搜索算法(GAVNS)對較大規(guī)模的農(nóng)機跨區(qū)調(diào)度問題進行求解。

2.1 算法流程

GAVNS算法流程如圖2所示。首先生成基于當(dāng)前參數(shù)組合的初始解,再執(zhí)行選擇、交叉操作,然后用鄰域方法對當(dāng)前解進行改進,最后,當(dāng)滿足終止條件時,輸出最優(yōu)解。GAVNS算法包括染色體編解碼、初始解構(gòu)造、遺傳操作、隨機擾動、自適應(yīng)鄰域選擇、種群管理等。

圖2 GAVNS算法流程圖Fig.2 GAVNS algorithm flowchart

2.2 染色體編解碼設(shè)計

根據(jù)農(nóng)機合作社提供的跨區(qū)服務(wù)特點,采用正整數(shù)的編碼方式。對染色體的編碼,具體表示為:節(jié)點0表示農(nóng)機合作社,其他節(jié)點表示待收區(qū),染色體基因的數(shù)量等于待收區(qū)數(shù)量的3倍。染色體分為3層,在第1層中,所有節(jié)點根據(jù)待收區(qū)編號隨機填充,第2層節(jié)點由隨機選擇的k型號收獲機填充,第3層節(jié)點對應(yīng)第2層填充的k型號收獲機的派遣數(shù)量。染色體編碼結(jié)構(gòu)如圖3所示。根據(jù)第2層的信息,k1型號的收獲機依次為待收區(qū)3、2、5、7服務(wù)。

圖3 染色體編碼方式Fig.3 Chromosome encoding method

2.3 初始解構(gòu)造

為構(gòu)造初始解,首先將每個待收區(qū)j按距離分配到最近的農(nóng)機合作社m,然后在每個農(nóng)機合作社覆蓋的待收區(qū)內(nèi),將所有待收區(qū)根據(jù)其時間窗的中心值(Ej+Lj)/2進行排序,如果新增加一個待收區(qū)后不再滿足模型約束條件,則將該待收區(qū)作為調(diào)度路徑的首個區(qū)域劃入到一條新的調(diào)度路徑中,由此得到每個農(nóng)機合作社的初始調(diào)度方案。雖然這種方法得到的目標(biāo)函數(shù)值質(zhì)量較差,但此種方法存在輕微的約束違規(guī),使算法在較短時間內(nèi)就能夠完成初始解的構(gòu)造。

2.4 評價函數(shù)

染色體適應(yīng)度函數(shù)可以根據(jù)模型中目標(biāo)函數(shù)式進行構(gòu)造,個體評價函數(shù)f(x)為目標(biāo)函數(shù)的倒數(shù),公式為

(21)

式中C(x)——目標(biāo)函數(shù)值

2.5 遺傳操作

2.5.1選擇操作

選擇操作采用精英保留策略與輪盤賭相結(jié)合的選擇策略。實現(xiàn)步驟為:先用精英保留策略將每一代種群中一定數(shù)量的最優(yōu)染色體直接保存到下一代,再用輪盤賭的方式對剩下的染色體進行選擇,每條染色體被選中的概率與其適應(yīng)度成正比。

2.5.2交叉操作

在交叉操作中,順序交叉既能保留原有排列基礎(chǔ),又能融合不同排列,故選用順序交叉算子。如圖4所示,從種群中選取一對父代個體1、2作為交叉對象,在父代個體1、2上隨機選擇兩個基因交叉點形成交叉子路徑。復(fù)制父代2中的交叉子路徑置于父代1的最后面,同理,復(fù)制父代1中的交叉子路徑置于父代2的最前面。最后刪除路徑中的重復(fù)基因,由此形成兩個新的子代1、2。

圖4 染色體交叉過程Fig.4 Chromosome crossover process

2.6 變鄰域操作

2.6.1變鄰域結(jié)構(gòu)設(shè)計

使用交換、插入、2-Opt、or-Opt鄰域算子進行變鄰域搜索。交換算子是從當(dāng)前解中隨機選擇兩個不同的節(jié)點,交換兩節(jié)點的位置。插入算子是從當(dāng)前解中隨機選擇一個節(jié)點,將其插入到新的位置。2-Opt算子是從當(dāng)前解中隨機選擇兩個不同的節(jié)點i、j,并將節(jié)點i后的節(jié)點順序進行逆轉(zhuǎn)。or-Opt算子隨機選擇兩個連續(xù)的節(jié)點,將其逆序插入到隨機選擇的節(jié)點j的后面。鄰域結(jié)構(gòu)示意圖如圖5所示。

圖5 鄰域結(jié)構(gòu)示意圖Fig.5 Neighborhood structure diagram

2.6.2隨機擾動

首先設(shè)定鄰域結(jié)構(gòu)Ni={N1,N2,…,Nn},Nn表示第n個鄰域結(jié)構(gòu),對種群中的個體c,隨機選擇一個鄰域結(jié)構(gòu)Ni開始擾動,來破壞當(dāng)前解的局部最優(yōu)解。在預(yù)設(shè)的鄰域搜索次數(shù)內(nèi),嘗試找到改進解c′,則令c=c′;若在該鄰域結(jié)構(gòu)Ni內(nèi)未找到改進解c′,則隨機選擇下一個鄰域結(jié)構(gòu)Ni進行擾動,直到達到預(yù)設(shè)的搜索次數(shù)。通過增加搜索的多樣性和跳出局部最優(yōu)解的限制,從而擴展搜索范圍,使目標(biāo)函數(shù)有機會找到更優(yōu)的解。這種機制能夠有效提升算法的全局搜索能力并改善解的質(zhì)量。

2.6.3自適應(yīng)選擇鄰域方法

每次迭代中, 經(jīng)過計算得到的新解有3種情況, 即新解優(yōu)化了目標(biāo)函數(shù)并成為新的局部最優(yōu)解、新解沒有優(yōu)化但是被接受、新解沒有優(yōu)化且被舍棄。上述3種情況分別對應(yīng)不同的分?jǐn)?shù),每個迭代周期結(jié)束后,鄰域方法的權(quán)重根據(jù)迭代過程中的表現(xiàn)評分變化實現(xiàn)動態(tài)變化。首先對每種鄰域方法Ni設(shè)置一個初始權(quán)重,初始權(quán)重均為1。然后,設(shè)置權(quán)重為1～5之間的整數(shù)。在每次搜索中,隨機選擇一種鄰域方法,如果選擇的鄰域方法產(chǎn)生的解比當(dāng)前最優(yōu)解更好,則將該鄰域的權(quán)重加1,最高可達到5。反之,如果沒有找到更好的解決方案,則將該鄰域方法的權(quán)重減1,最低可達到1。這種方法可以動態(tài)地調(diào)整鄰域結(jié)構(gòu)的權(quán)重,使搜索更加靈活和高效。

2.7 種群管理和停止準(zhǔn)則

為提高整個種群的質(zhì)量,每次迭代結(jié)束后,用最優(yōu)個體替換最差個體,以維持種群大小一致性和多樣性,這種機制能避免算法陷入早熟收斂的狀態(tài)。在保證種群規(guī)模不變的前提下,首先構(gòu)造新的個體作為初始解,再進行遺傳操作,最后利用自適應(yīng)變鄰域搜索方法對其進行改進。

當(dāng)達到最大允許迭代次數(shù)時,GAVNS算法停止迭代,求解過程終止。

3 案例分析

3.1 數(shù)據(jù)來源與收集

黃淮海平原是我國的小麥主要種植區(qū),已有研究表明,每年5月開始,河南南部以及安徽北部等地是小麥聯(lián)合收獲機跨區(qū)作業(yè)的主要輸出地,它們進行跨區(qū)作業(yè)的范圍從幾十千米到幾百千米不等[8]。數(shù)值實驗以河南省駐馬店市為發(fā)散中心,選取周邊72個小麥生產(chǎn)區(qū)縣,根據(jù)實際調(diào)查情況和收集的相關(guān)實驗數(shù)據(jù)對模型進行實例分析。各小麥生產(chǎn)區(qū)縣的小麥種植面積來源于《中國農(nóng)村統(tǒng)計年鑒》,假設(shè)每個區(qū)縣2%的小麥種植面積需要收獲機進行跨區(qū)作業(yè)服務(wù),各區(qū)縣地理位置已知,研究區(qū)位和各小麥生產(chǎn)區(qū)縣需求信息如圖6和表1所示。

表1 小麥生產(chǎn)區(qū)縣需求信息Tab.1 Demand information of wheat production counties

圖6 研究區(qū)位Fig.6 Investigation area

假設(shè)研究區(qū)域共有4個農(nóng)機合作社,分布在4個不同的區(qū)縣,每個區(qū)縣有3種型號的收獲機參與跨區(qū)作業(yè),整個調(diào)度問題將對4個農(nóng)機合作社周圍的72個區(qū)縣提供作業(yè)服務(wù),操作員每個工作日的最大工作時間為10 h。農(nóng)機合作社位置及擁有各型號收獲機數(shù)量如表2所示。

表2 農(nóng)機合作社位置及擁有各型號收獲機數(shù)量Tab.2 Locations of agricultural machinery cooperatives and number of harvesters of each model owned

3.2 模型設(shè)置

數(shù)值實驗采用Windows 10操作系統(tǒng),CPU為i7-12700,模擬平臺使用Matlab 2017a。經(jīng)過反復(fù)測試,算法參數(shù)設(shè)置如下:最大迭代次數(shù)(MG)為700、種群數(shù)量(NP)為100、交叉概率(Pc)為0.9、最大鄰域搜索次數(shù)(MS)為1 000。將相關(guān)數(shù)據(jù)和變量納入構(gòu)建的模型,對于同一實例,算例運行10次,10個目標(biāo)值的平均值作為此實例的結(jié)果。在“三夏”時節(jié),4個農(nóng)機合作社分別收集到前期工單,假設(shè)每個型號的收獲機都有待派遣的任務(wù)。表3給出了農(nóng)機性能參數(shù)及相關(guān)運行費用。

表3 農(nóng)機性能參數(shù)及相關(guān)運行費用Tab.3 Agricultural machinery performance parameters and associated operating costs

根據(jù)我國目前的碳交易價格,假設(shè)碳交易價格Pc為0.052 8元/kg,同時,參考文獻[29-30],將計算碳排放成本公式中的參數(shù)設(shè)置如下:ω0=110、ω1=0、ω2=0、ω3=0.000 375、ω4=8 702、ω5=0、ω6=0,χ0=1.27、χ1=0.061 4、χ2=0、χ3=-0.001 1、χ4=-0.002 35、χ5=0、χ6=0、χ7=-1.33。

3.3 算例計算

3.3.1不同優(yōu)化算法實驗結(jié)果分析

為驗證設(shè)計的遺傳變鄰域搜索算法(GAVNS)的有效性,基于相同環(huán)境另外編寫求解該模型的遺傳算法(Genetic algorithm, GA)、變鄰域搜索算法(Variable neighborhood search, VNS),將GAVNS算法與GA算法、VNS算法進行對比實驗,得到最終結(jié)果如表4所示,其對比迭代曲線如圖7所示。

表4 閉合路徑下3種算法求解結(jié)果對比Tab.4 Comparison of results obtained by three algorithms under closed-path mode

圖7 閉合路徑下3種算法迭代曲線Fig.7 Iteration curves for three algorithms under closed-path mode

從對比結(jié)果來看,在調(diào)度成本上,GAVNS算法求得的最優(yōu)值更低,分別比GA算法和VNS算法少16.41%、11.15%,說明GAVNS算法對降低調(diào)度成本具有顯著意義。在收獲機使用數(shù)和碳排放成本上,GAVNS算法求得的完成作業(yè)任務(wù)需派出387臺收獲機,收獲機使用數(shù)最少,最高減少6.20%;求得的碳排放成本為1.84×105元,優(yōu)于GA算法和VNS算法,最高節(jié)約26.09%,說明GAVNS算法能有效提升每個農(nóng)機合作社的收獲機使用率,減少車輛碳排放,減少環(huán)境污染。從圖7可知,調(diào)度成本隨迭代次數(shù)的增加而降低,GAVNS算法求解模型的速度快于GA算法和VNS算法,在迭代次數(shù)增加至490次左右即可收斂至穩(wěn)定值,得到最優(yōu)解的迭代次數(shù)更低、收斂速度更快,說明該算法具有較好的收斂性和搜索能力。 GAVNS算法求得的懲罰時間更少,有效降低了麥?zhǔn)諔土P成本,為農(nóng)忙時節(jié)麥?zhǔn)兆鳂I(yè)預(yù)留更多有效作業(yè)時間,對保障糧食作物按時收獲具有可行性、合理性和有效性。

3.3.2不同調(diào)度模式的實驗結(jié)果分析

(1)GAVNS算法在閉合路徑下的調(diào)度分析

根據(jù)仿真實驗所選區(qū)域跨區(qū)收獲作業(yè)的實際情況,使用建立的調(diào)度模型和設(shè)計的求解方法進行收獲機跨區(qū)調(diào)度仿真,在仿真實驗中,所有參與跨區(qū)作業(yè)的收獲機組的最優(yōu)調(diào)度路徑如圖8所示,最優(yōu)調(diào)度方案如表5所示。

表5 閉合路徑調(diào)度模式的最優(yōu)調(diào)度方案Tab.5 Optimal scheduling solution for closed-path scheduling mode

圖8 閉合路徑下的最優(yōu)調(diào)度路徑Fig.8 Optimal scheduling path under closed-path mode

從圖8可知,農(nóng)機合作社進行跨區(qū)作業(yè)服務(wù)時,優(yōu)先就近服務(wù),相鄰位置的作業(yè)區(qū)域由同一個農(nóng)機合作社提供服務(wù)。每個收獲機組的路徑清晰,不同路徑間的迂回和交叉情況較少。

由表5可知,調(diào)度成本為3.231 8×106元,收獲機總轉(zhuǎn)運距離為1.66×105km,4個農(nóng)機合作社均派出收獲機組進行跨區(qū)作業(yè)服務(wù),共使用387臺收獲機,每個合作社都有較高的農(nóng)機利用率。4個農(nóng)機合作社派出的收獲機組數(shù)分別為4、5、6、3,每個機組都進行了多個區(qū)縣的跨越,機收的小麥面積分別為3 695.41、4 851.55、6 517.45、3 815.23 hm2,同時每個合作社派出的收獲機組具有一定的相似性,如收獲面積、轉(zhuǎn)運時間等,說明設(shè)計的GAVNS算法能夠根據(jù)實際情況為合作社派出的收獲機組規(guī)劃合理的作業(yè)路線,分配適量的作業(yè)任務(wù),保證跨區(qū)作業(yè)的準(zhǔn)時性和均衡性。由式(6)可知,在不考慮收獲機田間作業(yè)的油耗下,碳排放成本與轉(zhuǎn)運距離存在正相關(guān)關(guān)系,每臺收獲機轉(zhuǎn)運過程中每行駛1 km平均產(chǎn)生0.28 kg二氧化碳,轉(zhuǎn)運過程中的燃油消耗會導(dǎo)致一定程度的大氣污染,同時運輸成本和碳排放成本占總調(diào)度成本的10.85%,在進行收獲機跨區(qū)調(diào)度時,對收獲機組的調(diào)度不僅要考慮經(jīng)濟成本,也要兼顧環(huán)境成本。

(2)GAVNS算法在開放路徑下的調(diào)度分析

在實際的收獲機跨區(qū)作業(yè)中,在小麥?zhǔn)斋@前期,為搶占農(nóng)時,合作社派出的收獲機往往在完成當(dāng)前作業(yè)后不返回合作社,而是繼續(xù)尋找下一個作業(yè)點,此時收獲機跨區(qū)調(diào)度是一個開放的多庫、多機型的車輛路徑問題,在開放路徑中,GAVNS算法的迭代曲線如圖9所示,其最優(yōu)調(diào)度方案如表6所示。

表6 開放路徑調(diào)度模式的最優(yōu)調(diào)度方案Tab.6 Optimal scheduling solution for open-path scheduling mode

圖9 開放路徑下GAVNS算法迭代曲線Fig.9 Iteration curves of GAVNS algorithm under open-path mode

由表6可知,在開放路徑下,完成所有收獲任務(wù)的調(diào)度成本為2.656 3×106元、轉(zhuǎn)移距離為 1.112×105km, 相比閉合路徑,調(diào)度成本、轉(zhuǎn)移距離分別降低17.76%、33.02%,其主要原因是在開放路徑中,不考慮每個合作社派出的收獲機組的返回路徑,減少了路徑代價,具有較高的經(jīng)濟性。完成跨區(qū)收獲共派出358臺收獲機,派遣的收獲機數(shù)比閉合路徑少7.49%,該模式能有效提升收獲機的使用率,同時各收獲機組存在收獲面積和轉(zhuǎn)運距離的偏差,說明收獲機組的路徑規(guī)劃基本遵循了小麥待收區(qū)的時間窗、收獲面積的變化規(guī)律。在開放路徑下,碳排放成本為1.35×104元,較閉合路徑降低26.63%,兩種調(diào)度模式都驗證了碳排放成本與轉(zhuǎn)運距離存在正相關(guān)關(guān)系,在轉(zhuǎn)運距離降低的情況下,碳排放成本也會減少,此種調(diào)度模式更有利于降低二氧化碳的排放,減少大氣污染,推動低碳農(nóng)業(yè)的發(fā)展。

4 結(jié)論

(1)為降低“三夏”時節(jié)收獲機跨區(qū)調(diào)度成本,兼顧環(huán)境保護,本文構(gòu)建合理的多庫、多機型的農(nóng)機跨區(qū)調(diào)度模型,設(shè)計遺傳變鄰域搜索算法(GAVNS)求解,通過黃淮海平原72個區(qū)縣的實例證明模型與算法的有效性。

(2)計算結(jié)果表明,GAVNS算法的尋優(yōu)策略在降低調(diào)度成本、轉(zhuǎn)運距離和懲罰時間方面均具備優(yōu)勢,GAVNS算法求得的目標(biāo)函數(shù)值較GA算法、VNS算法分別少16.41%、11.15%。對比兩種農(nóng)機跨區(qū)調(diào)度模式,開放路徑不考慮收獲機組的返回路徑,農(nóng)機合作社提供跨區(qū)作業(yè)服務(wù)的效率更高,相比閉合路徑,轉(zhuǎn)移距離減少33.02%,調(diào)度成本減少17.76%,具有更好的經(jīng)濟性。