带冲突关系装箱问题的启发式求解算法

现实物流活动中大量存在的食品、药品和危险品等货物的分组包装问题属于带冲突关系的装箱问题(BPPC),其优化目标是在满足货物间冲突限制的前提下完成装箱操作,并最小化使用货箱的数量。本文从实际需求出发,基于货物之间的冲突关系、装箱顺序和货箱容量等约束建立相应的数学规划模型;随后设计了求解BPPC问题的启发式算法,算法通过迭代求解最大团结构实现货物间冲突关系的消去,根据当前货物最大团采用改进降序首次适应算法(FFD)完成货物装箱操作,并通过“洗牌”策略对已有装箱方案进行局部优化;最后,针对Iori算例数据,将以上算法与基于图着色的启发式算法进行比较分析,结果表明,本文算法是求解BPPC问题更为有效的方法。     

约束装箱问题的混合遗传算法求解

本将最佳适应法和遗传算法相结合，提出了一种新的启发式混合遗传算法对具有时间约束的装箱问题进行求解，给出了具体的算法步骤，试算结果表明基于启发式算法的混合遗传算法适合于求解各种约束条件下的大规模装箱问题。     

三维多箱异构货物装载优化及其可视化

针对七种现实约束的集装箱三维多箱异构货物装载优化问题,提出了一种基于 “块”和“空间”的启发式搜索算法。算法采用树搜索策略,根据可用空间,对每一次搜索的货物块进行评估,得到最佳的货物块,直到无可用空间或无可装载的货物为止。基于开放式标准测试数据的计算结果表明,该算法在时间效率和体积利用率上均优于已有的同类研究。并基于Net平台开发了一款3D装箱布局优化可视化软件,已在相关物流企业中得到推广应用,验证了算法的实用性。     

图着色和标号问题的蚁群优化算法

对图着色问题的最大最小蚁群算法进行了改进,测试结果表明算法有效可行.在此基础上,分别设计了求解图条件着色和标号问题的相应蚁群优化算法,并对中国地图的条件着色、三正则图的条件着色、广义Petersen图的条件着色和标号问题进行了求解优化,改进和完善了目前理论研究的结论.     

求解图着色问题的量子蚁群算法

针对经典的图着色问题,在蚁群算法的基础上结合量子计算提出一种求解图着色问题的量子蚁群算法. 将量子比特和量子逻辑门引入到蚁群算法中,较好地避免了蚁群算法搜索易陷入局部极小的缺陷,并显著加快了算法的运算速度. 通过图着色实例的大量仿真实验,表明算法对图着色问题的求解是可行的、有效的,且具有通用性.     

基于对角转轮样式的托盘装箱优化模型

针对托盘装箱问题(PLP),建立了对角转轮样式下具有托盘柔性的整数规划模型,设计了求解模型的启发式算法,并利用VB程序对模型的最优解及装箱图谱进行了讨论分析,结果表明:对角转轮样式就提高具有较大长、宽比箱子的装载效率以及解决装箱压缝问题方面具有明显的优势;而柔性也是影响托盘装载效率的重要因素之一,具有较大的回报率.     

求解资源约束项目调度问题的启发式算法综述

本文综述了求解RCPSP的启发式算法.首先在对各种优先权规则进行归纳的基础上,概述基于优先权规则的RCPSP启发式算法研究现状;其次,综述项目进度的表述方式及常用超启发式策略,汇总求解RCPSP的超启发式算法的研究成果.此外,简要介绍除上述两大类启发式算法之外的其他几种启发式算法;最后,对全文进行总结,并指出该领域几个有希望的研究方向.     

改进差分进化算法求解装载率凹费用装箱问题

