A new heuristic algorithm for the circular packing problem with equilibrium constraints

The circular packing problem with equilibrium constraints is an optimization problem about simplified satellite module layout design.A heuristic algorithm based on tabu search is put forward for solving this problem.The algorithm begins from a random initial configuration and applies the gradient method with an adaptive step length to search for the minimum energy configuration.To jump out of the local minima and avoid the search doing repeated work,the algorithm adopts the strategy of tabu search.In the pr...     

基于禁忌搜索的启发式算法求解带平衡约束的圆形装填问题

带平衡约束的圆形装填(Packing)问题是一类简化的卫星舱布局优化问题.现提出一个基于禁忌搜索的启发式(TSH)算法对该问题进行求解.算法从任一初始格局出发,应用基于自适应步长的梯度法进行能量极小化.为了使计算能有效地逃离局部极小点的陷阱且避免迂回搜索,算法采用了禁忌搜索的策略.在禁忌搜索的过程中,我们对传统的邻域解、禁忌对象以及当前解接受原则进行了有效的改进.对两组共11个有代表性的算例进行了实算.计算结果表明,TSH算法刷新了其中7个算例的当今国际上的最好纪录,对于其余4个算例,该算法均达到问题的最优解.     

人工蜂群算法在带约束圆形布局问题中的应用

人工蜂群算法是一种基于蜜蜂采蜜机制的新型演化算法。给出了带平衡约束的圆形布局问题的数学模型,介绍了人工蜂群算法的基本过程以及计算流程,将人工蜂群算法应用于带平衡约束的圆形布局优化中。通过两个实例进行仿真计算,并将计算结果与文献结果比较,验证了人工蜂群算法是解决此类问题的一种有效且实用的群智能算法。     

A coarse-to-fine quasi-physical optimization method for solving the circle packing problem with equilibrium constraints

This paper addresses an important extension of the circle packing problem (CPP), the circle packing problem with equilibrium constraints (CPPEC). It considers the dense packing of n circular disks in a large circular container at the same time satisfying the equilibrium constraints. Under the industrial background of the layout design on satellite modules, this NP-hard global optimization problem is important in both theory and practice. We introduce two new quasi-physical models for solving CPPEC in this paper. One is to mimic the elastic movement driven by repelling forces from extruded disks, the other is to simulate a whole translation movement of the disks driven by a pulling force from an imaginative elastic rope connecting the centroid of the disks and the center of the container. Then, inspired by the coarse-to-fine control strategy in the manufacture industry, we propose a coarse-to-fine quasi-physical (CFQP) optimization method that adopts the two quasi-physical models for the quasi-physical descent procedure and combines a basin hopping with tabu method for the search procedure. In this way, not only could CFQP take into account the diversity of the search space to facilitate the global search, but it also does fine search to find the corresponding local minimum in a promising local area. Experiments were on two sets of 11 representative test instances. Computational results showed that CFQP achieved new and better results on four instances, at the same time it matched the current best records on the other six (accurate to 0.0001). Moreover, CFQP resulted in smaller equilibrium deviations than that of others published in the literature. In addition, we generated 34 new CPPEC instances basing on the CPP benchmarks, and provided computational results on the two sets of 34 new CPPEC instances, and the container radii obtained are close to the published results on CPP.     

用蚁群算法求解带平衡约束的圆形布局问题

采用启发式方法结合演化算法的思路求解带平衡约束的圆形布局问题.首先对传统优化模型进行调整,并探讨了调整的合理性;然后设计一种分步定位的布局方法,在此基础上利用蚁群算法寻优;最后利用局部搜索技术,在传统模型意义下对布局进行了改进.数值实验表明,算法的性能比目前已有的结果有较大的提高.     

求解online packing problem的F-B绝对近似算法

FF算法由于其在线特性在处理在线装箱问题得到广泛使用,但它无法预测后面达到物品造成装箱率低,提出一种预留一定比例的各类未装满箱体的装箱算法。首先对未装满箱体分类并给出相应的数据结构,接着设计一种绑定配对策略来预留各类未装满箱体数目,并引入间隔函数控制新箱体的启用,最后基于FF算法结合预留策略对物品进行装箱来保证装箱的绝对近似比。提出了一种预留绑定配对策略为后续输入物品提供预测空间,特别的是F-B算法能得到5/3的绝对近似比。     

