天气变化情形下基于动态时间窗的收获机应急调度技术

汪浩祥 曹光乔 闫子彤 陈 聪

(1.南京农业大学信息管理学院, 南京 210031; 2.农业农村部南京农业机械化研究所, 南京 210014)

0 引言

随着我国现代化农业的发展,在农业生产中对突发情况的高效应对和处理是现代化农业发展的重要组成部分,农业生产中出现的应急调度问题也被越来越多的专家学者所关注和研究。例如,在小麦收获时期遇到降雨,农机合作社如果不及时对受影响的农田快速调度资源完成抢收工作,则会给农民造成巨大损失。

当前应急调度方面的研究主要集中在重大突发事件发生后资源的调配:如LE-ANH等[1]针对国内运输系统提出了一种动态车辆应急调度启发式方法,并验证了该方法的性能。ZENG等[2]对自然灾害发生时的应急资源调度问题进行了研究,以运输距离最短为目标,以最大行驶里程和最晚到达时间为约束条件建立模型,将蚁群算法和遗传算法相结合对模型进行求解。杨海强等[3]建立了应急车辆调度模型,又将遗传算法进行改进并求解。巩玲君等[4]研究了重大突发事件发生后应急物资生产任务的优化问题,赵明等[5]针对大规模灾难发生时首批生命物资的应急调度建模及优化求解问题进行了研究。

目前针对农机应急调度问题研究较少,主要有:刘卉等[6]提出了矢量缓冲区算法、栅格缓冲区算法来解决农机收获面积实时、精准的获取问题,并在全球卫星导航系统下对两种测量方法进行了验证。张璠等[7]提出了根据农田与车场距离,结合农机贡献度来确定农田任务排序的多对多的应急调度算法,解决农机应急调度问题。黄凰等[8]针对农田与农机的匹配与调度需求问题,综合考虑农户满意度、多农机站协同、订单数量、农田面积和位置坐标等因素,建立带有模糊时间窗并以调度总时长最小和调度农机数量最少为目标的多农机站即时响应调度数学模型。设计了基于保留优秀父代基因的改进遗传算法的农机调度系统,完成多农机站响应多农田的同时作业需求的任务。MA等[9]参考现有农机调度模式,结合农业生产的实际需求,基于资源共享的思想,将软时间窗和硬时间窗相结合,开展农机动态需求调度策略研究。HU等[10]提出了两阶段分析方法,将不同规划层次之间的数据连接起来,旨在建立农机机队维修服务的动态能力规划方法,降低维护服务商的运营成本。

在农机调度方面,吴才聪等[11]则通过构建农田收获的成本矩阵,通过匈牙利法分配收获车辆,实现在时间窗限制下车辆运输成本的最小化。王雪阳等[12-14]也研究了在时间窗限制下的农机调度问题,使用多种启发式算法对其最小运输距离进行求解,并且比较了这些启发式算法的优缺点。张帆等[15]针对农机装备跨区作业存在作业任务重、转移范围大、作业时效性强等问题,开展了基于改进遗传算法的多机协同作业任务调度方法研究。HE等[16]提出了一种面向零碎农田的联合收获获机最优调度操作模型。以联合收获获机间收获时间差异最小为约束条件,目标函数是小麦收获周期最小。WANG等[17]研究了一种结合操作员分配的收获机调度问题。通过确定收获机和操作员的组合以及收获机的路线,达到总工作时间和成本最小化的目标。然而,在农业实际生产活动中,大量的作业活动会受到降雨的影响[18]。特别在小麦收获过程中,因雨天小麦脱粒率会降低,所以收获机在雨天不能进行小麦收获作业,那么在小麦收获时期内有突如其来的天气变化,小麦的可作业时间窗会发生改变,若收获机还继续按原序列调度,可能会造成农田收获时间延迟等现象的发生。

本文拟将受雨天影响的农田设为应急农田,并重新根据应急度排序,且雨后时间窗为空的农田排在最前,设计基于改进遗传算法的收获机应急调度算法,通过动态改变原收获机收获路线,为应急农田优先提供收获服务,尽可能降低因天气突然变化给农户带来的损失。

1 问题描述与模型建立

1.1 问题描述

为方便问题描述,进行相关定义:

