基于改进蚁群算法的联合收割机调度路径优化

龚瑞昆　吴天华

摘要：为缓解收割机在收获季节供不应求的局面，实现联合收割机在收割中的高效率、低成本和高收入。通过对影响收割机调度的多种因素进行分析，建立联合收割机调度的数学模型。针对基本蚁群算法易陷入局部最优解、收敛速度慢等缺点，引入节约矩阵，并对不同搜索时段采用不同的信息挥发因子，最后通过局部搜索策略2-opt法搜索最优解的方法改进基本蚁群算法，对模型进行求解。仿真结果表明，改进后的蚁群算法性能优良，且可降低调度成本，能够有效解决联合收割机在农忙时节的使用问题。

关键词：联合收割机;改进蚁群算法;数学模型;调度

中图分类号： S225.3  文献标志码： A  文章编号：1002-1302（2019）04-0197-04

我国是传统的农业大国，农作物产量直接影响着我国国民经济的发展，是国民经济又好又快发展的重要保障。但随着农作物产量的增大，一些在收割过程中遇到的问题容易暴露出来。根据调查，每年在收割季节，许多地区的联合收割机供不应求，但还有一些地方的收割机出现闲置现象，无法达到收割的最高效率和最大利润。事实上，收割机调度在农机调度领域的研究中一直处于空缺状态。农忙时短，如果错过了收割期，麦子就会炸裂，农户损失粮食;农机手如果在这期间找不到活干，会损失掉一年中大半的收入。以往农户与农机手的互动只能靠麦收期的电话联系或者路上拦截，这种碰运气式的联络往往会耽误不少时间。而由此产生的中介往往从中谋利，不仅能增加农户的成本，又会降低农机手的收入。因此，如何利用现有的计算机技术实现联合收割机调度路径优化，减小收割机的收割成本，提高农民的收入，成为许多农业企业研究的重大课题[1-3]。

本研究旨在从蚁群算法这一启发式算法入手，针对其运算时间长、收敛速度慢等缺点，引入节约矩阵对其路径选择进行改进，并对不同搜索时段采用不同的信息挥发因子，最后通过局部搜索策略2-opt法对最优解进行搜索的方法对基本蚁群算法进行改进。构造联合收割机调度成本最低化的目标函数，并将改进后的算法应用到目标函数中，实现收割机在调度过程中的路径优化，提高收割机在每年收获季节的利用率。

1 建立数学模型

1.1 联合收割机调度原则

（1）准时性原则。由于农忙时短，如果错过收获期，农户就会损失粮食，因此收割机调度系统的建立须要结合收割机位置、路线和运行速度等，以便调度中心及时进行处理，滿足系统的准时性原则。（2）路径最短原则。联合收割机调度系统意在协调地区之间收割机的资源配置问题，因此最佳路线的选择至关重要，通过选择最佳的调度路线，降低调度成本，提高联合收割机工作效率，进而谋求最大的经济效益[4-5]。（3）收割机使用最小化原则。收割机的启用成本较高，当现有的收割机资源可以满足收割需求时，应尽可能少地派收割机出去工作，以减少联合收割机的调度成本。

1.2 模型假设

假设所有联合收割机为同一类型，比如收割机都是收割小麦或都是收割玉米的;根据农户种植信息确定农田位置和收割点;设有且仅有1个中心农机点，每条路线的开始和结束位置都在该中心农机点;各条路线均处于较理想状况，不考虑天气、地势等特殊环境情况。

1.3 惩罚函数

联合收割机到达时间偏离农户约定时间的时间窗越大，惩罚的成本越高。本研究将惩罚成本设定为线性增长模式。因此，对惩罚成本作一些前提假设：收割机到达时间在时间窗内，则不会产生惩罚成本;当收割机到达时间偏离时间窗时，则进行如下惩罚。惩罚成本函数表达式为

