一种基于耦合算法的多林区航线调度规划方法

摘要

本发明公开了一种基于耦合算法的多林区航线调度规划方法，包括以下步骤：S1、设置模拟退火算法控制参数；S2、产生初始解；S3、计数器count＝0；S4、将k＝1；S5、解变换、变异、逆转得到新解；S6、根据Metropolis准则判断是否接受新解；S7、得到新解S1，并将k＝k+1；S8、判断k>L；S9、执行count＝count+1，T＝qT；利用降温速率q进行降温。S10、判断T是否小于Tend；S11、输出作业顺序路径解集；S12、设置遗传算法种群大小、交叉概率、变异概率；S13、遗传算法初始化种群Chrom2；S14、计算适应度值；S15、进行选择、交叉、变异操作；得到更新后种群Chrom2；S16、检测迭代次数；S17、输出最短的全局区域间调度路径。

权利要求

1.一种基于耦合算法的多林区航线调度规划方法，其特征在于：包括如下步骤：S1、算法开始，设置模拟退火算法的降温速率q、初始温度T0、结束温度Tend以及链长L；

S2、采用产生随机排列的方法产生一个初始作业路径顺序S1，将该顺序作为模拟退火算法的一个初始解；

S3、计数器count＝0；

S4、将k＝1；

S5、采用解变换、变异、逆转三种方式得到3个新解，以3个新解的作业顺序路径长度最小者作为新解S2；

S6、根据Metropolis准则判断是否接受新解；作业顺序路径采用片区之间的距离邻域表进行计算，以各片区进出入点连线的中点为计算基准点；记当前作业顺序路径长度为f(S),新解的作业顺序路径长度为f(S2),路径差为df＝f(S2)‑f(S1),则Metropolis准则为若df <0，则以概率1接受新的作业顺序路径；否则以概率exp(1‑df/T)接受新的路径；

S7、得到新解S1，并将k＝k+1；

S8、判断k>L，如果是，将进行S9，否则返回S5；

S9、执行count＝count+1，T＝qT；利用降温速率q进行降温；

S10、判断T是否小于Tend，如果是，就执行S11，否则执行S4；

S11、输出作业顺序路径解集；

S12、设置第二层遗传算法种群大小、交叉概率、变异概率，第二层算法最大迭代次数GENMAX，并将迭代次数初值置1，即gen＝1；

S13、第二层遗传算法初始化种群Chrom2，采用二进制编码的方式；

S14、计算第二层算法的适应度值，将飞机起降点看成2个点，但将坐标定为同一数值，以方便快速利用邻域表计算适应度值，从飞机起降点出发的考虑各片区进出点的全局区域间调度航线；适应度f2设计为针对每一种进出入状态下第一层算法得到的所有全局区域间调度航线的最短距离的倒数；

S15、对种群Chrom2中进行选择、交叉、变异操作；然后重新插入后得更新后种群Chrom2；

S16、检测迭代次数是否超过最大迭代次数GENMAX，当迭代次数未超过最大迭代次数时，返回步骤S14，否则进行步骤S17；

S17、输出最短的全局区域间调度路径，该最短调度路径即为多林区航线调度规划的最佳调度方案。

2.如权利要求1所述基于耦合算法的多林区航线调度规划方法，其特征在于：所述步骤S9中的遗传算法种群中的种群大小设置为林区数与飞机起降点之和的4～6倍，代沟设置为常数，交叉概率Pc和变异概率Pm均设计为动态变化概率。

3.如权利要求2所述基于耦合算法的多林区航线调度规划方法，其特征在于：代沟设置为0.9～0.95。

4.如权利要求1所述基于耦合算法的多林区航线调度规划方法，其特征在于：交叉概率随迭代次数增大而减小，变异概率随迭代次数增大而减小；其计算公式为：

5.如权利要求1所述基于耦合算法的多林区航线调度规划方法，其特征在于：Pcmin＝

0.6，Pcmax＝0.9，Pm0＝0.1。

说明书

一种基于耦合算法的多林区航线调度规划方法

技术领域

[0001] 本发明涉及林业管理技术领域，尤其涉及一种基于耦合算法的多林区航线调度规划方法。

背景技术