提前响应时间:为对应急农田优先调度的时间点,通常为可作业时间与下雨时间有重合的农田中最早的允许开始作业时间窗。

应急农田:应急农田包括两种,一种是可作业时间窗与下雨时间有重合的农田,另一种是在响应时间后、下雨前还未作业的农田。

由于响应时间到来时,可作业时间与下雨时间有交集的农田将会优先插入收获机序列应急调度,当应急农田作业结束后,在响应时间之后、下雨之前还未收获农田的可作业时间窗为0,所以这里也将响应时间后、下雨时间之前的还未收获农田也设为应急农田。如图1所示,其中,F2为在响应时间后下雨时间前还未收获的农田,F3、F4的可作业时间与下雨时间有重合,所以F2、F3、F4为应急农田,F1在响应时间前已完成作业,F5与下雨时间没有交集且不在响应时间后下雨事件前,都不属于应急农田。

图1 应急农田示意图Fig.1 Schematic of emergency farmland

应急度:为待收获农田面积和雨后时间窗的比值。

找出应急农田后计算这些农田的应急度,根据应急度定义,可作业时间窗与下雨时间段重合的农田中待收获面积越大且雨后时间窗越小,则该块农田的应急程度越高,雨后时间窗为零则排在最前,且按农田的开始可收获时间窗从早到晚排序。这样就可以在暴风雨到来前尽可能最大限度地收获应急程度高的农田,而相对面积小、雨后时间窗大的农田,可以放在雨后进行收获。如图1所示,农田F2雨后可作业时间窗为零排在最前,F3、F4按应急度排在后。

本文收获机应急调度问题可具体描述为:根据预报,在获知收获期的天气变化后,为应对因降雨对小麦收获的影响,减少损失,农机合作社的相关人员根据汇总的农户农田的相关信息和收获机的作业情况,确定提前响应时间和应急农田,当时间节点到达响应时间时,开始应急调度,先将应急农田从原序列中剔除,并搜索可使用收获机,因为在应急调度开始后,收获机需要先完成当前正在收获的农田,再去进行应急作业,所以需要剔除完成当前作业后,时间节点已经到达开始下雨时间的收获机。将排序好的应急农田按目标函数最优优先插入收获机原序列中,对收获机进行路线修正,优先调度应急农田。

本文以第一块农田的开始收获时间为时间轴零点,以最后一块农田的结束收获时间为1建立时间轴t,则该地区的整个收获时间为(0,1),设a、b、c、d∈(0,1)且a

表1 各个时间节点状态反应Tab.1 State response of each time node

1.2 数学模型

本文研究的是多个出发点与多个作业点即多对多模式的收获机调度问题,也就是根据农田的时间窗、作业面积、地理位置等因素,为多个车场中的收获机设计作业顺序的过程。首先,针对该收获机应急调度问题提出假设前提条件:

(1)假设收获机的作业能力和转移速度在单位时间内都是一样的,并且不受道路状况的影响。

(2)各收获机的作业能力可以完全满足作业点的需求。

(3)假设每块农田对收获机的需求类型仅有一种。

(4)在每一次调度过程中,每辆收获机只能被调度一次,且完成作业后返回原出发车场。

(5)在每次调度过程中,每辆被调度的收获机至少作业一个农田,即保证每次调度可靠性。

(6)假设每块农田仅能被一辆收获机访问。

(7)不考虑道路堵塞等一些特殊路况的发生。

(8)假设收获机从车场到达农田作业点所经过的路径是两点之间的最短路径。

(9)假设下雨时间可精准预测。

本文建立因天气变化导致的时间窗变动的收获机调度模型,综合考虑收获机转移时间、提前到达等待时间、延迟时间,以及应急调度中收获机转移时间、应急农田延迟时间、原序列农田偏离时间等,并依据该模型假设条件的前提下,建立收获机调度多目标数学模型。

设该区域的农田收获时间窗为(0,1),a、b、c、d∈(0,1)且a

(1)确定目标函数

在收获机应急调度中包括两方面的成本,又因在功率相同的情况下,成本只与时间有关,所以此模型只考虑时间。一方面是收获机调度涉及到的收获机转移时间、提前到达等待或延迟时间,另一方面是应急农田分配时收获机转移时间最小、应急作业拖延时间最小及农田收获的偏离时间最小。

minZ=(1-θ)Z1+θZ2

