面向纸板三维装箱问题的剩余空间最优算法

针对瓦楞纸板在装箱过程中遇到的多种实际约束,提出一种基于剩余空间最优和多种实际约束的快速求解算法.该算法先根据纸板的先进后出和组合装载约束,确定纸板的装箱序列,接着将三维装箱问题转换成带高度约束的二维装箱问题,再基于剩余空间最优策略,选择空间的分割方式和纸板的放置方式,并对剩下的空间进行合并和重新分割,从而求解得到纸板...     

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

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

基于装箱树算法求解集装箱装载问题的研究

研究了把同种货物装入一个集装箱内，使箱子内的空间利用率为最大的集装箱装载问题．首先，运用启发式算法,充分考虑了箱子和货物的方位、剩余空间等问题．然后，通过主空间装填、空间分层、剩余空间优化等建立一个装箱树．最后，用Java程序完成装箱树算法，并实现集装箱装载问题的求解．用实例验证了算法的可行性，能够投入实际应用．     

面向梯形箱子的三维装箱问题算法研究

针对梯形箱子的三维装箱问题,提出了一种基于空间分割的构造性启发式算法,根据梯形箱子三维装箱问题的特点,设计了相应的空间分割策略、空间合并策略与空间重组策略,在此基础上加入遗传算法,提高算法局部与全局搜索能力。实验结果表明,该算法能有效处理梯形箱子三维装箱问题。     

基于动作空间的三维装箱问题的确定性高效率求解算法

三维装箱问题要求将有限个三维矩形物体尽可能多地装入到一个三维矩形箱子中,使得箱子的填充率即体积利用率最大.在求解三维装箱问题的穴度算法的基础之上,进一步做了以下改进:(1)将当前剩余空间中可能放入的每个体积最大的三维矩形虚拟物体所对应的空间定义为动作空间,在动作空间内放入物体并使穴度的定义体现放入物体与动作空间的吻合程度;(2)在物体放入位置的选择上直接体现"金角银边草肚皮"的思想,每一步只选择最靠近箱子边缘的一个动作空间来装载物体;(3)结合捆绑策略,将形状大小相同的物体捆绑为一个较大的矩形块进行放入,对捆绑块形状大小的选择为在不超出动作空间的前提下尽量用物体填满该空间的两至三个维度.实验结果表明,改进后的穴度算法在付出很少的开销代价的情况下显著地提高了箱子的填充率.     

求解三维装箱问题的多层树搜索算法

提出了一种求解三维装箱问题的多层树搜索算法, 该算法采用箱子–片–条–层–实体的顺序生成装载方案, 装载方案由实体表示. 该算法由3层搜索树构成. 第1层为三叉树, 每个树节点的3个分叉分别对应向实体中填入XY面平行层、XZ面平行层、YZ面平行层; 第2层为二叉树, 每个树节点的两个分叉分别对应向层内装载两个相互垂直的最优条; 第3层为四叉树, 用于将同种的多个箱子生成片. 在同时满足摆放方向约束和完全支撑约束的前提下, 该算法求解BR12~BR15得到的填充率高于现有装箱算法.     

受启动空间约束的装箱问题

提出了一种带有启动空间的约束装箱问题(start-up bin packing problem,简称SBPP),即不同类型的物品放入同一箱子中需要一个启动空间.该问题在工作分配、任务调度和日常生活中的包装等问题中有着广泛的应用背景.给出了一个求解SBPP的线性脱线算法C-NF,其最坏情况渐近性能比为2,与启动空间的大小无关.对该算法的平均性能进行了实验分析.另外,还分析了SBPP的在线特性,指出大量的经典在线装箱算法应用于SBPP都不存在确定的最坏情况渐近性能比,也给出了一种具有确定的最坏情况渐近性能比的在线算法.     

分支定价方法求解带二维装箱约束的车辆路径问题EI北大核心CSCD

面向家具、电器等货物的物流配送场景,研究带二维装箱约束的车辆路径问题(2L–CVRP),构建了2L–CVRP的混合整数线性规划模型.为求解大规模2L–CVRP,构建了该问题集合划分模型,提出基于分支定价的方法.针对分支节点的松弛模型,基于列生成策略将其分解为线性规划主问题、带资源和二维装箱约束的最短路径子问题,并提出基于ng-route松弛策略的标签算法和基于禁忌搜索的装箱算法有效求解复杂子问题.仿真结果表明,提出的方法可高效求解大规模2L–CVRP,其中ng-route松弛策略能有效提升算法求解效率,研究成果为装箱约束下大规模车辆路径问题的高效求解提供了有效途径.     

