摘要：針對農(nóng)村土地流轉(zhuǎn)形成的大規(guī)模土地，提出基于輪盤的啟發(fā)式搜索（Heuristic search based on roulette，HSBOR）算法和基于最小值的啟發(fā)式搜索（Heuristic search based on minimum，HSBOM）算法，求解跨區(qū)域農(nóng)機調(diào)度問題；構(gòu)建農(nóng)機調(diào)度模型，設(shè)計HSBOR和HSBOM算法的核心思想，并通過模擬試驗比較HSBOR、HSBOM算法與基于優(yōu)先級規(guī)則的啟發(fā)式（Heuristic based on priority rules，HBOPR）算法在調(diào)度成本、運行效率上的優(yōu)劣。結(jié)果表明，HSBOM算法在調(diào)度成本和運行效率上最優(yōu)。

關(guān)鍵詞：跨區(qū)作業(yè)；啟發(fā)式搜索算法；農(nóng)機調(diào)度

中圖分類號：S232.3 文獻標識碼：A 文章編號：0439-8114（2016）16-4280-03

DOI：10.14088/j.cnki.issn0439-8114.2016.16.053

中國是傳統(tǒng)的農(nóng)業(yè)社會，在工業(yè)化、現(xiàn)代化轉(zhuǎn)型過程中產(chǎn)生了土地流轉(zhuǎn)問題，土地流轉(zhuǎn)使農(nóng)業(yè)經(jīng)營模式規(guī)模化、集約化、現(xiàn)代化。大規(guī)模土地生產(chǎn)，農(nóng)機跨區(qū)域作業(yè)問題有待解決。農(nóng)機調(diào)度問題是車輛路徑問題（Vehicle routing problem，VRP）[1-3]的進化，VRP問題中構(gòu)造的問題模型是一對多的，即在一定范圍內(nèi)，一個出發(fā)點對應(yīng)多個終點的問題。而農(nóng)機調(diào)度問題是多對多的NP-hard問題[4-7]，即農(nóng)機場個數(shù)與農(nóng)田作業(yè)點個數(shù)均為多個，農(nóng)機場有效為農(nóng)田分配農(nóng)機的問題。

針對多對多的農(nóng)機調(diào)度問題，本研究提出了HSBOR和HSBOM算法，并與基于優(yōu)先規(guī)則的啟發(fā)式農(nóng)機調(diào)度算法進行比較，3種算法都是在農(nóng)機充足的情況下為農(nóng)田分配農(nóng)機，HBOPR算法制定了農(nóng)田得到農(nóng)機的優(yōu)先級，而在實際應(yīng)用當中，農(nóng)田的重要程度是相近的。由此，HSBOR算法引入了農(nóng)田地位平等的思想，按照輪循的方式平等地為農(nóng)田分配農(nóng)機，保證每個農(nóng)田都能得到距離自己較近的農(nóng)機。HSBOM算法根據(jù)距離的遠近為農(nóng)田分配農(nóng)機，將所有距離數(shù)據(jù)存入數(shù)據(jù)庫，與農(nóng)田距離最小的農(nóng)機優(yōu)先分配，分配完成一次，數(shù)據(jù)庫更新，直到所有農(nóng)田得到所需的農(nóng)機數(shù)量。結(jié)果表明，HSBOR和HSBOM算法比HBOPR算法調(diào)度成本均有所降低，而運行效率上，HSBOR算法比HBOPR算法稍低，HSBOM算法與HBOPR算法效率相近，兩種算法具有可行性。

1 問題描述

本研究的農(nóng)機調(diào)度問題可描述為：在一定區(qū)域內(nèi)，存在兩個農(nóng)機點，3個農(nóng)田作業(yè)點。兩個農(nóng)機點的農(nóng)機可以為3個農(nóng)田按需分配，農(nóng)機點與農(nóng)田作業(yè)點的連線表示兩點之間的路徑，路徑上的標識表示兩點之間的距離。

如圖1所示，G=（V，D），V表示圖1中的頂點，有兩種類型，長方形Mi表示第i個農(nóng)機點，k表示農(nóng)機點的個數(shù)，其中1≤i≤k，k∈N；圓形Fj表示第j個農(nóng)田作業(yè)點，n表示農(nóng)田作業(yè)點的個數(shù)，其中，1≤j≤n，j∈N，Dij表示農(nóng)機點i與農(nóng)田作業(yè)點j之間存在路徑，權(quán)重表示兩點之間的距離，d表示單位時間內(nèi)農(nóng)機調(diào)度成本，包括農(nóng)機損耗、司機工資、耗油成本。

