基于时间窗的农机调度技术研究进展

黄凰， 陈燕燕， 陈鹏宇， 罗锐， 刘亚东， 胡炜

（1.华中农业大学工学院，农业农村部长江中下游农业装备重点实验室，武汉 430070；2.湖北省农业农村厅农业机械化管理处，武汉 430070；3.成都师范学院计算机科学学院，成都 611130）

农业机械化建设作为提高农业快速发展的奠基石，对发展具有中国典型特点的现代智慧农业意义重大。目前，我国农业用地呈现细碎化现象，而土地细碎化会造成地块生产趋同，影响和制约农户购置农机[1]。在农忙季节，农田如果无法及时进行农机作业，必将造成经济损失，也会降低农机利用率[2]。

我国农业在现代化转型过程中面临着农机供需信息滞后、农机资源调度不合理、农机站和农户沟通效率低下、资源配置不合理及农机作业效率低等问题，严重制约了智慧农业前进的步伐[3]。另外，伴随着现代化农业和农村城镇化步伐的加快，大量农村农业生产劳动力涌入城市，造成农业生产中劳动力的急剧匮乏，再加上老龄化严重，使得人们对农业机械具有越来越显著的依赖性，迫使农业进一步朝着机械化作业发展[4]，农机规模化作业已成为必然趋势。农机社会化服务形式已出现了蓬勃发展势头，亟需不断创新[5]。农机服务组织是从事各种农机化作业服务的单位或实体，是农机社会化服务的载体，经历了包括农机大户、农机协会和中介服务组织等发展阶段，当前，农机专业合作社是新型的农机服务组织[6]。农机服务方为实现农业机械合理调度需注意几下几点：①加强农机化与信息化融合，实行智能控制和精准化运行，提升农业和农机化水平；②合理分配和整合更多的农机资源，加强农机科学有效调度，最大限度发挥农机资源在农业上的作用；③提升农机服务组织信息水平和管理能力，做到有序作业和科学管理[7]。

当前，精细农业是在传统农业的基础上利用信息技术和人工智能技术在农业领域实现精准和可持续发展。利用信息技术对智能农业机械进行改造，有利于促进精细农业和精准农业的发展，是农机面向未来的发展趋势。其中，卫星导航技术为现代农业的升级和发展掀开了重要篇章。我国的北斗导航技术属于自主研发，目前，市面上大部分农机机具已安装了北斗导航装置，该技术为建立精准快速的农业机械跨区域调度作业系统提供了强有力的技术支撑，有助于我国农业发展建立独立的作业体系[8-9]。另外，地理信息系统技术和无线通信技术的快速发展也为农业机械调配作业提供了数据支撑，农户提交作业需求订单，农业机械通过使用定位技术和通用无线分组业务技术，将在农田的作业位置和完成作业任务的实时状态上传到数据库终端，多区域、多农机调度系统根据这些信息分配最优的农机调配作业方案，实现农机作业过程的优化配置，提高作业效率和农机利用率[10]。

因此，构建合理的跨区域多农机调度服务作业系统有利于农机服务方和农机需求方根据合适的作业协议及时地进行沟通与交流，大幅提升双方信息的匹配；避免多区域作业农机的盲目流动，降低农机服务组织调配农业机械的运转成本；提高农业耕、种、收效益；使农机能够及时服务对应农田作业点，提高农业机械的作业效率[11]。

本文结合农机作业的特点，从农机调度系统、作业时间窗、农机调度模型和智能优化算法等方面对国内外的研究进展进行了综述，分析了基于时间窗的农机调度技术的发展现状。智能信息技术在农机调度领域的应用可有效解决农业领域农机供需信息滞后、资源配置不合理和农机作业效率低等问题，有助于设计一种包含调度分析模块的农机调度服务作业系统，以便于深入分析和辅助决策，加强农机服务方和农机需求方之间的沟通交流，避免农机跨区域作业的盲目流动，减少农机传统调配方式作业的运转成本。

1 农机调度系统的研究现状

1.1 农机调度系统平台的研究现状

