多行设备布局的一种多目标差分进化算法和线性规划混合方法  

Combining Multi-objective Differential Evolution Algorithm and Linear Programming for Multiple Row Facility Layout Problem

作　　者：管超 张则强[1,2] 李云鹏[1,2] 贾林[1,2] GUAN Chao;ZHANG Zeqiang;LI Yunpeng;JIA Lin(School of Mechanical Engineering, Southwest Jiaotong University, Chengdu 610031;Technology and Equipment of Rail Transit Operation and Maintenance Key Laboratory of Sichuan Province, Southwest Jiaotong University, Chengdu 610031)

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

出　　处：《机械工程学报》2019年第13期160-174,共15页Journal of Mechanical Engineering

基　　金：国家自然科学基金(51205328,51675450);教育部人文社会科学研究青年基金(18YJC630255);四川省科技计划(2019YFG0285)资助项目

摘　　要：针对现有对多行设备布局研究中预先固定布置行数和未考虑行间距约束的不足,在满足最小间隙约束条件下,构建了优化物料流成本、布局行数和布局占地面积的多目标多行设备布局模型,并运用数学规划软件Lingo对模型进行了精确求解。基于所提问题的多目标、多约束、混合优化特性,提出一种基于Pareto解集的多目标差分进化算法和线性规划混合优化方法。该方法采用四列表直接编码方法表示可行解;提出一种结合改进换行策略的解码方式,该解码方式可以在满足边界约束条件的同时对所有可行的布局方案进行确定;为获得收敛性、分布性良好的多目标布局结果,采用Pareto思想、NSGA-Ⅱ拥挤距离机制筛选外部档案中的非劣解。应用所提算法求解不同规模多行设备布局问题测试算例,比较分析3种差分进化模式对所提方法在求解质量和求解效率方面的影响。最后,将所提模型和求解方法应用至两个布局实例中,不同算法的对比试验表明了所提方法的有效性、优越性。In order to overcome the shortcomings of fixed row number and ignoring spacing constraints between rows in the existing research on multiple row facility layout problem, a multi-objective multiple row facility layout problem model is constructed to optimize material flow cost, layout row number and layout area under the condition of minimum gap constraints, and the model is solved accurately by using Lingo, a mathematical programming software. Based on the multi-objective, multi-constraint and mixed optimization of the proposed problem, a hybrid optimization method of multi-objective differential evolution algorithm and linear programming based on Pareto solution set is proposed. This method uses four-list directly coding method to represent feasible solution, and proposes a decoding method combined with improved line-breaking strategy, which can determine the layout scheme of all possible rows while satisfying boundary constraints. In order to obtain a multi-objective layout result with good convergence and distribution, Pareto method and NSGA-Ⅱ congestion distance mechanism are used to screen external files. The proposed algorithm is applied to solve multiple row facility layout problem with different scales. The effects of three differential evolution modes on the solution quality and efficiency of the proposed method are compared and analysed. Finally, the proposed model and method are applied to two layout examples. The comparative experiments of different algorithms show the effectiveness and superiority of the proposed method.

关 键 词：多行设备布局问题 混合整数非线性规划 改进换行策略 差分进化算法 多目标优化 

分 类 号：TH165[机械工程—机械制造及自动化] TP301[自动化与计算机技术—计算机系统结构]