基于任务单元的运粮车响应调度优化

曹光乔 南 风，2 陈 聪 张庆凯

(1.农业农村部 南京农业机械化研究所，南京 210014；2.中国农业科学院 研究生院，北京 463000；3.西北农林科技大学 机械与电子工程学院，陕西 杨凌 712100)

目前我国新兴经营主体和适度规模的田间收获作业服务需求不断增长[1]，对农机配置与路径规划的要求也在不断提高，除了收割机单独的调度模式以外，服务组织也迫切需要精确合理的运粮车响应方案。研究多约束环境的复杂调度问题，摆脱依靠传统的人为经验，获得科学合理的运粮车响应路径优化方案，对节约农机资源以及提升粮食收获和运输整体效率具有重要意义[2-3]。

国内外大型农场的集中收获作业，收割机与运粮车调度有3种响应方式：运粮车田间跟随收割机进行作业；收割机专门配备固定数量的运粮车进行卸粮作业；收割机选择定点卸粮的位置，运粮车及时到达[4-5]。这3种方式均不需要考虑多台收割机与运粮车的复杂响应，很少针对运粮车制定精确路径规划。对于适度规模的新兴经营主体，服务组织无法为1台收割机专门配备 2 辆以上的运粮车，尤其在农忙时节，收割机与运粮车数量不匹配情况普遍存在。因此，类似大型农场的冗余运粮车与收割机响应调度模式和方法并不可取，服务组织缺乏运输设备不足环境下的调度规划方案。

随着我国农村劳动力大量转移，土地流转和作业服务托管加速，适度规模经营成为现代农业发展的必然趋势[6-9]。农作物收割和运输作业，具有很强的时效性，收割机和运粮车作业调度缺乏详细规划和技术手段，其效率很大程度依赖于人工操作的经验性[10]。家庭农场、综合农事服务中心等模式兴盛发展，其拥有的农田数量和经营规模不断增加，但仍然具有小规模和零散化的特点[11]，主要依靠农机服务组织提供生产性农事服务[12-14]。农业环境小规模、零散化的特点也决定了收运响应需要更加灵活、科学的匹配机制，以及对运粮车详细、精确的调度规划。

国内外针对农业机械调度问题多集中于田间农机资源的调配和路径优化问题，围绕联合收割机和大型农田任务等2个对象进行资源调度，重点研究联合收割机的路径转移。围绕不同类型的农机调度问题，张璠等[15]提出了两种基于优先策略的多机多任务紧急调配算法，建立了以调配成本和损失最小化为目标的紧急调配模型；吴才聪等[16-17]建立了带时间窗约束的农机资源调度数学模型，并以动态规划的思想进行模型求解。围绕农机调度算法问题，许多研究认为农机调度即为车辆调度，提出了一些相关算法，取得了良好的成效。例如 Bochtis D D等[18]针对农业领域的车辆调度问题，使用 VRP 的方法解决农业车队管理问题，增强传统的农机管理系统；Guan S等[19]提出一种两阶段的农机调度方案，首先对农机资源进行分配，然后利用遗传算法与模拟退火算法相结合对调度模型进行求解，同时他们也将农业生产过程划分为2个阶段，采用优先级原则对农机资源进行合理分配，利用遗传算法实现农机合理调度，提高资源利用率[20]。围绕收割机与运粮车协同调度问题，He P F等[21]将收割机收获和运粮车运输问题考虑为两级多行程问题，根据运粮车需要响应的具体位置动态变化，从而提出混合整数新型规划模型，并提出一种启发式算法进行求解，属于概念性的调度响应问题[22]；Ali O等[4]将收割机和运粮车的响应问题转化为内场物流的车辆路径问题，模型适用于大面积农田的场内路径规划，无法解决运粮车的场外路径规划。围绕农机具收获和运输协同调度的研究[23-27]，国内外更多的是集中于作业理论的系统分析和农机具数字化监控系统和信息平台的设计开发，但是不能为用户提供相关的调度决策。收割机和运粮车响应问题属于比较复杂的多目标组合优化问题[28-29]，在已有的少数响应调度研究中，多将其转化为带时间窗的旅行商问题、带时间窗的VPR问题或者运筹学的运输问题，仅仅考虑作业队行走路线，未结合时间因素和空间因素。

