基于改進蟻群算法的聯合收割機調度路徑優化

龔瑞昆　吳天華

摘要：為緩解收割機在收獲季節供不應求的局面，實現聯合收割機在收割中的高效率、低成本和高收入。通過對影響收割機調度的多種因素進行分析，建立聯合收割機調度的數學模型。針對基本蟻群算法易陷入局部最優解、收斂速度慢等缺點，引入節約矩陣，并對不同搜索時段采用不同的信息揮發因子，最后通過局部搜索策略2-opt法搜索最優解的方法改進基本蟻群算法，對模型進行求解。仿真結果表明，改進后的蟻群算法性能優良，且可降低調度成本，能夠有效解決聯合收割機在農忙時節的使用問題。

關鍵詞：聯合收割機;改進蟻群算法;數學模型;調度

中圖分類號： S225.3? 文獻標志碼： A? 文章編號：1002-1302（2019）04-0197-04

我國是傳統的農業大國，農作物產量直接影響著我國國民經濟的發展，是國民經濟又好又快發展的重要保障。但隨著農作物產量的增大，一些在收割過程中遇到的問題容易暴露出來。根據調查，每年在收割季節，許多地區的聯合收割機供不應求，但還有一些地方的收割機出現閑置現象，無法達到收割的最高效率和最大利潤。事實上，收割機調度在農機調度領域的研究中一直處于空缺狀態。農忙時短，如果錯過了收割期，麥子就會炸裂，農戶損失糧食;農機手如果在這期間找不到活干，會損失掉一年中大半的收入。以往農戶與農機手的互動只能靠麥收期的電話聯系或者路上攔截，這種碰運氣式的聯絡往往會耽誤不少時間。而由此產生的中介往往從中謀利，不僅能增加農戶的成本，又會降低農機手的收入。因此，如何利用現有的計算機技術實現聯合收割機調度路徑優化，減小收割機的收割成本，提高農民的收入，成為許多農業企業研究的重大課題[1-3]。

本研究旨在從蟻群算法這一啟發式算法入手，針對其運算時間長、收斂速度慢等缺點，引入節約矩陣對其路徑選擇進行改進，并對不同搜索時段采用不同的信息揮發因子，最后通過局部搜索策略2-opt法對最優解進行搜索的方法對基本蟻群算法進行改進。構造聯合收割機調度成本最低化的目標函數，并將改進后的算法應用到目標函數中，實現收割機在調度過程中的路徑優化，提高收割機在每年收獲季節的利用率。

1 建立數學模型

1.1 聯合收割機調度原則

（1）準時性原則。由于農忙時短，如果錯過收獲期，農戶就會損失糧食，因此收割機調度系統的建立須要結合收割機位置、路線和運行速度等，以便調度中心及時進行處理，滿足系統的準時性原則。（2）路徑最短原則。聯合收割機調度系統意在協調地區之間收割機的資源配置問題，因此最佳路線的選擇至關重要，通過選擇最佳的調度路線，降低調度成本，提高聯合收割機工作效率，進而謀求最大的經濟效益[4-5]。（3）收割機使用最小化原則。收割機的啟用成本較高，當現有的收割機資源可以滿足收割需求時，應盡可能少地派收割機出去工作，以減少聯合收割機的調度成本。

1.2 模型假設

假設所有聯合收割機為同一類型，比如收割機都是收割小麥或都是收割玉米的;根據農戶種植信息確定農田位置和收割點;設有且僅有1個中心農機點，每條路線的開始和結束位置都在該中心農機點;各條路線均處于較理想狀況，不考慮天氣、地勢等特殊環境情況。

1.3 懲罰函數

聯合收割機到達時間偏離農戶約定時間的時間窗越大，懲罰的成本越高。本研究將懲罰成本設定為線性增長模式。因此，對懲罰成本作一些前提假設：收割機到達時間在時間窗內，則不會產生懲罰成本;當收割機到達時間偏離時間窗時，則進行如下懲罰。懲罰成本函數表達式為

