汪浩祥 曹光喬 閆子彤 陳 聰

(1.南京農(nóng)業(yè)大學(xué)信息管理學(xué)院, 南京 210031; 2.農(nóng)業(yè)農(nóng)村部南京農(nóng)業(yè)機械化研究所, 南京 210014)

0 引言

隨著我國現(xiàn)代化農(nóng)業(yè)的發(fā)展,在農(nóng)業(yè)生產(chǎn)中對突發(fā)情況的高效應(yīng)對和處理是現(xiàn)代化農(nóng)業(yè)發(fā)展的重要組成部分,農(nóng)業(yè)生產(chǎn)中出現(xiàn)的應(yīng)急調(diào)度問題也被越來越多的專家學(xué)者所關(guān)注和研究。例如,在小麥?zhǔn)斋@時期遇到降雨,農(nóng)機合作社如果不及時對受影響的農(nóng)田快速調(diào)度資源完成搶收工作,則會給農(nóng)民造成巨大損失。

當(dāng)前應(yīng)急調(diào)度方面的研究主要集中在重大突發(fā)事件發(fā)生后資源的調(diào)配:如LE-ANH等[1]針對國內(nèi)運輸系統(tǒng)提出了一種動態(tài)車輛應(yīng)急調(diào)度啟發(fā)式方法,并驗證了該方法的性能。ZENG等[2]對自然災(zāi)害發(fā)生時的應(yīng)急資源調(diào)度問題進行了研究,以運輸距離最短為目標(biāo),以最大行駛里程和最晚到達時間為約束條件建立模型,將蟻群算法和遺傳算法相結(jié)合對模型進行求解。楊海強等[3]建立了應(yīng)急車輛調(diào)度模型,又將遺傳算法進行改進并求解。鞏玲君等[4]研究了重大突發(fā)事件發(fā)生后應(yīng)急物資生產(chǎn)任務(wù)的優(yōu)化問題,趙明等[5]針對大規(guī)模災(zāi)難發(fā)生時首批生命物資的應(yīng)急調(diào)度建模及優(yōu)化求解問題進行了研究。

目前針對農(nóng)機應(yīng)急調(diào)度問題研究較少,主要有:劉卉等[6]提出了矢量緩沖區(qū)算法、柵格緩沖區(qū)算法來解決農(nóng)機收獲面積實時、精準(zhǔn)的獲取問題,并在全球衛(wèi)星導(dǎo)航系統(tǒng)下對兩種測量方法進行了驗證。張璠等[7]提出了根據(jù)農(nóng)田與車場距離,結(jié)合農(nóng)機貢獻度來確定農(nóng)田任務(wù)排序的多對多的應(yīng)急調(diào)度算法,解決農(nóng)機應(yīng)急調(diào)度問題。黃凰等[8]針對農(nóng)田與農(nóng)機的匹配與調(diào)度需求問題,綜合考慮農(nóng)戶滿意度、多農(nóng)機站協(xié)同、訂單數(shù)量、農(nóng)田面積和位置坐標(biāo)等因素,建立帶有模糊時間窗并以調(diào)度總時長最小和調(diào)度農(nóng)機數(shù)量最少為目標(biāo)的多農(nóng)機站即時響應(yīng)調(diào)度數(shù)學(xué)模型。設(shè)計了基于保留優(yōu)秀父代基因的改進遺傳算法的農(nóng)機調(diào)度系統(tǒng),完成多農(nóng)機站響應(yīng)多農(nóng)田的同時作業(yè)需求的任務(wù)。MA等[9]參考現(xiàn)有農(nóng)機調(diào)度模式,結(jié)合農(nóng)業(yè)生產(chǎn)的實際需求,基于資源共享的思想,將軟時間窗和硬時間窗相結(jié)合,開展農(nóng)機動態(tài)需求調(diào)度策略研究。HU等[10]提出了兩階段分析方法,將不同規(guī)劃層次之間的數(shù)據(jù)連接起來,旨在建立農(nóng)機機隊維修服務(wù)的動態(tài)能力規(guī)劃方法,降低維護服務(wù)商的運營成本。