調(diào)度模型如下：

minR=d×■ （1）

式（1）表示農(nóng)機服務(wù)全部農(nóng)田所需的最小成本，是農(nóng)機調(diào)度問題的調(diào)度目標函數(shù)。

2 HSBOR和HSBOM算法設(shè)計

啟發(fā)式搜索算法是在狀態(tài)空間搜索算法的基礎(chǔ)上發(fā)展而來的，狀態(tài)空間搜索算法包括廣度優(yōu)先搜索算法和深度優(yōu)先搜索算法[8-11]。這兩種算法適合狀態(tài)空間小時使用，若狀態(tài)空間逐漸增大，狀態(tài)搜索算法將會出現(xiàn)嚴重偏差，且算法效率低。本研究對改進的HSBOR算法核心思想和HSBOM算法的關(guān)鍵步驟進行詳細闡述。

2.1 HSBOR算法核心思想

將農(nóng)田按照開始工作時間從早到晚排序，為今后研究在農(nóng)機不充足的情況下，農(nóng)機在農(nóng)田之間進行二次分配作鋪墊。排序好的農(nóng)田依次放在同一個輪盤中。假設(shè)排序好的農(nóng)田為F1，F(xiàn)2，F(xiàn)3，……，F(xiàn)n，在輪盤中顯示效果如圖2所示。

扇形的大小代表農(nóng)田面積，扇形面積越大，表示農(nóng)田面積越大。分配過程可描述為：從圖中“開始位置”處依次為每個農(nóng)田分配農(nóng)機，每次只為農(nóng)田分配一臺農(nóng)機，完成一次分配后，輪盤按照圖中箭頭所示，順時針旋轉(zhuǎn)一個扇形，直到為所有農(nóng)田分配完所需農(nóng)機數(shù)量，分配過程結(jié)束。

2.2 HSBOM算法關(guān)鍵步驟

HSBOM算法核心思想是根據(jù)農(nóng)機點到農(nóng)田作業(yè)點的距離，為農(nóng)田分配農(nóng)機，距離農(nóng)田作業(yè)點小的農(nóng)機優(yōu)先分配，保證分配的農(nóng)機距離農(nóng)田作業(yè)點盡可能小，減少調(diào)度過程中的調(diào)度成本，HSBOM算法的具體流程如下：

Step 1：初始化二維數(shù)組result[][]，存儲分配結(jié)果，整數(shù)變量i=0，控制循環(huán)語句；

Step 2：將農(nóng)機點到農(nóng)田作業(yè)點距離按照從小到大的順序排序，存儲在sort[]中，保留農(nóng)機編號與農(nóng)場編號的對應(yīng)關(guān)系；

Step 3：得到sort[]中最小距離所在農(nóng)田位置indexF；

Step 4：if i

Step 5：if農(nóng)機點分配后剩余車輛>0，農(nóng)田至少所需車輛>0，轉(zhuǎn)向Step 6，否則，轉(zhuǎn)向Step 4；

Step 6：if indexF=農(nóng)田編號，為農(nóng)田分配車輛，存儲在result[][]中，農(nóng)機點分配后剩余車輛，農(nóng)田至少所需車輛，轉(zhuǎn)向Step 4，否則，提示分配有誤，終止程序；

Step 7：分配過程結(jié)束。

3 仿真試驗結(jié)果

5個農(nóng)機點M1～M5，農(nóng)田作業(yè)點3～7個。在農(nóng)機數(shù)量確定，農(nóng)田作業(yè)點數(shù)量變化時，分別使用HSBOR、HSBOM、HBOPR算法計算農(nóng)機調(diào)度成本和算法運行效率，其中HBOPR是待比較算法。

3.1 調(diào)度成本測評

以兩種形式對農(nóng)機調(diào)度成本進行測評，一是宏觀上對比3種算法的調(diào)度成本，直觀得到3種算法調(diào)度成本的大?。欢俏⒂^上對比HSBOR、HSBOM算法較待比較算法HBOPR的提高率。綜合宏觀、微觀兩方面，得到3種算法在調(diào)度成本上的優(yōu)劣。

