龔瑞昆　吳天華

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

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

中圖分類號(hào)： S225.3? 文獻(xiàn)標(biāo)志碼： A? 文章編號(hào)：1002-1302（2019）04-0197-04

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

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

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

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

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

1.2 模型假設(shè)

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

1.3 懲罰函數(shù)

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

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

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

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

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

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

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

2.1 蟻群算法基本原理

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

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

2.3 改進(jìn)蟻群算法的工作流程

改進(jìn)后的蟻群算法流程如圖2所示。

3 仿真分析

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

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

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

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

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

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

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

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

4 結(jié)論

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

參考文獻(xiàn)：

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

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

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

[4]范 青. 基于改進(jìn)蟻群算法的物流配送路徑優(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]王曉東，張永強(qiáng)，薛 紅. 基于改進(jìn)蟻群算法對(duì)VRP線路優(yōu)化[J]. 吉林大學(xué)學(xué)報(bào)（信息科學(xué)版），2017，35（2）：198-203.

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

[9]潘挺雷. 基于改進(jìn)蟻群算法的區(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è)機(jī)械質(zhì)心測(cè)量系統(tǒng)的設(shè)計(jì)與研究[J]. 江蘇農(nóng)業(yè)科學(xué)，2019，47（4）：201-203.