在農(nóng)機調(diào)度方面,吳才聰?shù)萚11]則通過構(gòu)建農(nóng)田收獲的成本矩陣,通過匈牙利法分配收獲車輛,實現(xiàn)在時間窗限制下車輛運輸成本的最小化。王雪陽等[12-14]也研究了在時間窗限制下的農(nóng)機調(diào)度問題,使用多種啟發(fā)式算法對其最小運輸距離進行求解,并且比較了這些啟發(fā)式算法的優(yōu)缺點。張帆等[15]針對農(nóng)機裝備跨區(qū)作業(yè)存在作業(yè)任務(wù)重、轉(zhuǎn)移范圍大、作業(yè)時效性強等問題,開展了基于改進遺傳算法的多機協(xié)同作業(yè)任務(wù)調(diào)度方法研究。HE等[16]提出了一種面向零碎農(nóng)田的聯(lián)合收獲獲機最優(yōu)調(diào)度操作模型。以聯(lián)合收獲獲機間收獲時間差異最小為約束條件,目標(biāo)函數(shù)是小麥?zhǔn)斋@周期最小。WANG等[17]研究了一種結(jié)合操作員分配的收獲機調(diào)度問題。通過確定收獲機和操作員的組合以及收獲機的路線,達到總工作時間和成本最小化的目標(biāo)。然而,在農(nóng)業(yè)實際生產(chǎn)活動中,大量的作業(yè)活動會受到降雨的影響[18]。特別在小麥?zhǔn)斋@過程中,因雨天小麥脫粒率會降低,所以收獲機在雨天不能進行小麥?zhǔn)斋@作業(yè),那么在小麥?zhǔn)斋@時期內(nèi)有突如其來的天氣變化,小麥的可作業(yè)時間窗會發(fā)生改變,若收獲機還繼續(xù)按原序列調(diào)度,可能會造成農(nóng)田收獲時間延遲等現(xiàn)象的發(fā)生。

本文擬將受雨天影響的農(nóng)田設(shè)為應(yīng)急農(nóng)田,并重新根據(jù)應(yīng)急度排序,且雨后時間窗為空的農(nóng)田排在最前,設(shè)計基于改進遺傳算法的收獲機應(yīng)急調(diào)度算法,通過動態(tài)改變原收獲機收獲路線,為應(yīng)急農(nóng)田優(yōu)先提供收獲服務(wù),盡可能降低因天氣突然變化給農(nóng)戶帶來的損失。

1 問題描述與模型建立

1.1 問題描述

為方便問題描述,進行相關(guān)定義:

提前響應(yīng)時間:為對應(yīng)急農(nóng)田優(yōu)先調(diào)度的時間點,通常為可作業(yè)時間與下雨時間有重合的農(nóng)田中最早的允許開始作業(yè)時間窗。

應(yīng)急農(nóng)田:應(yīng)急農(nóng)田包括兩種,一種是可作業(yè)時間窗與下雨時間有重合的農(nóng)田,另一種是在響應(yīng)時間后、下雨前還未作業(yè)的農(nóng)田。

由于響應(yīng)時間到來時,可作業(yè)時間與下雨時間有交集的農(nóng)田將會優(yōu)先插入收獲機序列應(yīng)急調(diào)度,當(dāng)應(yīng)急農(nóng)田作業(yè)結(jié)束后,在響應(yīng)時間之后、下雨之前還未收獲農(nóng)田的可作業(yè)時間窗為0,所以這里也將響應(yīng)時間后、下雨時間之前的還未收獲農(nóng)田也設(shè)為應(yīng)急農(nóng)田。如圖1所示,其中,F2為在響應(yīng)時間后下雨時間前還未收獲的農(nóng)田,F3、F4的可作業(yè)時間與下雨時間有重合,所以F2、F3、F4為應(yīng)急農(nóng)田,F1在響應(yīng)時間前已完成作業(yè),F5與下雨時間沒有交集且不在響應(yīng)時間后下雨事件前,都不屬于應(yīng)急農(nóng)田。