传统的农机调度方法既浪费时间又浪费人力，且农机服务组织与农户之间的信息交互滞后，易造成农机盲目和随机流动，影响农业生产率和农机作业效率[12]。现代智能农机调度系统利用物联网技术、导航定位技术和地理系统技术等，在农机上安装北斗导航系统及位置和作业等传感器，建立农机智能管理平台，加强了农机管理、调度、生产和用户间的信息交流。新技术和新机具的推广应用在农机销售和作业中发挥着重要作用。

目前，农机调度系统在农业生产中的应用优势主要体现在几个方面：①实现了农机作业信息、农机性能参数、农户和农机信息、位置坐标等信息的采集、监测和管理；②利用数据库系统对数据信息进行储存和共享，避免了数据信息采集的滞后和缺失；③对采集储存的数据信息进行分析处理，有利于对整个农业生产过程进行宏观的决策以及微观的调控，完成农机调度的智能决策，提高农机资源的利用率，提高农田作业的服务效率，增加经济效益（图1）。

农机调度研究最早始于国外，美国农业与生物工程师学会（American Society of agricultural and Biological Engineers，ASABE）对农业领域调度的定义为：在考虑时间、人力、农业机械资源、农机作业优先级和农作物的生长状况等重要因素的基础上，合理规划各种农业作业生产的时间[5]。随后，Elderen[14]提出农业领域存在纯粹和连续两种基本调度问题。21世纪初，Bochtis等[15-16]将工业领域十分常见的车间流水线调度问题应用于农机农业田间作业的多区域连续调度问题。

国外有很多公司针对农机信息管理调度系统开发了相应的农机信息管理软件。美国John Deere公司开发了JD Link农机管理系统[17]，作业人员可通过电脑端获取农机信息，以便于制定合理的调度作业计划。英国Silsoe研究所也研发出了相应软件，该系统具有作业成本核算、农机选择和配套、作业规划等功能[18]。丹麦Butani等开发了一套决策支持系统，该系统可根据农田特点、农作物差异性以及农机设备信息等提供决策意见[19]。意大利的Lazzari等[20]开发了“农业机械系统评测”模型，输入农作物品种、作业时间和农机作业过程可输出农机作业的调配方案。

我国于20世纪末将全球定位系统(global positioning system，GPS)和地理信息系统(geographic information system，GIS)等技术运用到对农机资源的分配管理调度方面，计算机和互联网的发展极大地促进了农机资源调配的优化和完善。表1列举了国内学者设计和开发的一些农机作业管理和调度系统，极大地促进了智能调度系统的研发和功能的完善。

表1 农机调度系统研究设计情况Table 1 Research and design situation of agricultural machinery scheduling system

近十年，农机调度技术在全国各省发展迅速。黑龙江省在2013年结合互联网和物联网技术及3S等技术，对农机资源的日常维护、调配管理和远程服务等功能进行升级，从而完成了对全省农机资源的全面管理调度[11]。同年，北京顺义建立了当地首个基于北斗的新型农机管理平台，该平台利用北斗卫星导航技术为当地农业提供辅助决策，大幅度提高了农机生产管理的基准化水平[31-32]。2014年，河南省许昌市综合卫星定位系统、GIS、电子监控、自动化技术和通信网络技术等对全市的农机资源进行跨区管理，农机跨区作业调度指挥中心投入使用，该中心完成了农机跨区作业的调度，保证了农机与农户的供需和信息匹配[33]。2017年，京、津、冀共建农机联合调度平台，包括农机作业供需服务系统、农机作业调度与监控系统、农机作业辅助决策系统，为京津冀三地农户、农机服务组织、农机管理部门服务的综合管理平台。同年，湖北省也建立了湖北北斗农机信息化智能管理平台，解决了传统农机管理中调度不科学、监管不及时、统计不准确的问题，为农机管理者和生产管理者提供了作业农机实时信息的综合服务型平台。

综上所述，现阶段农机调度作业系统大部分为农机监控和农机作业管理平台，通常为对农户或农机管理服务中心提供某个方面的管理服务，侧重数据的采集、统计和可视化展示，缺少深入分析和智能辅助决策平台，而对农机调度系统采取智能算法进行调度分析的研究较少。

1.2 农机智能调度技术与传统调度的区别