[0002] 我国林区地形非常复杂，大面积林区和分散的小面积林地同时存在。我国北部地区多以大面积林地为主，然而东部地区则以道路、村庄以及农田等地区防护林为主，常为多
个面积分散的小片林区，因此，多林区的航线调度规划尤为重要。植保飞机作业时，在每个
小片林区施药完成后，进入下一个林区，直至完成所有林区的施药工作，再回到飞机起降
点。不同的作业顺序和片区进出点，却导致飞机非施药航程存在较大差异。减少飞机非施药
航程，意味着减少航空燃油消耗和作业时间，提升飞机植保作业效率，对实现精准农林作业
都有重要意义。然而考虑飞机各片区进出入点的全局区域间最短路径求解非常复杂，尤其
是当片区数较多时，传统的贪心法、深度搜索、广度搜索、分支限界搜索都很难求解出合理
的调度方案。因此运用先进的人工智能算法，快速求解出合理的各林区间航线调度规划方
案具有重要意义。目前对大型植保飞机航空施药作业调度航线规划研究较少，难以满足多
林区航空施药的使用要求，给多林区施药作业带来了一些困扰。

发明内容

[0003] 本发明的目的是针对现有技术的不足，提供一种基于耦合算法的多林区航线调度规划方法，操作简单，效率高。

[0004] 为了实现上述目的，本发明的技术方案是：

[0005] 一种基于耦合算法的多林区航线调度规划方法，包括如下步骤：

[0006] S1、算法开始，设置模拟退火算法的降温速率q、初始温度T0、结束温度Tend以及链长L；

[0007] S2、采用产生随机排列的方法产生一个初始作业路径顺序S1，将该顺序作为模拟退火算法的一个初始解；

[0008] S3、计数器count＝0；

[0009] S4、将k＝1；

[0010] S5、采用解变换、变异、逆转三种方式得到3个新解，以3个新解的作业顺序路径长度最小者作为新解S2；

[0011] S6、根据Metropolis准则判断是否接受新解；作业顺序路径采用片区之间的距离邻域表进行计算，以各片区进出入点连线的中点为计算基准点；记当前作业顺序路径长度
为f(S),新解的作业顺序路径长度为f(S2),路径差为df＝f(S2)‑f(S1),则Metropolis准则
为

[0012]

[0013] 若df<0，则以概率1接受新的作业顺序路径；否则以概率exp(1‑df/T)接受新的路径；

[0014] S7、得到新解S1，并将k＝k+1；

[0015] S8、判断k>L，如果是，将进行S9，否则返回S5；

[0016] S9、执行count＝count+1，T＝qT；利用降温速率q进行降温；

[0017] S10、判断T是否小于Tend，如果是，就执行S11，否则执行S4；

[0018] S11、输出作业顺序路径解集；

[0019] S12、设置第二层遗传算法种群大小、交叉概率、变异概率，第二层算法最大迭代次数GENMAX，并将迭代次数初值置1，即gen＝1；

[0020] S13、第二层遗传算法初始化种群Chrom2，采用二进制编码的方式；

[0021] S14、计算第二层算法的适应度值，将飞机起降点看成2个点，但将坐标定为同一数值，以方便快速利用邻域表计算适应度值，从飞机起降点出发的考虑各片区进出点的全局
区域间调度航线；适应度f2设计为针对每一种进出入状态下第一层算法得到的所有全局区
域间调度航线的最短距离的倒数；

[0022] 以四片片区域为例，作业顺序假定为ABCD；B区域的作业起始点可分别为B1与B2或B2与B1，两种状态分别用0与1表示；则A1A2B1B2C1C2D1D2的状态编码为0000；表明作业顺序
为从A1出发，进入A片区，从A2出，B1进，B2出，C1进，C2出，D1进，D2出，再回到A1。则
A1A2B2B1C1C2D2D1的状态编码即为0101；飞机起降点的处理是关键点，将飞机起降点看成2
个点，但将坐标定为同一数值，以方便快速利用邻域表计算适应度值；如此可以表示从飞机
起降点出发的考虑各片区进出点的全局区域间调度航线；适应度f2设计为针对每一种进出
入状态下第一层算法得到的所有全局区域间调度航线的最短距离的倒数；以状态编码0101
为例，假设算法第一层求得全局区域间调度航线有n种，则该适应度计算公式为

[0023] S15、对种群Chrom2中进行选择、交叉、变异操作；然后重新插入后得更新后种群Chrom2；

[0024] S16、检测迭代次数是否超过最大迭代次数GENMAX，当迭代次数未超过最大迭代次数时，返回步骤S14，否则进行步骤S17；

