基于遗传变邻域搜索算法的农机跨区调度优化研究

曹光乔 马 斌,2 陈 聪 任保鑫,2 胡朝中

(1.农业农村部南京农业机械化研究所, 南京 210014; 2.中国农业科学院研究生院, 北京 100081)

0 引言

随着我国新型生产经营主体不断涌现,规模化经营等现代农业生产模式开始兴起,从而带动对农机社会化服务等需求的增加[1-3]。在我国,大多数地区的耕地呈现碎片化的地理分布,零散农户仍是农业生产主体。农民的收入很大程度上取决于农产品的产量和市场价格,农机的按需使用能够帮助农户提高作物产量和收入[4]。然而,农业机械价格昂贵,小农难以负担,通常只有拥有较多田地的农户才会购买农机以满足作物收获需求[5]。在农忙时节,采用收获机跨区作业这种“共享农机”模式是为零散农户提供按需和低成本服务最有效的方法。

小麦是近一半亚洲地区居民的主要粮食来源,在我国,小麦产量超过全国粮食产量的1/5[6-7]。小麦成熟期因地理位置不同而具有差异,导致小麦收获机随作物成熟期自南向北跨区迁徙作业[8],因此农机跨区调度具有很强的时空演化特征和资源约束特征[9-11]。目前农机跨区调度多凭借人为经验,调度计划缺乏基于作物成熟期的合理规划,存在作业区域顺序混乱、农机资源配置不合理等问题,造成作业效率低下,贻误农时,降低了作物的收获产量和质量[12]。因此,基于“三夏”(夏收、夏种、夏管)时节农机跨区作业需求,研究多约束条件下农机资源配置问题对提高收获机跨区作业效率、保障作业质量具有重要意义。

近年来,学者从不同角度对农机调度问题进行了大量的研究,他们大都把农机调度问题转化为带时间窗的VRP问题或运筹学中的运输问题[13]。目前研究热点多集中在单个任务或小区域调度,通常情况下只考虑一个农机供应点或同种类型的农机,在农机调度研究中常用的调度优化目标包括:最大作业收益、最小调度总成本、最小调度路程等[14-16]。农机调度问题属于NP-hard难题,遇到大型计算实例时,NP-hard问题无法在有效时间内得到解决,常使用启发式算法进行求解[17-18]。例如文献[19]将模拟退火算法、遗传算法和混合Petri网络模型相结合,提出了一种两阶段的元启发式算法用于求解甘蔗生产收获的资源分配调度模型,并获得了较高的资源利用率。文献[20]以最小化农机工作时间为目标,提出了一种规划方法确定生物质收获和加工操作的顺序,解决了多领域生物质顺序处理的调度问题。文献[21]以收获机服务总面积最大为目标,提出的ALNS元启发式算法解决了带时间窗的甘蔗收获机械的调度问题。文献[22]分析了农机调度的各种成本,以总调度成本最低建立了重大疫情情况下的农机调度模型,并改进模拟退火算法对模型进行求解。

上述研究都聚焦在区域内的田间路径优化问题上,在农忙季节,农户作业需求往往来自不同的省、市、县,空间跨度从几十千米到几百千米不等,多种农机在空间大尺度下的规模化跨区调度更能满足农业生产需求。在农机跨区调度上,已有一部分研究,例如文献[23]建立了以调配成本和损失最小为目标的农机跨区作业紧急调配模型,并提出两种算法求解。文献[24]通过改进的非支配邻域搜索算法和禁忌搜索算法解决了农机静态分区和动态跨区协同调度问题。文献[25]考虑多库、多机型和作业时间窗等因素,对农机跨区作业进行研究,提高了服务的准时率和农机的使用率。

通过分析文献发现,现有的研究很少涉及农机车队作业,无论是小区域调度或大区域调度,很少考虑到作物的收获周期。事实上,空间大尺度下的农机跨区作业由若干台农机组成农机车队,当多台农机进行跨区作业时,要综合考虑调度距离、作物收获时间窗、农机利用率等因素,由于机械折旧费、路桥费等费用的存在,农机跨区作业的调度距离又会存在合理的范围[26]。近年来,带时间窗的车辆路径问题得到了广泛的拓展,其中解决绿色车辆路径问题是减少碳排放,实现“双碳”目标的重要手段,暂时尚未有研究在农机调度中考虑碳排放成本。如何在制定农机跨区调度计划时寻求社会经济效益最大化,同时推动绿色发展是一个值得探讨的问题。因此探讨多库、多机型、作业时间窗、空间距离等约束条件下的农机跨区作业资源配置问题,建立考虑碳排放的农机跨区调度模型,对保证粮食生产安全和促进碳中和具有重要意义。

