農機跨區作業緊急調配算法適宜性選擇

張 璠，滕桂法，苑迎春，王克儉，范鐵鋼，張昱婷

0 引 言

中國是農業大國，農業機械是現代農業發展的物質基礎和科技載體。如何提升農機作業組織化程度、信息化水平，確保糧食顆粒歸倉是當前中國農業的首要任務，如何增加機手和農戶收益是擺在我們面前的重要課題[1-2]。三夏時節大量聯合收割機跨區作業，當惡劣天氣來臨前或有緊急作業需求時，迫切需要緊急調配農機進行搶收搶種工作。由于時間緊迫，當地農機管理部門無法獲取可用農機的GPS位置、作業能力、作業位置等實時信息，一般采用打電話、發短信、貼通告等形式，召集可用農機來參與搶收任務，通過人為指派或憑經驗調配農機無法保證整個調配方案的合理。常出現一些農田作業點任務完成后農機有閑置，另一些農田作業點由于缺少農機，不能及時完成搶收任務，使農田遭受損失。因此合理的農機應急調配方案對順利完成搶收任務起決定作用。為使損失和成本降到最低，需要整合農機和農田信息，提出科學合理的緊急調配方案[3]。

大多數歐洲國家、美國、加拿大、澳大利亞等國家土地經營規模較大，經濟條件好，配有大型農業機械，不僅能保證農業生產需求，并且機具利用率相對較高。國外對農機跨區作業研究較少，國外農田和農機一般都是農場主自有，很少組織大規模農機跨區作業，重點考慮的是收獲機械和運輸車輛之間的配合問題[4-14]。在國內調度算法的研究中，文獻[15]構建基于時間窗的農機資源時空調度數學模型，通過動態規劃的思想完成對每個決策的最優解的計算。文獻[16]建立了應急車輛調度模型,提出基于遺傳算法的模型求解方法。文獻[17]針對復雜災害情景，采用自適應免疫克隆選擇文化算法[18]和勢能抵消算法進行求解。上述文獻的研究成果對農機緊急調配有一定啟發，但農機緊急調配不同于車輛應急調度問題，農機作為緊急調配的資源可重復利用，需要考慮多農機多階段調配。文獻[19-22]提出了基于機主選擇的農機調配模式，設計了基于啟發式優先級規則的調配算法，通過不斷改進，驗證了算法的有效性，但并未對農機緊急調配問題進行深入研究。文獻[23]根據極端天氣導致的災害分布情況，設計了農機調配最佳反應函數，根據粒子群算法得到極端天氣下農機調度離散種群映射，實現粒子群更新并獲取最優的調度。文獻[24-29]通過GIS、GPRS及GPS等技術采集農機作業數據，建立了農機作業信息管理或決策系統。農機信息服務平臺[30-31]僅為機手、農機合作社等提供作業過程中各類供需信息，并未給出可行的調度方案。當有緊急作業需求時，農機管理部門迫切需要緊急作業方案來指導搶收搶種。現有調度模型或系統不適合解決緊急調配問題，無法提供科學有效的智能決策服務。本文主要研究農機跨區作業緊急調配問題，綜合地塊位置、地塊面積、時間期限等因素和可用農機信息，以最小化損失和成本為目的，通過緊急調配算法計算得到可行的緊急調配方案，為農機管理部門決策分析提供科學依據。

1 智慧農機平臺下的緊急調配問題

1.1 問題分析

緊急調配要在時間期限內做出科學合理的決策，涉及到多地農機資源需要在多受災點間進行調配。因此需要將各受災點的信息和各地農機資源整合起來協同應對。智慧農機利用物聯網、移動互聯網和北斗定位等新一代信息技術，為種植戶、機手、合作社、政府管理部門等提供智能決策與信息化服務。當有緊急任務時，各地通過互聯網上報待作業農田地塊信息，主要包括農機作業緊急調度區域內的地塊面積、地塊經緯度信息等。安裝在農機上的智能終端實時采集的經緯度信息、作業能力、油耗、行駛速度等信息上傳到智慧農機平臺。