式中：Hi（tir）表示收割機r在時間ti的懲罰成本;p表示早到懲罰系數;q表示晚到懲罰系數;tir表示收割機實際到達收割點i的時刻;ai為收割機最早到達收割點i的時刻;bi為收割機最晚到達收割點i的時刻。

1.4 變量和參數符號

在建立模型以前，須要對模型所用到的變量和參數符號進行定義和說明，設i為單個收割點的編號，N為收割點數量，i∈{1，2，…，N}，其中i=1代表中心農機點;r為派出去工作的收割機編號;R為收割機的總體數量，r∈{1，2，…，R};s為閑置的收割機編號，s∈{1，2，…，R};Cr為出去工作的收割機數量，Cs為閑置的收割機數量，Cr+Cs=R;eij為從收割點i到收割點j的單位距離成本;dij為從收割點i到收割點j的距離;er為單個收割機的啟用成本;es為收割機的月閑置成本;ts為閑置時間，表示收割機s從回到中心農機點到下次啟用的時間間隔;gi為根據以往數據分析收割點i在單位時間內大約能收割的量;Tir為收割機r在收割點i的工作時間;ti為收割機r準時到達收割點i的時刻;Kr為收割機r出去工作的收割任務指標。

1.5 數學模型

式（4）表示每臺收割機均從中心農機點出發最后回到中心農機點;式（5）表示從中心農機點派出去工作的收割機數量不超過停在中心農機點的收割機總數R臺;式（6）、（7）表示每個收割點只能被1臺收割機收割1次;式（8）表示每臺收割機從出去工作到最后回到中心農機點要完成自己的收割任務;式（9）表示時間窗約束;式（10）表示出去工作的收割機與閑置的收割機總和為R。

2 基于蟻群算法的路徑優化與改進

2.1 蟻群算法基本原理

2.2.2 對揮發因子的改進 ρ的大小直接影響蟻群算法的全局搜索能力和收斂速度。ρ一般取（0，1）上的一個常數，1-ρ 表示信息素殘留因子。當ρ越大時，路徑上的信息素量減少得越多，路徑決策的隨機性越高，更有助于找到全局最優解，但算法的收斂速度較慢;當ρ較小時，導致局部路徑上的信息素積累過多，雖然算法會快速收斂，但容易陷入局部最優解。針對這一情況，本研究對不同迭代時段采用不同的揮發因子。在搜索初期采用一個較大的揮發因子，這樣有利于進行全局搜索得到全局最優解;在迭代中期和末期逐漸選取較小的揮發因子，從之前全局搜索中得到的較優路徑中進行集中搜索，得到最終的較優路徑。揮發因子ρ采用的分段函數表達式為

2.2.3 局部搜索能力的改進 為避免算法陷入局部最優，增加解的多樣性，本研究采用2-opt法對算法進行局部優化[9-10]。為加快算法的收斂速度，只對每次迭代產生的最優路徑進行優化，路徑交換的規則為用（i，j）、（i+1，j+1）代替（i，i+1）、（j，j+1），同時翻轉交換后線路方向，線路變短，路徑得到優化。具體的交換方法如圖1所示。

2.3 改進蟻群算法的工作流程

改進后的蟻群算法流程如圖2所示。

3 仿真分析

某農機企業有8輛收割小麥的聯合收割機，企業根據當地小麥的收獲期和往年收獲數據分析得知，當地總共有15個種植小麥的農田。為了方便調度分析，本研究對數據和數據單位作出如下假設：（1）收割機在農田工作的時間按小時（h）來計算;（2）以平面坐標的橫、縱坐標來表示農田所在位置的經、緯度;（3）收割機的收割量以公頃（hm2）為單位;（4）i=1為調度中心（也就是中心農機點），i∈{2，3，…，16}為收割點的編號。

算例仿真試驗數據見表1。其中序號1表示中心農機點，序號2～16表示15個收割點，由于對最終返回中心農機點的時間不作要求，因此取1 000作為最晚回到中心農機點的時間。