圖1 應(yīng)急農(nóng)田示意圖Fig.1 Schematic of emergency farmland

應(yīng)急度:為待收獲農(nóng)田面積和雨后時間窗的比值。

找出應(yīng)急農(nóng)田后計算這些農(nóng)田的應(yīng)急度,根據(jù)應(yīng)急度定義,可作業(yè)時間窗與下雨時間段重合的農(nóng)田中待收獲面積越大且雨后時間窗越小,則該塊農(nóng)田的應(yīng)急程度越高,雨后時間窗為零則排在最前,且按農(nóng)田的開始可收獲時間窗從早到晚排序。這樣就可以在暴風(fēng)雨到來前盡可能最大限度地收獲應(yīng)急程度高的農(nóng)田,而相對面積小、雨后時間窗大的農(nóng)田,可以放在雨后進行收獲。如圖1所示,農(nóng)田F2雨后可作業(yè)時間窗為零排在最前,F3、F4按應(yīng)急度排在后。

本文收獲機應(yīng)急調(diào)度問題可具體描述為:根據(jù)預(yù)報,在獲知收獲期的天氣變化后,為應(yīng)對因降雨對小麥?zhǔn)斋@的影響,減少損失,農(nóng)機合作社的相關(guān)人員根據(jù)匯總的農(nóng)戶農(nóng)田的相關(guān)信息和收獲機的作業(yè)情況,確定提前響應(yīng)時間和應(yīng)急農(nóng)田,當(dāng)時間節(jié)點到達響應(yīng)時間時,開始應(yīng)急調(diào)度,先將應(yīng)急農(nóng)田從原序列中剔除,并搜索可使用收獲機,因為在應(yīng)急調(diào)度開始后,收獲機需要先完成當(dāng)前正在收獲的農(nóng)田,再去進行應(yīng)急作業(yè),所以需要剔除完成當(dāng)前作業(yè)后,時間節(jié)點已經(jīng)到達開始下雨時間的收獲機。將排序好的應(yīng)急農(nóng)田按目標(biāo)函數(shù)最優(yōu)優(yōu)先插入收獲機原序列中,對收獲機進行路線修正,優(yōu)先調(diào)度應(yīng)急農(nóng)田。

本文以第一塊農(nóng)田的開始收獲時間為時間軸零點,以最后一塊農(nóng)田的結(jié)束收獲時間為1建立時間軸t,則該地區(qū)的整個收獲時間為(0,1),設(shè)a、b、c、d∈(0,1)且a

表1 各個時間節(jié)點狀態(tài)反應(yīng)Tab.1 State response of each time node

1.2 數(shù)學(xué)模型

本文研究的是多個出發(fā)點與多個作業(yè)點即多對多模式的收獲機調(diào)度問題,也就是根據(jù)農(nóng)田的時間窗、作業(yè)面積、地理位置等因素,為多個車場中的收獲機設(shè)計作業(yè)順序的過程。首先,針對該收獲機應(yīng)急調(diào)度問題提出假設(shè)前提條件:

(1)假設(shè)收獲機的作業(yè)能力和轉(zhuǎn)移速度在單位時間內(nèi)都是一樣的,并且不受道路狀況的影響。

(2)各收獲機的作業(yè)能力可以完全滿足作業(yè)點的需求。

(3)假設(shè)每塊農(nóng)田對收獲機的需求類型僅有一種。

(4)在每一次調(diào)度過程中,每輛收獲機只能被調(diào)度一次,且完成作業(yè)后返回原出發(fā)車場。

(5)在每次調(diào)度過程中,每輛被調(diào)度的收獲機至少作業(yè)一個農(nóng)田,即保證每次調(diào)度可靠性。