[0025] S17、输出最短的全局区域间调度路径，该最短调度路径即为多林区航线调度规划的最佳调度方案。

[0026] 作为对上述技术方案的改进，所述步骤S9中的遗传算法种群中的种群大小设置为林区数与飞机起降点之和的4～6倍，代沟设置为常数，交叉概率Pc和变异概率Pm均设计为动
态变化概率。

[0027] 作为对上述技术方案的改进，代沟设置为0.9～0.95。

[0028] 作为对上述技术方案的改进，交叉概率随迭代次数增大而减小，变异概率随迭代次数增大而减小；其计算公式：

[0029]

[0030]

[0031] 作为对上述技术方案的改进，其中Pcmin＝0.6，Pcmax＝0.9，Pm0＝0.1。

[0032] 步骤S1‑S11表示的为该耦合算法第一层，该层采用模拟退火算法求解作业顺序路径，算法第一层采用模拟退火算法求解作业顺序路径，该算法可以求解不同非线性问题，具
有较强的鲁棒性、全局收敛性、隐含并行性及广泛适用性。在步骤S5增加了遗传算法中变异
操作和逆转操作来产生新解的方式，用解变换、变异、逆转三种方式得到的3个新解，以3个
新解计算得到的最短作业路径顺序作为当前的新解S2，然后利用Metropolis准则进行判
断。这种方法耦合了遗传算法全局搜索能力强的优势，也保留了模拟退火算法较强的全局
收敛性，在TSP问题求解中具有很强竞争力。

[0033] 进一步的，步骤S12‑S17表示的为该耦合算法第二层，为一种实用的遗传算法，用来进一步在作业顺序路径的基础上考虑进入点机制。所述步骤S11中，依赖第一层模拟退火
算法的求解结果，第二层遗传算法适应度值计算采用针对Chrom2中每一条染色体，对第一
层算法得到的所有作业路径顺序进行扩展操作，并采用扩展领域表计算其全局区域间调度
距离长度，该长度不包含片区内部的距离，以得到的最短距离的倒数作为该条染色体的适
应度值。

[0034] 与现有技术相比，本发明具有的优点和积极效果是：

[0035] 本发明公开了一种基于耦合算法的多林区航线调度规划方法。对多林区航线调度路径进行规划，特别针对载人大型植保飞机航空施药。第一层采用模拟退火算法求解较优
的作业顺序路径，该算法采用二邻域解变化、自身变异、自身逆转三种方式得到新解的方
式，耦合了遗传算法全局搜索能力强的优点，较传统模拟退火算法提升了全局搜索能力；第
二层算法采用遗传算法，结合第一层得出的解集，考虑各片区进出点，从而得到最短全局区
域间调度路径，其避免了第一层程序里面只求得最短作业顺序路径而陷入的全局区域间调
度路径局部最优解，计算效率较高，从而提高了多林区施药的路径规划效率。遗传算法中采
用了动态的交叉概率和变异概率，交叉概率和变异概率均随迭代次数增大而减小，在照顾
全局搜索能力的前提下，提升了算法收敛速度，节约了搜索时间，提升了算法效率。本发明
可以缩短植保作业飞机在单片区林区中的施药转弯次数，降低了飞行员驾驶操作难度；可
缩短在多林区施药操作的全局区域间调度路径航程，节约了多林区航空施药的工作时间，
并且有效减小了航空燃油的使用量，节约了林区施药作业的经济成本，给多林区施药操作
带来了便利，提升了林区航空施药效率。

附图说明

[0036] 为了更清楚地说明本发明实施例或现有技术中的技术方案，下面将对实施例或现有技术描述中所需要使用的附图作简单地介绍，显而易见地，下面描述中的附图仅仅是本
发明的一些实施例，对于本领域普通技术人员来讲，在不付出创造性劳动性的前提下，还可
以根据这些附图获得其他的附图。

[0037] 图1为本发明中的耦合算法流程图；

[0038] 图2为多林区航线规划任务图；

[0039] 图3为单片区内航线规划示意图；

[0040] 图4为多林区全局航线调度规划结果示意图。

具体实施方式

[0041] 下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例仅仅是本发明一部分实施例，而不是全部的实施例。基于
本发明中的实施例，本领域普通技术人员在没有做出创造性劳动前提下所获得的所有其他
实施例，所作的任何修改、等同替换、改进等，均应包含在本发明的保护范围之内。

