帶時(shí)間窗農(nóng)機(jī)調(diào)度問(wèn)題的改進(jìn)遺傳算法

呂云杰，郭 輝，魯 東

（新疆農(nóng)業(yè)大學(xué)，新疆 烏魯木齊830000）

0 引言

農(nóng)機(jī)調(diào)度問(wèn)題實(shí)質(zhì)上是一類多因素控制的車輛調(diào)度問(wèn)題，屬于多目標(biāo)組合優(yōu)化問(wèn)題。本文針對(duì)農(nóng)業(yè)合作社服務(wù)范圍內(nèi)的農(nóng)田作業(yè)時(shí)間、作業(yè)地點(diǎn)等因素，以農(nóng)機(jī)和農(nóng)田作業(yè)點(diǎn)之間的組合優(yōu)化問(wèn)題展開研究。

目前，國(guó)內(nèi)外建立了比較完善的農(nóng)機(jī)社會(huì)服務(wù)體系。VanElderen 提出在農(nóng)業(yè)生產(chǎn)領(lǐng)域有純粹調(diào)度和連續(xù)調(diào)度兩類基本的調(diào)度問(wèn)題[1]。Bochtis 和Sorensen[2-4]為農(nóng)業(yè)領(lǐng)域的VRP 問(wèn)題提出了專用的操作方法來(lái)解決田間作業(yè)的規(guī)劃和調(diào)度問(wèn)題。在國(guó)內(nèi)，如王增建立了在時(shí)間窗限制條件下的資源損失最小化和時(shí)間方差最小化的多目標(biāo)應(yīng)急物資調(diào)度模型[6]。王雪陽(yáng)采用單個(gè)染色體指定位置交叉變換來(lái)降低不可行解的數(shù)量的方法求農(nóng)機(jī)轉(zhuǎn)移成本最低[8]。王玉巍采用自然數(shù)編碼、染色體隨機(jī)交叉的方式進(jìn)行農(nóng)機(jī)調(diào)度問(wèn)題優(yōu)化[9]。上述文獻(xiàn)主要研究的是一個(gè)農(nóng)機(jī)服務(wù)組織為多個(gè)農(nóng)田服務(wù)的農(nóng)機(jī)調(diào)度問(wèn)題，沒(méi)有綜合考慮帶時(shí)間窗農(nóng)機(jī)調(diào)度問(wèn)題的影響因素，本文在詳細(xì)思考以上文獻(xiàn)的基礎(chǔ)上更加全面的考慮了農(nóng)機(jī)調(diào)度問(wèn)題影響因素。

1 問(wèn)題描述與數(shù)學(xué)模型

1.1 問(wèn)題描述

本文研究的農(nóng)機(jī)調(diào)度問(wèn)題可描述為：某農(nóng)機(jī)服務(wù)組織在一定的服務(wù)范圍內(nèi)擁有多個(gè)不同位置的農(nóng)機(jī)庫(kù)，每個(gè)農(nóng)機(jī)庫(kù)擁有多種不同型號(hào)的農(nóng)機(jī)，需要給分布在不同位置的農(nóng)田提供農(nóng)機(jī)作業(yè)服務(wù)，每臺(tái)農(nóng)機(jī)按照調(diào)配路線逐次作業(yè)，對(duì)于同一個(gè)農(nóng)田作業(yè)點(diǎn)，該農(nóng)機(jī)只能到達(dá)一次。每個(gè)農(nóng)田的位置、面積、作業(yè)時(shí)間窗以及所需農(nóng)機(jī)型號(hào)均已知。

1.2 數(shù)學(xué)模型的構(gòu)建

1.2.1 變量說(shuō)明

針對(duì)構(gòu)建的農(nóng)機(jī)調(diào)度數(shù)學(xué)模型，為了方便描述，對(duì)模型中相關(guān)變量做如下說(shuō)明：

k，m，j 分別表示農(nóng)機(jī)編號(hào)、農(nóng)機(jī)庫(kù)編號(hào)和農(nóng)田編號(hào)；Aj—農(nóng)田j的面積，j=1，2，···n；—農(nóng)機(jī)作業(yè)時(shí)的單位面積作業(yè)成本；—農(nóng)機(jī)轉(zhuǎn)移時(shí)的單位時(shí)間消耗成本—農(nóng)機(jī)等待時(shí)的單位時(shí)間等待成本—在編號(hào)為m的農(nóng)機(jī)庫(kù)中，編號(hào)為k的農(nóng)機(jī)從農(nóng)田i到農(nóng)田j所用的轉(zhuǎn)移時(shí)間，其中i≠j，且i=0，1，2···n；j=0，1，2···n；—m農(nóng)機(jī)庫(kù)中的k農(nóng)機(jī)從農(nóng)田i轉(zhuǎn)移到達(dá)農(nóng)田j時(shí)的時(shí)間節(jié)點(diǎn)；[bj，ej]—農(nóng)田j的作業(yè)時(shí)間窗，bj代表農(nóng)田j允許作業(yè)的開始時(shí)間，ej代表農(nóng)田j允許作業(yè)的最晚完成時(shí)間—農(nóng)機(jī)k在農(nóng)田j作業(yè)的完成時(shí)間—農(nóng)機(jī)k完成農(nóng)田j任務(wù)的作業(yè)時(shí)長(zhǎng)。