(6)假設(shè)每塊農(nóng)田僅能被一輛收獲機訪問。

(7)不考慮道路堵塞等一些特殊路況的發(fā)生。

(8)假設(shè)收獲機從車場到達農(nóng)田作業(yè)點所經(jīng)過的路徑是兩點之間的最短路徑。

(9)假設(shè)下雨時間可精準(zhǔn)預(yù)測。

本文建立因天氣變化導(dǎo)致的時間窗變動的收獲機調(diào)度模型,綜合考慮收獲機轉(zhuǎn)移時間、提前到達等待時間、延遲時間,以及應(yīng)急調(diào)度中收獲機轉(zhuǎn)移時間、應(yīng)急農(nóng)田延遲時間、原序列農(nóng)田偏離時間等,并依據(jù)該模型假設(shè)條件的前提下,建立收獲機調(diào)度多目標(biāo)數(shù)學(xué)模型。

設(shè)該區(qū)域的農(nóng)田收獲時間窗為(0,1),a、b、c、d∈(0,1)且a

(1)確定目標(biāo)函數(shù)

在收獲機應(yīng)急調(diào)度中包括兩方面的成本,又因在功率相同的情況下,成本只與時間有關(guān),所以此模型只考慮時間。一方面是收獲機調(diào)度涉及到的收獲機轉(zhuǎn)移時間、提前到達等待或延遲時間,另一方面是應(yīng)急農(nóng)田分配時收獲機轉(zhuǎn)移時間最小、應(yīng)急作業(yè)拖延時間最小及農(nóng)田收獲的偏離時間最小。

minZ=(1-θ)Z1+θZ2

(1)

其中

(2)

(3)

式中M——收獲機場站個數(shù)

K——收獲機總臺數(shù)

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

Qm——第m個車場擁有的車輛數(shù)目,m∈{1,2,…,M}

i、j——農(nóng)田編號,i,j∈{1,2,…,N},i≠j

Ei——第i塊農(nóng)田允許開始的最早時間

Li——第i塊農(nóng)田允許結(jié)束的最晚時間

li——第i塊農(nóng)田的實際完成作業(yè)時間

ri——收獲機到達第i塊農(nóng)田的時間

r′i——修正路線后收獲機到達第i塊農(nóng)田的時間

θ——條件變量

公式(2)表示初始收獲機調(diào)度涉及到的收獲機轉(zhuǎn)移時間、提前到達等待時間和總延遲時間,公式(3)是應(yīng)急農(nóng)田分配時收獲機轉(zhuǎn)移時間、應(yīng)急農(nóng)田作業(yè)拖延時間和農(nóng)田收獲的偏離時間。如式(1)所示,當(dāng)時間窗為(0,b)時,此時沒有發(fā)生應(yīng)急調(diào)度,計算目標(biāo)函數(shù)為收獲機轉(zhuǎn)移時間、提前等待或延遲時間最小;當(dāng)時間窗為(b,1)時,觸發(fā)應(yīng)急調(diào)度,此時計算目標(biāo)函數(shù)為應(yīng)急農(nóng)田分配時收獲機轉(zhuǎn)移時間最小、應(yīng)急作業(yè)拖延時間最小及農(nóng)田收獲的偏離時間最小。

(2)約束條件

根據(jù)本文假設(shè)及問題描述,模型存在約束

(4)

(5)

(6)

(7)

(8)

(9)

ei≤Ei(i∈{1,2,…,N})

(10)

(11)

(12)

ei——第i塊農(nóng)田的實際開始作業(yè)時間

t——時間狀態(tài)