式中：Hi（tir）表示收割机r在时间ti的惩罚成本;p表示早到惩罚系数;q表示晚到惩罚系数;tir表示收割机实际到达收割点i的时刻;ai为收割机最早到达收割点i的时刻;bi为收割机最晚到达收割点i的时刻。

1.4 变量和参数符号

在建立模型以前，须要对模型所用到的变量和参数符号进行定义和说明，设i为单个收割点的编号，N为收割点数量，i∈{1，2，…，N}，其中i=1代表中心农机点;r为派出去工作的收割机编号;R为收割机的总体数量，r∈{1，2，…，R};s为闲置的收割机编号，s∈{1，2，…，R};Cr为出去工作的收割机数量，Cs为闲置的收割机数量，Cr+Cs=R;eij为从收割点i到收割点j的单位距离成本;dij为从收割点i到收割点j的距离;er为单个收割机的启用成本;es为收割机的月闲置成本;ts为闲置时间，表示收割机s从回到中心农机点到下次启用的时间间隔;gi为根据以往数据分析收割点i在单位时间内大约能收割的量;Tir为收割机r在收割点i的工作时间;ti为收割机r准时到达收割点i的时刻;Kr为收割机r出去工作的收割任务指标。

1.5 数学模型

式（4）表示每台收割机均从中心农机点出发最后回到中心农机点;式（5）表示从中心农机点派出去工作的收割机数量不超过停在中心农机点的收割机总数R台;式（6）、（7）表示每个收割点只能被1台收割机收割1次;式（8）表示每台收割机从出去工作到最后回到中心农机点要完成自己的收割任务;式（9）表示时间窗约束;式（10）表示出去工作的收割机与闲置的收割机总和为R。

2 基于蚁群算法的路径优化与改进

2.1 蚁群算法基本原理

2.2.2 对挥发因子的改进 ρ的大小直接影响蚁群算法的全局搜索能力和收敛速度。ρ一般取（0，1）上的一个常数，1-ρ 表示信息素残留因子。当ρ越大时，路径上的信息素量减少得越多，路径决策的随机性越高，更有助于找到全局最优解，但算法的收敛速度较慢;当ρ较小时，导致局部路径上的信息素积累过多，虽然算法会快速收敛，但容易陷入局部最优解。针对这一情况，本研究对不同迭代时段采用不同的挥发因子。在搜索初期采用一个较大的挥发因子，这样有利于进行全局搜索得到全局最优解;在迭代中期和末期逐渐选取较小的挥发因子，从之前全局搜索中得到的较优路径中进行集中搜索，得到最终的较优路径。挥发因子ρ采用的分段函数表达式为

2.2.3 局部搜索能力的改进 为避免算法陷入局部最优，增加解的多样性，本研究采用2-opt法对算法进行局部优化[9-10]。为加快算法的收敛速度，只对每次迭代产生的最优路径进行优化，路径交换的规则为用（i，j）、（i+1，j+1）代替（i，i+1）、（j，j+1），同时翻转交换后线路方向，线路变短，路径得到优化。具体的交换方法如图1所示。

2.3 改进蚁群算法的工作流程

改进后的蚁群算法流程如图2所示。

3 仿真分析

某农机企业有8辆收割小麦的联合收割机，企业根据当地小麦的收获期和往年收获数据分析得知，当地总共有15个种植小麦的农田。为了方便调度分析，本研究对数据和数据单位作出如下假设：（1）收割机在农田工作的时间按小时（h）来计算;（2）以平面坐标的横、纵坐标来表示农田所在位置的经、纬度;（3）收割机的收割量以公顷（hm2）为单位;（4）i=1为调度中心（也就是中心农机点），i∈{2，3，…，16}为收割点的编号。

算例仿真试验数据见表1。其中序号1表示中心农机点，序号2～16表示15个收割点，由于对最终返回中心农机点的时间不作要求，因此取1 000作为最晚回到中心农机点的时间。