[0042] 如图1至图4所示，本实施例公开了一种基于耦合算法的多林区航线调度规划方法，其航线规划任务如下：直升机从图2中飞机起落点H出发，然后经过每个片区的进入点和
出去点，遍历每个片区，然后回到H。要求区域间调度的航线最短。区域内部采用图3所示的
全覆盖航线规划算法，即从边界最长边根据飞机喷福宽度以此做平行线，到其它边界交界
时，飞机掉头飞行，直至遍历完片区所有面积。因此每个片区必有进入点和出入点。调度规
划时必须从两点进出，但不具体哪一点。如从图2中A1进入后，必须从A2出，或者从A2进入
后，必须从A1出。区域内部按照图3所示的航线规划。按照图1所示的模拟退火算法和遗传算
法耦合算法进行路线规划，得到如图4所示的较优结果。

[0043] 模拟退火算法和遗传算法耦合算法流程如图1所示，以下是算法实施过程：

[0044] 步骤1：算法开始，设置模拟退火算法的降温速率q、初始温度T0、结束温度Tend以及链长L；

[0045] 步骤2：根据待施药林区数量采用产生随机排列的方法产生一个初始作业路径顺序S1，将该顺序作为模拟退火算法的一个初始解；例如有5片林区需要施药，则S1的长度定为
5+1＝6。1表示飞机起降点，放在种群长度最后一位，则123456、213465、345216都是可以是
一个新解，要求数字不重复。

[0046] 步骤3、计数器count＝0；

[0047] 步骤4、将k＝1；

[0048] 步骤5、采用解变换、变异、逆转三种方式得到3个新解，以3个新解的作业顺序路径长度最小者作为新解S2。解变换方法，如林区数为5，则在[16]产生随机整数r1和r2，假设r1
＝2，r2＝4，则123456变换为143256。变异方法，如林区数为5，则在[16]产生随机整数r3，假
设r3＝3，则在3位置突变成[16]之间的一个随机整数，并将重复的林区数字置为r3位置原来
的数。如123456，在r3＝3处突变成6，则123456变换为126453。逆转方法，同样假设林区数为
5，则在[16]产生随机整数r1和r2，假设r1＝2，r2＝4，则123456变换为124356。三种方式产生
的三个解的计算最短作业顺序路径长度作为新解S2。

[0049] 步骤6、根据Metropolis准则判断是否接受新解；作业顺序路径采用片区之间的距离邻域表进行计算，以各片区进出入点连线的中点为计算基准点。记当前作业顺序路径长
度为f(S1),新解的作业顺序路径长度为f(S2),路径差为df＝f(S2)‑f(S1),则Metropolis准
则为

[0050]

[0051] 若df<0，则以概率1接受新的作业顺序路径；否则以概率exp(1‑df/T)接受新的路径。

[0052] 作业顺序路径长度计算方法：以图2中的调度任务为例，其18个片区和飞机起降点的坐标如表1所示。其进出点中点生成的邻域表如表2所示。根据表2，可快速计算出该层模
拟退火算法中解的路径长度。

[0053] 表1各林区坐标表

[0054]                                                           单位：m

[0055]

[0056]

[0057] 以各片区进出点中点坐标作为参考点计算各林区作业顺序路径距离。并以该18片区中点坐标和飞机起降点坐标生成距离邻域表。

[0058] 表2各片区进出点中点生成的距离邻域表

[0059]

[0060]

[0061] 步骤7、得到新解S1，并将k＝k+1；

[0062] 步骤8、判断k>L，如果是，将进行S9，否则返回S5；

[0063] 步骤9、执行count＝count+1，T＝qT；利用降温速率q进行降温。

[0064] 步骤10、判断T是否小于Tend，如果是，就执行S11，否则执行S4；

[0065] 步骤11、输出作业顺序路径解集；

[0066] 步骤12、设置遗传算法种群大小，交叉概率，变异概率。如种群大小设置为林区数与飞机起降点之和的4～6倍，如18片区，则设种群数为100；代沟均设置为常数；代沟设置为
0.9～0.95，如0.9。交叉概率Pc和变异概率Pm均设计为动态变化概率。交叉概率随迭代次数
增大而减小，变异概率随迭代次数增大而减小。其计算公式：
其中Pcmin＝0.6，Pcmax＝0.9，初
始变异概率Pm0＝0.1。遗传算法最大迭代次数GENMAX，如2000。并将迭代次数初值置1，即gen
＝1；