公式(4)表示每個收獲機服務(wù)站能夠調(diào)出的收獲機數(shù)量,須小于等于該車場擁有的收獲機數(shù)量;公式(5)表示每個車場中發(fā)出的收獲機在完成相應(yīng)的作業(yè)任務(wù)后返回原車場;公式(6)、(7)表示每個農(nóng)田作業(yè)點被訪問次數(shù)與所需收獲機數(shù)相等;公式(8)表示確保發(fā)生應(yīng)急調(diào)度時,車輛從它所在的農(nóng)田出發(fā);公式(9)表示流量守恒定律,即收獲機到達某節(jié)點后需保證離開該點;公式(10)表示農(nóng)田必須在開始時間窗之后才能開始作業(yè)時間;公式(11)、(12)表示條件變量。

2 基于改進遺傳算法的收獲機應(yīng)急調(diào)度算法

基于上述模型,本文將遺傳算法計算步驟中的編碼模塊進行改進,提出了兩級分階段染色體編碼方式;對遺傳操作中的選擇算子,使用輪盤賭注方法選擇最佳個體;對于交叉算子,提出單個染色體指定位置交叉來降低不可行解的數(shù)量,使遺傳算法更適用于本文模型。

2.1 兩級多段編碼方式

兩級多段編碼方式的實現(xiàn)主要分為3個步驟:首先,根據(jù)農(nóng)田的可作業(yè)時間窗,按照允許開始作業(yè)時間的先后進行排序作為第1級編碼;其次將排好序的農(nóng)田所需的車場及車輛編碼作為第2級;最后,將第2級編碼按第1級排序先后進行連接組合,構(gòu)成完整的染色體編碼。

2.1.1一級編碼

根據(jù)農(nóng)田的開始作業(yè)時間窗的先后進行排序,這樣可以表示出不同農(nóng)田作業(yè)時間的串并問題,按排序先后作業(yè)串行的農(nóng)田,并行的農(nóng)田并行作業(yè)。假設(shè)某區(qū)域有n塊農(nóng)田,將n塊農(nóng)田按照可作業(yè)時間窗進行排序,如圖2所示。

圖2 一級編碼Fig.2 First level coding

農(nóng)田排序方法:根據(jù)農(nóng)田作業(yè)點的可作業(yè)時間窗將農(nóng)田按照從早到晚排序。假設(shè)農(nóng)田F1和農(nóng)田F2的可作業(yè)時間窗為[E1,L1]和[E2,L2],當(dāng)[E1,L1]∩[E2,L2]等于空集時,農(nóng)田F1和農(nóng)田F2不存在并行任務(wù),且農(nóng)田可作業(yè)時間窗允許開始時間早的農(nóng)田作業(yè)點排序在前;若[E1,L1]∩[E2,L2]≠?且[E1,L1]≠[E2,L2]時,說明農(nóng)田F1和農(nóng)田F2時間窗存在交集,這里規(guī)定為允許開始時間早的農(nóng)田排序在前,若允許開始時間相同,則允許最晚結(jié)束時間最早的排序在前;若[E1,L1]=[E2,L2],說明兩農(nóng)田作業(yè)點允許開始作業(yè)時間和最晚結(jié)束作業(yè)時間窗全部相同,規(guī)定為并行任務(wù)且并行執(zhí)行。定義并行任務(wù)的思想為:首先將農(nóng)田作業(yè)點按時間窗先后從早到晚排序,排序最前的農(nóng)田作業(yè)點的序列號為1,按照排序順序依次取作業(yè)點農(nóng)田i與農(nóng)田i+1進行判斷是否為并行任務(wù),若是,則兩農(nóng)田序列號相同,若不是,序列號加1,按照排序依次判斷到最后一個作業(yè)點,序列號越小的農(nóng)田越優(yōu)先作業(yè)。

2.1.2二級編碼

二級編碼由分配到農(nóng)田的車場編號與收獲機編號組成,則每塊農(nóng)田由2個編號組合而成,如圖3所示第i塊農(nóng)田編碼,Im表示第i塊農(nóng)田的車場編碼,Ikm表示第i塊農(nóng)田第m個車場編號為k的收獲機編碼。

圖3 二級編碼Fig.3 Second level coding