本文针对“三夏”时节农机跨区调度的特点建立以最小调度成本为目标的跨区调度模型,同时考虑经济成本和环境成本,以期为农机跨区调度的管理决策提供依据。并提出一种遗传变邻域搜索算法(Genetic algorithm variable neighborhood search,GAVNS)求解模型,在该算法中,采用自适应机制对邻域权重进行动态调整,以期减少跨区调度成本。

1 问题描述与模型建立

1.1 问题描述

我国幅员辽阔,小麦作物由南向北依次成熟,这种规律为农机提供了一个连续的作业窗口,但我国的农机资源在地理空间上分布不均,在农忙时节,农户往往通过租赁外地的收获机服务来完成收获任务。通常,少量农户依赖社会信任和关系网络,往往基于经验数据,口头或电话传递需求信息给农机驾驶员以完成小麦的跨区机收作业,但这种模式过于依赖个人关系且调度效率低下,易造成资源和信息的不匹配。在大规模的农机调度中,农机合作社参与的调度模式是“三夏”时节完成小麦跨区机收的主要方式。在收获机跨区作业过程中,农户的作业需求往往来自不同的省、市、县,合作社收到包含农田类型、面积和位置等信息的作业订单后完成收获机的派遣。收获机通过卡车搭载成队列从合作社运输至待收区,完成收获作业,农机跨区调度网络如图1所示。

图1 农机跨区调度网络图Fig.1 Network diagram of agricultural machinery cross-region scheduling

该问题考虑多个合作社为多个小麦待收区提供收获机跨区作业服务,且每个合作社具有多数量、多机型的联合收获机。在建立模型之前,作以下假设:一个区县即为一个待收区;相同型号收获机的运输速率和工作效率相同,收获机从合作社运输到待收区仅存在公路运输一种方式,不考虑天气状况、道路拥堵情况,无道路容量限制;所有收获机与其运载卡车之间的比重相同;将收获机按型号分组,且每组收获机数量可能不同,分别运往不同区域;每个待收区只能由一个收获机组服务;农机合作社位置、待收区位置、待收区的待收获面积已知,一个待收区最多由一个合作社提供服务;收获机组到达待收区的时间即为开始收获时间;小麦在收获时间窗内的品质、产量恒定。

1.2 模型建立

基于以上问题描述,对模型建立中使用的集合、参数和决策变量定义如下:

(1)集合

I:待收区中出发区域集合,I={1,2,…,i}

J:待收区中到达区域集合,J={i+1,i+2,…,i+j}

M:农机合作社集合,M={1,2,…,m},M=I

V:收获机组集合,V={1,2,…,k}

A:待收区中节点集合,A={(i,j)|i∈I,j∈J}

(2)下标

i:待收区中的出发节点,i∈I

j:待收区中的到达节点,j∈J

k:收获机组型号,k∈V

(3)参数

qk:k型号收获机工作效率(hm2/h)

v:每台收获机转运速度(km/h)

ct:每台收获机单位距离运输成本(元/km)

wa:每个操作员时薪(元/h)

eijk:卡车k在路段(i,j)上的碳排放率(kg/km)

twj:完成待收区j收获所需的工作时间(h)

tij:收获机从待收区i转运到待收区j所需时间(h)

tjk:收获机组k到达待收区j的时间(h)

Sj:待收区j的待收获面积(hm2)

dij:待收区i和j之间的距离(km)

T:每日可用工作时间(h)

Pc:碳交易价格(元/kg)

N:一个足够大的正整数

Ej:待收区j小麦开始收获时间

Lj:待收区j小麦收获结束时间

α:早到等待成本

β:晚到惩罚成本

(4)决策变量

该问题优化目标为调度成本C,包括收获机运输成本C1、车辆和人员固定成本C2、时间惩罚成本C3和碳排放成本C4。