農機跨區緊急調配問題要在多農機和多作業點間建立一種映射關系。根據地塊位置信息，智能搜索出農田附近的可用農機信息，綜合地塊位置、地塊面積、時間期限等因素，組織適當的行車路線，使農機有序地為農田作業點服務，以最小化調配成本和損失為目標，計算得到最優的緊急調配方案，供政府、農機管理部門或者合作社等部門參考。圖 1為基于智慧農機的緊急調配示意圖。

圖1 智慧農機緊急調配示意圖Fig.1 Schematic diagram of emergency scheduling and allocating of intelligent agricultural machinery

1.2 農機緊急調配模型

1.2.1 調配問題形式化描述

根據對緊急調配問題的分析，本節將對緊急調配問題進行形式化描述。

式中， a reai表示農田i的面積,hm2；

LOCFi={表示農田 i的位置信息，LNGFi分別表示農田i的經緯度信息。

式中 a bilityj表示農機j的工作能力， ve locityj表示農機j的行駛速度；

cos tj=｝表示從農機 j到農田 i的成本，其中 c os t Ij表示每公里的油耗成本，元； c os t Sj表示每天的作業成本，元。

LOCMj=｝表示農機 j的位置信息，和 L ATMj分別表示農機j的經緯度信息。

的到達時刻， tsji表示農機j到農田i的開始作業時刻，表示農機j到農田i的結束時刻；s cji表示農機j為農田i作業的面積，hm2； dji表示農機j到農田i的實際距離，km； Tdeadline表示緊急調配任務的截止時刻。

1.2.2 調配模型建立

1）調配目標

式（1）中 Emin 表示緊急調配的總成本，包括農機的運輸成本和作業成本，運輸成本與每公里的油耗和行駛距離有關，作業成本與作業油耗和人工作業成本有關；min L 表示緊急調配中的損失，損失是指到緊急調配任務的截止期時，仍有未作業完的農田就會產生損失。損失通過單位面積的損失乘以未作業完的農田面積計算得到，其中p表示單位面積的損失。式（3）表示緊急調配的成本由路上成本和人工成本2部分組成；式（4）表示從農機j到達農田i的時間等于農機j出發去農田i的時間加上路上的運輸時間；式（5）表示所有到農田i作業的農機所完成的面積小于等于農田i的面積；式（6）表示農機j為農田i作業結束時間小于等于任務的截止時間。

2 多機多任務緊急調配算法

多機多任務的緊急調配問題是一類多階段決策優化問題，多臺農機要分多階段完成多塊農田緊急任務。當可用農機足以完成所有農田作業任務時，調配目標是最小化農機調配成本；當可用農機不足以完成所有農田作業任務時，調配目標首先是最小化農田作業點損失，然后是最小化農機調配成本。基于上述分析，本文提出了基于優先策略的多機多任務緊急調配算法，一種是基于距離最近優先的策略，一種是基于貢獻度最大優先的策略。為方便描述，本文首先做出定義。

2.1 相關定義

定義1實際距離

實際距離是指根據農機和農田經緯度信息，調用百度地圖接口計算得到的距離。

定義2最短距離

從當前每臺可用農機到每塊待作業農田間的實際距離中最短的一個稱為最短距離。

定義3貢獻度

農機對農田貢獻度是指某農機在時間期限內可以為某農田服務的面積，即該農機對該農田的貢獻度越大，說明該農機為該農田的服務面積就越大。如下為農機 j對農田i貢獻度的計算公式。

2.2 基于最短距離優先的緊急調配算法

該算法根據定義 2，搜索距離最短的一對農機和農田，優先分配并計算成本，若農田作業任務完成，而該農機仍可用則繼續把該農機分配給最近的農田；若該農田未完成，則記錄該農機不可用，繼續搜索當前距離最短農機和農田，直到所有農田均被完成，或所有農機被分配完為止。其中uncompletedcount為未完成的農田數量，unusedcount為可用農機數量，具體算法步驟如下圖2所示。

2.3 基于貢獻度最大優先的緊急調配算法研究.

該算法根據公式（7），計算各農機到各農田貢獻度，搜索貢獻度最大的一組農機和農田進行優先分配。若農田作業任務完成，而該農機仍可用，則計算該農機到各農田的貢獻度，把該農機分配給貢獻度最大的農田；若該農田未完成，則記錄該農機不可用，繼續搜索當前貢獻度最大的農機和農田，直到所有農田均被完成，或所有農機被分配完為止。具體算法步驟如下圖3所示。

圖2 基于最短距離優先的緊急調配算法流程Fig.2 Flow chart of emergency allocation algorithmwith rules of shortest-distance first

圖3 基于貢獻度最大優先的緊急調配算法流程Fig.3 Flowchart of emergency allocation algorithm with rules of max-ability first

3 算法比較

3.1 試驗數據準備

本文以河北省邯鄲市的小麥聯合收割機為研究對象，數據來源于智慧農機平臺。農田面積、位置等信息由農機管理部門發布，農機位置、工作能力等信息由安裝在農機上的智能終端盒子采集。緊急農田和可用農機的信息如下表1、表2和表3所示。表1為緊急作業農田的基本信息，主要包括農田面積以及農田的經緯度信息；表 2為可用聯合收割機的基本信息，包括聯合收割機類型以及聯合收割機當前的經緯度信息，表 3為聯合收割機的作業能力信息。

表1 緊急作業農田的基本信息Table 1 Basic information of farmland in emergency scheduling and allocating

表2 可用聯合收割機的基本信息Table 2 Basic information of available combine harvesters

表3 聯合收割機的作業能力信息Table 3 Operation ability of combine harvesters

3.2 算法計算結果

基于最短距離優先的緊急調配算法（shortest-distance first algorithm）記為SDFA，基于最大貢獻度的緊急調配算法（max-ability first algorithm）記為MAFA。表4從農機為農田作業的面積、作業時間和行駛距離 3方面記錄了算法SDFA和MAFA的調配方案。表5從緊急任務的損失比例、成本、調配距離、完成比例等方面，對 2種算法調配結果進行比較。

表4 最短距離優先的緊急調配和大貢獻度的緊急調配算法的調配結果Table 4 Scheduling and allocating results of shortest-distance first algorithm (SDFA) and max-ability first algorithm (MAFA)

表5 2種算法調配結果比較Table 5 Comparison results of two algorithms

從表4可知，算法SDFA和MAFA的調配方案包括為農田作業的每個農機、農機為農田作業的面積、作業時間等信息。從表5的比較可知，2種算法損失均為0，作業完成比例為100%，可用農機足以完成緊急農田作業任務。在此情況下，算法MAFA的調配成本和調配距離分別為13 936.50元和682.00km，算法SDFA的調配成本和調配距離分別為 14 648.50元和716.80km。即在農機充足時，算法MAFA的調配成本和調配距離均低于算法SDFA，MAFA的調配結果更優。

3.3 試驗分析

3.3.1 農機數量對算法的影響

為進一步驗證2種緊急調配算法的可行性和適用性，本文分別模擬5組農機充足的數據和5組農機不足的數據，每組包含6塊待作業農田、12臺可用聯合收割機。通過上述2種算法計算得到結果如表6和表7所示。通過算法MAFA計算出的損失、成本和調配距離分別記為LOSSm、 C OSTm和 D ISTANCEm，通過算法SDFA計算出的損失、成本和調配距離標記為 L OSSs、 C OSTs和DISTANCEs。當農機充足時，算法SDFA和MAFA的損失均為0，即 R atio1= 0 ； R atio2是指當農機充足時，表示算法MAFA的成本比SDFA成本的下降比例； R atio3是指當農機充足時，算法MAFA的調配距離比SDFA調配距離的下降比例，R atio4是指當農機不足時，算法SDFA的損失比MAFA損失的下降比例； R atio5是指當農機不足時，算法SDFA的成本比MAFA成本的下降比例；R a tio6是指當農機不足時，算法SDFA的調配距離比MAFA調配距離的下降比例。具體定義如下所示。

表6 農機充足時2種緊急調配方案的比較Table 6 Comparison of emergent scheduling and allocating schemes with adequate farm machinery

表7 農機不足時2種緊急調配算法的結果比較Table.7 Comparison of emergent scheduling and allocating schemes with insufficient farm machinery

從表6可知，當農機數量充足時，算法SDFA的調配成本和距離要高于算法MAFA，算法MAFA的調配成本和距離要比算法SDFA的平均降低了4.34% 和3.79%。從表7中可知，當農機數量不充足時，算法MAFA的損失、成本和調配距離要高于算法SDFA，算法SDFA的損失、成本和調配距離要比算法 MAFA的平均降低了12.79%、4.11%和4.96%。通過5組隨機數據的計算結果進一步驗證得出如下結論，當農機數量充足時，基于最大貢獻度優先的緊急調配算法的計算結果更優。當農機不足時，基于最短距離優先的緊急調配算法的計算結果更優。

3.3.2 農田數量對算法的影響

為進一步驗證算法性能，討論農機數量為 12，農田數量分別為6、10、15和30時，采用上述2種算法來計算調配方案，并從平均運算時間的角度對SDFA和MAFA 2種算法與文獻[22]中提出的基于非合作博弈應急調配算法(algorithm based on non-cooperative game, NCGA)進行比較。通過計算得到結果如表8所示。其中SDFA、MAFA和 NCGA 3種算法的平均運算時間，分別記為 A CTs、ACTm和 A CTn。算法SDFA和MAFA的下降率分別記為DRs和 D Rm， D Rs是指算法SDFA平均運算時間比算法NCGA平均運算時間的下降比例， D Rm是指算法MAFA平均運算時間比算法NCGA平均運算時間的下降比例，DRs和 D Rm的公式具體如下。

表8 3種算法的平均運算時間比較Table 8 Comparison of average calculating operationtime among threealgorithms

由表8可知，農田數量為6時，NCGA算法的平均運行時間為3.215 s，本文SDFA和MAFA 2種算法的平均運行時間均不超過2.4 s，運算性能均提升25%以上。農田數量為10時，NCGA算法的平均運行時間為4.286 s，本文2種算法的平均運行時間均不超過2.7 s，運算性能分別提升37%以上。農田數量為15時，NCGA算法的平均運行時間為5.369 s，本文的2種算法的均不超過3.3 s，運算性能分別提升39%以上。農田數量為30時，NCGA算法的平均運行時間為6.485 s，本文的2種算法的均不超過3.8 s，運算性能分別提升41%以上。

由此可知，隨著農田數量的增加，本文提出 2種算法的平均運算時間要明顯低于比文獻[22]中算法的運行時間。本文 2種算法的平均運算時間基本持平，均具有較好的性能。

4 結 論

多機多任務緊急調配問題以最小化調配成本和損失為目標，根據多臺農機要分多階段完成多塊農田緊急任務的特點，本文提出了 2種基于優先策略的多機多任務緊急調配算法，分別為算法SDFA和算法MAFA。通過隨機試驗分析可得出如下結論。

當可用農機充足時，算法 MAFA的調配成本要比SDFA的成本降低了4.34%，當農機不足時，SDFA的調配成本要比MAFA的損失和調配成本分別下降了12.79%和4.11%。由此可知基于最大貢獻度優先的緊急調配算法更適用于農機數量充足的情況，基于最短距離優先的緊急調配算法更適用于農機不足的情況。

當農機數量為6時，本文提出的2種算法比筆者之前提出的NCGA的平均運算性能均提升25%以上。當農機數量為30時，本文的2種算法的平均性能均提升41%以上。隨著農田數量的增加，本文提出 2種算法的平均運算時間基本持平，2種算法均具有較好的性能。本文研究成果可為緊急調配決策分析科學依據。

本文農機緊急調配的總成本主要包括農機運輸成本和作業成本 2部分。運輸成本主要與農機行駛油耗和行駛距離有關。為簡化問題方便計算，本文中假定各農機的行駛油耗相同。作業成本與作業油耗和機手的人工成本有關。本文假定單位時間的作業油耗和行駛油耗是固定的。然而農機的行駛油耗和作業油耗均為動態變量，跟農機動力、地塊形狀、大小、農機手駕駛習慣和熟練程度等多因素有關，在后續的研究中將會進一步研究行駛油耗和作業油耗的影響因素。

[1] 中國農業年鑒[Z]. 2016.

[2] 河北農村統計年鑒[Z]. 2016.

[3] 張璠. 農機調配策略研究[D]. 保定：河北農業大學，2012.Fan Zhang. Study on Farm Machinery Scheduling and Allocating Strategies[D]. Baoding: Agricultural University of Hebei, 2012. (in Chinese with English abstract)

[4] Sorensen C G, Bochtis D D. Conceptual model of fleet management in agriculture[J]. Biosystems Engineering, 2010,105(1): 41－50.

[5] Bochtis D D, Dogoulis P, Busato P, et al. A flow-shop problem formulation of biomass handling operations scheduling.Computers and Electronics in Agriculture, 2013, 49(5): 49－56.

[6] Zhiguo S, Hui X, Wensheng W. An architecture for the agricultural machinery intelligent scheduling in cross-regional work based on cloud computing and internet of things[C]. //International Conference on Computer and Computing Technologies in Agriculture. Springer, Berlin, Heidelberg,2011, 344: 9－15.

[7] A Orfanou, P Busato, DD Bochtis, et al. Scheduling for machinery fleets in biomass multiple-field operations[J].Computers & electronics in agriculture, 2013, 94(11): 12－19.

[8] Wayan Astika, Akira Sasao, Kenshi Sakai , et al. Stochastic farm work scheduling algorithm based on short range weather variation[J]. Journal of JSAM, 1999, 61(2): 157－164.

[9] Dionysis Bochtisa, ClausG C, Sorensena, et al. Advances in agricultural machinery management: A review[J]. Biosystems-Engineering, 2014, 126(39): 69－81.

[10] Spekken M, & de Bruin, S Optimized routing on agricultural fields by minimizing maneuvering and servicing time. Precision Agriculture, 2013, 14(2): 224－244.

[11] Bochtis D D, Dogoulis P, Busato P, et al. A flow-shop problem formulation of biomass handling operations scheduling.Computers and Electronics in Agriculture, 2013, 49(5): 49－56.

[12] Jensen M A, Bochtis D, Sorensen C G, et al. In-field and inter-field path planning for agricultural transport units.Computers & Industrial Engineering, 2012, 63(4): 1054－1061.[13] Hameed I A, Bochtis D D, Sorensen CG. Driving angle and track sequence optimization for the operational path planning using genetic algorithms. Applied Engineering in Agriculture,2011, 27(6): 1077－1086.

[14] Jin J, Tang L. Optimal coverage path planning for arrable farming on 2D surfaces. Transactions of the ASABE, 2010,53(1): 283－295.

[15] 吳才聰，蔡亞平，羅夢佳，等. 基于時間窗的農機資源時空調度模型[J]. 農業機械學報，2013，44(5)：237－241.Wu Caicong, Cai Yaping, Luo Mengjia, et al. Time-windows based temporal and spatial scheduling model for agricultural machinery resources[J]. Transactions of The Chinese Society of Agricultural Machinery, 2013, 44(5): 237－241. (in Chinese with English abstract)

[16] 楊海強，陳衛明. 存在不確定災害點的交通運輸網絡應急車輛調度研究[J]. 安全與環境工程，2017，24(5)：26－30.Yang Haiqiang, Chen Weiming.Study on emergency vehicle scheduling under transportation network with uncertain disaster points[J]. Safety and Environmental Engineering.2017, 24(5): 26－30. (in Chinese with English abstract)

[17] 葛洪磊，劉南. 復雜災害情景下應急資源配置的隨機規劃模型[J]. 系統工程理論與實踐，2014，(12)：3034－3042.Ge Honglei, Liu Nan. A stochastic programming model for relief resources allocation problem based on complex disaster scenarios[J]. Systems Engineering-Theory & Practice, 2014(12):3034－3042. (in Chinese with English abstract)

[18] 郭一楠，王輝，程健. 自適應免疫克隆選擇文化算法[J]，電子學報，2010，38(4)：966－972.GuoYinan, Wang Hui, Chen Jian. Adaptive immune clonal selection cultural algorithm[J]. Acta Electronica Sinica, 2010,38(4): 966－972. (in Chinese with English abstract)

[19] 張璠，滕桂法，馬建斌，等. 基于啟發式優先級規則的農機調配算法[J]. 農業工程學報，2012，28(10)：78－85.Zhang Fan, Teng Guifa, Ma Jianbin, et al. Farm machinery scheduling and allocating based on heuristic priority rules[J].Transactions of the Chinese Society of Agricultural Engineering(Transactions of the CSAE), 2012, 28(10): 78－85. (in Chinese with English abstract)

[20] Zhang Fan, Teng Guifa, Chang Shuhui, et al. Study on farm machinery scheduling and allocating problem with heuristic priority rules[J], ICIC Express Letters, 2012, 6(7): 1797－1802, 2012.

[21] Zhang Fan, Li Yueli, Chen Chen. Research on search-based scheduling and allocating algorithm[J], International Journal of Grid and Distributed Computing, 2016, 9(5): 167－180.

[22] Zhang Fan, Gao Yuan, Li Yueli. Research on cross-regional emergency scheduling and allocating strategies[J]. International Journal of Grid and Distributed Computing, 2016, 9(5): 89－98.

[23] 李婷. 極端天氣下的農機應急調配仿真模型[J]. 科技通報.2014，12：193－195.Li Ting, Simulation modeling of agricultural machinery emergency deployment under extreme weather[J]. Bulletin of Science and Technology, 2014, 12: 193－195. (in Chinese with English abstract)

[24] 楊立國，李傳友，賈生，等. 北京市農機管理調度系統設計與實現[J]. 農學學報，2014，4(8)：96－100.Yang Liguo, Li Chuanyou, Jia Sheng, et al. Design and implementation of Beijing agricultural machinery management system[J]. Journal of Agriculture, 2014, 4(8): 96－100. (in Chinese with English abstract)

[25] 劉碧貞，黃華，祝詩平等. 基于北斗/GPS的谷物收割機作業綜合管理系統[J]. 農業工程學報，2015，31(10)：204－210.Liu Bizhen, Huang Hua, Zhu Shiping, Xiang Biwang. Integrated management system of grain combine harvester based on Beidou & GPS[J]. Transactions of the Chinese Society of Agricultural Engineering (Transactions of the CSAE), 2015,31(10): 204－210. (in Chinese with English abstract)

[26] 李洪，姚光強，陳立平. 基于GPS，GPRS和GIS的農機監控調度系統[J]. 農業工程學報，2008，24(2)：119－112.Li Hong, Yao Guangqiang, Chen Liping. Farm machinery monitoring and scheduling system based on GPS, GPRS and GIS[J]. Transactions of the Chinese Society of Agricultural Engineering (Transactions of the CSAE), 2008, 24(2): 119－122. (in Chinese with English abstract)

[27] 王壯，陳立平，劉永生. 農機監控調度系統的設計與實現[J].計算機工程，2010，36(11)：232－234，237.Wang Zhuang, Chen Liping, Liu Yongsheng. Design and implementation of agricultural machinery monitoring and scheduling system[J]. Computer Engineering, 2010, 36(11):232－234, 237. (in Chinese with English abstract )

[28] 王少農，莊衛東，王熙. 農業機械遠程監控管理信息系統研究[J]. 農機化研究，2015，37(6)：264－268.Wang Shaonong, Zhuang Weidong, Wang Xi. Research on agricultural machinery remote control management system[J].Journal of agricultural mechanization research, 2015, 37(6):264－268. (in Chinese with English abstract)

[29] Zhu XiaoNing, Yan Rui, Wang HongLi. Harvesting scheduling operations for the machinery owners under multi-farmland,multi-type situation with time window-an empirical study arising in agricultural contexts in China[J]. INMATEHAgricultural Engineering, 2015, 46(2): 175－182.

[30] 農機跨區作業供求信息查詢. [EB/OL]2017 [2017-10-01]http://kq.amic.agri.gov.cn/nxtwebfreamwork/kq/more.do?typ esort=2

[31] 福田雷沃重工：信息化支撐服務化. [EB/OL]2012 [2012- 08-20]https://www.nongjitong.com/news/union/2012/600429. html