2.1.3兩級編碼連接

將兩級編碼連接起來,構(gòu)成完整的染色體,即將所有農(nóng)田二級編碼按照一級農(nóng)田排序連接起來,如圖4所示。

圖4 兩級編碼連接Fig.4 Code linkage of two levels

2.2 遺傳操作設(shè)計

2.2.1適應(yīng)度函數(shù)

遺傳算法在搜索進化過程中一般不需要其他外部信息,僅用評估函數(shù)來評估個體或解的優(yōu)劣,并作為以后遺傳操作的依據(jù),個體被遺傳的概率與其適值是成正比的,所以適應(yīng)度函數(shù)設(shè)計直接影響到遺傳算法的性能。本文使用最小路徑倒數(shù)作為適應(yīng)度函數(shù)。

2.2.2選擇

本文通過輪盤賭方法選擇算子,基于優(yōu)勝劣汰的思想。根據(jù)染色體的適應(yīng)度值選擇算子,個體被選擇的概率與其適應(yīng)度成正比,算法主要流程如下:

(1)通過計算種群(i=1,2,…,M)個體染色體適應(yīng)度與總適應(yīng)度之比得出選擇概率,適應(yīng)度函數(shù)為

(13)

適應(yīng)度函數(shù)越大,個體被選擇的概率越大。

(2)計算個體累計概率,染色體x[i]的累計概率為

(14)

2.2.3交叉

將收獲機調(diào)度問題與染色體編碼結(jié)合起來進行考慮染色體交叉方式的設(shè)計。本文將基本遺傳算法的交叉方式進行改進,采用單點交叉方式,這樣有利于減少不可行解的數(shù)量。

本文用5塊農(nóng)田的收獲機調(diào)度來簡單舉例說明交叉方式,如圖5a取任意兩條染色體作為父代:p(3 2 2 2 1 2 3 2 3 1)、q(2 2 3 3 3 3 1 2 2 2),隨機產(chǎn)生一個[0,1]之間的數(shù),如果該數(shù)小于自適應(yīng)交叉概率Pc,則兩個染色體進行交叉操作,否則繼續(xù)產(chǎn)生隨機數(shù)判斷之后的染色體是否交叉。根據(jù)編碼方式可知有意義的交叉點為{2,4,6,8},在這些可交叉點中隨機搜索一個交叉點,假設(shè)生成的交叉點為4,如圖5b,則分別在兩個父代染色體第4位后進行交叉變換,得到兩個子代染色體結(jié)果為:p′(3 2 2 2 3 3 1 2 2 2)、q′(2 2 3 3 1 2 3 2 3 1),如圖5c。最后將交叉后的群體S復(fù)制到S1中繼續(xù)進行后續(xù)操作。

圖5 p,q兩條染色體交叉示意圖Fig.5 Crossing two chromosomes p,q

2.2.4變異

為了進一步加強對未知空間的搜索,遺傳算法的變異操作在遺傳操作中占據(jù)非常重要的位置。區(qū)別于二進制編碼的變異操作,本文使用的是自然數(shù)編碼,變異在染色體某個基因值即Im、Ikm中隨機產(chǎn)生,產(chǎn)生概率為自適應(yīng)變異率PM,即隨機選取的一個[0,1]之間的數(shù)值,若該隨機數(shù)小于自適應(yīng)變異率PM,則進行變異操作。用上述例子說明變異方式:如圖6a,隨機取交叉后的兩條染色體p′(3 2 2 2 3 3 1 2 2 2)、q′(2 2 3 3 1 2 3 2 3 1)作為父代染色體,假設(shè)隨機搜索的變異點為1和3處,如圖6b,那么需要將兩條父代染色體的第1位和第3位進行交換來進行變異操作,結(jié)果為p″(2 2 3 2 3 3 1 2 2 2)、q″(3 2 2 3 1 2 3 2 3 1),如圖6c。最后將變異后的群體S1復(fù)制到S2中繼續(xù)進行后續(xù)操作。

