帶時間窗農機調度問題的改進遺傳算法

呂云杰，郭 輝，魯 東

（新疆農業大學，新疆 烏魯木齊830000）

0 引言

農機調度問題實質上是一類多因素控制的車輛調度問題，屬于多目標組合優化問題。本文針對農業合作社服務范圍內的農田作業時間、作業地點等因素，以農機和農田作業點之間的組合優化問題展開研究。

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

1 問題描述與數學模型

1.1 問題描述

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

1.2 數學模型的構建

1.2.1 變量說明

針對構建的農機調度數學模型，為了方便描述，對模型中相關變量做如下說明：

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

1.2.2 目標函數

本文以調度總成本低、準時性高和農機調度數量少為農機調度目標，構建多目標組合優化問題的農機調度模型，其步驟如下：

（1）農機調度成本

農機作業成本：

農機運輸成本：

農機等待成本：

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

農機調度總成本：

（2）農機調度總數

農機調度總數是指在一次農機調度過程中，各農機庫派出的所有農機的數量，其函數表達式如下：

1.2.3 約束條件

（1）在一次農機調度過程中，每個農田作業點j有且僅有一臺農機為其服務；

（2）在農機調度路線上，相鄰兩個農田作業點的時間約束關系，考慮了在前一個農田作業點準時完成作業的情況下，仍能保證下一個農田作業點能夠準時作業；

（3）在一次農機調度過程中，農機k在農田作業點i完成作業服務后到達農田作業點j的時間是否小于農田作業點j允許作業的開始時間，若是，則wij=1，否則為0。

1.2.4 多目標處理

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

其中，minX表示農機調度過程中總成本最低且配發的農機數量最少。

2 自適應遺傳算法設計

2.1 染色體編碼

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

2.2 遺傳操作設計

（1）選擇算子

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

（2）交叉算子

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

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

（3）自適應遺傳算子改進設計

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

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

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

3 仿真案例與結果分析

3.1 案例計算

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

表1 農機庫信息

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

表2 農機信息

表3 農田信息

表4 各區域間的距離

3.2 結果分析

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

圖1 是使用本文算法計算的一次運行結果顯示，M1號農機庫各農機最優路線分別是：1 號農機6-5-7，2號農機4-2；3 號10；M2號農機庫各農機最優路線分別是：1 號農機1-3，2 號農機8-9，3 號農機11，本次調度的最優值是164.7 元，最少配出的農機數量是6 臺，對應的最優染色體為：

3.3 算法有效性分析

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

圖1 目標函數值隨遺傳代數的變化

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

3.4 農田數量對算法性能的影響

當農機數量確定，農田數量由5 增加到11 時，分別應用本文算法和文獻中算法計算農機調度成本，實驗結果如表5 所示。

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

表5 農田數量變化測試結果

4 結論

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