帶時間窗農(nóng)機調(diào)度問題的改進遺傳算法

呂云杰，郭 輝，魯 東

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

0 引言

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

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

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

1.1 問題描述

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

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

1.2.1 變量說明

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

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

1.2.2 目標函數(shù)

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

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

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

農(nóng)機運輸成本：

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

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

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

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

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

1.2.3 約束條件

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

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

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

1.2.4 多目標處理

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

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

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

2.1 染色體編碼

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

2.2 遺傳操作設(shè)計

（1）選擇算子

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

（2）交叉算子

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

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

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

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

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

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

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

3.1 案例計算

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

表1 農(nóng)機庫信息

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

表2 農(nóng)機信息

表3 農(nóng)田信息

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

3.2 結(jié)果分析

針對本案例農(nóng)機調(diào)度問題，應(yīng)用Matlab 對本文算法和文獻算法進行編程仿真比較。并對遺傳算法的參數(shù)設(shè)置如下：種群規(guī)模N=60，最大遺傳迭代次數(shù)Gen=200，并且經(jīng)過多次試驗結(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 是使用本文算法計算的一次運行結(jié)果顯示，M1號農(nóng)機庫各農(nóng)機最優(yōu)路線分別是：1 號農(nóng)機6-5-7，2號農(nóng)機4-2；3 號10；M2號農(nóng)機庫各農(nóng)機最優(yōu)路線分別是：1 號農(nóng)機1-3，2 號農(nóng)機8-9，3 號農(nóng)機11，本次調(diào)度的最優(yōu)值是164.7 元，最少配出的農(nóng)機數(shù)量是6 臺，對應(yīng)的最優(yōu)染色體為：

3.3 算法有效性分析

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

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

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

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

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

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

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

4 結(jié)論

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