圖6 染色體p′、q′變異示意圖Fig.6 Schematic diagram of chromosome p′、q′ variation

3 算法仿真

3.1 算例描述

河北省石家莊市正定縣南樓鄉(xiāng)東里雙村(114.69°E,38.27°N)位于華北平原,地勢平緩,東南距縣城17 km,距鄉(xiāng)政府8 km。是一個以種植為主的農(nóng)業(yè)村,其主要種植作物為小麥。該區(qū)域農(nóng)田地圖如圖7所示。

圖7 研究區(qū)示意圖Fig.7 Schematic of study area

該村小麥?zhǔn)斋@主要依靠現(xiàn)有一個農(nóng)業(yè)機械合作社,在小麥?zhǔn)斋@季節(jié)到來時,合作社工作人員根據(jù)經(jīng)驗來調(diào)度小麥?zhǔn)斋@機進行作業(yè),該村農(nóng)田基本上為散戶,小麥種植時間雖然季節(jié)上沒有差異,但具體種植時間和小麥品種還是有差異,做不到完全一致,但是由于人工調(diào)度缺乏科學(xué)合理性,經(jīng)常會有農(nóng)戶農(nóng)田因收獲機供應(yīng)不足而延遲收獲,給農(nóng)戶帶來很大的損失。

根據(jù)實際調(diào)查可知東里雙村小麥?zhǔn)斋@期大約在6月9—20日之間,若該年夏季風(fēng)較強,華北平原將進入雨季,對該區(qū)域的小麥?zhǔn)斋@期造成影響。該村在2018年小麥?zhǔn)斋@期遭遇了暴風(fēng)雨天氣,在2018年6月12日10時突然預(yù)報小麥?zhǔn)斋@期13日4時至14日0時要下雨。同樣,以該村最南面的農(nóng)田建立橫坐標(biāo),以該村最西面的農(nóng)田建立縱坐標(biāo),以6月9日0時為零點建立時間軸,且以小時為單位,農(nóng)田、車場信息如表2、3所示。

農(nóng)業(yè)機械合作社在東里雙村,共設(shè)有3個車場用來停放收獲機,每個車場擁有3輛收獲機,參考實際情況,設(shè)定收獲機各項參數(shù)如表3所示。

表3 收獲機參數(shù)設(shè)置Tab.3 Harvester parameters

收獲機場站個數(shù)M為3,車場K1、K2、K3擁有收獲機數(shù)量為3臺。

3.2 算法步驟

該區(qū)域小麥?zhǔn)斋@期時間窗為[0,300 h],根據(jù)預(yù)報下雨時間令RainTime=[100,120],確定提前反應(yīng)時間Reaction=15,也就是應(yīng)急調(diào)度時間段為[85,100],則在這段時間內(nèi)需要根據(jù)收獲機修正后的路線,將應(yīng)急農(nóng)田優(yōu)先調(diào)度。

算法步驟設(shè)計如下:

(1)計算農(nóng)田間及車場與農(nóng)田間的距離,按農(nóng)田時間窗先后生成農(nóng)田作業(yè)序列,按目標(biāo)函數(shù)最優(yōu)原則對每塊農(nóng)田進行車輛分配,生成調(diào)度方案t時刻,并計算各個農(nóng)田的收獲機到達時間與完成時間,令t=0。

(2)執(zhí)行調(diào)度方案t時刻,t=t+1。

(3)判斷t=a?是則設(shè)置b值并繼續(xù);否則轉(zhuǎn)步驟(2)。

(4)執(zhí)行調(diào)度方案t時刻,t=t+1。

(5)判斷t=b?是則繼續(xù);否則轉(zhuǎn)步驟(4)。

