改進的啟發式搜索算法求解農機調度問題

摘要：針對農村土地流轉形成的大規模土地，提出基于輪盤的啟發式搜索（Heuristic search based on roulette，HSBOR）算法和基于最小值的啟發式搜索（Heuristic search based on minimum，HSBOM）算法，求解跨區域農機調度問題；構建農機調度模型，設計HSBOR和HSBOM算法的核心思想，并通過模擬試驗比較HSBOR、HSBOM算法與基于優先級規則的啟發式（Heuristic based on priority rules，HBOPR）算法在調度成本、運行效率上的優劣。結果表明，HSBOM算法在調度成本和運行效率上最優。

關鍵詞：跨區作業；啟發式搜索算法；農機調度

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

DOI：10.14088/j.cnki.issn0439-8114.2016.16.053

中國是傳統的農業社會，在工業化、現代化轉型過程中產生了土地流轉問題，土地流轉使農業經營模式規模化、集約化、現代化。大規模土地生產，農機跨區域作業問題有待解決。農機調度問題是車輛路徑問題（Vehicle routing problem，VRP）[1-3]的進化，VRP問題中構造的問題模型是一對多的，即在一定范圍內，一個出發點對應多個終點的問題。而農機調度問題是多對多的NP-hard問題[4-7]，即農機場個數與農田作業點個數均為多個，農機場有效為農田分配農機的問題。

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

1 問題描述

本研究的農機調度問題可描述為：在一定區域內，存在兩個農機點，3個農田作業點。兩個農機點的農機可以為3個農田按需分配，農機點與農田作業點的連線表示兩點之間的路徑，路徑上的標識表示兩點之間的距離。

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

調度模型如下：

minR=d×■ （1）

式（1）表示農機服務全部農田所需的最小成本，是農機調度問題的調度目標函數。

2 HSBOR和HSBOM算法設計

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

2.1 HSBOR算法核心思想

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

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

2.2 HSBOM算法關鍵步驟

HSBOM算法核心思想是根據農機點到農田作業點的距離，為農田分配農機，距離農田作業點小的農機優先分配，保證分配的農機距離農田作業點盡可能小，減少調度過程中的調度成本，HSBOM算法的具體流程如下：

Step 1：初始化二維數組result[][]，存儲分配結果，整數變量i=0，控制循環語句；

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

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

Step 4：if i

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

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

Step 7：分配過程結束。

3 仿真試驗結果

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

3.1 調度成本測評

以兩種形式對農機調度成本進行測評，一是宏觀上對比3種算法的調度成本，直觀得到3種算法調度成本的大小；二是微觀上對比HSBOR、HSBOM算法較待比較算法HBOPR的提高率。綜合宏觀、微觀兩方面，得到3種算法在調度成本上的優劣。

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

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

3.2 運行效率測評

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

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

4 小結

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

參考文獻：

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

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

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

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

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

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

[7] 周 蕾.基于動態信息的應急疏散與車輛調度研究[D].杭州：浙江大學，2012.

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

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

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

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