1.一种基于混合遗传算法的作业车间运动轨道路径导向优化方法，其特征在于，包括以下步骤：

设置种群规模、交叉概率、变异概率、最大迭代次数、RVNS的局部搜索个体数、AGV的运输速度；

生成满足强连通约束的导向路径网络，将导向路径网络有向图转换成n个耳朵分解序列，即生成n个初始个体；

采用基于贪婪准则的“制造‑储运”联合调度算法，计算既的适应度值；所述“制造‑储运”联合调度算法的贪婪准则的选择准则为：选择最早完成搬运任务的AGV为首选设备，选择最早开工的工件任务；

对迭代次数进行判断：当迭代次数＞最大迭代次数，输出最优的导向路径网络和调度方案，否则进行下述的步骤；

基于竞标赛和精英保留相结合的方式，从种群中选择需要进行交叉和变异的个体，组成一个新的种群；

基于交叉算子对新的种群进行交叉操作；

基于变异算子对交叉后的种群进行变异操作；

随机从变异后的种群中选择定量的个体，基于RNVS的邻域搜索算法，对此部分的个体进行邻域搜索，得到新的种群，之后返回对迭代次数进行判断步骤；

所述基于贪婪准则的“制造‑储运”联合调度算法的步骤如下：初始化AGV释放时间矩阵RA、机器释放时间矩阵RM、工件释放时间矩阵RJ；

转化工序加工信息矩阵Jobs_OInfo，工序总数TO_Num和工件已完工工序数Job_Oper；

i＝1；

(S1)：统计存在未完工工序的工件数量Wait_JobNum；

j＝1；

(S2)：确定工件等待搬运的位置节点Job_PointM；

k＝1；

(S3)：确定当前AGV所在位置节点AGVR_Point，并记录AGV的空载运输时间和运输完成时间；

k＝k+1；

当(k＜AGV_Num)，返回S3；

以最早搬运完成时间为准则确定被选择执行任务的AGV；

确定工件需要搬运的目标节点，并通过计算得到工序的最早开工时间Job_EarilestThe工件的完工时间Job_FinishT；

j＝j+1；

当(j＜Wait_JobNum)，返回S2；

以最早开工策略为准则确定当次执行的工件任务，并更新AGV释放时间、机器释放时间、工件释放时间；

i＝i+1；

当(i＜TO_Num)，返回S1；

其中，优化目标函数为F＝Cmax；

AGV机器联合调度约束条件：

Cmax≥fi(n+1)

fij≥dij+pij

pi0＝0，pi(m+1)＝0

di(j+1)≥f′ij

d′ij≥fij

δij，lq+δlq，ij＝1

Cpl＝Vpl

其中，n+1表示工件对应的回收工序，其中n表示工件最后一道加工工序，一个工件共有

0，1，2，…，n，n+1道工序；m表示加工设备数量，k为搬运设备总数，H是预定义的一个极大数值；Cpl是AGV将物料从设备p输送到设备1的装载耗时；Vpl是AGV从设备p输送到设备1的空载耗时； 是由编号RS的AGV将工件从设备Mij搬运到设备Mi(j+1)所花费的转载运输耗时；flq是工序任务O1q的完工时间；dlq是工序任务O1q在机器上的开始加工时间；

中的s和k是搬运设备的索引号； 表示搬运设备从工序任务O1q到O1(q+1)的转载运输时间， 表示搬运设备从工序任务O1(q+1)到工序任务Oij的空载运输时间；

表示搬运设

备从工序Oij到Oi(j+1)的转载运输时间；δlq，ij是确定运输任务O1q是否在运输任务Oij之前执行，pij表示Oij的加工时间，Tij：将工件i从工序任务Oij加工设备上运输到工序任务Oi(j+1)加工设备的运输任务，dij：工序任务Oij在机器上的开始加工时间，fij：工序任务Oij在机器上的任务完工时间，f′ij表示搬运任务Tij的搬运完成时间，d′ij表示搬运任务Tij的搬运开始时间。

2.根据权利要求1所述的基于混合遗传算法的作业车间运动轨道路径导向优化方法，其特征在于，AGV的导向路径组成的运输网络即为所述导向路径网络，导向路径网络对应的图为无向图G＝(V，E)，设备和AGV交汇点为顶点为G的顶点，导向路径为G的边，G为连通图；

所述导向路径的约束条件为：

Zab+Zba＝1

其中， 从加工设备Mi到设备Mj的最短运输路径的搬运时间， 从加工设备Mi到设备Mj的最短运输路径的距离，CV：AGV的运输速度，M：加工设备集合M＝{M1，M2，...，Mm}，

3.根据权利要求2所述的基于混合遗传算法的作业车间运动轨道路径导向优化方法，其特征在于，所述导向路径网络为单向导引路径网络，根据所述无向图G＝(V，E)求得满足强连通的有向图D(V，A)；

对于具有n个顶点和w条弧的强有向多重图D＝(V，A)，它的每一个耳朵分解有w‑n+1个耳朵，据此求得有向图D的耳朵分解序列ε＝{P0，P1，P2，P3}。

4.根据权利要求3所述的基于混合遗传算法的作业车间运动轨道路径导向优化方法，其特征在于，初始种群生成算法流程如下：输入为：种群个体数为NP，导向路径网络的无向图G；

输出为：NP个耳朵分解序列ε；

令k＝1；

(Stepl)：

采用图的深度搜索求得顶点标签序，再依据标签序求得一个强连通定向，即G→D；

随机选择D的顶点v，求得D的出分枝，即D→TD；

对于在D中而不在TD中的弧，可求得具有w‑n+1的耳朵分解序列，即TD→ε；

k＝k+1；