(6)生成應(yīng)急農(nóng)田序列,生成執(zhí)行完當(dāng)前任務(wù)時間點在(b,c)內(nèi)的可應(yīng)急調(diào)度的收獲機序列,并獲取位置,計算應(yīng)急農(nóng)田間及收獲機到應(yīng)急農(nóng)田的距離,按目標(biāo)函數(shù)最優(yōu)原則將應(yīng)急農(nóng)田分配到每輛可應(yīng)急調(diào)度的收獲機,修正收獲機路線,更新調(diào)度方案t時刻。

(7)執(zhí)行調(diào)度方案t時刻,t=t+1。

(8)判斷t=c?是則繼續(xù);否則轉(zhuǎn)步驟(7)。

(9)停止作業(yè),t=t+1。

(10)判斷t=d?是則繼續(xù);否則轉(zhuǎn)步驟(9)。

(11)繼續(xù)執(zhí)行調(diào)度方案t時刻,t=t+1。

(12)判斷t=1?是則繼續(xù);否則轉(zhuǎn)步驟(11)。

(13)結(jié)束。

3.3 運行結(jié)果

設(shè)置RainTime=[100,120]和Reaction=15后運行,可得到需應(yīng)急調(diào)度的農(nóng)田排序為45、14、24、25、17、36、27、41,總面積為63 333.65 m2,將這些農(nóng)田設(shè)置為應(yīng)急農(nóng)田,將該實例問題運行10次,結(jié)果如表4所示。

表4 仿真運行結(jié)果Tab.4 Instance run results

按照實際情況及本文調(diào)度目標(biāo),農(nóng)機合作社將選擇一個成本最低且延遲時間最小的方案作為收獲機調(diào)度方案,查看表4可以發(fā)現(xiàn)該模型第7次求解的總時長最低且無延遲,可以選取該次求解結(jié)果作為初始配送方案。

該次運行結(jié)果的各個收獲機的路徑如表5所示。應(yīng)急農(nóng)田的收獲機分配結(jié)果如表6所示。

表5 收獲機作業(yè)路徑Tab.5 Operation path of harvester

表6 應(yīng)急農(nóng)田收獲機分配結(jié)果Tab.6 Results of emergency farm harvester distribution

為方便計算機仿真,表5、6中收獲機路線和應(yīng)急農(nóng)田為結(jié)點編號,農(nóng)田編號為結(jié)點編號減3。為此,從表5和表6可看出,需要應(yīng)急調(diào)度的農(nóng)田編號為45、14、24、25、17、36、27和41,分別由2號車場編號為3的收獲機、3號車場編號為3的收獲機、1號車場編號為1的收獲機、3號車場編號為2的收獲機、2號車場編號為2的收獲機、3號車場編號為1的收獲機、2號車場編號為1的收獲機、1號車場編號為3的收獲機派去執(zhí)行應(yīng)急作業(yè)。

收獲機調(diào)度路徑圖如圖8所示。其中橫、縱坐標(biāo)分別表示起點出發(fā)正南和正西方向。

圖8 收獲機調(diào)度路徑圖Fig.8 Scheduling path of harvester

4 結(jié)束語

研究了天氣變化引起的農(nóng)田時間窗變動的收獲機應(yīng)急調(diào)度問題,建立了因天氣變化導(dǎo)致的時間窗動態(tài)變動的收獲機調(diào)度模型,綜合考慮收獲機轉(zhuǎn)移時間、提前到達等待時間、延遲時間,以及應(yīng)急調(diào)度中收獲機轉(zhuǎn)移時間、應(yīng)急農(nóng)田延遲時間、原序列農(nóng)田偏離時間等,建立收獲機調(diào)度多目標(biāo)數(shù)學(xué)模型。設(shè)計了改進遺傳算法對模型進行求解,并通過選取實例進行仿真,結(jié)果表明,在農(nóng)作物收獲時期,通過本文對天氣變化導(dǎo)致的農(nóng)田時間窗變動的應(yīng)急調(diào)度問題的研究,可避免或降低因天氣變化給農(nóng)戶帶來的損失。