收获机运输成本与路径长度呈正相关,运输成本为

(1)

车辆和人员固定成本主要由驾驶员工资构成,不考虑每台收获机在田间转运的时间损耗,固定成本为

(2)

时间惩罚成本与收获机到达待收区开始作业时间有关,时间惩罚成本为

(3)

碳排放成本与收获机转运途中燃油消耗密切相关,文献[27]对目前流行的油耗估算模型进行了详细的对比分析,考虑到收获机实际转运过程中的车辆特征、道路特征、车辆运行特征,采用MEET模型估算车辆碳排放量[28]。卡车k在路段(i,j)上的碳排放率(kg/km)为

(4)

其中:ε表示卡车空载且在坡度为0°以速度v行驶时的碳排放率,ω0～ω6为常数,根据卡车类型取值。碳排放率的载重修正因子为

(5)

其中:γ为卡车i在路段(i,j)上的实际载重与其容量的比值,χ0～χ7为常数,根据卡车类型取值。卡车k在路段(i,j)上的碳排放率(kg/km)为

(6)

在转运过程中收获机k的碳排放成本C4为

(7)

该问题构建的数学模型,目标函数为

(8)

(9)

(10)

(11)

(12)

(13)

(14)

(15)

(16)

(17)

(18)

Ej≤tjk+twj≤Lj(∀j∈J)

(19)

(20)

该模型的目标函数(8)表示最小经济成本与环境成本之和。其中,经济成本包括运输成本、固定人力成本和时间惩罚成本,环境成本包括碳排放成本。约束式(9)表示派出的收获机数小于或等于所有合作社的收获机总数。约束式(10)表示每个待收区必须且只能被一个收获机组服务一次,不允许多个收获机组服务同一个待收区。约束式(11)表示每一个待收区域只能由一个收获机组服务,不接受多个机组的多次服务。约束式(12)表示从合作社出发的收获机组在作业完成之后必须返回合作社。约束式(13)表示保证每个收获机组在完成作业后必须离开该地。约束式(14)表示保证合作社之间不进行收获机组的转运。约束式(15)表示禁止收获机组返回合作社后返回待收区。约束式(16)表示消除区域内环流。约束式(17)表示每日的作业时间和转运时间之和不超过规定的时间。约束 式(18) 表示收获机组从待收区i到待收区j的时间窗应满足的条件。约束式(19)表示收获机组到达待收区和完成作业需满足的时间窗。约束式(20)表示决策变量的取值范围。

2 模型解算

农机跨区调度问题属于NP-hard难题,采用精确算法求解大规模实例会出现运行时间长,难以求得最优解,现有的研究都倾向于采用智能优化算法求得近似最优解,如遗传算法、粒子群优化算法、变邻域搜索算法。遗传算法能够在解的空间进行全局搜索,且并行性高,变邻域搜索算法通过在当前解的邻域内搜索,可快速找到局部改进解,这种局部搜索能力使算法在每一步的迭代中逐渐改善解的质量,向更优解的方向前进。综合考虑模型决策变量定义域的规则性,提出遗传变邻域搜索算法(GAVNS)对较大规模的农机跨区调度问题进行求解。

2.1 算法流程

GAVNS算法流程如图2所示。首先生成基于当前参数组合的初始解,再执行选择、交叉操作,然后用邻域方法对当前解进行改进,最后,当满足终止条件时,输出最优解。GAVNS算法包括染色体编解码、初始解构造、遗传操作、随机扰动、自适应邻域选择、种群管理等。

图2 GAVNS算法流程图Fig.2 GAVNS algorithm flowchart

2.2 染色体编解码设计

根据农机合作社提供的跨区服务特点,采用正整数的编码方式。对染色体的编码,具体表示为:节点0表示农机合作社,其他节点表示待收区,染色体基因的数量等于待收区数量的3倍。染色体分为3层,在第1层中,所有节点根据待收区编号随机填充,第2层节点由随机选择的k型号收获机填充,第3层节点对应第2层填充的k型号收获机的派遣数量。染色体编码结构如图3所示。根据第2层的信息,k1型号的收获机依次为待收区3、2、5、7服务。