1.2.1 农机智能调度与车辆调度的区别 在容量约束方面，带时间窗车辆调度问题（vehicle routing problem with time windows，VRPTW）具有一定的容量约束，当车辆所载剩余货物不满足下一个客户的要求时，该调度路线停止；但在农机资源调配中，不需要考虑容量约束，只需满足作业时间窗即可，当时间窗不被满足时，调度作业路线即结束。

在车辆同质性方面，传统VRPTW假设车辆都具有同质性，不需为每条路线指定特定的车辆，最终求解结果是车辆路线集合；在农机调度中，农机没有同质性，不同农田作业点的特征和作类型可能存在差异，对农机的类型、作业能力和行驶速度等要求也就可能不同，这就使得农机调度问题比VRPTW问题更加复杂。

在调度时间和车库方面，传统VRPTW调度是单车库调度模式，其调度时间主要是车辆在送货路线上的转移时间，大部分模型都会忽略服务时间，或是以常数形式给出；但在农机调度中，调度是多车库、多任务点的调度，其调度时间除了转移时间，还有农机在不同农田的作业时间，其作业时间也会因农田面积、作业类型和农机作业能力的不同而不同。

1.2.2 农机调度系统与智能打车系统的区别

农机调度系统与智能打车系统在调度模型上会有较大差异。在即时订单的车辆推荐上，农机调度系统会对农户同时发出的多订单根据所需农机作业类型、农田位置、农田面积等调配对应农机前往进行作业，以保证完成所有农田作业的调度成本最低；而智能打车系统往往会推荐距离乘客最近的空乘车辆，也会根据司机的接单量和车辆的累计收入差异等进行综合考虑，建立车辆均衡调度机制[34]。另外，一台农机在同一时间只能服务一块农田，完成该农田作业之后才能进入下一块农田作业；而智能打车车辆可在乘客接受拼单前提下接单多位乘客，打车系统可以推荐多个用户给同一辆车辆实现车辆共享。2种系统的调度模型不同，采取的算法也会有差别[34]，农机调度一般采用元启发式算法，如遗传算法、蚁群算法、粒子群算法等群组算法进行调度优化；打车系统一般采用基于轨迹挖掘和实时用户的车辆推荐算法，如以用户请求为圆心，在一定半径范围内寻找局部最优车辆的Greedy算法、TripRec算法和Aprior算法等。

2 基于时间窗的车辆调度研究现状

带时间窗的路径规划和调度问题最先应用于车辆调度领域，是对车辆调度进行容量和时间的约束，优化求得最小代价成本的车辆路径。在车辆调度领域，时间窗主要分为硬时间窗、软时间窗和模糊时间窗3种类型。其中，硬时间窗要求车辆必须在客户需求时间内完成任务；软时间窗可允许车辆在客户要求时间之外完成任务，但需支付超出时间的惩罚费用；模糊时间窗将客户需求时间分为期望时间和可容忍时间，并用模糊隶属度函数进行刻画，以此来反映客户的满意度，在期望时间内，客户满意度为1，满意度随着模糊隶属度在[0,1]之间取值。国外学者对于3种时间窗的研究详见表2；国内学者对3种时间窗的研究详见表3。

表2 国外基于时间窗调度的研究情况Table 2 Foreign research situation of scheduling time window

表3 调度时间窗的国内研究情况Table 3 Domestic research status of dispatch time window

基于硬时间窗时，在遇到车辆资源有限且客户订单数量较多时很难找到合适可行的调度方案，且与实际弹性时间情况不符。因此，学者提出了软时间窗，不同于以往的固定性，软时间窗具有一定的应用性，更符合车辆调度中客户对时间窗的接受情况。但随着研究的深入，在实际中服务车辆迟到或提前并不一定会产生惩罚费用，只是会影响客户对服务的评价，这就引发了广大学者对客户满意度的评价表述，从而采用模糊时间窗刻画客户对车辆调度的满意度水平。相比较硬时间窗和软时间窗的研究，国内外对模糊时间窗在车辆调度路径优化方面的研究较少，尤其在农机调度领域，但采用模糊隶属度函数比硬时间窗和软时间窗在车辆调度问题中更接近实际情况，具有较高的实用价值。

3 农机资源调度优化问题模型