本研究运用Matlab软件分别对改进前后的算法进行仿真。初始参数设置为α=1，β=2，ε=2，Q=100，ρ的取值见式（17），蚂蚁数量M=60，q0=0.03，最大迭代次数 Nmax=300。

通过对程序进行多次运行，得到基本蚁群算法的收敛曲线（图3）和改进后蚁群算法的收敛曲线（图4）。可以看出，基本蚁群算法在迭代大概140次的时候趋于稳定，而改进后的蚁群算法在迭代大概90次的时候就趋于稳定，提高了算法的收敛速度，并且得到的最优成本也更低。

为进一步验证改进蚁群算法的优越性，本研究对2种算法程序分别运行10次，所得到改进前后蚁群算法的调度成本见表2。通过对2组解进行对比可以明显看出，改进后的蚁群算法得到的解整体优于基本蚁群算法。取改进前、后蚁群算法所得的最小解Z前=373.638 2、Z后=353.529 3 进行分析，其收割机调度路线轨迹分别如图5、图6所示。

基本蚁群算法的最小成本调度路径如表3所示。最优成本為373.638 2万元，收割机行驶路程为131.875 7 km。

改进后蚁群算法的最小成本调度路径如表4所示。最优成本为353.529 3万元，收割机行驶路程为116.867 2 km。

通过对比可得，改进后的蚁群算法得到的最优成本为353.529 3万元，比改进前减少了20万元左右;改进前收割机行驶路程为131.875 7 km，改进后收割机行驶路程为 116.867 2 km，改进后的蚁群算法缩短了收割机的行驶路程，符合路径最短的调度原则，说明改进后的蚁群算法可有效地解决收割机的调度问题。

4 结论

在对联合收割机调度问题进行深入分析后，建立以调度成本最小为目标函数的数学模型，并通过引入节约矩阵、对不同搜索时段采用不同的信息挥发因子、2-opt法进行局部搜索的手段改进基本蚁群算法。改进后的蚁群算法与改进前相比具有较快的收敛速度，且得到的最优调度成本也更优，同时可避免算法陷入局部最优解。改进后的蚁群算法可快速生成调度成本较低的调度方案，说明本研究所建模型合理，改进算法有效，可有效解决联合收割机调度问题。

参考文献：

[1]段运红. 农机调度将成“互联网+”农业突破点[J]. 农业机械，2015（15）：64-65.

[2]石良华. 联合收割机械在跨区作业中存在的几个问题[J]. 科技创新与应用，2013（27）：296.

[3]马梅琼. 联合收割机跨区作业调度研究[D]. 哈尔滨：东北农业大学，2017：1-6.

[4]范 青. 基于改进蚁群算法的物流配送路径优化及应用研究[D]. 西安：西安建筑科技大学，2014：11-12.

[5]Baldacci R，Mingozzi A，Roberti R. Recent exact algorithms for solving the vehicle routing problem under capacity and time window constraints[J]. European Journal of Operational Research，2012，218（1）：1-6.

[6]段海滨. 蚁群算法原理及其应用[M]. 北京：科学出版社，2005：24-43.

[7]王晓东，张永强，薛 红. 基于改进蚁群算法对VRP线路优化[J]. 吉林大学学报（信息科学版），2017，35（2）：198-203.

[8]孙 沁，欧邦才，丁晓银，等. 基于改进蚁群算法的配送路径优化问题研究——以南京苏宁易购为例[J]. 物流工程与管理，2018，40（2）：77-82.

[9]潘挺雷. 基于改进蚁群算法的区域车辆配送路径优化方法研究[D]. 杭州：浙江理工大学，2016：28.

[10]Englert M，Rglin H，Vcking B. Worst case and probabilistic analysis of the 2-opt algorithm for the TSP[J]. Algorithmica，2014，68：190-264.黎 虹，李 光. 高精度农业机械质心测量系统的设计与研究[J]. 江苏农业科学，2019，47（4）：201-203.