Efficient implementations of construction heuristics for the rectilinear block packing problem

The rectilinear block packing problem is a problem of packing a set of rectilinear blocks into a larger rectangular container, where a rectilinear block is a polygonal block whose interior angle is either 90° or 270°. There exist many applications of this problem, such as VLSI design, timber/glass cutting, and newspaper layout. In this paper, we design efficient implementations of two construction heuristics for rectilinear block packing. The proposed algorithms are tested on a series of instances, which are generated from nine benchmark instances. The computational results show that the proposed algorithms are especially efficient for large instances with repeated shapes.     

A biased‐randomized algorithm for the two‐dimensional vehicle routing problem with and without item rotations

This paper proposes an efficient algorithm, with a reduced number of parameters, for solving the two‐dimensional loading‐capacitated vehicle routing problem (2L‐CVRP). This problem combines two of the most important issues in logistics, that is, vehicle routing and packing problems. Our approach contemplates unrestricted loading including the possibility of applying 90° rotations to each rectangular‐shaped item while loading it into the vehicle, which is a realistic assumption seldom considered in the existing literature. The algorithm uses a multistart approach that is designed to avoid local minima and also to make the algorithm an easily parallelizable one. At each restart, a biased randomization of a savings‐based routing algorithm is combined with an enhanced version of a classical packing heuristic to produce feasible good solutions for the 2L‐CVRP. The proposed algorithm has been compared with the classical benchmarks for two different 2L‐CVRP variants, that is, with and without item rotations. Experimental results show that our approach outperforms several best‐known solutions from previous work, both in terms of quality and the computational time needed to obtain them.     

一种求解矩形块装填问题的拟人算法

在货物装载、木材下料、超大规模集成电路（VLSI）设计等工作中提出了矩形块装填与切割问题，对这一问题，国内外学者提出了诸如模拟退火算法、遗传算法及其它一些启发式算法等求解算法。本文利用人类的智慧和他们上万年以来形成的经验，提出了一种求解矩形块装填问题的拟人算法。谊算法使用了两个主要的思想策略，即矩形块选择策略和矩形块放置策略。用本文提出的算法，对21个测试算例进行了实算测试，测试结果表明：算法所得装填结果的优度高，计算时间短。对这21个测试算例。用本文算法计算，得到了其中16个算例的最优解，而计算时间都在2秒以内。进一步的测试表明，本文提出的算法对求解矩形块装填问题十分有效。     

A heuristic block-loading algorithm based on multi-layer search for the container loading problem

This paper presents an efficient heuristic block-loading algorithm based on multi-layer search for the three-dimensional container loading problem. First, a basic heuristic block-loading algorithm is introduced. This algorithm loads one block, determined by a block selecting algorithm, in one packing phase, according to a fixed strategy, until no blocks are available. Second, the concept of composite block is introduced, the difference between traditional block and composite block being that composite block can contain multiple types of boxes in one block under some restrictions. Third, based on the depth-first search algorithm, a multi-layer search algorithm is developed for determining the selected block in each packing phase, and making this result closer to the optimal solution. Computational results on a classic data set show that the proposed algorithm outperforms the best known algorithm in almost all the test data.     

A new heuristic algorithm for rectangle packing

The rectangle packing problem often appears in encasement and cutting as well as very large-scale integration design. To solve this problem, many algorithms such as genetic algorithm, simulated annealing and other heuristic algorithms have been proposed. In this paper, a new heuristic algorithm is recommended based on two important concepts, namely, the corner-occupying action and caving degree. Twenty-one rectangle-packing instances are tested by the algorithm developed, 16 of which having achieved optimum solutions within reasonable runtime. Experimental results demonstrate that the algorithm developed is fairly efficient for solving the rectangle packing problem.     

General Floorplans with L/T-Shaped Blocks Using Corner Block List

With the recent advent of deep submicron technology and new packing schemes, the components in the integrated circuit are often not rectangular. On the basis of the representation of Corner Block List （CBL）, we propose a new method of handling rectilinear blocks. In this paper, the handling of the rectilinear blocks is simplified by transforming the L/T- shaped block problem into the Mign-abutment constraint problem. We devise the block rejoining process and block alignment operation for forming the L/T-shaped blocks into their original configurations. The shape flexibility of the soft blocks, and the rotation and reflection of L/T-shaped blocks are exploited to obtain a tight packing. The empty rooms are introduced to the process of block rejoining. The efficiency and effectiveness of the proposed method are demonstrated by the experimental results on a set of some benchmark examples.     

求解三维装箱问题的混合模拟退火算法

