多目标一维装箱问题模型算法研究

对经典一维装箱问题进行了扩展研究,提出了在考虑各个箱子容量(或体积)限制不同的情况下的一维装箱问题模型,该模型的优化目标包含所使用的箱子数最少和所使用的箱子关联的费用最少。此外,考虑到装箱运输过程中所用箱子关联费用的随机性,提出了多目标一维装箱问题的随机机会约束规划模型。利用基于NSGA-II算法的混合智能算法来求解模型。为了例证算法的有效性,给出了具体数值算例,结果表明混合智能算法对模型求解是有效的。

BFD混合禁忌搜索在一维装箱问题中的应用

针对经典的一维离线装箱问题,本文首次提出了利用降序最佳适应BFD算法与禁忌搜索算法混合使用来解决此类问题的方法,并用Microsoft Visual C++编程得以实现,详细说明了算法的关键内容与步骤,并通过算例与简单遗传算法和单纯使用禁忌搜索算法解决装箱问题进行了对比,得到以下结论:在求解一维离线装箱问题时,BFD算法与禁忌搜索算法混合使用要比单纯地使用禁忌搜索算法和简单遗传算法效果好,实用价值良好。

装箱问题的一种新算法及其性能比的证明

给出了一个一维装箱问题的新算法——ＥＰＦＦ算法，并证明了此算法在最坏情况下的性能比ｒＥＰＦＦ＝１．６．

针对经典排序问题的一种新算法的近似比分析

给定m台平行机(同型机),n个工件,寻找一种分配方案,使得把这n个工件分配到m台机器后,整体完工时间尽可能短,这个NP-难问题被称为经典排序问题。如果每个工件的加工时间满足一定的条件,则有望能在多项式时间内有效地得到最优的分配方案。Yue等对加工时间满足整除性质的经典排序问题考虑了一种新的算法,该算法总是能得到这种特殊情况的最优分配。该算法在多项式时间内能够得到最优分配,是对于一般的经典排序问题的近似算法。文章在此基础上,考虑该新算法在一般问题上的近似比。文中考虑了这个新算法的两种版本,分别得到了3/2和2-1/2 ^(q)(q∈Z^(+))的近似比。紧例子表明,文中对算法的两个版本的分析都是最优的。

城市跨区拼箱问题的算法设计及其性能比

构建了一个关于分销商通过第三方物流公司向城市中m个不同片区配送货物的模型,模型中不仅涉及各片区包裹的装箱问题,而且还需考虑跨区拼箱配送问题。通过设计算法H来实现模型中总配送成本最小化的目标,并在此基础上证明所设计算法H的性能比,即PmH/Pm*<2。