图3 染色体编码方式Fig.3 Chromosome encoding method

2.3 初始解构造

为构造初始解,首先将每个待收区j按距离分配到最近的农机合作社m,然后在每个农机合作社覆盖的待收区内,将所有待收区根据其时间窗的中心值(Ej+Lj)/2进行排序,如果新增加一个待收区后不再满足模型约束条件,则将该待收区作为调度路径的首个区域划入到一条新的调度路径中,由此得到每个农机合作社的初始调度方案。虽然这种方法得到的目标函数值质量较差,但此种方法存在轻微的约束违规,使算法在较短时间内就能够完成初始解的构造。

2.4 评价函数

染色体适应度函数可以根据模型中目标函数式进行构造,个体评价函数f(x)为目标函数的倒数,公式为

(21)

式中C(x)——目标函数值

2.5 遗传操作

2.5.1选择操作

选择操作采用精英保留策略与轮盘赌相结合的选择策略。实现步骤为:先用精英保留策略将每一代种群中一定数量的最优染色体直接保存到下一代,再用轮盘赌的方式对剩下的染色体进行选择,每条染色体被选中的概率与其适应度成正比。

2.5.2交叉操作

在交叉操作中,顺序交叉既能保留原有排列基础,又能融合不同排列,故选用顺序交叉算子。如图4所示,从种群中选取一对父代个体1、2作为交叉对象,在父代个体1、2上随机选择两个基因交叉点形成交叉子路径。复制父代2中的交叉子路径置于父代1的最后面,同理,复制父代1中的交叉子路径置于父代2的最前面。最后删除路径中的重复基因,由此形成两个新的子代1、2。

图4 染色体交叉过程Fig.4 Chromosome crossover process

2.6 变邻域操作

2.6.1变邻域结构设计

使用交换、插入、2-Opt、or-Opt邻域算子进行变邻域搜索。交换算子是从当前解中随机选择两个不同的节点,交换两节点的位置。插入算子是从当前解中随机选择一个节点,将其插入到新的位置。2-Opt算子是从当前解中随机选择两个不同的节点i、j,并将节点i后的节点顺序进行逆转。or-Opt算子随机选择两个连续的节点,将其逆序插入到随机选择的节点j的后面。邻域结构示意图如图5所示。

图5 邻域结构示意图Fig.5 Neighborhood structure diagram

2.6.2随机扰动

首先设定邻域结构Ni={N1,N2,…,Nn},Nn表示第n个邻域结构,对种群中的个体c,随机选择一个邻域结构Ni开始扰动,来破坏当前解的局部最优解。在预设的邻域搜索次数内,尝试找到改进解c′,则令c=c′;若在该邻域结构Ni内未找到改进解c′,则随机选择下一个邻域结构Ni进行扰动,直到达到预设的搜索次数。通过增加搜索的多样性和跳出局部最优解的限制,从而扩展搜索范围,使目标函数有机会找到更优的解。这种机制能够有效提升算法的全局搜索能力并改善解的质量。

2.6.3自适应选择邻域方法

每次迭代中, 经过计算得到的新解有3种情况, 即新解优化了目标函数并成为新的局部最优解、新解没有优化但是被接受、新解没有优化且被舍弃。上述3种情况分别对应不同的分数,每个迭代周期结束后,邻域方法的权重根据迭代过程中的表现评分变化实现动态变化。首先对每种邻域方法Ni设置一个初始权重,初始权重均为1。然后,设置权重为1～5之间的整数。在每次搜索中,随机选择一种邻域方法,如果选择的邻域方法产生的解比当前最优解更好,则将该邻域的权重加1,最高可达到5。反之,如果没有找到更好的解决方案,则将该邻域方法的权重减1,最低可达到1。这种方法可以动态地调整邻域结构的权重,使搜索更加灵活和高效。

2.7 种群管理和停止准则

为提高整个种群的质量,每次迭代结束后,用最优个体替换最差个体,以维持种群大小一致性和多样性,这种机制能避免算法陷入早熟收敛的状态。在保证种群规模不变的前提下,首先构造新的个体作为初始解,再进行遗传操作,最后利用自适应变邻域搜索方法对其进行改进。

当达到最大允许迭代次数时,GAVNS算法停止迭代,求解过程终止。