结合农业环境小规模零散化的特点，收割机与运粮车响应模式研究与科学合理的运粮车调度规划研究较为薄弱，探究收割机与运粮车的协同响应成为启动本项研究的依据。

本研究拟将任务单元作为收割机作业的界限，分析适度规模场景下的收、运响应作业模式，运用动态规划思想去解决静态规划问题，以期为运粮车科学调度提供优化方案与决策依据，提高运输装备的利用效率。

1 运粮车与收割机响应模型的建立

1.1 任务单元

本研究将包含收割机的农作物收获区域定义为任务单元，单台收割机在一定规模的该区域独立完成收获作业。任务单元彼此间相互独立，为同一主体所有。同一主体是指经营农田的种粮大户或者家庭农场，为了方便收获安排，将该主体经营的所有土地划分为若干任务单元。同一主体能够满足运粮车进行往复循环使用的要求，承担多个任务单元的粮食载运。任务单元作为收获任务的分解，可以是零散分布的农田或者是大面积农田的某个划分区域。

运粮车的响应对象是收割机，而收割机的纯收割时间及运粮车响应次数又与农田产量息息相关，为了简化收运响应机制，减少多种对象的复杂约束，本研究将收割机与农田区域逐一对应，即以任务单元作为收割机作业的界限，1个任务单元只由1台收割机进行作业。经过实际调研，江苏省 3.0～13.5 hm2(50～200亩)的家庭农场和种粮大户等主体，80% 的单田面积为0.33～1.0 hm2，因此选取适度规模经营0.33～1.0 hm2为任务单元面积。

1.2 响应模式

收割机与运粮车响应调度描述为：农机服务组织为同一经营主体所属的任务单元服务，如何实现较少运粮车匹配收割机从而完成收获、运输任务的调度规划问题。

本研究选取当前时刻收割机在任务单元中的作业状态(收割作业状态、收割完成状态、等待卸粮状态)，进行模型建立和求解。由于任务单元面积较小，运粮车在单元内抵达响应位置时所行驶的路径要远小于运粮车在单元外的转移路径，故忽略收割机和运粮车在单元内的行走。若同时考虑收割机、运粮车两者的路径规划，模式动态且复杂，同时需要大量实时性数据，故忽略收割机路径规划，简化收割机与运粮车的响应复杂程度，实现运粮车整体的调度规划。

对收割机已知收割效率、收割周期等作业参数信息进行新状态的判断和预测，以及利用传感器等实时性传输设备的反馈和纠正获取收割机已收割量、作业时间等实时性信息。每个任务单元对应1台收割机，粮食满仓后，进行完全卸粮，完成响应后再进行下一轮作业。所有运粮车先前往最近的任务单元进行响应，响应结束后再抵达下个任务单元，最大化减少收割机非生产性作业时间[4](收割机未收割情况下在田间的等待时间)。每个任务单元可以由多个运辆车同时到达，以保证收割机收满后进行完全卸粮作业。

本研究基于任务单元的收、运响应调度模式，对模型做出如下假设：所有任务单元的机械设备作业参数相同，且作业过程中无故障发生；收割机连续作业至满仓，完全卸粮后再进行下次作业；运粮车达到满载，才能返回卸粮站，再进行下次分配；运粮车运输抵达同一终点位置；忽略运粮车和收割机折旧费用、人工费用等生产性成本。

1.3 参数及变量说明

1)任务单元用集合U={Vi,ai} 表示，其中Vi={V1,V2,…,Vm}、ai={a1,a2,…,am} 分别表示任务单元位置、任务单元面积，i={1,2,…,m} 为任务单元编号，m为任务单元数量。

2)收割机与运粮车分别用集合Hi={H1,H2,…,Hm}、Tj={T1,T2,…,Tn} 表示，其中i={1,2,…,m} 为任务单元编号；n为运粮车数量，j={1,2,…,n} 为运粮车编号；令CH表示收割机容量，CT表示运粮车容量。

3)定义集合P={Vp,dgh} 表示路网中各路径节点路径信息。其中运粮车分配节点的位置Vp=V0∪Vi，V0表示卸粮站，Vi表示任务单元位置；dgh表示节点g到h之间的距离，g∈Vp,h∈Vp。

1.4 时间槽定义

