汪浩祥 曹光喬 閆子彤 陳 聰

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

0 引言

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

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

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

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

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

1 問(wèn)題描述與模型建立

1.1 問(wèn)題描述

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

minZ=(1-θ)Z1+θZ2

(1)

其中

(2)

(3)

式中M——收獲機(jī)場(chǎng)站個(gè)數(shù)

K——收獲機(jī)總臺(tái)數(shù)

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

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

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

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

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

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

ri——收獲機(jī)到達(dá)第i塊農(nóng)田的時(shí)間

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

θ——條件變量

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

(2)約束條件

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

(4)

(5)

(6)

(7)

(8)

(9)

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

(10)

(11)

(12)

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

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

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

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

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

2.1 兩級(jí)多段編碼方式

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

2.1.1一級(jí)編碼

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

圖2 一級(jí)編碼Fig.2 First level coding

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

2.1.2二級(jí)編碼

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

圖3 二級(jí)編碼Fig.3 Second level coding

2.1.3兩級(jí)編碼連接

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

圖4 兩級(jí)編碼連接Fig.4 Code linkage of two levels

2.2 遺傳操作設(shè)計(jì)

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

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

2.2.2選擇

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

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

(13)

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

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

(14)

2.2.3交叉

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

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

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

2.2.4變異

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

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

3 算法仿真

3.1 算例描述

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

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

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

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

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

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

收獲機(jī)場(chǎng)站個(gè)數(shù)M為3,車(chē)場(chǎng)K1、K2、K3擁有收獲機(jī)數(shù)量為3臺(tái)。

3.2 算法步驟

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

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

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

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

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

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

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

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

(7)執(zhí)行調(diào)度方案t時(shí)刻,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時(shí)刻,t=t+1。

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

(13)結(jié)束。

3.3 運(yùn)行結(jié)果

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

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

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

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

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

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

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

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

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

4 結(jié)束語(yǔ)

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