提出了一个高效求解三维装箱问题(Three Dimensional Container Loading Problem 3D-CLP)的混合模拟退火算法.三维装箱问题要求装载给定箱子集合的一个子集到容器中,使得被装载的箱子总体积最大.文中介绍的混合模拟退火算法基于三个重要算法:(1)复合块生成算法,与传统算法不同的是文中提出的复合块不只包含单一种类的箱子,而是可以在一定的限制条件下包含任意种类的箱子.(2)基础启发式算法,该算法基于块装载,可以按照指定装载序列生成放置方案.(3)模拟退火算法,以复合块生成和基础启发式算法为基础,将装载序列作为可行放置方案的编码,在编码空间中采用模拟退火算法进行搜索以寻找问题的近似最优解.文中采用1500个弱异构和强异构的装箱问题数据对算法进行测试.实验结果表明,混合模拟退火算法的填充率超过了目前已知的优秀算法.     

Deterministic VLSI block placement algorithm using Less Flexibility First principle

In this paper,a simple while effective deterministic algorithm for solving the VLSI block placement problem is proposed considering the packing area and interconnect wiring simultaneously.The algorithm is based on a principle inspired by observations of ancient professionals in solving their similar problems.Using the so-called Less Flexibility First principle,it is tried to pack blocks with the least packing flexibility on its shape and interconnect requirement to the empty space with the least packing flexibility in a greedy manner.Experimental results demonstrate that the algorithm,though simple,is quite effective in solving the problem.The same philosophy could also be used in designing efficient heuristics for other hard problems,such as placement with preplaced modules,placement with L/T shape modules,etc.     

基于离散粒子群优化算法求解矩形件排样问题

改进了一种近似排样算法,并将改进的近似排样算法与离散粒子群优化算法结合求解矩形件排样问题.设计了应用离散粒子群优化算法求解矩形件排样问题的相关操作和定义,给出了离散粒子群优化算法求解矩形件排样问题的详细步骤,最后通过实验测试,验证了算法的有效性.     

Heuristics for two-dimensional strip packing problem with 90° rotations

This paper proposes a deterministic heuristic algorithm (DHA) for two-dimensional strip packing problem where 90° rotations of pieces are allowed and there is no guillotine packing constraint. The objective is to place all pieces without overlapping into a strip of given width so as to minimize the total height of the pieces. Based on the definition of action space, a new sorting rule for candidate placements is proposed such that the position for the current piece is as low as possible, the distance between the current piece and other inside pieces is as close as possible, and the adverse impact for further placements is as little as possible. Experiments on four groups of benchmarks showed the proposed DHA achieved highly competitive results in comparison with the state-of-the-art algorithms in the literature. Also, as a deterministic algorithm, the DHA could achieve high quality solutions by only one independent run on both small-scale and large-scale problem instances and the results are repeatable.     

Logic based Benders' decomposition for orthogonal stock cutting problems

We consider the problem of packing a set of rectangular items into a strip of fixed width, without overlapping, using minimum height. Items must be packed with their edges parallel to those of the strip, but rotation by 90° is allowed. The problem is usually solved through branch-and-bound algorithms. We propose an alternative method, based on Benders' decomposition. The master problem is solved through a new ILP model based on the arc flow formulation, while constraint programming is used to solve the slave problem. The resulting method is hybridized with a state-of-the-art branch-and-bound algorithm. Computational experiments on classical benchmarks from the literature show the effectiveness of the proposed approach. We additionally show that the algorithm can be successfully used to solve relevant related problems, like rectangle packing and pallet loading.     

用于二维不规则排样的离散临界多边形模型

提出了一个用于求解二维不规则排样问题的离散临界多边形模型.Burke等人的BLF算法是求解排样问题的一种有效算法,但其算法对一些特殊实例会产生非法的解.为了解决这个问题,提出了一种基于离散临界多边形模型,并对其正确性作了严格证明.新模型是只含有点和区间的简单模型,在大大降低原问题几何复杂性的同时,也使许多启发式策略可以更容易地求解该问题.计算结果表明,基于离散临界多边型模型的排样算法是很有效的.     

Frictional sliding motion in releasing manipulation

The characteristics of frictional sliding motion in releasing manipulation are discussed in this paper. Releasing manipulation is such a manipulation in which an object obtains its initial translational and rotational velocities by the striking of a manipulator and slides on a surface, and comes to stop at the destination with the desired orientation under the action of friction. First, based on our previous work, the properties of releasing manipulation are described. Second, the conclusion that trajectories of arbitrary shaped objects in sliding motion are nearly rectilinear is presented. Third, a phenomenon of simultaneous stopping of translational and rotational motion for arbitrary shaped objects is clarified. Fourth, motion monotonicity for two extreme cases, i.e. initially translation-dominated motion and initially rotation-dominated motion are discussed; several important original results are obtained. With the above obtained results, two simple approaches of determining the necessary initial velocities for releasing manipulation are naturally developed and their accuracies are confirmed.     