本研究基于每个任务单元的整体起止时间，进行时间槽划分。时间槽是指单个任务单元收割作业周期，该周期包含收割机满仓前的收割状态和满仓后的卸粮响应状态，是2个状态时间段的总合。划分依据是任务单元中收割机的作业周期，数目与收割机的收割总次数Ki相同，计算公式为：

(1)

式中：ai表示i任务单元的收获面积；λ是作物面积转化为产量的单位系数；λai表示该任务单元总产量。i任务单元含有Ki个时间槽表示该任务单元必须被收割λai/CH(向上取整)次，才能完全收获完毕。任务单元最后一次收割时需完全卸粮，保证离开该任务单元的收割机粮仓处于全空状态，能够满足任务单元作业结束后自由转移的需要。

(2)

分别表示收割机的开始收割时间、满仓时间、卸粮结束时间，分别表示运粮车到达时间、开始时间、结束时间；为收割机收割作业时间，为运粮车卸粮响应时间；k,i,j分别为时间槽、收割机、运粮车序号。 is time for unloading of grain by grain truck； k, i and j are the serial numbers of time slot, harvester and grain truck, respectively.图1 运粮车与收割机响应时间状态Fig.1 Response time status of grain trucks and harvester

(3)

1.5 响应模型的建立

1.5.1主要目标

基于任务单元的响应模式及相关影响因素分析，收运响应调度的非生产性总成本包含收割机等待时间成本、运粮车转移距离成本2部分。因此将模型分为2种具体目标，分别为收割机非生产性作业时间(等待时间)成本最小化和运粮车的转移距离成本最小化。

1)收割机非生产性作业时间成本最小化。模型目标数学表达式为：

(4)

2)运粮车转移距离成本最小化。模型目标数学表达式为：

(5)

式中：f2代表运粮车转移成本最小值；c2为运粮车单位距离成本。转移成本等于所有运粮车转移总距离与单位距离成本之积。

1.5.2主要约束条件

对运粮车收割机响应调度过程分析，工作量约束条件如下：

(6)

时间状态约束条件为：

(7)

2 运粮车与收割机响应模型的解算

2.1 解算基本原理

本研究首先考虑时间约束，在时间约束下完成有限次的调度决策。在作业期间内，将单个任务单元的整体起始时间切割成有限时间槽，每个时间槽根据当前状态完成1次调度决策。所有任务单元并行计算，最终完成所有单元的调度安排，获得完整的运粮车调度方案。

按照时间顺序依次完成各个时间槽的决策，最终完成整体解算，从而顺利解决时间和工作量约束的问题。每个时间槽在单独决策时，事先确定目标之间的相对重要程度，以此为依据将重要目标进行优先决策，次要目标随后决策，即多目标问题转化为2个单目标问题进行顺序求解。本研究将基于收割机非生产性时间为首要目标的动态时间槽算法记为 A，将基于运粮车运输距离为首要目标的动态时间槽算法记为 B。

2.2 算法构建

动态时间槽算法 A 中运粮车运输距离和收割机等待时间同时作为优化目标，决策中收割机等待时间处于更高优先级。具体分为针对单个任务单元的决策算法 A1和并行计算多个任务单元的算法 A2，简化步骤如下：

1)算法 A1。

步骤1：所有任务单元同时开始计算，每次迭代需更新时间集合T。每个任务单元都从第一个时间槽开始计算(k=1)。

步骤2：判断运粮车状态。将所有运粮车划分为等待分配和已分配状态。只有等待分配的运粮车才能参与各个任务单元的匹配。

步骤3：判断收割机状态。若该任务单元第k个时间槽下收割机处于卸粮未完成状态，直接执行算法A2；若收割机对应收割状态，进入下一步。

步骤4：优化分配。计算当前任务单元第k个时间槽剩余的收割作业时间，计算所有未分配运粮车到该任务单元的距离。执行算法A2。

步骤5：按照算法A2指定结果分配。若未能分配，则转入步骤3。

步骤6：判断该任务单元作业是否全部完成(k≥Ki)。若未完成，令k增加1后转入步骤1，再次循环。若完成，记录并结束该任务单元。

步骤7：若所有任务单元都被记录，结束算法A1。

2)算法A2。

步骤1：优先按时间分配。汇总当前所有单元收割机剩余收割时间，按照从小到大的顺序依次分配即将结束收割的任务单元。

