基于改進蟻群算法的聯(lián)合收割機調(diào)度路徑優(yōu)化

龔瑞昆　吳天華

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

關(guān)鍵詞：聯(lián)合收割機;改進蟻群算法;數(shù)學(xué)模型;調(diào)度

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

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

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

1 建立數(shù)學(xué)模型

1.1 聯(lián)合收割機調(diào)度原則

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

1.2 模型假設(shè)

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

1.3 懲罰函數(shù)

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

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

1.4 變量和參數(shù)符號

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

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

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

2 基于蟻群算法的路徑優(yōu)化與改進

2.1 蟻群算法基本原理

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

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

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

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

3 仿真分析

某農(nóng)機企業(yè)有8輛收割小麥的聯(lián)合收割機，企業(yè)根據(jù)當?shù)匦←湹氖斋@期和往年收獲數(shù)據(jù)分析得知，當?shù)乜偣灿?5個種植小麥的農(nóng)田。為了方便調(diào)度分析，本研究對數(shù)據(jù)和數(shù)據(jù)單位作出如下假設(shè)：（1）收割機在農(nóng)田工作的時間按小時（h）來計算;（2）以平面坐標的橫、縱坐標來表示農(nóng)田所在位置的經(jīng)、緯度;（3）收割機的收割量以公頃（hm2）為單位;（4）i=1為調(diào)度中心（也就是中心農(nóng)機點），i∈{2，3，…，16}為收割點的編號。

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

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

通過對程序進行多次運行，得到基本蟻群算法的收斂曲線（圖3）和改進后蟻群算法的收斂曲線（圖4）?？梢钥闯觯鞠伻核惴ㄔ诘蟾?40次的時候趨于穩(wěn)定，而改進后的蟻群算法在迭代大概90次的時候就趨于穩(wěn)定，提高了算法的收斂速度，并且得到的最優(yōu)成本也更低。

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

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

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

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

4 結(jié)論

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

參考文獻：

[1]段運紅. 農(nóng)機調(diào)度將成“互聯(lián)網(wǎng)+”農(nóng)業(yè)突破點[J]. 農(nóng)業(yè)機械，2015（15）：64-65.

[2]石良華. 聯(lián)合收割機械在跨區(qū)作業(yè)中存在的幾個問題[J]. 科技創(chuàng)新與應(yīng)用，2013（27）：296.

[3]馬梅瓊. 聯(lián)合收割機跨區(qū)作業(yè)調(diào)度研究[D]. 哈爾濱：東北農(nóng)業(yè)大學(xué)，2017：1-6.

[4]范 青. 基于改進蟻群算法的物流配送路徑優(yōu)化及應(yīng)用研究[D]. 西安：西安建筑科技大學(xué)，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]段海濱. 蟻群算法原理及其應(yīng)用[M]. 北京：科學(xué)出版社，2005：24-43.

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

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

[9]潘挺雷. 基于改進蟻群算法的區(qū)域車輛配送路徑優(yōu)化方法研究[D]. 杭州：浙江理工大學(xué)，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.黎 虹，李 光. 高精度農(nóng)業(yè)機械質(zhì)心測量系統(tǒng)的設(shè)計與研究[J]. 江蘇農(nóng)業(yè)科學(xué)，2019，47（4）：201-203.