农机资源调度模型的搭建（图2）经常以车辆调度问题（vehicle routing problem，VRP）或带时间窗车辆调度问题为基础模型，基于此模型，发展出一系列元启发式算法以求得调度最优解，在实际运用中取得了较好效果。针对小规模农机作业情况，Foulds等[68]研究油菜籽收获作业时，在考虑农机作业时间约束和农机资源限制约束的基础上建立了农机调配线性规划模型；Bochtis等[69-71]将农机资源调配分为农田覆盖、农机资源分配、调配路径最优化以及方案调整，建立了二进制整数规划问题模型，并在传统车辆调度模型基础上，提出了田间农机作业规划和资源调度模型。针对农机跨区域作业情况，Jensen等[72]综合跨农场作业时间和作业空间目标进行优化，建立了跨区域农机作业模型，使用图论法和Dijkstra算法解决单路径规划模型问题；Alaiso等[73]基于旅行商问题建立了时间窗旅行商变体模型，解决了大量农田作业承包问题。针对农机作业存在连续作业的情况，Orfanou等[74]建立了包括输入、调度和输出的农机连续作业调度模型。另外，针对模型非线性问题，Ramos-Castillo等[75]提出了基于代理的优化和混合整数非线性规划（mixed integer nonlinear programming，MINLP）模型。各种模型优化目标及模型具体表现如表4所示。

表4 农机调度模型的研究情况Table 4 Research status of agricultural machinery scheduling models

图2 智能优化模型平台的系统框架图[28]Fig.2 System framework diagram of the intelligent optimization model platform

4 农机调度问题的智能算法

在小规模车辆物流调度中，传统的启发式算法由于具有算法简单、求解速度快等优点而被广泛应用。但在农业生产领域，农机调度模型需要解决多农机服务中心跨区域作业调配问题，因此，较传统VRPTW问题更加复杂。随着对农机调度模式的分析和研究，遗传算法、蚁群算法、粒子群算法、模拟退火算法、禁忌搜索算法等智能优化算法被逐渐应用，且在不同的作业情境下取得了良好的效果。

4.1 单一智能算法

4.1.1 遗传算法 遗传算法具有较好的全局寻优能力和环境适应性，被广泛应用于组合优化领域，近年来经过不断地改进优化更适用于多种调度模型。在对简单调度模型寻优方面，Bochtis等[69]对农机调度路径生成模型进行了求解优化；任建顺等[88]在此基础上对遗传算法进行改进，利用多目标权重的适应度函数将多目标转化为单目标，以此来解决农机时空动态调度问题；谢婷婷[10]改进了路径交叉算子和自适应遗传算子，使遗传算法实现了全局最优。在作业时间窗问题上，王雪阳等[82]设计了初始种群的2级多段编码，提出了单个染色体指定位置交叉的遗传算法；王文权[89]基于改进插入式路径构造了启发式算法和邻域优化技术的遗传算法，改进了变异算子和邻域搜索算子，提高了计算效率；吕云杰等[90]改进了自适应遗传算子的农机调度方法，提出了父代染色体以随机生成的掩码为依据在指定位置交叉的算法规则，以及由种群状态来确定个体交叉概率与变异概率的自适应方法，在农田维数变化的调度问题中取得了良好的效果。

4.1.2 蚁群算法和粒子群算法 蚁群算法和粒子群算法都是寻求最优路径的概率性算法。龚瑞昆等[91]改进了蚁群算法，在算法中引入了节约矩阵，针对不同搜索时段采用不同的信息挥发因子，再通过局部搜索策略搜索最优解，解决了蚁群算法易陷入局部最优和收敛速度慢的缺点。谌林等[92]使用自适应策略，在选择概率方式后利用轮盘赌策略对下条路径进行选择，提高了蚁群算法的效率。针对多机协同的农田动态环境，曹如月等[93]设计了基于任务序列规划的蚁群算法，通过状态转移概率公式选择地块、修改禁忌表并更新信息素来进行迭代优化，有效地降低了路径代价。Sethanan等[94]将优化目标设置为最大化甘蔗产量和最小化收获距离，提出了MOGLNPSO算法，即结合gbest、lbest和nebest的粒子群优化算法，该算法制定出了新的粒子编码和解码方案，结合路径规划的可访问性和分割收获约束，在实际中有利于提出更好的解决方案。