步骤2：寻找运粮车。预算所有单元当前第k个时间槽需要的卸粮量，并与所有运粮车剩余载量比较，找出满足条件的运粮车。

步骤3：再次按距离分配。对步骤2满足载量条件的运粮车，取距离该任务单元位置最近的1个运粮车，直接执行步骤5。

步骤4：组合判断。步骤2中若无满足载重条件的运粮车，则将未参与的运粮车多个组合，直到满足；若全部不满足，则所有运粮车共同派往，并将该任务单元标记为分配优先级最高。

步骤5：结束A2，输出分配结果。

此外，本研究在算法A的基础上提出算法B，运粮车运输距离和收割机等待时间同时作为优化目标，决策中运粮车转移距离处于更高优先级。将算法A2中步骤1、3的优先分配规则互换，即可得算法 B。

3 运算分析

国家统计局2018年主要农作物产量统计年鉴数据显示，江苏省盐城市谷物小麦每1 hm2产粮5.827 t，即λ=5.827 t/hm2。根据江苏省常用品牌的收割机和运粮车参数，收割机粮容积为1.05～4.8 m3，本研究选用雷沃谷神GE80(4LZ-8E2)轮式谷物联合收割机，粮箱容积2.0 m3，容量1.6 t，即CH=1.6，收割效率0.533 hm2/h，数量为6辆。运粮车一般为拖拉机自带5～7 t容量的拖斗，本研究取值5 t，即CT=5，转移速率为30 km/h，数量为4辆。设置收割机单位等待时间成本为70 元/h(c1=70)；运粮车单位转移成本为4 元/h(c2=4)；响应卸粮速率为38 t/h。本次研究选取盐城市大有县6个农田作业点实际数据进行模拟，具体信息见表1。

表1 任务单元实际作业信息与时间槽数目Table 1 Actual operating data and number of time slots for work units

3.1 目标优化结果

3.1.1实际算例方案

算法A与算法B分别计算盐城大有县6个农田作业点的实际算例，得到2种不同结果的优化调度方案。方案呈现的收割机等待时间、运粮车转移距离及整体非生产性作业成本等目标优化结果见表2。

表2 算法A、B对实际案例的目标优化结果Table 2 Algorithm A and algorithm B optimize the objective results of the actual case

算法A得到此案例的方案在收割机等待时间上较少，算法 B得到运粮车转移距离较短，优化结果符合不同策略算法A、B的预期。基于多目标动态分割求解算法 A 产生方案中非生产性作业总成本较低，对该调度模型求解结果较好。因此本研究选择算法 A 作为该实例的求解算法，获得优化方案的调度响应甘特图(图2)与运粮车到访任务单元的路径顺序(表3)。

红色线框为收割机与运粮车实际卸粮响应时间,右侧数值表示到访的运粮车编号。The red line represents the unloading status. The value represents the number of the grain truck responding.图2 任务单元调度响应甘特图Fig.2 The scheduling response Gantt diagram for work units

表3 运粮车最佳路径顺序Table 3 Optimal path scheme for grain trucks to visit work units

3.1.2仿真算例运算分析

为比较不同优先决策顺序的算法A、B性能差异，本研究随机生成8 组仿真算例，对非生产性作业总成本、运粮车转移距离和收割机等待时间进行对比分析。每组算例包含6 个任务单元，每个任务单元面积范围为0.33～1 hm2，单元间节点距离范围为0.3～2 km。算法A、B计算每组算例得到的目标优化结果见表4。可见: 算法 A 求解的目标优化结果中非生产性作业成本比B低2%～18%，收割机等待时间比B低10%～40%；算法A、B中运粮车转移距离值的差异范围在10%以内。算法B求解的某些转移距离大于A的原因是：算法B优先考虑运粮车转移距离，会使运粮车集中于较近单元，最后完成距离较远单元任务时，容量已无法满足卸粮需要，需多辆共同前往，导致运粮车转移总距离反而增加。

表4 算法A、B对仿真算例的目标优化结果Table 4 Comparison between two algorithms with 8 sets of work units

因此，决策优先考虑等待时间的算法A总体上优于优先考虑转移距离的算法B。

3.2 影响因素分析

以算法 A 为运粮车和收割机响应调度模型的优化算法，进行影响因素仿真试验。

