摘要:針對農(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.