天氣變化情形下基于動態時間窗的收獲機應急調度技術

汪浩祥 曹光喬 閆子彤 陳 聰

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

0 引言

隨著我國現代化農業的發展,在農業生產中對突發情況的高效應對和處理是現代化農業發展的重要組成部分,農業生產中出現的應急調度問題也被越來越多的專家學者所關注和研究。例如,在小麥收獲時期遇到降雨,農機合作社如果不及時對受影響的農田快速調度資源完成搶收工作,則會給農民造成巨大損失。

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

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

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

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

1 問題描述與模型建立

1.1 問題描述

為方便問題描述,進行相關定義:

提前響應時間:為對應急農田優先調度的時間點,通常為可作業時間與下雨時間有重合的農田中最早的允許開始作業時間窗。

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

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

圖1 應急農田示意圖Fig.1 Schematic of emergency farmland

應急度:為待收獲農田面積和雨后時間窗的比值。

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

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

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

表1 各個時間節點狀態反應Tab.1 State response of each time node

1.2 數學模型

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

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

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

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

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

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

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

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

(8)假設收獲機從車場到達農田作業點所經過的路徑是兩點之間的最短路徑。

(9)假設下雨時間可精準預測。

本文建立因天氣變化導致的時間窗變動的收獲機調度模型,綜合考慮收獲機轉移時間、提前到達等待時間、延遲時間,以及應急調度中收獲機轉移時間、應急農田延遲時間、原序列農田偏離時間等,并依據該模型假設條件的前提下,建立收獲機調度多目標數學模型。

設該區域的農田收獲時間窗為(0,1),a、b、c、d∈(0,1)且a

(1)確定目標函數

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

minZ=(1-θ)Z1+θZ2

(1)

其中

(2)

(3)

式中M——收獲機場站個數

K——收獲機總臺數

N——農田總數

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

i、j——農田編號,i,j∈{1,2,…,N},i≠j

Ei——第i塊農田允許開始的最早時間

Li——第i塊農田允許結束的最晚時間

li——第i塊農田的實際完成作業時間

ri——收獲機到達第i塊農田的時間

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

θ——條件變量

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

(2)約束條件

根據本文假設及問題描述,模型存在約束

(4)

(5)

(6)

(7)

(8)

(9)

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

(10)

(11)

(12)

ei——第i塊農田的實際開始作業時間

t——時間狀態

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

2 基于改進遺傳算法的收獲機應急調度算法

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

2.1 兩級多段編碼方式

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

2.1.1一級編碼

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

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

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

2.1.2二級編碼

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

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

2.1.3兩級編碼連接

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

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

2.2 遺傳操作設計

2.2.1適應度函數

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

2.2.2選擇

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

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

(13)

適應度函數越大,個體被選擇的概率越大。

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

(14)

2.2.3交叉

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

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

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

2.2.4變異

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

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

3 算法仿真

3.1 算例描述

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

圖7 研究區示意圖Fig.7 Schematic of study area

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

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

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

表3 收獲機參數設置Tab.3 Harvester parameters

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

3.2 算法步驟

該區域小麥收獲期時間窗為[0,300 h],根據預報下雨時間令RainTime=[100,120],確定提前反應時間Reaction=15,也就是應急調度時間段為[85,100],則在這段時間內需要根據收獲機修正后的路線,將應急農田優先調度。

算法步驟設計如下:

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

(2)執行調度方案t時刻,t=t+1。

(3)判斷t=a?是則設置b值并繼續;否則轉步驟(2)。

(4)執行調度方案t時刻,t=t+1。

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

(6)生成應急農田序列,生成執行完當前任務時間點在(b,c)內的可應急調度的收獲機序列,并獲取位置,計算應急農田間及收獲機到應急農田的距離,按目標函數最優原則將應急農田分配到每輛可應急調度的收獲機,修正收獲機路線,更新調度方案t時刻。

(7)執行調度方案t時刻,t=t+1。

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

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

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

(11)繼續執行調度方案t時刻,t=t+1。

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

(13)結束。

3.3 運行結果

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

表4 仿真運行結果Tab.4 Instance run results

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

該次運行結果的各個收獲機的路徑如表5所示。應急農田的收獲機分配結果如表6所示。

表5 收獲機作業路徑Tab.5 Operation path of harvester

表6 應急農田收獲機分配結果Tab.6 Results of emergency farm harvester distribution

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

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

圖8 收獲機調度路徑圖Fig.8 Scheduling path of harvester

4 結束語

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