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

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

针对现有关于通道宽度对过道布置问题影响研究的不足,以最小化物料搬运成本和通道长度为目标,提出了考虑通道宽度的双目标过道布置问题,并建立了该问题的混合整数规划模型。鉴于该问题具有的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.