基于改进麻雀搜索算法的平行行排序问题  

Parallel row ordering problem based on improved sparrow search algorithm

作　　者：张则强[1,2] 王灿 刘俊琦[1,2] 计丹 刘思璐 ZHANG Ze-qiang;WANG Can;LIU Jun-qi;JI Dan;LIU Si-lu(School of Mechanical Engineering,Southwest Jiaotong University,Chengdu 610031,China;Technology and Equipment of Rail Transit Operation and Maintenance Key Laboratory of Sichuan Province,Southwest Jiaotong University,Chengdu 610031,China)

机构地区：[1]西南交通大学机械工程学院,成都610031 [2]西南交通大学轨道交通运维技术与装备四川省重点实验室,成都610031

出　　处：《吉林大学学报（工学版）》2024年第7期1851-1861,共11页Journal of Jilin University:Engineering and Technology Edition

基　　金：国家自然科学基金项目(52375268,52342505);教育部人文社会科学研究规划基金项目(23YJA630139);河北省自然科学基金项目(E2024105031);中央高校基本科研业务费专项资金项目(2682023CX009);四川省自然科学基金项目(2024NSFSC1048,2022NSFSC0449)。

摘　　要：针对平行行排序问题中的物流交互点位置问题,以车间布局为研究背景,提出了具备物流交互点及两行间距的平行行排序问题。以最小物流成本为目标,构建了混合整数规划模型,并运用Lingo求解器对小规模算例进行求解验证。结合问题特性,提出了一种改进的麻雀搜索算法。该算法采用佳点集初始化种群,使种群更具多样性,同时对警惕者数量动态变化,结合PMX交叉算子、连续2-opt算子、插入算子等操作加快求解速度,加入提前终止规则,减少冗余迭代次数。将本文算法与麻雀搜索算法、模拟退火算法、遗传算法等进行对比验证,用于求解25~49不同规模算例,结果表明本文算法在求解质量和求解速度上均具有一定优势。将本文算法应用在某生产车间布局中,对车间布局进行优化,改进后的布局降低了32.40%的物流成本,表明了本文模型及算法的有效性。Aiming at the lack of research on the parallel row ordering problem(PROP)of logistics interaction points,the PROP considering logistics interaction point and corridor width was proposed by taking workshop layout as the research background.A mixed-integer programming model with the goal of minimizing logistics costs was constructed.The solutions of a small-scale example were verified by Lingo solver.An improved sparrow search algorithm(ISSA)was proposed by combining the problem characteristics.The good point set was introduced for population initialization to make the population more diverse.The number of vigilants were changed dynamically by proposed algorithm,and algorithm performance was improved by combining operations such as PMX crossover operator,continuous 2-opt operator,and insertion operator.Early termination rule was applied to reduce redundant iterations.By comparing the ISSA with sparrow search algorithm,simulated annealing algorithm and genetic algorithm to solved 25-49 cases,it showed that ISSA has certain advantages in solution quality and solution speed.Finally,the proposed ISSA was applied to a production workshop layout in PROP mode,and the workshop layout was optimized.The results showed that the improved layout reduces the logistics cost by 32.40%,indicating the effectiveness of the proposed model and algorithm.

关 键 词：机械工程 平行行排序问题 物流交互点 麻雀搜索算法 

分 类 号：TH181[机械工程—机械制造及自动化]