研究了广泛存在于物流作业中一类新型的装箱问题,主要特征体现在箱子使用费用是关于装载率的凹函数。为求解问题,提出了一种基于分组编码策略的改进差分进化算法,以避免常规实数和整数编码方法存在放大搜索空间的不足。针对分组编码策略,定制化设计了以促进优秀基因传播为导向的新型变异和交叉操作,另外还嵌入了以物品置换为邻域的自适应局部搜索操作以增强局部搜索能力。对以往文献给出算例在不同凹费用函数下进行测试,实验结果显示所提出的算法明显优于BFD启发式算法,并且较遗传算法也有显著性改进。     

在线约束单机排序问题的启发式算法

由于约束单机排序问题是经典装箱问题的一种推广并且同经典装箱问题有一些相同的特征。本文主要讨论了经典装箱问题的一些启发式算法在在线约束单机排序问题上的推广和最坏界估计。     

分支定界算法求解带有释放时间的单机双代理调度问题

本文研究了带有释放时间的单机双代理调度问题,目标函数为极小化最大完工时间和。为了便于利用优化软件求解,建立了混合整数规划模型。考虑到该问题具有NP困难性,因此采用近似与精确算法分别求解不同规模问题。针对大规模问题,提出了优势代理优先启发式算法,并证明了其渐近最优性。针对小规模问题,设计了分支定界法进行最优求解,其中基于释放时间的分支规则和基于加工中断的下界有效地减少了运算时间。最后,通过数值测试验证了分支定界算法的有效性以及启发式算法的收敛性。     

一类带多重核元集在线装箱问题

本文讨论了一类在线变尺寸装箱问题,假定箱子的尺寸可以是不同的.箱子是在线到达的,仅当箱子到达后其尺寸才知道.给定一个带有核元的物品表及其上的核元关系图.我们的目标是要将表中元素装入到达的箱子中,保证任何箱子所装物品不互为核元,即所装物品对应的点所导出的子图是个空图,并使得所用的箱子总长最小.我们证明了该问题是NPHard的,并给出了基于图的点染色、图的团分解和基于背包问题的近似算法,给出了算法的时间复杂度和性能界.     

New lower bounds for bin packing problems with conflicts

The bin packing problem with conflicts (BPC) consists of minimizing the number of bins used to pack a set of items, where some items cannot be packed together in the same bin due to compatibility restrictions. The concepts of dual-feasible functions (DFF) and data-dependent dual-feasible functions (DDFF) have been used in the literature to improve the resolution of several cutting and packing problems. In this paper, we propose a general framework for deriving new DDFF as well as a new concept of generalized data-dependent dual-feasible functions (GDDFF), a conflict generalization of DDFF. The GDDFF take into account the structure of the conflict graph using the techniques of graph triangulation and tree-decomposition. Then we show how these techniques can be used in order to improve the existing lower bounds.     

Space defragmentation for packing problems

One of main difficulties of multi-dimensional packing problems is the fragmentation of free space into several unusable small parts after a few items are packed. This study proposes a defragmentation technique to combine the fragmented space into a continuous usable space, which potentially allows the packing of additional items. We illustrate the effectiveness of this technique using the two- and three-dimensional bin packing problem, where the aim is to load all given items (represented by rectangular boxes) into the minimum number of identical bins. Experimental results based on well-known 2D and 3D bin packing data sets show that our defragmentation technique alone is able to produce solutions approaching the quality of considerably more complex meta-heuristic approaches for the problem. In conjunction with a bin shuffling strategy for incremental improvement, our resultant algorithm outperforms all leading meta-heuristic approaches based on the commonly used benchmark data by a significant margin.     

Online variable-sized bin packing with conflicts

We study a new kind of online bin packing with conflicts, motivated by a problem arising when scheduling jobs on the Grid. In this bin packing problem, the set of items is given at the beginning, together with a set of conflicts on pairs of items. A conflict on a pair of items implies that they cannot be assigned to a common bin. The online scenario is realized as follows. Variable-sized bins arrive one by one, and items need to be assigned to each bin before the next bin arrives. We analyze the online problem as well as semi-online versions of it, which are the variant where the sizes of the arriving bins are monotonically non-increasing as well as the variant where they are monotonically non-decreasing.     