1.2.2 目標(biāo)函數(shù)

本文以調(diào)度總成本低、準(zhǔn)時(shí)性高和農(nóng)機(jī)調(diào)度數(shù)量少為農(nóng)機(jī)調(diào)度目標(biāo)，構(gòu)建多目標(biāo)組合優(yōu)化問(wèn)題的農(nóng)機(jī)調(diào)度模型，其步驟如下：

（1）農(nóng)機(jī)調(diào)度成本

農(nóng)機(jī)作業(yè)成本：

農(nóng)機(jī)運(yùn)輸成本：

農(nóng)機(jī)等待成本：

其中，i=0，1···n，j=0，1···n。

農(nóng)機(jī)調(diào)度總成本：

（2）農(nóng)機(jī)調(diào)度總數(shù)

農(nóng)機(jī)調(diào)度總數(shù)是指在一次農(nóng)機(jī)調(diào)度過(guò)程中，各農(nóng)機(jī)庫(kù)派出的所有農(nóng)機(jī)的數(shù)量，其函數(shù)表達(dá)式如下：

1.2.3 約束條件

（1）在一次農(nóng)機(jī)調(diào)度過(guò)程中，每個(gè)農(nóng)田作業(yè)點(diǎn)j有且僅有一臺(tái)農(nóng)機(jī)為其服務(wù)；

（2）在農(nóng)機(jī)調(diào)度路線上，相鄰兩個(gè)農(nóng)田作業(yè)點(diǎn)的時(shí)間約束關(guān)系，考慮了在前一個(gè)農(nóng)田作業(yè)點(diǎn)準(zhǔn)時(shí)完成作業(yè)的情況下，仍能保證下一個(gè)農(nóng)田作業(yè)點(diǎn)能夠準(zhǔn)時(shí)作業(yè)；

（3）在一次農(nóng)機(jī)調(diào)度過(guò)程中，農(nóng)機(jī)k在農(nóng)田作業(yè)點(diǎn)i完成作業(yè)服務(wù)后到達(dá)農(nóng)田作業(yè)點(diǎn)j的時(shí)間是否小于農(nóng)田作業(yè)點(diǎn)j允許作業(yè)的開始時(shí)間，若是，則wij=1，否則為0。

1.2.4 多目標(biāo)處理

本文以調(diào)度成本最低且配發(fā)農(nóng)機(jī)數(shù)量最少為調(diào)度目標(biāo)，為了使求解步驟簡(jiǎn)化同時(shí)方便在解集空間上搜索，故采用極差值法將兩個(gè)目標(biāo)函數(shù)進(jìn)行優(yōu)化組合，得到如下綜合目標(biāo)函數(shù)：

其中，minX表示農(nóng)機(jī)調(diào)度過(guò)程中總成本最低且配發(fā)的農(nóng)機(jī)數(shù)量最少。

2 自適應(yīng)遺傳算法設(shè)計(jì)

2.1 染色體編碼

本文基于農(nóng)田進(jìn)行染色體整數(shù)編碼，該編碼方式能夠清楚的表示農(nóng)機(jī)來(lái)自哪個(gè)農(nóng)機(jī)庫(kù)、農(nóng)機(jī)編號(hào)和作業(yè)路線。染色體編碼設(shè)計(jì)為R=（m1，m2···mi），每個(gè)基因mi包含了三個(gè)參數(shù)：農(nóng)機(jī)庫(kù)編號(hào)M、農(nóng)機(jī)編號(hào)K 和農(nóng)機(jī)出行路線，基因序列mi表達(dá)的關(guān)系是編號(hào)為i 的農(nóng)田由編號(hào)為M 的農(nóng)機(jī)庫(kù)配發(fā)編號(hào)為K 的農(nóng)機(jī)對(duì)其作業(yè)。初始種群的初始解編碼是在一定范圍內(nèi)隨機(jī)產(chǎn)生的，即M∈[1，2，3···m]，K∈[1，2，3···k]。

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

（1）選擇算子

本文中選擇算子采用輪盤賭選擇法實(shí)現(xiàn)，根據(jù)每個(gè)個(gè)體的適值進(jìn)行擇優(yōu)，并采用最優(yōu)保存策略，將適應(yīng)值最大的染色體直接復(fù)制給下一代，以保證將優(yōu)良基因不丟失，從而使得結(jié)果能收斂為全局最優(yōu)。對(duì)于種群大小為m，適值為fi（x）的第i個(gè)個(gè)體被選擇的概率如下公式：