本研究運用Matlab軟件分別對改進前后的算法進行仿真。初始參數設置為α=1，β=2，ε=2，Q=100，ρ的取值見式（17），螞蟻數量M=60，q0=0.03，最大迭代次數 Nmax=300。

通過對程序進行多次運行，得到基本蟻群算法的收斂曲線（圖3）和改進后蟻群算法的收斂曲線（圖4）。可以看出，基本蟻群算法在迭代大概140次的時候趨于穩定，而改進后的蟻群算法在迭代大概90次的時候就趨于穩定，提高了算法的收斂速度，并且得到的最優成本也更低。

為進一步驗證改進蟻群算法的優越性，本研究對2種算法程序分別運行10次，所得到改進前后蟻群算法的調度成本見表2。通過對2組解進行對比可以明顯看出，改進后的蟻群算法得到的解整體優于基本蟻群算法。取改進前、后蟻群算法所得的最小解Z前=373.638 2、Z后=353.529 3 進行分析，其收割機調度路線軌跡分別如圖5、圖6所示。

基本蟻群算法的最小成本調度路徑如表3所示。最優成本為373.638 2萬元，收割機行駛路程為131.875 7 km。

改進后蟻群算法的最小成本調度路徑如表4所示。最優成本為353.529 3萬元，收割機行駛路程為116.867 2 km。

通過對比可得，改進后的蟻群算法得到的最優成本為353.529 3萬元，比改進前減少了20萬元左右;改進前收割機行駛路程為131.875 7 km，改進后收割機行駛路程為 116.867 2 km，改進后的蟻群算法縮短了收割機的行駛路程，符合路徑最短的調度原則，說明改進后的蟻群算法可有效地解決收割機的調度問題。

4 結論

在對聯合收割機調度問題進行深入分析后，建立以調度成本最小為目標函數的數學模型，并通過引入節約矩陣、對不同搜索時段采用不同的信息揮發因子、2-opt法進行局部搜索的手段改進基本蟻群算法。改進后的蟻群算法與改進前相比具有較快的收斂速度，且得到的最優調度成本也更優，同時可避免算法陷入局部最優解。改進后的蟻群算法可快速生成調度成本較低的調度方案，說明本研究所建模型合理，改進算法有效，可有效解決聯合收割機調度問題。

參考文獻：

[1]段運紅. 農機調度將成“互聯網+”農業突破點[J]. 農業機械，2015（15）：64-65.

[2]石良華. 聯合收割機械在跨區作業中存在的幾個問題[J]. 科技創新與應用，2013（27）：296.

[3]馬梅瓊. 聯合收割機跨區作業調度研究[D]. 哈爾濱：東北農業大學，2017：1-6.

[4]范 青. 基于改進蟻群算法的物流配送路徑優化及應用研究[D]. 西安：西安建筑科技大學，2014：11-12.

[5]Baldacci R，Mingozzi A，Roberti R. Recent exact algorithms for solving the vehicle routing problem under capacity and time window constraints[J]. European Journal of Operational Research，2012，218（1）：1-6.

[6]段海濱. 蟻群算法原理及其應用[M]. 北京：科學出版社，2005：24-43.

[7]王曉東，張永強，薛 紅. 基于改進蟻群算法對VRP線路優化[J]. 吉林大學學報（信息科學版），2017，35（2）：198-203.

[8]孫 沁，歐邦才，丁曉銀，等. 基于改進蟻群算法的配送路徑優化問題研究——以南京蘇寧易購為例[J]. 物流工程與管理，2018，40（2）：77-82.

[9]潘挺雷. 基于改進蟻群算法的區域車輛配送路徑優化方法研究[D]. 杭州：浙江理工大學，2016：28.

[10]Englert M，Rglin H，Vcking B. Worst case and probabilistic analysis of the 2-opt algorithm for the TSP[J]. Algorithmica，2014，68：190-264.黎 虹，李 光. 高精度農業機械質心測量系統的設計與研究[J]. 江蘇農業科學，2019，47（4）：201-203.