正三角形容器内等圆Packing问题的启发式算法

等圆Packing问题研究如何将n个单位半径的圆形物体互不嵌入地置入一个边长尽量小的正三角形容器内,作为一类经典的NP难度问题,其有着重要的理论价值和广泛的应用背景.模拟退火算法是一种随机的全局寻优算法,通过将启发式格局更新策略与基于梯度法的局部搜索策略融入模拟退火算法,并与二分搜索相结合,提出一种求解正三角形容器内等圆Packing问题的启发式算法.该算法将启发式格局更新策略用来产生新格局和跳坑,用梯度法搜索新产生格局附近能量更低的格局,并用二分搜索得到正三角形容器的最小边长.对41个算例进行测试的实验结果表明,文中算法改进了其中38个实例的目前最优结果,是求解正三角形容器内等圆Packing问题的一种有效算法.     

求解圆形Packing问题的一个启发式算法

求解NP难度问题一直是计算机科学技术中的一个瓶颈任务,自20世纪70年代以来的研究表明,求解NP难度问题不存在既完整严格又不大慢的求解算法,因此,近年来,启发式方法成为研究热点,圆形Packing问题是NP难的,具有很高的理论和实践价值,它的求解目标是录求多个圆在一个大圆内的一个优良布局,使得这些圆互不重叠地放置,基于拟物法以及适者生存启发式思想,为圆形Packing问题的快速求解提出了一个高效的启发式算法,算法的高效性通过计算实例得到了验证。     

一种求解圆形Packing问题的模拟退火算法?

为求解矩形区域内的圆形Packing问题,提出一种启发式模拟退火算法。寻求多个圆在一个矩形区域内的优良布局,使这些圆两两互不嵌入地放置。算法从任一初始构形出发,采用模拟退火(SA)算法进行全局寻优,在SA执行过程中,应用基于自适应步长的梯度法进行局部搜索,同时介绍一些启发式策略。对2组共20个算例进行实算测试,计算结果证明了该算法的有效性。     

一种解决矩形布局问题的启发式快速算法

针对二维矩形Packing问题,提出了一种沿阶梯线轮廓进行布局矩形的启发式算法.该算法基于"阶梯式堆码"的启发式规则,能够快速地对矩形块进行紧靠布局.为避免算法陷入局部最优,算法采用随机回溯策略在选择矩形和阶位上扩大搜索范围.结果表明,算法对于浪费面积为零的矩形全Packing问题,能够在极短的时间内找到最优解,同时它也可以很好地求解非零浪费问题.采用国际公认的两个算例进行测试,证明文中算法是非常高效的.     

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

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

求解矩形Packing问题的砌墙式启发式算法

为求解正交矩形Packing问题提出了一个新颖而有效的砌墙式启发式算法.该算法主要基于砌墙式启发式策略,其思想主要来源于砖匠在砌墙过程中所积累的经验:基于基准砖的砌墙规则.对国际上公认的大量的Bench-mark问题例的计算结果表明,该算法的计算速度不仅比著名的现代启发式算法快,而且获得更优的高度.     

求解二维矩形Packing面积最小化问题的动态归约算法

二维矩形Packing 面积最小化问题(rectangle packing area minimization problem,简称RPAMP)是具有NP难度的高复杂度的布局优化问题,也是大规模集成电路设计中floorplanning 问题的一个核心问题.通过动态构造矩形框的宽和高,将求解一个RPAMP 转化为求解一组二维矩形Packing 判定问题(rectangle packing decision problem,简称RPDP).在求解RPDP 的最大适配度算法的基础上,进一步考虑了当前动作对全局紧凑性的影响,评估了当前动作对局部空间的损害程度,设计了求解RPDP 的最小损害度算法.然后,结合矩形框宽、高的动态构造方法,设计得到求解RPAMP 的最终算法.对15 个相关的RPAMP 算例(包括著名的MCNC 算例和GSRC 算例)进行了测试.更新了其中9 个算例的最好记录,另有2 个与当前的最好记录持平.得到了98.50%的平均填充率,将国内外文献中已见报道的最高平均填充率提高了0.85%.     

求解长方体Packing 问题的捆绑穴度算法

在穴度方法的基础上结合捆绑策略,为三维欧氏空间中长方体Packing问题的求解提供了一种高效的启发式算法.试算了由Loh和Nee于1992年提出的15个经典算例,对其中的困难算例LN2,取得了98.2%的空间利用率,比目前的最好纪录高1.6个百分点;对另一个困难算例LN6,取得了96.2%的空间利用率,与目前的最好纪录持平;对其他13个较为容易的算例均取得了最优的布局,与目前的最好纪录持平.总体而言,15个算例的平均空间利用率为70.96%,在整体空间利用率上达到了较好的效果.     

一种求解多维0-1背包问题的拟人算法

在项目决策与规划,资源分配,货物装载等工作中,提出了多维0-1背包问题,对这一问题,国内外学者提出了诸如模拟退火算法,遗传算法,蚁群算法及其它一些启发式算法等求解算法。该文提出了一种新的启发式求解算法。该算法使用了两个主要的思想策略,即依据物品单位容积价值的高低选择物品并对其进行标记的策略和拟人跳坑策略。用本文提出的算法,对55个测试算例进行了实算测试,得到了其中54个算例的最优解。测试结果表明,用该文提出的拟人算法求解多维0-1背包问题,计算结果的优度高,计算时间短,是求解此问题的有效算法。     

求解带硬时间窗车辆路径问题的时差插入启发式算法