除了任务单元和运粮车数量以外，响应调度模型还包括收割效率、卸粮速率以及收割机粮仓容量和运粮车载量等作业参数。收割机卸粮较快，卸粮时间相对于收割作业周期可以忽略；收割机粮仓容积与收割效率均通过影响收割机收割作业周期长短进而影响优化结果，作用效果相似。因此本研究选择收割机、运粮车数量配比以及收割效率作业参数，探究其对模型性能的影响。

3.2.1运粮车与收割机数量配比的影响

本研究固定6台收割机(任务单元)，选择运粮车数量为1～6辆(收运数量配比1∶1～6∶1)。对每组任务单元算例(随机生成6 个任务单元数据，单元面积范围为0.33～1 hm2，单元间节点距离范围为0.3～2 km)进行求解，运行结果见图3。

由图3可知，在收割机数量固定且多于运粮车的情况下，随着运粮车数量不断增加，收割机非生产性作业平均成本、平均等待时间以及单个运粮车的平均转移路程均不断下降，总成本、总等待时间都随着运粮车增加而不断下降。当运粮车数量为4～6辆(收运配比范围在1∶1～2∶1)时，每台收割机非生产性平均等待时间均在0.05 h以内，优化效果良好(图3(b))。固定6个任务单元情况下，服务组织配置6辆运粮车与配置1辆运粮车相比，非生产性总成本、平均等待时间和转移距离减少较为显著，增益较大。服务组织配置6辆运粮车与配置4辆运粮车相比，减少的平均等待时间与转移距离减少幅度不明显，运粮车数量增加对非生产性总成本的降低不明显，增大了对运输设备资源的占用，即收、运数量相近时提高运粮车数量带来增益减小。

图3 运粮车数量变化对目标优化结果的影响Fig.3 Influence of the quantity change of grain cart on the optimization results

因此在实际情况下服务组织选择4辆运粮车能取得较好的优化结果，并节约运粮车数量。尤其是对比当前大型农场运粮车冗余配置的情况，本研究内容对节约运粮车资源具有一定的指导意义。

同时，固定运粮车4辆，任务单元(或收割机)数量变化(4～20)，得到如下结论：在运粮车数辆固定且少于收割机的情况下，随着收割机数量增加，平均非生产性作业成本和平均等待时间呈上升趋势，总路程、等待时间和非生产性总成本也随之增加，趋势明显。即当运粮车数量不足时，盲目增加收割机数量，会导致单个收割机的平均等待时间、非生产性作业成本和运粮车平均转移路程增加，且收割机数量越多，各指标增加趋势更加显著。

3.2.2收割效率对模型的影响

研究模型以收割机等待时间、运粮车转移距离为目标。为证明该目标模型的有效性，设计1种常见的单目标(仅考虑最优等待时间)模型，产生方案与多目标模型方案优化结果进行对比。选择收割效率0.13～0.80 hm2/h，固定其他参数，探究收运配比为3∶2(收割机6辆，运粮车4辆)条件下收割效率对2种调度模型的影响，结果见图4。

由图4可知，当收割效率小于0.53 hm2/h，2种模式下数据重合，即方案规划相同，等待时间、转移路径相同。当效率大于0.53 hm2/h，2种模式呈现差异：同时考虑等待时间与转移距离的多目标模型产生方案中，随着收割效率增加，运粮车转移路径不再变化(图4(b))；单目标传统模型产生方案中，等待时间、转移距离、非生产性成本均随收割效率增加而增大。可以判断，多目标模型在收割效率大于0.53 hm2/h后优于传统单目标模型，本研究建立多目标模型的有效性得以证实。

收割效率小于0.53 hm2/h时，等待时间最短和转移路程最小(图4(a)、(b))；当收割效率小于0.40 hm2/h 时，2种模式下收割机等待时间与运粮车转移距离均可以达到最优(图4(c))，使得非生产性成本最低。收割效率超过0.53 hm2/h时，最优等待时间逐渐增加，原因是随着收割效率增加，收割作业完成较快，留给运粮车自由支配的转移时间相对减少，因此总体上收割机等待时间增加。运粮车总转移距离在0.40 hm2/h效率时开始增加，达到0.53 hm2/h以后，最优转移距离保持不变，原因是收割效率增加，但模型受运粮车数量制约，为降低收割机少量等待时间而造成运粮车转移距离显著增大，不符合最优非生产性成本的要求，即收割效率超过0.53 hm2/h，非生产性作业成本最优结果取决于转移距离是否最优，不再是等待时间。

