改進(jìn)的啟發(fā)式搜索算法求解農(nóng)機(jī)調(diào)度問題

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

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

中圖分類號(hào)：S232.3 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：0439-8114（2016）16-4280-03

DOI：10.14088/j.cnki.issn0439-8114.2016.16.053

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

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

1 問題描述

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

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

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

minR=d×■ （1）

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

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

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

2.1 HSBOR算法核心思想

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

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

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

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

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

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

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

Step 4：if i

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

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

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

3 仿真試驗(yàn)結(jié)果

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

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

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

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

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

3.2 運(yùn)行效率測評(píng)

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

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

4 小結(jié)

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

參考文獻(xiàn)：

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

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

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

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

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

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

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

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

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

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

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