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

2023年10 月第54卷第10 期农报业机械doi:10.6041/j.issn.1000-1298.2023.10.010基于遗传变邻域搜索算法的农机跨区调度优化研究曹光乔11马斌.2陈聪1任保鑫1，2胡朝中！（1.农业农村部南京农业机械化研究所，南京2 10 0 14；2.中国农业科学院研究生院，北京10 0 0 8 1）摘要：智慧农业的快速发展促使多区域互联农机的调度追求更高的实时性，为更合理配置农机资源，农机跨区作业已成为完成“三夏”机收任务的主要服务模式。基于小麦收获机跨区作业真实场景，研究了带时间窗的多库、多机型的农机跨区调度问题，同时考虑经济成本和环境成本，建立以最小调度成本为目标的跨区调度模型。根据问题特征，设计遗传变邻域搜索算法（Geneticalgorithmvariableneighborhoodsearch，G A VNS），该方法通过交叉、随机扰动、自适应邻域选择等操作，使解的搜索更加高效和灵活。对我国黄准海平原7 2 个小麦生产区县的作业需求进行计算与分析：不同算法相比，本文设计的算法得到最优解的送代次数更低、收敛速度更快，求得的目标函数值较遗传算法、变邻域搜索算法分别降低16.41%、11.15%；对比不同调度模式，开放路径模式更有利于提升跨区调度服务效率，较闭合路径模式，调度成本降低17.7 6%。关键词：农业机械；时间窗；跨区调度；遗传变邻域搜索算法中图分类号：S11*5；S2 3 1文献标识码：A文章编号：10 0 0-12 98（2 0 2 3）10-0 114-10OSID:Agricultural Machinery Cross-region Scheduling Optimization Based onGenetic Algorithm Variable Neighborhood SearchCAo GuangqiaoMA Bin.2CHEN CongREN Baoxinl.2HU Chaozhong(1.Nanjing Institute of Agricultural Mechanization,Ministry of Agriculture and Rural Affairs,Nanjing 210014,China2.Graduate School of Chinese Academy of Agricultural Sciences,Beijing 100081,China)Abstract:In recent years,the rapid advancement of smart agriculture has spurred the pursuit of higherreal-time scheduling for inter-connected agricultural machinery across multiple regions.This approachaims to achieve more reasonable allocation of agricultural machinery resources.Cross-regional agriculturalmachinery operations have emerged as the principal service mode for completing the tasks of the“threesummer harvest.Drawing from real-world scenarios of cross-regional wheat harvesting machineryoperations,the cross-regional scheduling problem involving multiple depots and machinery types wasinvestigated,incorporating time windows.Economic and environmental costs were simultaneouslyconsidered,leading to the establishment of a cross-regional scheduling model with the objective ofminimizing scheduling costs.Tailored to the characteristics of the problem,a genetic algorithm variableneighborhood search（G A VNS)w a s d e s i g n e d.T h i s a l g o r i t h m e n h a n c e d e f f i c i e n c y a n d f l e x i b i l i t y i nsolution search through operations like crossover,random perturbations,and adaptive neighborhoodselection.The operational demands of 72 wheat-producing counties in the Huang-Huai-Hai Plain inChina were computed and analyzed.Comparative analysis revealed that the proposed algorithmoutperformed alternative algorithms in terms of reduced iteration count to reach the optimal solution andfaster convergence speed,with 16.41%decrease compared with the genetic algorithm and 11.15%decrease compared with the variable neighborhood search algorithm in terms of the objective functionvalue.Furthermore,different scheduling modes were compared,highlighting the open path mode as moreconducive to enhancing cross-regional scheduling service efficiency,leading to 17.76%reduction inscheduling costs compared with the closed path mode.Key words:agricultural machinery;time window;cross-region scheduling;genetic algorithm variableneighborhood search收稿日期：2 0 2 3-0 7-11修回日期：2 0 2 3-0 8-0 2基金项目：中国农业科学院科技创新工程项目（农科院办（2 0 14）2 16 号）和中国农业科学院基本科研业务费专项（S202215）作者简介：曹光乔（197 8 一），男，研究员，博士，主要从事农业机械化管理工程研究，E-mail：c a o g u a n g q i a o 12 6.c o m通信作者：陈聪（198 6 一），男，助理研究员，主要从事农机运维管理信息化研究，E-mail：c h e n c h o n g 52 0 2 0 6 16 3.c o m115曹光乔等：基于遗传变邻域搜索算法的农机跨区调度优化研究第10 期0引言随着我国新型生产经营主体不断涌现，规模化经营等现代农业生产模式开始兴起，从而带动对农机社会化服务等需求的增加1-3)。在我国，大多数地区的耕地呈现碎片化的地理分布，零散农户仍是农业生产主体。农民的收入很大程度上取决于农产品的产量和市场价格，农机的按需使用能够帮助农户提高作物产量和收人【4。然而，农业机械价格昂贵，小农难以负担，通常只有拥有较多田地的农户才会购买农机以满足作物收获需求5。在农忙时节，采用收获机跨区作业这种“共享农机”模式是为零散农户提供按需和低成本服务最有效的方法。小麦是近一半亚洲地区居民的主要粮食来源，在我国，小麦产量超过全国粮食产量的1/56-7 O小麦成熟期因地理位置不同而具有差异，导致小麦收获机随作物成熟期自南向北跨区迁徙作业【8 ，因此农机跨区调度具有很强的时空演化特征和资源约束特征9-1。目前农机跨区调度多凭借人为经验，调度计划缺乏基于作物成熟期的合理规划，存在作业区域顺序混乱、农机资源配置不合理等问题，造成作业效率低下，贻误农时，降低了作物的收获产量和质量2)。因此，基于“三夏”（夏收、夏种、夏管）时节农机跨区作业需求，研究多约束条件下农机资源配置问题对提高收获机跨区作业效率、保障作业质量具有重要意义。近年来，学者从不同角度对农机调度问题进行了大量的研究，他们大都把农机调度问题转化为带时间窗的VRP问题或运筹学中的运输问题13 。目前研究热点多集中在单个任务或小区域调度，通常情况下只考虑一个农机供应点或同种类型的农机，在农机调度研究中常用的调度优化目标包括：最大作业收益、最小调度总成本、最小调度路程等14-16 。农机调度问题属于NP-hard难题，遇到大型计算实例时,NP-hard问题无法在有效时间内得到解决，常使用启发式算法进行求解解17-18 。例如文献19将模拟退火算法、遗传算法和混合Petri网络模型相结合，提出了一种两阶段的元启发式算法用于求解甘蔗生产收获的资源分配调度模型，并获得了较高的资源利用率。文献2 0 以最小化农机工作时间为目标，提出了一种规划方法确定生物质收获和加工操作的顺序，解决了多领域生物质顺序处理的调度问题。文献2 1 以收获机服务总面积最大为目标，提出的ALNS元启发式算法解决了带时间窗的甘蔗收获机械的调度问题。文献2 2 分析了农机调度的各种成本，以总调度成本最低建立了重大疫情情况下的农机调度模型，并改进模拟退火算法对模型进行求解。上述研究都聚焦在区域内的田间路径优化问题上，在农忙季节，农户作业需求往往来自不同的省、市、县，空间跨度从几十千米到几百千米不等，多种农机在空间大尺度下的规模化跨区调度更能满足农业生产需求。在农机跨区调度上，已有一部分研究，例如文献2 3 建立了以调配成本和损失最小为目标的农机跨区作业紧急调配模型，并提出两种算法求解。文献2 4 通过改进的非支配邻域搜索算法和禁忌搜索算法解决了农机静态分区和动态跨区协同调度问题。文献2 5 考虑多库、多机型和作业时间窗等因素，对农机跨区作业进行研究，提高了服务的准时率和农机的使用率。通过分析文献发现，现有的研究很少涉及农机车队作业，无论是小区域调度或大区域调度，很少考虑到作物的收获周期。事实上，空间大尺度下的农机跨区作业由若干台农机组成农机车队，当多台农机进行跨区作业时，要综合考虑调度距离、作物收获时间窗、农机利用率等因素，由于机械折旧费、路桥费等费用的存在，农机跨区作业的调度距离又会存在合理的范围2 6 。近年来，带时间窗的车辆路径问题得到了广泛的拓展，其中解决绿色车辆路径问题是减少碳排放，实现“双碳”目标的重要手段，暂时尚未有研究在农机调度中考虑碳排放成本。如何在制定农机跨区调度计划时寻求社会经济效益最大化，同时推动绿色发展是一个值得探讨的问题。因此探讨多库、多机型、作业时间窗、空间距离等约束条件下的农机跨区作业资源配置问题，建立考虑碳排放的农机跨区调度模型，对保证粮食生产安全和促进碳中和具有重要意义。本文针对“三夏”时节农机跨区调度的特点建立以最小调度成本为目标的跨区调度模型，同时考虑经济成本和环境成本，以期为农机跨区调度的管理决策提供依据。并提出一种遗传变邻域搜索算法(Genetic algorithm variable neighborhood search,GAVNS)求解模型,在该算法中,采用自适应机制对邻域权重进行动态调整，以期减少跨区调度成本。1问题描述与模型建立1.1问题描述我国幅员辽阔，小麦作物由南向北依次成熟，这种规律为农机提供了一个连续的作业窗口，但我国的农机资源在地理空间上分布不均，在农忙时节，农户往往通过租赁外地的收获机服务来完成收获任务。通常，少量农户依赖社会信任和关系网络，往往十+厂：待收区中到达区域集待收区中出发区域：晚到惩罚成本：早到等待成本文获结束时间E：开始收获时间N个足够大的正整数Pc：碳交易价格（元/kg）T：每日可用工作时间（h）d,：待收区i和j之间的距离（km）S.：X收获面积（hmti：收获机组k到达待收区j的时间（h）(h)t：收获机从待收区i转运到待收区j所需时间tui：完成待收区j收获所需的工作时间(h)e：卡车k在路段（i，j）上的碳排放率（kg/km）w。：每个操作员时薪（元/h）（元/km）大收利转运速度（km/h）厂作效率（hm/h）q：k 型号收获机二(3)参数k：收获机组型号.kEVj：待收区中的到达节点，jEJ：待收区中iE(2）下标A：待收区中节点集合,A=（i，j）liEI，jEJV:收获机组集合,V=1,2,k2023年农报116学机械业基于经验数据，口头或电话传递需求信息给农机驾驶员以完成小麦的跨区机收作业，但这种模式过于依赖个人关系且调度效率低下，易造成资源和信息的不匹配。在大规模的农机调度中，农机合作社参与的调度模式是“三夏”时节完成小麦跨区机收的主要方式。在收获机跨区作业过程中，农户的作业需求往往来自不同的省、市、县，合作社收到包含农田类型、面积和位置等信息的作业订单后完成收获机的派遣。收获机通过卡车搭载成队列从合作社运输至待收区，完成收获作业，农机跨区调度网络如图1所示。收获机组1收获机组2收获机组V收获机1收获机收获机1收获机收获机1收获机农机合作社1农机合作社m待收区1待收区待收区1待收区待收区2待收区3待收区2待收区3收获机组运行方向图1农机跨区调度网络图Fig.1Network diagram of agricultural machinerycross-region scheduling该问题考虑多个合作社为多个小麦待收区提供收获机跨区作业服务，且每个合作社具有多数量、多机型的联合收获机。在建立模型之前，作以下假设：一个区县即为一个待收区；相同型号收获机的运输速率和工作效率相同，收获机从合作社运输到待收区仅存在公路运输一种方式，不考虑天气状况、道路拥堵情况，无道路容量限制；所有收获机与其运载卡车之间的比重相同；将收获机按型号分组，且每组收获机数量可能不同，分别运往不同区域；每个待收区只能由一个收获机组服务；农机合作社位置、待收区位置、待收区的待收获面积已知，一个待收区最多由一个合作社提供服务；收获机组到达待收区的时间即为开始收获时间；小麦在收获时间窗内的品质、产量恒定。1.2模型建立基于以上问题描述，对模型建立中使用的集合、参数和决策变量定义如下：(1)集合M：农机合作社集合,M=1,2，,m l,M=（4）决策变量x：0-1决策变量，若由农机合作社m出发的收获机组k从待收区i到待收区j,则x=1,否则=0。该问题优化目标为调度成本C，包括收获机运输成本C,、车辆和人员固定成本C2、时间惩罚成本C,和碳排放成本C4。收获机运输成本与路径长度呈正相关，运输成本为C,=(d.c.)xmk(1)iETjEJmEMkel车辆和人员固定成本主要由驾驶员工资构成，不考虑每台收获机在田间转运的时间损耗，固定成本为C2=tui+timk(2)W订iETjEJmEMkEV时间惩罚成本与收获机到达待收区开始作业时间有关，时间惩罚成本为r(E,-ti)(tiE,;VjeJ)C,=/o(E,tkLi;VjeJ)117曹光乔等：基于遗传变邻域搜索算法的农机跨区调度优化研究第10 期碳排放成本与收获机转运途中燃油消耗密切相关，文献2 7 对目前流行的油耗估算模型进行了详细的对比分析，考虑到收获机实际转运过程中的车辆特征、道路特征、车辆运行特征，采用MEET模型估算车辆碳排放量2 8 。卡车h在路段（i，j)上的碳排放率(kg/km）为8=Wo+W,V+W2V+04W5W6（4)23V其中：8 表示卡车空载且在坡度为0 以速度行驶时的碳排放率，。为常数，根据卡车类型取值。碳排放率的载重修正因子为=Xo+Xi+X2+X3y+X4U+Xo+2(5)其中：为卡车i在路段（i，j)上的实际载重与其容量的比值，X。X为常数，根据卡车类型取值。卡车k在路段（i，j）上的碳排放率（kg/km）为em=1000(6)在转运过程中收获机k的碳排放成本C为C4=Pmkd(7)EmEMkEVie1iEJJmEMkEV该问题构建的数学模型，目标函数为minC=iEljEJmEMkEVw.(tui+t）mk+ieljeJmeMkeVmax/E,-tx,1 x*+mkieIjeJmeMkevmax/ti-L,0 xk+nkiEjeJmEMkeVPaxeudymk(8)iE1jEJmEMke约束条件为mkV(VmEM)(9)iETiEJmk=1(VieI)(10)mEMmkmk=1(Viel)(11)mEMkemEMkeVmkmkii（i+1)(VkeV)(12)mEMjEJmEMETmkmkX(Vke V)(13)mEMmEMEmk=0(VmEM)(14)EjEJmk(n+1)i=0(Viel)(15)mk=0(VieI)(16)+T(17)tWieljeJiEI-2.2imkEjmeMkeVE,L,(ViI)(18)E,ti+tu,L,(VjeJ)(19)XmkE10,11(VieI)(20)该模型的目标函数（8）表示最小经济成本与环境成本之和。其中，经济成本包括运输成本、固定人力成本和时间惩罚成本，环境成本包括碳排放成本。约束式(9)表示派出的收获机数小于或等于所有合作社的收获机总数。约束式（10）表示每个待收区必须且只能被一个收获机组服务一次，不允许多个收获机组服务同一个待收区。约束式（11）表示每一个待收区域只能由一个收获机组服务，不接受多个机组的多次服务。约束式（12）表示从合作社出发的收获机组在作业完成之后必须返回合作社。约束式（13）表示保证每个收获机组在完成作业后必须离开该地。约束式（14）表示保证合作社之间不进行收获机组的转运。约束式（15）表示禁止收获机组返回合作社后返回待收区。约束式（16）表示消除区域内环流。约束式（17）表示每日的作业时间和转运时间之和不超过规定的时间。约束式（18）表示收获机组从待收区i到待收区j的时间窗应满足的条件。约束式（19）表示收获机组到达待收区和完成作业需满足的时间窗。约束式（2 0）表示决策变量的取值范围。2模型解算农机跨区调度问题属于NP-hard难题，采用精确算法求解大规模实例会出现运行时间长，难以求得最优解，现有的研究都倾向于采用智能优化算法求得近似最优解，如遗传算法、粒子群优化算法、变邻域搜索算法。遗传算法能够在解的空间进行全局搜索，且并行性高，变邻域搜索算法通过在当前解的邻域内搜索，可快速找到局部改进解，这种局部搜索能力使算法在每一步的迭代中逐渐改善解的质量，向更优解的方向前进。综合考虑模型决策变量定义域的规则性，提出遗传变邻域搜索算法（GAVNS）对较大规模的农机跨区调度问题进行求解。2.1算法流程GAVNS算法流程如图2 所示。首先生成基于当前参数组合的初始解，再执行选择、交叉操作，然后用邻域方法对当前解进行改进，最后，当满足终止条件时，输出最优解。GAVNS算法包括染色体编解码、初始解构造、遗传操作、随机扰动、自适应邻域选择、种群管理等。2.2染色体编解码设计根据农机合作社提供的跨区服务特点，采用正整数的编码方式。对染色体的编码，具体表示为：节2023年农118报学机业械开始构造初始解Y满足终止准则？N遗传操作输出最佳解决方案选择交叉结束变邻域操作邻域结构的设计随机扰动自适应邻域选择种群管理删除相同的解决方案图2GAVNS算法流程图Fig.2GAVNS algorithm flowchart点0 表示农机合作社，其他节点表示待收区，染色体基因的数量等于待收区数量的3 倍。染色体分为3层，在第1层中，所有节点根据待收区编号随机填充，第2 层节点由随机选择的k型号收获机填充，第3层节点对应第2 层填充的k型号收获机的派遣数量。染色体编码结构如图3 所示。根据第2 层的信息，k，型号的收获机依次为待收区3、2、5、7 服务。第1层46325780第2 层21一2一一一21第3 层53238034图3染色体编码方式Fig.3Chromosome encoding method2.3初始解构造为构造初始解，首先将每个待收区j按距离分配到最近的农机合作社，然后在每个农机合作社覆盖的待收区内，将所有待收区根据其时间窗的中心值（E，+L)/2 进行排序，如果新增加一个待收区后不再满足模型约束条件，则将该待收区作为调度路径的首个区域划人到一条新的调度路径中，由此得到每个农机合作社的初始调度方案。虽然这种方法得到的目标函数值质量较差，但此种方法存在轻微的约束违规，使算法在较短时间内就能够完成初始解的构造。2.4评价函数染色体适应度函数可以根据模型中目标函数式进行构造，个体评价函数f（x）为目标函数的倒数，公式为1f(x)c(x)(21)式中C(x）一一目标函数值2.5遗传操作2.5.1选择操作选择操作采用精英保留策略与轮盘赌相结合的选择策略。实现步骤为：先用精英保留策略将每一代种群中一定数量的最优染色体直接保存到下一代，再用轮盘赌的方式对剩下的染色体进行选择，每条染色体被选中的概率与其适应度成正比2.5.2交叉操作在交叉操作中，顺序交叉既能保留原有排列基础，又能融合不同排列，故选用顺序交叉算子。如图4所示，从种群中选取一对父代个体1、2 作为交叉对象，在父代个体1、2 上随机选择两个基因交叉点形成交叉子路径。复制父代2 中的交叉子路径置于父代1的最后面，同理，复制父代1中的交叉子路径置于父代2 的最前面。最后删除路径中的重复基因，由此形成两个新的子代1、2。43125786父代122一11312573221431一13427568父代21122312343632315一口V交叉操作431257862722111312235732214332251342756811112231232243632315！一删除重复基因43158627子代122111223573243322513476811112323子代222436215图4染色体交叉过程Fig.4Chromosome crossover process2.6变邻域操作2.6.1变邻域结构设计使用交换、插入、2-Opt、o r-O p t 邻域算子进行变邻域搜索。交换算子是从当前解中随机选择两个不同的节点，交换两节点的位置。插人算子是从当前解中随机选择一个节点，将其插人到新的位置。2-Opt算子是从当前解中随机选择两个不同的节点i、j,并将节点i后的节点顺序进行逆转。or-Opt算子随机选择两个连续的节点，将其逆序插人到随机选择的节点i的后面。邻域结构示意图如图5所示。119曹光乔等：基于遗传变邻域搜索算法的农机跨区调度优化研究第10 期43125786交换4372518643125786插入43257186431257862-0pt43一7528643125786or-Opt43572186图5邻域结构示意图Fig.5Neighborhood structure diagram2.6.2随机扰动首先设定邻域结构N,=N,N2，,N,I,N,表示第n个邻域结构，对种群中的个体c,随机选择一个邻域结构N,开始扰动，来破坏当前解的局部最优解。在预设的邻域搜索次数内，尝试找到改进解c，则令c=c;若在该邻域结构N,内未找到改进解c,则随机选择下一个邻域结构N，进行扰动，直到达到预设的搜索次数。通过增加搜索的多样性和跳出局部最优解的限制，从而扩展搜索范围，使目标函数有机会找到更优的解。这种机制能够有效提升算法的全局搜索能力并改善解的质量。2.6.3自适应选择邻域方法每次送代中，经过计算得到的新解有3 种情况，即新解优化了目标函数并成为新的局部最优解、新解没有优化但是被接受、新解没有优化且被舍弃。上述3 种情况分别对应不同的分数，每个迭代周期结束后，邻域方法的权重根据迭代过程中的表现评分变化实现动态变化。首先对每种邻域方法N设置一个初始权重，初始权重均为1。然后,设置权重为15之间的整数。在每次搜索中，随机选择一种邻域方法，如果选择的邻域方法产生的解比当前最优解更好，则将该邻域的权重加1，最高可达到5。反之，如果没有找到更好的解决方案，则将该邻域方法的权重减1，最低可达到1。这种方法可以动态地调整邻域结构的权重，使搜索更加灵活和高效。2.7种群管理和停止准则为提高整个种群的质量，每次迭代结束后，用最优个体替换最差个体，以维持种群大小一致性和多样性，这种机制能避免算法陷人早熟收敛的状态。在保证种群规模不变的前提下，首先构造新的个体作为初始解，再进行遗传操作，最后利用自适应变邻域搜索方法对其进行改进。当达到最大允许送代次数时，GAVNS算法停止迭代，求解过程终止。3案例分析3.1数据来源与收集黄淮海平原是我国的小麦主要种植区，已有研究表明，每年5月开始，河南南部以及安徽北部等地是小麦联合收获机跨区作业的主要输出地，它们进行跨区作业的范围从几十千米到几百千米不等8 数值实验以河南省驻马店市为发散中心，选取周边72个小麦生产区县，根据实际调查情况和收集的相关实验数据对模型进行实例分析。各小麦生产区县的小麦种植面积来源于中国农村统计年鉴，假设每个区县2%的小麦种植面积需要收获机进行跨区作业服务，各区县地理位置已知，研究区位和各小麦生产区县需求信息如图6 和表1所示。1530162931325028474966673358204111502757346968105621354051702671553639373853面积/hm24113.40102.71102.71207.44207.44319.66N319.66510.260204080km农机合作社位置1510.26748.00图6研究区位Fig.6Investigation area表1小麦生产区县需求信息Tab.1Demand information of wheat productioncounties收获面积/序号地点时间窗位置hm21西峡县54.2760,130(3331N,11147E)2浙川县172.8440,100(3313N,11149E)3丹江口市43.5030,100(3254N,11151E)4保康县100.5510,80(3188N,11126E)5谷城县50.0320,90(3226N,11165E)70叶集区23.7530,100(3185N,11590E)71裕安区102.7230,100(3174N,11647E)72金寨县113.9120,90(3173N,11593E)假设研究区域共有4个农机合作社，分布在4个不同的区县，每个区县有3 种型号的收获机参与跨区作业，整个调度问题将对4个农机合作社周2023年农120机报学业械围的7 2 个区县提供作业服务，操作员每个工作日的最大工作时间为10 h。农机合作社位置及拥有各型号收获机数量如表2 所示表2农机合作社位置及拥有各型号收获机数量Tab.2ILocations of agricultural machinery cooperativesand number of harvesters of each model owned合作社收获机h型号收k2型号收k3型号收合作社地点总量获机总量获机总量获机总量合作社1邓州市200804080合作社2泌阳县2001204040合作社3息县160404080合作社4颖上县1204040403.2模型设置数值实验采用Windows10操作系统，CPU为i7-12700，模拟平台使用Matlab2017a。经过反复测试,算法参数设置如下：最大迭代次数（MG）为700、种群数量（NP）为10 0、交叉概率（Pc）为0.9、最大邻域搜索次数（MS）为10 0 0。将相关数据和变量纳人构建的模型，对于同一实例，算例运行10 次，10个目标值的平均值作为此实例的结果。在“三夏”时节，4个农机合作社分别收集到前期工单，假设每个型号的收获机都有待派遣的任务。表3 给出了农机性能参数及相关运行费用。表3 农机性能参数及相关运行费用Tab.3AAgricultural machinery performanceparameters and associated operating costs参数描述默认值单位距离运输成本/（元km-）2qk1k,型号收获机工作效率/（hm.h-l）0.48qk2kz型号收获机工作效率/（hm.h-1）0.52qk3k,型号收获机工作效率/（hm.h-l）0.45每台收获机转运速度/（kmh-1）60每台收获机早到等待成本/（元h-l）60每台收获机晚到惩罚成本/（元h-l）70W操作员时薪/（元h-）50卡车在路段（i，j）上的实际载重与其容量的比值0.7根据我国目前的碳交易价格，假设碳交易价格P。为0.0 52 8 元/kg，同时，参考文献2 9-3 0，将计算碳排放成本公式中的参数设置如下：W。=110、W=0、W2 =0、W3 =0.0 0 0 3 7 5、W4=8 7 0 2、Ws =0、W。=0,Xo=1.2 7、Xi =0.0 6 1 4、X2 =0、X3=-0.0 0 1 1、X4=-0.002 35、Xs=0、X=0、X7 =-1.3 3。3.3算例计算3.3.1不同优化算法实验结果分析为验证设计的遗传变邻域搜索算法（GAVNS）的有效性，基于相同环境另外编写求解该模型的遗传算法（Geneticalgorithm，G A）、变邻域搜索算法（Variable neighborhood search，VNS），将 GAVNS算法与GA算法、VNS算法进行对比实验，得到最终结果如表4所示，其对比迭代曲线如图7 所示表4闭合路径下3 种算法求解结果对比Tab.4Comparison of results obtained by threealgorithms under closed-path mode总作业时收获机使更总碳排放总调度成惩罚算法类型长h用数/台成本/元本/元时间/hGA4.691054112.321053.76106281.84VNS4.721054062.041053.59106204.52GAVNS4.50 1053871.84 105 3.23 106132.99注：各项结果为10 次实验的平均值。7.0 x106-GA6.5100-VNS-GAVNS6.0 x1065.5x1065.0 x1064.51064.0 x10%3.5x10%3.0 x10%100200300 400500600700送代次数图7闭合路径下3 种算法迭代曲线Fig.7Iteration curves for three algorithms underclosed-path mode从对比结果来看，在调度成本上，GAVNS算法求得的最优值更低，分别比GA算法和VNS算法少16.41%、11.15%，说明GAVNS算法对降低调度成本具有显著意义。在收获机使用数和碳排放成本上，GAVNS算法求得的完成作业任务需派出387台收获机，收获机使用数最少，最高减少6.20%；求得的碳排放成本为1.8 410 元，优于GA算法和VNS算法，最高节约2 6.0 9%，说明GAVNS算法能有效提升每个农机合作社的收获机使用率，减少车辆碳排放，减少环境污染。从图7可知，调度成本随送代次数的增加而降低，GAVNS算法求解模型的速度快于GA算法和VNS算法，在送代次数增加至490 次左右即可收敛至稳定值，得到最优解的送代次数更低、收敛速度更快，说明该算法具有较好的收敛性和搜索能力。GAVNS算法求得的惩罚时间更少，有效降低了麦收惩罚成本，为农忙时节麦收作业预留更多有效作业时间，对保障粮食作物按时收获具有可行性、合理性和有效性。121曹光乔等：基于遗传变邻域搜索算法的农机跨区调度优化研究第10 期3.3.2不同调度模式的实验结果分析(1)GAVNS算法在闭合路径下的调度分析根据仿真实验所选区域跨区收获作业的实际情况，使用建立的调度模型和设计的求解方法进行收获机跨区调度仿真，在仿真实验中，所有参与跨区作业的收获机组的最优调度路径如图8 所示，最优调度方案如表5所示从图8 可知，农机合作社进行跨区作业服务时，优先就近服务，相邻位置的作业区域由同一个农机合作社提供服务。每个收获机组的路径清晰，不同路径间的迁回和交叉情况较少。由表5可知，调度成本为3.2 3 18 10 元，收获机总转运距离为1.6 6 10 km，4个农机合作社社1社2社3作社433.5155486330收获机组216?4365收获机组3318284收获机组433.04294732收获机组5203349566收获机组6收获机7（。）/32.51157收获机组868收获机95669收获机组1094032.051收获机组112870收获机组12552225720713839收获机组135231.5收获机组14收获机组1553收获机组1654收获机组1731.028收获机组18111112113114115116117118经度（）图：闭合路径下的最优调度路径Fig.8Optimal scheduling path under closed-path mode表5闭合路径调度模式的最优调度方案Tab.5Optimal scheduling solution for closed-path scheduling mode派出该型号调度路径收获面积/区间转运惩罚时间农机合作社收获机型号调度路径数量/台序号hm2距离/kmh15112-5-3-1-2-12320.63303.180k230212-4-22-10-14-13-121265.99441.059.99合作社123312-6-8-9-11-18-17-15-121 027.69674.8110.15k321412-7-121081.10210.03017528-27-32-31-28958.09226.84021628-24-43-30-281062.38543.1926.25合作社221728-20-28712.89108.130k218828-26-25-19-16-28960.44365.4918.06k22928-23-21-29-33-281 157.75595.700k271050-40-37-34-44-49-501309.52445.9111.57k2311150-38-53-54-55-48-45-42-501 721.38750.400k3161250-52-56-47-501323.31342.3825.17合作社3111350-46-50365.75249.930k3181450-41-50653.2597.5103251550-39-36-35-51-57-501 144.24378.158.26291667-72-58-59-65-64671488.39503.320合作社4k2251767-71-60-61-69-70-63-671279.56654.518.06171867-68-66-62-671047.28286.3515.48均派出收获机组进行跨区作业服务，共使用3 8 7 台收获机，每个合作社都有较高的农机利用率。4个农机合作社派出的收获机组