An exact algorithm for the type-constrained and variable sized bin packing problem

In this paper, we introduce an additional constraint to the one-dimensional variable sized bin packing problem. Practically, some of items have to be packed separately in different bins due to their specific requirement. Therefore, these items are labelled as different types. The bins can be used to pack either any type of items if they are empty originally or the same type of items as what they already have. We model the problem as a type-constrained and variable sized bin packing problem (TVSBPP), and solve it via a branch and bound method. An efficient backtracking procedure is proposed to improve the efficiency of the algorithm.     

Max–min Bin Packing Algorithm and its application in nano-particles filling

With regard to existing bin packing algorithms, higher packing efficiency often leads to lower packing speed while higher packing speed leads to lower packing efficiency. Packing speed and packing efficiency of existing bin packing algorithms including NFD, NF, FF, FFD, BF and BFD correlates negatively with each other, thus resulting in the failure of existing bin packing algorithms to satisfy the demand of nano-particles filling for both high speed and high efficiency. The paper provides a new bin packing algorithm, Max–min Bin Packing Algorithm (MM), which realizes both high packing speed and high packing efficiency. MM has the same packing speed as NFD (whose packing speed ranks no. 1 among existing bin packing algorithms); in case that the size repetition rate of objects to be packed is over 5, MM can realize almost the same packing efficiency as BFD (whose packing efficiency ranks No. 1 among existing bin packing algorithms), and in case that the size repetition rate of objects to be packed is over 500, MM can achieve exactly the same packing efficiency as BFD. With respect to application of nano-particles filling, the size repetition rate of nano particles to be packed is usually in thousands or ten thousands, far higher than 5 or 500. Consequently, in application of nano-particles filling, the packing efficiency of MM is exactly equal to that of BFD. Thus the irreconcilable conflict between packing speed and packing efficiency is successfully removed by MM, which leads to MM having better packing effect than any existing bin packing algorithm. In practice, there are few cases when the size repetition of objects to be packed is lower than 5. Therefore the MM is not necessarily limited to nano-particles filling, and can also be widely used in other applications besides nano-particles filling. Especially, MM has significant value in application of nano-particles filling such as nano printing and nano tooth filling.     

超尺寸物品装箱问题及其算法

本文探讨一类新装箱问题-超尺寸物品装箱问题。针对实际解决该问题的两涉法，我们提出了一个评价效率更高的目标函数，证明了在此目标函数下两步法的渐近最坏比不小于2，并给出了渐近量坏比与拆分次数的关系。最后本文提出了一种不同于两步法的新在线算法MA，证明了在新目标函数下其渐近最坏比不超过7/4。     

超尺寸物品装箱问题

本文给出一类新的装箱问题，超尺寸物品装箱问题。就实际解决该问题所普遍彩的两步法，证明了当采用经典目标函数并且拆分次数不超过2时，第二步采用FFDLR的渐进最坏比为3/2。进而针对超尺寸物品装箱问题的算法提出了一个评价效率更高的目标函数。证明了在此目标函数下，当不限制物品的最大尺寸时，第二步采用最优装法两步法的渐近最坏比为2。最后，给出渐近最坏与拆分次数的关系。     

Relaxations and exact solution of the variable sized bin packing problem

We address a generalization of the classical one-dimensional bin packing problem with unequal bin sizes and costs. We investigate lower bounds for this problem as well as exact algorithms. The main contribution of this paper is to show that embedding a tight network flow-based lower bound, dominance rules, as well as an effective knapsack-based heuristic in a branch-and-bound algorithm yields very good performance. In addition, we show that the particular case with all weight items larger than a third the largest bin capacity can be restated and solved in polynomial-time as a maximum-weight matching problem in a nonbipartite graph. We report the results of extensive computational experiments that provide evidence that large randomly generated instances are optimally solved within moderate CPU times.