基于遗传算法的多RGV动态调度方法

摘要

本发明公开了一种基于遗传算法的多RGV动态调度方法，其特征是针对自动化立体仓库输送系统中环形轨道上的多个RGV(Rail Guided Vehicle)在大物流量下的动态调度问题，运用遗传算法建立模型并求解，从而得到调度多个RGV运送出入货任务的优化方案，以此大大提高RGV的运送效率，同时针对具体的问题提出了实用的编码方法，拓展了遗传算方法的应用范围。

主权项

基于遗传算法的多RGV动态调度方法，所述RGV(5)是单向循环运行在自动化立体仓库输送系统环形轨道(8)上的L个RGV；所述自动化立体仓库中，在环形轨道的一侧沿线顺次布置各入货输送带(1)、出货输送带(2)、多层货架(3)和堆垛机(4)，在环形轨道的另一侧沿线顺次布置入货站台(6)、拣选站台(7)、外部物料运送工具(9)和出货站台(10)，其特征是：所述各RGV的动态调度方法按如下步骤进行：第一步、针对所有已经生成的正在等待运送的K个出入货任务，根据要求取出前Q个出入货任务；所述K个出入货任务按照生成的时间顺序排列；所述根据要求是指预先根据历史数据估算出投入全部L个RGV完成运送Q个出入货任务所用时间ty，使ty不超过规定的时间值；若K值大于Q值，则Q值取值不变，若K值小于或等于Q值，则Q值取值等于K值；第二步、任意调整Q个出入货任务的先后顺序，运用遗传算法建立模型并求解得出调度L个RGV运送Q个出入货任务的优化方案：a、种群初始化：将调度L个RGV运送Q个出入货任务的方案定义为个体，对所述个体按如下方式进行编码以获得与个体相对应的染色体：将Q个出入货任务分别用数字1～Q依次编号，将L个RGV分别用数字1～L依次编号；每个染色体是由一上行字符串和一下行字符串所组成，所述上行字符串中的每个字符是在数字1～Q中随机生成，不重复，共生成Q个，每个字符代表对应编号的出入货任务；所述下行字符串与上行字符串的字符位置一一对应，下行字符串中的每个字符随机取自数字1～L，可以重复，共生成Q个，每个字符代表对应编号的RGV；经过N次编码获得N个染色体，以与所述N个染色体相对应的N个个体组成第一代种群，以所述第一代种群作为下一代的父种群，进行选择、交叉和变异遗传操作，N取值为20～100；在所述染色体中，以上行字符串与下行字符串中上下对应位置上的两个字符表征出入货任务的运送为：指派下行字符对应编号的RGV运送上行字符对应编号的出入货任务，若在一个染色体所对应的个体中出现由同一个RGV运送多个出入货任务时，按照出入货任务的编号在上行字符串中的先后顺序依次进行运送；b、选择：分别计算出按照父种群中每个个体运送完毕Q个出入货任务所用的运送时间Ts，以所述运送时间Ts为每个个体的目标函数值，对父种群中的个体按照目标函数值进行降序排列，把个体在父种群中的序位n应用在基于排序的适应度分配方法中的线性排序公式 (1)中，计算出每个个体的适应度值； f i = 2 - p + 2 ( p - 1 ) ( n - 1 ) N - 1 p∈[1.0，2.0]    (1)式(1)中，fi为个体i的适应度值，p为选择压力；把个体i的适应度值fi应用在式(2)中计算出个体i的选择概率Fi，从而计算出每个个体的选择概率； F i = f i Σ i = 1 N f i - - - ( 2 ) 按照式(3)计算出从父种群的N个个体中所要选择的个体数目M后，把每个个体的选择概率应用在随机遍历抽样法中，从父种群中选择出要进行交叉的M个个体，G取值为0.95～0.98；M＝N×G    (3)c、交叉：以选择出的M个个体相对应的M个染色体作为父代染色体，在所述M个染色体中随机进行两两配对，如果M为奇数，最后一个染色体不参加配对，直接成为一个子代染色体；对配对的两个父代染色体的上行字符串按照部分匹配交叉的方法，进行交叉操作，下行字符串保持不变，得到两个子代染色体，对所有配对的染色体全部进行相同的操作，产生M个子代染色体；d、变异：对所述M个子代染色体的下行字符串按照变异概率Pm进行如下变异操作，上行字符串不变：首先在M个子代染色体中的任一个染色体的下行字符串中随机选取一个要变异的字符位置w，然后在区间(0，1)内随机生成一个数字A，如果A小于或者等于Pm，则随机选取数字1～L中的一个数字，替换位置w处的字符；如果A大于Pm，则位置w处的字符不变，染色体的变异完成；对M个子代染色体都进行相同的操作，Pm取值为0.001～0.1；e、重插入：从父种群中选取适应度大的前S个个体相对应的染色体插入经过步骤d操作后的M个子代染色体中，插入的S个染色体相对应的个体和经过步骤d操作后的M个子代染色体相对应的个体共同构成子代种群，种群的遗传代数增加一代，S由式(4)求出；S＝N‑M(4)f、判断：若遗传代数达到终止代数，转到步骤g，否则把步骤e中形成的子代种群作为下一代的父种群转到步骤b开始下一代的遗传操作，终止代数取值为100～500；g、对步骤e中形成的子代种群，计算出按照每个个体运送完毕Q个出入货任务所用的运送时间Ts，确立运送时间Ts最小的个体为调度L个RGV运送Q个出入货任务的最佳方案；第三步、当L个RGV把Q个出入货任务全部运送完毕后，把K个出入货任务中剩余的K‑Q个任务和在L个RGV运送Q个出入货任务的时间内产生的新的出入货任务再次按照出入货任务生成的时间顺序进行排列，重复第一步、第二步和第三步，对L个RGV进行下一次的调度，直至所有等待运送的出入货任务全部运送完成为止，实现对L个RGV的动态调度。