（2）交叉算子

為避免過(guò)多的基因交換，經(jīng)過(guò)綜合考慮求解問(wèn)題和染色體編碼方式，設(shè)計(jì)如下交叉方式：

設(shè)定初始種群規(guī)模后，任意取兩條染色體p、q 作為父代，并隨機(jī)生成兩串長(zhǎng)度等于每組路徑上的農(nóng)機(jī)數(shù)的二進(jìn)制數(shù)并作為兩組路徑的掩碼T1、T2，將掩碼的各位與路徑一一對(duì)應(yīng)，其中“1”所對(duì)應(yīng)的路徑直接復(fù)制給下一代，而“0”對(duì)應(yīng)的路徑，找到另一個(gè)染色體子代路徑中與服務(wù)該農(nóng)田相同的農(nóng)機(jī)庫(kù)編號(hào)和農(nóng)機(jī)編號(hào)，則將該農(nóng)田插入到子代的這條路徑中，如果另一個(gè)染色體子代中沒(méi)有與服務(wù)該農(nóng)田相同的農(nóng)機(jī)庫(kù)和農(nóng)機(jī)編號(hào)，則該染色體在子代中繼續(xù)保留服務(wù)該農(nóng)田的農(nóng)機(jī)庫(kù)和農(nóng)機(jī)的對(duì)應(yīng)信息。

（3）自適應(yīng)遺傳算子改進(jìn)設(shè)計(jì)

本文采用了由種群進(jìn)化狀況來(lái)確定交叉概率pc和變異pm的自適應(yīng)方法，對(duì)于適應(yīng)度高于種群平均適應(yīng)度的個(gè)體，選擇較小的pc和pm，從而保護(hù)優(yōu)良個(gè)體，對(duì)于適應(yīng)度低于群體平均適應(yīng)度的個(gè)體選擇較大pc和pm，從而擴(kuò)大優(yōu)秀個(gè)體生成。自適應(yīng)算子的設(shè)計(jì)如下：

式中pc-max—最大交叉概率；pc-min—最小交叉概率；f'—交叉操作中較大個(gè)體的適應(yīng)度值；fitavg—當(dāng)前迭代過(guò)程中全部染色體適應(yīng)度的平均值，x1—0～1 之間的常數(shù)。

式中pm-max—最大變異概率；pm-min—最小變異概率；f—變異個(gè)體的適應(yīng)度值；fitavg—當(dāng)前迭代過(guò)程中全部染色體適應(yīng)度的平均值，x2—0～1 之間的常數(shù)。

3 仿真案例與結(jié)果分析

3.1 案例計(jì)算

本文研究對(duì)象是面向訂單的多農(nóng)機(jī)點(diǎn)服務(wù)多農(nóng)田的農(nóng)機(jī)調(diào)度問(wèn)題，為了驗(yàn)證本文算法的有效性，采集新疆沙灣縣宏基農(nóng)機(jī)服務(wù)專業(yè)合作社的實(shí)際數(shù)據(jù)，選取合作社中兩個(gè)農(nóng)機(jī)庫(kù)進(jìn)行實(shí)例計(jì)算，并根據(jù)沙灣縣農(nóng)田、農(nóng)機(jī)信息擁有量統(tǒng)計(jì)年鑒[10-11]和GPS 定位得到表1～表4 的數(shù)據(jù)。

表1 農(nóng)機(jī)庫(kù)信息

該合作社主要以面向訂單的農(nóng)機(jī)調(diào)度模式對(duì)表3 中11 個(gè)鄉(xiāng)鎮(zhèn)進(jìn)行農(nóng)田作業(yè)服務(wù)，現(xiàn)將沙灣縣的11 個(gè)鄉(xiāng)鎮(zhèn)抽象為11 個(gè)需要農(nóng)機(jī)服務(wù)的農(nóng)田訂單，其農(nóng)田位置、作業(yè)面積和作業(yè)時(shí)間窗信息以及農(nóng)田間距離如表4 和表5。假設(shè)農(nóng)機(jī)調(diào)路程全為直線距離，各種型號(hào)農(nóng)機(jī)運(yùn)行速度如表3，現(xiàn)求農(nóng)機(jī)調(diào)度成本最低且所配發(fā)的農(nóng)機(jī)數(shù)量最少。

表2 農(nóng)機(jī)信息

表3 農(nóng)田信息

表4 各區(qū)域間的距離

3.2 結(jié)果分析