3.1.1 宏觀對比 根據(jù)仿真試驗數(shù)據(jù)，使用HSBOR、HSBOM、HBOPR算法得出農(nóng)機調(diào)度成本，試驗結(jié)果如圖3所示。通過圖3可以看出，隨著農(nóng)田數(shù)量的增加，HBOPR算法調(diào)度成本高于HSBOR、HSBOM算法，HSBOM調(diào)度成本最低。結(jié)果表明，當農(nóng)田任務(wù)點數(shù)量變化，農(nóng)機數(shù)量總數(shù)確定時，HSBOR、HSBOM比HBOPR調(diào)度成本低，且HSBOM算法在調(diào)度成本方面最優(yōu)。

3.1.2 微觀對比 調(diào)度成本微觀對比過程：首先分別使用HSBOR、HSBOM、HBOPR算法得到農(nóng)機調(diào)度成本，然后將HSBOR、HSBOM算法得到的調(diào)度成本與HBOPR算法得到的調(diào)度成本進行對比，計算HSBOR、HSBOM算法較HBOPR算法的平均提高率，試驗結(jié)果如表1所示。由表1可以看出，HSBOR比HBOPR費用平均降低了266.46元，HSBOR比HBOPR平均提高了10.75%；HSBOM比HBOPR成本平均降低379.8元，HSBOM比HBOPR平均提高了15.51%。結(jié)果表明，HSBOM算法提高率比HSBOR算法提高率大，HSBOM算法在調(diào)度成本方面最優(yōu)。

3.2 運行效率測評

在農(nóng)田數(shù)量相同，農(nóng)機數(shù)量不變時，比較3種算法HSBOR、HSBOM、HBOPR的運行時間。運行時間越短，算法的運行效率越高，反之，算法運行效率越低。根據(jù)仿真試驗數(shù)據(jù)，分別使用HSBOR、HSBOM、HBOPR3種算法得出運行時間并比較，試驗結(jié)果如圖4所示。

通過圖4可以看出，HSBOR算法比HBOPR、HSBOM算法運行時間高；HSBOM與HBOPR運行時間接近相等。綜合圖3和圖4，HSBOM在調(diào)度成本和運行效率上最優(yōu)。

4 小結(jié)

本研究為農(nóng)機調(diào)度問題提出了兩種改進的啟發(fā)式搜索算法，兩種算法基于不同的核心思想：基于農(nóng)田地位平等的輪循式算法和基于最小值的搜索算法。在農(nóng)機調(diào)度成本方面，兩種算法均取得滿意結(jié)果；但在運行效率方面，HSBOR算法比HBOPR算法運行時間長。兩種算法均是在農(nóng)機充足的條件下產(chǎn)生的，有一定的局限性，HSBOR算法在運行效率方面有待進一步提高，仍需加以改善。

參考文獻：

[1] 潘立軍.帶時間窗車輛路徑問題及其算法研究[D].長沙：中南大學，2012.

[2] 徐 濱，張 亦.改進的螞蟻算法車輛運行調(diào)度算法研究[J].計算機仿真，2011，28（10）：366-369.

[3] 呂雄偉，趙 達，李 軍.基于多態(tài)蟻群算法的多目標郵政物流車輛路徑問題研究[J].計算機應(yīng)用研究，2009，26（6）：2070-2073.

[4] 王訓(xùn)斌，陸慧娟，陳五濤.帶時間窗動態(tài)車輛路徑問題的改進蟻群算法[J].工業(yè)控制計算機，2009，22（1）：41-43.

[5] 葛顯龍.面向云配送模式的車輛調(diào)度問題及算法研究[D].重慶：重慶大學，2011.

[6] 吳 萍.基于遺傳算法的智能公交調(diào)度研究[D].西安：西安電子科技大學，2012.

[7] 周 蕾.基于動態(tài)信息的應(yīng)急疏散與車輛調(diào)度研究[D].杭州：浙江大學，2012.

[8] 符 娟，鐘 忺，張 偉，等.通用啟發(fā)式搜索算法庫的設(shè)計[J].科技信息，2006（7）：23-24.

[9] 王 華.基于二叉樹的啟發(fā)式搜索算法改進[J].測繪工程，2014， 23（6）：31-32.

[10] 謝 琳.局部滿意的啟發(fā)式搜索算法[J].微電子學與計算機，2011，28（10）：194-200.

[11] 林 捷.基于粒度計算的啟發(fā)式搜索算法研究[J].赤峰學院學報（自然科學版），2013（14）：21-22.