3 案例分析

3.1 数据来源与收集

黄淮海平原是我国的小麦主要种植区,已有研究表明,每年5月开始,河南南部以及安徽北部等地是小麦联合收获机跨区作业的主要输出地,它们进行跨区作业的范围从几十千米到几百千米不等[8]。数值实验以河南省驻马店市为发散中心,选取周边72个小麦生产区县,根据实际调查情况和收集的相关实验数据对模型进行实例分析。各小麦生产区县的小麦种植面积来源于《中国农村统计年鉴》,假设每个区县2%的小麦种植面积需要收获机进行跨区作业服务,各区县地理位置已知,研究区位和各小麦生产区县需求信息如图6和表1所示。

表1 小麦生产区县需求信息Tab.1 Demand information of wheat production counties

图6 研究区位Fig.6 Investigation area

假设研究区域共有4个农机合作社,分布在4个不同的区县,每个区县有3种型号的收获机参与跨区作业,整个调度问题将对4个农机合作社周围的72个区县提供作业服务,操作员每个工作日的最大工作时间为10 h。农机合作社位置及拥有各型号收获机数量如表2所示。

表2 农机合作社位置及拥有各型号收获机数量Tab.2 Locations of agricultural machinery cooperatives and number of harvesters of each model owned

3.2 模型设置

数值实验采用Windows 10操作系统,CPU为i7-12700,模拟平台使用Matlab 2017a。经过反复测试,算法参数设置如下:最大迭代次数(MG)为700、种群数量(NP)为100、交叉概率(Pc)为0.9、最大邻域搜索次数(MS)为1 000。将相关数据和变量纳入构建的模型,对于同一实例,算例运行10次,10个目标值的平均值作为此实例的结果。在“三夏”时节,4个农机合作社分别收集到前期工单,假设每个型号的收获机都有待派遣的任务。表3给出了农机性能参数及相关运行费用。

表3 农机性能参数及相关运行费用Tab.3 Agricultural machinery performance parameters and associated operating costs

根据我国目前的碳交易价格,假设碳交易价格Pc为0.052 8元/kg,同时,参考文献[29-30],将计算碳排放成本公式中的参数设置如下:ω0=110、ω1=0、ω2=0、ω3=0.000 375、ω4=8 702、ω5=0、ω6=0,χ0=1.27、χ1=0.061 4、χ2=0、χ3=-0.001 1、χ4=-0.002 35、χ5=0、χ6=0、χ7=-1.33。

3.3 算例计算

3.3.1不同优化算法实验结果分析

为验证设计的遗传变邻域搜索算法(GAVNS)的有效性,基于相同环境另外编写求解该模型的遗传算法(Genetic algorithm, GA)、变邻域搜索算法(Variable neighborhood search, VNS),将GAVNS算法与GA算法、VNS算法进行对比实验,得到最终结果如表4所示,其对比迭代曲线如图7所示。

表4 闭合路径下3种算法求解结果对比Tab.4 Comparison of results obtained by three algorithms under closed-path mode

图7 闭合路径下3种算法迭代曲线Fig.7 Iteration curves for three algorithms under closed-path mode

从对比结果来看,在调度成本上,GAVNS算法求得的最优值更低,分别比GA算法和VNS算法少16.41%、11.15%,说明GAVNS算法对降低调度成本具有显著意义。在收获机使用数和碳排放成本上,GAVNS算法求得的完成作业任务需派出387台收获机,收获机使用数最少,最高减少6.20%;求得的碳排放成本为1.84×105元,优于GA算法和VNS算法,最高节约26.09%,说明GAVNS算法能有效提升每个农机合作社的收获机使用率,减少车辆碳排放,减少环境污染。从图7可知,调度成本随迭代次数的增加而降低,GAVNS算法求解模型的速度快于GA算法和VNS算法,在迭代次数增加至490次左右即可收敛至稳定值,得到最优解的迭代次数更低、收敛速度更快,说明该算法具有较好的收敛性和搜索能力。 GAVNS算法求得的惩罚时间更少,有效降低了麦收惩罚成本,为农忙时节麦收作业预留更多有效作业时间,对保障粮食作物按时收获具有可行性、合理性和有效性。

3.3.2不同调度模式的实验结果分析