(1)

其中

(2)

(3)

式中M——收获机场站个数

K——收获机总台数

N——农田总数

Qm——第m个车场拥有的车辆数目,m∈{1,2,…,M}

i、j——农田编号,i,j∈{1,2,…,N},i≠j

Ei——第i块农田允许开始的最早时间

Li——第i块农田允许结束的最晚时间

li——第i块农田的实际完成作业时间

ri——收获机到达第i块农田的时间

r′i——修正路线后收获机到达第i块农田的时间

θ——条件变量

公式(2)表示初始收获机调度涉及到的收获机转移时间、提前到达等待时间和总延迟时间,公式(3)是应急农田分配时收获机转移时间、应急农田作业拖延时间和农田收获的偏离时间。如式(1)所示,当时间窗为(0,b)时,此时没有发生应急调度,计算目标函数为收获机转移时间、提前等待或延迟时间最小;当时间窗为(b,1)时,触发应急调度,此时计算目标函数为应急农田分配时收获机转移时间最小、应急作业拖延时间最小及农田收获的偏离时间最小。

(2)约束条件

根据本文假设及问题描述,模型存在约束

(4)

(5)

(6)

(7)

(8)

(9)

ei≤Ei(i∈{1,2,…,N})

(10)

(11)

(12)

ei——第i块农田的实际开始作业时间

t——时间状态

公式(4)表示每个收获机服务站能够调出的收获机数量,须小于等于该车场拥有的收获机数量;公式(5)表示每个车场中发出的收获机在完成相应的作业任务后返回原车场;公式(6)、(7)表示每个农田作业点被访问次数与所需收获机数相等;公式(8)表示确保发生应急调度时,车辆从它所在的农田出发;公式(9)表示流量守恒定律,即收获机到达某节点后需保证离开该点;公式(10)表示农田必须在开始时间窗之后才能开始作业时间;公式(11)、(12)表示条件变量。

2 基于改进遗传算法的收获机应急调度算法

基于上述模型,本文将遗传算法计算步骤中的编码模块进行改进,提出了两级分阶段染色体编码方式;对遗传操作中的选择算子,使用轮盘赌注方法选择最佳个体;对于交叉算子,提出单个染色体指定位置交叉来降低不可行解的数量,使遗传算法更适用于本文模型。

2.1 两级多段编码方式

两级多段编码方式的实现主要分为3个步骤:首先,根据农田的可作业时间窗,按照允许开始作业时间的先后进行排序作为第1级编码;其次将排好序的农田所需的车场及车辆编码作为第2级;最后,将第2级编码按第1级排序先后进行连接组合,构成完整的染色体编码。

2.1.1一级编码

根据农田的开始作业时间窗的先后进行排序,这样可以表示出不同农田作业时间的串并问题,按排序先后作业串行的农田,并行的农田并行作业。假设某区域有n块农田,将n块农田按照可作业时间窗进行排序,如图2所示。

图2 一级编码Fig.2 First level coding

农田排序方法:根据农田作业点的可作业时间窗将农田按照从早到晚排序。假设农田F1和农田F2的可作业时间窗为[E1,L1]和[E2,L2],当[E1,L1]∩[E2,L2]等于空集时,农田F1和农田F2不存在并行任务,且农田可作业时间窗允许开始时间早的农田作业点排序在前;若[E1,L1]∩[E2,L2]≠∅且[E1,L1]≠[E2,L2]时,说明农田F1和农田F2时间窗存在交集,这里规定为允许开始时间早的农田排序在前,若允许开始时间相同,则允许最晚结束时间最早的排序在前;若[E1,L1]=[E2,L2],说明两农田作业点允许开始作业时间和最晚结束作业时间窗全部相同,规定为并行任务且并行执行。定义并行任务的思想为:首先将农田作业点按时间窗先后从早到晚排序,排序最前的农田作业点的序列号为1,按照排序顺序依次取作业点农田i与农田i+1进行判断是否为并行任务,若是,则两农田序列号相同,若不是,序列号加1,按照排序依次判断到最后一个作业点,序列号越小的农田越优先作业。

2.1.2二级编码

二级编码由分配到农田的车场编号与收获机编号组成,则每块农田由2个编号组合而成,如图3所示第i块农田编码,Im表示第i块农田的车场编码,Ikm表示第i块农田第m个车场编号为k的收获机编码。