互联网信息组织和规划中的带拒绝装箱问题

讨论如下定义的带拒绝装箱问题：设有许多等长的一维箱子，给定一个物品集，每个物品有两个参数：长度和罚值．物品可以放入箱子也可被拒绝放入箱子．如果将物品放入箱子，则使该箱剩余长度减少．一旦需将某一物品放入某一箱中，而该箱的剩余长度不够时，则需启用新箱子．如果物品被拒绝放入任何箱中，则产生惩罚．问怎样安排物品使所用箱子数与未装箱的物品总罚值之和最小．该问题是一个新的组合优化问题，来源于内部互联网的信息组织和规划．该文首先给出一个最优解值的下界估计，它可用于分枝定界法求最优解．由于该问题是强NP-难的，该文进一步研究它的离线和在线近似算法的设计与分析．文中给出一个离线算法，其绝对性能比为2；同时给出一个在线算法，其绝对性能比不超过3，渐近性能比为2，还对算法性能比的下界进行了讨论．     

基于多元优化算法的三维装箱问题的研究

用多元优化算法（Multi-variant optimization algorithm,MOA）实现三维装箱问题的求解.算法通过随机放置和局部调整从而逐步逼近最优解.随机放置是将随机选择的几个箱子装入容器中;局部调整是根据目标函数值对随机放置容器的箱子序列作局部调整优化;通过递推的随机放置和局部调整优化,目标函数值逐步逼近最优值,从而获得一个较为理想的三维装箱方案.算法通过对BR1~BR10共1000组三维装箱问题测试实例的测试仿真,得到理想的装箱效果,说明用多元优化算法实现三维装箱问题的有效性和可行性.     

考虑装卸频率的大规模车辆路径问题研究

通过分析大规模车辆路径问题的特点和求解难点,从我国的配送实践出发,引入装卸频率的概念,从新的视角认识大规模车辆路径问题,建立了考虑装卸频率的车辆路径优化多目标规划模型,并设计了改进的混合遗传算法进行求解。实验结果表明,该算法能够大幅降低企业配送成本和配送的装卸频率,具有实际参考价值和应用前景。     

基于改进遗传算法的3DNoC低功耗映射研究

二维片上网络（Two-Dimensional Network-on-Chip,2D NoC）在面积、功耗、布局布线、封装密度等方面都已达到了瓶颈。与2D NoC相比,三维片上网络（Three-dimensional Network-on-Chip,3D NoC）有着诸多优势,因此3D NoC逐渐成为一个重要的研究方向。随着3D NoC集成度的提高,低功耗映射逐渐成为研究热点。将贪心算法的思想与遗传算法相结合提出一种改进的遗传算法,用以解决3D NoC低功耗映射问题,相对于传统遗传算法,改进遗传算法具有更优的搜索能力。仿真结果表明,采用改进后的遗传算法解决3D NoC映射问题可以降低功耗,从总体趋势来看随着处理单元数量的增加功耗降低幅度逐渐增大,在120个处理单元情况下总功耗可降低14%。     

基于改进元胞多目标遗传算法的机床主轴优化

为了进一步提高元胞遗传算法在求解多目标优化问题时的收敛性和分布性。在多目标元胞遗传算法的基础上,引入了三维空间元胞,提出了三维元胞多目标遗传算法。采用多目标基准测试函数对该算法进行了测试,并将其与目前比较流行的几种多目标遗传算法进行对比。结果表明,此种算法在收敛性和分布性上取得了更好的效果。采用以上这几种算法分别对机床主轴多目标优化问题进行了求解,相比其他几种算法,改进的多目标元胞遗传算法得到了更优的结果,说明了改进的算法在求解此问题时行之有效。     

A C-tree decomposition algorithm for 2D and 3D geometric constraint solving

In this paper, we propose a method which can be used to decompose a 2D or 3D constraint problem into a C-tree. With this decomposition, a geometric constraint problem can be reduced into basic merge patterns, which are the smallest problems we need to solve in order to solve the original problem in certain sense. Based on the C-tree decomposition algorithm, we implemented a software package MMP/Geometer. Experimental results show that MMP/Geometer finds the smallest decomposition for all the testing examples efficiently.     

一种改进的动态k-均值聚类算法