矩形件三阶段带排样问题的遗传算法

采用混合遗传算法求解矩形件带排样问题,采用三阶段排样方式以满足特定的约束或简化切割工艺。改进遗传算子,在变异操作之后使用调整操作,以进一步简化得到的排样方案。在初始种群构造时,根据矩形件的特性采用一些简单有效的方法,使结果更好更快地收敛。实验结果表明方法对解决这类问题是有效的。     

New heuristics for packing unequal circles into a circular container

We propose two new heuristics to pack unequal circles into a two-dimensional circular container. The first one, denoted by A1.0, is a basic heuristic which selects the next circle to place according to the maximal hole degree rule. The second one, denoted by A1.5, uses a self look-ahead strategy to improve A1.0. We evaluate A1.0 and A1.5 on a series of instances up to 100 circles from the literature and compare them with existing approaches. We also study the behaviour of our approach for packing equal circles comparing with a specified approach in the literature. Experimental results show that our approach has a good performance in terms of solution quality and computational time for packing unequal circles.     

基于粗精调技术的求解带平衡约束圆形Packing问题的拟物算法

带平衡约束的圆形Packing问题是以卫星舱布局为背景的具有NP难度的布局优化问题.文中建立了此问题相应的数学模型,同时提出了两个新的物理模型,并受工艺加工过程中“粗精加工”现象的启发,提出了基于粗精调技术的拟物算法QPCFA.该算法既兼顾了搜索空间的多样性以利于全局搜索,又能对有前途的局部区域进行精细搜索以找到相应的局部最优解.同时,在计算过程中引入禁忌技术和跳坑策略,以提高算法的求解质量.对国际上11个代表性的算例进行了计算,QPCFA更新了其中7个算例的最好记录,其余4个与目前的最好记录基本持平,且与目前的最好结果相比在计算精度上均有较大的提高.     

A pure quasi-human algorithm for solving the cuboid packing problem

We excavate the wisdom from an old Chinese proverb “gold corner, silver side and strawy void”, and further improve it into “maximum value in diamond cave” for solving the NP-hard cuboid packing problem. We extract, integrate and formalize the idea by west modern mathematical tools, and propose a pure quasi-human algorithm. The performance of the algorithm is evaluated on two sets of public benchmarks. For 100 strongly heterogeneous difficult benchmarks, experiments show an average packing utilization of 87.31%, which surpasses current best record reported in the literature by 1.83%. For 47 difficult benchmarks without orientation constraint, experiments show an average volume utilization of 92.05%, which improves current best record reported in the literature by 1.05%. Supported by the National Natural Science Foundation of China (Grant No. 60773194), the National Basic Research Program of China (Grant No. 2004CB318000), and Postdoctoral Science Foundation of China (Grant No. 20070420174)     

A least wasted first heuristic algorithm for the rectangular packing problem

The rectangular packing problem is to pack a number of rectangles into a single large rectangular sheet so as to maximize the total area covered by the rectangles packed. The paper first presents a least wasted first strategy which evaluates the positions used by the rectangles. Then a random local search is introduced to improve the results and a least wasted first heuristic algorithm (LWF) is further developed to find a desirable solution. Twenty-one rectangular-packing instances are tested by the algorithm developed, the experimental results show that the presented algorithm can achieve an optimal solution within reasonable time and is fairly efficient for dealing the rectangular packing problem. LWF still performs well when it is extended to solve zero-waste and non-zero-waste strip packing instances.     

A hybrid simulated annealing metaheuristic algorithm for the two-dimensional knapsack packing problem

The rectangle knapsack packing problem is to pack a number of rectangles into a larger stock sheet such that the total value of packed rectangles is maximized. The paper first presents a fitness strategy, which is used to determine which rectangle is to be first packed into a given position. Based on this fitness strategy, a constructive heuristic algorithm is developed to generate a solution, i.e. a given sequence of rectangles for packing. Then, a greedy strategy is used to search a better solution. At last, a simulated annealing algorithm is introduced to jump out of the local optimal trap of the greedy strategy, to find a further improved solution. Computational results on 221 rectangular packing instances show that the presented algorithm outperforms some previous algorithms on average.     