图3 二级编码Fig.3 Second level coding

2.1.3两级编码连接

将两级编码连接起来,构成完整的染色体,即将所有农田二级编码按照一级农田排序连接起来,如图4所示。

图4 两级编码连接Fig.4 Code linkage of two levels

2.2 遗传操作设计

2.2.1适应度函数

遗传算法在搜索进化过程中一般不需要其他外部信息,仅用评估函数来评估个体或解的优劣,并作为以后遗传操作的依据,个体被遗传的概率与其适值是成正比的,所以适应度函数设计直接影响到遗传算法的性能。本文使用最小路径倒数作为适应度函数。

2.2.2选择

本文通过轮盘赌方法选择算子,基于优胜劣汰的思想。根据染色体的适应度值选择算子,个体被选择的概率与其适应度成正比,算法主要流程如下:

(1)通过计算种群(i=1,2,…,M)个体染色体适应度与总适应度之比得出选择概率,适应度函数为

(13)

适应度函数越大,个体被选择的概率越大。

(2)计算个体累计概率,染色体x[i]的累计概率为

(14)

2.2.3交叉

将收获机调度问题与染色体编码结合起来进行考虑染色体交叉方式的设计。本文将基本遗传算法的交叉方式进行改进,采用单点交叉方式,这样有利于减少不可行解的数量。

本文用5块农田的收获机调度来简单举例说明交叉方式,如图5a取任意两条染色体作为父代:p(3 2 2 2 1 2 3 2 3 1)、q(2 2 3 3 3 3 1 2 2 2),随机产生一个[0,1]之间的数,如果该数小于自适应交叉概率Pc,则两个染色体进行交叉操作,否则继续产生随机数判断之后的染色体是否交叉。根据编码方式可知有意义的交叉点为{2,4,6,8},在这些可交叉点中随机搜索一个交叉点,假设生成的交叉点为4,如图5b,则分别在两个父代染色体第4位后进行交叉变换,得到两个子代染色体结果为:p′(3 2 2 2 3 3 1 2 2 2)、q′(2 2 3 3 1 2 3 2 3 1),如图5c。最后将交叉后的群体S复制到S1中继续进行后续操作。

图5 p,q两条染色体交叉示意图Fig.5 Crossing two chromosomes p,q

2.2.4变异

为了进一步加强对未知空间的搜索,遗传算法的变异操作在遗传操作中占据非常重要的位置。区别于二进制编码的变异操作,本文使用的是自然数编码,变异在染色体某个基因值即Im、Ikm中随机产生,产生概率为自适应变异率PM,即随机选取的一个[0,1]之间的数值,若该随机数小于自适应变异率PM,则进行变异操作。用上述例子说明变异方式:如图6a,随机取交叉后的两条染色体p′(3 2 2 2 3 3 1 2 2 2)、q′(2 2 3 3 1 2 3 2 3 1)作为父代染色体,假设随机搜索的变异点为1和3处,如图6b,那么需要将两条父代染色体的第1位和第3位进行交换来进行变异操作,结果为p″(2 2 3 2 3 3 1 2 2 2)、q″(3 2 2 3 1 2 3 2 3 1),如图6c。最后将变异后的群体S1复制到S2中继续进行后续操作。

图6 染色体p′、q′变异示意图Fig.6 Schematic diagram of chromosome p′、q′ variation

3 算法仿真

3.1 算例描述

河北省石家庄市正定县南楼乡东里双村(114.69°E,38.27°N)位于华北平原,地势平缓,东南距县城17 km,距乡政府8 km。是一个以种植为主的农业村,其主要种植作物为小麦。该区域农田地图如图7所示。

图7 研究区示意图Fig.7 Schematic of study area

该村小麦收获主要依靠现有一个农业机械合作社,在小麦收获季节到来时,合作社工作人员根据经验来调度小麦收获机进行作业,该村农田基本上为散户,小麦种植时间虽然季节上没有差异,但具体种植时间和小麦品种还是有差异,做不到完全一致,但是由于人工调度缺乏科学合理性,经常会有农户农田因收获机供应不足而延迟收获,给农户带来很大的损失。