4.1.3 模拟退火算法和禁忌搜索算法 陈少华等[95]在模拟退火算法的基础上引入了协同进化，把高维变量分解成多组低维变量，每组低维变量形成独立的子种群，子种群间进行独立进化，个体适应度则以该个体和代表个体组合成完备解，对完备解计算适应度值，以此来评判个体优劣。Omidvar等[96]指出含有协同进化的模拟退火算法是解决高维优化问题的主流方法。

禁忌搜索算法通过模拟人的思维，利用短期和长期记忆来保证算法全局最优。刘明剑等[97]利用禁忌搜索算法解决了交叉路口自治车辆调度，证明基于禁忌搜索的调度优化策略优于FCFS策略和信号控制策略。针对软时间窗的多服务需求车辆调度问题，潘帅等[98]改进禁忌搜索算法，使用Lingo对多个算例进行精确求解，对解的构造方法与邻域变换规则进行改良，证明改进后的禁忌搜索算法更具有效性。

4.2 多种智能算法的结合

结合智慧农业发展现状和多区域互联农机服务调度特点，马军岩等[87]改进了原始粒子群算法，引入模拟退火过程优化农机作业路径，设计改进模拟退火和粒子群优化的混合智能算法，提高算法的全局搜索能力。为解决带时间窗的车辆路径问题，Orfanou等[74]提出结合贪婪算法和禁忌搜索算法对农机调度进行优化，其中，禁忌搜索算法采用邻域搜索算法，避免了优化结果陷入局部最优。

在智能优化求解中，遗传算法因全局择优而被广泛应用于农机调度领域，很多国内外学者将遗传算法和其他智能算法相结合，既提高了优化全局性，也避免了过早收敛。为优化农机资源的调配，Guan等[76-77]提出两阶段算法，其中，第一阶段利用模拟退火算法对农机资源先进行分配；第二阶段结合Petri网络模型和遗传算法对模型进行优化求解。两阶段算法避免了死循环，使资源相互独立，提高了生成最优方案的效率。吴珂[99]将遗传算法的全局收敛性和蚁群算法的并行性进行优势互补，提高了收敛速度和算法的全局搜索能力。秦勇等[100]将遗传算法和贪婪算法相结合，设计了尺度变换的适应度函数，采用确定式采样选择方法提高种群质量，有效地解决了并行测试任务的调度问题。

综上可见，智能优化算法在农机调度技术中的应用极大地提高了农机作业调度的精度和速度；多种算法结合的混合算法更是增强了全局寻优能力，提升收敛速率的同时避免了算法早熟；智能优化算法在跨区域多机调度问题上具有较强优势，而跨区域多机调度也是农机调度与传统车辆调度的主要区别之一。

5 结语

国内外关于时间窗的多农机跨区域农机资源调度问题的主要聚焦点略有不同。在农机调度系统方面，国外研究一方面主要关注大面积农田的农机资源调度，另一方面聚焦于多机协同连续作业问题；而国内研究主要聚焦在以农机合作社为服务中心，面向农户订单的调度模式，调度系统多为农机监控系统，对农机和作业人员进行信息管理，而对调度模块分析较少，调度智能算法和调度系统的结合力度不够。在农机调度模型的建立方面，国内外都多以旅行商和车辆调度问题的变体模型为基础，其中，国外研究在模型约束条件里考虑了更多的约束条件，包括动态和随机农机调度约束以及容量约束等；而我国农业生产与国外存在较大差异，因此，国外的很多调度模型不适用于国内农机调度，国内现有的农机调度模型大多属于带时间窗的车辆调度问题，而对农机作业匹配约束、多农机型号约束等考虑较少。在调度算法设计上，国内外均使用线性规划类的精确算法，近年来，随着元启发算法（遗传算法、蚁群算法、粒子群算法、模拟退火算法和禁忌搜索算法等）的提出和完善，这些智能算法越来越被广泛地应用于农机调度领域。但目前来说，综合考虑多农机服务中心收益和农户收益、农机使用成本、天气道路等影响、适用于多区互联的农机调度模型和全局优化智能调度算法仍然亟需开发。