(1)GAVNS算法在闭合路径下的调度分析

根据仿真实验所选区域跨区收获作业的实际情况,使用建立的调度模型和设计的求解方法进行收获机跨区调度仿真,在仿真实验中,所有参与跨区作业的收获机组的最优调度路径如图8所示,最优调度方案如表5所示。

表5 闭合路径调度模式的最优调度方案Tab.5 Optimal scheduling solution for closed-path scheduling mode

图8 闭合路径下的最优调度路径Fig.8 Optimal scheduling path under closed-path mode

从图8可知,农机合作社进行跨区作业服务时,优先就近服务,相邻位置的作业区域由同一个农机合作社提供服务。每个收获机组的路径清晰,不同路径间的迂回和交叉情况较少。

由表5可知,调度成本为3.231 8×106元,收获机总转运距离为1.66×105km,4个农机合作社均派出收获机组进行跨区作业服务,共使用387台收获机,每个合作社都有较高的农机利用率。4个农机合作社派出的收获机组数分别为4、5、6、3,每个机组都进行了多个区县的跨越,机收的小麦面积分别为3 695.41、4 851.55、6 517.45、3 815.23 hm2,同时每个合作社派出的收获机组具有一定的相似性,如收获面积、转运时间等,说明设计的GAVNS算法能够根据实际情况为合作社派出的收获机组规划合理的作业路线,分配适量的作业任务,保证跨区作业的准时性和均衡性。由式(6)可知,在不考虑收获机田间作业的油耗下,碳排放成本与转运距离存在正相关关系,每台收获机转运过程中每行驶1 km平均产生0.28 kg二氧化碳,转运过程中的燃油消耗会导致一定程度的大气污染,同时运输成本和碳排放成本占总调度成本的10.85%,在进行收获机跨区调度时,对收获机组的调度不仅要考虑经济成本,也要兼顾环境成本。

(2)GAVNS算法在开放路径下的调度分析

在实际的收获机跨区作业中,在小麦收获前期,为抢占农时,合作社派出的收获机往往在完成当前作业后不返回合作社,而是继续寻找下一个作业点,此时收获机跨区调度是一个开放的多库、多机型的车辆路径问题,在开放路径中,GAVNS算法的迭代曲线如图9所示,其最优调度方案如表6所示。

表6 开放路径调度模式的最优调度方案Tab.6 Optimal scheduling solution for open-path scheduling mode

图9 开放路径下GAVNS算法迭代曲线Fig.9 Iteration curves of GAVNS algorithm under open-path mode

由表6可知,在开放路径下,完成所有收获任务的调度成本为2.656 3×106元、转移距离为 1.112×105km, 相比闭合路径,调度成本、转移距离分别降低17.76%、33.02%,其主要原因是在开放路径中,不考虑每个合作社派出的收获机组的返回路径,减少了路径代价,具有较高的经济性。完成跨区收获共派出358台收获机,派遣的收获机数比闭合路径少7.49%,该模式能有效提升收获机的使用率,同时各收获机组存在收获面积和转运距离的偏差,说明收获机组的路径规划基本遵循了小麦待收区的时间窗、收获面积的变化规律。在开放路径下,碳排放成本为1.35×104元,较闭合路径降低26.63%,两种调度模式都验证了碳排放成本与转运距离存在正相关关系,在转运距离降低的情况下,碳排放成本也会减少,此种调度模式更有利于降低二氧化碳的排放,减少大气污染,推动低碳农业的发展。

4 结论

(1)为降低“三夏”时节收获机跨区调度成本,兼顾环境保护,本文构建合理的多库、多机型的农机跨区调度模型,设计遗传变邻域搜索算法(GAVNS)求解,通过黄淮海平原72个区县的实例证明模型与算法的有效性。

(2)计算结果表明,GAVNS算法的寻优策略在降低调度成本、转运距离和惩罚时间方面均具备优势,GAVNS算法求得的目标函数值较GA算法、VNS算法分别少16.41%、11.15%。对比两种农机跨区调度模式,开放路径不考虑收获机组的返回路径,农机合作社提供跨区作业服务的效率更高,相比闭合路径,转移距离减少33.02%,调度成本减少17.76%,具有更好的经济性。