Abstract: Aiming at the influence of land cost factor and site area constraint on the desperately desire for multi-layer corridor allocation,a double-layer corridor allocation problem was proposed,and its mixed integer programming model was constructed.By considering the layout in two layers of space,the cargo ladder was added as an interactive channel between facilities in different levels.A heuristic algorithm based on C2Opt neighborhood search was proposed,which involved inversion program to generate the perturbation.The current facility sequence was reordered in an inverted way,so the local optimal could be avoided,and the elite solutions were reserved through an operation with memory function on in the neighborhood searching process.The accurate solution of 28 benchmark problems (from 9 to 49 facilities) was acquired via Lingo software,and then heuristic algorithm was used to test the selected questions and compared with the results of the other three heuristic algorithms.The superiority of the proposed algorithm in solution quality and calculation time was verified.

Key words: double-layer corridor allocation problem, C2Opt, mixed integer programming model, accurate solution, heuristic algorithms

摘要： 针对布局活动中为节约用地成本设施被迫布置在多层空间的情况,提出双层过道布置问题,并构建了该问题的混合整数规划模型。该模型考虑了设施在两层空间的布置优化,且不同层设施之间存在物流交互,交互通道为放置在过道最左边的货梯。针对该问题,提出一种基于C2Opt邻域搜索的启发式算法,同时引入inversion程序产生扰动,采用倒置的方式重新排列当前设施序列,以避免算法陷入局部最优,并设置了最优设施序列的记忆功能,以保留邻域搜索过程中的精英解。基于建立的混合整数规划模型,运用Lingo软件对28个测试问题(9~49个设施)进行了精确求解,进而应用所提启发式算法对所选测试算例进行测试,并与3种启发式算法的求解结果进行对比,结果表明所提启发式方法在求解质量和计算时间上均有良好表现。

关键词: 双层过道布置问题, C2Opt, 混合整数规划模型, 精确求解方法, 启发式算法