当k＜NP，返回Stepl。

5.根据权利要求3所述的基于混合遗传算法的作业车间运动轨道路径导向优化方法，其特征在于，所述基于交叉算子对新的种群进行交叉操作的方法如下：令D＝(V，A)和D′＝(V，A′)分别是无向图G的强连通图，D1＝(V1，A1)为D的子图，D2＝(V′2，A′2)为D′相对D在D1中的差图，则D1和D2的并有向图D1∪ D2为无向图G的强连通图；

1 1 1 1 1 2 2 2 2 2令ε1＝{P0 ，P1 ，P2 ，...，Px ，...，Pt}和ε2＝{P0 ，P1 ，P2 ，...，Px ，...，Pt}分别为有向图D和D′的耳朵分解序列；若x∈[0，t‑1]，保留εl中的前x只耳朵，则可在线性时间内生成新

1 1 1 1 1′ 2 2 2 2的耳朵分解序列ε1′＝{P0 ，P1 ，P2 ，...，Px ，...，Pt }和ε2′＝{P0 ，P1 ，P2 ，...，Px ，...，

2′

Pt ，即两个子代的剩余耳朵。

6.根据权利要求3所述的基于混合遗传算法的作业车间运动轨道路径导向优化方法，其特征在于，

所述基于交叉算子对新的种群进行交叉操作的步骤如下：

1 1 1 1 1 2 2 2

输入：耳朵分解序列ε1＝{P0 ，P1 ，P2 ，...，Px ，...，Pt }和ε2＝{P0 ，P1 ，P2 ，...，

2 2

Px，...，Pt}；

输出：耳朵分解序列ε1′和ε2′；

ε1′＝{}，ε2′＝{}，

生成交叉位置，交叉位置属于[1，w‑n]，即x＝random(w‑n)；

保留父代前x只耳朵，

1 1 1 1 2 2 2 2

即ε1′＝{P0，P1，P2，...，Px}，ε2′＝{P0，P1，P2，...，Px}；

2 2 1 1

ε1′和{Px+1，...，Pt}的弧构成有向图D1，ε2’和{Px+1，...，Pt}的弧构成有向图D2；

求得D1和D2的剩余w+n‑1‑x只耳朵；

得到

1 1 1 1 1′ 2 2 2 2 2′ε1′＝{P0，P1，P2，...，Px，...，Pt }，ε2′＝{P0，P1，P2，...，Px，...，Pt }。

7.根据权利要求6所述的基于混合遗传算法的作业车间运动轨道路径导向优化方法，其特征在于，所述基于变异算子对交叉后的种群进行变异操作的方法如下：‑

令序列ε＝{P0，P1，P2，...，Pt}为强连通有向图D＝(V，A)的一个耳朵序列；P0表示反转P0‑中弧后对应的耳朵，新序列ε′＝{P0，P1，P2，...，Pt}对应的有向图D′为强连通有向图；

‑

令ε＝{P0，P1，...，Pi，...，Pt}为强连通有向图D＝(V，A)的一个耳朵分解序列；Pi (1≤i‑≤t)表示反转Pi中弧对应的耳朵，新序列ε′＝{P0，P1，...，Pi，...，Pt}对应的有向图D′为强连通有向图；

令ε＝{P0，P1，P2，...，Pt}为强连通有向图D＝(V，A)的一个耳朵分解序列；若x∈[v，t]，反转Pi中每一条弧的方向，则所得新的序列对应的有向图为强连通有向图；

所述基于变异算子对交叉后的种群进行变异操作的步骤如下：输入：耳朵分解序列ε＝{P0，P1，P2，...，Px，...Pt}，Xov，Xov为发生变异的概率；

输出：耳朵分解序列ε′；

生成[0，1]区间内的随机数，即per＝random(1)；

如果per＞Xov：

生成[0，w‑n+1]区间内的随机整数，即x＝random(w‑n+1)；

‑ ‑

Px→Px，Px表示反转Px中所有弧后的耳朵；

‑

得到ε′＝{P0，P1，P2，...，Px，...Pt}；

当不满足per＞Xor时，另ε′＝ε。

8.根据权利要求7所述的基于混合遗传算法的作业车间运动轨道路径导向优化方法，其特征在于，若D和D′分别是无向图G的k弧强定向图，则存在G的一个k弧强定向序列D＝D0，D1，...，Dr＝D′，使得每一个i＝1，2，...，r，每一个Di是反转Di‑1中一条路或一个圈的所有弧而产生的有向图；

所述基于RNVS的邻域搜索算法的步骤如下：输入初始解π，已知最好解πbest，最大循环次数Nmax，并令k＝l；

判断k的值，若k小于或等于最大循环次数Nmax，则根据k的值选择相应的邻域动作，若k＝1选择改变圈的方向邻域动作，若k＝2选择改变路的方向的邻域动作，生成新解π*，否则结束当前算法；

计算新解π*的目标函数值OFV(π*)，并与已知最好解得目标函数值OFV(πbest)进行比较，若更优，则更新已知最好解和k的值，否则只更新k的值，重复判断k值步骤。

9.根据权利要求8所述的基于混合遗传算法的作业车间运动轨道路径导向优化方法，其特征在于，所述基于RNVS的邻域搜索算法的步骤如下：输入：可行解π；

输出：局部最优解πbest；

πbest＝π，Nmax＝2，k＝1；

st1：k≤Nmax时：

*

如果k＝1，改变解π中圈的方向，即π＝N1(πbest)；

*

否则，则改变解π中路的方向，即π＝N2(πbest)；

* *

如果OFV(π)＜OFV(πbest)，则πbeset＝π，k＝1；

否则，k＝k+1；

如果k≤Nmax时返回st1。