基于变邻域搜索算法求解矩阵制造车间AGV调度的方法

专利主权项内容

1.一种基于变邻域搜索算法求解矩阵制造车间AGV调度的方法，其特征在于，包括以下步骤，步骤1，初始化变邻域搜索算法参数，设置种群大小Ps，进化过程中的迭代次数 ，重调度策略中的权重参数 />；步骤2，初始化种群，使用最近邻启发式规则生成1个解，使用随机方法生成剩余Ps-1个解，形成包含Ps个解的初始种群，从Ps个解中选择总成本最小的解，作为最佳方案进行更新；步骤3，进入扰动阶段，利用煎饼翻转策略指导解进行邻域扰动，接收总成本更小的解作为新解；煎饼翻转策略包括以下步骤，定义序列为AGV将物料运送到呼叫单元的顺序，其中包括 n个待安排的呼叫单元，从序列中找到序列号最大的呼叫单元，并设序列号最大的呼叫单元下标为 k，k∈[0，n-1] ，对前k+1个呼叫单元进行翻转操作，然后翻转所有呼叫单元，每次迭代都能将序列号最大的呼叫单元置于序列的底部，重复这一过程k次，直至获得新序列；步骤4，进入可变邻域下降阶段，利用同车插入策略和同车交换策略，指导当前解进化，继续接收总成本更小的解作为新解；同车插入策略为，从执行煎饼翻转策略之后的新序列中随机选择一个呼叫单元，并将所选择的呼叫单元/>随机插入当前序列中的一个位置，如果仍找不到总成本更小的解，则执行同车交换策略；同车交换策略为，从执行煎饼翻转策略之后的新序列中随机选择两个呼叫单元，呼叫单元/>，然后交换呼叫单元/>和呼叫单元/>，继续寻找总成本更小的解，重复上述过程 次后，接收此时的解作为当前解；步骤5，进入局部搜索阶段，利用合并策略指导当前解跳出局部最优；为防止陷入局部最优，执行合并策略指导当前解跳出局部最优，合并策略包括以下步骤，根据当前解来确定使用的AGV数量，将当前解中的序列按照呼叫单元的数量进行降序，尝试将降序后的序列中呼叫单元数量少的序列插入到其他序列中，直到无法插入为止，以此得到总成本最小的解；步骤6，判断是否进行重调度，若需要重调度，随机执行快速维修重新安排的重调度策略或改进的最近邻域搜索的重调度策略，若不需要重调度，则继续执行下一步；步骤7，更新总成本最小的解，判断是否达到终止时间，若满足则终止进化，输出当前最佳解的总成本，反之执行步骤3。