[0067] 步骤13、第二层遗传算法初始化种群Chrom2，采用二进制编码的方式。编码方式采用二进制编码，以四片片区域为例，作业顺序假定为ABCD，其中A表示飞机起降点。B区域的
作业起始点可分别为B1与B2或B2与B1，两种状态分别用0与1表示。则A1A2B1B2C1C2D1D2的
状态编码为0000，特别说明的是，飞机起降点A1和A2的坐标完全相同，表明作业顺序为从A
出发，B1进，B2出，C1进，C2出，D1进，D2出，再回到A。则A1A2B2B1C1C2D2D1的状态编码即为
0101。如此可以表示从飞机起降点出发的考虑各片区进出点的各片区间作业调度路径情
况。

[0068] 步骤14、计算第二层算法的适应度值。为方便第二层遗传算法适应度的计算，同样利用邻域表，该邻域表为将表1中的各片区进出点横坐标、纵坐标生成的邻域表，如表3所
示。由于18个片区的考虑进出入点的邻域表太大，这里就展示4个片区和1个飞机起降点的
领域距离矩阵。四个片区分别A、B、C、D，将每个片区的进出点分别表示为两个代号，如A片区
的进出点表示为A1和A2。飞机起降点坐标用H表示。18片区的考虑进出入点和飞机起降点的
领域距离矩阵可参考本方法。适应度f2设计为针对每一种进出入状态下第一层算法得到的
所有全局区域间调度航线的最短距离的倒数。以状态编码10010为例，根据10010状态修正
第一层算法得出的较优路径解集，修正方法如表4所示。假设算法第一层求得全局区域间调
度航线有n种，则该适应度计算公式为公式(8)。

[0069]

[0070] 表3考虑片区进出入点和飞机起落点的领域距离矩阵

[0071]

[0072] 表4根据状态表Chrom2修正第一层算法作业顺序路径的一个例子

[0073]

[0074]

[0075] 需要说明的是，表4中的7对应于表3中的A2点，1对应表中的A1点。以此类推。具体可参考步骤16。

[0076] 步骤15、对种群Chrom2中进行选择、交叉、变异操作；然后重新插入后得更新后种群Chrom2；

[0077] 步骤16、检测迭代次数是否超过最大迭代次数GENMAX，当迭代次数未超过最大迭代次数时，返回步骤11，否则进行步骤14；

[0078] 步骤17、输出最短的全局区域间调度路径，该最短调度路径即为多林区航线调度规划的最佳调度方案。

[0079] 本发明通过采用模拟退火算法和遗传算法耦合算法对多林区航线调度路径进行规划，特别针对载人大型植保飞机航空施药。考虑到安全及各林区间调度无喷施飞行距离，
因此将植保喷雾作业续航航程、载药量、植保喷雾作业续航时间参数的设置小于飞机自身
性能参数。

[0080] 本发明的模拟退火算法和遗传算法耦合算法采用串联式耦合方法，迭代次数为两次算法各自迭代次数相加之和，速度较嵌套式耦合更快。两层算法均收敛。第一层采用模拟
退火算法，增加了遗传算法中变异操作和逆转操作来产生新解的方式，用解变换、变异、逆
转三种方式得到的3个新解，以3个新解计算得到的最短作业路径顺序作为当前的新解S2，
然后利用Metropolis准则进行判断。这种方法耦合了遗传算法全局搜索能力强的优势，也
保留了模拟退火算法较强的全局收敛性，在TSP问题求解中具有很强竞争力，能够较快得出
较优的作业顺序路径解集；第二层算法采用遗传算法，结合第一层得出的作业顺序路径解
集，考虑各片区进出点，从而得到最短全局区域间调度路径，其避免了第一层程序里面只求
得最短作业顺序路径而陷入的全局区域间调度路径局部最优解，计算效率较高，从而提高
了多林区施药的路径规划效率。

[0081] 本发明可以缩短植保作业飞机在单片区林区中的施药转弯次数，可缩短在多林区施药操作的区域间调度路径航程，节约了多林区施药操作的工作时间，提高了林区施药的
施药效率，并且其有效减小了航空燃油的使用量，节约了林区施药作业的经济成本，给多林
区施药操作带来了便利。