矩形布局的启发式优化策略

利用可行域算法求解矩形布局问题,通过调整矩形布入形态,改变其单一的可行域形式增大其解空间。算例结果表明,矩形调整对布局结果影响有规律,利用可行域算法求解矩形布局问题,简便、快捷、灵活、适应性强,从而能够灵活快速地获得更优异的矩形布局排布方案指导工程实践。     

Bandwidth allocation algorithm for aggregated tree in optical networks

Wavelength and bandwidth allocation is important for multicast communication in optical networks. In this paper, a new method based on scheduling theory is proposed. The proposed method formulates wavelength bandwidth capacity as a large rectangle and these multicast stream bandwidth requirements as small rectangles. It treats the wavelength and bandwidth allocation question as a rectangle packing problem. The proposed algorithm solves the problem by taking quasi-human strategy with Euclidian distance. It is an effective heuristic algorithm to quickly solve multicast stream bandwidth allocation problem in optical networks by theoretic analysis. Further simulation experiments show the bandwidth allocation algorithm can increase network utilization and have a good fairness performance for unicast stream and multicast stream in optical networks. The results indicate the effectiveness of the algorithm.     

矩形布局空间的处理及优化研究

针对矩形布局中的空间处理问题,根据布局空间的结构特点及变化规律,提出采用可行域算法求解矩形布局问题,并利用Visual C＋＋6.0编程工具开发出具有实用意义的矩形智能布局系统。实例表明,该方法可以提高矩形布局问题的求解效率。     

回溯算法求解TSP问题的改进

回溯法构成的解空间树中存在着大量的重复解,降低了搜索的效率．该文在阐述回溯算法基本思想的基础上,运用解路径反转。找出其重复解,然后从解空间树中将其删除的方法对四溯算法加以改进,改进后的算法空间复杂度只有O（n）,并省掉了重复路径的权值计算,节省了搜索时间,提高了搜索效率．     

集装箱装箱的一种拟物拟人算法

本文对集装箱装箱问题,利用最大穴度优先原则,提出了一种新的拟物拟人算法,使放入集装箱中的长方体尽可能紧凑的排列,从而提高集装箱空间的利用率。     

整数可分离凹规划问题的一个线性规划松弛定界算法

给出了整数可分离凹规划问题的一个线性规划松弛定界算法,该算法中的分枝过程是简单的整矩形二剖分过程,定上界是简单的启发式方法,而定下界过程需要解一个线性规划松弛问题来确定的,数值实验表明所提出的算法是有效的,它可以求解中等规模的问题.     

条形装箱问题的基于后缀表达式的混合遗传算法

装箱问题作为一种常见的运筹问题,在很多领域有着重要的应用,装箱问题可以分为一维、二维和三维装箱.主要讨论了二维装箱中条形装箱问题的遗传算法的求解,其中采用后缀表达式的形式对装箱方案进行编码,并详细提出了解码的算法和有关的证明,最后通过实例证明了该算法是可行的.     

射线法判断点与多边形内外关系的改进算法

射线法是判断点与多边形内外关系的最基本有效的方法,但射线法要伴随着大量的求交点运算以及异常情况处理。本文从点引一条线段代替射线,对多边形的边构建最小外接矩形,分析线段与外接矩形的关系,成功判断点与多边形内外关系,避免了求交点运算以及异常处理。该算法易于理解,运算简单,效率高。     

供电网络优化的逐次改善算法

对供电网络优化设计提出了一种新算法。把供电网络优化设计问题抽象成图论问题，应用图论最优化方法解决该问题。同时提出了多边形变换的方法，对供电网络逐次优化，阳终得到一个费用最小化网络。     

多方法融合的特征点匹配算法

将传统相似三角形匹配方法和快速二维聚类匹配方法进行融合,再利用基于灰度的方法对部分伪匹配三角形进行剔除,实现了一种新的抗旋转、缩放的特征点匹配算法．融合后的算法对有效点的要求降低,同时通过在复数向量空间中进行相似三角形检索及参数聚类,提高了算法的效率．     

Quality of Service Routing Strategy Using Supervised Genetic Algorithm

Genetic algorithms (GAs) can deal withcomplex optimization problems better thantraditional optimization techniques[1,2]. The use ofGAs for optimization tasks has become popular withthe constant development of new algorithms,theoretical achievement and nov…     

Simulated Annealing Algorithm and Its Application in Irregular Polygons Packing

Two-dimensional irregular polygons packing problem is very difficult to be solved in traditional optimal way.Simulated annealing (SA) algorthm is a stochastic optimization technique that can be used to solve packing problems.The whole process of SA is introduced firstly in this paper,An extended neighborhood searching method in SA is mainly analyzed,A general module of SA algorithm is given and used to lay out the irregular polygons.The judgment of intersection and other constrains of irregular polygons are analyzed,Then an example that was used in the paper of Stefan Jakobs is listed .Results show that this SA algorithm shorterns the computation time and improves the soluiton.     

