Abstract: The Closed-Loop Layout Problem (CLLP) is an NP-hard mixed optimization problem, in which an optimal placement order of facilities is found along adjustable rectangle loop with the objection of minimizing the total transport cost of material flow between facilities. In most of the existing methods, meta-heuristic algorithm was used to find the optimal order for the placement of facilities, and enumeration method was applied to find the optimal size of the rectangle loop, which causes extremely low efficiency. To solve this problem, a Hybrid Population-Based Incremental Learning (HPBIL) algorithm was proposed for solving CLLP. In the algorithm, the Discrete Population-Based Incremental Learning (DPBIL) operator and Continuous PBIL (CPBIL) operator were used separately to search the optimal placement order of facilities and the size of rectangle loop at the same time, which improved the efficiency of search. Furthermore, a local search algorithm was designed to optimize some good solutions in each iteration, enhancing the refinement ability. Simulation experiments were carried out on 13 CLLP instances. The results show that HPBIL algorithm finds the best new optimal layouts on 9 instances, and is significantly superior to the algorithms to be compared on the optimization ability for CLLP.

Key words: Population-Based Incremental Learning (PBIL) algorithm, Closed-Loop Layout Problem (CCLP), hybrid optimization, local search algorithm, meta-heuristic method

摘要： 闭环布局问题（CLLP）是一种NP-困难的混合优化问题，它在大小可调的矩形环上寻找设施最佳放置次序，目标是最小化设施之间物料流的运输成本。现有方法均采用元启发式算法来寻找最优的设施放置次序，并且通过枚举方法来获得最优的矩形环大小，而枚举方法的计算效率不高。为了解决这个问题，提出了求解CLLP的混合群体增量学习（HPBIL）算法，分别使用离散群体增量学习（DPBIL）算子和连续PBIL（CPBIL）算子同时对设施放置次序和矩形环大小进行优化，提高了搜索效率；同时还设计了一个局部搜索算法来优化每代中的部分优质解，以提高算法的求精能力。在13个CLLP测试实例上进行实验，结果表明HPBIL算法在9个测试实例上找到了新的最优布局，它对CLLP的寻优能力明显优于对比算法。

关键词: 群体增量学习算法, 闭环布局问题, 混合优化, 局部搜索算法, 元启发式方法