针对经典k_均值聚类方法只能处理静态数据聚类的问题,本文提出一种能够处理动态数据的改进动态k-均值聚类算法,称为Dynamical K-means算法.该方法在经典k-均值方法的基础上,通过对动态变化的数据集中 新加入样本进行分析和处理,根据聚类目标函数改变的实际情况选择最相似的类别进行局部更新或进行全局经典k_均值聚类,有效检测发生聚类概念漂移和没有发生聚类概念漂移的情况,从而实现了动态数据的在线聚类,避免了经典k_均值方法在动态数据中每次都要对全部数据重新聚类而导致算法速度过慢的问题.标准数据集和人工社会网络数据集上的实验结果表明,与经典k_均值聚类方法相比,本文提出的动态k_均值聚类方法能快速高效地处理动态数据聚类问题,并有效地检测动态数据聚类过程中所产生的概念漂移问题.     

Optimization Algorithms on Subspaces: Revisiting Missing Data Problem in Low-Rank Matrix

Low-rank matrix approximation has applications in many fields, such as 3D reconstruction from an image sequence and 2D filter design. In this paper, one issue with low-rank matrix approximation is re-investigated: the missing data problem. Much effort was devoted to this problem, and the Wiberg algorithm or the damped Newton algorithm were recommended in previous studies. However, the Wiberg or damped Newton algorithms do not suit for large (especially “long”) matrices, because one needs to solve a large linear system in every iteration. In this paper, we revitalize the usage of the Levenberg-Marquardt algorithm for solving the missing data problem, by utilizing the property that low-rank approximation is a minimization problem on subspaces. In two proposed implementations of the Levenberg-Marquardt algorithm, one only needs to solve a much smaller linear system in every iteration, especially for “long” matrices. Simulations and experiments on real data show the superiority of the proposed algorithms. Though the proposed algorithms achieve a high success rate in estimating the optimal solution by random initialization, as illustrated by real examples; it still remains an open issue how to properly do the initialization in a severe situation (that is, a large amount of data is missing and with high-level noise).     

基于改进人工萤火虫算法的装配序列规划研究

装配是装备保养维护的重要环节,高效和无损地装配好拆卸维护的零件在战场上尤为重要.为了解决装配序列规划最优解问题,根据装配序列规划的特点,提出了基于人工萤火虫算法的离散SA-GSO算法.首先利用干涉矩阵对装配序列进行了可行性分析,并根据操作实际设定了适应度函数;然后针对人工萤火虫算法存在的易早熟等缺陷,利用模拟退火原理进行优化并对算法进行离散化,以适用于装配序列最优解问题;最后进行了实例验证,实验结果证明了该算法的可行性及有效性.     

一类特殊的非抢占式周期任务的调度方法

现实世界中针对许多任务的资源调度分配和使用具有时效性,对该类任务的调度问题目前的研究还较少。针对此类调度问题,分析其特点,明确其与已有调度模型研究问题的区别,提出新的非抢占式周期任务调度模型,并证明了该类问题为NP完全问题。在此基础上,给出了一种求解最优解的模式剪枝算法,以及一种求解近似解的快速求解算法。相关实验表明,提出的两种算法能够针对不同的需求场景分别对调度问题进行高效求解。     

混合型蛙跳算法及其应用研究*

为了提高蛙跳算法求解无约束连续优化问题的能力,提出了一种改进型混合蛙跳算法。为验证该算法求解函数优化问题的高效性,将其与基本蛙跳算法进行比较实验,结果表明该算法的解精度及收敛速度均优于基本蛙跳算法,更适用于求解复杂的无约束连续优化问题。     

一种面向维修资源配送调度的遗传-烟花混合算法

为减轻资源供应不及时对维修活动顺利开展的影响,本文针对配送式供应保障,基于带时间窗的多配送中心车辆路径规划问题提出了一种半开放式的协同配送调度模型,使得多个资源库存中心之间达成了协同合作与互相保障,从而减少了资源的供应时长和调度成本,提高了全局调度效率。为高效地求解该模型,本文提出了一种遗传-烟花混合算法,混合算法在经典遗传算法的基础上引入了烟花算法的爆炸算子以增加种群优秀个体的数量,丰富种群基因的多样性,从而提高算法的寻优能力。通过仿真实验对比,证明了爆炸算子对遗传算法容易“早熟”的缺点有所改善,且混合算法具有更高的求解效率。