Layer-layout-based heuristics for loading homogeneous items into a single container

The container loading problem (CLP) is a well-known NP-hard problem. Due to the computation complexity, heuristics is an often-sought approach. This article proposes two heuristics to pack homogeneous rectangular boxes into a single container. Both algorithms adopt the concept of building layers on one face of the container, but the first heuristic determines the layer face once for all, while the second treats the remaining container space as a reduced-sized container after one layer is loaded and, hence, selects the layer face dynamically. To handle the layout design problem at a layer's level, a block-based 2D packing procedure is also developed. Numerical studies demonstrate the efficiency of the heuristics.     

Heuristic algorithm based on the principle of minimum total potential energy （HAPE）： a new algorithm for nesting problems

We present a new algorithm for nesting problems. Many equally spaced points are set on a sheet, and a piece is moved to one of the points and rotated by an angle. Both the point and the rotation angle constitute the packing attitude of the piece. We propose a new algorithm named HAPE (Heuristic Algorithm based on the principle of minimum total Potential Energy) to find the optimal packing attitude at which the piece has the lowest center of gravity. In addition, a new technique for polygon overlap testing is proposed which avoids the time-consuming calculation of no-fit-polygon (NFP). The detailed implementation of HAPE is presented and two computational experiments are described. The first experiment is based on a real industrial problem and the second on 11 published benchmark problems. Using a hill-climbing (HC) search method, the proposed algorithm performs well in comparison with other published solutions.     

基于简单多边形相邻凹点关系的凸剖分算法

目的:对简单多边形的三角剖分问题中的凸剖分问题,给出一种优化的算法。方法:利用简单多边形相邻凹点连线之间的关系,对简单多边形进行分类,采用递归分解的方法,实现简单多边形的凸剖分。结果:设计的算法每次分解可以获取多个子多边形,递归分解的次数少,每次分解前求交次数方面也优于参考文献[1]。结论:设计的算法简明实用,效率高,时间复杂度为O(n)。     

结合Delaunay三角网的自适应多尺度图像重叠域配准方法

为改进随机采样一致性算法模型参数估计可能不是最优导致图像特征点配准率不高的问题,缩短特征点提取时间,提出一种结合Delaunay三角网格约束的自适应多尺度图像重叠域配准方法。采用自适应通用加速分割检测算法,快速检测出均匀稳定的特征点,并且用二进制特征描述子解决尺度不变性和旋转不变性问题。因传统随机采样一致性算法阈值选取和迭代次数的局限性,会掺杂部分难筛的误配点,在此前提下借助Delaunay算法剖分粗匹配点集,遍历计算网格间对应三角形相似度并储存在相似性度量矩阵中。依据Delaunay三角网特性,剔除相似度差异大的三角形,重构网格保存余下的匹配点集。实验结果表明,该方法特征点提取速率比FAST快15%~20%,特征点正确配准率比随机采样一致性算法提高约4.9%,不仅可自适应多尺度快速提取特征点,而且在保证特征点正确配准率基础上尽量多地保留有效特征点数量。     

三角形packing问题中零自由度动作的分类

三角形packing问题中三角形可以进行连续平移和旋转,如果不对三角形放置动作进行限制,则计算将无法实现。本文提出了零自由度动作概念,并对它进行了详细的分类,为求解三角形Packing问题建立了一个接近客观情况的模型。     

An integrated approach for modeling and solving the scheduling problem of container handling systems

INTRODUCTION Worldwide container trade has grown 9.5% per year last decade and will continue to do so at an 8% growth rate in the coming years (James et al., 1997), so container terminals have to handle containers more efficiently. Fig.1 shows a typical container terminal layout composed of “Quayside area” and “Storage yard”. Many optimization problems associated with a container terminal have been extensively studied in the past few years. Vis and De Koster (2003) gave a comprehens…     

注塑件最小包围矩形算法的研究

运用任意二维多边形顶点环描述了最小包围矩形的算法，给出了数据结构的链表形式和计算最小包围矩形的程序流程图，为注塑件最小包围盒的计算奠定了基础。     

Algorithm for 2D irregular-shaped nesting problem based on the NFP algorithm and lowest-gravity-center principle

INTRODUCTION 2D irregular-shaped nesting problem is the problem of finding an efficient arrangement for pieces in a containing region without overlapping (Fig.1), and is aimed at maximizing use of material. Nesting problem is of great interest to garment, paper, ship building, and sheet metal industries since small improvement of layout can lead to large savings in material. Many effective solutions have been pro- posed for the case when pieces and containing region are both rectangular. …