基于模拟退火算法的布局问题研究

在传统模拟退火算法的基础上,对布局问题的优化算法进行了研究,采用回火策略,改进一般模拟退火算法寻优的效果;结合布局问题的具体特点,采用Sequence Pair来描述布局问题的解结构,综合构成了一种新的求解布局问题的模拟退火算法.通过算例验证,该算法优于传统优化算法和普通启发式搜索算法,并且对增量布局也能够取得较好的效果.     

Note on: An improved algorithm for the packing of unequal circles within a larger containing circle

This note proposed an improved version of the algorithm proposed by Wang et al. [Wang, H. Q., Huang, W. Q., Zhang, Q., & Xu, D. M. (2002). An improved algorithm for the packing of unequal circles within a larger containing circle. European Journal of Operational Research, 141, 339–347] for solving the disk packing problem with equilibrium constraints. An efficient strategy of accelerating the search process is introduced in the gradient method to shorten the execution time. A number of computational results are presented, showing the effectiveness of the proposed method.     

双约束Logit随机交通均衡问题的有效算法

依据现实交通网络中路段容量与出行终点停车容量空间有限性的特征,建立带路段流量和终点需求双约束的Logit随机用户均衡问题的不动点模型,设计了一种有效的Lagrangian乘子法来求解,通过合理调整Lagrangian乘子使算法快速趋于收敛。在算法的迭代过程中,对通常Logit均衡问题则设计改进的自适应相继加权平均法来求解,使路段流量不超过相应路段容量并避免了繁琐的路线枚举,改进了算法的计算效率。数值实验验证了算法的有效性和结果的可行性。     

A dynamic programming algorithm for tree-like weighted set packing problem

In hierarchical organizations, hierarchical structures naturally correspond to nested sets. That is, we have a collection of sets such that for any two sets, either one of them is a subset of the other, or they are disjoint. In other words, a nested set system forms a hierarchy in the form of a tree structure. The task assignment problem on such hierarchical organizations is a real life problem. In this paper, we introduce the tree-like weighted set packing problem, which is a weighted set packing problem restricted to sets forming tree-like hierarchical structure. We propose a dynamic programming algorithm with cubic time complexity.     

带平衡约束矩形布局优化问题的深度强化学习算法

带平衡约束的矩形布局问题源于卫星舱设备布局设计,属于组合优化问题。深度强化学习利用奖赏机制,通过数据训练实现高性能决策优化。针对布局优化问题,提出一种基于深度强化学习的新算法DAR及其扩展算法IDAR。DAR用指针网络输出定位顺序,再利用定位机制给出布局结果,算法的时间复杂度是O（n³）;IDAR算法在DAR的基础上引入迭代机制,算法时间复杂度是O（n⁴）,但能给出更好的结果。测试表明DAR算法具有较好的学习能力,用小型布局问题进行求解训练所获得的模型,能有效应用在大型问题上。在两个大规模典型算例的对照实验中,提出算法分别超出和接近目前最优解,具有时间和质量上的优势。     

Self-adaptive metaheuristics for solving a multi-objective 2-dimensional vector packing problem

In this paper, a multi-objective 2-dimensional vector packing problem is presented. It consists in packing a set of items, each having two sizes in two independent dimensions, say, a weight and a length into a finite number of bins, while concurrently optimizing three cost functions. The first objective is the minimization of the number of used bins. The second one is the minimization of the maximum length of a bin. The third objective consists in balancing the load overall the bins by minimizing the difference between the maximum length and the minimum length of a bin. Two population-based metaheuristics are performed to tackle this problem. These metaheuristics use different indirect encoding approaches in order to find good permutations of items which are then packed by a separate decoder routine whose parameters are embedded in the solution encoding. It leads to a self-adaptive metaheuristic where the parameters are adjusted during the search process. The performance of these strategies is assessed and compared against benchmarks inspired from the literature.