根据实际调查可知东里双村小麦收获期大约在6月9—20日之间,若该年夏季风较强,华北平原将进入雨季,对该区域的小麦收获期造成影响。该村在2018年小麦收获期遭遇了暴风雨天气,在2018年6月12日10时突然预报小麦收获期13日4时至14日0时要下雨。同样,以该村最南面的农田建立横坐标,以该村最西面的农田建立纵坐标,以6月9日0时为零点建立时间轴,且以小时为单位,农田、车场信息如表2、3所示。

农业机械合作社在东里双村,共设有3个车场用来停放收获机,每个车场拥有3辆收获机,参考实际情况,设定收获机各项参数如表3所示。

表3 收获机参数设置Tab.3 Harvester parameters

收获机场站个数M为3,车场K1、K2、K3拥有收获机数量为3台。

3.2 算法步骤

该区域小麦收获期时间窗为[0,300 h],根据预报下雨时间令RainTime=[100,120],确定提前反应时间Reaction=15,也就是应急调度时间段为[85,100],则在这段时间内需要根据收获机修正后的路线,将应急农田优先调度。

算法步骤设计如下:

(1)计算农田间及车场与农田间的距离,按农田时间窗先后生成农田作业序列,按目标函数最优原则对每块农田进行车辆分配,生成调度方案t时刻,并计算各个农田的收获机到达时间与完成时间,令t=0。

(2)执行调度方案t时刻,t=t+1。

(3)判断t=a?是则设置b值并继续;否则转步骤(2)。

(4)执行调度方案t时刻,t=t+1。

(5)判断t=b?是则继续;否则转步骤(4)。

(6)生成应急农田序列,生成执行完当前任务时间点在(b,c)内的可应急调度的收获机序列,并获取位置,计算应急农田间及收获机到应急农田的距离,按目标函数最优原则将应急农田分配到每辆可应急调度的收获机,修正收获机路线,更新调度方案t时刻。

(7)执行调度方案t时刻,t=t+1。

(8)判断t=c?是则继续;否则转步骤(7)。

(9)停止作业,t=t+1。

(10)判断t=d?是则继续;否则转步骤(9)。

(11)继续执行调度方案t时刻,t=t+1。

(12)判断t=1?是则继续;否则转步骤(11)。

(13)结束。

3.3 运行结果

设置RainTime=[100,120]和Reaction=15后运行,可得到需应急调度的农田排序为45、14、24、25、17、36、27、41,总面积为63 333.65 m2,将这些农田设置为应急农田,将该实例问题运行10次,结果如表4所示。

表4 仿真运行结果Tab.4 Instance run results

按照实际情况及本文调度目标,农机合作社将选择一个成本最低且延迟时间最小的方案作为收获机调度方案,查看表4可以发现该模型第7次求解的总时长最低且无延迟,可以选取该次求解结果作为初始配送方案。

该次运行结果的各个收获机的路径如表5所示。应急农田的收获机分配结果如表6所示。

表5 收获机作业路径Tab.5 Operation path of harvester

表6 应急农田收获机分配结果Tab.6 Results of emergency farm harvester distribution

为方便计算机仿真,表5、6中收获机路线和应急农田为结点编号,农田编号为结点编号减3。为此,从表5和表6可看出,需要应急调度的农田编号为45、14、24、25、17、36、27和41,分别由2号车场编号为3的收获机、3号车场编号为3的收获机、1号车场编号为1的收获机、3号车场编号为2的收获机、2号车场编号为2的收获机、3号车场编号为1的收获机、2号车场编号为1的收获机、1号车场编号为3的收获机派去执行应急作业。

收获机调度路径图如图8所示。其中横、纵坐标分别表示起点出发正南和正西方向。

图8 收获机调度路径图Fig.8 Scheduling path of harvester

4 结束语

研究了天气变化引起的农田时间窗变动的收获机应急调度问题,建立了因天气变化导致的时间窗动态变动的收获机调度模型,综合考虑收获机转移时间、提前到达等待时间、延迟时间,以及应急调度中收获机转移时间、应急农田延迟时间、原序列农田偏离时间等,建立收获机调度多目标数学模型。设计了改进遗传算法对模型进行求解,并通过选取实例进行仿真,结果表明,在农作物收获时期,通过本文对天气变化导致的农田时间窗变动的应急调度问题的研究,可避免或降低因天气变化给农户带来的损失。