农机跨区作业紧急调配算法适宜性选择

张 璠，滕桂法，苑迎春，王克俭，范铁钢，张昱婷

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