針對(duì)本案例農(nóng)機(jī)調(diào)度問(wèn)題，應(yīng)用Matlab 對(duì)本文算法和文獻(xiàn)算法進(jìn)行編程仿真比較。并對(duì)遺傳算法的參數(shù)設(shè)置如下：種群規(guī)模N=60，最大遺傳迭代次數(shù)Gen=200，并且經(jīng)過(guò)多次試驗(yàn)結(jié)果分析，其他參數(shù)取值為：x1=0.6，=0.8，最大和最小交叉概率分別為pc-max=0.9，pc-min=0.4，最大和最小變異概率為pm-max=0.1，pm-min=0.01。編程得到仿真結(jié)果（圖1）。

圖1 是使用本文算法計(jì)算的一次運(yùn)行結(jié)果顯示，M1號(hào)農(nóng)機(jī)庫(kù)各農(nóng)機(jī)最優(yōu)路線分別是：1 號(hào)農(nóng)機(jī)6-5-7，2號(hào)農(nóng)機(jī)4-2；3 號(hào)10；M2號(hào)農(nóng)機(jī)庫(kù)各農(nóng)機(jī)最優(yōu)路線分別是：1 號(hào)農(nóng)機(jī)1-3，2 號(hào)農(nóng)機(jī)8-9，3 號(hào)農(nóng)機(jī)11，本次調(diào)度的最優(yōu)值是164.7 元，最少配出的農(nóng)機(jī)數(shù)量是6 臺(tái)，對(duì)應(yīng)的最優(yōu)染色體為：

3.3 算法有效性分析

算法有效性分析過(guò)程：分別使用本文算法和文獻(xiàn)9 中的算法計(jì)算綜合目標(biāo)函數(shù)值，若值越小，則算法性能越好；若值越大，則算法性能越差，圖1 為目標(biāo)函數(shù)值隨遺傳代數(shù)的變化。

圖1 目標(biāo)函數(shù)值隨遺傳代數(shù)的變化

從模擬實(shí)驗(yàn)得出的結(jié)果可以看到，本文改進(jìn)后的算法與文獻(xiàn)[9]中的算法相比較，能夠得到更優(yōu)的目標(biāo)函數(shù)，并且能夠更早的收斂于最優(yōu)解，從圖中可以直觀的看到，當(dāng)遺傳算法的迭代次數(shù)設(shè)置為200，種群規(guī)模為80，遺傳算法在迭代次數(shù)為0-22 和65-200 之間時(shí)，本文提出的改進(jìn)遺傳算法的調(diào)度成本和所需配發(fā)農(nóng)機(jī)數(shù)量明顯小于文獻(xiàn)，能夠得到更好的農(nóng)機(jī)調(diào)度方案，能夠更快地收斂于最優(yōu)解，從而驗(yàn)證了本文改進(jìn)后算法的可行性和有效性。

3.4 農(nóng)田數(shù)量對(duì)算法性能的影響

當(dāng)農(nóng)機(jī)數(shù)量確定，農(nóng)田數(shù)量由5 增加到11 時(shí)，分別應(yīng)用本文算法和文獻(xiàn)中算法計(jì)算農(nóng)機(jī)調(diào)度成本，實(shí)驗(yàn)結(jié)果如表5 所示。

分析表5 可以看出，隨著農(nóng)田數(shù)量的增加，本文算法相比文獻(xiàn)算法，調(diào)度成本降低更快，平均費(fèi)用也有所降低，本文算法比文獻(xiàn)算法平均提高了6.0%，實(shí)驗(yàn)結(jié)果表明：當(dāng)農(nóng)田維數(shù)變化，農(nóng)機(jī)數(shù)量確定時(shí)，本文算法比文獻(xiàn)算法性能好。

表5 農(nóng)田數(shù)量變化測(cè)試結(jié)果

4 結(jié)論

針對(duì)帶時(shí)間窗的多農(nóng)機(jī)點(diǎn)服務(wù)多農(nóng)田的農(nóng)機(jī)調(diào)度問(wèn)題，首先構(gòu)建了農(nóng)機(jī)調(diào)度數(shù)學(xué)函數(shù)模型，然后設(shè)計(jì)了符合農(nóng)田作業(yè)收割時(shí)間窗的染色體編碼方式和改進(jìn)的自適應(yīng)遺傳算法，并利用沙灣縣宏基農(nóng)機(jī)服務(wù)專業(yè)合作社的實(shí)際農(nóng)機(jī)數(shù)據(jù)情況進(jìn)行了模擬實(shí)驗(yàn)，比較了本文算法和文獻(xiàn)中算法的穩(wěn)定性，驗(yàn)證了本文算法的有效性和可行性。最后在農(nóng)田數(shù)量變化農(nóng)機(jī)數(shù)量確定和農(nóng)田數(shù)量確定農(nóng)機(jī)數(shù)量變化的兩種條件下，比較了兩種算法的性能，實(shí)驗(yàn)結(jié)果顯示本文算法性能優(yōu)于文獻(xiàn)中算法。