扩展双目标过道布置问题的建模与求解方法  

Modeling and optimizing method for expanding bi-objective corridor allocation problem

作　　者：管超 张则强[1,2] 贾林[1,2] 刘思璐 GUAN Chao;ZHANG Zeqiang;JIA Lin;LIU Silu(School of Mechanical Engineering, Southwest Jiaotong University, Chengdu 610031, China;Sichuan Provincial Key Laboratory of Technology and Equipment of Rail Transit Operation and Maintenance,Southwest Jiaotong University,Chengdu 610031,China)

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

出　　处：《计算机集成制造系统》2019年第10期2513-2538,共26页Computer Integrated Manufacturing Systems

基　　金：国家自然科学基金资助项目（51205328,51675450）;教育部人文社会科学研究青年基金资助项目（18YJC630255）;四川省科技计划资助项目（2019YFG0285）;西南交通大学博士创新基金资助项目（G-CX201910）~~

摘　　要：针对现有关于通道宽度对过道布置问题影响研究的不足,以最小化物料搬运成本和通道长度为目标,提出了考虑通道宽度的双目标过道布置问题,并建立了该问题的混合整数规划模型。鉴于该问题具有的NP-hard组合优化特性,提出一种基于Pareto占优的遗传变邻域算法。引入Pareto思想、拥挤距离机制对多目标结果进行处理,设计并对比了4种新生代种群产生方式以提高算法收敛性,将寻优过程中自适应转换搜索深度和搜索广度的变邻域搜索结构嵌入到遗传算法中,在个体完成遗传算法的并行操作之后继续执行变邻域搜索。通过对比所提算法与GUROBI数学规划方法对33个测试算例的运算结果,验证了算法的有效性。最后,应用该算法求解未考虑通道宽度的双目标过道布置问题,不同算法的对比实验表明了所提算法的先进性。Aiming at the short comings of the existing research on the influence of corridor width about the corridor allocation problem, a bi-objective corridor allocation problem considering corridor width was proposed that aiming at minimizing the total logistics cost and corridor length, and a mixed integer programming model was established as well. Due to the complexity of NP-hard problem, a genetic algorithm with variable neighborhood search based on Pareto dominance was designed. the design of Four new population generation method was designed for improving the algorithm's convergence, and the variable neighborhood search was embedded in the algorithm that could transform search depth and width of the neighborhood adaptively which could individual continue the variable neighborhood search after the genetic parallel operation. Through comparing the solution obtained by GUROBI mathematical programming method to the proposed algorithm, the validity of the algorithm was verified by the results of 33 test cases. The proposed algorithm was used to solve the problem of bi-objective corridor allocation problem without considering the width of the corridor, and the comparison experiment of different algorithms illustrated the modernity of the proposed algorithm.

关 键 词：多目标优化 过道布置问题 混合整数规划模型 遗传变邻域搜索 PARETO占优 

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