针对已有求解带硬时间窗车辆路径问题时插入启发式算法结构复杂、参数多、求解效率不高的缺点,提出了求解该问题的时差插入启发式算法。该算法引入时差的概念,将时差作为启发规则的评价指标。相比已有求解该问题的经典启发式算法,该算法有参数个数少、算法结构简单等特点。应用标准测试算例测试表明,所提算法的求解质量优于Solomon的插入启发式算法和Potvin的平行插入启发式算法。     

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

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

Extended guided tabu search and a new packing algorithm for the two-dimensional loading vehicle routing problem

In this paper, we develop an extended guided tabu search (EGTS) and a new heuristic packing algorithm for the two-dimensional loading vehicle routing problem (2L-CVRP). The 2L-CVRP is a combination of two well-known NP-hard problems, the capacitated vehicle routing problem, and the two-dimensional bin packing problem. It is very difficult to get a good performance solution in practice for these problems. We propose a meta-heuristic methodology EGTS which incorporates theories of tabu search and extended guided local search (EGLS). It has been proved that tabu search is a very good approach for the CVRP, and the guiding mechanism of the EGLS can help tabu search to escape effectively from local optimum. Furthermore, we have modified a collection of packing heuristics by adding a new packing heuristic to solve the loading constraints in 2L-CVRP, in order to improve the cost function significantly. The effectiveness of the proposed algorithm is tested, and proven by extensive computational experiments on benchmark instances.     

Flow shop scheduling with blocking using modified harmony search algorithm with neighboring heuristics methods

The flow shop scheduling with blocking is considered an important scheduling problem which has many real-world applications. This paper proposes a new algorithm which applies heuristic techniques in harmony search algorithm (HSA) to minimize the total flow time. The proposed method is called modified harmony search algorithm with neighboring heuristics methods (MHSNH). To improve the initial harmony memory, we apply two heuristic techniques: nearest neighbor (NN) and constructive modified NEH (MNEH). A modified version of harmony search algorithm evolves to explore and generates a new solution. The newly generated solution is then enhanced by using neighboring heuristics. Lastly, another neighboring heuristic is applied to improve the obtained solution. The proposed algorithm is evaluated using 12 real-world problem instances each with 10 samples. The experimental evaluation is accomplished using two factors: CPU computational time and the number of iterations. For the first factor, comparative evaluation against six well-established methods shows that the proposed method achieves almost the best overall results in six problem instances out of the twelve and yields fruitful results for others. For the second factor, comparative evaluation against twelve well-regarded methods shows that the proposed method achieves the best overall results in three problem instances and obtains very good results in other instances. In a nutshell, the proposed MHSNH is an effective strategy for solving the job shop scheduling problem.     

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.     

求解二维装箱问题的强化学习启发式算法

二维带形装箱问题是一个经典的NP-hard的组合优化问题,该问题在实际的生活和工业生产中有着广泛的应用.研究该问题,对企业节约成本、节约资源以及提高生产效率有着重要的意义.提出了一个强化学习求解算法.新颖地使用强化学习为启发式算法提供一个初始的装箱序列,有效地改善启发式冷启动的问题.该强化学习模型能进行自我驱动学习,仅使用启发式计算的解决方案的目标值作为奖励信号来优化网络,使网络能学习到更好的装箱序列.使用简化版的指针网络来解码输出装箱序列,该模型由嵌入层、解码器和注意力机制组成.使用Actor-Critic算法对模型进行训练,提高了模型的效率.在714个标准问题实例和随机生成的400个问题实例上测试提出的算法,实验结果显示：提出的算法能有效地改善启发式冷启动的问题,性能超过当前最优秀的启发式求解算法.     

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.     

带静不平衡约束的矩形装填问题的启发式算法

卫星舱布局问题不仅是一个复杂的耦合系统设计问题,也是一个特殊的优化问题,具有NP难度性。解决这类问题最大的挑战在于需要优化的目标函数具有大量的被高能势垒分隔开的局部极小值点。Wang-Landau（WL）抽样算法是一种改进的蒙特卡罗方法,已经被成功地运用蛋白质结构预测等优化问题。本文以卫星舱布局优化问题为背景,首次将WL抽样算法引入矩形装填问题的求解。针对矩形装填物的特点,提出了启发式格局更新策略,以引导抽样算法在解空间中进行有效行走。为了加速搜索全局最优解,每次蒙特卡罗扫描生成新的布局时,便执行梯度法进行局部搜索。通过将局部搜索机制、启发式格局更新策略与WL抽样算法相结合,提出了一种用于解决带静不平衡约束的任意矩形装填问题的启发式布局算法。在布局优化过程中,通过在挤压弹性势能的基础上增加静不平衡量惩罚项并采用质心平移的方法,使布局系统的静不平衡量达到约束要求。另外,为了改进算法的搜索效率,提出了改进的有限圆族法用于装填物之间的干涉性判断和干涉量计算。通过对文献中两组共10个有代表性的算例进行实算,计算结果表明,所提出的装填算法是一种求解带静不平衡性能约束的任意矩形装填问题的有效算法。     

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.     

An enhanced exact procedure for the absolute robust shortest path problem

The aim of this paper is to investigate the use of heuristic information to efficiently solve to optimality the robust shortest path problem. Starting from the exact algorithm proposed by Murty and Her, we describe how this algorithm can be enhanced by using heuristic rules and evaluation functions to guide the search. The efficiency of the proposed enhanced approach is tested over a range of random generated instances. Our computational results indicate that the use of heuristic criteria is able to speed up considerably the search and that the enhanced exact solution method outperforms the state‐of‐the‐art algorithm proposed by Murty and Her in most of the instances.