图4 不同模型收割效率变化对目标优化结果的影响Fig.4 Influence of harvesting efficiency change on the target optimization results under different models

实际收获作业中，将收割效率控制在0.53 hm2/h以内，使得该配置下的收运响应效率最高，此范围内收割机等待时间最短，运粮车转移距离产生的影响最小。若考虑完工时间，选择0.53 hm2/h收割效率，能达到较佳作业状态；若不考虑完工时间，选择0.40 hm2/h收割效率，达到最优作业状态。

4 讨论与结论

实际收获作业过程中收割机与运粮车响应方式较多，如模式一：收、运响应过程中，收割机先装满粮仓，再完全卸出收取的粮食。模式二：收、运响应过程中，收割机装满粮仓，随后不用全部卸出，携带部分粮食进行下次作业。模式三：收、运响应过程中，收割机不用装满粮仓，但必须完全卸出所收粮食。模式四：收、运响应过程中，收割机不必装满粮仓，随后也不必完全卸出所收粮食。模式二适合于运粮车较少的场景；模式三适用于运粮车量冗余的场景；模式四中收割机能够自由根据运粮车剩余容量收割或卸载粮食，在运粮车抵达时直接卸粮，无论剩余直接返回作业，使运粮车和收割机减少等待时间、运粮车载量充分，达到了收割机与运粮车最佳状态。但是实现这种复杂的动态响应，全靠人工经验，难度较大，目前没有合适模型和算法进行实现。这3种模式共同点是收割机可以自由根据实际约束改变每次作业的收割量，在已知产量的作业区域中收割次数动态变化，增大了模型构建和解算难度。相比之下模式一更适合于规模数量稍大的收获任务，在1个任务单元内收割机收割次数固定，为模型和算法构建提供了便利，同时也比较符合实际生产场景。因此本研究以模式一构建收、运响应模型，定义任务单元，凭借单元产量获得收割次数，并根据收割频率划分时间槽，设计算法进行求解。

本研究提出基于任务单元的多目标规划模型，共同考虑收割机田间等待时间及运粮车距离远近的目标，以动态规划的思想划分时间槽，根据目标不同优先级顺序设计了算法 A 和算法 B，选择非生产性作业成本、运粮车调配路程和收割机非生产性等待时间等目标优化结果进行对比发现，优先考虑等待时间的算法 A 在非生产性总成本和等待时间等方面，均优于优先考虑运粮车距离的调度算法 B，因此采用算法 A 作为该调度模型的求解算法。该算法为解决运粮车不足和提高资源配置效率提供了一种解决方案。同时，具体探究了特定型号(收、运容量分别为1.6和5.0 t；收、运数量配比为3∶2；收割效率为0.53 hm2/h)收割机与运粮车响应调度，获得该场景下任务单元响应甘特图与运粮车精确路径顺序(图2，表3)。

运粮车资源不足的情况下，运粮车数量与收割机数量相差显著时，运粮车转移距离和收割机等待时间显著增加。两者数量相近时，运粮车数量变化产生的总成本基本不变，增益减小，与配置6 辆运粮车相比，服务组织配置4 辆运粮车也能取得较好响应结果，同时节约运粮车设备资源。进一步研究发现，收、运数量配比为3∶2情况下，应保持0.40 hm2/h，获得该配置下最优响应作业效率，使等待时间最短、转移距离最小、非生产性成本最低。对于其他型号的收割机和运粮车，若提供收、运的容量以及数量配比等参数，能得出对应条件下的具体结论，获得最优响应方案和作业效率。因此该模型和算法能够为运粮车不足问题提供一定的指导意义。

本研究模型创新之处在于引入了收、运响应机制，更符合田间实际作业情况。但由于运粮车到达时间、载量不断变化，设计算法在处理更大规模数据时无法收敛，适用算法需进一步研究；同时模型仅考虑运粮车，未涉及收割机精确调度规划，针对收割机与运粮车的两级调度研究和增加对任务单元改变的动态规划研究是未来智能农机调度领域的重要研究方向。