A*算法在Shortest-Path方面的优化研究

在游戏和地理信息系统开发等领域中,专门针对最短路径搜索方面的优化研究较多,尤其是最短路径中启发式搜索算法中的A*算法的效率优化研究.本文将针对在人工智能或算法研究中的使用的地图大多数是基于任意图而不是网格图的状况,通过任意图与网格图及方向的相结合,提出了三种优化A*算法的启发式函数搜索策略,较好地减小了算法搜索的范围和规模,有效地提高了A*算法的运行效率.最后的实验结果显示,与传统的A*算法相比较,优化启发搜索策略后的A*算法寻径更快速,更准确,计算效率更高.     

一种基于密度的文本聚类挖掘算法*

针对DBSCAN算法需用户设置参数值、易产生挖掘结果偏差等不足,提出改进算法DBTC(density-based text clustering),该算法不仅能够发现任意形状的簇,还有效地解决了基于密度的DBSCAN聚类算法在文本挖掘中参数设置困难和高密度的簇被相连的低密度簇包含的问题。理论分析和实验结果表明,算法是有效可行的。     

用于求解二维圆形排样问题的自适应混合算法

针对二维圆形版面不等圆排样问题,在最小局部距离定位布局策略的基础上,引入紧凑度和适应度,提出基于拟矩形排样的自适应启发式算法,并与以自然数编码的遗传算法相结合构建混合算法。该混合算法发挥两者的全局搜索能力与局部寻优能力。在标准测试算例上,与一些经典算法进行比较,结果表明,该算法能够在更短的时间内获得更为满意的结果。     

Exploring Unknown Environments with Obstacles

We study exploration problems where a robot has to construct a complete map of an unknown environment using a path that is as short as possible. In the first problem setting we consider, a robot has to explore n rectangles. We show that no deterministic or randomized online algorithm can be better than Ω(\sqrt n ) -competitive, solving an open problem by Deng et al. [7]. We also generalize this bound to the problem of exploring three-dimensional rectilinear polyhedra without obstacles. In the second problem setting we study, a robot has to explore a grid graph with obstacles in a piecemeal fashion. The piecemeal constraint was defined by Betke et al. [4] and implies that the robot has to return to a start node every so often. Betke et al. gave an efficient algorithm for exploring grids with rectangular obstacles. We present an efficient strategy for piecemeal exploration of grids with arbitrary rectilinear obstacles.     

基于离散粒子群算法的矩形件优化排样

目前,粒子群算法在连续问题优化上的应用已经很广泛,然而在离散问题优化方面仍处在尝试阶段.提出了一种改进粒子群算法来解决矩形件排样优化问题(离散优化问题).该算法融合了遗传算法中的交叉和变异思想,采用了信息交流策略,使其达到快速优化目的.算法也对"最低水平线法"解码方式进行了改进.实验结果表明,该算法具有快速,高效特点,与现有同类算法比较,在解决矩形件排样问题方面的优势明显.     

求解单位等边三角形Packing问题的近似算法

多边形Packing问题不仅具有重要的理论意义，而且也有广阔的应用前景，由于该问题具有NP难度，且具有连续的性质，一般要事先对多边形的放置方位进行限制，例如不允许多边形旋转，然后再进行优化求得近似解，该文采用一种新的思路对多边形Packing问题的一个特例－单位等边三角形Packing问题进行了研究，提出了零自由度动作和零自由度放置策略的概念，并设计了一个近似求解算法－最小损伤法，复杂性分析和计算结果表明该算法是高效的，以此为基础，可能为多边形Packing问题找到类似的求解算法。     

Exploring Unknown Environments with Obstacles

Abstract. We study exploration problems where a robot has to construct a complete map of an unknown environment using a path that is as short as possible. In the first problem setting we consider, a robot has to explore n rectangles. We show that no deterministic or randomized online algorithm can be better than Ω(\sqrt n ) -competitive, solving an open problem by Deng et al. [7]. We also generalize this bound to the problem of exploring three-dimensional rectilinear polyhedra without obstacles. In the second problem setting we study, a robot has to explore a grid graph with obstacles in a piecemeal fashion. The piecemeal constraint was defined by Betke et al. [4] and implies that the robot has to return to a start node every so often. Betke et al. gave an efficient algorithm for exploring grids with rectangular obstacles. We present an efficient strategy for piecemeal exploration of grids with arbitrary rectilinear obstacles.